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

你好，我是陈东。

LevelDB是由Google开源的存储系统的代表，在工业界中被广泛地使用。它的性能非常突出，官方公布的LevelDB的随机读性能可以达到6万条记录/秒。那这是怎么做到的呢？这就和LevelDB的具体设计和实现有关了。

LevelDB是基于LSM树优化而来的存储系统。都做了哪些优化呢？我们知道，LSM树会将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并。但是，这里面存在着大量的细节问题。比如说，数据在内存中如何高效检索？数据是如何高效地从内存转移到磁盘的？以及我们如何在磁盘中对数据进行组织管理？还有数据是如何从磁盘中高效地检索出来的？

其实，这些问题也是很有代表性的工业级系统的实现问题。LevelDB针对这些问题，使用了大量的检索技术进行优化设计。今天，我们就一起来看看，LevelDB究竟是怎么优化检索系统，提高效率的。

如何利用读写分离设计将内存数据高效存储到磁盘？

首先，对内存中索引的高效检索，我们可以用很多检索技术，如红黑树、跳表等，这些数据结构会比B+树更高效。因此，LevelDB对于LSM树的第一个改进，就是使用跳表代替B+树来实现内存中的C0树。

好，解决了第一个问题。那接下来的问题就是，内存数据要如何高效存储到磁盘。在第7讲中我们说过，我们是将内存中的C0树和磁盘上的C1树归并来存储的。但如果内存中的数据一边被写入修改，一边被写入磁盘，我们在归并的时候就会遇到数据的一致性管理问题。一般来说，这种情况是需要进行“加锁”处理的，但“加锁”处理又会大幅度降低检索效率。

为此，LevelDB做了读写分离的设计。它将内存中的数据分为两块，一块叫作MemTable，它是可读可写的。另一块叫作Immutable MemTable，它是只读的。这两块数据的数据结构完全一样，都是跳表。那它们是怎么应用的呢？

具体来说就是，当MemTable的存储数据达到上限时，我们直接将它切换为只读的Immutable MemTable，然后重新生成一个新的MemTable，来支持新数据的写入和查询。这时，将内存索引存储到磁盘的问题，就变成了将Immutable MemTable写入磁盘的问题。而且，由于Immutable MemTable是只读的，因此，它不需要加锁就可以高效地写入磁盘中。

好了，数据的一致性管理问题解决了，我们接着看C0树和C1树的归并。在原始LSM树的设计中，内存索引写入磁盘时是直接和磁盘中的C1树进行归并的。但如果工程中也这么实现的话，会有两个很严重的问题：

合并代价很高，因为C1树很大，而C0树很小，这会导致它们在合并时产生大量的磁盘IO；
合并频率会很频繁，由于C0树很小，很容易被写满，因此系统会频繁进行C0树和C1树的合并，这样频繁合并会带来的大量磁盘IO，这更是系统无法承受的。

那针对这两个问题，LevelDB采用了延迟合并的设计来优化。具体来说就是，先将Immutable MemTable顺序快速写入磁盘，直接变成一个个SSTable（Sorted String Table）文件，之后再对这些SSTable文件进行合并。这样就避免了C0树和C1树昂贵的合并代价。至于SSTable文件是什么，以及多个SSTable文件怎么合并，我们一会儿再详细分析。

好了，现在你已经知道了，内存数据高效存储到磁盘上的具体方案了。那在这种方案下，数据又是如何检索的呢？在检索一个数据的时候，我们会先在MemTable中查找，如果查找不到再去Immutable MemTable中查找。如果Immutable MemTable也查询不到，我们才会到磁盘中去查找。

因为磁盘中原有的C1树被多个较小的SSTable文件代替了。那现在我们要解决的问题就变成了，如何快速提高磁盘中多个SSTable文件的检索效率。

SSTable的分层管理设计

我们知道，SSTable文件是由Immutable MemTable将数据顺序导入生成的。尽管SSTable中的数据是有序的，但是每个SSTable覆盖的数据范围都是没有规律的，所以SSTable之间的数据很可能有重叠。

