openGauss数据库源码解析系列文章——存储引擎源码解析（六）

上一篇详细讲述了“4.2.5 行存储索引机制”、“4.2.6 行存储缓存机制”及“4.2.7 cstore”等精彩内容。本篇我们详细讲述“4.3 内存表”相关内容。

4.3 内存表

MOT（memory-optimized tables，内存表）是事务性、基于行存储的存储引擎，针对众核和大内存服务器进行了优化。MOT是openGauss数据库的一个先进特性，可提供非常高的事务性工作负载性能。MOT完全符合ACID要求，并支持严格的持久性和高可用性。企业用户可以将MOT用于关键任务、性能敏感的在线事务处理应用程序，以实现高性能、高吞吐量、低且可预测的延迟，并提升众核服务器的利用率。

4.3.1 总体架构和代码概述

MOT引擎架构概述如4-43所示。

图4-43 MOT总体架构

MOT的关键技术包括下面几个内容。
（1） 面向内存优化的数据结构。
（2） 乐观并发控制。
（3） 无锁索引。
（4） NUMA感知技术，事务性本地内存。
（5） 即时编译（Just-In-Time，JIT）。
总体而言，MOT的目标是建立一个在众核CPU架构中表现出色的OLTP系统，特别是性能可以随核数增加而线性扩展。根据经验实验，Masstree无锁实现和针对Silo（请参阅错误!未找到引用源。）的改进是最佳组合。
索引方面，通过比较各种先进解决方案后选择了Masstree，因为它在点查询、迭代等方面表现出最佳的整体性能。Masstree是Trie和B+树的组合，实现了对缓存、预取和细粒度锁的高效利用。它针对锁冲突严重的情况进行了优化，并在其他先进索引的基础上增加了各种优化。Masstree索引的缺点是内存消耗较大，虽然每行数据消耗的内存大小相同，但是每行每个索引（主索引或次索引）的内存平均高出16个字节：在磁盘表使用的基于锁的B树中为29个字节，而MOT的Masstree为45个字节。
并发控制算法方面，为了从内存架构中获得优势，设计考虑上最大限度地提高OLTP事务处理速度。虽然最近有一些内存多版本并发控制方面的改进，但为了避免迅速的垃圾收集，MOT只维护实际数据。MOT的另一个设计选择是不像HStore那样对数据进行分区，因为在实际的工作负载中事务跨区时性能会急剧下降。尽管已出现一些新的方法通过静态和动态分析来调整并行性，但此类方法会增加时延，并引入额外限制。
内存存储引擎常用的单版本、shared-everything类型的并发控制算法主要分为三类。

1. 乐观并发控制（Optimistic Concurrency Control，OCC），乐观并发控制有三个阶段。
   1. 读取阶段，从共享内存中读取事务记录，并将所有记录写入本地的私有副本。
   2. 验证阶段，执行一系列事务检查以确保一致性。
   3. 写阶段，验证成功后，提交该事务；验证失败时将中止该事务，不会提交。两个OCC事务同时执行时不会互相等待。
2. 遭遇时间锁定（encounter time locking，ETL）。在ETL中，读取者是乐观的，但写入者会锁定待访问的数据。因此，来自不同ETL事务的写入者会互相看到，并可据此决定是否中止事务。ETL在两个方面提高了OCC的性能。首先，ETL能尽早发现冲突，而事务处理是有代价的，因为在提交时发现的冲突，需要中止至少一个事务，因此ETL可以在冲突情况下提高事务吞吐量。其次，ETL能够高效地处理写后读（reads-after-writes，RAW）。
3. 悲观的并发控制（以2PL为例）。在读取或写入时锁定一行，提交后释放锁。这些算法需要一些避免死锁的方法。死锁可以通过周期性的计算等待图（wait-for graph）来检测，也可以通过保持TSO（total store ordering）中的时间顺序或一些其他的规避方案来避免。在2PL算法中，如果一个事务正在写一行数据，其他事务就不能访问或写入该行数据，如果正在读一行数据，则不允许任何事务写该行数据，但可以读取这行数据。
   对于大多数工作负载而言，OCC是最快的选择。原因之一是当CPU执行多个交互线程时，一个锁很可能被一个切换出去的线程持有。另外一个原因是悲观的算法涉及死锁检测，这会增大开销，同时读写锁比标准的自旋锁效率低。Silo来自Stephen Tu等人在计算机顶级会议SOSP13上发表的《Speedy Transactions in Multicore In-Memory Databases》，可以在现代众核服务器上实现卓越的性能和可扩展性。MOT最终选择了Silo，因为它比其他现有的方案，如TicToc更简单，同时在大多数工作负载下可保持很高的性能。ETL虽然有时比OCC快，但可能会触发不必要的中止退出。相比之下，OCC只在提交时实际发生冲突时中止退出。
   目前，与业界其他领先的内存数据库理系统类似，MOT表的数据容量被限制在最大可用内存范围内。通过操作系统的内存页面交换技术可以扩展内存范围，但在这种情况下性能可能会下降。观察近年来业界出现了几种技术来缓解这个问题，包括数据重组、反缓存和分层等，这也是MOT未来的工作方向之一。
   与磁盘引擎（包括共享内存等磁盘数据库的内存优化技术）相比，设计内存引擎的挑战主要是避免磁盘引擎那样基于页面的间接访问方式。
   MOT存储引擎代码位于src/gausskernel/storage/mot目录下。目录结构如下。

src/gausskernel/storage/mot/
├── core
├── fdw_adapter
└── jit_exec

MOT文件夹下有三个顶层子目录。
（1） core：包含MOT引擎的核心模块，如并发控制、事务管理、内存管理、存储、检查点、重做、恢复、事务、基础设施组件、统计、实用程序等。
（2） fdw_adapter：包含FDW适配器接口和实现。
（3） jit_exec：包含MOT JIT（Just-In-Time）组件。它有两种实现，一种使用本地LLVM（low level virtual machine），另一种使用TVM（tiny virtual machine），可以在不提供本地LLVM支持的计算机上使用。

4.3.2 FDW

openGauss使用FDW API与内存引擎进行对接。实现上分为两个层次。
（1） 消费者层——FDW API的实现，它由提供数据管理和操作的静态函数组成。这些函数通过fdwapi.h中的FdwRoutine结构以回调的形式暴露给上层。
（2） 通信层——连接openGauss其他部分和MOT内部API。这包括数据和数据定义转换和对MOT内部表示的调整。

