1. RocksDB简介

• 一个带版本的Key-Value存储引擎，Key/Value采用字符串编码，Key和Value最大长度为4GB，主要针对高性能的SSD场景，也支持不同介质的存储模型
• 它是一个C++库，支持点查和范围查询，提供不同类型的ACID保障
• 将随机写转换为顺序写，带来读写放大的问题
• Key有序，支持Get(key)/Put(Key)/Delete(Key)/Merge(Key) and NewIterator()方法
• 它引入了LevelDB project(version 1.5)的部分源码，同时吸收了Apache Hbase的一些优秀的设计理念，LevelDB 的选择是：牺牲部分 Get 性能，换取强悍 Put 性能，再极力优化 Get

2. RocksDB Feature Timeline

3. RocksDB的存储结构

3.1. MemoryTable

开发库提供了三个 memtable：

• skiplist memtable
• vector memtable
• 前缀散列（prefix-hash） memtable

Vector memtable 适用于将数据批量加载到数据库中。每个写入在向量的末尾插入一个新元素; 当它刷新 memtable 到存储的时候，向量中的元素被排序并写出到 L0 中的文件。

前缀散列 memtable 允许对 gets，puts 和 scans-within-a-key-prefix 进行有效的处理。

SkipList：跳表由 William Pugh 在 1990 年提出，相关论文为：Skip Lists: A Probabilistic Alternative to Balanced Trees。跳表是一种可以取代平衡树的数据结构。跳表使用概率均衡而非严格均衡策略，从而相对于平衡树，大大简化和加速了元素的插入和删除。

3.2. SSTable

SSTable 的格式为文件本身就是一个排序的、不可变的、持久的Key/Value对Map。其中Key和value都可以是任意的byte字符串。 KeyValue 对根据固定比较规则有序地写入到文件中，文件内部分成一系列的Blocks(Block 不会太大，可自定义，默认4KB，常见的是 64KB，RocksDB对应配置项：table_options.block_size)，同时具有必要的索引信息。这样就既可以顺序地读取内部 KeyValue 记录，也能够根据某个Key值进行快速定位。

如图所示，SST 文件从头到尾分成5个部分。

3.3. Block

从上面的表格可以看出RocksDB的SSTable除了Footer外其余都是使用Block进行存储的，Block在硬盘上存储的时候，会在实际数据之后加上5个字节的额外内容：compression type、crc，如下图所示：

3.4. Bloom Filter

这里再说一下MetaBlock中的Bloom Filter，Bloom Filter的作用是对于任意集合的key，基于BitMap可以用来构建一个bit数组的算法。给出任意key，这个bit数组可以用于决定这个key是不是可能存在或者绝对不存在于这个key集合，用来减少无用的查询次数，从而加快查询的速度。

3.5. Footer

以上各部分都是 Block 的结构，只有 Footer 不同，是一个定长的格式。

序列化后，Footer的长度固定，为48个字节（旧）或53字节（新），格式如下：

// legacy footer format:
//    metaindex handle (varint64 offset, varint64 size)
//    index handle     (varint64 offset, varint64 size)
//    <padding> to make the total size 2 * BlockHandle::kMaxEncodedLength
//    table_magic_number (8 bytes)
// new footer format:
//    checksum type (char, 1 byte)
//    metaindex handle (varint64 offset, varint64 size)
//    index handle     (varint64 offset, varint64 size)
//    <padding> to make the total size 2 * BlockHandle::kMaxEncodedLength + 1
//    footer version (4 bytes)
//    table_magic_number (8 bytes)

Footer 中的信息，指明了 MetaIndexBlock 和 IndexBlock的位置，进而找到 MetaBlock 和 DataBlock。

读取 SST文件的时候，就是从文件末尾，固定读取这48或53字节，进而得到了 Footer 信息。

3.6. 磁盘文件

• *.log: 事务日志用于保存数据操作日志，可用于数据恢复
• *.sst: 数据持久换文件（此处的例子没有生成sst文件是因为第一次写数据，数据量小没触发flush操作，数据都在内存的MemoryTable中）
• MANIFEST：数据库中的 MANIFEST 文件记录数据库状态。Compaction过程会添加新文件并从数据库中删除旧文件，并通过将它们记录在 MANIFEST 文件中使这些操作持久化。
• CURRENT：记录当前正在使用的MANIFEST文件
• LOCK：rocksdb自带的文件锁，防止两个进程来打开数据库。
• IDENTITY：id
• LOG：统计日志
• OPTIONS：配置信息

