手摸手学习 RocksDB 的 MemTable

❝

本文翻译自 RocksDB 官方 Wiki《MemTable》：https://github.com/facebook/rocksdb/wiki/MemTable

翻译者：fanrui

本文分为以下几部分：

1、 结论
2、 MemTable 介绍
3、 SkipList MemTable 介绍
4、 HashSkipList MemTable 介绍
5、 Flush
6、 并发插入
7、 MemTable 多种实现类的比较

❞

1、结论

1.1 MemTable 介绍

1. 写数据流程：先写 MemTable，写满后当前的 MemTable 变成不可变的，再生成一个新的 MemTable。后台异步线程将会 flush 不可变的 MemTable 生成 SST 文件。
2. 读数据流程：先读 MemTable，再读 SST 文件。
3. 影响 MemTable 的参数：MemTable 的工厂对象、单个 MemTable 的大小、所有 Column Family 的 MemTable 总大小、Write Buffer Manager、内存中 MemTable 的最大数量、写历史数据保存在内存中的数量。

1.2 MemTable 的实现类

1. MemTable 的默认实现是 SkipList，其他实现类有：HashLinkList、HashSkipList 或 Vector。
2. 基于 SkipList 的 MemTable 可以为读、写、随机访问和顺序 Scan 提供良好的性能。此外还提供了并发插入 和带 Hint 插入。
3. HashSkiplist 将数据组织为一个 Hash 表，每个 Hash 桶内部是排好序的链表。当查询和插入 key 时，先定位到具体的桶，桶内按照 SkipList 的方式查找。局限性：对于多个前缀进行 Scan 操作时需要 copy 和排序，非常慢且内存成本较高。

1.3 Flush

有多个条件会触发内存 flush，单个 MemTable 超过设定大小、总的 MemTable 超过设定大小、write_buffer_manager
发送 flush 信号（这两种情况 flush 最大的 MemTable）以及 WAL 文件超过设置大小（该情况 flush 最老的 MemTable）。

MemTable 可以在写满之前被 flush，且 SST 文件对数据有压缩，MemTable 中的数据是未压缩的。所以生成的 SST 文件可以比相应的 MemTable 小。

1.4 MemTable 多种实现类的比较

从适用场景、索引类型、是否支持完整的数据库 Scan、内存开销、Flush 效率及开销、并发插入、带 Hint 插入几个维度分析了四种 MemTable 的实现类的区分，具体参考下文。

分割线，以上是译者的总结，以下对译文的完整翻译。

2、 MemTable 介绍

MemTable 是 RocksDB 内存中的数据结构，数据 flush 到 SST 文件之前将会保存在 MemTable 中。MemTable 既支持读又支持写：新写入的数据会插入到 MemTable 中，读数据时先查询 MemTable 再读取 SST 文件，因为 MemTable 中的数据比 SST 中的数据更新。一旦一个 MemTable 写满，将会变成不可变的 MemTable ，并被一个新的 MemTable 替换。一个后台线程将会 flush 不可变 MemTable 中的数据到 SST 文件中，flush 完毕后，不可变的 MemTable 将会被销毁。

影响 MemTable 最重要的参数如下所示：

• memtable_factory
  ：MemTable 的工厂对象。通过指定工厂对象，用户可以更改 MemTable 的基础实现，并提供特定的配置选项。
• write_buffer_size
  ：单个 MemTable 的大小。
• db_write_buffer_size
  ：所有 Column Family 的 MemTable 总大小。该参数可以管理 MemTable 使用的总内存。
• write_buffer_manager
  ：用户可以实现自己的 Write Buffer Manager 来控制所有 MemTable 的内存使用，而不用指定 MemTable 的总大小。该参数将会覆盖 db_write_buffer_size
  参数。
• max_write_buffer_number
  ：flush 到 SST 文件之前，内存中 MemTable 的最大数量。
• max_write_buffer_size_to_maintain
  ：写历史数据保存在内存中的数量（单位是 byte）。包括当前的 MemTable、不可变的 MemTable 以及已经 flush 完毕但还未删除的 MemTable。RocksDB 将会尽量保持内存中有这么多的数据。如果删除一个已经 flush 的 MemTable 将会导致历史数据占用的内存空间低于设定的阈值，那么 RocksDB 将不会删除这个 MemTable。（译者注：该参数配置较大时，内存中将会保留更多的 MemTable，从而减少 SST 文件的访问，提高 RocksDB 的读取性能）

MemTable 的默认实现是 skiplist。除了 MemTable 的默认实现之外，用户可以使用其他类型的 MemTable 实现来加快一些查询的速度，例如：HashLinkList、HashSkipList 或 Vector。

3、 SkipList MemTable 介绍

基于 SkipList 的 MemTable 可以为读、写、随机访问和顺序 Scan 提供良好的性能。此外，它提供了一些其他有用的功能，例如：并发插入 和 带 Hint 插入。

4、 HashSkiplist MemTable 介绍

顾名思义，HashSkiplist 将数据组织为一个 Hash 表，每个 Hash 桶内部是排好序的链表。建立这两种类型是为了减少执行查询时的比较次数。一个很好的用例是将他们与 PlainTable SST 格式结合使用，然后将数据存储在 RAMFS 中。

当查询和插入一个 key 时，使用 Options.prefix_extractor
检索目标 key 的前缀，该前缀用于查找对应的 hash 桶。在 hash 桶内部，所有的比较都是使用整个（内部） key 完成的，就像基于 SkipList 的 MemTable 一样。

基于 Hash 表的 MemTable 最大的局限性是：对于多个前缀进行 Scan 操作时需要 copy 和排序，非常慢且内存成本较高。

5、 Flush

三种场景会触发内存的 flush：

1. 写操作后，MemTable 大小超过 write_buffer_size
   
2. 所有 Column Family 的 MemTable 大小总和超过了 db_write_buffer_size
   或  write_buffer_manager
   发送了一个 flush 信号。在这种场景下，最大的 MemTable 将会被 flush。
3. WAL 文件的总大小超过了 max_total_wal_size
   。在这种场景下，最老的 MemTable 将会被 flush，这样就可以清除该 MemTable 对应的 WAL 文件。

MemTable 可以在写满之前被 flush，这就是为什么生成的 SST 文件可以比相应的 MemTable 小。压缩是 SST 文件比相应 MemTable 小的另一个因素，因为 MemTable 中的数据是未压缩的。

6、并发插入

如果 MemTable 不支持并发写，那么多线程对 RocksDB 的并发写将顺序地应用于 MemTable。默认情况下 MemTable 的并发写是开启的，并且可以通过 allow_concurrent_memtable_write
参数关闭。虽然只有基于 SkipList 的 MemTable 支持这个功能。

带 Hint 插入

原地更新

7、 MemTable 多种实现类的比较

8、 总结

请参考本文第一部分的结论。