8.1.1 不一样的kv存储RocksDB的使用场景

简介

RocksDB 是 Facebook 的一个实验项目，目的是希望能开发一 套能在服务器压力下，真正发挥高速存储硬件性能的高效数据 库系统。这是一个 C++ 库，允许存储任意长度二进制 KV 数据。支持原子读写操作。

RocksDB 依靠大量灵活的配置，使之能针对不同的生产环境进 行调优，包括直接使用内存，使用 Flash，使用硬盘或者 HDFS。支持使用不同的压缩算法，并且有一套完整的工具供生 产和调试使用。

RocksDB 大量复用了 levedb 的代码，并且还借鉴了许多 HBase 的设计理念。原始代码从 leveldb 1.5 上fork 出来。同时 RocksDB 也借用了一些 Facebook 之前就有的理念和代码。

RocksDB 应用场景非常广泛；比如支持 redis 协议的 pika 数据 库，采用 RocksDB 持久化 Redis 支持的数据结构；MySQL 中 支持可插拔的存储引擎，Facebook 维护的 MySQL 分支中支持 RocksDB；

基本接口

Status Open(const Options& options, const std::string& dbname, DB** dbptr); 

Status Get(const ReadOptions& options, const Slice& key, std::string* value); 
Status Get(const ReadOptions& options, ColumnFamilyHandle* column_family, const Slice& key, std::string* value); 

Status Put(const WriteOptions& options, const Slice& key, const Slice& value); 
Status Put(const WriteOptions& options, ColumnFamilyHandle* column_family, const Slice& key, const Slice& value); 

// fix read-modify-write 将 读取、修改、写入封装到一个 接口中
Status Merge(const WriteOptions& options, const Slice& key, const Slice& value); 
Status Merge(const WriteOptions& options, ColumnFamilyHandle* column_family, const Slice& key, const Slice& value);

// 标记删除，具体在 compaction 中删除
Status Delete(const WriteOptions& options, const Slice& key); 
Status Delete(const WriteOptions& options, ColumnFamilyHandle* column_family, const Slice& key, const Slice& ts);

// 针对从来不修改且已经存在的key; 这种情况比 delete 删除 的快; 
Status SingleDelete(const WriteOptions& options, const Slice& key);
Status SingleDelete(const WriteOptions& options,  ColumnFamilyHandle* column_family,  const Slice& key);

// 迭代器会阻止 compaction 清除数据，使用完后需要释放;
Iterator* NewIterator(const ReadOptions& options);
Iterator* NewIterator(const ReadOptions& options, ColumnFamilyHandle* column_family)

LSM-Tree

LSM-Tree 的核心思想是利用顺序写来提升写性能；LSM-Tree 不是一种树状数据结构，仅仅是一种存储结构；LSM-Tree 是为 了写密集型的特定场景而提出的解决方案；如日志系统、海量 数据存储、数据分析；

LO 层数据重复，文件间无序，文件内部有序；

L1 ~ LN 每层数据没有重复，跨层可能有重复；文件间是有序 的；

先写磁盘，WAL追加式 redis中的 aof、mysql中的redolog相当于WAL。 N最大就是7层

追加更新不会去找key所在的位置，直接从memtable开始，不管下面如sstable存在相同的key，这样直接更新导致出现冗余存储的情况。

首先写到WAL，为了未来确保写内存的操作是一个安全的操作，未来如果进程机，内存数据丢失，可以根据WAL去恢复内存数据。Memable是有阈值的，大小是有限定的，超过一定大小后会转变成一个只读的跳表结构Immutable Memtable ，转变的同时也会生成一个空的跳表结构 ，接下来写的操作都会在这个新的跳表table，原来的已经变成了只读的table。接下来， Immutable Memtable的数据会异步的刷到SStable，此时，原来的WAL这个文件可以删除了，重复以上操作，在level0可能会出现重复的key，在level1~levelN不允许出现重复的key了，但可以和level0有一个重复的key。这样可能会出大量的冗余数据， 处理方法就是Compact合并压缩：从level0开始，将level0冲的key进行一个和并，会选中level1的文件与level0中的文件进行合并，把里面重复的数据做成一份然后写入到level1新的文件里面，当level1中的数据达到一定程度也会触发Compact，将数据压缩合并到level2层，以此类推。

关于访问速度

磁盘访问时间：寻道时间 + 旋转时间 + 传输时间；

• 寻道时间：8ms~12ms；

• 旋转时间：7200转/min（半周 4ms）；

• 传输时间：50M/s（约0.3ms）；

磁盘随机 IO << 磁盘顺序 IO ≈ 内存随机 IO << 内存顺序 IO；

MemTable

MemTable 是一个内存数据结构，他保存了落盘到 SST 文件前 的数据。他同时服务于读和写——新的写入总是将数据插入到 memtable，读取在查询 SST 文件前总是要查询 memtable，因 为 memtable 里面的数据总是更新的。一旦一个 memtable 被 写满，他会变成不可修改的，并被一个新的 memtable 替换。 一个后台线程会把这个 memtable 的内容落盘到一个 SST 文 件，然后这个 memtable 就可以被销毁了。

