levelDB源码阅读
架构分析
整体结构
- memtable：skiplist
- Immutable MemTable：当MemTable数据容量达到阈值（默认是4MB）时，则将其转化了一个只读的MemTable，即：Immutable MemTable。这两者的结构定义完全一样，区别只是Immutable MemTable只读。
- log（journal）日志文件：WAL。
- SSTable：当内存中数据容量达到阈值（默认是4MB）时，则将其转化了一个只读的MemTable，即：Immutable MemTable，然后创建SSTable文件来保存内存中的数据。
- Manifest文件：LevelDB中有版本Version的概念，一个版本Version主要记录了每一层Level中所有文件的元数据。
- Current文件：这个文件中只有一个信息，就是记录当前的Manifest文件名。
- 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文件。
LSMtree的原理及实现
LSM-tree 的组成部分，是一个多层结构，由C0，C1，…，Ck树，由小到大。首先是内存的 C0 层，保存了最近所有写入的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每一层都是一个在 key 上有序的结构。
写入操作：put（k，v）会首先追加到WAL日志中（Write Ahead Log，也就是真正写入之前先记录到日志，防止宕机丢失数据），接下来加到 C0 层的内存树，当 C0 层的数据达到一定大小，会触发C0 层 和 C1 层合并，类似于归并排序，这个过程就是Compaction（合并）。而归并操作本身是只有顺序写，合并出来的新的 new-C1 会替换掉原来的 old-C1。当 C1 层达到一定大小，则继续和下层Ck合并。合并之后所有的旧文件都可以删掉，只留下新的。由于Key-Value的写入可能重复，新版本需要覆盖老版本。比如，先写a=10，再写a=20，20就是新版本。如过 a=10的 老版本已经到 Ck 层了，这时候 C0 层来了个新版本a=20，此时并不会去管底层的文件有没有老版本a=10，老版本a=10的清理是在合并Compaction的时候清理掉。写入过程基本只用到了内存，Compaction 是在后台异步完成的，不阻塞写入。
读操作：get（key）由于最新的数据在内存的C0层，最老的数据在 Ck 层，因此查询也是先查 C0 层，如果没有要查的 key，再查 C1层，依次逐层查。由于一次查询可能需要多次查找操作，因此读操作会稍微慢一些。所以 LSM-tree 主要针对的是写多读少的场景。