比如说，第一个SSTable中的数据从1到1000，第二个SSTable中的数据从500到1500。那么当我们要查询600这个数据时，我们并不清楚应该在第一个SSTable中查找，还是在第二个SSTable中查找。最差的情况是，我们需要查询每一个SSTable，这会带来非常巨大的磁盘访问开销。

因此，对于SSTable文件，我们需要将它整理一下，将SSTable文件中存的数据进行重新划分，让每个SSTable的覆盖范围不重叠。这样我们就能将SSTable按照覆盖范围来排序了。并且，由于每个SSTable覆盖范围不重叠，当我们需要查找数据的时候，我们只需要通过二分查找的方式，找到对应的一个SSTable文件，就可以在这个SSTable中完成查询了。

但是要让所有SSTable文件的覆盖范围不重叠，不是一个很简单的事情。为什么这么说呢？我们看一下这个处理过程。系统在最开始时，只会生成一个SSTable文件，这时候我们不需要进行任何处理，当系统生成第二个SSTable的时候，为了保证覆盖范围不重合，我们需要将这两个SSTable用多路归并的方式处理，生成新的SSTable文件。

那为了方便查询，我们要保证每个SSTable文件不要太大。因此，LevelDB还控制了每个SSTable文件的容量上限（不超过2M）。这样一来，两个SSTable合并就会生成1个到2个新的SSTable。

这时，新的SSTable文件之间的覆盖范围就不重合了。当系统再新增一个SSTable时，我们还用之前的处理方式，来计算这个新的SSTable的覆盖范围，然后和已经排好序的SSTable比较，找出覆盖范围有重合的所有SSTable进行多路归并。这种多个SSTable进行多路归并，生成新的多个SSTable的过程，也叫作Compaction。

随着SSTable文件的增多，多路归并的对象也会增多。那么，最差的情况会是什么呢？最差的情况是所有的SSTable都要进行多路归并。这几乎是一个不可能被接受的时间消耗，系统的读写性能都会受到很严重的影响。

那我们该怎么降低多路归并涉及的SSTable个数呢？在第9讲中，我们提到过，对于少量索引数据和大规模索引数据的合并，我们可以采用滚动合并法来避免大量数据的无效复制。因此，LevelDB也采用了这个方法，将SSTable进行分层管理，然后逐层滚动合并。这就是LevelDB的分层思想，也是LevelDB的命名原因。接下来，我们就一起来看看LevelDB具体是怎么设计的。

首先，从Immutable MemTable转成的SSTable会被放在Level 0 层。Level 0 层最多可以放4个SSTable文件。当Level 0层满了以后，我们就要将它们进行多路归并，生成新的有序的多个SSTable文件，这一层有序的SSTable文件就是Level 1 层。

接下来，如果Level 0 层又存入了新的4个SSTable文件，那么就需要和Level 1层中相关的SSTable进行多路归并了。但前面我们也分析过，如果Level 1中的SSTable数量很多，那么在大规模的文件合并时，磁盘IO代价会非常大。因此，LevelDB的解决方案就是，给Level 1中的SSTable文件的总容量设定一个上限（默认设置为10M），这样多路归并时就有了一个代价上限。

当Level 1层的SSTable文件总容量达到了上限之后，我们就需要选择一个SSTable的文件，将它并入下一层（为保证一层中每个SSTable文件都有机会并入下一层，我们选择SSTable文件的逻辑是轮流选择。也就是说第一次我们选择了文件A，下一次就选择文件A后的一个文件）。下一层会将容量上限翻10倍，这样就能容纳更多的SSTable了。依此类推，如果下一层也存满了，我们就在该层中选择一个SSTable，继续并入下一层。这就是LevelDB的分层设计了。

尽管LevelDB通过限制每层的文件总容量大小，能保证做多路归并时，会有一个开销上限。但是层数越大，容量上限就越大，那发生在下层的多路归并依然会造成大量的磁盘IO开销。这该怎么办呢？

对于这个问题，LevelDB是通过加入一个限制条件解决的。在多路归并生成第n层的SSTable文件时，LevelDB会判断生成的SSTable和第n+1层的重合覆盖度，如果重合覆盖度超过了10个文件，就结束这个SSTable的生成，继续生成下一个SSTable文件。

