“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名字的由来了。

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