1. 消费者层

MOT消费者层FDW API的功能和用途如表4-35所示。其中，计划、执行阶段请参考《SELECT/UPDATE/DELETE（计划阶段）》以及《SELECT/UPDATE/DELETE（执行阶段）》两小节。

表4-35 MOT消费者层FDW接口简介

 

函数名	使用阶段（数字为调用顺序）	描述
GetForeignRelSize	计划1	查询过程中表的每个实例均调用，以评估大小
GetForeignPaths	计划2	有索引情况下调用，确定哪些索引可用于从当前查询中的表中获取数据
GetForeignPlan	计划3	创建用于从表中取数据的执行计划
PlanForeignModify	计划4	在数据修改查询时调用。设置数据修改的附加信息
AddForeignUpdateTargets	计划5	向查询输出添加其他结果列
BeginForeignScan	执行1	在数据提取开始时，对查询中的每个表实例调用
BeginForeignModify	执行1.1	修改查询
IterateForeignScan	执行2	调用以获取相应的记录
ReScanForeignScan	执行3	应重新启动迭代时调用
EndForeignScan	执行4	调用以完成取数据
EndForeignModify	执行4.1	在通过修改查询启动数据扫描时调用
ExecForeignInsert	执行过程	满足其他条件时调用以完成记录插入
ExecForeignUpdate	执行过程	满足其他条件时调用以完成记录修改
ExecForeignDelete	执行过程	满足其他条件时调用以完成删除记录
ExplainForeignScan	输出计划	执行explain时调用以打印详细计划信息
AnalyzeForeignTable	分析1	对表做analyze操作
AcquireSampleRows	分析2	收集采样信息用来做analyze操作
TruncateForeignTable	截断	调用以清空表数据
VacuumForeignTable	垃圾回收	清理表
NotifyForeignConfigChange	配置	在数据库配置更改事件中调用
ValidateTableDef	DDL	查询数据定义时调用
IsForeignRelUpdatable	信息	调用以确定FDW支持的操作（SELECT/INSERT/UPDATE/DELETE）
GetFdwType	信息	提供FDW类型
GetForeignMemSize	统计信息	以字节为单位提供MOT引擎的内存使用情况
GetForeignRelationMemSize	统计信息	以字节为单位提供存储表/索引数据的内存使用情况

2. 主要流程时序图

请注意，为了便于读者更好的理解正常流程和异常流程的关系，本节中的时序图均将正常流程和异常流程放在同一张图中，其中P1、P2……Pn为异常流程。同时，为简化时序图帮助理解流程，异常流程仅在异常发生的位置进行标识，未完整绘制异常流程的时序。

1） CREATE表

图4-44 CREATE表时序图

用户创建一个新的内存表时，openGauss通过FDW适配器将请求转发给MOT存储引擎。创建表的正常流程和主要异常流程如图4-44所示。
正常事件流：FDW创建一个新的表对象。然后对每个列执行以下操作。
（1） FDW验证列定义。
（2） MOT引擎进一步验证列定义。
（3） 创建给定类型的列对象并将其添加到表中。
（4） 对所有列定义重复此过程。
添加完所有列后表定义本身就被验证，表对象已添加到MOT引擎，并通过锁保护，最后，由于表还没有索引，所以会向表中添加一个伪主索引/键。DDL命令会持久化到重做日志中。
P1：在此异常事件流中，列定义失败时FDW通过ereport函数向openGauss报告无效列定义（invalid column definition）错误。
P2：在此异常事件流中，由于以下原因之一，导致表的列定义验证失败：①不支持的列类型；②字段大小无效；③资源限制：已超过允许的表最大列数；④资源限制：列的总大小已超过最大元组大小；⑤资源限制：列名大小超过允许的最大值。
P3：在此异常事件流中，由于以下原因之一，导致表的列定义验证失败：①资源限制：超出每个表的最大列数；②资源限制：列的总大小超过最大元组大小；③资源限制：列名大小超过允许的最大值。
P4：总元组大小超过了允许的最大元组大小。

2） DELETE表

图4-45 DELETE表时序图

如图4-45所示，用户DELETE内存表时，openGauss通过FDW适配器将请求转发给MOT存储引擎。
正常事件流：FDW从MOT引擎中检索表对象，并将DELETE表的请求转发给MOT引擎。DDL命令在重做日志中持久化，然后对于表中的每个索引，索引数据将被截断并DELETE索引对象。随后对表中的每个索引重复此过程。在DELETE所有索引对象之后，MOT将DELETE表对象并返回给FDW。
P1：在此异常事件流中，没有找到索引所属的表。此错误条件被静默忽略，FDW不会向openGauss报告错误。
P2：在此异常事件流中，在表对象中找不到请求的二级索引。此错误条件被静默忽略，FDW不会向openGauss报告错误。

3） CREATE索引

图4-46 CREATE索引时序图

如图4-46所示，用户希望在现有的内存表中创建新索引时，openGauss通过FDW适配器将请求转发给MOT存储引擎。
正常事件流：FDW从MOT引擎中检索表对象并创建一个索引对象。然后，对每个列执行以下操作：①FDW验证列大小；②FDW验证列类型。对所有列定义重复此过程。验证所有列之后，生成的键大小也会被验证。在创建主索引时，原创建表阶段时添加的伪主索引将被新的主索引替换，应当在表仍然为空时完成。否则，将向表添加二级索引。索引数据本身是由主索引数据创建的。最后，整个DDL命令将持久化到重做日志。
P1：在此异常事件流中，不支持索引类型，FDW通过ereport工具向openGauss报告未支持的特性（feature unsupported）错误。目前只支持BTREE索引类型。
P2：在此异常事件流中，列大小验证失败，FDW通过ereport实用程序向openGauss报告无效列定义错误。
P3：在此异常事件流中，列类型验证失败，FDW通过ereport实用程序向openGauss报告未支持的特性（feature unsupported）错误。
P4：在此异常事件流中，索引的总键大小超过了最大允许的键大小，FDW通过ereport工具向openGauss报告无效列定义错误。
P5：在此异常事件流中，由于资源限制（内存不足），无法执行操作。
P6：在此异常事件流中，由于以下原因之一无法执行操作：①资源限制（内存不足），无法执行操作，②唯一主键冲突。