默认的 memtable 实现是基于 skiplist 的。

影响 memtable 大小的选项：

• write_buffer_size: 一个 memtable 的大小；

• db_write_buffer_size: 多个列族的 memtable 的大小总 和；这可以用来管理 memtable 使用的总内存数；

• max_write_buffer_number: 内存中可以拥有刷盘到 SST 文件 前的最大 memtable 数；

落盘策略

Memtable 的大小在一次写入后超过 write_buffer_size。

所有列族中的 memtable 大小超过 db_write_buffer_size 了，或者 write_buffer_manager 要求落盘。在这种场景，最 大的 memtable 会被落盘；

WAL 文件的总大小超过 max_total_wal_size。在这个场景， 有着最老数据的 memtable 会被落盘，这样才允许携带有跟这个memtable 相关数据的 WAL 文件被删除。

WAL

RocksDB 中的每个更新操作都会写到两个地方：

1. 一个内存数据结构，名为 memtable (后面会被刷盘到SST 文件)

2. 写到磁盘上的 WAL 日志。

在出现崩溃的时候，WAL 日志可以用于完整的恢复 memtable 中的数据，以保证数据库能恢复到原来的状态。在默认配置的 情况下，RocksDB 通过在每次写操作后对 WAL 调用 fflush来保 证一致性。

WAL 创建时机：

1. db打开的时候；

2. 一个列族落盘数据的时候；（新的创建、旧的延迟删除）

重要参数

• DBOptions::max_total_wal_size： 如果希望限制 WAL 的大 小，RocksDB 使用 DBOptions::max_total_wal_size 作为列 族落盘的触发器。一旦 WAL 超过这个大小，RocksDB 会开始强 制列族落盘，以保证删除最老的 WAL 文件。这个配置在列族以 不固定频率更新的时候非常有用。如果没有大小限制，如果这个 WAL中有一些非常低频更新的列族的数据没有落盘，用户可能会 需要保存非常老的 WAL 文件。

• DBOptions::WAL_ttl_seconds , DBOptions::WAL_size_limit_MB：这两个选项影响 WAL 文件 删除的时间。非0参数表示时间和硬盘空间的阈值，超过这个阀 值，会触发删除归档的WAL文件。

Immutable MemTable

Immutable MemTable 也是存储在内存中的数据，不过是只读 的内存数据；

当 MemTable 写满后，会被置为只读状态，变成 Immutable MemTable。然后会创建一块新的 MemTable 来提供写入操 作；Immutable MemTable 将异步 flush 到 SST 中；

SST

SST （Sorted String Table） 有序键值对集合；是 LSM-Tree 在 磁盘中的数据结构；可以通过建立 key 的索引以及布隆过滤器 来加快 key 的查询；LSM-Tree 会将所有的 DML 操作记录保存 在内存中，继而批量顺序写到磁盘中；这与 B+ Tree 有很大不 同，B+ Tree 的数据更新直接需要找到原数据所在页并修改对应 值；而 SM-Tree 是直接 append 的方式写到磁盘；虽然后面会 通过合并的方式去除冗余无效的数据；

文件格式

 <beginning_of_file>
 [data block 1] 
 [data block 2] 
 ...
 [data block N] 
 [meta block 1: filter块] 
 [meta block 2: stats块] 
 [meta block 3: 压缩字典块] 
 [meta block 4: 范围删除块]
 ...
 [meta block K: 未来拓展块]   (以后可能会加入新的元数据块)
 [metaindex block] 
 [index block] 
 [Footer]                    （定长脚注， 从file_size - sizeof(Footer)开始）
 <end_of_file>

BlockHandle

offset:         varint64 
size:           varint64 

1. 键值对序列在文件中是以排序顺序排列的，并且切分成了一序列 的数据块。这些块在文件头一个接一个地排列。每个数据块都根 据 block_builder.cc 的代码进行编排（参考文件中的注 释），然后选择性压缩（compress）;

2. 数据块之后，我们存出一系列的元数据块。支持的元数据块类型 在下面描述。更多的数据块类型可能会在以后加入。同样的，每 个元数据块都根据 block_builder.cc 的代码进行编排（参考 文件中的注释），然后选择性压缩（compress）;

3. 一个 metaindex 块对每个元数据块都有一个对应的入口项，key 为meta块的名字，值是一个 BlockHandle ，指向具体的元数据 块。

4. 一个索引块，对每个数据块有一个对应的入口项，key 是一个 string，该 string >= 该数据块的最后一个key，并且小于下一个 数据块的第一个 key。值是数据块对应的 BlockHandle。如果索 引类型 IndexType 是 kTwoLevelIndexSearch，这个索引块就 是索引分片的第二层索引，例如，每个入口指向另一个索引块， 该索引块包含每个数据块的索引；

5. 在文件的最后，有一个定长的脚注，包含 metaindex 以及索引 块的 BlockHandle，同时还有一个魔数：

metaindex_handle: char[p];     // metaindex的 Block handle
index_handle:     char[q];     // 索引块的Block handle 
padding:         char[40-p-q]; // 填充0以达到固 定大小 
// (40==2*BlockHandle::kMaxEncodedLength)
magic:           fixed64;     // 0x88e241b785f4cff7 (小端) 

