「分布式技术专题」并发系列三：乐观并发控制之理论研究

原创天云数据 2021-02-20

920

以时间轴的方式对不同时期的有代表性的论文（从理论研究、原型系统、生产系统三个维度分类）进行了梳理，带你简要回顾一下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，作者直接列举了基于锁的并发控制协议的五宗罪：

加锁协议开销大，对于不会改变数据库约束完整性的只读事务也需要加读锁保护以防止别人修改；对于可能造成死锁的加锁协议还需要额外增加死锁检测开销
为了避免死锁，需要定制各种复杂的加锁协议
在持有锁的情况下可能会等待I/O操作，会大幅降低系统整体的并发吞吐量
加锁事务回滚时必须持有锁，直到事务回滚结束，降低了系统整体的并发吞吐量
只有在最坏情况下才需要加锁；很多真实的应用场景往往是高并发低竞争的
作者据此提出了一种新的乐观并发控制方法用于解决上述问题（所谓的乐观是针对并发事务冲突概率极低的工作负载场景），该方法将一个事务的生命周期划分为三个阶段：

• 读取阶段
– 所有更新操作缓冲在事务本地内存空间中，维护事务的写集
– 所有读取操作先访问事务本地内存空间，若不存在则从数据库中读取并可选地缓存在事务私有内存空间中，维护事务的读集

• 验证阶段
根据某种可串行化标准检查待提交事务是否满足可串行化调度

• 写入阶段（只读事务不需要）
将事务私有内存中的更新数据写入数据库使其全局可见

假设系统中每个事务能够被赋予全局唯一的事务号，则有事务号Ti和Tj，且Ti<Tj，可以将系统内是否存在一个与事务号顺序等价的并发事务调度序列作为可串行化标准，则检查事务Tj是否符合可串行化（即Ti在Tj之前完成），需满足如下三种条件之一：

Ti在Tj开始读取阶段前完成写入阶段，即Ti在Tj之前提交
Ti的写集与Tj的读集不相交，且Ti在Tj开始写入阶段前完成写入阶段
Ti的写集与Tj的读集和写集都不相交，且Ti在Tj完成读取阶段前完成读取阶段
作者提出了两种满足上述条件的验证阶段实现方案：
串行方案（事务并发满足条件1或2）
事务开始
获取当前已提交的事务号
事务结束
① 进入临界区
② 获取当前已提交的事务号
③ 验证事务开始和结束期间提交的事务的写集与待验证事务的读集是否相交
④ 相交，则发现冲突，退出临界区并中止待验证事务
⑤ 不相交，则验证成功，执行写入阶段（如果是只读事务无需执行）并递增提交事务号
⑥ 退出临界区
并行方案（事务并发满足条件1或2或3）
事务开始
获取当前已提交的事务号
事务结束
① 在临界区内获取当前已提交的事务号/获取当前活跃事务列表/将自身加入活跃事务列表
② 验证事务开始和结束期间提交的事务的写集与待验证事务的读集是否相交
③ 验证活跃事务（这些活跃事务均已完成读取阶段，读集和写集不会再发生变化，可理解为进入验证的事务列表）的写集与待验证事务的读集和写集是否相交
④ 相交，则发现冲突，在临界区内将本事务从活跃事务中去除并中止待验证事务
⑤ 不相交，则验证成功，执行写入阶段（如果是只读事务无需执行）
⑥ 在临界区内递增提交事务号并将本事务从活跃事务中去除
在系统实现中，还需要考虑两种特殊情况的解决方案：
长事务
根据上述规则，需要检查长事务开始时未提交的事务的写集。由于数据库系统只能维护有限的事务写集，作者建议只维护最近事务的写集，如果验证时无法找到事务号对应的写集，则中止待验证事务并重新执行。
饿死现象
验证失败时事务需要中止并重新执行，存在一种极端情况使得事务持续地中止并重新执行，作者建议记录事务的失败验证次数，若超过一定阈值，则在临界区内重新执行事务，彻底排除其它并发事务的干扰。
显然，上述方案都是针对单数据版本的集中化数据库系统，在分布式数据库系统中的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研究者指出了改进的方向。