4） DELETE索引

图4-47 DELETE索引时序图

如图4-47所示，用户希望DELETE内存表中的现有索引时，openGauss通过FDW适配器将请求转发给MOT存储引擎。
正常事件流：FDW从MOT引擎中检索表对象，并转发从表中DELETE二级索引的请求。DDL命令在重做日志中持久化，然后截断索引数据并DELETE索引对象。
P1：在此异常事件流中，没有找到索引所属的表。此错误条件被静默忽略，FDW不会向openGauss报告错误。
P2：在此异常事件流中，在表对象中找不到请求的二级索引。此错误条件被静默忽略，FDW不会向openGauss报告错误。

5） 截断表

图4-48 截断表时序图

如图4-48所示，用户截断现有的内存表内容时，openGauss通过FDW适配器将请求转发给MOT存储引擎。
正常事件流：FDW从MOT引擎中检索表对象并转发截断表的请求。表中每个索引的索引数据被截断，并且将DDL命令持久化到重做日志。
P1：在此异常事件流中，没有找到该表。此错误条件被静默忽略，FDW不会向openGauss报告错误。
P2：在此异常事件流中，由于资源限制（内存不足），无法执行操作。

6） INSERT行

图4-49 INSERT行时序图

如图4-49所示，openGauss通过FDW适配器将请求转发给MOT存储引擎。可以通过自动提交（auto-commit）INSERT行，也可以在事务中INSERT行。
正常事件流：FDW从MOT引擎中检索表对象并创建新的行对象。由于内存引擎不同于磁盘引擎，不使用基于页面的间接访问形式，因此需要将行格式从openGauss行格式转换为MOT行格式（MOT将这种行格式转换称为Pack，反向转换称为unpack）后才能INSERT到表中。随后为该表的每个索引创建一个键。INSERT行的整个请求被传递到当前Txn，随后将该请求转发到并发控制模块，并持久化到重做日志。
P1：在此异常事件流中，由于资源限制（内存不足），无法执行操作。
P2：在此异常事件流中， INSERT行失败，原因如下：①内存分配失败；②在主节点上违反了唯一约束。在这两种情况下，父事务都将使用正确的错误代码中止。

7） SELECT/UPDATE/DELETE（计划阶段）

图4-50 SELECT/UPDATE/DELETE（计划阶段）时序图 用户可以在内存表中SELECT/UPDATE/DELETE行。每个操作分为两个阶段：计划阶段和执行阶段。图4-50主要关注计划阶段。 每个SELECT/UPDATE/DELETE的规划阶段包括选择最佳执行计划。为此，openGauss准备了几个可能的执行路径，并要求FDW估计每个此类路径的开销，以便openGauss可以选择最佳的执行路径。 正常事件流：openGauss调用GetForeignRelSize接口,FDW从MOT中检索相关表对象，并用启动成本和总成本估计初始化此查询的FDW状态。openGauss调用GetForeignPaths触发所有涉及索引对象的开销计算。最后，openGauss调用GetForeignPlan触发结束整个过程，包括查询子句对本地和远程排序，以及根据所选执行路径对FDW状态进行序列化。PREPARE语句的执行在此结束，其他语句待执行的部分将在执行阶段中描述。 P1：在此异常事件流中，由于资源限制（内存不足），无法执行操作。

8） SELECT/UPDATE/DELETE（执行阶段）

图4-51 SELECT/UPDATE/DELETE（执行阶段）

如图4-51所示，计划阶段完成后，执行阶段开始。
正常事件流：openGauss调用BeginForeignScan，FDW检索相关表并初始化查询的FDW状态。在进行UPDATE/DELETE操作时，openGauss通过调用BeginForeignModify接口触发一个额外的初始化阶段，然后返回NULL。openGauss通过调用IterateForeignScan接口进行如下操作：①仅在需要时一次性初始化游标；②在当前事务对象中查找下一行；③将行数据从MOT格式转换为openGauss格式；④游标前进；⑤返回包含unpack行的槽位。重复此过程，直到游标中不再有行，并且返回NULL到openGauss。然后openGauss应用本地条件/查询子句等本地过滤器来决定是否继续处理该行。在进行SELECT操作时，该行将被添加到结果集中，并返回结果集给用户。进行UPDATE和DELETE操作需执行的其余部分将在后文中进行描述。

9）UPDATE（结束执行阶段）

图4-52 UPDATE（结束执行阶段）时序图

执行SELECT、UPDATE和DELETE语句的公共部分后，每个语句的剩余部分有所不同。图4-52描述UPDATE的剩余部分。
正常事件流：openGauss为特定的更新元组调用ExecForeignUpdate接口。FDW更新当前事务对象中最后一行的状态以进行并发控制，然后FDW将行数据从openGauss格式转换为MOT格式，并通过覆盖该行的方式完成变更字段的更新。该操作在重做日志中持久化，并返回openGauss。
P1：在此异常事件流中，由于并发控制事务对象的行状态更新失败。在这种情况下，父事务将以适当的错误代码中止。

10） DELETE行（结束执行阶段）

图4-53 DELETE行（结束执行阶段）

图4-53描述了DELETE操作执行的剩余部分。
正常事件流：openGauss为特定更新的元组调用ExecForeignDelete接口。FDW更新当前事务对象中最后一行的状态以进行并发控制，然后将操作持久化到重做日志中，并返回openGauss。
P1：在此异常事件流中，由于并发控制事务对象的行状态更新失败。在这种情况下，父事务将以适当的错误代码中止。

4.3.3 内存表的存储

Table类包含管理数据库中内存表所需的所有项。表由以下组件组成：列、主索引和可选的二级索引。关键成员变量说明如表4-36 Table类的关键成员变量所示。

表4-36 Table类的关键成员变量

成员变量	描述
tableCounter : std::atomic<uint32_t>	原子表ID
m_tupleSize : uint32_t	原始元组大小（以字节为单位）
m_tableExId : uint64_t	openGauss提供的外部表ID
m_secondaryIndexes : SecondaryIndexMap	按名称访问的二级索引映射
m_rwLock : pthread_rwlock_t	RW Lock，防止在检查点/真空期间删除
m_rowPool : ObjAllocInterface*	row_pool行分配器对象池
m_primaryIndex : MOT::Index*	主索引
m_numIndexes : uint16_t	正在使用的耳机索引数
m_indexes : MOT::Index**	索引数组
m_fixedLengthRows : bool	指定行是否具有固定长度
m_fieldCnt : uint32_t	表schema中的字段个数
m_columns : Column**	列数组

