RocksDB笔记 -- 整体架构

RocksDB是由Facebook开发的存储引擎, 它最初的目标是用于快速存储, 特别是Flash存储. 一个基于C++开发keys-values存储引擎库.

整体架构

RocksDB由这三个基本结构组成: memtable, sstfile 和 logfile. 其中:

1. memtable是一个内存数据结构, 新的写入会插入到memtable中, 同时可选择性地写入到logfile中.
2. logfile是一种顺序写入文件(sequentially-written).
3. 当所有的memtable都被写满后, memtable里面的数据将会转存储到一个sstfile文件中.并且相关的logfile将会安全删除. (将内存数据安全存储到文件上)
4. 在sstfile中的数据将会通过排序方式存储以方便相关键值.

MemTable

默认memtable是基于跳表实现的.
新的写入会插入数据到memtable, 一旦memtable被写满将会变为immutable并且被新的memtable替换. 之后会将该memetable的内容刷新(flush)到一个SSTfile文件中, 当内容都刷新到SSTfile后该memtable将会被销毁(destroyed).

一些影响memtable的选项(opions):

1. AdvancedColumnFamilyOptions::memtable_factory: memtable的工厂对象. 通过特殊化工厂对象能够改变memtable的实现, 并且提供实现特殊化的选项(specific options) [默认: SkipListFactory]
2. ColumnFamilyOptions::write_buffer_size: 单个memtable的大小(默认: 64MB)
3. DBOptions::db_write_buffer_size: 将整个memtables写入列组. 通过memtables管理整个内存空间(默认: 0 (Disabled).
4. DBOptions::write_buffer_manager: 用户可以提供他们自己的写入缓存管理俩控制整个memtable的内存使用情况. 覆盖db_write_buffer_size操作. (默认: nullptr)
5. AdvancedColumnFamilyOptions::max_write_buffer_number: 在memtables刷新到SST files之前, 在内存中设置memtables的最大数量. (默认: 2)
6. AdvancedColumnFamilyOptions::max_write_buffer_size_to_maintain: 以字节形式在内存中存储写入历史的总数. 包括: 当前memtable的大小, 密封但未刷新的memtables 以及 保留刷新过的memtables. Tips: RocksDB will try to keep at least this much history in memory - if dropping a flushed memtable would result in history falling below this threshold, it would not be dropped. (默认: 0)

Skiplist MemTable

基于跳表的memtable一般能够拥有兼具读写, 随机访问以及顺序扫描的较好性能. 
Tips: it provides some other useful features that other memtable implementations don’t currently support, like Concurrent Insert and  Insert with Hint.

HashSkiplist MemTable

哈希跳表以哈希表的形式组织数据, 另外每个哈希桶都是一个跳表. 另外这每个哈希桶作为排序过的单链表 (为了减少查询时的比较次数). 还有一种好的使用方法是结合上述数据结构并且通过使用PlainTable SST格式以及在RAMFS存储数据的方式.

当要查询或者插入某个键时, 使用目标键的前缀选项检索. prefix_extractor常常被用来查找哈希桶. 在哈希桶中, 所有比较都是用键来完成的.

然而, 这种基于哈希的memtables在扫描多个需要复制和排序的前缀时会比较慢并且消耗更多内存.

Flush

以下情况会在memtable刷新时被触发:

1. 在写入后, memtable的大小超过了ColumnFamilyOptions::write_buffer_size设置的大小
2. 所有通过整个列组的memtable大小超过了DBOtptions::db_write_buffer_size设置的大小  或者 DBOptions::write_buffer_manager 发起一个刷新信号. 这两种情况下最大的memtable将会被刷新.
3. 整个WAL文件的大小超过了DBOptions::max_total_wal_size设置的大小. 这种情况下, 保存最久数据的memtable会被刷新, 这是为了能够清除来自这些memtable的WAL 文件数据.

以上情况会在memtable没写满之前执行刷新. 之所以要这样做是因为生成的SST文件一般要比相关的memtable小. 另外就是压缩问题, 在memtable中的数据是未经压缩的数据, 这也是为什么memtable要比SST文件大的原因.

SST File

这个文件的格式是基于块表的(BlockBasedTable)
格式如下所示:

<beginning_of_file>
[data block 1]
[data block 2]
…
[data block N]
[meta block 1: filter block]                  (see section: “filter” Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block]  (see section: “compression dictionary” Meta Block)
[meta block 4: range deletion block]          (see section: “range deletion” Meta Block)
[meta block 5: stats block]                   (see section: “properties” Meta Block)
…
[meta block K: future extended block]  (we may add more meta blocks in the future)
[metaindex block]
[Footer]                               (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

该文件包含一个名叫BlockHandles的内部指针, 它的结构如下所示:

offset:         varint64
size:           varint64

关于SST file的更多细节我会专门写一篇博客说明, 关于它的内容今天就简要说明一下. 
 

参考:

RocksDB Overview · facebook/rocksdb Wiki · GitHub
MemTable · facebook/rocksdb Wiki · GitHub
Rocksdb BlockBasedTable Format · facebook/rocksdb Wiki · GitHub