刚刚进入工作大半年，深感职场与学校的氛围差异之大，不免时常在对过去的反省和未来的思考中产生一些沮丧。好在工作氛围轻松，压力也不甚大，因此也有机会自己去学习更多额外的知识，阅读一些有趣的开源项目。LevelDB 不是这段时间以来阅读的第一个项目，但却是在代码风格上最工整最清楚的一个。因此这里简要的记录一下阅读心得，以备以后温固。
LevelDB 简介
LevelDB 是 google 的两位大神 Jeff Dean 和 Sanjay Ghemawat 开发的一个单机持久化 K/V 数据库。其基于 LSM(LOG Structured Merge Tree) 实现，将所有的 Key/Value 按照 Key 的词法序有序地储存在文件中，具有很高的随机/顺序写性能，非常适用于写多读少的环境。根据 LevelDB 的官网介绍，其具有特性如下：
- Keys 和 Values 可以是任意的字节序列
- 数据是按照 Key 排序的
- 调用者可以提供一个定制的比较函数来决定 Keys 的排序方式。
- 针对数据库的操作非常简单，i.e.
Put,Get,Delete - 可以在一次原子的批处理中同时多次修改数据库
- 用户可以创建 snapshot 保持对于数据视图的一致性
- 这个数据结构提供前向和后向的迭代器 (iterator)
- 数据可以自动经过 Snappy 算法压缩
- 针对于操作系统文件的交互操作，LevelDB 提供给外部用户一个可以定制的虚拟的接口(Env)
这些特性初看起来可能很难理解，但是随着后续阅读的深入，可以很清楚地看到它们是如何一步一步反映到代码中的。当然，LevelDB 并不是一个通用的数据库，其同样具有一些使用场景的限制:
- LevelDB 不是一个 SQL 数据库，它不支持关系数据模型，不支持 SQL 语言，也不支持索引。
- 在同一时刻只允许单个进程（可以是多线程）访问数据库。
- 在整个工程中不提供 Client-Server 的网络支持，任何需要类似支持的应用需要自行包装。（e.g. ssdb）
目录结构
整个项目的基本结构如下：
leveldb
+--- util <== 通用的工具代码
+--- port <== 为可移植准备的平台相关接口
+--- table <== table相关实现
+--- db <== db的所有实现
+--- helpers
+--- memenv <== Env的一个具体实现(Env是leveldb封装的运行环境)
+--- doc
+--- table_format.txt <== 磁盘文件数据结构说明
+--- log_format.txt <== 日志文件数据结构说明
+--- impl.html <== 实现说明
+--- index.html <== 使用说明
+--- bench.html <== 测试数据
+--- include
+--- leveldb <== 所有头文件
+--- c.h <== 提供给C的接口
+--- cache.h
+--- comparator.h
+--- db.h
+--- env.h
+--- filter_policy.h
+--- iterator.h
+--- options.h
+--- slice.h
+--- status.h
+--- table.h
+--- table_builder.h
+--- write_batch.h
LevelDB 整体的设计如下图：
从图中可以看出，构成 levelDB 的静态结构主要有六个部分，存储在内存中的 memtable 和 Immutable memtable，存储在磁盘上的 CURRENT 文件，log 文件，MANIFEST 文件，SSTable 文件。这里先简要的介绍一下 LevelDB 的写入流程：
- 每次写入一个 Key/Value 对时，首先将该数据追加到 log 中，然后再将其写入到内存的 memtable。memtable 是一个基于 SkipList 的有序的结构，每一个 Key 都会按序组织到 memtable 中。
- 当 memtable 中的数据量达到一定的限制后，其将会转变成为一个 Immutable memtable，同时 levelDB 会新建新的 Log 文件和 memtable 结构用来接收后续的插入操作。
- 内存在的 Immutable memtable 将会被后台的线程持久化的存储到磁盘中，行成按序 sstable 文件。
- 磁盘上的 sstable 文件按照 level 的形式组织，从 memtable 序列化得到的 sst 文件位于 level0 层。由于经过 compaction 线程的压缩，文件将不断地从 level n 层向 level n+1层移动。这也就是 levelDB 命名的由来。
有关 LevelDB 的简介就到此为止，后面我们将一点一点的剖析其实现过程。