萌约 MoeYork

一个普通的博客站点

0%

RocksDB 内部结构浅析

发表于 更新于
本文字数： 4.7k 阅读时长 ≈ 8 分钟
简单介绍了RocksDB内部键值的编码和存储过程

本文基于 RocksDB v6.8.1 版本

键值的内部编码

RocksDB 内部将用户提供的键值对 称为 user_key, 并在内部将其编码为 internal_key. 编码过程发生在 MemTable::Add 中, internal_key 的编码过程大致如下:

1
2
3
4
5
6
7
8
uint32_t key_size = static_cast<uint32_t>(key.size());
uint32_t val_size = static_cast<uint32_t>(value.size());
uint32_t internal_key_size = key_size + 8;

uint64_t packed = PackSequenceAndType(SequenceNumber s, ValueType type);

// internal_key 结构示意
Varint32(internal_key_size) + key + Fixed64(packed) + Varint32(val_size) + value;

其将序列号(SequenceNumber s)和键值类型(ValueType type) 编码为一个8字节整数, 并添加到 internal_key 内部.

因此 internal_key 的整体排布如下:

1
2
|user_key|timestamp|seqno|type|
|<-------internal_key-------->|

Memtable 提供的比较器 Memtable::KeyComparator comparator_ 在进行比较时, 只使用 InternalKeyComparator comparator 比较 key + Fixed64(packed) 这部分, 其中 key 部分 InternalKeyComparator 使用 用户指定的 Comparator user_comparator_ 进行比较.

值得注意的是 RocksDB 支持 User-defined-Timestamp 功能, 这个功能允许用户为键值对插入一个可指定长度的时间戳, 并可指定一个 Timestamp-aware 的 Comparator. 时间戳部分在进入 MemTable::Add 时是已经编码在 key 中的尾部的, 其比较过程直接由 Comparator::Compare 处理.

键值的内部类型

键值类型 ValueType 定义在 db/dbformat.h 中, 其主要类型如下:

1
2
3
4
5
6
7
8
9
10
11
12
enum ValueType : unsigned char {
    kTypeDeletion = 0x0,
    kTypeValue = 0x1,
    kTypeMerge = 0x2,
    ...
    kTypeSingleDeletion = 0x7,
    ...
    kTypeRangeDeletion = 0xF,  // meta block
    ...
    kTypeBlobIndex = 0x11,     // Blob DB only
    ...
};

其中kTypeDeletion, kTypeValue, kTypeMerge, kTypeBlobIndex 及 kTypeSingleDeletion 为 “值类型”

1
2
3
4
5
// Checks whether a type is an inline value type
// (i.e. a type used in memtable skiplist and sst file datablock).
inline bool IsValueType(ValueType t) {
  return t <= kTypeMerge || t == kTypeSingleDeletion || t == kTypeBlobIndex;
}

具体实现中, RocksDB 将 ValueType 的数据与 kTypeRangeDeletion 的数据分开存储, 这些类型被合称为 “扩展值类型”

1
2
3
4
5
// Checks whether a type is from user operation
// kTypeRangeDeletion is in meta block so this API is separated from above
inline bool IsExtendedValueType(ValueType t) {
  return IsValueType(t) || t == kTypeRangeDeletion;
}

kTypeMerge, kTypeSingleDeletion 及 kTypeRangeDeletion 类型分别对应 RocksDB 提供的 Merge 和 Single-Delete 以及 DeleteRange 操作, 此处不再赘述.

键值的存储过程

WAL

这部分还没仔细看, 鸽了.

MemTable

键值对通过 MemTable::Add 添加到 Memtable 中, 在编码为 internal_key 后, Memtable 根据值的类型对其进行存储.

Memtable 默认的存储结构为跳表(SkipListRep : MemTableRep), RocksDB 支持的所有存储结构均继承了 MemTableRep (memtable representation). 完整的 MemTableRep 需实现内存分配(Allocate), 插入(Insert), 读取(Get) 以及 迭代器(GetIterator) 等操作, Memtable 通过这些操作来实现最终的键值插入和查找功能.

