RocksDB起源于LevelDB，设计的初衷是能够利用好SSD和内存的高性能，通过配置承载高强度读写。

RocksDB 是一个嵌入式 key value数据库, 所有键都是有序的. RocksDB 中三个最基础的结构分别是 memtable, sstfile 和 logfile. memtable 是一个内存数据结构, 新的写入首先写入到memtable, 然后有可能写入到 logfile 中. logfile 是一个在硬盘上顺序写入的文件. 当 memtable 存满了之后, 它会被 flush 到 sstfile, 然后相应的 logfile 就可以安全的删除了. sstfile 中的数据为了方便查找key排序.

RocksDB支持两种形式的comapaction.

Universal Style Compaction 所有文件都存在L0模式, 并且按照时间排序. 这时候一个compaction会把时间上相连的两组文件合并并组成一个新的文件, 再放回到L0. 所有的文件都有可能有重复的键.

Level Style Compaction. 数据按层存储, 也就是L0…Ln. 最新的数据存储在L0, 最老的数据存储在Lmax层. 在L0的文件可能会有交叉的key, 但是在其它层就不会有. compaction发生的时候, 去除Ln的一个文件, 和在Ln+1层所有有相同key的文件, 把他们合并之后作为一个新的文件存储在Ln+1层. 通常来说USC比LSC 产生比较小的写入放大, 但是比较大的空间放大.

数据库系统调优很大一部分工作是在写放大、读放大和空间放大这三个放大因子之间做取舍。

写放大

平均写入1个字节，引擎中在数据的声明周期内实际会写入n个字节，其写放大率是n。如果业务方写入速度是10MB/s，在引擎端或者操作系统层面能观察到的数据写入速度是30MB/s，系统的写放大率就是3。写放大过大会制约系统的实际吞吐。对于SSD来说，也会导致SSD寿命缩短。

读放大

一个读请求，系统所需要读n个页面来完成查询，其读放大率是n。逻辑上的读操作可能会命中引擎内部的cache或者文件系统cache，命中不了cache就会进行实际的磁盘IO，命中cache的读取操作的代价虽然很低，但是也会消耗CPU。

空间放大

平均存储1个字节的数据，在存储引擎内部所占用的磁盘空间n和字节，其空间放大是n。比如写入10MB的数据，磁盘上实际占用了100MB，这是空间放大率就是10。空间放大和写放大在调优的时候往往是排斥的，空间放大越大，那么数据可能不需要频繁的compaction，其写放大就会降低；如果空间放大率设置的小，那么数据就需要频繁的compaction来释放存储空间，导致写放大增大。

Statistics

Parallelism options

LSM架构引擎主要有两种线程，flush和compaction。flush优先级高，compaction优先级低。为了充分利用多核，RocksDB中的两种线程可以配置线程数。

max_background_flushes: memtable dump成sstable的并发线程数。当使用多个column family时，内部会存在多个memtable，可能会同时发生flush，如果线程是1，在写入量大的情况下，可能会导致flush不及时，出现无法写入的情况。

max_background_compactions: sstable flush线程，因为一般RocksDB会有多层，涉及多个sstable文件，并发compaction会加快compaction的速度，如果compaction过慢，达到soft_pending_compaction_bytes_limit会发生阻塞，达到hard_pending_compaction_bytes会停写。

RocksDB目前支持两种表格式：Plain Table & Block-Based Table。

  • Block-Based Table 从LevelDB继承来的默认格式，设计用于在磁盘与闪存存储数据。
  • Plan Table SSTable格式，用于在内存存储&低延迟查询进行优化。

BlockBasedTableOptions

flush_block_policy_factory

cache_index_and_filter_blocks [false]

BlockHandle is a pointer to the extent of a file that stores a data block or a meta block.

Footer encapsulates the fixed information stored at the tail end of every table file.

1
2
3
4
5
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)
1
2
3
4
5
6
7
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)

CompressionType：

  • No Compression
  • Snappy Compression
  • Zlib Compression
  • BZip2 Compression
  • LZ4 Compression
  • LZ4HC Compression
  • Xpress Compression
  • ZSTD
  • ZSTD Not Final Compression
  • Disable Compression Option

LSM Compaction

Google发表BigTable的论文，推动了基于LSM系统架构流行。数据首先写WAL，再写Memtable，满足一定条件后冻结Memtable，执行转储操作形成一个SSTable。随着数据写入不断增多，转储次数也会不断增多，进而转储SSTable也会越来越多。然而，太多SSTable会导致数据查询IO次数增多，因此后台尝试着不断对这些SSTable进行合并，这个合并过程称为Compaction。Compaction分为两类：Minor Compaction和Major Compaction。

Minor Compaction是指选取一个或多个小的、相邻的转储SSTable与0个或多个Frozen Memtable，将它们合并成一个更大的SSTable。一次Minor Compaction的结果是更少并且更大的SSTable。