3.7. 内存

RocksDB的内存大致有如下四个区：

• Block Cache
• Indexes and bloom filters
• Memtables
• Blocked pinned by iterators

Block Cache

RocksDB 的数据的缓存，这个缓存可以在多个 RocksDB 的实例下缓存。一般默认的Block Cache 中存储的值是未压缩的，而用户可以再指定一个 Block Cache，里面的数据可以是压缩的。用户访问数据先访问默认的 Block Cache，待无法获取后再访问用户 Cache，用户 Cache 的数据可以直接存入 page cache 中。

Cache 有两种：LRUCache 和 BlockCache。Block 分为很多 Shard，以减小竞争，所以 shard 大小均匀一致相等，默认 Cache 最多有 64 个 shards，每个 shard 的 最小 size 为 512k，总大小是 8M，类别是 LRU。

    std::shared_ptr<Cache> cache = NewLRUCache(capacity);
    BlockedBasedTableOptions table_options;
    table_options.block_cache = cache;
    Options options;
    options.table_factory.reset(new BlockedBasedTableFactory(table_options));  

这个 Cache 是不压缩数据的，用户可以设置压缩数据 BlockCache，方法如下：

table_options.block_cache_compressed = cache;

如果 Cache 为 nullptr，则RocksDB会创建一个，如果想禁用 Cache，可以设置如下 Option：

table_options.no_block_cache = true;

默认情况下RocksDB用的是 LRUCache，大小是 8MB， 每个 shard 单独维护自己的 LRU list 和独立的 hash table，以及自己的 Mutex。

RocksDB还提供了一个 ClockCache，每个 shard 有自己的一个 circular list，有一个 clock handle 会轮询这个 circular list，寻找过时的 kv，如果 entry 中的 kv 已经被访问过则可以继续存留，相对于 LRU 好处是无 mutex lock，circular list 本质是 tbb::concurrenthashmap，从 benchmark 来看，二者命中率相似，但吞吐率 Clock 比 LRU 稍高。

Block Cache初始化之时相关参数：

• capacity 总的内存使用量
• num_shards_bits 把 key 的前 n bits 作为 shard id，则总 shard 的数目为 2 ^ num_shards_bits；
• strict_capacity_limit 在一些极端情况下 block cache 的总体使用量可能超过 capacity，如在对 block 进行读或者迭代读取的时候可能有插入数据的操作，此时可能因为加锁导致有些数据无法及时淘汰，使得总体capacity超标。如果这个选项设置为 true，则此时插入操作是被允许的，但有可能导致进程 OOM。如果设置为 false，则插入操作会被 refuse，同时读取以及遍历操作有可能失败。这个选项对每个 shard 都有效，这就意味着有的 shard 可能内存已满， 别的 shard 却有很多空闲。
• high_pri_pool_ratio block中为高优先级的 block 保留多少比例的空间，这个选项只有 LRU Cache 有。

默认情况下 index 和filter block 与 block cache 是独立的，用户不能设定二者的内存空间使用量，但为了控制 RocksDB 的内存空间使用量，可以用如下代码把 index 和 filter 也放在 block cache 中：

BlockBasedTableOptions table_options;
table_options.cache_index_and_filter_blocks = true;

Indexes and bloom filters

Index 由 key、offset 和 size 三部分构成，当 Block Cache 增大 Block Size 时，block 个数必会减小，index 个数也会随之降低，如果减小 key size，index 占用内存空间的量也会随之降低。

filter是 bloom filter 的实现，如果假阳率是 1%，每个key占用 10 bits，则总占用空间就是 num_of_keys * 10 bits，如果缩小 bloom 占用的空间，可以设置 options.optimize_filters_for_hits = true，则最后一个 level 的 filter 会被关闭，bloom 占用率只会用到原来的 10% 。

结合 block cache 所述，index & filter 有如下优化选项：

