这部分是来自于leveldb的impl.md文档，详细介绍了leveldb实现方面的设计。
Contents
1、文件
leveldb其实是Bigtable的简单的实现。Bigtable论文地址:http://research.google.com/archive/bigtable.html。当然，文件的组织方法和bigtable有一些不同之处，下面会逐个介绍。
1.1 日志文件
一个日志文件(*.log)存储一系列的最近的更新。每一个更新都会添加到当前日志文件的最后。当所有日志文件达到了预定义的大小（默认是4M），它会转换成一个有序的表（参见下面介绍），一个新的日志文件被创建提供给之后的更新。
当前日志文件的副本是保存在一个内存结构中（称为memtable）。每一次读都会向这个memtable中查询，所以读操作其实还是映射到所有记录下来的更新中。
2.有序表
一个有序表(*.ldb)存储了一系列的由键排序的键值对。每个键值对要么键对应着值，要么是键对应着一个删除标记。（删除标记保存在旧的排序表中存储着过时的值）。
排序表的集合是由一系列的等级(level)组织的。排序表如果是由一个日志文件生成，就会被置为一个特别的younglevel(也被称为level-0)。当young文件的数量超过了某个特定的阈值（当前是4），所有的young level文件和所有键范围重叠的level-1文件被合并在一起产生一系列的新的level-1文件（我们每2MB的数据创建一个新的level-1文件）
属于young level的文件可能自己相互包含重叠的键，但属于其他等级的文件有唯一的不重叠的键范围。level-L(L >= 1)，当level-L所有的文件大小超过了(10^L)MB（例如,level-1是10MB,level2是100MB），在level-L中取一个文件，和所有在level-(L+1)中与之重叠的文件，合并成level-(L+1)的新的文件集合。这些合并使得新的更新逐渐从young-level的文件转移到最大的等级,这个过程只需要批量的读写操作即可完成(注：最小的时间复杂度)
2.1 Manifest
一个MANIFEST文件中个列举了由各个level组成的有序表的集合,包含了相应的键范围，以及其他重要的元数据。任何时候数据库被打开，一个新的MANIFEST文件（文件名中有一个新的数字代表）被创建。MANIFEST文件和log文件的格式相同，任何发生的改变都会被添加到这个文件中（比如文件添加或者移除）。
2.2 Current
CURRENT是一个简单的文本文件，包含了最新的MANIFEST文件的名字。
2.3 信息日志（Info logs）
信息消息被打印到LOG和LOG.old文件中
2.4 其他
其他文件用来记录一些杂项。（LOCK，*.dbtmp)
3.Level 0
当一个日志文件增长到一个特定的值（默认1MB）：
创建一个新的memtable和log文件，并将未来的更新放在这里。
在后台的操作：
将上一个memtable的内容写入到sstable
丢弃上一个memtable
删除旧的日志文件和旧的memtable
将新的sstable添加到young(level 0) level。
4.压实（不是对数据进行压缩，只是将数据整合到一起，并且在这个过程中会去除重复键以及删除的键）
当level L超出了文件大小的限制，我们在另外一个后台线程中压实它。这个压实操作选择level L中的一个文件以及来自下一个level L+1的所有与之重叠的文件。注意：如果一个level-L文件只和一个level-(L+1)文件部分重叠，这个文件的所有部分都被作为压实的输入，然后在压实之后被丢弃。例外：因为level-0是特别的（level-0的文件可能彼此重叠），我们特殊对待从level-0到level-1的压实：当这些level-0文件彼此重叠时，一个level-0的压实会选择多个level-0的文件。
一个压实操作合并选择的文件的内容，产生一系列的level-(L+1)文件。在当前的输出文件超过目标文件大小(2MB)时，我们切换到一个产生的新的level-(L+1)文件。在当前输出文件的键范围增长到足够大，以致于和超过10个level-(L+2)的文件产生重叠时，我们同样切换到产生的新的输出文件。最后一条准则保证了之后的一次level-(L+1)文件压实不会从level-(L+2)中选择太多的数据。
旧的文件被丢弃，新的文件被加入到服务状态。
特定level的压实通过键空间的压实。详细来说，对于每个level L，我们记住最后一次level L的压实的结尾的键。下一次level L的压实将会选择在这个键之后的第一个文件（如果没有这个文件，就从键空间的起点环绕。
压实会丢弃覆盖的值，如果没有更大的数字level包含一个范围重叠当前键的文件，也会丢弃删除标记。
4.1 时间复杂度
level-0的压实将会从level-0中读取最多4个1MB的文件,在最坏情况下读取所有的level-1文件(10MB)。这样一来，我们将会读取14MB,写入14MB。
对于其他等级的压实，我们将会从level L中选择一个2MB的文件。最坏的情况下，将会从level L+1中重叠大概12个文件（10个文件是因为level-(L+1)是level-L的10倍大，其他在两边的两个文件是因为level L的文件范围通常和level-(L+1)的文件范围是不对齐的）。压实因此会读取26MB，写入26MB。假设磁盘IO速度为100MB/s，最差的压实大概消耗0.5s
如果我们减慢后台写入，只取全速100MB/s的10%，一次压实可能耗时5s。如果用户的写入速度为10MB/s，我们可能创建许多level-0的文件（大概5*10MB总共50MB）。这将明显的增加读取消耗，因为每次读取合并了更多的文件增加了负载。
解决方案1：为了减轻这个问题，我们可能希望当level-0文件数很大的时候，增加日志切换的阈值。虽然缺点是这个阈值越大，需要越多的内存来保存相应的memtable。
解决方案2:我们可能希望当level-0的文件数变多时，人为增加写入速度。
解决方案3：我们致力于降低大量文件合并的成本。也许大多数level-0文件在缓存中都有未压缩的块，我们仅仅需要担心O(N)复杂度的合并迭代。
4.2 文件的数量
除了总是生成2MB的文件，我们也可以为更高的等级生成更大的文件，以此减少文件的总数，虽然代价是更多突发的压缩。当然，我们也可以将文件集合分片放在不同的文件夹中。
在2011年2月4日，在ex3文件系统上做了一次测试，该测试显示，在很多文件的目录中做100K次文件打开的平均用时如下：
| Files in directory | Microseconds to open a file |
|---|---|
| 1000 | 9 |
| 10000 | 10 |
| 100000 | 16 |
因此，在现代文件系统中，也许连分片也是不需要的。
5.恢复
- 读取CURRENT去找到最后一次提交的MANIFEST文件名
- 读取该MANIFEST文件
- 清除过期的文件
- 我们可以在这里打开所有的sstables，但是懒加载可能会更好。
- 将log块转换成新的level-0 sstable
- 开始将恢复的序列导向到新的日志文件的新的写入流。
6.文件的垃圾回收
每次恢复的最后以及每次压缩的最后DeleteObsoleteFiles()会被调用。它会找出数据库中所有的文件的名字。然后删除所有的不是当前日志文件的日志文件。再删除所有的不涉及到某些level和不是一个活跃的压缩输出的表文件。