“Level”DB

今天终于写到LevelDB最有意思的部分了。我们知道,在经典的merge-dump系统查询数据,运气差时可能需要访问每个SSTable,才能找到需要的数据。虽然BloomFilter在概率上解决了这一问题,但付出的代价却是与key/value对数据成正比的内存使用量(例如每个key/value对占用两三个比特,主要取决于可以容忍的出错概率)。如果将经典的merge-dump系统比喻成链表的话,LevelDB则使用一种类似搜索树的方式精心排列好SSTable,让查询在树的每一层上只命中一个SSTable,从而极大减少磁盘寻道次数。

我们先从SSTable的产生来源开始说。生成SSTable的途径有两种:
1. MemTable内存满,溢写到磁盘
2. 将旧的SSTable”合并”成新的,优化寻道次数

第一种溢写出来的SSTable是在系统内存耗尽时被迫的写出来的,优化余地不大。LevelDB中的优化是作用在第二种途径产生的SSTable上。传统的merge-dump系统只是简单地选择将几个小的SSTable合并为一个大的,由于SSTable内部是类似B树的索引方式(当然是只读的),实际中最多随机寻道两三次,相比原先的几个小的SSTable可以显著减少寻道次数。

但是大文件带来的问题是下次合并时会不灵活:下次合并时,这个大文件要么整体参与合并,要么整体不参与合并,再也不能像几个小文件那样选择其中的几个放弃另外几个了。尽管有如此不灵活,但考虑到合并带来的好处--寻道次数一下从线性级变成了对数级,大家仍然会”义无反顾”地选择合并。

LevelDB走了另一条路:从多个文件”合并”到多个文件。SSTable按顺序地存储了很多key/value对,我们可以记下其中最小和小大的key。最小key和最大key组成一个区间,当在用户查询落在这个区间之外(即用户查询的key比SSTable中最小的key还要小、或者比最大的key还大),那么就自然不必在这个SSTable中继续查找。显然,当这个区间范围越小时,这个SSTable也就不容易被无效命中了。LevelDB正是利用这个特点,让每次”合并”产生区间不重叠的多个输出文件,这样一来这些小文件逻辑上与单个大文件无异,又可以增加灵活性,一举两得。

LevelDB将所有SSTable分为7层(level),下文称为第0层至第6层。MemTable溢写生成的SSTable放在第0层。除第0至外,第1至6层中,每层内的SSTable的最小key和最大key区间是不重叠的。这就保证用户查找到第1至6层的SSTable时每层最多只需读一个SSTable。

如何生成这样的文件布局?让我们回到最开始,只有MemTable溢写出的第0层。随着用户不断写入,第0层的文件越来越多,当超过4个时开始第0层到第1层的合并。类似的,当第1层的数据太多时就合并到第2层,依次类推。衡量某层数据多少的标准是,第0层是否多于4个文件,或者第i层数据总量大于(10^i) MB。每次合并向更高一层输出多个区间不重叠的文件。当进行第i层到第i+1层的合并时,如果第i+1层原先也有一些文件存在,那么在发生区间重叠时需要将这些文件一起合并。

LevelDB中所有SSTable都是固定2MB大小。假如用以覆盖key区间为底、占用空间为面积的矩形表示SSTable,应用以上规则不断整理数据,最终会形成上图中布局:每层的文件数和数据量呈指数增长,越高层的文件越偏向瘦高,即单个文件覆盖更小的key区间。

到这里,想必读者应该已经明白LevelDB名字的由来了。

SSTable

SSTable,从字面上理解是”sorted string table”,即包含排序过的字符串的表。LevelDB的SSTable实际上是存储key/value数据的一种文件。SSTable有以下特点:

  • 数据是按key排好序的,顺序读SSTable可以得到有序的数据,多路归并多个SSTable可以得到全局有顺的数据;
  • 由于所有写操作写好操作日志即可返回成功,将SSTable写入磁盘一个离线的追加写过程;
  • SSTable在写完后就不再修改,最终只会整体的删除。

后两个特点让SSTable特别适合在分布式文件系统上使用。

SSTable的代码在LevelDB中是比较独立的一部分,用户可以跳过数据库直接接口通过TableBuilder/Table类读写SSTable文件。需要注意的是,使用TableBuilder生成SSTable文件时添加的key/value对需要是有序的,这也是LevelDB使用TableBuilder的方式:用户写入数据时先写日志,待内存缓冲区填满后排好序写出SSTable文件。