• cache_index_and_filter_blocks 这个 option 如果为 true，则 index & filter 会被存入 block cache，而 block cache 中的内容会随着 page cache 被交换到磁盘上，这就会大大降低 RocksDB的性能，把这个 option 设为 true 的同时也把 pin_l0_filter_and_index_blocks_in_cache 设为 true，以减小对性能的影响。

如果 cache_index_and_filter_blocks 被设置为 false （其值默认就是 false），index/filter 个数就会受 max_open_files 影响，官方建议把这个选项设置为 -1，以方便 RocksDB 加载所有的 index 和 filter 文件，最大化程序性能。

可以通过如下代码获取 index & filter 内存量大小：
std::string out;
db->GetProperty(“rocksdb.estimate-table-readers-mem”, &out);

Memtable

memtable 则是写 buffer，所有 kv 首先都会被写进 memtable，其 size 是 write_buffer_size。 memtable 占用的空间越大，则写放大效应越小，因为数据在内存被整理好，磁盘上就越少的内容会被 compaction。如果 memtable 磁盘空间增大，则 L1 size 也就随之增大，L1 空间大小受 max_bytes_for_level_base option 控制。

可以通过如下代码获取 memtable 内存量大小：

    std::string out;
    db->GetProperty(“rocksdb.cur-size-all-mem-tables”, &out);

Blocks pinned by iterators

这部分内存空间一般占用总量不多，但是如果有 100k 之多的transactions 发生，每个 iterator 与一个 data block 外加一个 L1 的 data block，所以内存使用量大约为 num_iterators * block_size * ((num_levels-1) + num_l0_files)。

可以通过如下代码获取 Pin Blocks 内存量大小：
table_options.block_cache->GetPinnedUsage();

4. I/O流

4.1. 写流程

rocksdb写入时，直接以append方式写到WAL文件以及memtable，随即返回，因此非常快速。memtable达到一定阈值后切换为Immutable Memtable，只能读不能写。

Immutable memtable触发阈值后，后台Flush线程负责按照时间顺序将Immutable Memtable刷盘 生成Level 0 SST，Level 0 SST触发阈值后，经合并操作(compaction)生成level 1 SST，level 1 SST 合并操作生成level 2 SST，以此类推，生成level n SST。流程如下：

同步写 与 异步写

默认情况下，RocksDB 的写是异步的：仅仅把数据写进了操作系统的缓存区就返回了，而这些数据被写进磁盘是一个异步的过程。如果为了数据安全，可以用如下代码把写过程改为同步写：

    rocksdb::WriteOptions write_options;
    write_options.sync = true;
    db->Put(write_options, …);

这个选项会启用 Posix 系统的 fsync(...) or fdatasync(...) or msync(..., MS_SYNC) 等函数。

异步写的吞吐率是同步写的一千多倍。异步写的缺点是机器或者操作系统崩溃时可能丢掉最近一批写请求发出的由操作系统缓存的数据，但是 RocksDB 自身崩溃并不会导致数据丢失。而机器或者操作系统崩溃的概率比较低，所以大部分情况下可以认为异步写是安全的。

RocksDB 由于有 WAL 机制保证，所以即使崩溃，其重启后会进行写重放保证数据一致性。如果不在乎数据安全性，可以把 write_option.disableWAL 设置为 true，加快写吞吐率。

RocksDB 调用 Posix API fdatasync() 对数据进行异步写。如果想用 fsync() 进行同步写，可以设置 Options::use_fsync 为 true。

4.2. 读流程：

按照 memtable --> Level 0 SST–> Level 1 SST --> … -> Level n SST的

顺序读取数据。这和记录的新旧顺序是一的。因此只要在当前级别找到记录，就可以返回。

4.3. Flush流程

简单来说在RocksDB中，每一个ColumnFamily都有自己的Memtable,当Memtable超过固定大小之后(或者WAL文件超过限制)，它将会被设置为Immutable Memtable,然后会有后台的线程启动来刷新这个Immutable Memtable到磁盘(SST)。

在下面这几种条件下RocksDB会flush Memtable到磁盘：

• 当某一个Memtable的大小超过write_buffer_size
• 当所有的Memtable的大小超过db_write_buffer_size
• 当WAL文件的大小超过max_total_wal_size，我们需要清理WAL,因此此时我们需要将此WAL对应的数据都刷新到磁盘，也是刷新Memtable

4.4. Compaction操作

