区块链之LevelDB

一、leveldb简介
Leveldb是一个Google实现的非常高效的kv开源数据库，版本1.2能够支持billion级别的数据量了。 在这个数量级别下还有着非常高的性能，主要归功于它的良好的设计，实现原理是依据LSM-Tree（Log Structed-Merge Tree）算法。其在区块链底层存储也有很好的应用，以太坊链和波场链等比较熟知的公链底层都是采用LevelDB数据库存储。LevelDB 是单进程的服务，性能非常之高，在一台4核Q6600的CPU机器上，每秒钟写数据超过40w，而随机读的性能每秒钟超过10w。

二、leveldb设计思路
做过存储的同学都很清楚，对于普通机械磁盘，由于写 *** 作需要磁盘旋转和磁道寻址，顺序写的性能要比随机写的性能好很多。比如对于15000转的SAS盘，4K写IO，顺序写在200MB/s左右，而随机写性能可能只有1MB/s左右，LevelDB的设计正是利用了磁盘的这个特性。

LevelDB是依据LSM-Tree（Log Structed-Merge Tree）的原理实现的，LSM-Tree写性能极高，其原理简单地来说就是将磁盘的随机写转化为顺序写，从而大大提高了写速度。

LSM tree (log-structured merge-tree) 是一种对写 *** 作非常友好的存储方案。LSM tree 是许多 KV型或日志型数据库所依赖的核心实现，例如BigTable、HBase、Cassandra、LevelDB、SQLite、RocksDB 等，甚至在mangodb3.0中也带了一个可选的LSM引擎（由Wired Tiger 实现的）。

三、LSM-Tree算法原理
LSM-tree 是专门为KV存储系统设计的，Key-Value类型的存储系统最主要的两个功能，put（key，value）：写入一个Key-Value ; get（key）：给定一个 key 查找 value。
从名字看，由两部分组成“Log Structed”和“Merge Tree”。“Log Structed”是日志结构的意思，而我们常说的日志就是软件系统输出的执行信息，其特点就是不断追加的写入日志文件中，不需要更改，只需要在后边追加就好了。很多数据库在写 *** 作前的日志也是追加型的，因此说到日志结构，基本就是指“追加，Append-Only”。而“Merge Tree”，就是“合并树”的意思，就是把多个树合成一个大树。所以LSM-Tree就是数据以Append-Only方式写入文件，成为一颗小树，然后通过合并形成更大的树。

LSM tree是基于如下背景事实：简单来说，问题的本质还是磁盘随机 *** 作慢，顺序读写快的问题。磁盘或内存的连续读写性能远高于随机读写性能，有时候这种差距可以达到三个数量级之高。这种现象不仅对传统的机械硬盘成立，对SSD 硬盘也同样成立。

LSM-Tree被设计成通过避免随机 *** 作，充分发挥了连续读写的性能优势，采用Append-Only的日志追加的方式进行写 *** 作，通过扬长避短达到了比传统的B+树更好的写性能，不失为一个好方法、好思路。打破了过去传统的思路“更新某个数据必须要同时覆盖旧的数据”的束缚（这带来了无数问题），开启了“更新某个数据不需要覆盖旧的数据”的完全不同的设计理念。

”扬长“付出的代价就是牺牲部分读性能、写放大（B-Tree/B+Tree 同样有写放大的问题）。而”避短“则进行了大量的读优化，使用了空间换时间的思想。

三、leveldb整体架构

LevelDB由以下几个重要的组件构成：

（1）MemTable：这是常驻内存的C0树，写 *** 作数据的落脚点。写 *** 作并不是直接将数据写入磁盘文件，而是写入内存的MemTable后即表示写成功，然后返回。MemTable就是一个在内存中进行数据组织和维护的数据结构，其本质是一个跳表SkipList，而之所以选用跳表这种数据结构，是由于其应用场景决定的。跳表SkipList这种数据结构的设计来源于数组的二分查找算法，把指针通过设计成数组的方式实现了数组二分查找的高效，使用了用空间换时间的思想。跳表SkipList在查找效率上可比拟二叉查找树，绝大多数情况下时间复杂度为O(log n)。这契合了LevelDB快速查找Key的需要。在MemTable中，所有的数据按用户定义的排序方法排序后有序存储，当其数据容量达到阈值（默认是4MB）时，则将其转化了一个只读的MemTable，即：Immutable MemTable。同时创建一个新的MemTable供用户继续读写。

（2）Immutable MemTable：当MemTable数据容量达到阈值（默认是4MB）时，则将其转化了一个只读的MemTable，即：Immutable MemTable。这两者的结构定义完全一样，区别只是Immutable MemTable只读。后台的Compaction线程会将Immutable MemTable中的内容，创建一个SSTable文件，持久化到该磁盘文件中。

（3）log（journal）日志文件：持久化的存储系统为了防止机器掉电或系统宕机造成正在写入的数据丢失，在写 *** 作时通常都会先写日志，将要写入的数据先保存下来，若发生机器掉电或系统宕机，机器恢复后，可以读该日志文件恢复待写入的数据。LevelDB也是如此，LevelDB在写入内存MemTable之前，先写入Log日志文件，再写内存MemTable。当发生以下异常情况时，均可以通过Log日志文件进行恢复。

