引擎整体架构

img

MemTable 与 WAL

RocksDB 使用 LSM （Log-structed Merge-tree）作为主要的存储数据结构，每当数据写入到 RocksDB 之中，就会被添加到 MemTable 内存的写缓冲区，以及一个磁盘上的超前写入日志（WAL）。数据会被写入到 WAL 和 MemTable，WAL 是 MemTable 的易失性保护机制。

RocksDB 中 Memtable 的数据结构有三种，分别是 skiplist、hash-skiplist、hash-linklist，跳表的好处在于插入的时候可以保证数据的有序，并且支持二分查找、范围查询。插入和搜索的代价都是 O(log n)。

在达到指定大小之后现有 MemTable 和 WAL 锁定变为不可变，新数据写入新的 MemTable 和 WAL。

SSTable

SSTable 是一种数据结构，当 MemTable 到达一定的上限之后，会 flush 到硬盘上 Sorted String Table (SSTable)，并放置在第 0 层(L0)，对应的 WAL 空间回收；L0 大小达到上限时，L0 的 SSTable 经过 compaction 落到 L1；Ln：以此类推完成上述操作。

在每一级中，都会使用二分搜索；而布隆过滤器会消除 SSTable 文件中不必要的检索。

Compaction

Campact 可以翻译成压缩，也可以被称为压实，其作用主要有：清除无效数据；对数据的排序进行优化。而无效数据的产生于 update：标记覆盖与 delete：标记删除。使用 Compact 的好处有：整个文件的批量读写，比较高效；可以并行化操作。

比较几种常见的 Compaction 策略：

  • Leveled：leveldb 的方式，SSTable 数量逐层以指数增长，读写放大都比较严重，但是空间放大较低；leveled 算法的特点是以读放大和写放大为代价最小化空间放大。
  • Tired/Universal：Cassandra 与 HBase 的方式，空间放大和读放大严重，但是写放大最小；Tiered合并通过增加读放大和空间放大，来最小化写放大 。
  • FIFO：删除旧的过期文件，执行轻量级压缩，适用于那些 in-memory 缓存应用。

大家也可以发现，并不存在写放大、读放大和空间放大都很完美的方案；和计算机世界的其他领域一样，数据库也没有银弹。

Level 0的压缩策略采用的是Size-Tiered Compaction策略，即将多个大小相等的sst文件合并成一个更大的sst文件，减少磁盘空间的占用。L0的sst文件时无序的，仅将MemTable中全部数据创建一个新的sst插入level0。对于L0 的文件，RocksDB 采用遍历的方法查找

Level 1以后的每个level大小是前一个level的倍数，Level n的压缩策略采用的是Leveled Compaction策略，即将多个sst文件按照level进行合并，保证每个level的sst文件数量不超过一个阈值，同时保证每个level的sst文件大小不超过一个阈值.对于 L1 层以及 L1 层以上层级的文件，每个 SSTable 没有交叠，可以使用二分查找快速找到 key 所在的 Level 以及 SSTfile。

各层限制大小：leve1:300M, level2:3G, level3:30G, level4:300G

RocksDB会先从Level 0中的sst文件开始查找，如果找不到，则会从Level 1开始查找，直到找到为止。由于每个level内部的sst文件都是有序的，因此可以利用这个特性来进行快速查。

详细

合并流程

  1. 数据追加写入MemTable，MemTable满了构建一个SST放到L0层。导致L0层的sst文件是无序的，需要遍历查找
  2. L0层的文件数达到level0_file_num_compaction_trigger，compaction会被触发。
  3. L0层会挑选一个SST文件，如果SST文件key空间太大，会进行拆分，选取出一部分key在某个范围内的。将这部分合并到L1层和这些key所在key空间一致的。
  4. 假设L0层挑选出来的SST需要和L1层的SST_x, SST_y, SST_y合并。则会生成一个新的SST，并将其进行分隔，写入到L1层，然后删除旧的SST文件
  5. L1层达到空间上限了，又会挑选一个SST文件，按类似的方式合并到下一层。

rocksdb事务

ACID事务实现

参考文献：
深入RocksDB原理 https://zhuanlan.zhihu.com/p/616209332
RocksDB学习记录 https://km.woa.com/articles/show/506592
RocksDB上锁机制 https://www.cnblogs.com/cchust/p/7107392.html
图解RocksDB合并过程 https://blog.csdn.net/qq_40586164/article/details/117914647