RocksDB 架构

RocksDB 是 Facebook 针对高性能磁盘开发开源的嵌入式持久化存储系统，采用了 WAL 机制和 LSM Tree 结构。RocksDB 所有类型的数据都是采用追加写，没有更新文件的操作。比较适合使用基于 Append Only 的高性能分布式文件系统。

1、RocksDB 摘要

1.1、RocksDB 特点

• 基于 LevelDB
• 嵌入式 KV 存储引擎
• 针对写密集型场景而提出的解决方案。例：日志系统、海量数据存储、海量数据分析
• 紧凑型存储。相同的数据量，更少的空间占用。
• 基于 LSM-Tree 的存储结构。

• 内存：MemTable
• 磁盘：SST | WAL

1.2、基本接口

• Open
• Get：获取 key
• Put：存放 key
• Delete：删除 key，具体在 compaction 中删除
• SingleDelete：针对从未修改过的 key，比 delete 删除快
• Merge：合并新写入的数据。带来大量的读数据请求，提前获取 Merge 的增量数据，然后进行合并。
• Iterator：通过给定的 key 批量获取符合条件的 KV 记录。

1.3、编译

# 1、RocksDB
 git clone https://github.com/facebook/rocksdb.git
 cd rocksdb
 # 编译成调试模式
 make
 # 编译成发布模式
 make static_lib 
 # 压缩库 Ubuntu
 # gflags
 sudo apt-get install libgflags-dev
 # snappy
 sudo apt-get install libsnappy-dev
 # zlib
 sudo apt-get install zlib1g-dev
 # bzip2
 sudo apt-get install libbz2-dev
 # lz4
 sudo apt-get install liblz4-dev
 # zstandard
 sudo apt-get install libzstd-dev

2、LSM - Tree

RocksDB 架构基于 LSM-Tree, log structured merge tree存储结构，其核心就是利用顺序写来提升写性能。

LSM-Tree 组成

• 内存：可写的 MemTable + 只读的 Immutable Memtable
• 磁盘：WAL + 多层级 SST

LSM-Tree VS B+ Tree

读写性能上

• LSM-Tree：顺序写，追加更新，LSM-Tree 写性能更好。由于采用 append 的方式，会造成数据冗余，需要后台线程做 compaction 操作。在读取数据时，可能需要同时遍历 memtable 和 SST，读性能较差。
• B+ Tree：随机写，就地更新，B+ Tree 的读性能更好。由于磁盘随机 IO 的速度小于磁盘顺序 IO 的速度，且 DML 操作时需要对整个 B+ 树加锁，锁粒度大，因此写性能较差。

在存储空间上

• LSM-Tree：紧凑存储，占用空间少， 高压缩比， SST 每一层级的空间浪费控制在 10%
• B+ Tree：B+ 树分裂时，造成 50% 空间浪费，存在页内碎片

接下来，从整体上先介绍 RocksDB 架构图，如图所示：

用户的数据需要同时写到内存中的 Memtable 数据结构和磁盘 WAL 日志。可写的 Memtable 用于快速索引查询的缓存数据，并采用了跳表数据提升查找数据的速度。当 Memtable 的大小达到阈值后变成只读的 Immutable Memtable。当 Immutable Memtable 的数量达到阈值后，刷盘到 L0 SST 文件中（flush 磁盘操作）。在此期间，若出现服务故障，重启系统会从 WAL 中将数据通过 Redo 的方式恢复到 Memtable。

为了定期 compact （合并压缩）数据，将 Immutable Memtable 分为多个层次。Level 0 层允许数据重复，文件间无序，文件内部有序；Level 1 ~ Level N 没有数据重复，跨层可能有重复，文件间是有序的。数据逐层愈冷，压缩程度愈高。SST 文件为每一层的主要存储方式。在 L0 文件个数达到阈值后，合并到 L1 上并依次往下刷。RocksDB 中可以配置多个线程用于对每层数据文件进行 compaction。

读取数据时，先读内存 Memtable；若不存在，则基于 SST 文件元数据查找是否缓存在 Block Cache 中；若没有被缓存，则读磁盘的 SST 文件，找到后并加载到 Block Cache 中。

参考论文：Chen G J, Wiener J L, Lyer S, et al. Realtime data processing at facebook[C]. Proceedings of the 2016 International Conference on Management of Data. 2016: 1087-1098.

2.1、Memtable

Memtable 内存数据结构，其中的数据总是最新的。同时服务于读和写，写操作先插入 Memtable。读数据先查询 Memtable。当 Memtable 写满，修改为只读的 Immutable Memtable，并被新的 Memtable 替换。后台线程会该 Immutable Memtable 异步落盘（flush）到一个 SST 文件，落盘后销毁 Memtable。

Memtable 基于跳表实现。跳表是多层级有序链表，其特点是：

• 从最高层次开始跳跃查找，并记录跳跃路径，查询时间O(logn)
• 找到待插入位置后，插入节点，并随机层高
• 根据跳跃路径，构建层级链表关系

跳表应用场景

• 范围查询
• 快速有序地列出所有的节点
• 并发粒度非常低。相较红黑树加锁整棵树，只将相邻的结点操作加锁

重要参数

#  一个 memtable 的大小
 write_buffer_size
 # 管理 memtable 使用的总内存数
 db_write_buffer_size
 # 刷盘到 SST 文件的最大 memtable 数
 max_write_buffer_number

其他常见的层级数据结构

• 跳表：多层级有序链表
• B+ 树：叶子节点包含所有的数据，非叶子节点只包含索引 key 信息
• 时间轮：按照定时任务到期时间轻重缓急进行分层

