6.3.3 数据库的并发控制机制
所谓并发控制机制，就是保证并发执行的事务在某一隔离级别上的正确执行的机制。并发控制由DBMS的调度器负责，事务本身并不感知。如图6-12所示，调度器将多个事务的读写请求，排列为合法的序列，使之依次执行。
图6-12 调度器对并发事务的调度
这个过程中，对可能破坏数据正确性的冲突事务，调度器可能选择下面两种处理方式：
延迟（Delay）：延迟某个事务的执行到合法的时刻。
终止（Abort）：直接放弃事务的提交，并回滚该事务可能造成的影响。
可以看出Abort比Delay带来更高的成本。
下面介绍不同的并发控制机制在不同的情况下的处理方式。
图6-13描述了数据库并发控制采用的常见实现方法，图中从纵横两个维度，对常见的并发控制机制进行了分类：
图6-13 数据库并发控制方法分类
1）乐观程度
不同的实现机制，基于不同的对发生冲突概率的假设，悲观方式认为只要两个事务访问相同的数据库对象，就一定会发生冲突，因而应该尽早阻止；而乐观的方式认为冲突发生的概率不大，因此会延后处理冲突的时机。如图6-13横坐标所示，乐观程度从左向右增高。
基于锁：最悲观地实现，需要在操作开始前，甚至是事务开始前，对要访问的数据库对象加锁，对冲突操作延迟。
基于时间戳：乐观地实现，每个事务在开始时获得全局递增的时间戳，期望按照开始时的时间戳依次执行，在操作数据库对象时检查冲突并选择延迟或者终止。
基于验证：更乐观地实现，仅在提交（Commit）前进行验证，对冲突的事务终止。
可以看出，不同乐观程度的机制本质的区别在于，检查或预判冲突的时机，锁在事务开始时，时间戳在操作进行时，而验证在最终提交前。相对于悲观的方式，乐观机制可以获得更高的并发度，而一旦冲突发生，终止事务也会比延迟事务带来更大的开销。
2）单版本VS多版本
如图6-13纵坐标所示，相同的乐观程度下，还存在多版本的实现。所谓多版本，就是在每次需要对数据库对象修改时，生成新的数据版本，每个对象的多个版本共存。读请求可以直接访问对应版本的数据，从而避免读写事务和只读事务的相互阻塞。当然多版本也会带来对不同版本的维护成本，如需要垃圾回收机制来释放不被任何事务可见的版本。
需要指出的是这些并发控制机制并不与具体的隔离级别绑定，通过冲突判断的不同规则，可以实现不同强度的隔离级别，下面基于可串行化具体介绍每种机制的实现方式。
（1）单版本实现
①基于锁：基于锁实现的调度器需要在事务访问数据前加上必要的锁保护，为了提高并发，会根据实际访问情况分配不同模式的锁，常见的有读写锁、更新锁等。最简单地，需要长期持有锁到事务结束，为了尽可能在保证正确性的基础上提高并行度，数据库中常用的加锁方式称为两阶段锁（2PL）。需要注意的是2PL并不能解决死锁的问题，因此还需要有死锁检测及处理的机制，通常是选择死锁的事务进行终止。
②基于时间戳：基于时间戳的调度器会在事务开始时分配一个全局自增的时间戳，这个时间戳通常由物理时间戳或系统维护的自增id产生，用于区分事务开始的先后。
基于时间戳的调度器会假设开始时时间戳的顺序就是事务执行的顺序，当事务访问数据库对象时，通过对比事务自己的时间戳和该对象的信息，可以发现这种与开始顺序不一致的情况，并做出晚读、晚写等不同的应对。
③基于验证：基于验证的方式，也称为乐观并发控制（Optimistic Concurrency Control，OCC），因为它比基于时间戳的方式要更加乐观，将冲突检测推迟到提交（Commit）前才进行。不同于时间戳方式记录每个对象的读写时间，验证方式记录的是每个事物的读写操作集合，并将事物划分为3个阶段：
读阶段：从数据库中读取数据并在私有空间完成写操作，这个时候其实并没有实际写入数据库。维护当前事务的读写集合，RS、WS。
验证阶段：对比当前事务与其他有时间重叠的事务的读写集合，判断能否提交。
写阶段：若验证成功，进入写阶段，这里才真正写入数据库。
同时，调度器会记录每个事务的开始时间START（T），验证时间VAL（T），完成写入时间FIN（T），基于验证的方式是假设事务验证的顺序就是事务执行的顺序，因此验证的时候需要检查访问数据顺序可能不一致：
RS（T）和WS（U）是否有交集，对任何事务U，FIN（U）＞START（T），如果有交集，则T的读可能与U的写乱序。
WS（T）和WS（U）是否有交集，对任何事务U，FIN（U）＞VAL（T），如果有交集，则T的写可能与U的写乱序。
（2）多版本实现
对应上述每种乐观程度，都可以有多版本的实现方式，多版本的优势在于，可以让读写事务与只读事务互不干扰，因而获得更好的并行度，也正是由于这一点成为几乎所有主流数据库管理系统的选择。为了实现多版本的并发控制，需要给每个事务在开始时分配一个唯一标识TID，并对数据库对象增加以下信息：
txd-id：创建该版本的事务TID；
begin-ts及end-ts：分别记录该版本创建和过期时的事务TID；
pointer：指向该对象其他版本的链表。
其基本的实现思路是，每次对数据库对象的写操作都生成一个新的版本，用自己的TID标记新版本begin-ts及上一个版本的end-ts，并将自己加入链表。读操作对比自己的TID与数据版本的begin-ts和end-ts，找到其可见最新的版本进行访问。根据乐观程度多版本的机制也分为3类：
①两阶段锁（Two-phase Locking，MV2PL）：与单版本的2PL方式类似，同样需要跟踪当前的加锁及等待信息，另外给数据库对象增加了多版本需要的begin-ts和end-ts信息。写操作需要对最新的版本加写锁，并生成新的数据版本。读操作对找到的最新的可见版本加读锁访问。
②时间戳顺序（Timestamp Ordering，MVTO）：对比单版本时间戳方式，对每个数据库对象记录的读时间戳（Read TimeStamp，RT）、写时间戳（Write TimeStamp，WT）以及事务提交标志（Commited flag，C）信息外，还增加了标识版本的begin-ts和end-ts。
在事务开始前获得唯一递增的开始时间戳（Start TimeStamp，TS），写事务需要对比自己的TS和可见最新版本的RT来验证顺序，写入是创建新版本，并用自己的TS标记新版本的WT，不同于单版本，这个WT信息永不改变。读请求是读取自己可见的最新版本，并在访问后修改对应版本的RT。
③乐观并发控制（Optimistic Concurrency Control，MVOCC）：对比单版本的验证（OCC）方式，同样分为三个阶段，读阶段根据begin-ts，end-ts找到可见最新版本，不同的是在多版本下读阶段的写操作不在私有空间完成，而是直接生成新的版本，并在其之上进行操作。