浅谈 LevelDB¶

在阅读 Spark 源码的过程中，发现了内部封装了一份 LevelDB 的类。在类似于 External Shuffle Service 等多处地方都有使用。

External Shuffle Service 使用 LevelDB 来构建存放 Executors 信息的 ConcurrentHashMap。ESS 默认开启的 spark.shuffle.service.db.enabled 用于帮助 ESS 重启后，获得之前注册的 Executors Block 信息，就是通过 LevelDB 从本地磁盘存储的文件中读取出信息。

LevelDB 用于构建轻量级的失败恢复机制还是比较合适的。

因而，浅谈一下LevelDB。

LevelDB 基础¶

LevelDB 是一个持久化存储的KV系统，LevelDB 偏向于将数据存在内存，随后进行内存溢写到磁盘进行持久化。LevelDB 存储的Key是有序的，并且可以自定义实现比较函数。Level DB 支持 Snapshot（快照功能），能使读操作过程中读取的数据保持一致、支持数据压缩的功能。

简单的介绍一下：LevelDB 中出现的一些文件和类。

引用[1]

基本上可以分为在内存中的和在磁盘中的。

简单来说，内存维护的 MemTable 存放着最新的记录，等待其达到持久化的临界值时，就会先变成 Immutable MemTable，随后经过一系列操作写入到 SSTable 文件中。Log 文件用于记录 MemTable的变化，以便于重构一个 MemTable（为什么需要重构，在下文讲到）。Manifest 文件记录着每个 SSTable 所在的 Level信息，以及其存储记录的最小Key与最大Key。

Manifest File¶

根据上述提到的，LevelDB 所存储的 Key 是有序的，那么对于每个存储了KV记录的 SSTable 文件，都会存在文件的最小记录Key和最大记录Key。这部分信息，寻找规定范围内的 SSTable 文件来说很重要。同时，他还会记录每个 SSTable 所在的 Level，即所在层级。

Current File¶

由于 SSTable 文件发生变化的时候，Manifest 文件也会发生变化，产生新的 Manifest 文件。Current 文件存储的信息就是目前正在用的 Manifest文件。

Log File¶

Log 文件在 LevelDB 中的作用在于，帮助系统崩溃恢复而不丢失数据。

假如没有 Log 文件，写入的 Key:Value 记录先写入到内存中，再持久化到磁盘文件中。在写入内存后，系统发生了崩溃，那么内存中未持久化到磁盘的数据就会丢失。

具体的使用过程为，LevelDB 的写入过程，即使发生了系统崩溃，我们也可以通过 Log 文件来恢复内存中的 MemTable。

LevelDB 会将一个 Log 文件按照大小进行分割为一块一块的32k大小的 Block。每次读取 Log 文件的时候，都会以一个 Block 作为基本单位进行读取。所以，log 文件可以看作一个一个的32k Block。

Log File

在 LevelDB内部，Block 存储了Record的同时还会存储一个Record的Header，包含CRC验证，记录长度，类型。

Log Record

CRC 验证可以理解为 CheckSum，用来验证数据是否损坏丢失。
记录长度表示为Record Data的长度
类型有 FULL，FIRST，LAST，MIDDLE。存在类型的原因为：一个完成的KV记录大小可能大于一条Block的大小，导致需要对KV记录进行切分，如上述图所示。FULL代表Record的所有数据都在这个Block里，没有切分；FIRST代表这里存放的是Record的开头；MIDDLE表示这里存放Record的中间顺序；LAST代表这里存放是Recrod的最后部分。

LevelDB 即每次读取一块Block，随后按照逻辑进行拼接成完整的以供使用。

MemTable & Immutable MemTable¶

总体而言，所有的数据都是存储在 MemTable, Immutable MemTable 和 SSTable 文件中的。而内存中的数据是存放在 MemTable 和 Immutable MemTable中。

MemTable 与 Immutable MemTable 的区别在于，后者不可修改，只可读。Immutable MemTable 由 MemTable 转化而来。

当 MemTable 写入的数据占内存达到了一定的数量，则会自动转化成 Immutable MemTable，等待持久化到磁盘当中，经过操作变为SSTable 文件，系统也会自动生成新的 MemTable 以供写入。

MemTable 提供写入 KV Record，删除以及读取KV记录的接口。然而，实际上，MemTable 并不会真正的删除已经存在于内存中的KV记录，而是会使用Key添加一条带有Key和删除标志的Record。真正的删除操作是Lazy的，等到 Compaction 的过程中，才会去去除这个KV Record。

值得注意的是，MemTable 会对存储的 KV记录按照Key的大小进行有序的存储，在插入新记录的时候，会需要将这个KV插入到合适的位置上保持Key的有序性。而MemTable 是有 SkipList这类数据结构来实现的。

具体有关SkipList的会之后展开，篇幅有限这里不进行介绍。

