对于LSM-Tree设计的若干思考(分层原因、same size

LSM-Tree是现代NoSQL, NewSQL数据组织和索引的基本结构，一般认为是从1996年Acta Inf.的一篇文章为起源，在随后至今的25年的时间里，对它的研究和优化从未中断过，主要是由于其提供的高超的写吞吐量和时间顺序性，非常契合现代互联网的应用；而较为宽松的结构，为后来开发者提供了非常大的优化空间。下面这张图显示了这些年对LSM-Tree的优化方向。

image.png

Hbase/BigTable/LevelDB/Cassendra/InfluxDB，基本都采用了LSM-Tree的结构。

这样一个经典而广泛使用的数据结构是值得深入学习的。最近我在学习过程中思考了一些问题（不断更新），在这里分享出来，以供复习和讨论。

0. LSM-Tree的基本结构

分层结构，每层都有特定的数据结构在磁盘上用以存储数据，各层的Capacity是逐渐放大的，有常量的放大比例。
在分层结构之上，有一个Memstore，写入时只需写入WAL和MemStore即可。
MemStore大小达到一个阈值时，会flush到Level0；同理，各层level之间会定期/不定期的进行compaction，整合到下一层。
类似于日志写，修改和删除不会去找原record，而只是一个特殊的insert而已。
对于点查询，可以找最新的（最上层的）一条record。
对于范围查询，要扫描全部的levels。

MemStore的数据结构：通常为红黑树、跳表等；
Disk Level的数据结构：通常为SSTable、初版实现为B+树。

1. 为什么要分层？

先给出一个统一的回答：为了最小化I/O代价。
然后我们来解释为什么分层可以最小化I/O代价。
首先我们考虑不分层的，只有一个Memstore和一个disk level的情景。假设disk level由B+树实现。
我们分别考虑内存占比很大和很小的情况：

• 如果内存占比非常大，大到几乎不需要去flush进磁盘，那么此时的性能瓶颈则不在I/O,而是在于内存结构的维护，CPU开销；（此时退化成内存数据结构了）
• 如果内存占比非常小，小到只能容纳一条entry，那么每次插入都要flush磁盘，则此时瓶颈完全是I/O，每次都几乎要读出所有的磁盘叶子节点，然后再写回去；（此时退化成一颗B+树，甚至比B+树还要慢）。

在这两种极端的情况下，中间肯定会有一个平衡点，能够使得CPU开销+disk I/O开销总和是最小的，此时内存和外存的比例是适中的，这就是只有1个disk level的最佳情况了。

上面是一些比较感性的分析，我们把它形式化一下，引入一个重要的参数M。这个M表示，每次merge时写入一个新页时，平均有几条entry来自memstore。或者说，这个新页中，来自memstore的比例。对于一些常见的例子，如果这个比例不足0.5%，这个单level的LSM-Tree就不如B+-Tree的性能好。

借助参数M，我们可以表示一次插入的代价，假设顺序读写磁盘1页的代价是X，那么做一次merge，就要一读一写2X的代价，这2X的代价可以让M条内存的数据落盘，那么平均每条数据插入的I/O代价就是。

可以看到，如何降低插入的I/O代价呢？只能增大M，就是增大内存的比例，但是也不能太大，否则CPU开销将成为瓶颈，正如我们刚才所描述的。

但是这就是问题的极限了么？不是的。增大M还有一种途径就是缩小外存，把disk level那一层的size变小，就可以降低平均插入的I/O代价。但是缩小disk level的size不是相当于把LSM-Tree的承载容量变得很小么？因此我们要分层，形成多级的level，下层都比上层要大，但是相邻两层的size比例又不会很悬殊，以尽可能减小I/O代价。

我们假设各层的size比例是固定的，都是20倍，分别计算只有1层和2层的插入代价来解释。假设Memstore是1GB，一页有421个条目。

• 1层：disk level的大小是20*20+20=420GB，一次merge每写一页，要从1层读420页，一读一写I/O代价是840次，平均插入代价=2次IO / 平均1个条目被写入=2（平均每次插入的I/O代价）
• 2层：disk level1=20GB, disk level2=400GB，一次merge(0->1)每写一页从1层读20页写20页，共40次I/O；一次merge(1->2)从1层读一页写一页，从2层读20页写20页，共42次I/O。加起来共82次。
  平均插入代价(Level1)=2次IO / 平均20个条目被写入 = 0.1 （平均每次插入的I/O代价）
  平均插入代价（Level2）= (2次Level2 IO + 1/20次Level1 I/O)/平均20个条目被写入=0.1025
  总平均插入代价0.2025

可以看到，2层的I/O，比1层的I/O，少了10倍还多。

那么我们总结一下，LSM-Tree为了在保证数据总存储容量不变的前提下，尽可能缩小内存和外存的Size比例以减少I/O代价而想出来的方法。

2. 为什么各层的放大比例是一样的？

首先说明，各层的放大比例一致是数学推导得出的结论，在这种情况下性能最佳。虽然看上去非常死板，但是在后面的优化中，是一根不能触碰的“红线”，即使会带来一些麻烦。
第二点要说明的，放大比例一样是基于一个假设，就是在最后一层disk level K的size是固定的，此时放大比例才是一样的能达到最佳。如果要固定各层的size之和，然后确定放大比例，则不是相同的才是最佳的。

下面我们来证明。
假设insert是以每秒R Bytes写入LSM-Tree的，那就要求每层之间数据流通速度也是R。一般的，对于到，要有每秒R Bytes的流出，其实就是页的读入(for merge)，然后因此要有页的读入，然后有的写入，共有次I/O。那么K个层级都有这么多I/O，总共的IO代价称为H，如下式。我们对H求导，找极值即可，最终结论就是放大比例有应该相等。

image.png

如果要保证磁盘总容量恒定，则是另外一种情况，结论放在下面，不作证明。层数越大，放大比例越小了。

image.png

3. 为什么SSTable要分区/分多个文件存储？

image.png

现代典型的LSM-Tree长成上图这个样子，Level0按照Tier compaction，Level1及后面按照Level Compaction。看起来很合理，一行比一行多，下面我们再放一个初版LSM-Tree的样子。

image.png

可以看到初版中的B+树实现法，是一行比一行大，而不是一行比一行多。为什么会有这种差异呢？
还是一句话概括：为了减少后台compaction操作对前台CRUD的影响。
Compaction对LSM-Tree结构的数据索引的影响是非常大的，想想看，如果每层仅有一个SSTable，进行层之间compaction的时候就会锁住两层的数据，会阻塞掉大部分的前台的query。
那可不可以边compaction，边query呢？不太可以，可以的话也很复杂，因为SSTable中包含了许多的meta data(极值范围，blocks位置等)和index data(布隆过滤器等) ，这些数据在compaction的时候都要进行调整，很难做到同时进行。
那此时就有一个idea，compaction能不能更细粒度一点，也就是说，每次compaction不要把一整个level都合并掉，只合并部分，比如30%，那剩下的70%还仍然可以进行Query。这个思路确实可以，也就是现代的实现方案，进一步，还可以让数据在每一层的时候就有序，这样更容易控制，查询也更快。但是实现中，如何控制一个合适的SSTables数量、各SSTable如何均衡等一些问题也要细粒度的考量。

那初版实现没有分区，是因为没想到这个事情么？不是的。B+树不同于SSTable，各子树之间天生就存在着独立性和有序性，每次compaction的时候，选择一部分子树，可以达到同样的效果。

（未完待续）
（后面继续考虑开一篇新文章对LSM-Tree的各种现代版优化做一个总结，包括软硬件等。本文后面会继续对LSM-Tree设计的核心问题进行思考总结，持续更新）