最近看了一篇 Paper，Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging，让我觉得受益匪浅。里面作者详细的用公式列出来不同的 Compaction 策略对不同的操作的 I/O 影响，以及空间占用，从而指导作者做了相关的优化，构建了 Dostoevsky。
因为论文写得非常详细，我觉得也有必要好好的整理一下，顺带让自己重新学习下 RocksDB 相关的代码。不过在开始之前，还是先吐槽下这个 KV 的名字，竟然叫做 Dostoevsky，也就是大名鼎鼎的陀思妥耶夫斯基，也不觉得念出来多绕口。
Tiered Compaction vs Leveled Compaction
大家应该都知道，对于 LSM 来说，它会将写入先放到一个 memtable 里面，然后在后台 flush 到磁盘，形成一个 SST 文件，这个对写入其实是比较友好的，但读取的时候，很可能会遍历所有的 SST 文件，这个开销就很大了。同时，LSM 是多版本机制，一个 key 可能会被频繁的更新，那么它就会有多个版本留在 LSM 里面，占用空间。
为了解决这两个问题，LSM 会在后台进行 compaction，也就是将 SST 文件重新整理，提升读取的性能，释放掉无用版本的空间，通常，LSM 有两种 Compaction 方式，一个就是 Tiered，而另一个则是 Leveled。
上图是两种 compaction 的区别，当 Level 0 刷到 Level 1，让 Level 1 的 SST 文件达到设定的阈值，就需要进行 compaction。对于 Tiered 来说，我们会将所有的 Level 1 的文件 merge 成一个 Level 2 SST 放在 Level 2。也就是说，对于 Tiered 来说，compaction 其实就是将上层的所有小的 SST merge 成下层一个更大的 SST 的过程。
而对于 Leveled 来说，不同 Level 里面的 SST 大小都是一致的，Level 1 里面的 SST 会跟 Level 2 一起进行 merge 操作，最终在 Level 2 形成一个有序的 SST，而各个 SST 不会重叠。
上面仅仅是一个简单的介绍，大家可以参考 ScyllaDB 的两篇文章 Write Amplification in Leveled Compaction，Space Amplification in Size-Tiered Compaction，里面详细的说明了这两种 compaction 的区别。
Compaction Analyzing
无论是 Tiered 还是 Leveled，它们都各有优劣，我们也需要根据实际情况进行选择，直观来说，Leveled compaction 会有写放大问题，而 Tiered compaction 则会有空间放大问题。在 Dostoevsky 里面，作者定量分析了不同的 compaction 在不同 case 情况下面的 I/O 开销，以及两种 compaction 的空间占用情况。
| 术语 | 定义 | 单位 |
|---|---|---|
| N | 总的 entries 个数 | entries |
| L | 总的 Level 层数 | levels |
| Lmax | 最大的 level 层数 | levels |
| B | 在一个存储 block 里面的 entries 个数 | entries |
| P | 一个 block 的 buffer size | blocks |
| T | 相邻两个 level 之间的 size 比 | |
| Tlim | Level L 相对于 Level 1 的 size 比 | |
| M | 最大的给 Bloom filters 分配的内存 | bits |
| Pi | 在 Level i Bloom filters 的失败率 | % |
| s | 对于 range 查询的可选择率 | % |
| R | 没有结果的点查开销 | I/Os |
| V | 有结果的点查开销 | I/Os |
| Q | range 查询的开销 | I/Os |
| W | 更新开销 | I/Os |
| K | 从 Level 1 到 Level L - 1 的 runs 个数范围 | runs |
| Z | Level L 的 runs 个数范围 | runs |
| μ | 顺序读相比随机读速度差异 | |
| φ | 写入相比读取的开销差异 |
这里说下 runs 的定义，根据 Wiki Log-structured merge-tree，可以知道一个 runs 就是一个或者多个有序不重叠的 SST 文件。从 Level 1 层开始，Leveled 的 runs 就是 1，而 Tiered 则可能是 T - 1。
对于 Level 0 来说，一个 buffer 包含 B * P 个 entries，通常来说，Level i 就有 B * P * T ^ i 个 entries。而大的 Level 择优 N * (T - 1) / T 个 entries。L 则是 ㏒T(N / (B * P) * (T - 1) / T) )。
对于两种不同的 compaction，下图列出了不同情况下面的 I/O 开销
Updates
对于 Update 来说，一个 entry 的开销其实是依赖于后台的 compaction merge 操作。对于最坏的情况，也就是 entry 在最大的 Level 上面有更新，那么只有这个 entry 新的版本到达了最大 Level，老的版本才会被删除。
对于 Tiered 来说，每次 merge 可以认为是 O(1) 的开销，那么总共就是 O(L) 的开销，因为每次 merge 我们不可能只移动一个 entry，而是会批量的处理 B 个 entries，所以总的开销可以认为是 O(L / B)。
而对于 Leveled 来说，因为 Level i 的一个 run 可能会跟上一层的 i + 1 T 个 runs 一起merge。所以，一个 entry 的开销可以认为是 O(T)，总共的开销就是 O(L * T / B)。
Point Lookups
对于点查来说，最坏的情况就是数据不存在，我们会在每层都进行检查，而每层的 Bloom filter 都返回 false，这样对于 Leveled 来说，开销就是 O(L)，而 Tiered 则是 O(L * T)。
通常，我们都给每个 entry 使用 10 bits 来作为 Bloom filter，这样 false positive rate （FPR）则接近 1%，实际中，每层的 Bloom filter 的 bits 都是一样的，所以最大层的 Bloom filter 会占用最多的内存，而最大层的 FPR Pi 则是 O(e ^ (-M / N))，因为其他所有的层的 FPRs 都有同样的 Pi，所以对于 Leveled 来说，它的开销是 O(e ^ (-M / N) * L)，而 Tiered 则是 O(e ^ (-M / N)) * L * T。
不过，现在已经有一些 Paper 指出，不一定每层的 Bloom filter bits 需要一致，譬如 Monkey 这篇 paper 就提到给不同的层设置不同的 Bloom filter bits，能有效的减少 I/O 开销，能将 Leveled 的减少到 O(e ^ (-M / N))， Tiered 减少到 O(e ^ (-M / N)) * T，这个后续会分析 Monkey。
而对于 RocksDB 来说，它提供了一个参数可以在最大层不使用 Bloom filter，对于一些业务来说，如果我们能确定要查询的 key 一定在 LSM 里面，那么最大层不使用 Bloom filter 可以有效的节省内存，这样我们也可以增大 bits，或者让 block cache 里面存放更多的 entries。
Range lookups
在 Dostoevsky 里面，long range lookups 的定义就是如果访问的 blocks 数量满足 s / B > 2 * Lmax，那么就认为是 long。
通常来说，range lookups 是不能用 Bloom filter 的，所以对于 Leveled 来说，short 总共需要 O(L) 的开销，而 Tiered 则是 O(L * T)。而对于 long 来说，Leveled 则是 O(s / B)，而 Tiered 则是 O(T * s / B)。
Space Amplification
对于空间放大，我们定义如下，amp = N / unq - 1，unq 就是 unique entries 的数量。
对于 Leveled 来说，最坏情况就是从 Level 1 到 L - 1，一个 entry 都有更新，那么在 L 层，就可能会有 1 / T 个废弃的 entry，所以总的空间放大就是 O(1 / T)，而对于 Tiered 来说，最坏情况就是从 Level 1 到 L - 1 的所有更新都 merge 到了 Level L，也就是 L 层包含所有的 entries 数据，这时候的放大就是 O(T)。
小结
上面简单的列出来两种不同的 Compaction 在不同的 case 下面的 I/O 开销，以及空间放大问题。简单来说，Leveled 会有写放大问题，而 Tiered 则会有读放大以及空间放大问题。对于 Dostoevsky 来说，它并没有单纯的采用 Leveled 或者 Tiered，而是采用了一种更加巧妙的方式。
Lazy Leveling
首先就是 Lazy Leveling，原理非常简单，也就是混合了 Tiered 以及 Leveled，在最大层使用 Leveled，而其它层使用 Tiered。这样最大层的 runs 就是 1，而其他层的则是 T - 1。另外，因为小的 Level 现在使用的是 Tiered，为了加速点查，Dostoevsky 为不同的 Level 的 Bloom filter 使用了不同的内存。
上图列出了使用 Lazy Leveling 跟其他两种 compaction 方式的对比，可以看到，在不同 case 下面的最坏开销其实还是挺不错的。譬如对于 update 来说，在 Level 1 到 L - 1 层，开销都是 O(T)，而 L 层则是 O(L)，那么总的开销就是 O((T + L) / B)。而对于空间放大来说，因为最大层有最多的 entries，所以整体的开销仍然接近于 O(1 / T)。
但是，虽然 Lazy Leveling 能在很多方面有折中，但在特定场景下面仍然赶不上 Tiered 或者 Leveled compaction，所以这世界并没有银弹，实际并不是只有一个单一的 compaction 策略。
Fluid LSM-Tree
在 Lazy Leveling 基础上面，Dostoevsky 引入了 Fluid LSM-Tree，其实原理也很简单，相比于 Lazy Leveling 最大层是 Leveled，其它层是 Tiered，Fluid 使用了一个可调解的方式，在最大层使用最多 Z runs，而其它层最多使用 K runs。
可以发现：
- Z = 1， K = 1，就是 Leveled Compaction
- Z = T - 1， K = T - 1，就是 Tiered Compaction
- Z = 1， K = T - 1，就是 Lazy Leveling
上图是使用 Fluid 模型之后不同 case 的开销，公式太复杂就不解释了。既然有了 Fluid，下一个问题就显而易见了，我们如何去确定 Z 和 K，这就需要 tuning 了。这方面 Dostoevsky 貌似也没有啥黑科技，就是不断调整 Z，K 和 T，在不同的应用场景去测试，从而找到一个比较优的配置。
结语
LSM 虽然是现今主流的一种存储引擎实现方式，但它仍然有一些不足，而业界也一直在对它进行优化，用以适配更多的场景。在 TiKV，我们也在基于 RocksDB 做另一款存储引擎，如果你对这方面感兴趣，欢迎联系我 tl@pingcap.com。