简单来说，SkipList是平衡树的替代数据结构，与红黑树等平衡树不同的是，SkipList的插入和删除比较简单，并且在插入时不用进行复杂的树节点平衡操作。

SSTable: Sorted String Table¶

在上面我们提到过，SSTable 文件存储了持久化的记录数据，并且对应了LevelDB的Level的层级概念。至于如何形成Level，会在下面的 Compaction阶段进行介绍。

SSTable 文件以.sst为后缀，内部的布局也是一致的。上文介绍了Log 文件是分Block进行存储的，而SSTable也是按照Block进行存储的，不同的是Log文件存储的Record是不用维护有序的，SSTable 文件内部按照Key的从小到大进行排序。

SSTable File

由上图可以看到，SSTable File存储了五个类型的信息：

Footer
IndexBlock
MetaIndexBlock
FilterBlock
DataBlock

其中，DataBlock存放了Key:Value，FilterBlock存放了布隆过滤器二进制数据。其余三种为管理块，IndexBlock记录了DataBlock相关的信息；MetaIndexBlock记录了FilterBlock相关的信息。而Footer则指出IndexBlock和MetaIndexBlock在文件中的偏移量，指出他们的位置。

简单的用伪代码，表示一下Footer类的内部构造。

Java
class BlockInfo {
    int offset;
    int size;
}
class Footer {
    BlockInfo metaIndexInfo;
    BlockInfo IndexInfo;
    byte[] padding;
    long magicBits;
}

Footer内部就存放了MetaIndexBlock和IndexBlock的偏移量以及大小，同时记录了LevelDB的MagicWord，使用了对齐填充，使Footer大小始终保持在48字节。

Block¶

Java
class Block {
    byte[] data;
    short type;
    int crc;
}

其余的四种类型，都属于Block类，即除了里面存放的数据，还包含压缩类型和CRC校验码，占用五个字节。

DataBlock¶

DataBlock默认大小是4K字节（但并不意味着DataBlock始终在4K以内，之后最后一条记录存储完毕，发现DataBlock > 4k了，才会新创建一个DataBlock，这意味着如果最后一条记录的Value很大，会把DataBlock也撑大。同时这告诉我们，DataBlock不会将Value进行分块存储。），里面存储了一系列的键值对。前文提到了SSTable文件中存储了Key是保持有序的，这意味着Key会存在前缀重叠的情况，LevelDB即可以利用这个特性，节省了一大块的重复前缀空间。

DataBlock

DataBlock 按照Shared Key来进行分割，每隔几个Entry就会设置基准Key。基准key的特点是其SharedKey为空。基准Key在Block中的位置，即偏移量会被记录，当作Restart Point。DataBlock会在末尾记录Restart Point的个数。

Java
class Entry {
    int sharedKeyLength;
    int unsharedKeyLength;
    int valueLength;
    byte[] unsharedKeyContent;
    byte[] valueContent;
}

class DataBlock {
    Entry[] entries;
    int[] restartPoints;
    int restartPointCount;
}

DataBlock 中的基准Key默认为16个Key设置一个，这不是最优的策略。这也意味着SharedKey为空的不一定是基准Key，而是基准Key的SharedKey一定为空。

如果没有开启布隆过滤器，是不存在FilterBlock的。

布隆过滤器用来加速SSTable 文件的Key定位效率。如果没有布隆过滤器，那么LevelDB会对SSTable文件进行二分查找寻找Key，最后在最坏的情况下，查询了N遍，发现Key不在其中；布隆过滤器的作用就是避免在Key不存在的时候，浪费了查询的IO时间。通过布隆过滤器判断这个Key在不在，然后进行二分查找。

Filter Block

通过 BaseLG 分割系数，来判断这块布隆过滤器的Filter Entry 属于那块DataBlock，每块Filter Entry存放连续范围的Key的映射。

布隆过滤器相关原理和设计，之后出文章浅谈。

Java
class FilterEntry {
    byte[] raw;
}

class FilterBlock {
    FilterEntry[] filterRaws;
    int[] filterEntryOffsets;
    int offsetArrayOffset;
    short baseLG;
}

MetaIndexBlock¶

MetaIndexBlock 存储了前文提到的 FilterBlock的元信息，Key存了固定前缀的filter名称，Value对应的是FilterBlock在文件中的偏移量和长度。

MetaIndexBlock

IndexBlock¶

与上述的MetaIndexBlock 类似，不过存储的是 DataBlock的元信息，存在多少的DataBlock，IndexBlock中就有多少的Entry。

Key存储的是对应的DataBlock中的最大的Key，Value存储的是DataBlock的偏移量和长度。

不考虑Key的共享，不考虑重启点。

IndexBlock

写入过程¶

LevelDB 写入一个Key:Value记录，LevelDB会先往log File里写入，成功之后，才会将记录插入 MemTable，这样子就完成了对 LevelDB 的写入。

这也是为什么 LevelDB 写入记录的速度快，只需要一次磁盘文件的添加写和内存SkipList的添加。