BlockCache

Rocksdb: blockcache innodb:buffer pool（减少磁盘io） 记录索引信息，记录数据信息。最近使用的索引数据信息。

块缓存是 RocksDB 在内存中缓存数据以用于读取的地方。用户 可以带上一个期望的空间大小，传一个 Cache 对象给 RocksDB 实例。一个缓存对象可以在同一个进程的多个 RocksDB 实例之 间共享，这允许用户控制总的缓存大小。块缓存存储未压缩过的块。用户也可以选择设置另一个块缓存，用来存储压缩后的 块。读取的时候会先拉去未压缩的数据块的缓存，然后才拉取 压缩数据块的缓存。在打开直接 IO 的时候压缩块缓存可以替代 OS 的页缓存。

RocksDB 里面有两种实现方式，分别叫做 LRUCache 和 ClockCache。两个类型的缓存都通过分片来减轻锁冲突。容量 会被平均的分配到每个分片，分片之间不共享空间。默认情况 下，每个缓存会被分片到 64 个分片，每个分片至少有 512 B 空间。

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

BlockBasedTableOptions table_options; 
table_options.cache_index_and_filter_blocks = true; 

std::shared_ptr cache = NewLRUCache(capacity); 
table_options.block_cache = cache; 
Options options; 
options.table_factory.reset(new BlockBaseTableFactory(table_options)); 

LRU 缓存

默认情况下，RocksDB 会使用 LRU 块缓存实现，空间为 8MB。每个缓存分片都维护自己的 LRU 列表以及自己的查找哈 希表。通过每个分片持有一个互斥锁来实现并发。不管是查找 还是插入，都需要申请该分片的互斥锁。用户可以通过调用 NewLRUCache 创建一个 LRU 缓存；

Clock缓存

ClockCache 实现了CLOCK算法。每个clock缓存分片都维护一 个缓存项的环形列表。一个clock指针遍历这个环形列表来找一 个没有固定(unpinned block)的项进行驱逐，同时，如果在上一 个扫描中他被使用过了，那么给予这个项两次机会来留在缓存 里。tbb::concurrent_hash_map 被用来查找数据。

与 LRU 缓存比较，clock 缓存有更好的锁粒度。在 LRU 缓存下 面，每个分片的互斥锁在读取的时候都需要上锁，因为他需要 更新他的 LRU 列表。在一个 clock 缓存上查找数据不需要申请 该分片的互斥锁，只需要搜索并行的哈希表就行了，所以有更 好锁粒度。只有在插入的时候需要每个分片的锁。用 clock 缓 存，在一定环境下，我们能看到读性能的增长；

写入流程

1. 写入位于磁盘中的 WAL（Write Ahead Log）里。

2. 写入memtable。

3. 当大小达到一定阈值后，原有的memtable冻结变成 immutable。后续的写入交接给新的memtable和WAL。

4. 后台开启 Compaction 线程，开始将immutable落库变成一个 L0 层的SSTable，写入成功后释放掉以前的 WAL。

5. 若插入新的SSTable后，当前层（Li）的总文件大小超出了阈 值，会从Li中挑选出一个文件，和Li+1层的重叠文件继续合 并，直到所有层的大小都小于阈值。合并过程中，会保证L1以 后，各SSTable的Key不重叠。

读取流程

1. FindFiles。从SST文件中查找，如果在 L0，那么每个文件都 得读，因为 L0 不保证Key不重叠；如果在更深的层，那么Key保 证不重叠，每层只需要读一个 SST 文件即可。L1 开始，每层可 以在内存中维护一个 SST的有序区间索引，在索引上二分查找即 可；

2. LoadIB + FB。IB 和 FB 分别是 index block 和 filter block 的缩写。index block是SST内部划分出的block的索 引；filter block 则是一个布隆过滤器（Bloom Filter），可 以快速排除 Key 不在的情况，因此首先加载这两个结构；

3. SearchIB。二分查找 index block，找到对应的block；

4. SearchFB。用布隆过滤器过滤，如果没有，则返回；

5. LoadDB。则把这个block加载到内存；

6. SearchDB。在这个block中继续二分查找；

7. ReadValue。找到 Key后读数据，如果考虑 WiscKey KV分离的 情况，还需要去 vLog 中读取；

LSM-Tree 三大问题

分布式CAP原则：一致性-可用性-分区隔离性

读放大

用来描述数据库必须物理读取的字节数相较于返回的字节数之 比。和数据分层存放，读取操作也需要分层依次查找，直到找 到对应数据；这个过程可能涉及多次 IO；在 range query 的时 候，影响更大；

空间放大

用来描述磁盘上存储的数据字节数相较于数据库包含的逻辑字 节数之比；所有的写入操作都是顺序写，而不是就地更新，无效数据不会马上被清理掉；

写放大

用来描述实际写入磁盘的数据大小和程序要求写入的数据大小 之比；为了减小读放大和空间放大，RocksDB 采用后台线程合 并数据的方式来解决；这些合并过程中会造成对同一条数据多次写入磁盘；

参考连接：https://github.com/0voice