RocksDB索引模型

(1) RocksDB是什么

RocksDB是 Facebook 开源的一个高性能持久化 KV 存储。

RocksDB是一个基于LSM树的键值存储引擎，旨在提供高性能、可扩展性和可靠性。
它的核心思想是将数据分为多个层级，每个层级使用不同的数据结构来存储数据。

越来越多的新生代数据库，都不约而同地选择 RocksDB 作为它们的存储引擎。
比如 CockroachDB 用到了 RocksDB 作为它的存储引擎;
MyRocks 项目用 RocksDB 给 MySQL 做存储引擎，目的是取代现有的 InnoDB 存储引擎。

(2) 为什么要用RocksDB

简单来说有3个主要原因：1:持久化 2:数据量大时用磁盘存储便宜

来对比一下 RocksDB 和 Redis 这两个 KV 存储。

Redis是内存数据库，从官方给出的测试数据来看，它的随机读写性能大约在 50 万次 / 秒左右。
RocksDB 数据存储在磁盘， 相应的随机读写性能大约在 20 万次 / 秒左右。

虽然性能还不如 Redis，但是已经可以算是同一个量级的水平了。

Redis 是一个内存数据库，并不是一个可靠的存储。数据写到内存中就算成功了，它并不保证安全地保存到磁盘上。
而 RocksDB 它是一个持久化的 KV 存储，它需要保证每条数据都要安全地写到磁盘上

(3) RocksDB索引模型

RocksDB 采用了一个非常复杂的数据存储结构，并且这个存储结构采用了内存和磁盘混合存储方式，使用磁盘来保证数据的可靠存储，并且利用速度更快的内存来提升读写性能。这种数据结构就是 LSM-Tree 。

(3.1) RocksDB使用的数据结构

LSM-Tree 的全称是：The Log-Structured Merge-Tree，是一种非常复杂的复合数据结构，它包含了 WAL（Write Ahead Log）、跳表（SkipList）和一个分层的有序表（SSTable，Sorted String Table）。

LSM-Tree 论文 https://ranger.uta.edu/~sjiang/pubs/papers/wang14-LSM-SDF.pdf

WAL 保证数据顺序写入
跳表 查询性能O(log N)
分层有序表 排序

LSM-Tree（Log-Structured Merge Tree）是一种针对写入密集型工作负载进行优化的基于磁盘的数据结构。
它由多个级别组成，每个级别都是键值对的排序运行。
当执行写操作时，新的键值对将添加到内存缓冲区中。一旦缓冲区达到一定大小，它将作为新的排序运行刷新到磁盘上。
当一个级别中的排序运行数量超过一定阈值时，它们将合并为下一个级别中的新的排序运行。

这个合并过程是LSM-Tree的效率所在。通过合并排序运行而不是单个键值对，LSM-Tree可以减少读取特定键值对所需的磁盘寻道次数。
此外，通过保持内存缓冲区相对较小，LSM-Tree可以减少维护数据结构所需的内存量。

要实现LSM-Tree，可以使用SkipList数据结构作为每个级别中的排序运行。SkipList的Insert方法可用于将新的键值对添加到内存缓冲区中，FindGreaterOrEqual方法可用于在排序运行中高效地搜索特定键。合并过程可以使用Iterator对象和SkipList的Merge方法的组合来实现。

总的来说，LSM-Tree是一种强大的数据结构，非常适合写入密集型工作负载。通过利用SkipList和排序运行的原理，LSM-Tree可以提供高效的写入和读取性能，同时最小化维护数据结构所需的内存量。

(3.2) 新增数据

当 LSM-Tree 收到一个写请求，比如说：PUT foo bar，把 Key foo 的值设置为 bar。
1、操作命令会被写入到磁盘的 WAL 日志中（图中右侧的 Log）。
2、数据会被写入到内存中的 MemTable 中，返回写入成功。
3、MemTable 写满(默认是32M)之后，就被转换成 Immutable MemTable，然后再创建一个空的 MemTable 继续写。
4、后台线程不断把 Immutable MemTable 复制到磁盘文件中，然后释放内存空间。 (此时每个文件里的Key是有序的，但是文件之间是完全无序的)
5、分层合并使文件有序。 (除第0层无序， 第0层是MemTable 直接 dump 出来的磁盘文件所在的那一层)

(3.2.1) WAL日志的作用

写WAL日志是顺序写磁盘，性能较好。
WAL日志可以用于故障恢复，一旦系统宕机，可以从日志中把内存中还没有来得及写入磁盘的数据恢复出来。
WAL日志解决了数据可靠性的问题。

(3.2.2) MemTable的作用

MemTable 是一个按照 Key 组织的跳表（SkipList），查询复杂度是 O(log N)
写 MemTable 是个内存操作，速度也非常快。

跳表和平衡树有着类似的查找性能，但实现起来更简单一些。

这里面有一点需要注意的是，LSM-Tree 在处理写入的过程中，直接就往 MemTable 里写，并不去查找这个 Key 是不是已经存在了。

把 MemTable 写入 SSTable 这个写操作，因为它是把整块内存写入到整个文件中，这同样是一个顺序写操作。

(3.2.3) 分层合并

SSTable 被分为很多层，越往上层，文件越少，越往底层，文件越多。
每一层的容量都有一个固定的上限，一般来说，下一层的容量是上一层的 10 倍。
当某一层写满了，就会触发后台线程往下一层合并，数据合并到下一层之后，本层的 SSTable 文件就可以删除掉了。
合并的过程也是排序的过程，除 Level 0 以外，每一层内的文件都是有序的，文件内的 KV 也是有序的。

