注释：如下所提及的文献，请按照索引号对应参考《分布式数据库原理、架构与实践》一书的引用参考。

CMU大学的H.T. KUNG在文献[176]提出了OCC（Optimistic Concurrency Control，乐观并发访问控制）算法，开启了事务并发处理技术的乐观并发控制策略。

OCC算法的优势与不足

如图4-2所示，OCC算法把事务执行过程分为三个阶段：第一个阶段是读取阶段，这是事务过程最长，也就是最耗时的阶段，在这个阶段读取数据到事务私有空间中并对数据项进行修改；第二个阶段是验证阶段，通过TO算法实现并发访问冲突机制的仲裁过程，使得某个可能导致冲突的事务回滚以规避出现数据异常现象；第三个阶段是提交阶段，通过验证的事务完成提交操作，把修改的数据项合法地写入数据库中。

图4-2 OCC算法的三个阶段图

这三个阶段的划分，带来的优势非常明显：

1 事务处理性能高：事务处理效率的提升主要是依靠第一阶段通过读写互不阻塞来保证的，这极大地提高了读写、写读这两种情况的并发度，多核的硬件资源能够得到充分利用；并且对于只读事务因不被阻塞而倍显友好。

2 可避免死锁问题：OCC可以在第一阶段通过对读写对象排序，在第二阶段按序加锁可避免死锁。对于解决死锁问题，OCC的这两点明显比封锁并发访问控制算法更有优势。这两点优势使得OCC在分布式事务处理、高数据热点、高通信延时等场景下依然能够支持高事务吞吐率，在高并发场景下没有明显的系统性能抖动现象（文献[169]通过实验表明高竞争情况下OCC算法性能不高）。

3 数据一致性的正确性得到保证：正确性是在第二阶段得到保证的，其原理是通过事务冲突关系构造有向图检测是否存在有环的情况，然后通过回滚某个事务破除环的存在，达到解决事务冲突的目的；而写写冲突是在验证阶段通常通过封锁机制保证。但在工程实现中，保证正确性的方式有多种，如文献[220]中介绍了OCC改进算法，这种算法在验证阶段检查本事务的读集，如果读集被其他并发事务写过则触发回滚以避免数据不一致，从而不用构造用于检测是否存在有环的有向图。

当然，除了优点，OCC也有其不足之处，而且OCC的缺点较为明显：

1 OCC只适用于冲突少的场景：传统观念认为，事务回滚的开销非常大，尤其在分布式系统中，回滚涉及多个节点、涉及网络消息传递，所以回滚带来的开销可能会远大于封锁同步的开销。但应用封锁并发访问控制算法进行单机系统的死锁检测，开销也很巨大，分布式系统下的死锁检测的开销将更大，且检测到死锁后依旧需要通过回滚其中的某个事务来解决冲突。另外，OCC在验证通过前，并没有真实修改数据库中的数据，因此回滚操作只是放弃事务私有空间中被修改过的数据，操作速度很快，回滚代价小。

2 回滚方式使得事务被整体撤销：OCC依赖于回滚操作以解决事务冲突，而回滚操作使得一个事务之前成功执行过的SQL语句全部被回滚。相较于封锁并发访问控制算法，OCC算法通常事务只是在某个时刻阻塞SQL语句，之前成功执行过的SQL语句在没有发生死锁的情况下，是不会被回滚掉的，因此会节约部分计算资源。

3 OCC对写写冲突机制的解决依赖于封锁并发访问控制算法：OCC没有独立解决写写冲突的机制，因此可以认为OCC是对于封锁并发访问控制算法的改进，或者说OCC依赖封锁机制解决写写冲突。

4 在分布式系统中OCC在提交阶段依赖于2PC机制：在分布式数据库实现中，OCC在第三阶，依赖于2PC中的锁机制实现原子写操作，如果不在第二阶段按序对操作对象加锁，则不能彻底消除锁机制造成的死锁、降低事务吞吐量、系统资源利用率下降等问题。文献[157]讨论了一个基于OCC机制可消除2PC中的锁机制、且能大幅降低事务误回滚率的分布式数据库系统，可供参考（参考4.3.4第二小节）。

5 维护的数据量大：OCC在第一阶段维护读集或写集，对于读写数据量大的事务而言，需要维护的读集/或写集（还包括删除集）数据量大，且在第二阶段验证的过程中耗时增加。不利于长事务或大事务执行，OCC因此不适合用于于分析性系统使用。

OCC算法的应用场景非常多：

1 OCC算法可应用到分布式数据库系统中，具体参见文献[115，116]。

2 OCC算法可以应用到生产系统中，具体参见文献[120，121，122]。

3 OCC可以应用到内存数据库Hekaton中，使用全内存的无锁哈希表存储多版本数据，数据的访问全部通过索引查找实现。并发访问控制采用OCC技术（相关内容参见文献[120]。

4 在分布式系统中可以实现OCC，具体参见文献[121]，该文献简单介绍了在客户端实现OCC的几个优点（主要是强调在客户端实现OCC带来的便利。文献[54]也提出在客户端实现分布式事务处理）。

5 Megastore作为生产级分布式数据库系统在内核层实现了OCC，在Entity Group的数据分区级别使用MVCC和OCC技术，实现了串行化隔离级别的事务。但是，其同一分区一次只能执行一个事务，分布多副本间可以并发执行事务。具体参见文献[122]。

6 Centiman是一个在云环境基于NoSQL存储层用OCC技术在事务处理层实现的具备串行化事务隔离级别的KV系统，由KV存储、事务处理子系统（包括处理结点和验证结点）、全局总控结点及客户端组成。具体参见文献[123]

数据库系统可采用OCC框架实现事务处理，具体参见文献[124]。该文献还介绍了基于Log-structured的存储以及在Log-structured存储的基础上用树做索引（Tree-structured）的数据库系统，，但没有深入介绍并发访问控制的相关算法。