通过这个限制，LevelDB就保证了第n层的任何一个SSTable要和第n+1层做多路归并时，最多不会有超过10个SSTable参与，从而保证了归并性能。

如何查找对应的SSTable文件

在理解了这样的架构之后，我们再来看看当我们想在磁盘中查找一个元素时，具体是怎么操作的。

首先，我们会在Level 0 层中进行查找。由于Level 0层的SSTable没有做过多路归并处理，它们的覆盖范围是有重合的。因此，我们需要检查Level 0层中所有符合条件的SSTable，在其中查找对应的元素。如果Level 0没有查到，那么就下沉一层继续查找。

而从Level 1开始，每一层的SSTable都做过了处理，这能保证覆盖范围不重合的。因此，对于同一层中的SSTable，我们可以使用二分查找算法快速定位唯一的一个SSTable文件。如果查到了，就返回对应的SSTable文件；如果没有查到，就继续沉入下一层，直到查到了或查询结束。

可以看到，通过这样的一种架构设计，我们就将SSTable进行了有序的管理，使得查询操作可以快速被限定在有限的SSTable中，从而达到了加速检索的目的。

SSTable文件中的检索加速

那在定位到了对应的SSTable文件后，接下来我们该怎么查询指定的元素呢？这个时候，前面我们学过的一些检索技术，现在就可以派上用场了。

首先，LevelDB使用索引与数据分离的设计思想，将SSTable分为数据存储区和数据索引区两大部分。

我们在读取SSTable文件时，不需要将整个SSTable文件全部读入内存，只需要先将数据索引区中的相关数据读入内存就可以了。这样就能大幅减少磁盘IO次数。

然后，我们需要快速确定这个SSTable是否包含查询的元素。对于这种是否存在的状态查询，我们可以使用前面讲过的BloomFilter技术进行高效检索。也就是说，我们可以从数据索引区中读出BloomFilter的数据。这样，我们就可以使用O(1)的时间代价在BloomFilter中查询。如果查询结果是不存在，我们就跳过这个SSTable文件。而如果BloomFilter中查询的结果是存在，我们就继续进行精确查找。

在进行精确查找时，我们将数据索引区中的Index Block读出，Index Block中的每条记录都记录了每个Data Block的最小分隔key、起始位置，还有block的大小。由于所有的记录都是根据Key排好序的，因此，我们可以使用二分查找算法，在Index Block中找到我们想查询的Key。

那最后一步，就是将这个Key对应的Data block从SSTable文件中读出来，这样我们就完成了数据的查找和读取。

利用缓存加速检索SSTable文件的过程

在加速检索SSTable文件的过程中，你会发现，每次对SSTable进行二分查找时，我们都需要将Index Block和相应的Data Block分别从磁盘读入内存，这样就会造成两次磁盘I/O操作。我们知道磁盘I/O操作在性能上，和内存相比是非常慢的，这也会影响数据的检索速度。那这个环节我们该如何优化呢？常见的一种解决方案就是使用缓存。LevelDB具体是怎么做的呢？

针对这两次读磁盘操作，LevelDB分别设计了table cache和block cache两个缓存。其中，block cache是配置可选的，它是将最近使用的Data Block加载在内存中。而table cache则是将最近使用的SSTable的Index Block加载在内存中。这两个缓存都使用LRU机制进行替换管理。

那么，当我们想读取一个SSTable的Index Block时，首先要去table cache中查找。如果查到了，就可以避免一次磁盘操作，从而提高检索效率。同理，如果接下来要读取对应的Data Block数据，那么我们也先去block cache中查找。如果未命中，我们才会去真正读磁盘。

这样一来，我们就可以省去非常耗时的I/O操作，从而加速相关的检索操作了。

重点回顾

好了，今天我们学习了LevelDB提升检索效率的优化方案。下面，我带你总结回顾一下今天的重点内容。

首先，在内存中检索数据的环节，LevelDB使用跳表代替B+树，提高了内存检索效率。

