LevelDB是一个Google开源的一个Key-Value高性能单机数据库。它最初的作者是Jeff Dean和Sanjay Ghemawat两位大神。LevelDB无论设计还是实现细节都非常优秀，通过阅读开源代码，我们可以一睹两位大神风采。
LevelDB采用分布式系统中常用的Merge-Dump模型。它将用户最新的修改保存在内存中的MemTable结构中，同时在磁盘上记录操作日志，待内存中积攒的数据足够多才在磁盘上写出SSTable文件。数据库中的绝大部分数据存在于若干SSTable文件中，每个SSTable文件一旦写完成就不会修改，因此SSTable天生就支持高并发的读操作。MemTable则需要同时支持读写操作，这也是Merge-Dump模型中唯一需要处理并发读写的部分。处理用户的读操作时，”首当其冲”的便是MemTable，若不命中才会继续查询磁盘上的SSTable，所以MemTable的并发性能就显得尤为重要。
在执行每个更新操作时，LevelDB会分配一个递增的序号。该序号随着用户数据一起保存在MemTable中，并最终持久化到磁盘上。LevelDB保存相同key不同版本的value，以更新分配的序号标识版本。假如我们将数据库中所有小于等于某个序号的所有数据抽出来，这些数据就可以表示数据库的某一历史状态。
DB* db = NULL;
WriteOptions wo;
ReadOptions ro;
const Snapshot* snapshot = NULL;
string v;
// 初始化数据库...
db->Put(wo, "x", "1");
snapshot = db->GetSnapshot(); // 取得当前系统的快照
db->Put(wo, "x", "2");
db->Get(ro, "x", &v); // v == "2"
ro.snapshot = snapshot;
db->Get(ro, "x", &v); // 读快照中的数据，v == "1"
db->ReleaseSnapshot(snapshot);
快照是一种内存状态，用户需要显式地创建和释放快照，LevelDB在内存中维护了当前使用的快照列表。创建快照操作局限在当前时刻，用户只能创建系统在当前时刻快照，而无法在事后创建某个历史时刻的快照。这是因为LevelDB需要定期删除无用的旧版本数据来回收空间，数据一旦被删除后就无法”复生”了。在上例中，第一次写的数据被第二次覆盖了，由于我们持有了两次写之间的快照，通过这个快照我们仍然可以读到第一次写的数据。当ReleaseSnapshot()调用完成后，我们就再也无法读到第一次写的数据，即使以后再创建新快照也不能，至此我们才可以安全地删除它。这也是用户不能创建历史快照的原因。
MemTable内部使用跳跃表将数据有序地组织起来。从功能上说，跳跃表就是一个增强版的Map，和传统的平衡树实现相比，它有以下特点：
- 多线程读，单线程写，读写不互斥
- 实现简单，核心的插入和查找方法只有十余行代码
- 在概率上平衡，算法复杂度与平衡树相当，在最差情况下查询和插入操作可能是O(n)的（尽管这非常难发生）
MemTable保留了所有版本的数据，包括那些已经确信无用的版本。这是因为是删除操作需要和读互斥，无法无锁实现。此外，由于MemTable的生命期较短，在dump阶段可以轻而易举地忽略掉那些不需要的版本。跳跃表的每个节点（除头节点外）以(key,序号,value)的形式存储用户数据，首先比较key，对于同一个key的不同版本value，取序号较大（即写入时间晚）的存放在前面。因为序号总是严格递增，所以不会出现两个节点有相同序号的情况。这个比较顺序在查找时也会用到。
MemTable的查询接口支持在给定的快照中查找某key对应的value。做法是这样的，从左向右依次扫描，当找到第一个key相同且序号小于等于给定快照序号的节点，将对应value即可返回。在上图的例子中查找”x”，若给定快照序号20将返回2，若给定快照序号11将返回1。上图为了描述简单，忽略了跳跃表中”跳得更远”的指针，实际上高度至少为h节点的比例为4^(-h)。正是利用了这些节点，跳跃表才可以做到和平衡树相当的查找效率。
Codingstory 