读了一遍leveldb作者写的实现笔记，记(fan)录(yi）要（yi)点(bian)， 该文回答了以下问题：
- leveldb数据是如何组织的
- 读，写，删是如何工作的
- 合并是如何工作的
日志文件
一个日志文件(log file)记录了一系列最新的更新。每个更新都追加到当前的日志文件中。 当日志文件到达一个预先设置的阈值（默认为4M左右），当前日志文件会被转换为一个sst文件， 然后创建一个新的日志文件来保存将来的更新操作。当前的日志文件在内存里面也保留了一份(memtable)。内存中的副本，可以让读操作获取到最近的更新，避免读到陈旧数据。
有序表
有序表（.sst文件）存储了一系列按key排序的键值对（对，有序的）。每个键值对要么包含了某个key对应的value，要么记录着一个删除标记，表示某个key已经被删除了。（删除标记的保留可以防止老的有序表中的值被读取到）
一组有序表集合被组织为多个层次（levels）。有序表产生的来源有两个，一个由日志文件转化而来，另一个是由低层中的sst文件合并而来。日志文件产生的有序表位于一个特殊层，叫做level-0， 即0层。当0层中的文件数量超过一个预设阈值（默认为4）时，做文件合并：将所有0层中的文件，以及1层中key范围与其有重合的文件，做合并操作，产生新的有序表，放到1层中（默认1层中每个文件的大小是2MB）。
0层中文件包含的key的范围可能相互间存在交集，但其它层的文件包含的key的范围是没有交集的。对于L层中的文件，L >= 1，当所有文件的大小加起来超过了（10 ^ LMB）（i.e, 1层是10MB，2层是100MB。。。）时，将L层的一个文件，与L+1层中所有key范围与其重合的文件合并，产生一组新的文件到L+1层中。这些合并的效果很明显： 只是用一些读和写操作，逐渐将0层中的最近更新迁移到最高层，最小化磁盘寻道带来的性能损耗。但问题来了，如何从L层中选择一个文件去和L+1层中的文件合并呢？ 简单来说，就是按照key轮转， 具体细节参考合并部分。
Manifest文件
Manifest文件列出了每一层所有的有序表，每个有序表包含的key的范围，以及其他的元数据。在一个数据库在被再次打开时，一个新的MANIFEST文件会被建立（文件名中有个新的数字）。MANIFEST文件和日志文件操作的方式一致， 记录数据库状态改变（文件增加或者删除）的信息会被追加到MANIFEST文件的结尾。
Current文件
CURRENT文件是个包含了最新版本MANIFEST名字的简单文本文件。
Info日志文件
运行时信息输入到LOG文件和LOG.old文件中。
其它文件
LOCK文件，临时文件等等。
0 层
当日志文件增长超过一定的大小时（默认1MB）：
- 创建一个全新的的memtable和日志文件，新的更新写入新建的memtable和日志文件中
-
在后台，做要做如下几件事情：
- 将之前的memtable的内容写入一个有序表
- 删除memtable中的内容
- 删除旧的日志文件和旧的memtable
- 将新的有序表加入到0层
合并
当第L层的大小超过限制，一个后台线程对其进行合并。合并线程会从第L层中挑出一个有序表文件，并且找到第L+1层中所有和这个文件的key范围重合的有序表文件。注意，即使一个L层有序表的key范围只和L+1层某个有序表的key范围部分重合，这个L+1层的有序表的整个文件都要作为合并操作的输入，合并完成后，这个文件将会被丢弃。另外：由于0层比较特殊(有序表文件的key范围可以相互重合)，0层和1层的合并需要被特殊处理：一个涉及0层的合并操作有可能从0层中选取多个有序表，只要它们的key范围相互重合。
对L层的合并操作会合并被选取的文件（L层的一个文件和L+1层的若干个文件）的内容，产生一系列的第L+1层文件。何时产生文件？当合并操作产生的输出文件超过目标大小时（2M），就会在第L+1层产生一个新的文件。另外，当合并操作输出文件的key范围增长到足以覆盖10个以上的L+2层文件时，也会在L+1层产生一个文件，这可以防止后续对L+1层的某个文件进行合并时，从L+2层选取太多的数据。
合并完成时，旧的文件会被丢弃，新文件会加入到MANIFEST中，更新数据库的状态信息。
上面问到了，当对L层文件进行合并时，如何从多个有序表文件中选取出一个。具体做法是，按照key轮转。由于很容易得到L层文件包含的所有key的排序信息，我们可以从包含最小key的文件开始；每次合并的时候，计算出从L层选取的文件包含的key范围，记录该范围的结束key；下次做合并时，找到起始key刚好大于这个结束key的文件，选取这个文件做合并操作。
L层的合并操作，会丢弃L+1层被覆盖的值（很简单，新值代替旧值）；而对带有删除标记的key/value对，如果任何一个位于大于L层的文件不包含这个key，该删除标记也会被丢弃（删除的对象不存在）。
合并耗时
0层合并操作会从0层中最多读4个1MB的文件，且最坏情况下会读取1层的所有文件（1层中所有文件的key范围和被选取的0层文件的key范围都有重合）。此时，最多读取14MB，写14MB。
除了特殊的0层合并，对于其他任意L > 0层的合并，会从L层选取一个2MB的文件。最坏情况下，该文件的key范围会同12个L+1层文件的key范围重合（10是因为L+1层文件总数是L层文件数的10倍，参考合并细节； 2是因为L层和L+1层文件的key范围往往不会对齐），所以合并操作会读26MB，写26MB。假设磁盘的吞吐是100MB/s, 那么最慢的时候合并会花0.5s。
如果我们限制后台线程合并线程的写的速度，比如100M/s吞吐的10%，一次合并操作最多花上5s。如果用户以10MB/s的速度写，那么在一次合并操作期间，0层会产生很多文件（最有能有50个， 5 * 10M/1M）。0层中文件多对读操作很不利，因为0层文件的key范围是可以重合的，每做一次读，都需要对多个文件做一次合并的操作。解决方案：
- 当0层文件数变多时，增加memtable的大小。增加memtable的大小可以减少memtable的数量，但是需要耗费更多的内存。
- 当0层文件变多时，可以人为降低写入速度
- 大部分的0层文件可能都是以未压缩的状态存在于缓存中，因此解决读操作中复杂度为O(N)的大范围合并问题，可以降低读的性能损耗
文件数量
我们可以增加文件的大小，不再生成一些2MB的文件，生成8M, 16M等等大小，更大的文件意味着更少的文件数量，但是以为着合并操作中更动的读写。或者，将文件分布到不同的目录中，也可能是个选项。
故障恢复
故障恢复的步骤：
- 读取CURRENT文件找到最近提交的MANIFEST文件的名字
- 读取目标MENIFEST文件
- 清理过时文件
- 可以打开所有的有序表，或者等到用到的时候打开
- 将日志文件转化为新的0层文件
- 将新的写操作写入到新的日志文件
文件的垃圾回收
DeleteObsoleteFiles()在每次合并结束的时候或者故障恢复结束的时候会被调用。执行时，该函数会找到数据库中所有文件的名字，然后删掉除当前正在使用的日志文件外的所有日志文件，删除所有不被任何层级引用，也不是任意合并操作生成的有序表文件。
Ref:
- https://leveldb.googlecode.com/svn/trunk/doc/impl.html
- https://en.wikipedia.org/wiki/Log-structured_merge-tree