可以看到，内存引擎通过原有的Foreign Data Wrapper（外部数据封装器）扩展能力与openGauss的优化执行流程相交互，通过事务机制的回调以及与openGauss相兼容的WAL机制，保证了与其他存储引擎在这一体系架构内的共存，保证了整体对外的一致表现；同时通过维护内部的内存管理结构、无锁化索引、乐观事务机制来为系统提供极致的事务吞吐能力。

以下将逐步展开讲解相关关键技术点与设计。

内存引擎的兼容性设计

由于数据形态的不同以及底层事务机制的差别，此处如何与一个以段页式为基础的系统对接是内存引擎存在于openGauss中的重点问题之一。

此处openGauss原有的FDW（Foreign Data Wrapper）机制为内存引擎提供了一个很好的对接接口，优化器可以通过FDW来获取内存引擎内部的元信息，内存引擎的内存计算处理机制可以直接通过FDW的执行器接口算子实现直接调起、并通过相同的结构将结果以符合执行器预期的方式（比如Scan（扫描）操作的pipelining（流水线））将结果反馈回执行器进行进一步处理后（如排序、Group by（分组））返回给客户端应用。

与此同时内存引擎自身的Error Handling（错误处理机制），也可以通过与FDW的交互，提交给上次系统，以此同步触发上层逻辑的相应错误处理（如回滚事务、线程退出等）。

内存引擎借助FDW的方式接近无缝的工作在整个系统架构下，与以磁盘为基础的行列存储引擎实现共存。

在内存引擎中Create Table（创建表）的实际操作流程如图38所示。

图38 内存引擎操作流程图

可以看到FDW充当了一个整体交互API的作用。实现中同时扩展了FDW的机制，使得其具有更完备的交互功能，包括：

(1) 支持DDL接口；

(2) 完整的事务生命周期对接；

(3) 支持checkpoint（检查点）；

(4) 支持持久化WAL；

(5) 支持故障恢复（Redo）；

(6) 支持Vacuum（垃圾清理回收）。

借由FDW机制，内存引擎可以作为一个与原有openGauss代码框架异构的存储引擎存在于整个体系中。

内存引擎索引

内存引擎的索引结构以及整体的数据组织都是基于Masstree实现的。主体如图39所示。

图39 内存引擎主体结构

在前序文章【如何掌握openGauss数据库核心技术？秘诀三：拿捏存储技术（2）】中的图15，很好地呈现了内存引擎的组织架构。

图15 MVCC判断流程

Primary Index（主键索引）在内存引擎的一个表中是必须存在的要素，因此要求表在组织时尽量存在primary index；如果不存在，内存引擎也会额外生成surrogate key（代理键）来用于生成Primary index。Primary Index指向各个代表各个行记录的Sentinel（行指针），由Sentinel来对行记录数据进行内存地址的记录以及引用。Secondary Index（二级索引）索引后指向一对键值，键值的value（值）部分为到对应数据Sentinel的指针。

Masstree作为Concurrent B+ tree（并行B+树），集成了大量B+树的优化策略，并在此基础上做了进一步的改良和优化。其大致实现如图40所示。

图40 Masstree实现方式

Masstree实现比于传统的B-tree，Masstree实际上是一个类似于诸多B+-树以trie（前缀树）的组织形式堆叠的Radix tree（基数树）模式，以Key（键）的前缀作为索引，每k个字节形成一层B+-树结构，在每层中处理Key（键）中这k个字节对应所需的insert/lookup/update/delete流程。图41为k=8时情况。

图41 k等于8时的Masstree

注：图来自于“Cache craftiness for fast multicore key-value storage” , Eddie Kohler et. al.

Masstree中的读操作使用了类OCC（Optimistic Concurrency Control，乐观并发控制）的实现，而所有的update（更新）锁仅为本地锁。在树的结构上，每层的interior node（内部节点）和leaf node（叶子节点）都会带有版本，因此可以借助version validation（版本检查）来避免fine-grained lock（细粒度锁）的使用。

Masstree除了lockless（无锁化）之外，最大的亮点是cache line（缓存块）的高效利用。Lockless本身一定程度避免了lookup/insert/update操作互相invalidate共享cache line（失效共享缓存块）的情况。而基于prefix（前缀）的分层，辅以合适的每层中B+-树fanout（扇出）的设置，可以最大程度的利用CPU prefetch（预取）的结果（尤其是在树的深度遍历过程中），减少了与DRAM交互带来的额外时延。

Prefetch（预取）在Masstree的设计中显得尤为关键，尤其是在Masstree从tree root（树根节点）向leaf node（叶子节点）遍历、也就是树的下降过程中。此过程中的执行时延大部分由于内存交互的时延组成，因此prefetch（预取）可以有效地提高masstree traverse（遍历）操作的执行效率以及cache line（缓存块）的使用效率（命中）。

未完待续......

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除

数据库