Row类包含管理表中的内存行所需的所有项，关键成员变量如表4-37所示。

表4-37 Row类的关键成员变量

成员变量	描述
m_data : uint8_t	保存行数据的原始缓冲区，开始于类的结束位置
m_keyType : KeyType	使用的键类型。 Internal –用于内部测试（64位） Surrogate –用于无索引表 External –需要从行生成
m_pSentinel : Sentinel*	指向主哨兵的指针
m_rowHeader : RowHeader	OCC行的头部，包含OCC操作的所有相关信息
m_rowId : uint64_t	创建行时生成的唯一rowId
m_table : Table*	指向内存管理表的指针

4.4.4 索引

MOT使用索引来高效地访问数据。MOT索引支持范围查询等所有基本操作。由于数据存储在Row类中，每个MOT索引都按顺序使用哨兵来访问数据。
IndexFactory类提供了创建新索引对象的能力。
作为Table类的一部分，Index抽象类提供了创建和访问数据索引的能力。索引是否满足唯一性决定了该索引是否允许插入重复键。如图4-54所示，描述了一个有三行和两个索引的MOT表T的结构，其中一个索引是非唯一索引，另一个索引是唯一索引。对于非唯一索引而言，MOT内部通过在插入时用唯一标识符填充每个键的方式将键视为唯一。在图4-54中，MOT将哨兵插入到带有键的唯一索引和带有键+后缀的非唯一索引中。使用哨兵方便了维护操作，因为在进行维护操作时，可以在不接触索引数据结构的情况下替换行。

图4-54 唯一、非唯一索引和哨兵

Sentinel类包含指向唯一索引情况下的行数据或非唯一索引情况下主哨兵的指针，还包含一些标志位和引用计数等支持跨事务并发的信息。每次向索引插入新键时都会创建哨兵。例如，对于具有3个索引的表，插入新键时将创建3个哨兵，每个索引对应一个哨兵。哨兵和行之间的关系如图0-所示。

图4-55 哨兵与行关系

MasstreePrimaryIndex类实现了索引接口。它基于Masstree K/V存储实现，同时封装了MOT内存分配池，根据对象分配任意大小内存。
IndexIterator抽象类提供了创建迭代器并根据提供的迭代器访问数据的能力。

4.3.5 事务

事务部分覆盖了从openGauss映射到MOT的所有支持的DDL/DML操作。
事务与并发控制机制紧密耦合，每个操作都必须通过并发控制管理，并完成相应的行为。
MOT基于乐观并发机制，几乎不使用锁，因此每个客户端都有自己的事务视图，并且不会阻塞DML，与磁盘表对每个非SELECT操作都加锁的使用方式有显著区别。
每个局部行都有一个初始状态，状态由txn_state_machine管理。txn_state_machine扩展了Silo，支持新操作写后读和读后写，类似于MESI缓存一致性协议。如图4-56所示，MOT将新操作（RD/WR）视为本地缓存中的缓存不命中，并将状态从无效提升为新状态。

图4-56 DML事务状态机 图注：状态说明： INV：错误状态（INVALID STATE）；RD：查询状态（SELECT STATE）；WR：更新状态（UPDATE STATE）；DEL：删除状态（DELETE STATE）；INS：插入状态（INSERT STATE）。 操作说明： INV：无效操作（INVALID）；RD：读操作（READ）；WR：写操作（WRITE）；DEL：删除操作（DEL）；INS：插入操作（INSERT）。

详细流程

SELECT具体流程如图4-57所示。

图4-57 SELECT时序图

（1） 当SELECT操作被发送到FDW，FDW就会打开一个游标并将正确的哨兵发送到事务管理器。
（2） 事务管理器检查哨兵，如果哨兵有效则在缓存中搜索，否则返回未找到该行。
（3） TxnAccess在内部查找哨兵，如果在高速缓存中找到该行则返回该行，并认为是高速缓存命中。
（4） TxnManager评估隔离级别和来自缓存的结果：如果TxnAccess返回了一行，直接将其返回给openGauss；否则以下下两种情况。
① 隔离级别为READ_COMMITED时生成行的副本并返回给FDW。
② 隔离级别为REPEATABLE_READ时映射缓存中的行，并将缓存的行返回给FDW。

UPDATE具体流程如图4 58所示。

图4-58 UPDATE时序图

（1） 当UPDATE操作被发送到FDW，FDW就会打开一个游标，并将正确的哨兵发送到事务管理器。
（2） 事务管理器检查哨兵，如果哨兵有效就在缓存中搜索，否则返回未找到该行。
（3） TxnAccess在内部查找哨兵，如果在高速缓存中找到该行则返回该行，并认为是高速缓存命中。
（4） TxnManager评估来自缓存的结果。
① 如果TxnAccess返回了一行，直接将其返回openGauss。
② 如果没有找到该行，则映射哨兵并返回缓存的行。
（5） openGauss计算返回的行，如果该行与筛选器匹配则openGauss向FDW发送带有更新数据的更新操作。
（6） TxnManager将行的状态提升为WR，并用从openGauss接收的新数据更新本地行。

DELETE具体流程如图4-59所示。

图4-59 DELETE时序图

（1） 当DELETE操作被发送到FDW，FDW就会打开一个游标并将正确的哨兵发送到事务管理器。
（2） 事务管理器检查哨兵，如果哨兵有效就在缓存中搜索，否则返回未找到该行。
（3） TxnAccess在内部查找哨兵，如果在高速缓存中找到该行则返回该行，并认为是高速缓存命中。
（4） TxnManager评估来自缓存的结果。
① 如果TxnAccess返回了一行，直接将其返回openGauss。
② 如果没有找到该行，则映射哨兵并返回缓存的行。
（5） openGauss计算返回的行，如果该行与筛选器匹配，则openGauss向FDW发送带有更新数据的删除操作。
（6） TxnManager将行的状态提升为DEL，并将本地行标记为已删除。

INSERT具体流程如图4-60所示。

图4-60 INSERT序列图

（1） 操作发送到FDW后，FDW使用表API准备插入的行，并将该行发送到事务管理器。
（2） 事务管理器执行以下算法。
对于表中的每个索引执行以下操作。
① 将哨兵插入索引。
② 如果已提交行–中止事务。
③ 如果成功插入行–映射并完成插入。
④ 如果行不存在，如下。

