4.3.6 并发控制
MOT采用源自SILO的单版本并发控制（concurrency control，CC）算法，是一种OCC算法。并发控制模块满足内存引擎的所有事务性需求，其主要设计目标是为MOT内存引擎提供各种隔离级别的支持。当前支持如下隔离级别。
（1） 读已提交（READ-COMMITED）。
（2） 可重复读（REPEATABLE-READ）。
图461 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）校验流程
① 验证行保持不变；已删除的行将被视为更新。
② 从索引中删除行，即将已删除的哨兵/行放入垃圾回收器中。
图462 MOT提交协议伪代码
MOT提交协议伪代码如图4 62所示。
5. 关键类和数据结构
并发控制的关键类和数据结构如表4-38所示。
表4-38 并发控制的关键类和数据结构简介
