LevelDB的高并发MemTable实现

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)。正是利用了这些节点,跳跃表才可以做到和平衡树相当的查找效率。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s