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

BOCC与FOCC

文献[129]中总结了两种规则以避免读和写操作的冲突。

规则1：没有读取依赖。

q规则1-1：Ti不读取由并发事务Tj修改的数据。

q规则1-2：Tj不读取由并发事务Ti修改的数据。

规则2：禁止覆盖。Ti不会覆盖由并发事务Tj写入的数据，反之亦然。

文献[129]在OCC算法的上述规则，提出Backward oriented optimistic CC（BOCC）和Forward oriented optimistic CC（FOCC）两种变种算法。

BOCC算法的缺点是事务完成后，其写集需要保留一段时间，因为并发的事务需要用此写集与其自身的读集做冲突判断，尤其是长事务需要保留大尺寸的写集。文献[104]在BOCC的基础上提出ROCC（Range OCC）算法。该算法指出，已经完成事务的写集可以按数据项合并在一起，构成谓词范围，即多个事务的写范围谓词可以合并为一个，这样将减少与写集的判断次数）。

另外，对于BOCC算法，只读事务也需要验证阶段，不利于AP型应用。BOCC算法实现过程如下：

VALID := TRUE; //Tj进入验证阶段FOR Ti := Tj-start+1TO Tj-finish DO //从Tj事务开始的每一个并发事务Ti IF RS(Tj) ∩ WS(Ti) ≠ Ø  THEN     //Tj读集如果与Ti事务的并发事务且在本事务验证阶段已经成功提交事务的写集相交非空，则有冲突 VALID := FALSE;IF VALID THEN COMMIT ELSE ABORT; //冲突发生，只能回滚事务

如上算法过程所示，时间可能消耗在循环次数上，即Tj的并发事务数越多，验证算法花费的时间越多（对于OCC算法，验证算法花费的时间多，可能导致冲突发生的概率增加，从而使得并发冲突发生的概率更大，由此形成恶性循环），所以这是一个可优化点。

对于BOCC算法的实际应用，大家可以参见文献[117、176、219、239、240、241]等。

FOCC算法的优点较BOCC多：首先只读事务无需验证阶段；其次只需要与当前的活跃事务进行验证（但确认活跃事务也是一个耗时操作）；再次，该算法有着便于解决冲突的能力（可选择延迟或回滚正在进入验证阶段的事务，也可选择回滚冲突事务）。总之，FOCC利于HTAP型应用。

FOCC算法的实现过程如下：

VALID := TRUE; //Tj进入验证阶段FOR Ti := Tact1TO Tactn DO //从Tj事务开始到Tj事务进入验证阶段，这之间的所有活跃事务 IF WS(Tj) ∩ RS(Ti) ≠ Ø THEN  //Tj写集如果与活跃事务的读集相交非空，则有冲突 VALID: = FALSE;IF VALID THEN COMMITELSE RESOLVE CONFLICT; //冲突发生，可不采用类似BOCC这样的算法只能回滚事务，而是采用某种解决冲突的机制

另外，文献[129]讨论了OCC机制中的几个重要的问题：

（1）正确性方面：

q幻象异常不好解决：OCC读操作优先从事务的私有内存中获取所需数据，因此可避免不可重复读异常。但是，别的事务生成的数据是不被本事务的读集写集维护的，因此不能发现幻象异常。如果想避免幻象异常，可在所读对象所在的节点维护一个谓词锁表，如CockroachDB的Timestamp Cache机制。

q读取阶段看到的数据库视图不一致：这个问题对于封锁机制同样存在，不是只有OCC才存在这样的问题。只有保留历史数据，才能获得一个静态的点，才能在一个事务内部动态执行的过程中始终获取一致的视图（结合MVCC技术基于Snapshot进行读取可解决该问题）。

（2）性能方面，OCC比封锁机制有着更高的事务回滚率（但文献[201]发表于1983年，数据库实现的技术已经今非昔比，该文的是否还有借鉴意义？文献[168、169]在不同负载下比较了OCC和2PL等并发访问控制算法之间的性能差异，有着更强的说服力）。其中，文献[201]中的测试数据被文献[129]引用：This study reveals clearly that validation conflicts in optimistic CC schemes cause transactions to be aborted to a much higher percentage than do deadlocks in the locking oriented schemes (with a parallelism of 32 transactions 36% compared to 10%). 其含义为：这项研究清楚地揭示了OCC方案中的验证冲突导致事务的回滚率远远高于面向锁方案中的出现死锁时的回滚率（32个并发事务，OCC的回滚率36%，锁回滚率为10%）。但笔者不认同该观点，期待将来有机会对多种并发访问控制算法的回滚率做定量研究，测试表明OCC算法的回滚率低于封锁类算法。注意，前述内容时对于OCC和Locking算法从回滚率的角度对比的。但是，实际系统中（如MySQL5.7版本）如果存在热点数据的并发冲突，且死锁检测已经致使整个系统不可用（事务处理量保持在每秒个位数以内甚至为0），那么单纯比较回滚率的意义就不大了。而OCC因为不必做死锁检测，所以可以避免出现死锁，，单从这个角度来说，OCC的可用性高于封锁机制。

