RocksDB · 特性介绍 · HashLinkList 内存表

本文涉及的产品
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云原生数据库 PolarDB 分布式版,标准版 2核8GB
云数据库 RDS MySQL Serverless,0.5-2RCU 50GB
简介: Table of Contents1. RocksDB 内存表简介2. HashLinkList 内存表2.1. 应用示例2.2. 实现代码2.2.1. Put2.2.2. Get2.2.3. DeleteRocksDB 内存表简介RocksDB 是一个基于 LSM 树(Log-Structured Merge-tree)结构的单机数据库引擎,内

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 的使用。例如:

$ 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
目录
相关文章
|
1月前
|
存储 算法 编译器
【C++ 内存管理 重载new/delete 运算符 新特性】深入探索C++14 新的/删除的省略(new/delete elision)的原理与应用
【C++ 内存管理 重载new/delete 运算符 新特性】深入探索C++14 新的/删除的省略(new/delete elision)的原理与应用
46 0
|
2月前
|
Rust 安全 开发者
Rust的安全特性概览:守护内存安全与空指针的终结者
Rust作为一种系统级编程语言,以其独特的内存安全特性和对空指针的严格管理,为开发者提供了更加稳健和安全的编程环境。本文将对Rust的内存安全机制、空指针处理策略以及其他安全特性进行概览,旨在展示Rust如何帮助开发者构建更加安全和可靠的软件系统。
|
9月前
|
存储 缓存 SpringCloudAlibaba
JUC并发编程(一):Java内存模型(JMM)及三大特性:可见性、有序性、原子性
在当今高流量、高并发的互联网业务场景下,**并发编程技术**显得尤为重要,不管是哪一门编程语言,掌握并发编程技术是个人进阶的必经之路。时隔一个半月没有写技术博客文章,有点生疏了。。。闲话少叙,接下来我将围绕并发编程知识点进行总结讲解,这里从并发编程入门开始,讲述Java内存模型和并发的三大特性。
118 1
JUC并发编程(一):Java内存模型(JMM)及三大特性:可见性、有序性、原子性
|
7月前
|
缓存 Oracle 关系型数据库
Linux 内存管理新特性 - Memory folios 解读
if (compound_head(page)) // do A; else // do B; folio 并不完美,或许因为大家期望太高,导致少数人对 folio 的最终实现表示失望。但多数人认为 folio 是在正确方向上的重要一步。毕竟后续还有更多工作要实现。
225 0
|
8月前
|
关系型数据库 Linux API
Linux 内存管理新特性:Memory folios 解读
本文主要讲解folio ,极其在应用中的直接价值。
|
9月前
|
SQL
GPDB-内核特性-资源组内存管理机制-2
GPDB-内核特性-资源组内存管理机制-2
54 0
|
9月前
|
SQL 监控 数据库
GPDB-内核特性-资源组内存管理机制-1
GPDB-内核特性-资源组内存管理机制-1
70 0
|
9月前
|
安全 测试技术 Linux
Cloud Kernel SIG 月度动态:支持龙芯和申威架构,合入两个内存新特性
Cloud Kernel SIG 月度动态送达,一键了解 6 月各项目进展。
|
10月前
|
弹性计算 固态存储 数据可视化
阿里云服务器租用优惠价格表(CPU内存/带宽/系统盘)
阿里云服务器租用优惠价格表(CPU内存/带宽/系统盘)2023年阿里云服务器租用费用,轻量应用服务器和云服务器ECS优惠价格表,阿里云轻量应用服务器2核2G3M带宽轻量服务器一年108元,2核4G4M带宽轻量服务器一年297.98元12个月,云服务器ECS包括通用算力型u1、ECS计算型c7、通用型g7和内存型r7均有活动
|
11月前
|
弹性计算 大数据 测试技术
阿里云ECS服务器通用型g7、计算c7和内存r7租用优惠价格表
阿里云ECS服务器通用型g7、计算c7和内存r7租用优惠价格表,CPU内存配置可选2核2G、2核4G、2核8G、2核16G、4核4G、4核8G、4核16G、4核32G、8核8G、8核16G、8核32G、8核64G等配置,云服务器包括轻量应用服务器和云服务器ECS,ECS实例可选通用算力型u1、计算型c7、通用型g7和内存型r7实例