其次，在将数据从内存写入磁盘的环节，LevelDB先是使用了读写分离的设计，增加了一个只读的Immutable MemTable结构，避免了给内存索引加锁。然后，LevelDB又采用了延迟合并设计来优化归并。具体来说就是，它先快速将C0树落盘生成SSTable文件，再使用其他异步进程对这些SSTable文件合并处理。

而在管理多个SSTable文件的环节，LevelDB使用分层和滚动合并的设计来组织多个SSTable文件，避免了C0树和C1树的合并带来的大量数据被复制的问题。

最后，在磁盘中检索数据的环节，因为SSTable文件是有序的，所以我们通过多层二分查找的方式，就能快速定位到需要查询的SSTable文件。接着，在SSTable文件内查找元素时，LevelDB先是使用索引与数据分离的设计，减少磁盘IO，又使用BloomFilter和二分查找来完成检索加速。加速检索的过程中，LevelDB又使用缓存技术，将会被反复读取的数据缓存在内存中，从而避免了磁盘开销。

总的来说，一个高性能的系统会综合使用多种检索技术。而LevelDB的实现，就可以看作是我们之前学过的各种检索技术的落地实践。因此，这一节的内容，我建议你多看几遍，这对我们之后的学习也会有非常大的帮助。

课堂讨论

当我们查询一个key时，为什么在某一层的SSTable中查到了以后，就可以直接返回，不用再去下一层查找了呢？如果下一层也有SSTable存储了这个key呢？
为什么从Level 1层开始，我们是限制SSTable的总容量大小，而不是像在Level 0层一样限制SSTable的数量？（提示：SSTable的生成过程会受到约束，无法保证每一个SSTable文件的大小）

欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这一讲分享给你的朋友。

精选留言

奕

2020-05-08 17:29:29

当 MemTable 的存储数据达到上限时，我们直接将它切换为只读的 Immutable MemTable，然后重新生成一个新的 MemTable
------------------
这样的一个机制，内存中会出现多个Immutable MemTable 吗？上一个Immutable MemTable 没有及时写入到磁盘

作者回复

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

2020-05-08 22:44:46
奕

2020-05-09 11:56:56

LevelDB 分层的逻辑没有理解
当 Level0 层有四个 SSTable 的时候，这时候把这个四个进行归并，然后放到 Level1 层，这时候 Level0 层清空，这个有个问题是当进行归并后后生成几个 SSTable ,这里是有什么规则吗？

接下来，然后 Level0 层在满了之后，是Level0 层的每个 SSTable 分别与 Level1 所有的 SSTable 进行多路归并吗？

再然后 Level1 层满了之后，是按照顺序取 Level1 层的一个 SSTable 与 Level2所有的 SSTable 进行多路归并吗？

这样会有大量的磁盘 IO,老师说利用判断重合度进行解决的？这个重合度是怎么计算计算判断的呢？

==============================
老师的文中的这句话没有看明白：
在多路归并生成第 n 层的 SSTable 文件时，LevelDB 会判断生成的 SSTable 和第 n+1 层的重合覆盖度，如果重合覆盖度超过了 10 个文件，就结束这个 SSTable 的生成，继续生成下一个 SSTable 文件

作者回复

你的问题我重新整理一下，尤其是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中。

2020-05-09 17:14:58
吴小智

2020-05-08 00:34:13

之前看过基于 lsm 的存储系统的代码，能很好理解这篇文章。不过，还是不太理解基于 B+ 树与基于 lsm 的存储系统，两者的优缺点和使用场景有何不同，老师有时间可以解答一下。

作者回复

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

2020-05-08 12:55:18
wangkx

2020-05-18 13:31:21

1. 既然要查找的数据在某一层查到了，按照LevelDB的分层管理的设计，即使下一层数据也存在，数据也是一样的，没有必要再去查找下一层的数据了。

2. “在多路归并生成第 n 层的 SSTable 文件时，LevelDB 会判断生成的 SSTable 和第 n+1 层的重合覆盖度，如果重合覆盖度超过了 10 个文件，就结束这个 SSTable 的生成，继续生成下一个 SSTable 文件。”———如果通过控制sstable文件数量来限制每层容量的话，有可能每个sstable会比较小，很快就达到数量限制，可能分层作用就不明显了。