• 如果已映射-自己插入，则中止。
• 否则将它映射到本地缓存。

（3） TxnManager对于重复的key返回RC_OK或RC_ABORT。TxnDDLAccess用于缓存和访问事务性DDL更改。事务中执行的所有DDL都存储在TxnDDLAccess中，并在事务提交/回滚时应用回滚。假设openGauss负责DDL并发，并确保并发的DDL更改不会并行执行。TxnAccess类用于缓存和访问事务性DML更改的。在事务中执行的所有DML都存储在TxnAccess中，并在事务提交/回滚中应用回滚。Access类用于保存单行访问的数据。AccessParams用于保存当前访问的参数，为CC管理提供额外的信息。InsItem用于保存行插入请求的数据。

4.3.6 并发控制

MOT采用源自SILO的单版本并发控制（concurrency control，CC）算法，是一种OCC算法。并发控制模块满足内存引擎的所有事务性需求，其主要设计目标是为MOT内存引擎提供各种隔离级别的支持。当前支持如下隔离级别。
（1） 读已提交（READ-COMMITED）。
（2） 可重复读（REPEATABLE-READ）。

图4-61 MOT本地内存和全局内存

图4-61显示了MOT运行事务时的关键技术，包括如下内容。
（1） 私有事务内存用于无锁读写，仅在最终提交时使用锁，低争用。
（2） 低时延，NUMA感知的本地内存。
（3） 乐观并发控制：数据锁最小化，低争用。
（4） 无锁自动清理（Auto-Vacuum），无开销。
（5） 极致优化的Masstree实现。

1. SILO并发控制背景&算法

Silo来自Stephen Tu等人在计算机顶级会议SOSP13上发表的《Speedy Transactions in Multicore In-Memory Databases》，在现代众核服务器上实现了卓越的性能和可扩展性。Silo的设计完全是为了高效地使用系统内存和高速缓存。例如，它避免了所有集中的争用点，包括集中事务ID分配。Silo的关键贡献是一种基于乐观并发控制的提交协议，它支持序列化，同时避免对仅读取的记录进行共享内存写入。Silo可提供与其他可序列化数据库一样的保证，而不会出现不必要的可扩展性瓶颈或额外的延迟。
设计
MOT的设计原则是通过减少对共享内存的写入来消除不必要的争用。Silo按照固定时间间隔的epoch进行时间分段，因此Silo这种OCC的变体可以支持序列化，即在epoch边界形成自然序列化点。在恢复之后也能通过CSN或周期性更新的epoch实现序列化。Epoch还有助于提高垃圾回收效率并使能快照事务。其他一些设计，如事务ID的设计、记录覆盖和支持范围查询等，进一步加快了事务执行，同时非中心化的持久化子系统也避免了争用。

2. 事务ID

SILO的并发控制以事务ID（tansaction ID，TID）为中心，它标识事务并记录版本，也用作锁和检测数据冲突。每个记录都包含最近修改它的事务的TID。TID为64位整数。每个TID的高位包含一个CSN，CSN等于对应事务提交时间的全局序列号；低三位分别为：Bit 63：锁定标志位，Bit 62：最新版本标志位，Bit 61：不存在状态标志位。由于CSN有效长度为61bit，因此MOT忽略了事务ID回卷。另外，与许多系统不同，Silo以分散而非集中的方式分配TID。

3. 数据布局

Silo中的一条记录包含以下信息。
（1） 一个64位的TID（MOT使用CSN）。
（2） 记录数据。提交的事务通常就地修改记录数据，主要通过减少记录对象的内存分配开销来提升短写的性能。然而，读者必须使用版本验证协议以确保已读取每个记录数据的一致性版本。

4. 乐观并发控制的数据库操作

1） 读/写流程

（1）事务流程
①在索引中搜索行引用。
② 将数据免锁复制到基于类型的本地集，包括读写集（Read/Write Set, R/W set）。
③ 基于本地副本进行处理。
（2）校验流程
① 按主键顺序对写集（Write Set）进行排序。
② 锁定写集中的所有行。
③ 验证读写集的行。
④ 验证本地行CSN是否更改。
⑤ 验证该行是否为该键的最新版本（由于存在本地数据，可能并非最新）。
⑥ 验证该行未被其他事务锁定。
⑦ 如果以上任一项验证失败，则中止事务。
⑧ 否则将更新CSN后的所有写集中的行复制回去，然后释放这些行上的锁。

2） 插入流程

（1）事务流程
① 构造一个CSN=0且状态为不存在的新行r。
     添加r到写集并视为常规更新。
     生成唯一的键k。
② 在状态为不存在的情况下，向树/索引添加从k → r的映射。

• 如果k已经映射到一个状态为存在的记录，则插入失败。
• 否则在读阶段增大版本号。

（2）校验流程
① 锁定写集。
② 验证插入集（insert set）。
③ 若事务中止，则垃圾回收器记录状态为不存在的行。

3） 删除流程

（1）事务流程
① 在索引中搜索行引用。
② 将行映射到本地缓存。
③ 将本地副本标记为已删除。
（2）校验流程
① 验证行保持不变；已删除的行将被视为更新。
② 从索引中删除行，即将已删除的哨兵/行放入垃圾回收器中。

图4-62 MOT提交协议伪代码 MOT提交协议伪代码如图4 62所示。

5. 关键类和数据结构

并发控制的关键类和数据结构如表4-38所示。

表4-38 并发控制的关键类和数据结构简介

关键类和数据结构	描述
OccTransactionManager类	管理整个事务验证机制，与事务类紧耦合
RowHeader类	每一行的OCC元数据。头部为64位，包含状态位和CSN

4.3.7 重做日志

MOT重做日志（Redo Log）使用预写式日志（write-ahead logging，WAL）技术来确保数据完整性。WAL的核心概念是，内存中的数据和索引的更改只有在记录下这些更改之后才会发生。因此写入重做日志是MOT提交协议的一部分。
如图4-63所示，MOT存储引擎的重做日志模块同样使用openGauss磁盘引擎的日志接口进行持久化和恢复。这意味着MOT重做数据被写入相同的XLOG文件，并使用相同的XLOG逻辑。使用与openGauss磁盘引擎相同的日志记录接口可确保跨引擎事务的一致性，并减少复制、日志恢复等模块的冗余实现。

