Rocksdb KV分离存储实践

原创 董道光 喜马拉雅技术博客 2020年09月18日 19:45

Rocksdb 简介

在介绍 Rocksdb 之前，我们不得不先提一下 Leveldb。Leveldb 是由 google 的传奇工程师 Jeff Dean 开发的一款持久化存储的 KV 数据库。与 Redis 这种内存型的 KV 系统不同，Leveldb 不会像 Redis 一样狂吃内存，而是将大部分数据存储到磁盘上。而 Rocksdb 就是基于 Leveldb 代码做的开发，它是由 Facebook 开源维护的，但是做了很多优化工作，如多线程compact，锁优化，迭代器优化等。性能较于 Leveldb 有了很大的提升，现在很多厂商都是用 Rocksdb 作为底层的核心存储引擎。如类 Redis 数据库 Pika、图数据库 Arangodb、NewSQL数据库 Tidb 等。
 

既然有如此多的大厂商都青睐 Rocksdb，也就说明 Rocksdb 的性能应该还是很不错的。当然，强悍的性能肯定离不开好的架构，下面我们就来了解一下 Rocksdb 存储引擎的架构设计。

我们先看一下常见的存储引擎架构都有哪些：

• Hash 存储引擎：支持快速增删改查等随机操作，且时间复杂度为 O(1)，但是不支持顺序读取扫描。代表性的数据库有：Redis，Memcache
• B 树存储引擎：相比哈希存储引擎，B 树存储引擎不仅支持随机读取，还支持范围扫描。代表性的数据库有：MySQL
• LSM-tree 存储引擎：LSM-tree 存储引擎和 B 树存储引擎，一样支持增删改查，也支持顺序扫描操作。LSM-tree 牺牲了读性能，提高写性能。代表性的数据库有：Leveldb，Rocksdb

Hash 和 B 树存储引擎本文暂时不做讨论，我们主要来深入了解一下 LSM-tree 存储引擎，因为 Rocksdb 底层就是用的 LSM-tree 存储引擎。

LSM-tree 详解

LSM-tree（Log-Structured Merge-Tree）全称日志结构合并树。其原理是把一棵大树拆分成 N 棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会 flush 到磁盘中，磁盘中树定期可以做 merge 操作，合并成一棵大树。
 

需要注意的是，对 LSM-tree 的任何操作都是以 append-only 的方式写入，比如删除一个 key，它不会立马删除这个 key，而是添加一条对这个 key 的操作记录，操作的类型是 delete，后续通过 compat 机制，删除垃圾数据。

LSM-tree 只是一种设计思想，但真正实现起来可以有很多种方式，下面我们就看一下 Rocksdb 的存储引擎是如何基于 LSM-tree 实现的。

基于 LSM-tree 的 Rocksdb 存储引擎

首先，先来看一下 Rocksdb 存储引擎的整体架构
 

关键组件及流程说明：

• MemTable：Rocksdb 写数据先写到 Memtable 中，MemTable 存储在内存中，一般采用 skiplist 实现。
• Immutable Memtable：只读 Memtable，当 Memtable 达到一定大小后，变为只读，等待数据刷到磁盘上。
• SST：数据落盘后的文件。
• WAL：持久化 Memtable 中的数据，防止故障后 Memtable 数据丢失。
• Flush：将内存中的数据刷到磁盘上。
• Compact：文件合并，删除垃圾数据。

Rocksdb 存储引擎的优缺点

优点

写入速度快，原因主要有以下两点：

1. 数据直接写内存，通过异步线程定期将内存中的数据flush到磁盘上。
2. 将随机写转化为顺序写，在传统的机械盘上顺序写的性能远远高于随机写性能，这个性能差异接近1000倍。

缺点

1. 读放大：读操作需要从新到旧（从上到下）一层一层查找，直到找到想要的数据。这个过程可能需要不止一次 I/O。特别是范围查询的情况，影响很明显。
2. 空间放大：所有的写入都是以追加的方式（append-only）顺序写入的，不是原地更新 ，所以过期数据不会马上被清理掉。

对于读放大和空间放大问题，我们可以通过 Rocksdb 的 compact 机制来解决，因为 compact 可以删除垃圾数据，这就降低了空间放大问题。并且由于垃圾数据的降低，读命令就会减少对垃圾数据的遍历，也降低的读放大问题。

但是 compact 机制本身还存在一个比较严重的问题，就是写放大的问题，下面我们就聊聊什么是写放大。

Rocksdb 写放大问题

SST 文件格式

首先我们先看一下 Rocksdb 的 SST 文件存储格式。
 

Rocksdb 将 SST 文件划分为多个 Block：

• Data Block 存放 Key-Value 数据的 Block
• Meta Block 各个元信息的 Block，包括 Filter、Properties(整个table的属性信息)、Compression dictionary、Range deletion tombstone
• MetaIndex Block 指向各个元信息 Meta Block 的索引指针
• Index Block 每个 Data Block
• Footer 包括指向 MetaIndex 和 Index Block的索引指针

从 SST 文件的存储格式中，我们需要关注的一点就是在 Data Block 中 key 和 value 是存在一起的。

compact 原理

Rocksdb 在磁盘上的文件是分为多层的，除了 level 0 层， 每层的文件的 key 默认都是按字典序，有序存储。

每层文件之间不会出现 key 重叠，但层与层之间会出现 key 重叠。