作者回复

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

2020-05-18 19:37:35
时隐时现

2020-05-11 20:44:37

老师好，有2个问题：
1、内存中的C0树，采用跳表替换掉B+树，检索效率会有提升吗？我一直觉得两者是差不多的吧，什么场景下跳表会比B+树性能高很多？
2、滚动合并应该是后台操作，在合并的过程中，相应的sstable应该是被写锁锁定的吧？此时如果有应用执行读，会不会被阻塞？如果不阻塞，如何保证读写一致性？

作者回复

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

2020-05-11 22:41:13
xaviers

2020-05-08 22:59:31

老师，不好意思哈，再追问一下😬那为啥用change buffer + WAL优化后的MySQL的写性能还是不如LSM类的存储系统啊？原因是啥啊

作者回复

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

2020-05-09 08:55:58
奕

2020-05-09 20:51:44

在评论下回复老师看不到啊，那就在评论问一下

第一问还有点疑问:level0层的每个sstable可能会有范围重叠，需要把重叠的部分提取到合并列表，这个这个合并列表是什么？还有就是提取之后呢，还是要遍及level0层的每个sstable与level1层的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的文件容量是否超过限制。超过上限比例最大的，将会被触发合并操作。

2020-05-10 00:48:24
那时刻

2020-05-08 10:12:52

有两个问题，请教下老师。
1。在多路归并生成第 n 层的 SSTable 文件时，如何控制当前层最大容量呢？如果超过当前层的容量是停止计算还是把多余的量挪到下一层？
2。数据索引区里meta index block，当存在多个过滤器时，对过滤器进行索引。这是涉及到filter block过滤么？

作者回复

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

2020-05-08 22:13:27
Bachue Zhou

2021-01-06 09:44:41

这个数据库在海量数据的情况下真的很快吗，我总感觉一般般的样子啊。
1. 层次没有上限单层文件总容量却有上限，因此极端情况下需要搜索的文件依然很多，虽然每个文件有布隆过滤器预搜索，所以单个文件检索性能还不错，但需要一层层打开文件解析文件然后开始搜索，文件数量如果很多，则性能不佳
2. 如果是范围检索，则注定所有层次都必须被查询，性能不佳
3. 每个文件尺寸有上限，而且很小，意味着文件数量很多，文件打开数就会很多，当达到通常的 65536 的上限时（如果每个文件 2m 大小，那么也就存了 128g，实际上由于进程自身也有文件打开数开销，实际上能提供给 leveldb 的文件打开数配额会远远小于这个值），就只能被迫使用 lru 来关闭一些不常用的小文件了，如果频繁打开解析关闭小文件时，性能不佳
4. 多路归并多个文件的数据，意味着磁盘在多个文件中来回寻道，哪怕只有最多十个文件，性能也不佳
5. 无法理解为何只选一个文件参与和下一层的归并，选一个文件和选两个文件的区别在哪里？

作者回复

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

2021-01-17 22:24:14
piboye

2020-09-18 21:36:47

如果把sstable换成B+树，也有bloomfilter，是不是可以不用限制文件为2m的大小？

作者回复

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

2020-09-20 23:10:30
piboye

2020-09-18 21:35:05

为什么要限制sstable为2m，感觉很小啊，如果是个很大的数据集，文件不是会很多？

作者回复

实际上，sstable的大小是可以设置的，可以调整到2m以上。不过不建议设置太大。原因如下:
1.对于level 0层的sstable而言，它是由内存中的memtable转过来的。如果内存中要写满大量数据才落盘，那么为了防止内存数据丢失，wal文件就要写入相应数据量的数据。但wal为了保证效率不宜过大，因此level 0层的sstable不宜过大。
2.对于level 1层以上的sstable，文件上限可以放宽一些，不过也不宜过大。否则两个sstable合并时，合并代价就会很大，会有大量的无关数据被进行读写，反而影响整体效率。

此外，多个小文件并不一定会比一个大文件读写效率低。一方面，是level db的sstable合并机制，对于小文件是更有利的(大文件合并更慢);另一方面，sstable的信息其实有缓存和meta文件进行管理，对多个文件的读写操作其实可以避免多次文件io操作，比常规的文件系统随机读写多个小文件效率会高很多。因此，level db存储和管理多个sstable文件，整体效率并不低。