2.2、WAL

WAL, Write Ahead Log。RocksDB 中的 DML 操作同时写入内存 Memtable 和磁盘 WAL 日志文件。当系统崩溃时，WAL 日志可以完整恢复 Memtable 中的数据，以保 WAL中的数据通过 redo 的方式恢复到 Memtable。

重要参数

# WAL 文件的最大大小
 DBOptions::max_total_wal_size
 # WAL 文件的删除时间
 DBOptions::WAL_ttl_seconds

2.3、SST

SST, Sorted String Table，有序键值对集合，是 LSM - Tree 在磁盘中的数据结构。与 B+ Tree 就地更新不同（找到元数据所在页并修改值），LSM-Tree 直接 append 写到磁盘，再同通过合并的方式取出冗余数据。

为了加快 key 的查询速度

• 建立索引
• 布隆过滤器（Bloom Filter）：判断某个字符串一定不在该集合，若该字符串存在，可能有误差。

• 原理：位图 + N 个哈希算法。key 经过 N 个哈希后，若对应的位图是 0，则 key 不存在
• 场景限制：不支持删除 key，而 SST 本身不会被修改，所以可以使用。

SST 文件格式

• Footer：程序启动位置，存储 IndexBlock 和 MetaIndexBlock 的位置
• IndexBlock：存储 DataBlock 的位置
• MetaIndexBlock：存储了过滤元数据、属性信息、压缩字典索引的位置
• DataBlock：存储有序的数据记录

引用论文：Cho M, Choi W, Park S H. A Study on WAF reduction and SST file size on RocksDB[C]. Proceedings of the Korea Information Processing Society Conference. Korea Information Processing Society, 2017: 709-712

2.4、BlockCache

背景：内核 page cache 不可定制。因此，用户可以在内存中指定 RocksDB 缓存块，传一个 Cache 对象给 RocksDB 实例。一个缓存对象可以在同一个进程的多个 RocksDB 实例之间共享。块缓存存储未压缩过的块，也可以设置块缓存去存储压缩后的块。

RocksDB 两种类型的缓存都通过分片来减轻锁冲突，容量被平均分配到每个分片，分片间不共享空间。默认情况下，每个缓存会被分成 64 个分片，每个分片至少 512 B。

默认情况下，索引和过滤块都在 BlockCache 外面存储，用户可以选择将它们缓存在 BlockCache 中；

• LRUCache：基于 LRU 算法，lru 列表 + 哈希表。
• ClockCache：基于 Clock 算法，clock 指针 + 环形列表 + 哈希表。

与 LRU 缓存比较，Clock 缓存有更好的锁粒度。LRU 缓存读取数据时，需要对所有分片加互斥锁，因为需要更新的 LRU 列表；而在 Clock 缓存上读取数据时，不需要申请该分片的互斥锁，只需要搜索并行的哈希表。只有在插入的时候需要每个分片的锁，锁粒度更小。因此，一定环境下，Clock 缓存性能更好。

3、读写流程

3.1、读取流程

• 先读内存 memtable
• 若不存在，读磁盘 SST

SST 查找流程

• FindFiles。从 SST 文件中查找，如果在 L0，那么每个文件都得读，因为 L0 不保证 key 不重叠；如果在更深的层，key 保证不重叠，每层只需要读一个 SST 文件即可。L1 开始，每层可以在内存中维护一个 SST 的有序区间索引，在索引上二分查找即可。
• LoadIB + FB。IB, index block是 SST block 的索引；FB, filter block 是一个布隆过滤器，可以快速排除 key 不在的情况，因此优先加载。
• SearchIB。二分查找 index block，找到对应的 block
• SearchFB。用布隆过滤器过滤，如果没有，则返回；
• LoadDB。加载 block 到内存；
• SearchDB。block 中继续二分查找；
• ReadValue。找到 key 后读数据。若考虑 WiscKey KV 分离的情况，还需要去 vLog 中读取

3.2、写入流程

• 写入磁盘 WAL 文件
• 写入内存 memtable
• memtable 大小达到阈值后，冻结成 immutable memtable。后续的写入交给新的 memtable 和 WAL
• 后台 compaction 线程，将 immutable memtable 落盘成 level 0 的 SST，持久化后释放对应的 WAL
• 若插入新的 SST 后，当前层 Li 的总文件大小超出阈值，会从 level i 挑出一个文件和 level i + 1 层的重叠文件合并，直到所有层的大小都小于阈值。合并过程中，保证 level 1 以后各 SST 的 key 不重叠

4、LSM-Tree 放大问题

4.1、放大问题

• 读放大：描述物理读取的字节数相较于返回的字节数之比。RocksDB 读取操作需要分层依次查找，直到找到对应数据，该过程可能涉及多次 IO
• 写放大：描述磁盘上存储的数据字节数相较于数据库包含的逻辑字节数之比。所有的写入操作都是顺序写，而不是就地更新，无效数据不会马上被清理掉。
• 空间放大：描述实际写入磁盘的数据大小和程序要求写入的数据大小之比。为了减小读放大和空间放大，RocksDB 采用后台线程合并数据的方式来解决，但会造成对同一条数据多次写入磁盘

4.2、compaction

rocksdb 默认采用 leveled compaction（leveled & tiered）合并算法。compaction 操作会造成写放大，但会减少读放大，空间放大。

除 L0 外，其他层级不会出现重复数据。

• leveled：每一层只有一个文件，且每一层文件大小是上一层的 10 倍
• tiered：将文件分成拆分成大小相同的部分

将相邻层的重复数据进行合并。同时，也可以并行 compaction