RocksDB · 特性介绍 · HashLinkList 内存表

Table of Contents

  • 1. RocksDB 内存表简介
  • 2. HashLinkList 内存表
    • 2.1. 应用示例
    • 2.2. 实现代码
      • 2.2.1. Put
      • 2.2.2. Get
      • 2.2.3. Delete

RocksDB 内存表简介

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

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

从内存表的基类 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 跳表。代码注释得非常清楚，参看下图：

由于存在上述的一些优化，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
时间： 2024-09-17 04:05:07

RocksDB · 特性介绍 · HashLinkList 内存表的相关文章

MySQL内存表的特性与使用介绍_Mysql

内存表,就是放在内存中的表,所使用内存的大小可通过My.cnf中的max_heap_table_size指定,如max_heap_table_size=1024M,内存表与临时表并不相同,临时表也是存放在内存中,临时表最大所需内存需要通过tmp_table_size = 128M设定.当数据超过临时表的最大值设定时,自动转为磁盘表,此时因需要进行IO操作,性能会大大下降,而内存表不会,内存表满后,会提示数据满错误. 临时表和内存表都可以人工创建,但临时表更多的作用是系统自己创建后,组织数据以提升

MySQL内存表的特性与使用介绍

  国内私募机构九鼎控股打造APP,来就送 20元现金领取地址:http://jdb.jiudingcapital.com/phone.html内部邀请码:C8E245J (不写邀请码,没有现金送)国内私募机构九鼎控股打造,九鼎投资是在全国股份转让系统挂牌的公众公司,股票代码为430719,为"中国PE第一股",市值超1000亿元.        ----------------------------------------------------------------------

SQL server 2014 内存表特性概述

内存优化表是SQL server2014版本中推出的新特性之一.也是基于create table创建的,只不过是驻留在内存中表.从内存读取表中的行和将这些行写入内存. 整个表都驻留在内存中.表数据的另一个副本维护在磁盘上,但仅用于持续性目的.内存中 OLTP 与 SQL Server 集成,以便在所有方面(如开发.部署.可管理性和可支持性)提供无缝体验. 内存优化表中的行是版本化的. 这意味着表中的每行都可能有多个版本. 所有行版本均维护在同一个表数据结构中. 本文主要描述SQL server

AliSQL · 特性介绍 · 支持 Invisible Indexes

前言 MySQL 8.0 引入了 Invisible Indexes 这一个特性,对于 DBA 同学来说是一大福音,索引生命周期管理除了有和无外,又多了一种形态–可见和不可见,进而对业务SQL的调优又多了一种手段. 关于 Invisible Indexes,不管是官方还是第三方,都有非常多的介绍文档,这里推荐大家可以先看下: 官方文档: Invisible Indexes 官方 server 层团队博客: MySQL 8.0: Invisible Indexes 官方 worklog: WL#8

SQL Server 优化器特性导致的内存授予相关BUG

原文:SQL Server 优化器特性导致的内存授予相关BUG 我们有时会遇到一些坑,要不填平,要不绕过.这里为大家介绍一个相关SQL Server优化器方面的特性导致内存授予的相关BUG,及相关解决方式,也顺便回答下邹建同学的相关疑问.   问题描述 一个简单的查询消耗了匪夷所思的内存.(邹建同学发现的) 原文链接 Code create table test_mem ( id int identity(1,1) primary key, itemid int not null, date d

SQL Server在AlwaysOn中使用内存表的“踩坑”记录

前言 最近因为线上alwayson环境的一个数据库上使用内存表.经过大概一个星期监控程序发现了一个非常严重问题这个数据库的日志文件不会截断,已用空间一直在增加(存在定时的每个小时的日志备份),同时内存表数据库文件也无法删除,下面就介绍一下后面我的处理过程,话不多说了,来一起看看详细的介绍吧. 数据库:SQL Server2014 Enterprise Edition (64-bit) 删除文件 使用一个单独非alwayson环境的数据库测试. 一.创建内存表 ---创建内存表文件组 ALTER

【转载】MySQL 之临时表和内存表

      今天(2013-10-17)又看了一篇很久以前的博客文章,题目是< How to eliminate temporary tables in MySQL >,里面的一些观点和结论摘录如下:  to make statement-based replication reliable is eliminate temporary tables. true temporary tables are created with CREATE TEMPORARY TABLE, and inte

MySQL的内存表的基础学习教程_C 语言

内存表,就是放在内存中的表,所使用内存的大小可通过My.cnf中的max_heap_table_size指定,如max_heap_table_size=1024M,内存表与临时表并不相同,临时表也是存放在内存中,临时表最大所需内存需要通过tmp_table_size = 128M设定.当数据超过临时表的最大值设定时,自动转为磁盘表,此时因需要进行IO操作,性能会大大下降,而内存表不会,内存表满后,会提示数据满错误. 临时表和内存表都可以人工创建,但临时表更多的作用是系统自己创建后,组织数据以提升

**关于mysql5.7版本新特性介绍 ------数据类型 JSON**

关于mysql5.7版本新特性介绍 ------数据类型 JSON 测试环境: Win10.mysql 5.7.14 内容简介:随着mysql5.7版本的到来,大家对其的热情也越来越高涨,身为mysql圈子里的一员,我本身也对mysql5.7的一些新特性有所了解,通过学习了解到了很多新的特性,今天给大家介绍一下它在灵活性方面的一个新的功能:提供对JSON的支持 JSON介绍 首先介绍一下什么是JSON: > JSON(JavaScript Object Notation, JS 对象标记) 是一