(3.3) 更新数据

和新增数据一样

(3.4) 删除数据

LSM-Tree 删除数据：在每条数据上增加一个删除的标志位，查询的时候判断是否已经删除，落盘的时候根据删除标志位合并数据，但是这样会浪费一些空间资源

标记删除，有墓碑的概念，被删除的条目，如果在memtable里，可以直接通过墓碑标记为删除，如果不在memtable里就插入一条新的删除记录，这两种情况都会在层级合并的时候真正发挥作用，同时WAL里通过一条额外的log记录这个删除操作。

另外感觉WAL里存储的其实就是操作指令流，和raft里面的日志完全一个概念，所以raft协议和leveldb/rocksdb的组合简直是绝配

(3.5) 查询数据

查询的过程是按照顺序从一个一个table中去查询，先查内存后查磁盘
Level 0 是无序的，所以一般Level只保存很少的几个文件。Level 0的查找顺序就是按照文件的创建顺序倒序查找，也就是从最新的向最旧的查找。

(3.6) 其它

在写入时，数据首先被写入内存中的MemTable，然后根据大小和数量的限制，MemTable会被转换为一个SSTable文件并写入磁盘。
在读取时，RocksDB会首先在内存中的MemTable中查找数据，如果没有找到，则会在磁盘上的SSTable文件中查找。

为了提高读取性能，RocksDB还使用了Bloom Filter和Skip List等数据结构来加速查找。

此外，RocksDB还支持多种数据压缩算法，以减少磁盘空间的使用。

(4) RocksDB索引模型源码解读

(4.1) 源码解析

源码地址: https://github.com/facebook/rocksdb/tree/v8.0.0/memtable

RocksDB索引模型主要源码
Memtable结构
数据结构-SkipList
分层有序表

(4.2) 跳表(SkipList)源码解析

SkipList类是一个模板类，它有两个模板参数：Key和Comparator。Key参数指定键值存储中使用的键的类型，而Comparator参数指定用于比较键的比较函数。

SkipList类提供了几种方法，用于在存储中插入、搜索和迭代键值对。
Insert方法将新的键值对插入存储中；
Contains方法检查给定的键是否存在于存储中；
Iterator类提供了一种按排序顺序迭代存储中键值对的方法。

SkipList类被设计为线程安全的，写操作需要外部同步，通常是互斥锁。
另一方面，读操作不需要任何内部锁定或同步，但需要保证在读取过程中SkipList不会被销毁。

总的来说，SkipList类提供了一个高性能、线程安全的数据结构，用于存储和检索RocksDB中的键值对。

(4.2.1) 跳表结构

https://github.com/facebook/rocksdb/blob/v8.0.0/memtable/skiplist.h#L170

// filepath: memtable/skiplist.h

// 定义 SkipList 类，模板参数为 Key 和 Comparator
template <typename Key, class Comparator>

// 跳表结构定义
class SkipList {
 private:
  // 节点
  struct Node;
                 
 private:
  // 最大高度
  const uint16_t kMaxHeight_;
  // 分支因子的默认值
  const uint16_t kBranching_;
  const uint32_t kScaledInverseBranching_;

  // 构造函数 后 不可更改
  Comparator const compare_;
  // 用于分配节点的分配器
  Allocator* const allocator_; 

  // 头节点
  Node* const head_;

  // 跳表的高度
  // 只能被 Insert() 修改，可以被读取器读取，但是过时的值是可以接受的
  std::atomic<int> max_height_;  

  // 用于优化顺序插入模式，比较棘手
  // prev_[i] 对于 i 小于等于 max_height_ 是 prev_[0] 的前驱节点，prev_height_ 是 prev_[0] 的高度
  // 在插入之前，prev_[0] 只能等于 head_，此时 max_height_ 和 prev_height_ 都为 1
  Node** prev_;
  int32_t prev_height_;

 public:
  // 构造函数，接受比较器和分配器，以及最大高度和分支因子的默认值
  explicit SkipList(Comparator cmp, Allocator* allocator,
                    int32_t max_height = 12, int32_t branching_factor = 4);

}

(4.2.2) 跳表节点

// filepath: memtable/skiplist.h

// 跳表节点
template <typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node {
  explicit Node(const Key& k) : key(k) {}

  // 节点的key
  Key const key;

 private:
  // 下一个节点(们)  每层指向的下一个节点不一样
  // 类似链表的next节点 只不过有多层/多个
  // std::atomic 是原子类型对象，是为了解决并发编程中的线程安全提供的api，类似Java里的
  std::atomic<Node*> next_[1];
};

(4.3) Memtable结构

MemTable是一个内存中的数据结构，用于存储最近写入的键值对。当MemTable达到一定大小时，它将被转换为SSTable并写入磁盘。SSTable是一种静态的、只读的数据结构，它被用作RocksDB的持久化存储。

Rocksdb 支持创建多数据结构类型的 Memtable，默认的是 SkipList，即跳跃表。

参考资料

[1] 后端存储实战课 - 24 | RocksDB：不丢数据的高性能KV存储
[2] An Efficient Design and Implementation of LSM-Tree based Key-Value Store on Open-Channel SSD
[3] 技术贴 | Rocksdb 中 Memtable 源码解析