数据库内核月报

数据库内核月报 - 2017 / 05

RocksDB · 特性介绍 · HashLinkList 内存表

Author: 田汉

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,真正的删除是在数据合并过程中做的。

应用示例

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

$ git diff examples/simple_example.cc
diff --git a/examples/simple_example.cc b/examples/simple_example.cc
index 57d1b25..7b67ff0 100644
--- a/examples/simple_example.cc
+++ b/examples/simple_example.cc
@@ -9,6 +9,7 @@
 #include "rocksdb/db.h"
 #include "rocksdb/slice.h"
 #include "rocksdb/options.h"
+#include "rocksdb/slice_transform.h"
 
 using namespace rocksdb;
 
@@ -17,6 +18,9 @@ std::string kDBPath = "/tmp/rocksdb_simple_example";
 int main() {
   DB* db;
   Options options;
+  options.memtable_factory.reset(NewHashLinkListRepFactory(4, 0, 1, true, 4));
+  options.prefix_extractor.reset(NewFixedPrefixTransform(1));
+  options.allow_concurrent_memtable_write = false;
   // Optimize RocksDB. This is the easiest way to get RocksDB to perform well
   options.IncreaseParallelism();
   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

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

Get

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

Delete

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