Compaction操作的具体作用：

• 数据合并迁移：首先当上层level的sst文件数量或者大小达到阈值时，就会触发指定的sst文件的合并并迁移到下一层。每一层都会检查是否需要进行compaction，直到数据迁移到最下层
• 数据真删：LSM树的特点决定数据的修改和删除都不是即时的真删，而是写入一条新的数据进行冲抵。这些数据只会在compaction时才会真正删除（HBase是在major compaction中才会删除，minor compaction不会进行真删），所以compaction能释放空间，减少LSM树的空间放大，但是代价就是写放大，需要根据业务场景要求通过参数来调整两者之间的关系，平衡业务与性能。
• 冷热数据管理：RocksDB的数据流向是从Memtable到level 0 最后到 level N，所以数据查询时也是通过这个路径进行的。由于业务上查询大多是热数据的查询，所以数据的冷热管理就显得很必要，能很大程度上提高查询效率；而且由于各个level的sst文件可以使用不同的压缩算法，所以可以根据自己的业务需求进行压缩算法的配置，达到最佳性能。

LSM tree相关的经典压缩算法有下面几种：经典Leveled，Tiered，Tiered+Leveled，Leveled-N,FIFO。除了这些，RocksDB还额外实现了Tiered+Leveled和termed Level，Tiered termed Universal，FIFO。这些算法各有各的特点，适用于不同的场景，不同的 compaction 算法，可以在空间放大、读放大和写放大之间这三个LSM tree的"副作用"中进行取舍，以适应特定的业务场景。大家可以按需选择，如果没有特殊需求，开箱即用即可。至于每一种压缩算法的具体方式以及实现将会在高级特性篇进行讲解。

Compaction算法

主要两个类型的LSM树合并算法：

Leveled

leveled 合并，这个是RocksDB的默认策略

leveled 算法的特点是以读放大和写放大为代价最小化空间放大。

LSM-tree 可以看作是包含若干 level 的序列，每个 level 是仅包括1个 sorted run。相邻 level 的大小之比通常被我们称为 fanout（扇出），当不同 level 之间的 fanout 相同时，LSM-tree 的写放大最小。compaction 选择 L(n) 的数据，与原有 L(n+1) 的数据进行合并，得到新的 L(n+1) 数据。每次 compaction 的最大写放大系数等同于 fanout。

Tiered

一种替代合并策略，有时候被叫做“size tiered”或者“tiered”

Tiered合并通过增加读放大和空间放大，来最小化写放大 。

LSM-tree 依然可以看作是包含若干 level 的序列，每个 level 包括 N 个 sorted run。L(n) 的 sorted run 大小是 L(n-1) 的 N 倍。compaction 通常选择 L(n) 的数据合并得到新的 sorted run 输出到 L(n+1)，但并不与 L(n+1) 的已有数据进行合并。每次 compaction 的最大写放大系数是 1。

两种算法的主要差别在于，leveled合并倾向于更加频繁的把小的排序结果合并到大的里面，而“tiered”等待多个大小接近的排序结果，然后把它们合并到一起。

Tiered+Leveled

Tiered+Leveled会有比leveled更小的写放大，以及比teired更小的空间放大。

Tiered+Leveled实现方式是一种混合实现，在小的层使用tiered，在大的层使用leveld。具体哪一层切换tiered和leveled可以非常灵活。

RocksDB中的Leveled合并也是Tiered+Leveled。一个memtable落盘过程类似于tiered合并——memtable的输出在L0构建一个新的排序结果并且不需要读/重写L0上已经存在的排序结果。根据level0_file_num_compaction_trigger的配置，L0可以有多个sort run，所以L0是Teired的。 其它层为Leveled。

FIFO Compaction

FIFO Style Compaction 是最简单的合并策略。很适合用于保存低开销的事件日志数据（例如查询日志）。当文件总大小超过配置值 CompactionOptionsFIFO::max_table_files_size （默认值为 1GB) 时，最早的 SST 文件将会被删除。

使用FIFO时，所有的文件都位于 L0，因此SST文件过多，导致查询性能急剧下降。

开启 CompactionOptionsFIFO.allow_compaction 参数，可以触发 L0 IntraCompaction，每次至少选取 level0_file_num_compaction_trigger 个 SST 文件进行合并，从而减少文件数量。

