LevelDB 源码分析（一）：简介 | 陈浩的个人博客

LSM tree

LevelDB 中一个核心的结构就是 LSM tree，所以这里先介绍下 LSM tree。

在 key-value store 中 Log-Structured Merge-Trees (LSM-trees) 应用得相当广泛。与其他的索引结构(如B-tree)相比，LSM-trees 的主要优点是能够维持顺序的写操作。在B树中小的更新会带来较多的随机写，为了提高性能，LSM-trees 可以批量处理 key-value 对，然后将他们顺序写入。

一个 LSM-tree 由一些大小成倍增加的小组件组成。如下图所示，C0层是驻留内存的原地更新的排序树，其他的层 C1-Cn 是驻留磁盘的只允许插入的B树。

当插入一个 key-value 对到 LSM tree 中时，首先将其添加到磁盘的日志文件中用以在崩溃情况下的恢复。然后 key-value 对会被添加到内存中的 C0 中，且 C0 是有序的。一旦 C0 的大小达到一个限制值后，它会和磁盘上的 C1 数据利用归并算法进行有序地合并。新的合并的树会替代原来版本的 C1 并顺序地写到磁盘上。当磁盘上的 C1-Cn 中的任意一层的大小达到限制值时，都会进行类似的合并操作。合并的操作只能发生在相邻的层之间，并且他们可以在后台异步进行。

LevelDB

LevelDB 是一个基于 LSM tree 的 key-value store ，其架构如下所示。

LevelDB 主要的数据结构是：磁盘上的日志文件，内存上的两个有序的跳表(memtable和 immutable memtable) 和存储在磁盘上的7层的有序的字符串表(SSTable)文件。

写操作

当应用写入一条 key-value 记录的时候，LevelDB 会先往磁盘上的日志文件里写入，成功后将记录插进内存中的 memtable中，这样基本就算完成了写入操作，因为一次写入操作只涉及一次磁盘顺序写和一次内存写入，这是 LevelDB写入速度极快的主要原因。

一旦 memtable 满了之后，LevelDB 会生成新的 memtable 和日志文件来处理用户接下来的请求。在后台，之前的 memtable 被转换成 immutable memtable，顾名思义，就是说这个 memtable 的内容是不可更改的，只能读不能写入或者删除，一个合并的线程会将它里面的内容刷新到磁盘上，产生一个大约 2M 大小的 SSTable文件，并将其放在 level 0 层。同时，以前的日志文件将会被丢弃。

合并

每一层所有文件的大小是有限制的，大约是以10倍依次递增。当某一层的总大小超过了它的限制时，合并线程就会从该层选择一个文件将其和下一层的所有重叠的文件进行归并排序产生一个新的 SSTable 文件放在下一层中。合并线程会一直运行下去直到所有层的大小都在规定的限制内。当然，在合并的过程中，LevelDB 会保持除 level 0 之外的每一层上的所有文件的 key 的范围不会重叠，L0 层上文件的 key 的范围是可以重复的，因为它是直接从 memtable 上刷新过来的。

查找操作

对于查询操作，LevelDB 首先会查询 memtable，接下来是 immutable memtable，然后依次查询 L0-L6 中每一层的文件。确定一个随机的 key 的位置而需要搜索文件的次数的上界是由最大的层数来决定的，因为除了L0之外，每一层的所有文件中key的范围都是没有重叠的。 由于L0中文件的key的范围是有重叠的，所以在L0中进行查询时，可能会查询多个文件。为了降低查询操作的延迟，当L0层的文件数量超过8时，LevelDB 就会降低前台写操作的速度，这是为了等待合并线程将L0中的文件合并到L1中。

写放大

LevelDB 中的写放大是很严重的。假如，每一层的大小是上一层的10倍，那么当把 i-1 层中的一个文件合并到 i 层中时，LevelDB 需要读取 i 层中的文件的数量多达10个，排序后再将他们写回到 i 层中去。所以这个时候的写放大是10。对于一个很大的数据集，生成一个新的 table 文件可能会导致 L0-L6 中相邻层之间发生合并操作，这个时候的写放大就是50（L1-L6中每一层是10）。

读放大

LevelDB 中的读放大也是一个主要的问题。读放大主要来源于两方面：

(1) 查找一个 key-value 对时，LevelDB 可能需要在多个层中去查找。在最坏的情况下，LevelDB 在 L0 中需要查找8个文件，在 L1-L6 每层中需要查找1个文件，累计就需要查找14个文件。

(2) 在一个 SSTable 文件中查找一个 key-value 对时，LevelDB 需要读取该文件的多个元数据块。所以实际读取的数据量应该是：index block bloom-filter blocks data block。例如，当查找 1KB 的 key-value 对时，LevelDB 需要读取 16KB 的 index block，4KB的 bloom-filter block 和 4KB 的 data block，总共要读取 24 KB 的数据。在最差的情况下需要读取 14 个 SSTable 文件，所以这个时候的写放大就是 24*14=336。较小的 key-value 对会带来更高的读放大。

引用

Lu L, Pillai T S, Arpaci-Dusseau A C, et al. WiscKey: separating keys from values in SSD-conscious storage[C] 14th USENIX Conference on File and Storage Technologies (FAST 16). 2016: 133-148.

LevelDB相关文章

（1）数据分析与处理之二（Leveldb 实现原理）： http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html

（2）http:///leveldb.html

（3）http://blog.csdn.net/sparkliang/article/category/1342001

（4）levledb接口预览