将数据排好序是为了查找方便。由于SSTable一经写成不再修改,因此索引结构可以做在非常简单的静态结构,无需像数据库那样考虑更新数据时索引维护的问题。在分析内存数据结构和算法时,我们往往关注的是比较次数,因为这直接反应了算法的运行效率。然而在磁盘中查找数据,我们更看重的是读磁盘的次数。从传统的机械硬盘上随机读一块数据,即使只读一个扇区,也要花费至少10毫秒。这个时间称为寻道时间。在这10毫秒时间内,CPU可以进行成千上万次的内存比较操作。因此,无论是采用简单如SSTable的索引,还是是复杂如B树的索引,最终目标都是最小化磁盘寻道次数。

用户写入的key/value对在SSTable中是以一个个block的形式存放的。默认配置的block是4K左右。每个block中存储若干排序后相邻的key和与之对应的value。无论查找block中任何一个key时,都会将一个block完整读出。这是因为寻道时间占整个读磁盘花销的主要部分,读一个扇区和多读几个也区别不大。同时,我们可以整体地将block中的key/value以特别的形式编码(下文详述),以求达到更高的压缩率。此外,由于block中的key是排序后相邻的,在用户的逻辑中也很可能是相关的(例如在有表结构的存储中可能是属于同一行的数据),将block整体做为内存缓存的最小单位也会更有效率。


图1: 数据/索引block在SSTable文件中的位置


图2: 索引结构

索引block和数据block的结构相似,只是value变成了数据block在SSTable文件中的偏移和长度。在查找时(假设未命中缓存),首先从磁盘中读出索引block,然后通过二分查找定位到相应数据block的位置,再从磁盘读出数据block。如此,在一个SSTable中查找一对key/value只需至多两次读盘。当然,一个数据库中往往存储了多个SSTable文件,后续博文将介绍在减少读盘次数上的一些优化。


图3: 采用前缀压缩的block结构,其中”key_000″、”key_010″等是恢复点,”key_001″、”key_002″等采用前缀压缩编码

让我们回头看看block的存储结构。逻辑上一个block可以认为是若干key/value的集合。在实际中为了节省空间,LevelDB采用前缀压缩编码存储key。具体来说,因为同一block中的key是在字典序中相邻的,那么它们就很可能有公共前缀(如上例中的”key_0″、”key_1″等,考虑上层有表结构的存储可能有很长的公共前缀)。在存储key/value对时,我们不需要完整地存储key,而是记录下当前key与上一个key的共同前缀长度和不同部分即可。这样做的负面影响是要匹配到某个key必须顺序遍历先前的所有key。为解决这一问题,在block中并不是所有key都采用这种前缀编码,而是每隔几个key就记录下完整的值。这些key称为恢复点(restart point)。在二分查找时,只需要比较恢复点便可得知大致的范围,再从最接近的恢复点再后遍历即可找到相应的数据。

值得一提的是,在SSTable层面并不处理直接处理序号。在数据库层面,将序号和key一起拼成SSTable层面的key,并指定一个特别的比较器实现多版本的key/value支持(逻辑和MemTable中基本一样:若key相同,序号大的排在前面)。

参考资料:
Table Format

LevelDB的操作日志

LevelDB将用户写入的数据临时存储在MemTable中,内存数据足够多后才排序写入SSTable文件(避免写出过小的文件)。那么如果在写磁盘之前,系统崩溃了怎么办呢?作为数据库系统,最基本的要求就是保证数据持久,即向用户承诺已写成功的数据不会丢失,无论是系统重启还是进程退出。经典的解决方案是在向用户返回写操作成功之前,首先在磁盘上将这个写操作记录在日志文件中。一旦写日志成功,后续操作便可以放心的只在内存中进行了。当数据库因为任何原因重启时,它会首先重播日志文件中的操作记录,保证之前承诺过的操作不会丢失。

写操作分为两种:插入和删除。LevelDB允许用户原子地执行若干插入和删除,或者全部成功或者全部失败。这些写操作放在一起称作write batch,write batch是日志记录中的最小单位。


图1:日志中的一条记录,即一个write batch(格式详见include/write_batch.h和db/write_batch.cc)