FIFO Compaction with TTL

FIFO Compaction with TTL 在 FIFO compaction 的基础之上，提供 SST 文件级别的过期删除功能。当 SST 的最新的 key 存在时间超过 mutable_cf_options.ttl，则该 SST 文件将会在 TTL compaction 中被删除。

Write Stall

Too many memtables

• 写限速: 如果max_write_buffer_number大于3，将要flush的memtables大于等于max_write_buffer_number - 1，write会被限速。
• 禁写: memtable个数大于等于max_write_buffer_number，触发禁写，等到flush完成后允许写入

Too many level-0 SST files

• 写限速: L0文件数量达到level0_slowdown_writes_trigger，触发写限速。
• 禁写: L0文件数量达到level0_stop_writes_trigger，禁写。

Too many pending compaction bytes

• 写限速: 等待compaction的数据量达到soft_pending_compaction_bytes，触发写限速。
• 禁写: 等待compaction的数据量达到hard_pending_compaction_bytes，触发禁写。

4.5. Compression操作

使用options.compression来指定使用的压缩方法。默认是Snappy。但是大多数情况下LZ4总是比Snappy好。之所以把Snappy作为默认的压缩方法，是为了与旧版本保持兼容。LZ4/Snappy是轻量压缩，所以在CPU使用率和存储空间之间能取得一个较好的平衡。

如果你想要进一步减少存储的使用并且你有一些空闲的CPU，你可以尝试设置options.bottommost_compression来使用一个更加重量级的压缩。最底层会使用这个方式进行压缩。通常最底层会保存大部分的数据，所以用户通常会选择偏向空间的设定，而不是花费cpu在各个层压缩所有数据。我们推荐使用ZSTD。如果没有，Zlib是第二选择。

如果你有大量空闲CPU并且希望同时减少空间和写放大，把options.compression设置为重量级的压缩方法，所有层级都生效。推荐使用ZSTD，如果没有就用Zlib

当然也可以通过一个已经过期的遗留选项options.compression_per_level，你可以有更好的控制每一层的压缩方式。当这个选项被使用的时候，options.compression不会再生效，但是正常情况下这个是不必要的，除非你有极特殊的需求或者性能优化要求。

最后可以通过把BlockBasedTableOptions.enable_index_compression设置为false来关闭索引的压缩。

4.5. 离线Ingest

Ingest实现上主要是两部分：创建SST文件和导入SST文件：

4.5.1. 创建SST文件

创建SST文件的过程比较简单，创建了一个SstFileWriter对象之后，就可以打开一个文件，插入对应的数据，然后关闭文件即可。 写文件的过程比较简单，但是要注意下面三点：

• 传给SstFileWriter的Options会被用于指定表类型，压缩选项等，用于创建sst文件。
• 传入SstFileWriter的Comparator必须与之后导入这个SST文件的DB的Comparator绝对一致。
• 行必须严格按照增序插入

4.5.2. 导入SST文件

导入SST文件也非常简单，需要做的只是调用IngestExternalFile()然后把文件地址封装成vector以及相关的options传入参数即可。下面是IngestExternalFile()的实现逻辑：

• 把文件拷贝，或者链接到DB的目录。
• 阻塞DB的写入（而不是跳过），因为我们必须保证db状态的一致性，所以我们必须确保，我们能给即将导入的文件里的所有key都安全地分配正确的序列号。
• 如果文件的key覆盖了memtable的键范围，把memtable进行flush操作。
• 把文件安排到LSM树的最合适的层级。
• 给文件赋值一个全局序列号。
• 重新启动DB的写操作。

为了减少compaction的压力，我们总是想将目标的sst文件写入最合适的层级，即合适写入的最低层级，下面三个条件作为约束可以选出合适的层级：

• 文件可以安排在这个层
• 这个文件的key的范围不会覆盖上面任何一层的数据
• 这个文件的key的范围不会覆盖当前层正在进行压缩

另外，5.5以后的新版本的RocksDB的IngestExternalFile加载一个外部SST文件列表的时候，支持下层导入，意思是如果ingest_behind为true，那么重复的key会被跳过。在这种模式下，我们总是导入到最底层。文件中重复的key会被跳过，而不是覆盖已经存在的key。