2020-09-20 22:59:51
飞翔

2020-06-25 07:50:29

老师 level db 的应用场景是什么呀

作者回复

因为levelDB的本质还是lsm树的优化实现，因此它的应用场景和lsm树一样，依然是适用于写多读少的kv存储场景中。

2020-06-25 23:38:11
Geek_863b69

2020-06-19 09:11:11

老师，请教下，levelDB中，data block存的是sstable的数据，如果sstable跟上一层数据合并了，那么查找的时候如果直接从缓存找，数据不就不一致了？还是说合并的时候会顺带删除缓存？

作者回复

你思考了缓存数据和磁盘数据的一致性问题，这一点非常好。在这里我补充两个知识点:
1.对于leveldb而言，每个sstable都是只读的，不可修改的，所谓的sstable和上一层数据合并了，结果是会生成新的sstable，然后删除旧的sstable。因此并不会出现缓存和磁盘数据不一致的问题(缓存的是一个旧的sstable，而磁盘上是另一个新的sstable，查询时会访问新的sstable文件，该文件并不在缓存中，因此系统并不会去误读缓存中旧的sstable中的数据)。
2.对于其他的一些应用，关于如何保证内存缓存数据和磁盘数据的一致性，一种常见的解决方案是在写操作时，先删除缓存，然后再修改磁盘数据。

2020-06-20 17:09:17
xaviers

2020-05-08 20:48:31

老师晚上好，请教个问题哈。

MySQL在写数据的时候，是先写到change buffer内存中的，不会立刻写磁盘的，达到一定量再将change buffer落盘。这个和Memtable的设计理念类似，按理说，速度也不会太慢吧？

作者回复

你说得对，在MySQL的b+树的具体实现中，其实借鉴了许多lsm树的设计思想来提升性能，比如使用wal技术+change buffer，然后批量写叶子节点，而不是每次都随机写。这样就能减少磁盘IO。的确比原始的b+树快。
不过在大批量写的应用场景中，这样优化后的b+树性能还是没有lsm树更好。因此日志系统这类场景还是使用lsm树更合适。

2020-05-08 22:29:07
那时刻

2020-05-08 09:42:17

讨论问题1：在某一层找到了key，不需要再去下一层查找的原因是，这一层是最新的数据。即使下一层有的话，是旧数据。这引申出另外一个问题，数据删除的时候是怎么处理的呢？是另外一个删除列表来保存删除的key吗？
问题2：如老师提示的这样，SSTable 的生成过程会受到约束，SSTable在归并的过程中，可能由于数据倾斜，导致某个分区里的数据量比较大，所以没有办法保证每个SSTable的大小。

作者回复

问题1:你进一步去思考删除问题。这一点很好。数据删除时，是会将记录打上一个删除标记，然后写入sstable中。
sstable和下一层合并时，对于带着删除标记的记录，levelDB会判断下层到最后一层是否还有这个key记录，有两种结果:
1.如果还有，那么这个删除标记就不能去掉，要一直保留到最后一层遇到相同key的时候才能删除；
2.如果没有，那么就可以删除掉这个带删除标记的记录。
问题2:因为在进行合并时，新生成的sstable会受到一个约束:如果和下一层的sstable重叠数超过了十个，就要停止生成这个sstable，要再继续生成一个新的sstable。这个机制会导致我们不好控制文件的个数。不如限定容量更合适。

2020-05-08 22:01:07
快跑

2021-04-23 11:33:58

“LevelDB 会判断生成的 SSTable 和第 n+1 层的重合覆盖度”，
判断第N层的SSTable跟N+1层的覆盖重合度，这块逻辑是怎么实现的，需要将第N层的数据加载到内存每条记录都判断，还是有额外的索引记录着第N层的数据范围？

作者回复

这是一个好问题。你可以先思考一下，如果让你设计你会怎么做。这门课学到这里，相信你会有做索引的思路了，实际上，leveldb就是加了一个叫manifest的索引文件来实现的。
在manifest文件中，所有sstable的 Key 取值范围、层级和其它元信息都被记录下来。只需要将manifest文件加载到内存中，就可以快速查到所有sstable文件的层级和 Key 取值范围。

