LevelDB RocksDB Boltdb Comparion
LevelDB
LevelDB 是 Google 的 Jeff Dean和Sanjay Ghemawat 设计开发的KV存储类型的依赖包，其本质是一个有序的数据Map。
LevelDB 底层采用 LSM-Tree 数据结构，设计实现类似于单个节点的Bigtable tablet ，两者底层存储的文件数据不一样。
LevelDB 的每个 database 由某个目录下的一堆有序文件组成。其中包含的文件类型有:
log file
用于存储一系列更新的操作。每个操作都会append到当前log 文件，当log文件达到预定大小（默认约为4MB）时，log文件会转换成一个sorted table，并创建出一个新的log文件用于存储新的updates操作。
当前正在写入log file的数据会有一份副本保存在内存结构（memtable）中。每次读取数据都会查阅内存中的副本数据。
Sorted tables
一个sorted table (*.ldb) 存储了一系列基于key排序的数据，每条数据要么是key的value，要么是删除标记。（删除标记是为了隐藏sorted table中已经被删除的数据）。
一系列sorted table 用level级别管理起来，默认生成的sorted table的level是0级别，当level-0级别的文件数量超过了阈值（当前是4），会将4个level-0的文件与已有的level-1文件进行合并。（level-1级别每mb生成一个文件。）
在初级的文件可能包含重复的keys，但是在其他层级这些keys会去重。当Level-L级别的文件存储超过(10^L) MB ，就会将其和Level-(L+1)的文件合并成新的文件。这些合并通过逐步迁移update操作丛低级别到高级别，采用批量读写的方式，保证迁移带来的搜索效率降低。
Manifest文件
MANIFEST 文件列出了组成每个level的sorted tables，以及sorted table的键值范围和其他重要元数据。每当database打开的时候，一个Manifest文件（伴随着一个number）都会创建。MANIFEST 文件会用来做日志记录，当产生文件的添加和删除都会追加到MANIFEST 文件中。
Current
CURRENT 是一个text文件，用于描述当前最新Manifest文件的名字。
Info logs
日志信息会打印到 LOG and LOG.old 文件中。
Others
还有一些其他用处的文件，比如 LOCK, *.dbtmp。
Level 0
当 log file 增长到一个确定的大小（默认是4MB）: 创建一个新的memtable和log file，用于处理新的请求。后台的步骤如下:
- 将当前memtable写入到一个sstable中。
- 放弃当前memtable。
- 删除老的log file 和老的memtable。
- 添加一个新的sstable加入到level-0层级中。
Compactions
当Level-L的大小超过它的limit，会使用一个后台线程进行压缩。从Level L级别中抽取一个文件，将其和所有Level+1有重叠的文件进行合并。由于Level-L是Level L+1 级别的一部分，当压缩完成后，原有用于合并的Level- L+1的文件会丢弃。对于Level-1和Level-0级别的文件比较特殊，可能会选取多个Level-0级别的文件与Level-1进行合并，因为Level-0级别的文件会有一些重叠。
压缩产生一系列level-(L+1)级别的文件，如果当前输出文件达到(2MB)大小，就会切换输出一个新的level-(L+1)文件。当当前输出的文件键值对范围与下一级别的文件重叠超过了10个文件，也会切换到一个新的文件进行输出，这条规则保证了压缩不会从下一级别抽取太多的数据。
旧的文件文件被丢弃，新文件会标记为处于服务状态。
对于每个Level L级别的文件，我们会记住最后一次压缩的末尾key。下一次压缩会从这个key之后的第一个文件进行合并。（如果没有这个文件，就会将这个key所在文件进行压缩）
压缩会丢弃覆盖的值。如果没有更高Level的文件键值对包含了当前key，就会舍弃已经标记为删除的数据。
Timing
Level-0 级别的压缩，读取四个1MB Level-0文件，最多读取10MB的Level-1文件。我们会读取14MB并写入14MB。
除了Level-0级别的压缩比较特殊，比如我们从 Level-0 读取一个2MB的文件，最坏的情况下，这将与Level L+1 重叠12个文件（其中10个文件是因为Level L+1 是 Level L 的10倍文件范围，另外两个文件处于边界范围，因为Level L与Level L+1的文件范围对齐）。因此，压缩将读取 26MB 并写入 26MB。假设磁盘 IO 速率为 100MB/s（现代驱动器的大致范围），最差的压缩成本将约为 0.5 秒
如果我们将后台写入限制为较小的值，例如 100MB/s 速度的 10%，则压缩可能需要 5 秒。如果用户以 10MB/s 的速度写入，我们可能会构建大量的 0 级文件（约 50 个来容纳 5*10MB）。由于在每次读取时将更多文件合并在一起的开销，这可能会显着增加读取成本。
解决读取成本过高的问题有三种方案：
方案一: 增加log file 阈值大小，这种方式会需要更多的内存保存对应的memtable。
方案二: 降低写入速率。
方案三: 在内存memtable中提前合并，提高效率。
Number of files
与其总是产生2MB的文件，我们可以增加文件大小，减少产生的文件数目。
可能会带来更多的突发性的压缩，我们可以将文件存储到多个目录中。
有一项关于在目录中打开文件数的消耗时间对比:
| 目录文件数 | 打开一个文件的时间 |
|---|---|
| 1000 | 9 |
| 10000 | 10 |
| 100000 | 16 |
| 10w文件数打开时间是16ms，所以不分目录效率也还好。 |
Recovery
恢复流程如下:
- 读取 CURRENT 文件找到最新提交的 MANIFEST 文件
- 读取 MANIFEST 文件
- 清理旧文件
- 我们可以打开所有的sstables，但最好是懒加载。
- 将log chunk 转换成一个新的level-0 sstable。
- 开始将新的写入到一个新的拥有恢复序列的日志文件。
Garbage collection of files
在每次压缩结束和恢复结束的时候都会调用 RemoveObsoleteFiles 方法。它会查找数据库所有文件，它会删除所有不是当前当前日志文件的日志文件。它会删除所有未从某个Level引用且不是当前正在压缩的输出的table文件。
RocksDB
Rocksdb 是fackebook数据库团队提供。也是采用 Log-Structured-Merge-Database (LSM) 数据结构，可在读放大，写放大， 空间放大之间做好权衡。具有多线程压缩数据的功能，可以用于存储数TB级别的数据。
LSM 介绍
LSM 原理是将数据先写入内存中， 当满足一定大小后，将其刷写到磁盘上生成一个文件。
随着文件越来越多，读操作需要查询多个文件。所以LSM具备Compaction 机制，将生成的文件不停的合并，保证读操作性能。
Compaction 机制有一些取舍，如果不做compaction操作，读取操作性能会越来越低，如果生成文件就立即执行compaction操作，对磁盘压力也很大。
compaction机制的取舍会带来以下三个问题:
读放大: LSM 将数据拆分成很多个文件，需要逐级查找，想要查询到想要的数据，可能需要不止一次I/O操作，打开多个文件。
空间放大: 由于LSM都有定期压缩的功能，所以无效数据不会立即清理，空间存储有冗余数据。
写放大:从用户视角是写了一遍数据，但是在后台包含 redo log的写入/内存数据 Immutable Memtable 写入到 L0 文件以及文件进行压缩重新回写磁盘。
LSM Compaction 有level 和 size-tiered两种实现。
Size-Tiered Compaction
从名字可以看出Size-Tiered 是当Level 0里的文件数量达到一定数量，就开始进行合并至Level 1。每一层都有文件数量的条件判断，满足就进行Compaction。这种方式导致每一层都不是全局有序，只能保证某个文件是有序的。
Leveled Compaction
Leveled 保证每一层都是全局有序的，当Level 0有四个文件后，就将Level 0里文件与Level 1的数据进行合并，保证Level 1全局有序。
Boltdb
boltdb 相比于rocksdb和leveldb，采用的是b+tree数据结构。如果你的场景是大量的随机读写，leveldb是一个不错的选择。如果你的应用读取需要大量读取或者进行大范围的范围扫描，boltdb是一个不错的选择。