「分布式技术专题」并发系列三：乐观并发控制之原型系统

「分布式技术专题」并发系列三：乐观并发控制之原型系统

以时间轴的方式对不同时期的有代表性的论文（从理论研究、原型系统、 生产系统三个维度分类）进行了梳理，带你简要回顾一下OCC在学术界及工业界的发展历程。

原型系统——MVCC+OCC+2PC

Distributed transaction management in jasmin VLDB 1984这篇论文给出了OCC在分布式系统实现层面的解决方案，系统采用多版本存储，数据对象的粒度为一个页面，事务流程简要描述如下：

• 读取阶段

选取全局读时间戳，保证读取阶段能够看到一致的数据库视图。对于只读事务，在读取阶段结束后就可以提交。事务写页面时会在系统内部创建影子页面。

• 验证阶段/写入阶段

使用两阶段提交完成验证和写入阶段：

获取一个全局的事务时间戳由协调者消息通知相关各结点启动验证阶段各结点统一使用该全局时间戳，基于论文[1]中提到的并行验证版本进行验证协调者根据收到的所有的验证反馈决定发送提交还是中止消息该论文从原型实现验证了OCC落地的可行性，并首次使用全局时间戳解决OCC读取阶段数据库视图不一致及全局事务中子事务串行化验证标准不一致的问题。理论研究——动态调整提交时间戳减少事务中止率Certification by intervals of timestamps in distributeddatabase systems 1984

论文认为[1]中的OCC是将事务进入验证阶段的时间作为事务提交时间戳并据此调度事务的可串行化，这会导致一些非必要的事务中止，提出一种在验证阶段基于访问数据的时间戳版本动态调整事务提交时间戳的方法，其基本思想如下：

基本数据结构：

• 在事务访问的每个结点上需要维护该事务的提交时间戳区间• 每个数据对象维护一个最大读时间戳和最大写时间戳，这些时间戳均为已提交事务的提交时间戳• 每个结点维护活跃事务表及其读集、写集• 每个数据对象维护读/写过该对象的活跃事务

基本流程：

事务初始提交时间戳区间设置为0到正无穷

读取阶段① 事务执行过程中访问任意结点上的数据时都需要传递客户端上的事务提交时间戳区间信息② 进入临界区③ 结点将客户端提交时间戳区间信息与本地维护的提交时间戳区间求交集得到最新的提交时间戳区间信息④ 根据读写类型区别操作– 如果是读操作，将事务提交时间戳区间的下限设置为数据对象的最大写时间戳+1；将事务加入数据对象的读事务列表中；将数据对象加入结点维护的事务读集中– 如果是写操作，将事务提交时间戳区间的下限设置为数据对象的最大写时间戳与最大读时间戳之间的最大值+1；将事务加入数据对象的写事务列表中；将数据对象加入结点维护的事务写集中⑤ 更新本地事务提交时间戳区间信息⑥ 向客户端回传最新的事务提交时间戳区间信息及读取的值⑦ 退出临界区⑧ 客户端将回传信息与当前信息作交集得到最新的时间戳区间（通过这种方式使得结点能够感知到事务在其它结点上的依赖信息，便于早发现不符合串行化调度的事务）验证和写入阶段（由于其它事务的读写操作与当前事务的验证阶段都会修改事务的时间戳区间，所以结点上的读写操作与验证时的调整操作需要互斥）① 客户端向各参与结点发送验证/提交消息（消息中包含验证事务的最新提交时间戳区间）② 提议阶段– 参与结点将最新提交时间戳与本地合并后广播给集群中的所有其它结点– 同步等待其它结点，最终得到一个所有结点一致的待验证事务提交时间戳区间③ 时间戳选择阶段– 如果该时间戳区间无效（空集），则中止事务– 否则，在有效区间内选择一个具体的提交时间戳（所有结点上的时间戳选择策略要一致，该时间戳影响读冲突事务的上限/写冲突事务的下限，如果选择提交时间戳区间下限，意味着能够避免更多的写冲突事务的中止，增大读冲突事务的中止；反之，则效果相反）④ 调整及写入阶段– 对于验证事务读集中的每个数据对象，调整该对象上的所有活跃写事务的提交时间戳下限为验证事务提交时间戳+1；如果验证事务提交时间戳大于数据对象上的最大读提交时间戳，则修改为验证事务的提交时间戳– 对于验证事务写集中的每个数据对象，调整该对象上的所有活跃读事务的提交时间戳上限为验证事务提交时间戳-1；调整该对象上的所有活跃写事务的提交时间戳下限为验证事务提交时间戳+1；调整该对象的最大写提交时间戳为验证事务提交时间戳并设置为更新的数据– 清除结点上与验证事务相关的信息，返回客户端事务已提交作者为了发现串行化冲突，需要结点在验证阶段开启时将本结点的事务时间戳区间信息广播到所有结点，等到全部结点回复后才开始对事务进行串行化检查，在分布式系统中人为设置了同步点，对扩展性会有一定的影响。

其它关于OCC的研究主要集中在与传统并发控制技术的性能对比[5]，如何减少不必要的事务中止率[9]，同时支持2PL与OCC[4]，如何防止事务饿死[10]及OCC在实时数据库系统中的应用[11]，可以看出，这一时期OCC基本处于学术研究及原型验证阶段，当时的数据库工业界，如Oracle、DB2，还是使用了主流的并发控制技术，如2PL、MVCC。

今生

进入21世纪后，数据库运行的硬件基础设施在向两个方向发展：

• 内存数据库

随着硬件技术的发展，如论文[12][19]中所述，多核（几十、几百）、大内存（T级别）的单节点配置已在市场上出现， 意味着大多数OLTP场景下的数据处理可以完全运行在内存中，SAP HANA、MemSQL、TimesTen、SolidDB、Hekaton等内存数据库也应运而生。

• 分布式NewSQL数据库

随着互联网应用的兴起，标榜着高可靠、高可用、高可扩展的NoSQL运动席卷而来， 运行环境也由大型机过渡到分布式集群、多数据中心、多可用区等；NoSQL系统虽然实现了承诺的目标， 但其不支持SQL语言、缺乏强一致性的短板一直备受开发人员的抱怨，于是NewSQL系统又进入了人们的视野， 其主打口号是既具有NoSQL的所有优点并且还支持SQL语言及ACID事务，如F1、Spanner、CockroachDB、TiDB、OceanBase等。

与传统并发控制方法相比，OCC的优点是在高资源竞争、低数据竞争场景下，能够减少事务运行同步开销，避免死锁，支持更高的事务吞吐率； 缺点是在高数据冲突场景下有较高的事务中止率，浪费计算资源（2PL在此场景下事务中止率也很高，但能够提前中止，不用等到事务提交时）。

上述两种场景，一个关注单机事务吞吐量；另一个关注分布式事务吞吐量，其性能优化目标可以统一描述为在硬件资源充足的情况下如何提高事务吞吐量。 节约资源已不再是重点，减少系统同步，提高资源利用率才是核心问题。尤其是在分布式计算环境下，网络交互的延迟或异常容易导致2PL协议可能长时间持有锁从而导致系统整体事务吞吐率降低或死锁。 OCC的价值在新的数据库基础设施环境上又获得了学术界与工业界的重视。

以上为分布式技术专题之并发系列三：乐观并发控制之原型系统，「分布式技术专题」是由hubble数据库团队精心整编，专题会持续更新，欢迎大家保持关注。