图4-63 使用相同的XLOG (WAL)基础架构的openGauss磁盘库和MOT

1. 事务日志记录

与openGauss其他存储引擎不同，MOT内存引擎仅在事务实际提交时才会写入重做日志。因此，在事务期间或事务中止时，数据不会写入重做日志。这样可以减少写入的数据量，从而减少不必要的磁盘IO调用，因为这种磁盘IO调用很慢。例如，如果在事务期间多次更新同一行，则只将表示已提交行的最终状态写入日志。
由于设计MOT内存引擎时考虑了对接不同的数据库的可能性，因此如图4-64所示，MOT通过抽象的ILogger接口对接重做日志。

图4-64 ILogger接口

2. 日志类型

设计MOT内存引擎时同样考虑了支持不同的日志记录方式。如图4-65所示，MOT当前已实现同步日志（synchronous redo Log）和同步组日志（group synchronous redo log）。这是通过RedoLogHandler类实现的。RedoLogHandler封装了日志逻辑，在数据库启动时初始化。RedoLogHandler可以根据需要扩展实现新的日志记录方式。

图4-65 RedoLogHandler接口

每个事务管理器对象（TxnManager）都包含一个Redolog类，该类负责在提交时将事务数据序列化到缓冲区中。如图4-66所示，该缓冲区被传输到RedologHandler以进行日志记录。

图4-66 使用RedoLogHandler的事务日志记录

1） 同步日志记录
同步日志使用SynchronousRedoLogHandler。如图4-67所示，这是一个简单的RedoLogHandler实现，它只将序列化缓冲区委托给ILogger（XLOGLogger），以便将其写入XLOG。因为在写缓冲区时，事务被阻塞，所以称为同步。只有当所有事务数据被序列化并写入日志时，提交协议才会继续。

图4-67 SynchronousRedoLogHandler

2） 同步组提交日志记录

同步组提交日志由SegmentedGroupSyncRedoLogHandler类实现。它通过将几个事务分组到一个写块（write block）中并一起写入的方式优化日志记录。这种方法在一次调用中收集更多数据，可以最大限度地减少磁盘IO次数。除此之外， SegmentedGroupSyncRedoLogHandler将每个NUMA处理器（socket）的事务分组，以减少跨NUMA处理器的数据传输，因为跨NUMA处理器的数据访问比同一NUMA处理器本地内存访问慢。
当事务提交时，它将数据序列化到缓冲区中，这个缓冲区被传输到SegmentedGroupSyncRedoLogHandler，并放入一个提交组中。提交组（Commit Group）是一组序列化事务缓冲区的集合，这些事务缓冲区将被提交并写入磁盘。根据不同的配置参数，当一个组被填满或超过预先配置的时间时，MOT将关闭该组，并将该组内所有缓冲区一起写入日志。
图4-68描述了将多个事务分组一起写入的组提交逻辑。

图4-68 同步组提交对每个NUMA处理器的事务进行分组

3） 异步日志

MOT暂未开发专用的异步日志机制，异步日志是通过在conf配置文件中将synchronization_commit参数设置为“off”来实现的。

3. 关键类和数据结构

重做日志的关键类和数据结构如表4-39所示。

表4-39 重做日志的关键类和数据结构简介

关键类和数据结构	描述
RedoLog类	负责事务数据序列化的主要类，它是TxnManager类的成员对象。RedoLog的commit方法由TxnManager在事务通过验证阶段并且所有更新的行均已锁定后在提交协议中调用。在将变更应用到存储之前，RedoLog将在加锁后序列化事务数据，持久化到日志，释放锁。RedoLog使用RedoLogHandler将数据写入日志。RedoLogBuffer类是序列化缓冲区的一个简单实现，RedoLog类通过RedoLogBuffer序列化事务操作。RedoLogBuffer的前4个字节预留给缓冲区大小，在序列化时写入。OperationCode枚举是支持的事务操作列表。RecoveryManager通过根据OperationCode确定如何解析数据并应用事务操作
RedoLogWriter	用于将操作序列化到缓冲区中。RedoLogWriter是一个简单的helper类，获取数据和缓冲区，并将数据序列化到缓冲区中
EndSegmentBlock	控制块，写在每个flushed缓冲区的末尾。包括事务、CSN、是否提交等信息
EndSegmentBlockSerializer	一个简单的helper类，用于序列化和反序列化EndSegmentBlock
Ilogger接口	写日志接口的抽象。MOT通过ILogger可以写入不同类型的日志
LoggerFactory	一个工厂类，用于创建不同类型的ILogger。LoggerFactory通过MOT配置项确定要创建哪种logger
XLOGLogger	基于openGauss XLOG (WAL)的ILogger的一个实现，它简单地使用openGauss WAL接口将序列化的事务写入WAL中。MOT WAL日志项有自己的资源管理器，这可以使openGauss识别到该日志项是一个MOT WAL日志项，并将其转发到MOT处理。AddToLog为XLOGLogger子接口，XLOGLogger使用openGauss日志基础能力。因此，AddToLog是一个对openGauss XLOG接口的简单委托

图4-69所示代码为XLOGLogger::AddToLog接口的实际实现。

图4-69 XLOGger对openGauss XLOG的委托

RedoLogHandler是重做日志逻辑的抽象。RedoLogHandler的派生类可实现不同的日志方法。RedoLogHandler是一个单例模式，由MOT管理，为RedoLog所用。

RedoLogHandlerFactory用于创建RedoLogHandler。MOT根据配置项中配置的RedoLogHandlerType创建RedoLogHandler。

SynchronousRedoLogHandler简单地将RedoLogBuffers委托给ILogger，以便写入重做日志。请参阅前述的同步日志记录小节。

GroupSyncRedoLogHandler是最先进的无锁组提交RedoLogHandler。GroupSyncRedoLogHandler将几个事务的redo log缓冲区分组到一个组，并把他们写在一起，以便优化和最小化磁盘IO。请参阅前述同步组提交小节。CommitGroup表示将一组RedoLogBuffer一起记录。一个提交组有一个主线程，由该主线程创建该提交组，它负责将组内的所有RedoLogBuffer写入日志。主线程写日志时，所有其他线程都在等待。主线程完成写入后将发送信号来唤醒组内其他所有线程，一旦唤醒，事务就可以继续。SegmentedGroupSyncRedoLogHandler是配置了GroupCommit日志方法时的RedoLogHandler。它是RedoLogHandler的一个实现，每个socket都有GroupSyncRedoLogHandler。SegmentedGroupSyncRedoLogHandler的优点在于可以通过维护多个组提交处理程序实现更高的并发。SegmentedGroupSyncRedoLogHandler维护一个GroupSyncRedoLogHandler数组，并将线程绑定到Socket以将线程委托给正确的处理程序。