2021-05-05 21:34:42
牛牛

2020-05-09 15:17:27

老师、我想请教下、levelDB是怎么处理`脏缓存`(eg. 有用户突然访问了别人很久不访问的数据(假设还比较大)、导致本来应该在缓存中的数据被驱逐, Data Block的优化效果就会打折扣)的 ?

------
我是想到了Mysql 处理Buffer Poll的机制(分为Old 和 Young区)、类似的思想在jvm的gc管理中也有用到

作者回复

首先，levelDB并没有“脏缓存”的问题。因为lsm树和b+树不一样。
b+树的缓存对应着磁盘上的叶子节点，叶子节点是可以被修改的，因此会出现缓存在内存中的数据被修改，但是磁盘对应的叶子节点还未修改的“脏缓存”问题。
而levelDB中，data block存的是sstable的数据，而每个sstable文件是只读的，不可修改的，因此不会出现“脏缓存”问题。
另一点，如果缓存数据被大片读入的新数据驱除，是否会有优化方案？这其实就依赖于lru的具体实现了(比如分为old和young区)，levelDB本身并没有做特殊处理。

2020-05-10 00:33:30
奕

2020-05-08 18:24:08

课后思考：
1: 因为 LevelDB 天然的具有缓存的特性，最经常使用的最新的数据离用户最近，所有在上层找到数据就不会在向下找了
2: 如果规定生成文件的个数，那么有可能当前层和下一层的存储大小相近了，起不到分层的作用了

作者回复

1.没错，最新的数据在上层，所以上层能找到，就不需要去下层读旧数据了。
2.是的，由于在生成sstable文件时，有这么一个限制:新生成的sstable文件不能和下层的sstable覆盖度超过十个，因此可能会生成多个小的sstable文件。那如果只看文件数的话，多个小的sstable文件可能容量和下一层差不多，这样就没有了分层的作用了。

2020-05-08 22:49:41
峰

2020-05-08 07:40:01

问题1：因为只是get(key), 所以上层的sstabe的数据是最新的，所以没必要再往下面查，但如果有hbase这样的scan(startkey,endkey) 那还是得全局的多路归并（当然可以通过文件元数据迅速排除掉一些hfile）
问题2：SSTable 的生成过程会受到约束，无法保证每一个 SSTable 文件的大小。哈哈哈，我在抄答案，我其实有疑问，就算限定文件数量，那么在层次合并的时候，假设我是先合成一个整个sstable再切，面临的对这一整个sstable怎么切成文件的问题，那就顺序的2m一个算会不会文件数量超标，决定是否要滚动下一层，不过我这样想法过于理想显然假设那块就不成立，应该是多路归并式的动态生成，否则对内存压力太大，但是如果按整个层的文件大小分，就不用考虑文件量的问题，只要key连续性大点，文件大小不超过2m就生成就好了。

作者回复

1.你提到的这个问题非常好，lsm的范围查询比较弱，需要遍历。一种优化思路是先在level 1层中找到range，然后基于start和end的位置，去下一层再找start和end的位置。这样能提高范围查询的性能。
2.我说一下我的理解，由于有“生成的每个sstable和下一层的sstable重合度不能超过十个”这个约束，所以sstable生成过程中可能随时被截断，因此不好控制sstable的数量。不如控制容量简单。

2020-05-08 16:07:52
yic

2023-09-26 18:20:22

"而从 Level 1 开始，每一层的 SSTable 都做过了处理，这能保证覆盖范围不重合的。因此，对于同一层中的 SSTable，我们可以使用二分查找算法快速定位唯一的一个 SSTable 文件" -- 老师，关于这个点我有疑问还请帮忙解答：
这句话描述的是一个终态吧？我理解一条比较大的数据A（预期应该放在L6层）写入了Level0层后，要到达L6层是需要一定的时间的。

如果我上面的理解没有错误，那么当数据A到达了L3层时，用户过来查询，会是怎样的处理过程呢？