Table of Contents

RocksDB 内存表简介

RocksDB 是一个基于 LSM 树（Log-Structured Merge-tree）结构的单机数据库引擎，内存表是它最重要的数据结构之一。除了默认的跳表（SkipList）之外，它还增加了各种其他的内存表，例如：HashSkipList、HashLinkList、Vector 等。HashSkipList 是在跳表外套了一层 Hash，每个桶对应了一个跳表。类似的，HashLinkList 是在链表外套了一层 Hash，每个桶对应了一个链表。这两种内存表都需要配置 prefix_extractor，以计算 hash 值。RocksDB 支持的内存表类型见下图：

RocksDB 内存表

为了方便使用，内存表有对应的工厂类 MemTableRepFactory。与内存表类型对应，完整的内存表工厂类的继承关系如下图：

RocksDB 内存表工厂类

从内存表的基类 MemTableRep 中可以看到，它支持的 API 有 Get、Insert 等，但是没有 Delete。这是因为 Delete 被上层转换成了一个 Insert，真正的删除是在数据合并过程中做的。

HashLinkList 内存表

应用示例

相比 HashSkipList 而言，HashLinkList 要更简洁/简单一些，也可以节约内存的占用。它的缺点是不支持并发的写入。为了测试各种内存表的表现，RocksDB 提供了一个简单的测试工具，参看：memtablerep_bench.cc。我们也可以在示例代码 examples/simple_example.cc 中修改一下来验证 HashLinkList 的使用。例如：

  1. $ git diff examples/simple_example.cc
  2. diff --git a/examples/simple_example.cc b/examples/simple_example.cc
  3. index 57d1b25..7b67ff0 100644
  4. --- a/examples/simple_example.cc
  5. +++ b/examples/simple_example.cc
  6. @@ -9,6 +9,7 @@
  7.  #include "rocksdb/db.h"
  8.  #include "rocksdb/slice.h"
  9.  #include "rocksdb/options.h"
  10. +#include "rocksdb/slice_transform.h"
  12.  using namespace rocksdb;
  14. @@ -17,6 +18,9 @@ std::string kDBPath = "/tmp/rocksdb_simple_example";
  15.  int main() {
  16.    DB* db;
  17.    Options options;
  18. +  options.memtable_factory.reset(NewHashLinkListRepFactory(4, 0, 1, true, 4));
  19. +  options.prefix_extractor.reset(NewFixedPrefixTransform(1));
  20. +  options.allow_concurrent_memtable_write = false;
  21.    // Optimize RocksDB. This is the easiest way to get RocksDB to perform well
  22.    options.IncreaseParallelism();
  23.    options.OptimizeLevelStyleCompaction();

需要注意的几个地方：

  1. options.memtable_factory.reset() 是将默认的 SkipList 替换为我们要测试的 HashLinkList。
  2. options.prefix_extractor.reset() 是设置 Hash 需要的 prefix_extractor，如果不设置，默认用的还会是 SkipList。
  3. options.allow_concurrent_memtable_write = false 是因为 HashLinkList 不支持并发写入，不设置运行时会报错。
  4. 数据存放在 /tmp/rocksdb_simple_example，如果数据目录已经存在，则会打开已经存在的数据库。

实现代码

HashLinkList 的代码存在以下两个文件中：memtable/hash_linklist_rep.h 以及 memtable/hash_linklist_rep.cc。可以看到它做了一些细节的优化，从简单的 Hash 链表逐步演化到 Hash 跳表。代码注释得非常清楚，参看下图：

HashLinkListDataStructure

由于存在上述的一些优化，Hash 表在不同时刻会存在不同的形式。

  1. 第一种情况最简单，也就是桶为空。不占用额外内存空间。
  2. 第二种情况下，桶里头只有一条记录，存在链表第一个节点中。Next 指针占用额外空间。Next 指针取值为 NULL。后续其他情况下 Next 指针都不是 NULL，可以依赖这一点来区分不同的场景。
  3. 第三种情况下，桶里头的记录多余一条，链表的第一个节点是个表头，记录链表中的记录数。记录数是为了判断链表是否应该转换为跳表而设的。额外空间包括这个表头节点以及每个节点中的 Next 指针。
  4. 第四种情况下，桶里头的记录数超过了设定的阈值（threshold_use_skiplist），链表被转换为一个跳表。链表的第一个节点的 Next 指针指向自己。Count 继续保留，可以用来做测试等。

如果 HashLinkList 要支持并发写，就需要对数据结构做适当的控制。不过当前它并不支持并发写，而是单写多读。它实现时采用了 C++ 11 的 Atomic 做一些特殊的处理避免加锁。另外需要注意的是，这个 Iterator 的实现 MemTableRep::Iterator* HashLinkListRep::GetIterator() 比较费资源，它会 new 一个 MemtableSkipList，把记录都遍历出来并插入进去。

采用修改后的 simple_example.cc，可以看到插入、查找、删除所对应的执行路径，用来理解代码的主要执行流程。

Put

  1. (gdb) bt
  2. #0  rocksdb::(anonymous namespace)::HashLinkListRep::Insert (this=0xcd2af0, handle=0xcf3250) at memtable/hash_linklist_rep.cc:580
  3. #1  0x000000000044af7f in rocksdb::MemTable::Add (this=0xcf3000, s=1, type=rocksdb::kTypeValue, key=..., value=..., allow_concurrent=false, post_process_info=0x0) at db/memtable.cc:452
  4. #2  0x00000000004a9850 in rocksdb::MemTableInserter::PutCF (this=0x7fffffffb550, column_family_id=0, key=..., value=...) at db/write_batch.cc:944
  5. #3  0x00000000004a422e in rocksdb::WriteBatch::Iterate (this=0x7fffffffbb60, handler=0x7fffffffb550) at db/write_batch.cc:386
  6. #4  0x00000000004a61f1 in rocksdb::WriteBatchInternal::InsertInto (writers=..., sequence=1, memtables=0xceb780, flush_scheduler=0xcf0780, ignore_missing_column_families=false, recovery_log_number=0, 
  7.     db=0xcf0000, concurrent_memtable_writes=false) at db/write_batch.cc:1294
  8. #5  0x0000000000609f2e in rocksdb::DBImpl::WriteImpl (this=0xcf0000, write_options=..., my_batch=0x7fffffffbb60, callback=0x0, log_used=0x0, log_ref=0, disable_memtable=false)
  9.     at db/db_impl_write.cc:215
  10. #6  0x00000000006093c2 in rocksdb::DBImpl::Write (this=0xcf0000, write_options=..., my_batch=0x7fffffffbb60) at db/db_impl_write.cc:48
  11. #7  0x000000000060ca99 in rocksdb::DB::Put (this=0xcf0000, opt=..., column_family=0xcce9e0, key=..., value=...) at db/db_impl_write.cc:794
  12. #8  0x0000000000609240 in rocksdb::DBImpl::Put (this=0xcf0000, o=..., column_family=0xcce9e0, key=..., val=...) at db/db_impl_write.cc:23
  13. #9  0x00000000005f7ee7 in rocksdb::DB::Put (this=0xcf0000, options=..., key=..., value=...) at ./include/rocksdb/db.h:201
  14. #10 0x00000000004082a0 in main () at simple_example.cc:40