4.3.8 检查点

与openGauss磁盘存储引擎不同，MOT存储引擎不基于页面存储数据，因此MOT的检查点机制与磁盘引擎的检查点机制完全不同。MOT检查点机制基于CALC（checkpointing asynchronously using logical consistency，使用逻辑一致性异步检查点）算法，该算法出自耶鲁大学Kun Ren等人在数据库顶级会议SIGMOD 2016发表的《Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems》。

1. CALC算法

CALC算法的优点如下。
（1） 内存占用少：任意时刻每行最多2个副本。只有当检查点为活动状态时，更具体地说，仅在检查点的一个特定阶段，才会创建第二个副本，从而减少了内存占用。
（2） 开销小：CALC比其他异步检查点算法开销小。
（3） 使用虚拟一致性点：CALC不需要停止数据库就能实现物理一致性。虚拟一致性点是数据库的视图，它反映了在指定时间之前提交的所有修改，而不包含指定时间之后提交的修改，而且在不停止数据库系统的情况下就可以获得。实际上，可以通过部分多版本创建虚拟一致性点。
如图4-70所示，精确部分多版本算法（precise partial multi-versioning）的总体思想如下。
（1） 每行都与两个版本相关联，一个是活动版本，一个是稳定版本。通常，稳定版本为空，表明稳定版本与活动版本一致，检查点线程可以安全地记录实时版本。稳定版本仅在检查点的一个特定阶段创建，此时检查点线程将记录该稳定版本。
（2） 每行维护一个稳定状态位，指示稳定行的状态。

图4-70 检查点概述

MOT检查点算法在五个状态之间循环，如图4 71所示。

图4-71 检查点状态机

通常，在进入下一阶段之前，系统要等待所有上一阶段开始提交的事务完成。
1） REST阶段：初始阶段，不进行checkpoint。
（1） 在REST阶段，每行只存储一个活动版本。所有稳定版本都为空，稳定状态位始终为不可用（not available）。
（2） 在此阶段开始提交的任何事务将直接对行的活动版本进行操作，并且不会创建稳定版本。
2） PREPARE阶段：这是虚拟一致性点之前的阶段。当openGauss要求MOT创建快照时，系统从REST阶段移动到PREPARE阶段。
（1） 与REST阶段类似，每行只存储一个活动版本。所有稳定版本都为空，稳定状态位始终为不可用。
（2） 在此阶段开始提交的任何事务将直接对行的活动版本进行操作，不会创建稳定版本。
3） RESOLVE阶段：该阶段标识出虚拟一致性点。在此时间点之前提交的所有事务都将包含在此检查点中，而随后提交的事务将不包含在检查点中。一旦在REST阶段开始提交的事务完成，系统将自动从REST阶段变为RESOLVE阶段。
（1） 在此阶段不允许任何事务启动提交，以避免这些事务在openGauss占用检查点的重做点前写入重做日志。
（2） 一旦在REST阶段开始提交的事务完成，MOT将在此阶段获取要包含在此检查点中的任务列表。
4）CAPTURE阶段：在此阶段中，后台工作进程将数据刷入磁盘。RESOLVE阶段一直持续，直到在准备阶段已开始的所有事务完成并释放其所有锁为止。系统准备任务列表，然后进入CAPTURE阶段。
（1） 在CAPTURE阶段开始的事务已经在一致性点之后开始，因此他们肯定会在一致性点之后完成。因此，除非记录已经具有显式稳定版本，否则总是在更新前将活动版本复制为对应的稳定版本。
（2） 收到BEGIN_CHECKPOINT事件后，系统生成检查点工作进程，扫描所有记录，并将没有显式稳定版本的行，或活动版本的对应的稳定版本刷盘。在此过程中，显式稳定版本一旦刷盘就会被释放。
5） COMPLETE阶段：这是紧跟捕获阶段完成的阶段。检查点捕获完成后，系统进入COMPLETE阶段。事务写入行为恢复为与REST阶段相同的状态。
与REST阶段类似，每行只存储一个活动版本。所有稳定版本都为空，稳定状态位始终为不可用（not available）。
一旦在捕获阶段开始的所有事务都完成，系统将转换回REST阶段，并等待下一个触发检查点的信号。但是，在返回到REST阶段之前，调用函数SwapAvailableAndNotAvailable翻转稳定状态位。这允许MOT避免只能通过完全扫描来重置稳定状态位，因为在CAPTURE阶段之后，所有稳定状态位都可用，但在Rest阶段开始时，希望所有稳定状态位都不可用。

2. 详细流程

（1） 一旦触发了检查点，Checkpointer后台会触发MOT的CREATE_SNAPSHOT事件。
（2） 当检查点处于REST阶段时，CheckpointManager将等待在COMPLETE阶段启动的事务完成。
（3） CheckpointManager修改checkpoint阶段为PREPARE。如果没有在REST阶段启动提交的事务处于活动状态，则立即进入RESOLVE阶段，否则等待REST阶段启动提交的最后一个事务完成后进入RESOLVE阶段。
（4） RESOLVE阶段标记了虚拟一致性点。在此阶段不允许任何事务开始提交，以避免在openGauss采取检查点的重做点之前这些事务写入重做日志。CheckpointManager等待在PREPARE阶段启动的事务完成。
（5） CheckpointManager准备要flush的表的列表（任务列表）并读取这些表的锁状态。
（6） 然后获取写锁，锁定redolog handler，并将检查点阶段更改为CAPTURE。这标志着CREATE_SNAPSHOT事件结束。
（7） openGaussCheckpointer获取WalInsertLock锁并计算此检查点的重做点。然后，该重做点触发MOT的SNAPSHOT_READY事件。
（8） CheckpointManager存储重做点，释放redolog handler锁。这标志着SNAPSHOT_READY事件结束。
（9） 然后openGaussCheckpointer释放WalInsertLock并将所有磁盘引擎脏页刷盘，即磁盘引擎的检查点。
（10） 然后触发MOT的BEGIN_CHECKPOINT事件。
（11） CheckpointManager在这个阶段生成检查点worker来完成MOT检查点任务列表。
（12） 检查点worker之间共享任务列表，并将所有符合条件的行刷入磁盘（行的稳定版本或没有显式稳定版本到磁盘的活动版本）。在此过程中任何显式稳定版本一旦刷新到磁盘，就会释放。
（13） 一旦所有检查点worker完成任务，CheckpointManager将解锁表并清除任务列表。
（14） CheckpointManager还可将检查点阶段提前到COMPLETE。
（15） 通过创建map文件、结束文件等来完成检查点，然后更新mot.ctrl文件。
（16） 等待CAPTURE阶段开始的事务完成。
（17） 交换可用位和不可用位，以便将他们映射到稳定状态位中的1和0值。
（18） 修改checkpoint阶段为REST。这标志着BEGIN_CHECKPOINT事件和MOT检查点的结束。
（19） 然后openGauss将检查点记录插入到XLOG中，刷新到硬盘，最后更新控制文件。openGauss中的检查点就此结束。