上文提到了，LevelDB 删除记录是Lazy的，本质上会先写入带有删除标记的Key:Value记录，在之后的写入SSTable再进行删除操作。

更新操作，也不会去真正的更新Key:Value记录。LevelDB的随机读是不理想的，LevelDB更新记录的本质也是插入一个相同Key的键值对，对于旧记录的操作也要到Compaction操作了。

那么，为什么插入新的一条记录就能达到更新的效果呢，往下看LevelDB的读取操作。

读取过程¶

Read

LevelDB 首先会去查看内存中的MemTable，如果没有读取到，则会前往同样存在内存中的 Immutable MemTable 中读取。再没有读取到的话，会进入磁盘读取，由于SSTable 文件会比较多，会进行分层寻找。首先从Level 0进行查询，依次进入，直到找到或者完全没找到。

为什么会选择这样子的查询路径呢？从内存的MemTable到磁盘的SSTable文件，都保持了优先读取最新鲜的记录的原则。对于Level i 和 Level i+1的SSTable来说，相同的Key，Level i的信息一定比 Level i+1新。

这就解释了上文，我们提到的更新操作，我们查到最新的记录就会返回，这样子就达到了更新的效果。

那么为什么Level i 会比 Level i+1 的数据比较新呢？Level i+1 的数据是从 Level i经过 Compaction过程后，得到的。那么原来的Level i变成了 Level i+1，新的 Level i当然记录比 Level i+1更新。

那么SSTable 文件很多，如何快速的找到key对应的value？

首先要说明一个特殊的层级Level 0，Level 0的不同文件Key的范围可能会存在重叠，某个待查询的Key在Level 0的多个文件中都存在。

这样的话LevelDb的策略是先找出level 0中哪些文件包含这个key（manifest 文件中记载了level和对应的文件及文件里key的范围信息，LevelDb在内存中保留这种映射表），之后按照文件的新鲜程度排序（更新的思路），新的文件排在前面，之后依次查找，读出key对应的value。而如果是非level 0的话，因为这个level的文件之间key是不重叠的，所以只从一个文件就可以找到key对应的value。

那么当Level DB得到了Key，获得了Manifest 文件中的 Key的范围后，如何进行寻找？

Level DB会先去内存的Cache中查找是否缓存了这个文件（节省IO），如果没有缓存，就将文件的索引拉进内存，并放入Cache中。注意这里只有索引部分，随后按照索引找到对应的DataBlock，查看是否含有这个Key，如果没有的话，继续下一Level的查找。

Compaction 过程¶

Level DB为了保证写入的简单性，可能会导致出现无用的Key（比如需要被修改的Key）记录，为了加快读取和减少存储的数据，Level DB采取了Compaction对已有的记录进行整理压缩，从而删除无效记录，减少数据规模，减少文件数量。

Level DB 包含两类的 Compaction: - Minor Compaction - Major Compaction

Minor Compaction¶

针对于 MemTable内存持有的数据达到阈值之后，将其持久化到磁盘的过程。

当MemTable持有的数据到达阈值后，MemTable会变为Immutable MemTable，此时不能再向其中写入数据。由于MemTable的结构是多层级的跳表，持有的数据是按Key有序排列的。

因而Minor Compaction只需按照Immutable MemTable的记录，从小到大的进行遍历，写入一个Level 0的新建SSTable文件中，建立完之后，构建对应的Index文件，随后就完成了Minor Compaction。

但是，对于被删除的记录，在Minor Compaction中，并没有任何的处理，因为无法直接的定位到Key存在于哪个文件中，进行这个操作需要进行一次读操作。

Major Compaction¶

当某个Level 下的 SSTable 文件数目超过一定的值之后，LevelDB会在这个Level（>0）中选择一个文件，将其与高一级的SSTable文件进行合并。

除去Level 0外的层级中，每个SSTable文件的Key都是从小到大有序存储，并且不同文件不会出现Key范围重叠的问题，所以对于非0层级的Major Compaction，只需要挑选一个文件即可进行。而对于Level 0，需要找出所有重叠的文件参与Major Compaction，即可能存在多个文件参与Major Compaction。

Level DB选择本层文件进行Major Compaction的时候，遵循按照顺序依次进行，比如本次为1文件进行Major Compaction，下一次就是紧邻着1文件的2文件进行Major Compaction。

那么给定一系列的文件之后，如何进行合并，保证之前文件有序的情况下，生成的文件也保持有序，同时抛弃无效的Key:Value记录呢？

Major Compaction 对于多个文件先采取多路归并排序的方式，依次找出最小的Key记录，也就是多个有序记录进行重排序。之后判断这个记录是否有保存的价值（判断在本层之前，是否存在该Key，即有新的Key记录），如果没有抛弃，有则写如Level i+1 层新的SSTable文件当中。直到最后，抛弃掉这些参与Major Compaction的文件，完成本次Major Compaction。