（3）系统实现方面：

q读集/写集的维护浪费内存空间：XXX，尤其是长事务，需要更大的私有内存空间。

q推迟了完整性约束的检查工作：完整性工作的检查被推迟到了验证或提交阶段执行。

q写入阶段工作量集中：所有的写入操作都发生在写入阶段，这可能引发大量的IO；而且写入阶段不只影响是数据，还影响索引、约束的检查、触发器的执行等，这些工作集中在一起完成，需要仔细斟酌。

q读写对象，是选择行级还是页面级别[1]：OCC的实现依赖行级，这会导致读取阶段数据可能不一致（结合MVCC解决，参见4.3.3节）、行级查询阶段流程复杂，而页面级会浪费空间并增大冲突概率、提高了回滚率等。文献[129]认为“基于页面级的数据实现OCC是唯一的选择（Page-level CC seems to be the only choice for optimistic CC in a complex DB environment.）”。

其他方面，诸如依赖同步机制避免事务饿死等，都需要仔细斟酌。

[1]早期的数据库是磁盘型数据库，数据的读写单位在系统内部实现是以页面（Page）为操作单位。

ROCC

文献[218]针对K-V存储系统提出一个新算法——MVRCC （a multi-version timestamp ordering concurrency control for logical ranges，逻辑范围内的多版本时间戳排序并发控制），，该算法提出logical ranges（逻辑范围）的概念用以在实现事务处理时，解耦数据存储（Storage）和数据访问（access）模块。而文献[104]借鉴了逻辑范围（logical ranges）概念，提出一个新的OCC算法——ROCC（Range Optimistic Concurrency Control，范围乐观并发控制）。

如图4-4所示，ROCC算法把DML、DQL语句中的WHERE语句中的谓词（图4-4 a所示，基于全局活跃事务列表，从事务的角度进行验证。其中，事务T2、T3、T4、T5已经在事务Tx读取数据阶段成功提交，但事务Tx的开始时间是事务T2的开始时间，即事务T2、T3、T4、T5与Tx是处于并发阶段；事务Tx读取事务T5写过的数据项，使得Tx只能通过回滚才能满足可串行化）转换为对数据访问的一个个片段（对数据的访问范围，如查询学生成绩表中成绩大于90分的学生时，“score>90”即是一个片段，如图4-4 b所示，从谓词范围片段的角度进行验证），然后通过这样的片段，再定位每个片段内正在执行的事务（如R2片段对应执行的事务是T1、T3、Tx），如果有多个正在执行的事务，事务Tx处于验证阶段，则根据Tx读取数据的范围找到Rn区域，此时可发现事务T5写过的数据项y落在了Tx读过的范围内。这两个事务在片段内重叠表明冲突存在，使得Tx不得不回滚才能满足可串行化。

ROCC算法对当前事务的读集和并发事务的写集进行冲突判断，这一点其实和前述的FOCC基本思想一样，只是ROCC算法验证事务冲突的角度从遍历并发事务转换为了谓词范围的定位，这样有助于缩小冲突检测时对并发事务的遍历判断次数。而谓词的范围（谓词是SQL语句中Where子句中的条件表达式），在SQL优化阶段执行完对谓词的逻辑优化（如常量传递、表达式计算、消除似码、等式变换、不等式变换、布尔表达式变换等[1]）后就可以精准获得，而不必等到具体的数据项获取后（事务生命周期已经开始）才在OCC思想的指导下构造出读集，所以ROCC算法可以提前构造一个逻辑的读集（事务生命周期开始前即可构造逻辑上的基于范围的读集），这为提前判断并发事务的冲突关系提供了可能，由此可以构造自适应的、确定性的并发访问控制算法。

以谓词锁定的读写范围为单位，如果数据项值域范围较小，则冲突概率会增大，这将影响并发度的提高，不利于以“细粒度”的思维方式（详见4.4.3节）进行冲突判断。如果结合细粒度的思维方式，则图4-4 b)所示中的R1、R2、Rn可以是元组对象，也可以是字段对象，这使得ROCC的算法适用范围变广。另外，一条SQL语句的WHERE子句如果是复杂的，其谓词表达式也是复杂的，那么构造图4-4 b所示的R1、R2、Rn等时，与复杂的谓词表达式不存在必然关系，可以按照被访问的“对象”进行构造。

图4-4文献[218]给出的ROCC算法示意图

[1] 参考《数据库查询优化器的艺术:原理解析与SQL性能优化》2.2.4节

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

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