3. 关键类和数据结构

检查点的关键类和数据结构如表4-40所示。

表4-40 检查点的关键类和数据结构简介

关键类和数据结构	描述
CheckpointManager类	理整个检查点机制的主类，是MOT中所有检查点相关任务的接口类。CheckpointWorkerPool类用于生成检查点worker并刷盘。该类不提供真正的接口。实例化对象时会生成检查worker，并使用回调通知任务完成。在CAPTURE阶段CheckpointManager实例化一个CheckpointWorkerPool对象，并等待所有任务完成。CheckpointControlFile用于实现checkpoint控制文件逻辑。MOT控制文件保存着最后一个有效检查点ID、lsn（openGauss中的重做点）和最后一个重放lsn。控制文件mot.ctrl在每个检查点结束时更新
CheckpointWorkerPool类	用于生成检查点worker并刷盘

4.3.9 恢复

恢复部分有两个目的，一是在崩溃或关机后达到最新的一致状态，也称为冷启动（coldstart），二是在HA复制场景中，在备机侧通过重放redo log完成复制。
冷启动时，当所有WAL记录都重放完成后恢复结束；但在HA复制场景中，复制将持续进行，直到备机改变状态。
在恢复过程中，可能存在跨越多个重做日志段的长事务，MOT将其保存在InProcessTransactions映射对象中，直到提交。包含在映射中的数据作为检查点处理过程的一部分进行序列化，并在检查点恢复期间进行反序列化。
此外，在最后恢复阶段，完成所有检查点/WAL记录之后将设置最后的CSN，并将代理键生成器恢复到崩溃或关闭前的最新状态。
为了恢复代理状态，每个恢复线程（检查点和重做日志）都在更新每个线程id的代理最大键数组。最后，这些数组被合并成单个数组，用于恢复最后状态。

1. 详细流程

具体恢复流程如图4-72所示。

图4-72 恢复时序图

恢复过程如下。
（1） 通过openGauss的StartupXLOG函数调用MOT恢复过程。
（2） 如果存在检查点则从检查点执行第一次恢复。
（3） 读取控制文件，并获取重放lsn。当重启点（备机检查点）存在时，将使用lastReplayLsn作为重放点，而非lsn。
（4） 处理检查点映射文件并生成任务列表。由于MOT检查点仅由行组成，不需要以特定顺序重放，因此这些行的恢复可以并行执行。这就是检查点进程将表拆分成段的原因。
（5） 从元数据文件中恢复所有表的元数据。
（6） 创建检查点恢复线程，每个线程尝试从列表中获取任务，读取与此任务关联的文件并恢复行数据。此恢复是非事务性的。
（7） 如果有进程内事务，也会从检查点恢复。（8） 检查点恢复完成，返回StartupXLOG，开始重放redo记录。
（9） 当遇到MOT资源管理器（resource manager，rmgr）记录时，将调用MOT引擎的MOTRedo函数，该函数调用恢复管理器ApplyRedoRecord方法。
（10） 在ApplyRedoRecord中，只有当数据的lsn大于恢复的检查点lsn，并且调用ApplyLogSegmentFromData时，才会处理数据。
（11） ApplyLogSegmentFromData从数据中提取LogSegment，分配并插入InProcessTransactions Map。
（12） 当遇到提交记录时，该记录可以是仅MOT事务的LogSegment的一部分，也可以来自MOT注册到openGauss的DDL或跨引擎事务的提交后回调。事务的相关日志段将进行事务性重放和提交。
（13） 上述过程将继续循环，直到StartupXLOG完成。
（14） 调用RecoverDbEnd完成恢复，设置CSN并应用代理状态。

2. 关键类和数据结构

恢复的关键类和数据结构如表4-41所示。

表4-41 关键类和数据结构简介

关键类和数据结构	描述
RecoveryManager	实现了IRecoveryManager的API，它是恢复中使用的主类
IRecoveryManager	是一个抽象类，定义了每个RecoveryManager应该实现的接口
SurrogateState	保存了内部数组中每个连接ID的代理键值
LogStats	用于统计，统计信息在LogStats::Entry中按表收集，需在mot.conf中启用
CheckpointRecovery	负责从有效的检查点恢复所有行。它封装了恢复所需的所有操作，包括表的元数据和并行行插入
LogSegment	实际上是重做日志保存的数据段，除了缓冲区外还包括描述操作及其事务ID的元数据
RedoLogTransactionSegment	多个日志段的容器，可以形成一个完整的事务
RedoLogTransactionIterator	一个从XLOG数据中提取LogSegments的helper类
InProcessTransactions	单例模式的Map对象，用于保留正在运行的事务LogSegments，并一直收集直到这些事务提交为止
RecoveryOps	从LogSegment执行DML和DDL操作的实际恢复

4.4 小结

本章主要介绍了openGauss的存储引擎，包括磁盘引擎和内容表。在磁盘引擎中，openGauss提供不同存储格式的磁盘引擎来满足不同业务场景对于数据不同的访问和使用模式。内存表针对众核和大内存服务器进行了优化，可提供非常高的事务性工作负载性能。

第4章存储引擎源码解析的所有内容将告一段落，下一篇我们将开启第5章事务机制源码解析的内容介绍。敬请期待。