OCC（Optimstic Concurrency Control）,从广义上理解，OCC表示一种乐观并发控制的思想，只在事务提交时对事务是否符合串行化进行验证；而悲观并发控制（Pessimistic Concurrency Control）会对事务执行过程中的每个操作进行串行化验证。在这一思想的指导下，应用层的乐观锁也属于OCC；从狭义上理解，OCC特指一个具体的不依赖加锁的并发控制技术，与2PL/TO/MVCC等处于同一个概念层次，属于数据库内核层。本文以下提到的OCC指代的是狭义的概念。
前言
上一篇 提到了苹果新近开源的FoundationDB基于NoSQL+ACID架构实现了一个支持事务语义的NoSQL数据库，并由此简单回顾了一下开源社区从NoSQL到NewSQL运动的转变，同时强调了Google在这一变革中起到的决定性作用，最后列出了当前几种流行的NewSQL生产级分布式数据库所使用的并发控制技术及支持的隔离级别，可以明显看出FoundationDB在并发控制技术上的独树一帜。
本篇为该系列文章的续篇，以时间轴的方式对不同时期的有代表性的论文（从理论研究、原型系统、生产系统三个维度分类）进行了梳理，带你简要回顾一下OCC在学术界及工业界的发展历程。
这里需要先对 OCC（Optimistic Concurrency Control） 指代的概念做一个说明，从广义上理解，OCC表示一种乐观并发控制的思想，只在事务提交时对事务是否符合串行化进行验证；而悲观并发控制（Pessimistic Concurrency Control）会对事务执行过程中的每个操作进行串行化验证。
在这一思想的指导下，应用层的乐观锁也属于OCC；从狭义上理解，OCC特指一个具体的不依赖加锁的并发控制技术，与2PL/TO/MVCC等处于同一个概念层次，属于数据库内核层。本文以下提到的OCC指代的是狭义的概念。
本文重点在于沿着OCC发展的时间线的梳理，由于相关论文较多，作者无法深入探究每篇论文的详细内容，仅描述了论文中的大致思想，可能也有不全面或错误的地方，感兴趣的同学可以研读论文原著。
前世
理论研究——集中式OCC
On Optimistic Methods for Concurrency Control 1981
OCC技术最早由CMU大学的H.T. KUNG教授提出，当时数据库并发控制研究的热点是2PL，作者直接列举了基于锁的并发控制协议的五宗罪：
1. 加锁协议开销大，对于不会改变数据库约束完整性的只读事务也需要加读锁保护以防止别人修改；对于可能造成死锁的加锁协议还需要额外增加死锁检测开销
2. 为了避免死锁，需要定制各种复杂的加锁协议
3. 在持有锁的情况下可能会等待I/O操作，会大幅降低系统整体的并发吞吐量
4. 加锁事务回滚时必须持有锁，直到事务回滚结束，降低了系统整体的并发吞吐量
5. 只有在最坏情况下才需要加锁；很多真实的应用场景往往是高并发低竞争的
作者据此提出了一种新的乐观并发控制方法用于解决上述问题（所谓的乐观是针对并发事务冲突概率极低的工作负载场景），该方法将一个事务的生命周期划分为三个阶段：
- 读取阶段
- 所有更新操作缓冲在事务本地内存空间中，维护事务的写集
- 所有读取操作先访问事务本地内存空间，若不存在则从数据库中读取并可选地缓存在事务私有内存空间中，维护事务的读集
- 验证阶段
根据某种可串行化标准检查待提交事务是否满足可串行化调度
- 写入阶段（只读事务不需要）
将事务私有内存中的更新数据写入数据库使其全局可见
假设系统中每个事务能够被赋予全局唯一的事务号，则有事务号Ti和Tj，且Ti<Tj，可以将系统内是否存在一个与事务号顺序等价的并发事务调度序列作为可串行化标准，则检查事务Tj是否符合可串行化（即Ti在Tj之前完成），需满足如下三种条件之一：
1、Ti在Tj开始读取阶段前完成写入阶段，即Ti在Tj之前提交
2、Ti的写集与Tj的读集不相交，且Ti在Tj开始写入阶段前完成写入阶段
3、Ti的写集与Tj的读集和写集都不相交，且Ti在Tj完成读取阶段前完成读取阶段
作者提出了两种满足上述条件的验证阶段实现方案：
1、串行方案（事务并发满足条件1或2）
事务开始
获取当前已提交的事务号
事务结束
① 进入临界区
② 获取当前已提交的事务号
③ 验证事务开始和结束期间提交的事务的写集与待验证事务的读集是否相交
④ 相交，则发现冲突，退出临界区并中止待验证事务
⑤ 不相交，则验证成功，执行写入阶段（如果是只读事务无需执行）并递增提交事务号
⑥ 退出临界区
2、并行方案（事务并发满足条件1或2或3）
事务开始
获取当前已提交的事务号
事务结束
① 在临界区内获取当前已提交的事务号/获取当前活跃事务列表/将自身加入活跃事务列表
② 验证事务开始和结束期间提交的事务的写集与待验证事务的读集是否相交
③ 验证活跃事务（这些活跃事务均已完成读取阶段，读集和写集不会再发生变化，可理解为进入验证的事务列表）的写集与待验证事务的读集和写集是否相交
④ 相交，则发现冲突，在临界区内将本事务从活跃事务中去除并中止待验证事务
⑤ 不相交，则验证成功，执行写入阶段（如果是只读事务无需执行）
⑥ 在临界区内递增提交事务号并将本事务从活跃事务中去除
在系统实现中，还需要考虑两种特殊情况的解决方案：
1、长事务
根据上述规则，需要检查长事务开始时未提交的事务的写集。由于数据库系统只能维护有限的事务写集，作者建议只维护最近事务的写集，如果验证时无法找到事务号对应的写集，则中止待验证事务并重新执行。
2、饿死现象
验证失败时事务需要中止并重新执行，存在一种极端情况使得事务持续地中止并重新执行，作者建议记录事务的失败验证次数，若超过一定阈值，则在临界区内重新执行事务，彻底排除其它并发事务的干扰。
显然，上述方案都是针对单数据版本的集中化数据库系统，在分布式数据库系统中的OCC算法还有待后人扩展。
理论研究——分布式OCC
Optimistic Methods for Concurrency Control in Distributed Database Systems 1981
Problems of Optimistic Concurrency Control in Distributed Database Systems 1982
这两篇论文提出了将原集中化数据库系统中的OCC应用到分布式数据库系统中的解决方案，第一篇论文的内容始终无法找到，本文猜测其基本思想为：
- 读取阶段与集中化数据库系统中的方案类似
- 全局事务的验证阶段可以分解为每个结点上的本地子事务的验证阶段，如果所有的子事务验证通过，则全局事务验证通过
- 验证和写入阶段与分布式系统中的2PC结合，验证属于prepare阶段，写入属于commit阶段
作者紧接着在第二篇论文中指出了OCC在分布式系统中面临的两个关键问题及可能的解决方案：
- 问题一
全局事务的验证阶段和写入阶段无法保证在临界区内顺序执行
- 可能的解决方案
- 强制前一个事务完成写入阶段后才能开始下一个事务的验证阶段
- 采用论文[1]的并行版本
- 问题二
全局事务中各本地子事务的验证阶段采用的可串行化标准可能不一致
- 可能的解决方案
- 使用全局事务号保证各结点在验证阶段使用相同的可串行化标准
理论研究——BOCC和FOCC
Observations on optimistic concurrency control schemes 1984
对论文[1]中OCC的串行版本进行了扩展，由此归类出两种OCC验证方案：
- BOCC （论文[1]方案）
检查待验证事务的读集是否与事务读取阶段完成的事务的写集有交集
- FOCC
检查待验证事务的写集是否与当前活跃事务的读集有交集
BOCC有如下缺点：
- 只读事务也需要验证阶段
- 只能中止当前验证事务
- 待验证事务的读集可能很大
- 对于长事务可能需要保留大量期间已提交事务的写集
反之，FOCC有如下优点：
- 只读事务无需验证阶段
- 只需与当前有限的活跃事务进行验证且验证事务的写集通常情况下较小
- 灵活的冲突策略，可选择延迟或中止验证事务，也可选择中止冲突事务
同时，作者从实现角度列举了OCC的一些通用问题：
- 高事务中止率
- 依赖同步机制避免事务饿死
- 读集/写集的维护浪费内存空间
- 读取阶段看到的数据库视图不一致
- 幻读问题不好解决
- 行粒度OCC读取阶段数据可能不一致
- 行粒度OCC写入阶段开销可能很大
- 行粒度OCC查询阶段流程复杂
- 页面粒度OCC会浪费空间并增大冲突中止概率
这篇论文总体看来对OCC的评价是负面的，但罗列出的通用问题也为后续的OCC研究者指出了改进的方向。
原型系统——MVCC+OCC+2PC
Distributed transaction management in jasmin VLDB 1984
这篇论文给出了OCC在分布式系统实现层面的解决方案，系统采用多版本存储，数据对象的粒度为一个页面，事务流程简要描述如下：
- 读取阶段
选取全局读时间戳，保证读取阶段能够看到一致的数据库视图。对于只读事务，在读取阶段结束后就可以提交。
事务写页面时会在系统内部创建影子页面。
- 验证阶段/写入阶段
使用两阶段提交完成验证和写入阶段：
1、获取一个全局的事务时间戳
2、由协调者消息通知相关各结点启动验证阶段
3、各结点统一使用该全局时间戳，基于论文[1]中提到的并行验证版本进行验证
4、协调者根据收到的所有的验证反馈决定发送提交还是中止消息
该论文从原型实现验证了OCC落地的可行性，并首次使用全局时间戳解决OCC读取阶段数据库视图不一致及全局事务中子事务串行化验证标准不一致的问题。
理论研究——动态调整提交时间戳减少事务中止率
Certification by intervals of timestamps in distributeddatabase systems 1984
论文认为[1]中的OCC是将事务进入验证阶段的时间作为事务提交时间戳并据此调度事务的可串行化，这会导致一些非必要的事务中止，提出一种在验证阶段基于访问数据的时间戳版本动态调整事务提交时间戳的方法，其基本思想如下：
基本数据结构：
- 在事务访问的每个结点上需要维护该事务的提交时间戳区间
- 每个数据对象维护一个最大读时间戳和最大写时间戳，这些时间戳均为已提交事务的提交时间戳
- 每个结点维护活跃事务表及其读集、写集
- 每个数据对象维护读/写过该对象的活跃事务
基本流程：
事务初始提交时间戳区间设置为0到正无穷
1、读取阶段
① 事务执行过程中访问任意结点上的数据时都需要传递客户端上的事务提交时间戳区间信息
② 进入临界区
③ 结点将客户端提交时间戳区间信息与本地维护的提交时间戳区间求交集得到最新的提交时间戳区间信息
④ 根据读写类型区别操作
- 如果是读操作，将事务提交时间戳区间的下限设置为数据对象的最大写时间戳+1；将事务加入数据对象的读事务列表中；将数据对象加入结点维护的事务读集中
- 如果是写操作，将事务提交时间戳区间的下限设置为数据对象的最大写时间戳与最大读时间戳之间的最大值+1；将事务加入数据对象的写事务列表中；将数据对象加入结点维护的事务写集中
⑤ 更新本地事务提交时间戳区间信息
⑥ 向客户端回传最新的事务提交时间戳区间信息及读取的值
⑦ 退出临界区
⑧ 客户端将回传信息与当前信息作交集得到最新的时间戳区间（通过这种方式使得结点能够感知到事务在其它结点上的依赖信息，便于早发现不符合串行化调度的事务）
2、 验证和写入阶段 （由于其它事务的读写操作与当前事务的验证阶段都会修改事务的时间戳区间，所以结点上的读写操作与验证时的调整操作需要互斥）
① 客户端向各参与结点发送验证/提交消息（消息中包含验证事务的最新提交时间戳区间）
② 提议阶段
- 参与结点将最新提交时间戳与本地合并后广播给集群中的所有其它结点
- 同步等待其它结点，最终得到一个所有结点一致的待验证事务提交时间戳区间
③ 时间戳选择阶段
- 如果该时间戳区间无效（空集），则中止事务
- 否则，在有效区间内选择一个具体的提交时间戳（所有结点上的时间戳选择策略要一致，该时间戳影响读冲突事务的上限/写冲突事务的下限，如果选择提交时间戳区间下限，意味着能够避免更多的写冲突事务的中止，增大读冲突事务的中止；反之，则效果相反）
④ 调整及写入阶段
- 对于验证事务读集中的每个数据对象，调整该对象上的所有活跃写事务的提交时间戳下限为验证事务提交时间戳+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的价值在新的数据库基础设施环境上又获得了学术界与工业界的重视。
生产系统——在验证阶段使用Paxos提交协议发现冲突
Megastore: Providing Scalable, Highly Available Storage for Interactive Services CIDR 2011
Megastore是少有的在内核层实现OCC的生产级分布式数据库系统，在Entity Group的数据分区级别使用MVOCC实现了串行化隔离级别的事务，同一分区一次只能执行一个事务，分布多副本间可以并发执行事务。一个OCC事务三个阶段的实现大致描述如下：
1、读取阶段
① 在任意副本均可发起强一致读；数据更新缓存在应用的事务私有内存
② 从多数派副本中获取最新事务提交时间戳及事务日志的位置（可以通过查询本地coordinator中副本的数据状态做优化）
③ 选择一个合适的副本（综合考虑本地性、响应时间、事务提交时间等），使用Paxos协议同步事务日志并将其应用到本地Bigtable中
④ 若选择了本地副本，则异步更新coordinator中副本数据状态为有效
⑤ 根据获取的事务提交时间戳从本地Bigtable中读取数据
2、验证阶段
① 从强一致读得到的事务日志中获取下一次写入事务日志的位置
② 选取一个比最新事务提交时间戳更大的值作为本次事务提交时间戳
③ 将事务私有内存中的更新打包到一个事务日志中
④ 发起一次完整的两阶段Paxos协议实例（可以优化为一阶段Paxos协议），一个事务日志位置只能由一个事务提交成功。如果成功，则将未成功接受当前事务日志的副本所对应的coordinator中的数据状态设置为失效，通知应用事务已提交；如果失败（prepare阶段发现提交的内容与达成一致的内容不匹配），则终止事务并重新执行
3、写入阶段（异步执行）
将更新数据异步写入Bigtable，清理应用事务私有内存数据
由上述流程可以看出，Megastore将事务局限在一个EG且只能串行化执行，并发冲突的控制粒度在事务级别，导致事务吞吐率非常低。虽然论文[15]中提出了一种提高Megastore事务提交吞吐量的可能方案，但Google内部最终还是放弃了Megastore，转而使用了Spanner（使用MV2PL并发控制技术），因为Spanner通过2PL+2PC实现了跨分区的事务。
生产系统——MVCC+OCC在内存数据库中的落地
High-Performance Concurrency Control Mechanisms for Main-Memory Databases VLDB 2012
真正把OCC在生产系统中落地的是内存数据库Hekaton，论文使用全内存的无锁哈希表存储多版本数据，数据的访问全部通过索引查找实现，一个OCC事务的生命周期实现如下：
1. 正常处理阶段（读取阶段）
① 获取事务开始时的当前时间作为读时间戳并赋予一个唯一的事务号，事务状态设置为active
② 在事务处理的过程中维护读集（指向读版本的指针）、写集（指向写版本的指针）、扫描集（重新执行扫描时需要的信息，如扫描条件）
③ 更新数据时（总在最新的版本上更新），版本可更新的判断：
a. 更新数据的end域无效或事务号所属事务已经中止
- 将原始版本的end域原子更新为当前事务号，防止其它事务的并发修改
- 链接新的数据版本并设置begin域为当前事务号
- 可能会出现更新begin域的事务处于preparing状态的数据版本，采取投机更新策略并记录提交依赖
b. 更新数据的end域事务号所属事务处于active或preparing状态
写写冲突，更新事务需要中止
④ 读取数据时，版本可见性的判断：
a. 读取数据的begin/end域都是有效的时间戳
如果读时间戳在begin/end之间，则可见；否则不可见
b. 读取数据的begin域是事务号
- 如果事务号所属的事务状态为active，仅对事务号所属事务可见
- 如果事务号所属的事务状态为preparing，读时间戳如果比事务提交时间戳大，则采取投机读策略并记录提交依赖（引入了级联中止问题）
- 如果事务号所属的事务状态为aborted，直接忽略
- 如果事务号所属的事务状态为commited，读时间戳如果比事务提交时间戳大，正常读取
c. 读取数据的end域是事务号
- 如果事务号所属的事务状态为active，仅对事务号所属事务不可见
- 如果事务号所属的事务状态为preparing，读时间戳如果比事务提交时间戳大，则采取投机忽略策略并记录提交依赖（引入了级联中止问题）；读时间戳如果比事务提交时间戳小，则可见
- 如果事务号所属的事务状态为aborted，可见
- 如果事务号所属的事务状态为commited，读时间戳如果比事务提交时间戳小，则可见
2、准备阶段（验证阶段）
① 获取当前时间戳作为提交时间戳，事务状态设置为preparing
② 读集有效性验证，检查读集中的版本是否依然可见；重新执行扫描集检查是否存在幻读
③ 等待提交依赖全部完成或当前事务是否已被其它事务设置为中止
④ 同步写redo日志
⑤ 将事务状态设置为commited
3、后处理阶段（写入阶段）
① 如果提交，将新数据的begin域和旧数据的end域设置为提交时间戳
② 如果中止，将新数据的begin域设置为无效，尝试将旧数据的end域设置为无效（如果已被其它事务更新则忽略）
③ 处理提交依赖，如果提交，则减少依赖该事务的其它事务的提交依赖计数；如果中止，则通知依赖该事务的其它事务中止
④ 清理事务表
生产系统——应用层OCC在分布式环境的价值
F1: A Distributed SQL Database That Scales VLDB 2013
F1是Google内部研发的分布式关系数据库，存储层基于Spanner，自建SQL层，用于Google最重要的广告业务。F1在Spanner之上基于行级的修改时间戳列实现了乐观事务并将其设置为默认配置，论文提到使用乐观事务有如下优缺点：
- 优点
- 容忍客户端的不正确行为（如无意义的长事务或未正常结束的事务）
- 长事务/交互式事务友好（没有锁超时导致中止的问题/用户查询期间不持有锁）
- 服务端重试友好，对用户透明
- 事务更新状态保存在客户端，利于容灾及负载均衡
- 易于实现投机写（检查读数据的版本变更发现冲突）
- 缺点
- 幻读问题需要借助其它手段避免
- 高数据竞争场景下的低事务吞吐率
其中关于OCC优点的描述来自生产级分布式环境运维的最佳实践经验，虽然只是应用层的简单实现，但也从另一方面验证了OCC在现代分布式数据库环境中的技术价值。
原型系统——动态调整提交时间戳减少事务中止率
MaaT: Effective and scalable coordination of distributedtransactions in the cloud VLDB 2014
这篇论文可以称为是为OCC摇旗呐喊的战斗檄文。论文首先提出了事务级云存储系统的概念，有代表性的系统如工业界的Spanner、学术界的Calvin、开源界的MySQL Cluster。与传统事务级云数据库的区别在于更加透明的数据分区，包括自动化的分区拆分、合并、迁移、负载均衡，这使得高效的跨结点分布式事务成为一个必选功能。
当前实现跨结点分布式事务的并发控制技术要么是2PL（Spanner、MySQL Cluster），要么是静态锁（Calvin，对事务操作进行静态分析后提前加锁），而OCC仅在应用层或Megastore中有所应用。OCC没有被普遍使用的原因有如下两点：
- 就适用场景来看，OCC适合于交互式或系统内部组件同步延时较大的场景，而在数据库系统内，磁盘、网络延时通常以毫秒计，OCC导致事务中止浪费计算资源的开销劣势远大于减少同步开销的优势
- 在分布式数据库实现中，OCC在写入阶段的原子提交协议依然依赖于2PC中的锁机制，没有彻底消除锁机制在云环境中可能会造成的死锁、降低事务吞吐量、系统资源利用率下降等问题
但是在云环境下，一个理想的云数据库应该满足如下要求：
- 在长事务、跨结点事务、高数据热点、高通信延时等场景下依然能够支持高事务吞吐率
- 高效的CPU利用率
- 高扩展性，减少系统内的同步点
- 高并发场景下没有系统性能抖动
- 系统无死锁或永久阻塞点
OCC在这种场景下是有技术优势的，因此，论文致力于实现一个消除2PC中的锁机制且大幅降低事务误中止率的分布式数据库系统MaaT。MaaT的理论基础基于论文[8]并在系统实现上进行了优化，其基本思想如下：
基本数据结构：
- 在事务访问的每个结点上需要维护内存事务表，记录事务的提交时间戳区间及当前状态（runing/validated/committed/aborted）
- 每个数据对象维护一个最大读时间戳和最大写时间戳，这些时间戳均为已提交事务的提交时间戳
- 每个数据对象维护读/写过该对象的活跃事务号
基本流程：
1、读取阶段
① 在事务请求结点上分配一个全局唯一事务号，并在内存事务表中初始化事务信息（提交时间戳区间设置为0到正无穷，状态设置为running）
② 事务执行过程中第一次访问任意远程结点上的数据时都需要在结点本地的内存事务表中建立事务相关初始信息
③ 根据读写类型区别操作
- 读操作
- 将事务号加入读对象的未提交读事务号列表
- 返回读对象数据、读对象上当前加写锁的活跃事务号及读对象的最大写时间戳（事务提交时需保证提交时间戳小于所有该对象上写事务的时间戳并大于最大写时间戳）
- 客户端将返回数据缓存在事务私有内存中
- 写操作
- 将更新数据写入客户端的事务私有内存中
2、验证阶段
① 客户端发送预写/验证消息到所有相关数据服务器（读写涉及到的服务器），消息中包括与服务器相关的读集、写集及在读取阶段从服务器获取的信息（所有在读对象上加写锁的活跃事务号及最大写时间戳）
② 预写（处理服务器上的写操作）
- 收到消息的服务器将事务号加入写对象的未提交写事务列表
- 写事务日志
- 获取在写对象上加读锁的活跃事务号及最大读提交时间戳（事务提交时需保证提交时间戳大于所有该对象上读事务的时间戳并大于最大读时间戳）
- 获取在写对象上加写锁的活跃事务号
③ 验证（保证事务的串行化顺序按提交时间戳排序，通过调整事务提交时间戳区间的上下限实现，调整的原则为尽量减少事务中止率）
- 对于读集中的对象，需要保证验证事务能在读对象的最大写时间戳之后提交
- 对于读对象上的加写锁事务，需要保证在验证事务之后提交
- 对于写集中的对象，需要保证验证事务在写对象的最大读时间戳之后提交
- 对于写对象上的加读锁事务，需要保证在验证事务之前提交
- 对于写对象上的加写锁事务，需要保证在验证事务之后提交
④ 验证结束后，如果验证事务的提交时间戳区间有效（下限小于等于上限），则将事务状态改为validated；否则，将事务状态改为aborted
⑤ 各结点通知客户端事务状态及调整后的提交时间戳区间
3、写入阶段
① 如果有结点返回aborted，则事务最终状态为aborted
② 如果所有结点均返回committed，则计算所有提交时间戳区间的交集，区间无效，则事务最终状态为aborted；否则事务最终状态为committed，此时客户端需要从有效区间中选取任意的时间戳作为该事务的提交时间戳
③ 客户端向相关数据结点发送事务提交或中止消息，提交消息中包含更新数据及确定的提交时间戳
④ 对于abort消息，数据结点将本地事务表中的事务状态改为aborted，删除该事务在数据对象上加过的锁并记录事务中止日志
⑤ 对于committed消息，数据结点将本地事务表中的事务状态改为committed，提交时间戳区间设置为客户端确定的时间戳，删除该事务在数据对象上加过的锁并记录事务提交日志
⑥ 对于读集中的数据对象，如果事务提交时间戳大于读对象的最大读时间戳，则将读对象的最大读时间戳设置为事务提交时间戳
⑦ 对于写集中的数据对象，如果事务提交时间戳大于写对象的最大写时间戳，则将写对象的最大写时间戳设置为事务提交时间戳并修改写对象的内容
论文提出的OCC实现方案被2017年的VLDB论文[21]作为测试OCC性能的参考实现，间接证明这里提出的OCC算法已经得到了学术界的认可，虽然论文[21]中对新OCC算法的性能与其它并发控制算法的比较仍然没有正面评价，但性能瓶颈已经转移到网络传输及CPU计算消耗，事务中止率及同步开销已成为性能瓶颈的次要因素，OCC的扩展性得到了提高。
原型系统——分布式验证
Centiman: Elastic, High Performance Optimistic Concurrency Control by Watermarking 2015
Centiman是一个在云环境基于NoSQL存储层+事务处理层（OCC）实现的具备串行化事务隔离级别的KV系统，由KV存储、事务处理子系统（包括处理结点和验证结点）、全局总控结点及客户端组成。
一个事务的完整生命周期分为如下阶段：
- 读取阶段
1. 处理结点维护一个本地的已应用事务提交时间戳（watermark，此时间戳之前的数据更新已写入kv存储）及其它节点已应用事务提交时间戳的缓存（缓存定期异步更新）
2. 每次读操作读取最新版本的kv，处理结点会计算最新的watermark时间（取全局最小），将key、version、watermark记入读集；写入操作需将kv缓存到处理结点的事务私有内存空间并将key记入写集
- 验证阶段
1. 只读和读写事务都需要走验证流程（优化：处理结点若发现待验证事务的所有读时间戳都小于事务第一次读时的watermark，则直接向客户端返回提交）
2. 处理结点给待验证事务赋值一个全局单调递增的提交时间戳
3. 将执行阶段记录的读集、写集按照key的某种分片规则分别发送到对应的验证结点，同时将事务私有内存中的数据异步写日志
4. 每个验证节点维护一个滑动时间窗口，小于滑动时间窗口到来的验证请求则直接返回验证失败；落在滑动窗口内的验证请求按照事务提交时间戳顺序进行处理并持续推进滑动窗口
5. 采用BOCC算法进行验证，对于事务在某个分片验证节点读集中的每个key，在验证结点缓存的事务写集中查找所有在读key时间戳和待验证事务提交时间戳之间提交的事务并验证读key是否与已提交事务的写集冲突 （优化：如果读key时间戳小于记录的watermark时间戳，则冲突检查区间可以缩小为在watermark时间戳和待验证事务提交时间戳之间）
6. 若冲突，则中止事务；否则，将待提交事务的写集缓存在验证节点用于后续新事务的验证并提交事务
7. 如果所有相关验证结点都同意提交事务，则发起验证的处理结点写提交日志并通知客户端，转入写入阶段；否则直接通知客户端事务已中止（可能存在有些验证结点认为应该提交，有些验证结点认为应该终止的状态，虽然事务整体是终止状态，但部分验证结点会存在冲突误判，论文中也是依赖watermark机制尽量减少误判）
- 写入阶段
1. 处理结点将事务本地内存中的更新内容写入kv存储（写入过程不要求保证原子性，允许其它事务读到部分写入的新值；通过kv存储的MVCC机制保证提交时间戳靠后的事务写入的数据不会被提交时间戳靠前的事务写入的数据覆盖）
2. 待全部写入成功后，更新本地watermark并异步记录事务已完成日志
这个系统的实现架构是具有一定代表性的，所有不支持ACID事务的NoSQL系统都可以参照此原型架构实现串行化事务隔离级别，后续我们要研究的FoundationDB架构也与此类似，当然生产环境的数据库还会考虑更具体的问题，比如幻读的处理、性能优化等。
至此，本文列举了OCC在这一时期在学术及工业界的主要结果，可以看出主要是性能优化，扩展性提高及生产级系统的实践。这里也忽略了一些有代表性的OCC系统，比如Percolator[13]、Silo[17]，因为这些系统在并发控制实现中使用了锁机制并存在写读阻塞的情况，虽然可以降低事务中止率，但却违背了OCC读写不阻塞、没有死锁的理念。
相比于前世理论研究的玩具，应用场景的缺乏，今生在内存及分布式数据库场景的落地，理论与工业界不断地性能优化等方面屡有建树，其技术带来的实际使用价值正越来越多地得到系统架构设计人员的认可，尤其是在跨分区、跨数据中心、跨地域分布式事务[22]，实现串行化隔离级别等现今分布式数据库尚未深入触碰的领域有着巨大的挖掘潜力。
结语
本文按照时间线简要回顾了OCC从诞生、理论研究、原型系统验证到生产系统落地的发展脉络，从中可以看出OCC技术从1980年代初发展至今将近40年的时间了，一路走来磕磕绊绊，从不适用于传统单机数据库，到在内存数据库中落地生根；从不适用于分布式数据库，到完美实现在NoSQL分布式数据库上支持ACID事务，甚至在跨分区事务、跨地域分布式系统的研究中也体现出了巨大的优势，有理由相信OCC技术的乐观、尽量减少事务同步开销的理念在未来的云环境中会有更多的运用。
在梳理OCC发展历程的过程中，笔者也逐渐总结出从技术角度应该如何分析实现了OCC的分布式数据库系统（仍有待完善）：
- 读取阶段
- 是否保证读一致性
- 使用事务私有内存还是共享数据内存
- 私有内存在客户端还是服务端
- 私有内存在服务端是单结点还是多结点
- 私有内存是否存储读入的数据
- 如何尽早发现冲突
- 验证阶段
- 事务提交时间戳如何分配
- 验证算法是BOCC还是FOCC模式
- 验证和写入阶段是否需要原子完成
- 如何解决幻读问题
- 如何降低事务中止率
- 如何避免事务饿死
- 如何降低长事务中止率
- 如何优化只读事务
- 写入阶段
- 是否要求原子性
- 使用了什么样的原子提交协议，2PC、Paxos还是不需要
身为一名程序员，笔者恪守Linus Torvalds大神说过的话：
talk is cheap, show me the code
把OCC在生产系统中落地的只有Microsoft的内存数据库Hekaton和Google的分布式KV数据库Megastore。虽然论文[14]、[15]、[16]对Megastore、Hekaton及相关的OCC进行了原理性的概要描述，但还是无法从代码实现细节上对OCC落地时可能遇到的实际问题进行解惑。好在苹果今年4月份开源了FoundationDB（又一个使OCC落地的新军），让码农有机会从代码实现层面上更详细地了解如何将OCC落地。
（本文仅代表作者个人观点，不代表OceanBase立场）
下期预告
本文是该系列文章的第二篇， 下一篇将致力于为你解读FoundationDB如何实现OCC。敬请期待！
参考文献
1. On Optimistic Methods for Concurrency Control 1979
2. Optimistic Methods for Concurrency Control in Distributed DatabaseSystems 1981
3. Problems of Optimistic Concurrency Control in Distributed Database Systems 1982
4. Concurrency control in database systems: A step towards the integration of optimistic methods and locking 1982
5. Empirical comparison ofdatabase concurrency control schemes 1983
6. Distributed transaction management in jasmin VLDB 1984
7. Observations on optimistic concurrency control schemes 1984
8. Certification by intervals of timestamps in distributeddatabase systems 1984
9. Distributed optimistic concurrency control with reduced rollback 1987
10. A New Distributed Optimistic Concurrency Control Method and a Comparison of its Performance with Two-Phase Locking 1990
11. Concurrency Control in Real-Time Database Systems: Optimistic Scheme vs Two-Phase Locking 1990
12. The End of an Architectural Era 2007
13. Large-scale Incremental Processing Using Distributed Transactions and Notifications 2010
14. Megastore: Providing Scalable, Highly Available Storage for Interactive Services 2011
15. Serializability, not Serial: Concurrency Control andAvailability in Multi-Datacenter Datastores 2012
16. High-Performance Concurrency Control Mechanisms for Main-Memory Databases 2012
17. Speedy Transactions in Multicore In-Memory Databases 2013
18. F1: A Distributed SQL Database That Scales 2013
19. Staring into theAbyss: An Evaluation of Concurrency Control with One Thousand Cores 2014
20. MaaT: Effective and scalable coordination of distributedtransactions in the cloud 2014
21. An Evaluation of Distributed Concurrency Control 2017
22. Carousel: Low-Latency Transaction Processing forGlobally-Distributed Data 2018
OceanBase技术交流群
想跟本文作者 龙逢 深入交流吗？
想认识蚂蚁金服OceanBase团队的一线技术专家吗？
扫描下方二维码联系蚂蚁金服加群小助手，快速加入OceanBase技术交流群！