1）写log时，进程异常
2）写log完成，写内存未完成
3）写 *** 作完成（即：写log、写内存MemTable均完成），进程异常
4）Immutable MemTable持久化过程中进程异常
5）其他压缩异常

当出现1）中异常时，数据库重启读取log日志文件，发现log日志文件异常，则认为此次用户写入 *** 作失败，这样保障了数据的一致性。当2）3）4）异常发生时，用户上次写入的数据、MemTable、Immutable MemTable中的内存数据必然会丢失，而数据库重启后要读取log日志文件，都可以重新恢复出用户上次写入的数据、MemTable、Immutable MemTable。这也意味着log日志文件保留了所有的写入数据（包括旧数据），随着频繁地写 *** 作，log日志文件必然随之膨胀。已经持久化地数据SSTable文件，不应该再恢复，它只在数据库损坏情况下，修复数据库时用来恢复SSTable文件，此时，如果log日志文件太大，势必恢复起来非常耗时间。

此外，LevelDB的用户写 *** 作的原子性同样通过日志来实现。

（4）SSTable文件：虽然LevelDB的写 *** 作是写内存中的MemTable，但是写内存不可能无限的膨胀，一旦机器掉电或系统宕机，恢复起来必然时间很长，因此当内存中数据容量达到阈值（默认是4MB）时，则将其转化了一个只读的MemTable，即：Immutable MemTable，然后创建SSTable文件来保存内存中的数据。除了少数元数据信息，LevelDB中的数据都是通过SSTable存储的。何谓SSTable？就是Sorted String Table，有序的固化表文件，有序体现在Key是按序存储的，也体现在除了Level-0之外，其他Level中的SSTable文件之间也是Key有序的，即：Key不重叠。

为何会有这样特点的SSTable文件呢？本质还是为了查找方便，为了读性能！查找算法最好的就是二分查找算法，要想使用二分查找算法，就要保证每个SSTable文件中的Key是有序排列，但是在Level-0，由于直接由内存中的Immutable MemTable新创建的SSTable文件，而内存中的Immutable MemTable存储的Key数据是有重复的，有重叠的，这样查找起来就要查找多个SSTable文件，查找效率低下。因此，就需要有一个额外的线程定期地来整理这些SSTable文件，使之没有重叠，并且减少文件个数目，从而减少磁盘IO的次数，这样就可以方便的使用二分查找算法，这个额外的线程就是Compaction压缩线程。

注意，所有的SSTable文件本身是不可修改的，Compaction压缩线程会把多个SSTable文件归并后产生新的SStable文件，并删除旧的SSTable文件。由于Level-0是直接由内存Immutable MemTable中的数据转化而来，所以Level-0中的SSTable文件中的Key是存在重叠的，不同的SSTable文件也存在Key重叠的情况，因此Level-0会有很多的限制条件，1）Level-0中文件的个数达到4个时，会触发压缩Compaction；2）Level-0中文件的个数达到8个时，写入 *** 作将会受到限制；3）Level-0中文件的个数达到12个时，写入 *** 作将会被停止。

后期归并生成的SSTable文件在Level-i层，这就是LevelDB的名字的由来。而之所以叫leveled，而不是tiered，是因为第i+1层的数据量是i层的倍数。 这种设计哲学为LevelDB带来了许多优势，简化了很多设计。

（5）Manifest文件：LevelDB中有版本Version的概念，一个版本Version主要记录了每一层Level中所有文件的元数据。std::vector files_[config::kNumLevels];，而一个文件的元数据主要信息包含：文件号、文件大小、最大的Key和最小的Key等。每次Compaction完成，LevelDB都会创建又给新的Version，newVersion=oldVersion+VersionEdit，其中VersionEdit是指在oldVersion基础上变化的内容（新增或减少的SSTable文件）。Manifest文件就是用来记录这些VersionEdit信息的。一个VersionEdit信息会被编码成一条Record记录，写入Manifest文件，每条记录包括：1）新增哪些SSTable文件；2）删除哪些SSTable文件；3）当前Compaction的指针下标；4）日志文件编号；5） *** 作SequenceNumber等信息。通过这些信息LevelDB在启动时便可以基于一个空的Version，不断地Apply这些记录，最终得到一个上次运行结束时的版本信息。

下图便是一个Manifest文件示意图：

（6）Current文件：这个文件中只有一个信息，就是记录当前的Manifest文件名。

因为每次LevelDB启动时，都会创建一个新的Manifest文件。因此数据目录可能会存在多个Manifest文件。Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

（7）Compaction压缩：LSM-Tree中有两种压缩策略Size-Tiered Compaction Strategy和Leveled Compaction Strategy。LevelDB采用的是Leveled Compaction Strategy。SSTable被划分到不同的Level中，Level-0层的SSTable文件中的Key是存在相互重叠的，且限制默认文件个数是4个。除Level-0层，Level-i（i>0）中的SSTable文件之间所包含的Key是不重叠的，全局有序，任意两级Level之间的SSTable文件容量呈指数级倍数。在Compaction过程中，首先对参与压缩的SSTable文件按key进行归并排序，然后将排序后结果写入到新的SSTable文件中，删除参与Comaction的旧SSTable文件。

以上是对LevelDB的总体介绍，谢谢。

技术交流请加微信：wxid_508b6ru2awt022