每个写操作的格式如下:日志文件是由若干个32KB的定长数据块组成的,每个块头有整个块的校验和。过长的write batch会被拆开保存到几个连续的数据块中。LevelDB的作者在文档中提到了使用定长数据块的好处(doc/log_format.txt),笔者在此简单复述和解释一下 :

  • 若日志文件部分损坏,我们可以直接定位到下一个32KB的数据块,继续读接下来的数据,不至于整个日志文件读不出。
  • 容易对数据进行切分,特别适合用于MapReduce。MapReduce需要在不读出文件内容的情况下对文件按chunk进行切分,典型的chunk长度是64MB,32KB对齐的数据块自然也是64MB对齐的。考虑到过长的write batch会跨chunk边界分布在的连续的块中,这里需要特殊处理一下。
  • 处理大记录时不需要分配额外的缓冲区。这里不太明白,无论在写数据还是从重播日志,都需要将数据复制到MemTable中。(原文:We do not need to put extra buffering for large records)

坏处是这样做会造成空间浪费:

  • 一个32KB定长数据块只存储一个小write batch,比如key/value都只有几字节。
  • 没有压缩。

好在日志文件占空间较小,并且是在SSTable写入磁盘后就会被删除,所以造成的空间浪费并不严重。

保证日志文件正确无误非常十分重要。在系统崩溃或掉电后所有内存数据都会丢失(包括还在系统page cache中的数据),在Linux系统中,只有fsync()成功后的数据才保证写入磁盘不丢失。在响应用户读写请求的流程中,fsync()是一个耗时的操作。在传统机械硬盘和ext3文件系统环境下,开启fsync后顺序写32KB数据每秒仅能完成百次左右,这直接影响数据库的写入性能。

首先不是所有的数据库数据都重要到立即fsync()的程序(比如在桌面应用的本地数据就不值得)。LevelDB为用户提供了一个开关控制每个写操作是否需要进行fsync()。但到目前的版本为止,LevelDB都没有提供周期性触发fsync()的折衷方案(MySQL和MongoDB都可以使用这个方案,典型的触发周期是几百亳秒)。

另一方面,服务器应用中通常写入操作是多线程同时进行的。为了防止写日志在高并发下成为瓶颈,LevelDB将不同线程同时产生的日志数据聚合在一起写入文件并进行一次fsync(),而非对每个线程写的数据进行单独fsync()。这个做法称为group commit。这样一来,虽然每秒完成的fsync()数量无法突破硬件限制,但实际上每次写入的数据量包含更多数据,对用户来说这样也就可以提高写入性能。顺便提一句:这部分代码写得短小精悍,值得学习(db/db_impl.cc中的DBImpl::Write()方法,或见下文)。


图2:线程1正在写日志,线程2和线程3正在等待锁


图3:线程1已完成,线程2和线程3的将日志合并在一起写入文件,只需进行一次write()和fsync()

Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {
  Writer w(&mutex_);
  w.batch = my_batch;
  w.sync = options.sync;
  w.done = false;

  MutexLock l(&mutex_);
  writers_.push_back(&w); // 并发写的线程在这里排队
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  if (w.done) {
    return w.status;
  }

  // 排在队首的线程负责将数据聚合起来写入日志。
  // 只有排在队首的线程会进入这里。其它线程则等待被通知。
  // May temporarily unlock and wait.
  Status status = MakeRoomForWrite(my_batch == NULL);
  uint64_t last_sequence = versions_->LastSequence();
  Writer* last_writer = &w;
  if (status.ok() && my_batch != NULL) {  // NULL batch is for compactions
    WriteBatch* updates = BuildBatchGroup(&last_writer); // 将排在队首的几个batch聚合在一起
    WriteBatchInternal::SetSequence(updates, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(updates);

    // Add to log and apply to memtable.  We can release the lock
    // during this phase since &w is currently responsible for logging
    // and protects against concurrent loggers and concurrent writes
    // into mem_.
    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(updates)); // 写日志
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
      }
      if (status.ok()) {
        status = WriteBatchInternal::InsertInto(updates, mem_); // 写MemTable
      }
      mutex_.Lock();
    }
    if (updates == tmp_batch_) tmp_batch_->Clear();

    versions_->SetLastSequence(last_sequence);
  }

  // 通知这些在等待的线程,我们已经将日志写完了
  while (true) {
    Writer* ready = writers_.front();
    writers_.pop_front();
    if (ready != &w) {
      ready->status = status;
      ready->done = true;
      ready->cv.Signal();
    }
    if (ready == last_writer) break;
  }

  // Notify new head of write queue
  if (!writers_.empty()) {
    writers_.front()->cv.Signal();
  }

  return status;
}

参考资料:
LevelDB官方性能测试报告

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