# 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树进行归并的。但如果工程中也这么实现的话，会有两个很严重的问题：

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

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

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

![](https://static001.geekbang.org/resource/image/22/1a/22cbb79dd84126a66b12e1b50c58991a.jpeg "增加Immutable MemTable设计的示意图")

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

## SSTable的分层管理设计

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

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

![](https://static001.geekbang.org/resource/image/5f/02/5f197f2664d0358e03989ef7ae2e7e02.jpeg "范围重叠时，查询多个SSTable的示意图")

因此，对于SSTable文件，我们需要将它整理一下，将SSTable文件中存的数据进行重新划分，让每个SSTable的覆盖范围不重叠。这样我们就能将SSTable按照覆盖范围来排序了。并且，由于每个SSTable覆盖范围不重叠，当我们需要查找数据的时候，我们只需要通过二分查找的方式，找到对应的一个SSTable文件，就可以在这个SSTable中完成查询了。  
![](https://static001.geekbang.org/resource/image/4d/a7/4de515f8b4f7f90cc99112fe5b2b2da7.jpeg "范围不重叠时，只需查询一个SSTable的示意图")

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

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

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

![](https://static001.geekbang.org/resource/image/32/0a/32e551a4f13d5630b7a0e43bef556b0a.jpeg "SSTable保持有序的多路归并过程")

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

那我们该怎么降低多路归并涉及的SSTable个数呢？在[第9讲](https://time.geekbang.org/column/article/222807)中，我们提到过，对于少量索引数据和大规模索引数据的合并，我们可以采用滚动合并法来避免大量数据的无效复制。因此，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的分层设计了。

![](https://static001.geekbang.org/resource/image/ca/5a/ca6dad0aaa0eb1303b5c1bb17241915a.jpeg "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文件；如果没有查到，就继续沉入下一层，直到查到了或查询结束。

![](https://static001.geekbang.org/resource/image/57/8b/57cd22fa67cba386d83686a31434e08b.jpeg "LevelDB分层检索过程示意图")

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

## SSTable文件中的检索加速

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

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

![](https://static001.geekbang.org/resource/image/53/40/53d347e57ffee9a7ea14dde2b5f4a340.jpeg "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的实现，就可以看作是我们之前学过的各种检索技术的落地实践。因此，这一节的内容，我建议你多看几遍，这对我们之后的学习也会有非常大的帮助。

## 课堂讨论

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

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