OCC的三个阶段

第一个阶段是读取阶段，这个阶段的主要工作包括：

（1）读操作首先访问事务私有内存空间，如果不存在，则从数据库中读取并可选地缓存在事务私有内存空间中，构成事务的读集。这种方式避免了不可重复读数据异常。

（2）更新（UPDATE语句）造成的写操作的结果缓冲在事务私有内存空间中，构成事务的写集，并把新写入的值存入copy(n)对象，以便之后读写过的对象不再从数据库中获取。原算法构造了一个copy(n)对象，新写入的值先存入copy(n)对象，然后并入写集，而对此对象的读取实则是读取的是copy(n)对象。。

（3）由删除（DELETE语句）造成的写操作，可维护独立的删除集合。由插入（INSERT语句）造成的写操作，可维护独立的创建集合。

第二个阶段为验证阶段（Validation Phase），主要工作为：

（1）根据某种可串行化标准检查待提交事务是否满足可串行化调度。具体方式如下，本质是基于TO算法确认提交顺序。

（2）保证可串行化，即在事务完成第一阶段的操作后获取事务的提交时间戳，在事务成功完成验证再为事务号赋值。在事务Tj进入验证阶段后，确定Tj与其他并发的事务（如Ti）的关系（Ti的事务号<Tj的事务号），且需满足如下三个条件，此三个条件可用图4-3表示：

n条件一： Ti的写集完成早于Tj读集的完成，这表明Ti和Tj完全是串行执行的。如果不满足本条件，则判断是否满足如下条件。

n条件二： Ti和Tj并发，但Ti的写集和Tj的读集不相交，即没有写读冲突，且Ti的写集完成早于Tj写集的完成即没有写写冲突发生。如果不满足本条件，则判断是否满足如下条件。

n条件三： Ti的写集和Tj的读集或写集不相交表明没有写读冲突或写写冲突，且Ti的读阶段完成早于Tj的读阶段。

事务号是递增的逻辑全局时间戳，在事务完成第一阶段的操作后为事务号赋值。

如果“Ti的事务号>Tj的事务号”，则表明Tj先于Ti发生了读阶段操作，故不能满足前述条件三，需要回滚事务Ti或Tj。

第三个阶段为写入阶段（Write Phase），主要工作为：

（1）将事务私有内存中的写集中的数据写入数据库并使这些数据可见，按照删除集中的数据删除数据库中的真实数据。

（2）只读事务被优化，不需要执行写入阶段，但只读事务可能带来多种读异常，需要在验证阶段进行验证。

图4-3 OCC允许的并发情况图

另外，文献[176]提出了两种满足上述条件实现验证阶段的方案，一种是串行方案，一种是并行方案，这两种方案的差别在于解决图4-3中所示的不同情况：(1)是完全是串行执行；(2)是接近串行执行；(3)对应的是并发的事务故方案，这种方案称为并行方案。在给出这两种方案前，文献[176]给出了针对读集、写集等的维护方式。

注意，上面所说的“事务私有内存”维护读写集，相对于编程实现来说表述并不精准。对于多进程架构下的数据库系统，如PostgreSQL，每个事务的载体都是一个独立的进程，并发事务意味着有多个进程存在，而读写集要放在一起比较，只有存放在共享缓存区中，读写集才能被每个进程读取到，从而方便判断本事务/进程的读集和其他并发事务/进程的写集是否相交。若是依靠事务私有内存存放读写集，则需要在验证阶段判断读写集是否相交时从其他事务的读写集进行大量的内存拷贝，性能不高。

读写集维护方式

读写集的维护很重要，这是OCC算法的基础。文献[176]提出如下针对读写集进行维护的方法。

tcreate = (  //对应INSERT操作，但是对于UPDATE操作生成的新数据项是否在此集合中（多数数据库的实现方式是先删除旧数据，再生成一个新数据），作者没有深入讨论，而是采用了如下方法来维护写集，故认为UPDATE操作对应写集 n := create; create set := create set ∪ {IL} ; return n) twrite(n, i, u) = ( //写集的维护 if n ∈ create set  //该写（插入）操作所在的事务生成的新值，将进入写集 then write(n, i, u) else if n ∈ write set  //再次改写数据库原有的值，生成该值的副本（为这样的数据维护一个副本集合及copyies），且使该副本进入写集 then write(copies[n], i, u) else ( //否则，首次改写数据库原有的值，生成副本，并使该副本进入写集 m := copy(n); copies[n] := m; write set := write set ∪ {n); write (copies[n], i, u))) tread(n, i) = (  //读集的维护 read set := read set ∪ {n} ;  //把读到的数据都并放入读集。即更新、删除等操作读取过的数据也进入读集 if n ∈ write set  //如果读取的数据在写集中，则从写集读取。工程实现中，写集副本要存入读集，此点很重要[1] then return read (copies[n], i) else return read (n, i)) tdelete (n) = (  //删除集合的维护 delete set := delete set U (n})

[1] 因本事务写过的数据也被维护在读集中，所以使用本事务的读集和其他并发事务的写集做判断，相当于用本事务的写集和其他并发事务的写集做判断，在避免读写冲突时，也可避免写写冲突。文献[157]也描述了读写集的关系：“Typically, the write set of T is subset of the read set of T”（T事务的写集通常是T事务的读集的子集），但是也有不同实现方式，如文献[157]不使用读集和写集做冲突验证，故不需要构造读写集之家的关系。想要了解把写集作为读集的子集的内容，也可参考文献[220]。

扫码加关注，知数行云，专业有深度

声明：本文禁止用于开发“任何软件程序,包括但不限于训练机器学习或人工智能(AI)系统”。