一种内存数据库存储引擎管理方法_CN113688130B_上海沄熹科技有限公司.pdf
免费下载
(19)国家知识产权局
(12)发明专利
(10)授权公告号
(45)授权公告日
(21)申请号 202110894627 .6
(22)申请日 2021 .08 .05
(65)同一申请的已公布的文献号
申请公布号 CN 113688130 A
(43)申请公布日 2021 .11 .23
(73)专利权人 上海沄熹科技有限公司
地址 200120 上海市浦东新区中国（上海）
自由贸易试验区张东路1158号、丹桂
路1059号2幢305-22室
(72)发明人 张华海
(74)专利代理机构 济南信达专利事务所有限公
司 37100
专利代理师 郗艳荣
(51)Int.Cl .
G06F
16/22
(2019 .01)
G06F
16/2455
(2019 .01)
(56)对比文件
CN 112667644 A ,2021 .04 .16
CN 112269786 A ,2021 .01 .26
CN 108280229 A,2018 .07 .13
CN 105320775 A ,2016 .02 .10
CN 110347336 A ,2019 .10.18
WO 2021085717 A1 ,2021 .05.06
KR 20210052845 A ,2021 .05 .11
谢平.存储系统重复数据删除技术研究综
述 .计算机科学 .2014 ,第41卷(第1期) ,22-30.
审查员 裴希亚
(54)发明名称
一种内存数据库存储引擎管理方法
(57)摘要
本发明特别涉及一种内存数据库存储引擎
管理方法。该内存数据库存储引擎管理方法，基
于RocksDB存储引擎的Memtable管理机制，在
Memtable内部新建ART索引用以取代skiplist索
引，采用ART索引加Hash索引的双索引机制查询
key‑value，优化RocksDB存储引擎的读性能，从
而实现RocksDB内存引擎模式，减少磁盘读写，提
高查询速度。该内存数据库存储引擎管理方法，
优化了现有分布式NewSQL数据库中基于RocksDB
存储引擎的读性能问题，充分发挥了内存的高效
读写性能，能够在内存中缓存更多的数据，解决
了RocksDB的读放大问题。
权利要求书2页 说明书4页 附图1页
CN 113688130 B
2023.10.13
CN 113688130 B
1 .一种内存数据库存储引擎管理方法，其特征在于：基于RocksDB存储引擎的Memtable
管理机制，在Memtable内部新建ART索引用以取代skiplist索引，采用ART索引加Hash索引
的双索引机制查询key‑value；
具体实现过程如下：
1）将插入Memtable的数据转为插入到ART算法管理的内存块中，并将ART算法的叶节点
地址加入Hash索引中；
新建一个ART索引维护类，使用ART算法替换Memtable中的skiplist算法；在ART索引维
护类中新建一个Hash索引类成员HashMap，用于ART索引叶节点的快速查询；
2）修改Memtable刷盘的逻辑，使得Memtable永不转换imMemtable，通过内存块的形式
进行刷盘，内存块通过双向链表进行管理；
启用异步刷盘线程，维护所有内存块的队列，队列按照内存块的上次刷盘时间排序；线
程从队列取内存块，并将内存块增量的key‑value数据进行落盘，追加到文件末尾或形成新
的磁盘SST文件；
3）执行查询操作时，先从Hash表中查询，然后查询ART树，最后查询磁盘SST文件；
调用Memtable::NewIterator接口创建基于ART树的Iterator，用于遍历ART树中的节
点；
新建Memtable::NewHashIterator接口，增加ReadOptions参数，用于判断是否为
MVCCGet读取；如果是则调用NewHashIterator接口，直接从Hash表中查找存储key的双向链
表所对应的叶子节点，如果不是则调用NewIterator接口在hash索引中查找叶子节点，若没
有再去ART索引查询；
最终得到ART树的叶子节点，得到存储多版本key的双向链表，通过遍历双向链表得到
内存块中的数据；
当读取多版本数据即MVCCGet数据时，在Hash表中取出key对应的叶子节点，然后从叶
子节点对应的双向链表中取出对应的key；如果hash索引中没有查到key，说明已经数据已
经落盘，则去磁盘SST文件中查找；
当读取非MVCCGet数据时，则在hash索引中查找对应的叶子节点，若没找到对应的叶子
节点，则在ART树中查找叶子节点，若ART树中没有找到对应的叶子节点，则去磁盘SST文件
中查找。
2.根据权利要求1所述的内存数据库存储引擎管理方法，其特征在于：所述步骤1）中，
写入的数据在内存中以内存块的形式存储，通过双向链表对key进行排序，双向链表的每个
节点内存储当前key对应的多个版本数据形成的链表，双向链表的每个节点指向内存块存
储的该key对应的key‑value；所述ART索引用于快速定位双向链表的特定节点，所述Hash索
引用于快速查询ART树的叶子节点的地址；
写入数据时，首先通过Hash索引与ART索引计算待插入的叶子结点位置，然后根据ART
的叶子节点添加双向链表，通过双向链表对业务key进行排序。
3 .根据权利要求2所述的内存数据库存储引擎管理方法，其特征在于：所述步骤1）中，
当有新的key插入叶子节点时，使用ART算法快速定位到双向链表的插入节点进行插入，同
时增加hash表的插入逻辑，对Hash表加锁；将key的String类型作为Hash表中的key，将叶子
节点指针位置作为Hash表中的value插入到Hash表中。
权 利 要 求 书
1/2 页
2
CN 113688130 B
2
of 8
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论