17 | 存储系统：从检索技术角度剖析LevelDB的架构设计思想

作者回复: 这是一个好问题！实际上，这也是levelDB的一个瓶颈。当immutable memtable还没有完全写入磁盘时，memtable如果写满了，就会被阻塞住。 因此，Facebook基于Google的levelDB，开源了一个rocksDB，rocksDB允许创建多个memtable，这样就解决了由于写入磁盘速度太慢导致memtable阻塞的问题。

作者回复: 你的问题我重新整理一下，尤其是level 0层怎么处理，这其实是一个很好的问题: 问题1:level 0层到level 1层合并的时候，level 0层是有多少个sstable参与合并？ 回答:按道理来说，我们应该是根据轮流选择的策略，选择一个level 0层的sstable进行和下层的合并，但是由于level 0层中的sstable可能范围是重叠的，因此我们需要检查每一个sstable，将有重叠部分的都加入到合并列表中。 问题2:level n层中的一个sstable要和level n+1层中的所有sstable进行合并么？ 回答:不需要。如果level n层的sstable的最大最小值是begin和end，我们只需要在level n+1层中，找到可能包含begin到end之间的sstable即可。这个数量不会超过10个。因此不会带来太大的io。 问题3:为什么level n层的sstable和level n+1层的合并，个数不会超过10个？ 回答:在level n层的sstable生成的时候，我们会开始判断这个sstable和level n+1层的哪些sstable有重叠。如果发现重叠个数达到十个，就要结束这个sstable文件的生成。 举个例子，如果level n+1层的11个sstable的第一个元素分别是[100，200，300，400，……，1000，1100]，即开头都是100的整数倍。那么，如果level n层的sstable文件生成时，准备写入的数据就是[100，200，300，400，……，1000，1100]，那么在要写入1100的时候，系统会发现，如果写入1100，那么这个sstable文件就会和下一层的11个sstable文件有重叠了，会违反规则，因此，这时候会结束这个sstable，也就是说，这个sstable文件中只有100到1000十个数。然后1100会被写入到一个新的sstable中。

作者回复: lsm树和b+树会有许多不同的特点。但是如果从使用场景来看，最大的区别就是看读和写的需求。 在随机读很多，但是写入很少的场合，适合使用b+树。因为b+树能快速二分找到任何数据，并且磁盘io很少；但如果是使用lsm树，对于大量的随机读，它无法在内存中命中，因此会去读磁盘，并且是一层一层地多次读磁盘，会带来很严重的读放大效应。 但如果是大量的写操作的场景的话，lsm树进行了大量的批量写操作优化，因此效率会比b+树高许多。b+树每次写入都要去修改叶子节点，这会带来大量的磁盘io，使得效率急剧下降。这也是为什么日志系统，监控系统这类大量生成写入数据的应用会采用lsm树的原因。

作者回复: 1.结论是对的，不过有一个小细节要注意一下，下一层的数据，是更老的一个数据，不一定是“一样的”。由于它不够上一层的新，因此可以放弃。 2.是的。你把这一个约束规则找到了！因为有着这一条约束规则，可能某一层的sstable在某个时刻数量很多，但是每个文件都很小，如果通过文件数量限制，就使得这一层可能存不了什么数据。因此用总容量进行限制更合理。

作者回复: 因为对于b+树，当内存中的change buffer写满的时候，会去更新多个叶子节点，这会带来多次磁盘IO;但lsm当内存中的memtable写满时，只会去写一次sstable文件。因此它们的主要差异，还是在怎么将数据写入磁盘上。 当然所有的系统设计都是有利有弊，要做权衡。b+树写入磁盘后，随机读性能比较好;而lsm树写磁盘一时爽，但要随机读的时候就不爽了，它可能得在多层去寻找sstable文件，因此随机读性能比b+树差。

作者回复: 1.虽然跳表和b+树在时间代价上都是一个量级的，但是跳表的插入删除都很简单，而b+树的插入删除会有节点分裂，节点合并，节点调整等问题，因此从工程效率来看，在纯内存的环境下，b+树并不比跳表和红黑树更合适。 2.所有的sstable都是只读的，不可更改。新的sstable生成了以后，老的sstable才会被删除，读操作才会转移到新的sstable上。因此，sstable不会被同时读写，没有读写阻塞的问题。

作者回复: 1.合并列表其实就是记录需要合并的sstable的列表。实际上，每次合并时，系统都会生成两个合并列表。 以你提问的level 0层的情况为例，先选定一个要合并的sstable，然后将level 0层中和它范围重叠的sstable都加入到这个列表中;这就是合并列表1。 然后，对于合并列表1中所有的sstable，我们能找到整体的范围begin和end。那么我们在下一层中，将和begin和end范围重叠的所有sstable文件加入合并列表2。 那么，对于合并列表1和合并列表2中的所有的sstable，我们将它们一起做一次多路归并就可以了。 2.如果下层空间满了，没关系，先合并完，这时候，下层空间就超容量了。那么，我们再针对这一层，按之前介绍的规则，选择一个sstable再和下层合并即可。 PS:再补充一下知识点:合并的触发条件。 系统会统计每个level的文件容量是否超过限制。超过上限比例最大的，将会被触发合并操作。

作者回复: 1.不用停止计算，而是算完后，判断容量是否达到上限，如果超过，就根据文中介绍的选择文件的方式，将多余的文件和下一层进行合并。 2.如果存在多个filter block，而且每个filter都很大的话(比如说bloomfilter就有许多数据)，将所有的filter都读入内存会造成多次磁盘IO,因此需要有metaphor index block，帮助我们只读取我们需要的filter即可。

作者回复: 可以看出来你思考得很深入，包括分析解决方案的缺陷和局限性，这是很好的学习方法。我也说一下我对你的问题的一些解读。 lsm类型的数据库不是用来做随机检索或范围检索的最佳选择，它更适合的是写多读少，尤其是读近期数据的场景。 至于打开多个文件效率低，包括寻道性能低的问题，这其实可以通过缓存来部分解决。但的确当大量文件被打开的时候，磁盘读写性能是不高的。因此文件的分层，缓存的使用，其实都是为了解决这个问题。包括你的第五个问题，为什么不对多个文件进行处理，也有这一方面的原因。(以上是对1－4问题的回答)。 至于第五个问题，为什么只选一个文件，我的理解是为了保证一次合并不要涉及过多的文件，减少io。实际上，只要知道了这个合并原理，一次选两个或三个文件来合并也不是不可以。比如说seek compaction过程，就是可以将经常查询失败的sstable放在合并列表中，进行批量处理。主要还是要注意io性能。

作者回复: 其实，sstable是lsm树的基本单位，大约等于b+树中的叶子节点。你会发现，b+树中的每个叶子节点其实也不大，仅仅是一个block大小而已。 或者你也可以将两个sstable用分隔符区分，然后写到同一个文件中，这样文件个数会减少，然后每个文件也会更大。但这样和维持两个sstable文件有什么区别呢? 其实回到磁盘读写的本质来看，多个小文件和一个大文件相比，只是多了一些文件打开的操作(读取对应inode)，后面的读取数据其实都是以block为单位进行的，并没有本质区别。 因此，只要能高效管理多个sstable文件，那么整体性能能得到保证，那么读取性能上和一个大文件差异不大。