在 MemTable::Add 中, 值类型(IsValueType() == true) 放置在 MemTableRep table_ 中, kTypeRangeDeletion 类型放置在 MemTableRep range_del_table_ 中. 值得注意的一点是 range_del_table_ 总是 SkipListRep.

在满足条件后, DBImpl::SwitchMemtable 将被调用, 将 Memtable 变为 Immutable memtable. 具体过程就是通过 MemTableList::Add 将 Memtable 放入 MemTableList cfd->imm(), 在 MemTableList::Add 中还会调用 Memtable::MarkImmutable 通知 Memtable.

Flush & Compaction

Flush 过程主要在 FlushJob::WriteLevel0Table 中, 笔者认为其与 Compaction 过程的最大不同只是其构建 SST 的数据来源不同.

在 Flush 过程中, 所有待 Flush 的 Memtable 的迭代器((Memtable m)->NewIterator) 将通过 NewMergingIterator 被组合为一个 ScopedArenaIterator; 并和所有的 (Memtable m)->NewRangeTombstoneIterator 一起传递给 BuildTable, 进行最终的 SST 创建过程.

Compaction 过程主要在 CompactionJob::ProcessKeyValueCompaction 中.

SST 构建

BlockBasedTable 是 RocksDB 默认的 SST 实现. 它由 Block 和 Footer 组成, 其文件布局如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]
[meta block 2: index block]
[meta block 3: compression dictionary block]
[meta block 4: range deletion block]
[meta block 5: stats block]
...
[meta block K: future extended block]
[metaindex block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

其中 [Footer] 中存放了 metaindex block 和 index block 的 BlockHandle; [metaindex block] 则按 (块名称, BlockHandle) 存储了 元信息块 (meta block) 的偏移, 例如 range deletion block 的 key 为 std::string kRangeDelBlock = "rocksdb.range_del";

[Footer] 内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
legacy footer format:
    metaindex handle
    index handle
    <padding> 
        // make the total size 2 * BlockHandle::kMaxEncodedLength
    table_magic_number (8 bytes)
new footer format:
    checksum type (char, 1 byte)
    metaindex handle
    index handle
    <padding>
        // make the total size 2 * BlockHandle::kMaxEncodedLength + 1
    footer version (4 bytes)
    table_magic_number (8 bytes)

BlockHandles 用于描述块的偏移量和大小

1
2
offset:         varint64
size:           varint64

值得注意的是每个 Block (除 [Footer] 外的所以类型的均相同), 都设计为用于存储键值数据, 其大概结构如下:

1
2
3
4
5
6
7
8
9
10
11
<完整KV 1>
<去除相同前缀KV 2>
<去除相同前缀KV 3>
...
<完整KV k>
<去除相同前缀KV k+1>
...
<重启点 1>
<重启点 2>
...
<IndexTypeAndNumRestarts> // block footer

其中 <IndexTypeAndNumRestarts> 通过 PackIndexTypeAndNumRestarts 编码, 记录了索引类型及重启点个数.

Block 通过 BlockBuilder 进行创建, 通过 BlockBuilder::Add 方法可写入一个键值对; 在写入完成后通过 BlockBuilder::Finish 写入重启点信息和 block footer 完成单个块的构建过程.

在存储和读取时, SST 会以 Block 为单位进行读取和写入. 创建 SST 时, 在使用 BlockBasedTableBuilder::Add 按顺加入全部键值对后, 调用 BlockBasedTableBuilder::Finish 将 按文件布局顺序写入各元信息块和[Footer], 完成整个 SST 的构建过程.

写入顺序:

1
2
3
4
5
6
7
8
9
1. [meta block: filter]
2. [meta block: index]
     index_blocks.meta_blocks ( <-- metaindex_block )
     index_blocks.index_block_contents ( <-- Footer )
3. [meta block: compression dictionary]
4. [meta block: range deletion tombstone]
5. [meta block: properties]
6. [metaindex block]
7. [Footer]