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

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