Major Compaction是指将所有的转储SSTable和一个或多个Frozen Memtable合并成一个SSTable，这个过程会清理被删除的数据。一般情况下，Major Compaction时间会持续比较长，整个过程会消耗大量系统资源，对系统有比较大的影响。

通常Compaction涉及到三个放大因子，Compaction需要在三者之间做取舍。

Write Amplification : 写放大，假设每秒写入10MB的数据，但观察到硬盘的写入是30MB/s，那么写放大就是3。写分为立即写和延迟写，比如Redo Log是立即写，传统基于B Tree数据库刷脏页和LSM Compaction是延迟写。Redo Log使用direct IO写时至少以512字节对齐，假如log记录为100字节，磁盘需要写入512字节，写放大为5。

Read Amplification : 读放大，对应于一个简单query需要读取硬盘的次数。比如一个简单query读取了5个页面，发生了5次IO，那么读放大就是 5。假如B Tree的非叶子节点都缓存在内存中，point read-amp 为1，一次磁盘读取就可以获取到Leaf Block；short range read-amp 为1~2，1~2次磁盘读取可以获取到所需的Leaf Block。

Space Amplification : 空间放大，假设我需要存储10MB数据，但实际硬盘占用了30MB，那么空间放大就是3。有比较多的因素会影响空间放大，比如在Compaction过程中需要临时存储空间，空间碎片，Block中有效数据的比例小，旧版本数据未及时删除等等。

RocksDB放大系数高达42倍，LevelDB也高达27倍。写放大意味着更多的读写，会造成系统性能波动，比如对SSD来说会加速寿命衰减，从成本角度说也更加耗电，采用更优的避免写放大的算法可以使用成本更低廉的SSD，写放大还影响数据库系统的持续写入的带宽，假如磁盘带宽为500M/s，写放大为10，那么数据库持续写入的的最大带宽为50M/s，所以解决写放大就成了一个很重要的问题。

放大问题的本质是一个系统对随时全局有序的需求有多么的强烈。

随时，就是任何的写入都不能导致系统无序；

全局，即系统内任意元单位之间都要保持有序。

B-Tree系列是随时全局有序的典型代表，而Fractal Tree打破了全局的约束，允许局部无序，提升了随机写能力；LSM系列进一步打破了随时的约束，允许通过后台的Compaction来整理排序。在LSM这种依靠后台整理来保序的系统里面，系统对序的要求越强烈，写放大越严重。

要同时将写放大，读放大，空间放大优化到最优是很难的，比如SSD内部的碎片整理，碎片越多，空间放大和读放大越严重，为了改善空间放大和读放大，将page中的有效数据拷贝到新的page里（copy-out），这样会带来写放大，如果page中有效数据率越低，那么空间放大越大，copy-out的写放大越低，反之，空间放大越小，copy-out写放大越大。

随着数据写入不断增加，Minor Freeze不断触发，转储数据不断增多，一次查询可能需要越来越多的IO操作，读取延时也在不断变大。而执行Minor Compaction会使得转储文件数基本稳定，进而IO Seek次数会比较稳定，延迟就会稳定在一定范围。然而，Minor Compaction操作重写文件会带来很大的带宽压力以及短时间IO压力。因此可以认为，Minor Compaction就是使用短时间的IO消耗以及带宽消耗换取后续查询的低延迟。

为了换取后续查询的低延迟，除了短时间的读放大之外，Compaction对写入也会有很大的影响。当写请求非常多，导致不断触发Minor Compaction生成转储SSTable，多次Minor Freeze会触发Major Freeze，从而导致Major Compaction，但Compaction的速度远远跟不上数据写入速度，Memtable内存不足时，会限制用户数据写入。如果Compaction消耗大量IO和带宽，也会导致读性能急剧下降。为了避免这种情况，在Memtable内存紧张时候会限制写请求的速度。

Minor Compaction释放Memtable内存，清理不必要的多版本数据，同时保证转储SSTable数量稳定，降低读延迟；Major Compaction清除删除和过期的数据，有效降低存储空间，也可以有效降低读取时延。Compaction会使得数据读取延迟一直比较平稳，但付出的代价是大量的读延迟毛刺和一定的写阻塞。

Compaction的设计总是会追求一个平衡点，一方面需要保证Compaction的基本效果，另一方面又不会带来严重的IO压力。然而，并没有一种设计策略能够适用于所有应用场景或所有数据集。Compaction选择什么样的策略需要根据不同的业务场景、不同数据集特征进行确定。设计Compaction策略需要根据业务数据特点，目标就是降低各种放大，不断权衡如下几点：

  • 合理控制读放大：避免因Minor Freeze增多导致读取时延出现明显增大，避免请求读取过多SSTable；

  • 合理控制写放大：避免一次又一次地Compact相同的数据；

  • 合理控制空间放大：避免让不需要的多版本数据，已经删除的数据和过期的数据长时间占据存储空间，避免在Compaction过程中占用过多临时存储空间，及时释放已经Compact完成的无用SSTable的存储空间；

  • 控制Compaction使用的资源：在业务高峰期少使用资源，业务低峰期使用更多的资源；

  • 控制Compaction平滑度：在一定的负载下，业务的响应时间和吞吐量稳定可预期；

