MOT：Industrial-Strength OLTP Usi

openGauss是华为的关系型数据库管理系统(RDBMS)，主要采用基于磁盘的存储引擎。本文提出了一种新的GaussDB存储引擎，该引擎经过了主存和多核优化。

Indexing and Storage

非唯一索引.png

上图描述了一个MOT的T表的结构，它有三个行和两个索引。矩形表示数据行，索引指向指向行的哨兵（椭圆形）。哨兵用键插入唯一索引，用键+后缀插入非唯一索引。哨兵可以方便维护操作，无需接触索引数据结构就可替换行。此外，在哨兵中嵌入了各种标志和参考计数，以便于乐观插入。

乐观插入算法

乐观插入算法.png

上图是乐观插入算法的流程图。

• 插入算法的入口参数是要插入的row(源码中是ExecuteOptimisticInsert(Row* row))。
• 在开始时，事务X插入一个未连接到行的标记。在引用计数等于1的情况下，将标记插入到缺席状态。如果插入成功，X需要在访问集的事务性私有插入集部分中插入的私有行。访问集是由键-值映射实现的（std::map<void*, Access*, std::less<void*>> m_rowsSet），作为行的键，使用指向sentinel的指针。注意，如果一个表有多个索引，那么行将在访问集中用不同的键映射多次，键是指向不同索引中的哨兵的指针。
• 如果插入失败，并且索引中有一个非缺失的哨兵，我们就会得到一个重复的插入并中止事务。
• 如果哨兵处于缺席状态，我们就增加它的引用计数。当引用计数为0时重插入，因为这个哨兵被删除了。如果这个sentinel已经提交并且未删除，则插入失败，如果已删除或者没有提交，则尝试将其映射到访问集。如果映射失败，就意味着在访问集中已经有了这个标记作为键。唯一可能发生的情况是当前事务已经尝试插入相同的唯一键，因此，由于重复插入而终止事务。
• 在提交阶段，锁定X插入的所有哨兵之后，这些哨兵被链接到插入的私有行，该行变为公有行。

Concurrency Control

并发控制.png

传统的OCC执行，事务不能访问本事务执行过程中更新的记录。MOT创建状态机，并对所有读取、更新、插入和删除的行保持一个访问集。该集合由指向原始行或哨兵的指针作为键值，因此一旦遇到它，就可以在访问集中找到它。键的值是事务中该行的私有副本和该行的状态。如果在更新(WR)、插入(INS)或删除(DEL)中发现一行，则声明相关值，即将该行的本地副本返回给用户。
上图是并发控制的执行过程。

• 先收集需要更新的行，也就是状态为WR和DL的，加入到写集
• 将插入的行加入到insert集，并将主哨兵插入到写集
• 状态是RD的加入读集中
• 锁住读集和插入集中的行，并进行验证，验证不通过则abort
• 验证成功后，写入更新后的数据，私有插入的行与已插入的哨兵连接起来，将该行设置为not absent，即committed。释放了哨兵中的所有锁，行中的所有锁。