Content #
合并策略Size-Tiered Compact Strategy，简称 Tiered。BigTable 和 HBase 都采用了 Tiered 策略。它的基本原理是，每当某个尺寸的 SSTable 数量达到既定个数时，将所有 SSTable 合并成一个大的 SSTable。这种策略的优点是比较直观，实现简单，但是缺点也很突出。下面我们从 RUM 的三个角度来分析下：
- 读放大
执行读操作时，由于单个 SSTable 内部是按照 Key 顺序排列的，那么查找方法的时间复杂度就是 O(logN)。因为 SSTable 文件是按照时间间隔产生的，在 Key 的范围上就会存在交叉，所以每次读操作都要遍历所有 SSTable。如果有 M 个 SSTable，整体时间复杂度就是 O(MlogN)。执行 Compact 后，时间复杂度降低为 O(log(MN))。在只有一个 SSTable 时，读操作没有放大。
- 写放大
Compact 会降低读放大，但却带来更多的写放大和空间放大。其实 LSM 只是推迟了写放大，短时间内，可以承载大量并发写入，但如果是持续写入，则需要一部分 I/O 开销用于处理 Compact。
你可能听说到过关于 B+Tree 和 LSM 的一个争论，就是到底谁的写放大更严重。如果是采用 Tiered 策略，LSM 的写放大比 B+Tree 还严重。此外，Compact 是一个很重的操作，占用大量的磁盘 I/O，会影响同时进行的读操作。
- 空间放大
从空间放大的角度看，Tiered 策略需要有两倍于数据大小的空间，分别存储合并前的多个 SSTable 和合并后的一个 SSTable，所以 SAF 是 2，而 B+Tree 的 SAF 是 1.33。