Compaction算法演进

  1. Memtable(增量数据) + L1(基线数据)： 业务每天的修改几乎可以全部存储在Memtable中，采用每日Major Compaction的方式将增量数据与基线数据进行合并。
  2. Memtable(增量数据)+L0(增量转储数据)+L1(基线数据)：Memtable已经不能存储整天的修改数据，当系统内存紧张时，触发Minor Freeze，然后转储生成SSTable。

根据场景选择Compaction策略

Write Only，大量随机rowkey insert/update/delete

优化写放大，采用Memtable + L0 + L1模式，每次转储生成一个SSTable，L0的总大小与L1相同时进行Major Compaction写放大最小。

Write Mostly，大量随机rowkey insert/update/delete

优化写放大，容忍稍大的读放大，采用Memtable + L0 + L1模式，L0层累积多次Major Freeze的增量SSTable数据，L0层包含多个SSTable，按照优化写放大策略控制L0层SSTable数量和大小，使用Stripe Compaction和渐进合并策略减少Major Compaction的写放大和临时空间放大。

Read Only，或write很少

最优写放大，读放大和空间放大，采用Memtable + L1模式，Memtable没有数据或只有少量数据。

Read Mostly，少量随机rowkey insert/update/delete

优化读放大，采用Memtable + L0 + L1模式，每次转储Frozen Memtable与前一个L0层SSTable合并成一个新的L0层SSTable，如果delete range比较多，则在Memtable和L0层SSTable中标记delete range，L0与L1进行Major Compaction的写放大比较小。

Read Mostly，大量随机rowkey insert/update/delete

优化写放大和读放大，采用Memtable + L0 + L1模式，L0层累积多次Major Freeze的增量SSTable数据，L0层包含多个SSTable，根据用户的访问热点决定哪些range内的L0层SSTable合并，如果delete range比较多，则在Memtable和L0层SSTable中标记delete range，将L0和L1分成多个sub-range条带，每个sub-range积累了足够增量数据后才进行Major Compaction，类似渐进合并的方式，每次Major Freeze都合并L0和L1的部分range数据。如果delete比较多，空间放大不优，不能即使释放已经删除数据的存储空间。

MANIFEST

MANIFEST是记录RocksDB状态改变的所有transction log的一种机制。Manifest 日志记录了RocksDB状态的Snapshot和Edit Log，命名方式为 MANIFEST-(序列号，递增)。CURRENT是最近的Manifest 日志。

Version

LeveDB用Version表示一个版本的元信息。

Version中主要包括一个FileMetaData指针的二维数组，分层记录了所有的SST文件信息。

FileMetaData数据结构用来维护一个文件的元信息，包括文件大小，文件编号，最大最小值，引用计数等，其中引用计数记录了被不同的Version引用的个数，保证被引用中的文件不会被删除。

Version中还记录了触发Compaction相关的状态信息，这些信息会在读写请求或Compaction过程中被更新。

通过庖丁解LevelDB之概览中对Compaction过程的描述可以知道在CompactMemTable和BackgroundCompaction过程中会导致新文件的产生和旧文件的删除。每当这个时候都会有一个新的对应的Version生成，并插入VersionSet链表头部。

VersionSet是一个Version构成的双向链表，这些Version按时间顺序先后产生，记录了当时的元信息，链表头指向当前最新的Version，同时维护了每个Version的引用计数，被引用中的Version不会被删除，其对应的SST文件也因此得以保留，通过这种方式，使得LevelDB可以在一个稳定的快照视图上访问文件。VersionSet中除了Version的双向链表外还会记录一些如LogNumber，Sequence，下一个SST文件编号的状态信息。

Version Edit Layout

DBImpl keeps a ColumnFamilySet, which references to all column families by
pointing to respective ColumnFamilyData object of each column family.

ColumnFamilyHandle also points to ColumnFamilyData directly, so that
when a user executes a query, it can directly find memtables and Version
as well as SuperVersion to the column family, without going through
ColumnFamilySet.

ColumnFamilySet points to the latest view of the LSM-tree (list of memtables
and SST files) indirectly, while ongoing operations may hold references
to a current or an out-of-date SuperVersion, which in turn points to a
point-in-time view of the LSM-tree.

ColumnFamilyData keeps all the data that a column family needs.

ColumnFamilySet

MemTableList stores references to all the immutable memtables.

The memtables are flushed to L0 as soon as possible and in any order.

If there are more than one immutable memtable, their flushes can occur concurrently.

SuperVersion holds references to memtable, all immutable memtables and version.

Version A column family’s version consists of the SST files owned by the column family at a certain point in time.

Reference

  1. A Tutorial of RocksDB SST formats
  2. 看图了解RocksDB
  3. 一文带你了解LSM Compaction
  4. RocksDB参数调优
  5. LSM树原理探究