Get

  1. (gdb) bt
  2. #0  rocksdb::(anonymous namespace)::HashLinkListRep::Get (this=0xcd2af0, k=..., callback_args=0x7fffffffb750, callback_func=0x44b82c <rocksdb::SaveValue(void*, char const*)>)
  3.     at memtable/hash_linklist_rep.cc:727
  4. #1  0x000000000044c1fc in rocksdb::MemTable::Get (this=0xcf3000, key=..., value=0x7fffffffc020, s=0x7fffffffc090, merge_context=0x7fffffffba60, range_del_agg=0x7fffffffb910, seq=0x7fffffffb898, 
  5.     read_opts=...) at db/memtable.cc:678
  6. #2  0x00000000005f9800 in rocksdb::MemTable::Get (this=0xcf3000, key=..., value=0x7fffffffc020, s=0x7fffffffc090, merge_context=0x7fffffffba60, range_del_agg=0x7fffffffb910, read_opts=...)
  7.     at ./db/memtable.h:196
  8. #3  0x00000000005e667a in rocksdb::DBImpl::GetImpl (this=0xcf0000, read_options=..., column_family=0xcce9e0, key=..., pinnable_val=0x7fffffffbba0, value_found=0x0) at db/db_impl.cc:959
  9. #4  0x00000000005e6296 in rocksdb::DBImpl::Get (this=0xcf0000, read_options=..., column_family=0xcce9e0, key=..., value=0x7fffffffbba0) at db/db_impl.cc:905
  10. #5  0x00000000005f811f in rocksdb::DB::Get (this=0xcf0000, options=..., column_family=0xcce9e0, key=..., value=0x7fffffffc020) at ./include/rocksdb/db.h:289
  11. #6  0x00000000005f8233 in rocksdb::DB::Get (this=0xcf0000, options=..., key=..., value=0x7fffffffc020) at ./include/rocksdb/db.h:299
  12. #7  0x0000000000408364 in main () at simple_example.cc:44

Delete

  1. (gdb) bt
  2. #0  rocksdb::(anonymous namespace)::HashLinkListRep::Insert (this=0xcd2af0, handle=0xcf3278) at memtable/hash_linklist_rep.cc:580
  3. #1  0x000000000044af7f in rocksdb::MemTable::Add (this=0xcf3000, s=2, type=rocksdb::kTypeDeletion, key=..., value=..., allow_concurrent=false, post_process_info=0x0) at db/memtable.cc:452
  4. #2  0x00000000004a9d9e in rocksdb::MemTableInserter::DeleteImpl (this=0x7fffffffb680, column_family_id=0, key=..., value=..., delete_type=rocksdb::kTypeDeletion) at db/write_batch.cc:999
  5. #3  0x00000000004a9eb8 in rocksdb::MemTableInserter::DeleteCF (this=0x7fffffffb680, column_family_id=0, key=...) at db/write_batch.cc:1018
  6. #4  0x00000000004a42db in rocksdb::WriteBatch::Iterate (this=0x7fffffffbc60, handler=0x7fffffffb680) at db/write_batch.cc:393
  7. #5  0x00000000004a61f1 in rocksdb::WriteBatchInternal::InsertInto (writers=..., sequence=2, memtables=0xceb780, flush_scheduler=0xcf0780, ignore_missing_column_families=false, recovery_log_number=0, 
  8.     db=0xcf0000, concurrent_memtable_writes=false) at db/write_batch.cc:1294
  9. #6  0x0000000000609f2e in rocksdb::DBImpl::WriteImpl (this=0xcf0000, write_options=..., my_batch=0x7fffffffbc60, callback=0x0, log_used=0x0, log_ref=0, disable_memtable=false)
  10.     at db/db_impl_write.cc:215
  11. #7  0x00000000006093c2 in rocksdb::DBImpl::Write (this=0xcf0000, write_options=..., my_batch=0x7fffffffbc60) at db/db_impl_write.cc:48
  12. #8  0x0000000000408480 in main () at simple_example.cc:53