注释：如下所提及的文献，请按照索引号对应参考《分布式数据库原理、架构与实践》一书的引用参考。
串行方案
串行方案需要把验证和写入阶段都放在一个临界区中，即下述tend在一个临界区中执行。如下算法只使用了前述条件一或条件二，没有使用条件三，原因是这个算法把写入阶段和验证阶段置于同一个临界区中，这样不管硬件中有多少个CPU/核，在验证和写入阶段，所有并发事务都是串行的，这严重限制了并发度，所以串行方案适合于只有一个CPU的场景。
tbegin = ( //事务开始create set := empty;read set := empty;write set := empty;delete set := empty;start tn := tnc) //事务开始的时候，用全局递增的逻辑时间戳tnc先为事务号赋值tend = ( //事务结束，在一个临界区内，先进行验证阶段的工作，然后再进行写入阶段的工作(finish tn := tnc; //获取本事务的结束时间点，注意这需要在临界区内进行valid := true;for t from start tn + 1 to finish tndo //验证阶段：遍历本事务生命周期内的并发事务[1]if(write set of transaction with transaction number t intersects read set)then valid := false; //如果本事务的读集和被遍历的事务的写集相交，则回滚本事务if validthen ((write phase); tnc := tnc + 1; tn := tnc)); //完成写阶段工作。然后全局的事务号tnc递增后，为本事务的事务号tn赋值，这表明事务号的获取是在事务成功提交才能取得，使得本事此后具有了“能用于判断是否与待验证事务存在冲突的身份”。这点影响着对上面循环条件的理解。注意这些工作都在一个临界区内完成。if validthen (cleanup)else (backup))
为了提高并发度，写阶段可被并发执行。该改进方案提供了更大的并行度，其所用技巧是把验证分为两个子阶段，在第一个子阶段进入临界区获取活跃事务号后退出临界区（允许其他并发事务继续执行），然后才验证本事务读集和其他并发事务的写集是否相交（注意只验证了并发事务的一部分），算法期待大部分并发情况能够被这个子阶段完成。然后再次进入临界区，再次获取活跃事务号，并且在临界区内完成“验证本事务读集和其他并发事务的写集是否相交”（注意只验证了并发事务的余下的那部分）的工作，算法期待少部分并发情况能够在这个子阶段完成，因此在临界区内应该尽量减少事务的验证过程，缩短在临界区的停留时间（提高了并发度）。被改进的算法如下：
tend:= (mid tn := tnc; //获取一个中间时间点，注意这需要在临界区内进行，获取事务号后退出临界区valid := true;for t from start tn + 1 to mid tn do //先判断本事务读集和其他并发事务的写集是否相交if (write set of transaction withtransaction number t intersects read set)then valid := false; //for循环在临界区外执行(finish tn := tnc; //获取本事务的结束时间点，注意这需要和如下代码共同在临界区内执行for t from midtn + 1 to finish tndo //然后判断本事务读集和其他并发事务的写集是否相交if (write set of transaction withtransaction number t intersects read set)then valid := false;if validthen (( writephase); tnc := tnc + 1; tn:= tnc));if validthen (cleanup)else (backup)) //完成后需要退出临界区
另外，对于只读事务，因其没有写入阶段故不会有写集存在，可不给这样的事务赋予事务号，这样避免只读事务被其他事务在验证阶段作为可能存在写集的事务而被纳入上述算法的FOR循环中。另外，上述算法中只读事务的“finish tn”值可以被赋值为读阶段完成时的txn的值。
对于长事务，根据前述算法，需要检查长事务开始时未提交的并发事务的写集。由于资源有限，数据库引擎只能维护最近的、有限个数的事务的写集，如果验证时无法找到事务号对应的写集，则中止待验证的长事务并重新执行。
对于事务的饿死现象，可记录事务验证失败的次数，若超过一定阈值，则在临界区内重新执行事务，这可以消除其它并发事务的干扰，从而解决事务饿死现象。
[1] 本事务生命周期内的并发事务，在文献[127]并没有给出事务完成状态的描述；但该算法本身表明为“在本事务生命周期内已经成功提交的事务”与待验证事务进行验证（使用事务号进行循环判断和冲突检测发现没有冲突才为本事务赋值事务号），这表明了原始的OCC算法遵从的是TO算法做可串行化。
并行方案
并行方案基于前述条件一和条件二，这种方案并发度更高，相较于前述的串行方案其主要改进，采用了两段临界区，目的是使得在临界区中的代码尽可能减少。并行方案是对串行方案的改进，所以两者的伪码基本一样。这个方案适合多CPU的场景，且写阶段（OCC的第三个阶段）相对于前面的读阶段（OCC的第一个阶段）耗时相差不多。相关实现如下：
tend := (<//进入临界区mid tn := tnc;>//退出临界区valid := true;for t from start tn + 1 to mid tn do //临界区外执行本循环if (write set of transaction withtransaction number t intersects read set)then valid := false;< 进入临界区finish tn := tnc;for t from mid tn + 1 to finish tn doif (write set of transaction withtransaction number t intersects read set)then valid := false;if validthen (( writephase); tnc := tnc + 1; tn:= tnc)>; 退出临界区if validthen (cleanup)else (backup))
文献[176]给出一个并发度更高的实现方式，采取了前述的前述条件一、条件二和条件三（满足了条件三就一定能满足条件二和一）。与串行方案相比，本方案除了对条件三进行判断外，事务号的赋值发生在写阶段完成之后，并且维护了一套已经完成读阶段但是尚没有完成写阶段的活跃事务的列表。相关实现如下：
tend = (//进入临界区(finish tn := tnc; //在临界区内执行，分配一个“暂时的”事务号，验证成功并完成写入阶段后将重新分配新的事务号给本事务finish active := (make a copy of active);//获取已经完成读阶段但没有完成写阶段的活跃事务集合的一份副本，此行为对应前述第三个条件active := active ∪ { id of thistransaction } ) ; //∪是并操作，进入验证阶段，把本事务加入活跃事务集合中。然后退出临界区valid := true;// 如下从“start tn + 1”开始验证，表明是从与本事务并发的事务进行验证，先于本事务已经完成的事务不必进行验证，这意味着隐含实现条件一for t from start tn + 1 to finish tndo //待验证的本事务读集和并发事务的写集是否相交（实现条件二的前半部分）if (write set of transaction withtransaction number t intersects read set)then valid := false; //相交则验证失败for i ∈ finish active do //判断是否满足前述第三个条件，本事务对应条件三中的Tjif (write set of transaction Tiintersects read set or write set)then valid := false;if validthen ((write phase); //执行写入阶段< tnc := tnc + 1; //进入临界区tn := tnc; //验证成功并完成写入阶段后重新分配新的事务号给本事务active := active - (id of thistransaction) >; //完成验证和写入阶段后，把本验证事务从活跃事务集合中去掉。然后退出临界区(cleanup))else (< active := active - { id oftransaction} >; //同上，在临界区内执行(backup))) //
前述的串行方案、并行方案，都可归类为BOCC方式（具体见4.3.2节），都是对待验证事务的读集与已经提交的事务的写集进行判断。除了BOCC方式外，还有一种方式——FOCC，关于这种方式可参见4.3.2节。
可串行化的实现
前面描述过实现可串行化的三个条件（在事务Tj进入验证阶段）。其中，条件一能保证事务之间是串行化的，但是并发度低。条件二确保在并发事务的写读不冲突的情况下，写写操作是串行化的。条件三的并发度最高，可确保在并发事务的写读、写写不冲突的情况下，读读操作是串行化的。
对于串行的可串行化的实现方式，文献[176]进行了详细介绍，其中包括对条件一和条件二的判断。对于条件二，该文献中介绍，可采用临界区的方式，实现读写操作互斥从而达到串行化的目的。
对于并行的可串行化的实现方式，文献[176]也进行了详细介绍，其中包括对条件一、条件二和条件三的判断，且包括临界区的使用。使用临界区会导致并发度在多核环境下的降低。
另外，有人提出，在验证读集是否发生了读写冲突、写集是否发生过写读冲突时，可先采取重新获取读集和写集的方式，然后与原始的读集和写集进行对比，以验证读写、写读冲突是否发生，此举的好处是该方法直接解决了幻读这样的数据异常（此种方式可不再用谓词锁的方式解决幻读异常）。但是，重新获取读集和写集对象，代价较大，尤其是在分布式系统跨节点获取读集、写集时代价更大，故这种方案是不可行的。对此，文献[120, 209, 220, 223]等都有相关介绍。
扫码加关注，知数行云，专业有深度
声明：本文禁止用于开发“任何软件程序,包括但不限于训练机器学习或人工智能(AI)系统”。
原文作者：那海蓝蓝知数行云；如有侵权，请联系管理员删除。