从上到下，每层容量逐渐增大，比如 level 1 层容量是100M，那么 level 2 层的容量就是 1000M，10 倍递增。

如上图，当 level 1 层达到容量上限后，会在该层挑选一个 SST 文件，假设为 SST1。然后再在 level 2 层挑选 key 范围和 SST1 有重叠的所有 SST 文件做 compact。最后将新生成的文件写入到 level 2 层。然后依次向下层 compact。

结合 SST 文件的存储格式，我们不难看出 compact 过程中会产生很多无效的读写 IO。因为我们在 compact 的过程中，只要保证 key 的有序就可以了，根本不需要将 value 读出来，再反复写文件。并且在实际应用中，key 一般都比较小，而 value 比较大，如果 key 有 10 个字节，而 value 有 1kB，那么就会产生 100 倍的无效 IO。

那么针对这个问题，有没有比较好的解决方案呢？下面我们就聊一聊 Rocksdb 的 KV 分离存储解决方案。

KV 分离存储方案实践

什么是 KV 分离存储

这个要从一篇论文说起 —— 《WiscKey》。

我们知道 Rocksdb 中，key 和 value 是存在一起的，该论文提出了一种优化思路：在 LSM-tree 上做 key 和 value 分离存储。如下图：
 

该论文的思想比较好理解，就是将 key 和 value 对应的索引存 LSM-tree 中，将真正的 value 存在另一个文件中。

KV 分离的好处

1. compact 不需要重写 value，大大减少了无效 IO。
2. LSM-Tree 不存储 value，体积更小，一个 STT 文件能存更多的 key，有利于减少读 LSM-Tree 的 I/O。
3. LSM-Tree 的体积小，操作系统的文件缓存效果会更好。LSM-Tree 基本都可以 cache 在内存中。

KV 分离后存在的问题

1. 当 value 较小时，重写 value 这部分的开销就比较小，KV 分离存储带来的好处就不足以抵消它带来开销。
2. 如何对删除 value 中的垃圾数据
   
   针对上述问题，下面就来看看，我们是如何在 Rocksdb 上实现 KV 分离存储。

KV 分离存储方案设计

我们将 key 和 value 对应的索引还是存储在 SST 文件中，将真正的 value 存储在 blob 文件中。

key 和 value 分离的时机是在内存数据 flush 到磁盘的时候。

当 value 小于分离阈值时，将 key 和 value 都存储在 SST 文件中；

当 value 大于分离阈值时，将 key 和 value 索引存储在 SST 文件中，value 存储在 blob 文件中。

如何删除 blob 文件中的垃圾数据

我们知道 compact 会删除 SST 文件中的垃圾数据，但并不会删除 blob 中真正的 value，那我们如何删除 blob 文件中的垃圾数据呢，这就要引入 blob 文件的 GC 机制。blob 文件的 GC 要解决两个问题：

1. 何时进行 GC
2. 挑选哪些文件进行 GC

首先看第一个问题，何时 GC ？
RocksDB是通过Compact来丢弃旧版本数据以回收空间的，因此每次Compact完成后，某些Blob文件中便可能有部分或全部数据过期，因此可以在每次Compact结束后进行GC。

挑选哪些文件进行GC？
垃圾数据最多的文件进行GC。

那么问题又来了，如何判断文件的垃圾数据大小？

RocksDB 允许用户使用自定义的TablePropertiesCollector（文件信息搜集器）来搜集 SST 文件上的用户所关心的数据。我们可以通过这个特性来搜集 SST 文件上的 Blob 文件信息。如下图：
 

左边 SST 中 Index 的格式为：

第一列代表 BlobFile 的文件 ID，第二列代表 blob record 在 BlobFile 中的 offset，第三列代表 blob record 的 size。

右边 BlobFileSizeProperties 中的每一行代表一个 BlobFile 以及 SST 中有多少数据保存在这个 BlobFile 中，第一列代表 BlobFile 的文件 ID，第二列代表数据大小。

每次 compact 都会记录输入文件和输出文件
 

inputs 代表参与 Compaction 的所有 SST 的 BlobFileSizeProperties，
outputs 代表 Compaction 生成的所有 SST 的 BlobFileSizeProperties，
discardable size 是通过计算 inputs 和 outputs 得出的每个 BlobFile 被丢弃的数据大小，第一列代表 BlobFile 的文件 ID，第二列代表被丢弃的数据大小。

这样，我们就可以计算出每个 blob 文件的垃圾数据大小，然后排序，优先 GC 垃圾数据最多的 blob 文件。

KV 分离存储除了 GC 的问题，还有很多问题需要解决，如 blob 文件的多版本并发访问、服务重启后如何重新计算 blob 文件的垃圾数据量等，由于篇幅限制，在这里就不展开了。

未来优化工作

• GC 速度自动调节
• Blob 文件存储优化

结语

目前 KV 分离存储方案已经应用到了喜马拉雅的 XCache 存储系统中，大大降低了大 value 场景下的延时问题。XCache 是由喜马拉雅系统架构团队基于开源项目 Codis、Pika、Redis 深度定制开发的一套分布式 KV 持久化存储系统，目前已经开源。
XCache github地址：https://github.com/XimalayaCloud/xcache，欢迎大家使用，并提出宝贵建议

参考资料

• https://github.com/facebook/rocksdb/wiki
• https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf