并发控制

设计原则

事务的并发控制首先要保证并发执行的正确性，满足可序列化要求，即并发执行的结果和某种串行执行的结果是一致的，然后在满足正确性的前提下尽可能地获得最高的并发度。当然在某些业务场景下，可以适当牺牲部分正确性（即接受某些异常），从而获得更高的并发性能。并发控制大体分为悲观算法和乐观算法，为了尽可能深入了解各种算法的优缺点，本章在Oracle、MySQL的基础上增加了PostgreSQL、CockroachDB和VoltDB。Oracle、MySQL、PostgreSQL采用了悲观控制策略，同时通过MVCC进一步提高并发性，而PostgreSQL在此基础上实现了Serializable Snapshot Isolation。CockroachDB完全采用了乐观控制，是乐观控制的开源和商业化实现。VoltDB在并发控制策略上做了突破新创新，舍弃了悲观控制和乐观控制，采用了全串行化的执行策略。在设计和实现并发控制时，有如下几点需要考虑：

• 并发控制算法的用户友好度和正确性，与ANSI SQL 隔离级别的匹配度；
• 并发控制算法的效率；
• 并发控制算法的死锁策略；

Oracle设计原理

事务

Oracle数据库支持ANSI SQL定义的Read Committed、Serializable隔离级别以及一个自定义的Read Only隔离级别，且默认Read Committed隔离级别。不支持ANSI SQL定义的Read Uncommitted和Repeatable Read隔离级别，主要基于如下考虑：

• Read Uncommitted ：脏读主要有两个作用，其一是读不加锁，降低读操作的成本，以提高并发度。其二是可以读到最新的未提交数据。Oracle 采用了多版本设计，读语句天然不会对记录加锁，同时读取最新脏数据的应用场景也比较少，基于上述考虑，Oracle 不支持Read Uncommitted 隔离级别；
• Repeatable Read ：Repeatable Read 和Serializable 的主要区别是读断言锁是长期的还是短期的（详细情况请回顾“事务”章节的“Locking ”小节），而Oracle 在记录上没有设计读锁，所以两者没有区别，因此Oracle 只提供了Serializable 隔离级别，不支持Repeatable Read 隔离级别；

Oracle在事务的并发控制上综合运用了锁机制和多版本机制（MVCC），在锁机制中仅在记录上设计了行级写锁，没有设计行级读锁，读导致的相关异常通过多版本机制和用户加锁来解决（select ... for update）。

在Read Committed隔离级别下，记录被修改时会在该记录上加上写锁且一直持续到事务提交或回滚，而读取记录则通过多版本机制读取已经提交的最新记录（多版本一致性读的原理，请回顾“数据前像与回滚”章节的“一致性读”小节）。为了能够读到最新的已提交数据，在每次查询语句开始前会获取当前的最新scn，该scn之前的最新已提交记录都可以被读取。这样既可以保证读到最新的已提交事务的数据，又保证了语句执行过程中的一致性。

在Serializable隔离级别下，记录被修改时会在该记录上加上写锁且一直持续到事务提交或回滚。多版本机制和Read Committed下有所不同，Read Committed在每条查询语句开始之前都会获取当前最新的scn，而Serializable在事务开始前获取当前最新的scn。整个事务运行期间保持该scn不变，从而解决了不可重复读和幻读异常。然而只有写加锁，读不加锁，从而存在如下异常：

• Lost Update ：r1[x=100]r2[x=100]w2[x=120]c2w1[x=130]c1 是“事务”章节中的示例，事务T2 对x 增加的20 将丢失。Oracle 是通过报错来解决Lost Update 异常的。当事务修改某条记录时，发现该记录的当前提交scn 大于本事务的开始scn ，说明该记录在本事务运行期间被其它事务修改并提交过，此时已经无法达成可序列化，报“ORA-08177: can’t serialize access for this transaction ”错误，本次事务执行失败；
• Write Skew ：r1[x=50]r1[y=50]r2[x=50]r2[y=50]w1[y=-40]w2[x=-40]c1c2 是“事务”章节中的示例，需满足x+y 为正数的约束，从单个事务T1 和T2 来看都是满足该约束的，但执行成功后不再满足该约束；

解决上述异常的方式是使用select ... for update，即应用通过语句要求数据库在读操作时在记录上加锁（原则上此处加读锁即可，但Oracle没有记录级读锁，所以此处加的仍然是记录级写锁，一定程度上影响并发性），从而解决上述两种异常。实际上，在Read Committed隔离级别下，应该也可以通过select ... for update强制读语句加上写锁以达成可序列化的效果，缺点是降低了并发性。

在Read Only隔离级别下，多版本机制和在Serializable隔离级别下是一样的，不同的是Read Only隔离级别下不允许执行DML写语句。Read Only对于分析型等只读场景是非常有意义的，既可以读到一致性的数据，同时又不阻塞正常的写事务。

记录锁

图6.2-1 记录级锁示意图

在上节我们知道Oracle只有记录级写锁，没有记录级读锁，即完全是通过记录级写锁达成事务的并发控制。图6.2-1给出了Oracle记录级写锁的示意图，在每行记录的头部都有一个字节的lb字段，记录本条记录被ITL中的哪个事务给锁定了。如果某条记录的lb指向ITL中的事务A，且该事务处于活跃态，那么该记录就被事务A锁住了，即事务A在该记录上加了记录级写锁。此处引出了Oracle的一个重要的设计理念，锁就是数据的一部分（占用1个字节），存在于block（data block、index block）中。这样的设计有如下优势：

• 锁资源轻量且无限大：不需要在独立的内存区域中设计锁结构，锁就在数据中，随着block 在内存和持久设备中换入换出，锁资源无限大，所以Oracle 不需要设计多层次的锁粒度，并根据锁记录的数目在不同锁粒度间升级；
• 易于传输：锁是记录的一部分，可以随着block 进行传输，这一点在Oracle RAC 中体现得非常明显，当block 在数据库实例间传输时锁信息自然也就传输过去了；

表锁

当我们在做DDL语句时需要对操作的表加表锁，从而防止其他用户同时对该表做DDL操作。在更改表结构时还需要防止此时有其它事务正在更改本表中的记录，为此需要逐行检查本表的记录上是否有锁。如果表中的记录非常多，逐行检查表上记录是否有锁非常消耗资源，可能还涉及block的读入与写出，导致性能进一步恶化。为了解决此问题，可以在表上引入新的锁类型，以表明其所属的行上有锁，这就是意向锁。意向锁指如果对某个节点加意向锁，则说明该节点的下层节点正在被加锁。对任一节点加锁，必须先对上层节点加意向锁。对应到表和记录，对表中的任何记录加记录锁前，必须先对该表加意向锁，然后再对该记录加记录锁。这样DDL对表加锁时，不需要再逐行检查表中每条记录上的锁标志了，直接判断表上是否有意向锁即可，系统效率得以提升。意向锁有如下锁类型：

• 意向共享锁（Intent Share Lock ，IS 锁）：如果对记录加S 锁，需要先对表加IS 锁，以表示该表的记录准备（意向）加S 锁；
• 意向排它锁（Intent Exclusive Lock ，IX 锁）：如果对记录加X 锁，需要先对表加IX 锁，以表示该表的记录准备（意向）加X 锁；

表上有基本的S锁和X锁，意向锁又引入了IS锁和IX锁，这样可以组合出新的S+IS、S+IX、X+IS、X+IX四种锁。但实际上只有S+IX有意义，其它三种组合都没有使锁的强度得以增强（即：S+IS=S，X+IS=X，X+IX=X，等于指强度相等）。这样我们引入了一种新的锁类型：共享意向排它锁（Shared Intent Exclusive Lock，SIX锁）。事务对某表加SIX锁，表示该事务要读取整个表（所以要对该表加S锁），同时会更新表中的部分记录（所以要对该表加IX锁）。意向锁封锁的策略：

• 加锁：申请封锁时，应按照自上而下的次序进行；
• 解锁：释放锁时，应按照自下而上的次序进行；

可见，数据库表上的锁类型有S、X、IS、IX、SIX五种。Oracle的表锁分别有S、X、RS、RX、SRX，与S、X、IS、IX、SIX一一对应。需要注意的是Oracle在记录上只提供X锁，所以与RS（通过select ... for update语句获得）对应的记录锁也是X锁（该行实际上海没有被修改），这与理论上的IS锁有所区别的。

表6.2-1 表锁相容矩阵

表6.2-2 语句与表锁的对应关系

表6.2-1为Oracle表锁的相容矩阵，Y表示相容，N表示不相容，需要阻塞等待。表6.2-2给出了语句与表锁之间的对应关系示例，锁给出了字符和数值两种表达方式。当Oracle执行select ... for update、insert、update、delete等DML语句时，会在操作的表上自动加上表级RX锁。当执行alter table、drop table等DDL语句时，会在操作的表上自动加上表级X锁。另一方面，应用程序或者操作人员也可以通过lock table语句指定需要获得某种类型的表锁。

最后再介绍一下Oracle的breakable parse locks（分析锁）。Oracle会在share pool中缓存分析和优化过的SQL语句和PL/SQL程序，这样再次执行这些相同的SQL或PL/SQL程序时，不必再进行解析、编译、生成执行计划，直接使用缓存的执行计划。缓存的执行计划对所涉数据库表是有依赖的，即当表结构发生变更时，缓存的所涉的执行计划需要及时失效。分析锁就是为了解决及时通知问题的，当缓存执行计划时，会在所涉数据库对象上加上分析锁。该分析锁会一直持有，直到对应的执行计划失效。分析锁不会产生任何阻塞，当表结构发生变更时，会及时通知对缓存的相关执行计划失效。

Enqueue

在上面章节我们知道Oracle有记录级X锁，有多种模式的表锁。通过这些锁在保证正确性的前提下，提供了最大的事务并发度。但从实现层面来看，我们还有两个关键问题尚未解决：

• 问题1 ：如何高效地知道某个数据库对象上已经加了锁，加了什么模式的锁；
• 问题2 ：当发生冲突时如何对事务排队，持有者释放锁时如何及时唤醒阻塞事务并保证公平性；

表6.2-3 部分常见enqueue type

首先来看问题1，因为锁是加在数据库对象上的，这些对象可以是表、文件、表空间、并行执行的从属进程、重做线程等等，我们将这些对象统一称为资源。为此，Oracle在SGA中设计了enqueue resource数组，数组中的每个元素代表一个资源，数组的总大小可通过参数_enqueue_resources设置（可通过x$ksqrs和v$resources查看enqueue resources）。Enqueue resource中的每个元素就是一个ksqrs结构，ksqrs结构中的关键成员有：

• enqueue type ：标识锁类型（或称为资源类型），Oracle 内部的锁类型非常丰富，表6.2-3 给出了部分常见的锁类型。各种internal locks 都会在system enqueue 中对应一种类型，记录锁和表锁属于user enqueue ，分别对应于TX 和TM 类型；
• enqueue identification （ID1 、ID2 ）：用于标识具体的资源，例如当enqueue type 等于TM 时，identification 存放具体哪个表（ID1 等于表的object id ），当enqueue type 等于TX 时，identification 存放具体哪个事务（ID1 高位的2 个字节存放undo segment id ，ID1 低位的2 个字节存放transaction table id ，ID2 存放wrap ）；
• link ：双向指针，用于将相同状态的ksqrs 结构链接在一起，例如处于空闲状态或者在同一个hash 桶中；
• owners ：指向双向链表的头部和尾部，该双向链表存放所有已经持有本资源的锁信息；
• converters ：指向双向链表的头部和尾部，该双向链表存放所有已经持有本资源并等待升级到锁强度更高的锁信息；
• waiters ：指向双向链表的头部和尾部，该双向链表存放所有已经等待本资源的锁信息；

图6.2-2 Enqueue Free List与Hash Table

如图6.2-2所示，正常情况下单个ksqrs结构未被使用前通过link双向指针串在一起，组成ksqrs的free list。当需要申请一个资源时，从free list上摘一个ksqrs结构下来，填写enqueue type和enqueue identification，并根据enqueue type和enqueue identification计算hash值，从而算出本krqrs结构归属的hash bucket，并将该ksqrs结构加入到算出的hash bucket中的hash chains中（hash chain中的ksqrs也是通过link双向指针链接在一起的）。hash算法越优秀，hash冲突越小，hash chain的长度越短。可见，处于使用状态的ksqrs是通过hash进行管理的，这样可以快速定位某个资源是否已经加锁（enqueue type和enqueue identification可以唯一标识某个特定的资源）。Hash table的长度（即bucket的数量）可以通过参数_enqueue_hash设置。由于多个用户会并发访问enqueue hash table，所以需要对其进行并发访问保护。系统会申请若干个enqueue hash chains latch（parent latch与child latch，详细情况请回顾“同步与互斥”章节），每个enqueue hash chains latch保护一段bucket（实际上是round-roubin方式）以及这些bucket后面的hash chain。Enqueue hash chains latch的数量由参数_enqueue_hash_chain_latches设置，默认值为cpu_count。

假设表t1的object id为1234，现在需要对t1加表锁，那么首先需要申请TM资源。申请资源的大致过程如下：

• step1 ：查找enqueue hash table 中是否已经有表t1 的资源（表资源的类型为TM ），对TM 、1234 （id1=object id ）、0 （id2=0 ）计算hash 值，从而得到对应的bucket （此处假设为bucket12 ）；
• step2 ：申请获得bucket12 对应的enqueue hash chains latch ；
• step3 ：成功获得latch 后，查找bucket12 的hash chain ，看是否已经有表t1 的TM 资源，如果有则表示不需要创建新的t1 资源，释放latch 直接退出，否则进入下一步；
• step4 ：从ksqrs free list 上摘下一个ksqrs 结构，将enqueue type 设置为TM ，将enqueue identification 设置为id1=1234 ，id2=0 ，然后将该ksqrs 结构添加到bucket12 的hash chain 中；
• step5 ：至此完成表t1 资源的创建，释放latch ，并退出；

在上述步骤4中，需要从ksqrs free list上摘下一个空闲的ksqrs结构。Ksqrs free list本身也需要同步与互斥保护，在高并发场景下会有大量频繁的申请与释放，此处就会成为瓶颈。为此，Oracle采用了Lazy策略，即释放资源后对应的ksqrs结构并不立刻归还到ksqrs free list中，而是保留一部分空闲ksqrs结构在chain chain上，这样后继可以直接复用，从而提升性能。

至此，我们已经完成enqueue resource的介绍。但enqueue resources只是一个容器，只能给出问题1的部分答案，即解决了如何快速找到某个数据对象（资源）的问题，还需要回答问题1提出的锁模式和问题2。为此，我们需要引入另外一个结构“锁”，“锁”是加在资源上的，即附着在某个ksqrs结构上的。

图6.2-3 KSQRS结构及锁对应关系

如图6.2-3所示，每个资源都对应一个ksqrs结构，加在该资源上的所有锁都通过ksqrs结构进行排队：

• Owners ：持有者，即该资源的拥有者，每个锁对应一个拥有者，拥有者不会被阻塞，当有多个拥有者时这些拥有者的锁一定是相容的；
• Converters ：转换者，由拥有者转换而来，表示已经拥有低强度的锁，但在申请变更为更高强度锁时和其它拥有者的锁不相容；
• Waiters ：等待者，和拥有者的锁不相容；

当拥有者释放锁时，首先唤醒转换者，即将转换者变更为新的拥有者。当拥有者和转换者都为空时，依次唤醒等待者。如果等待者中有多个相邻的锁是相容的，可以同时唤醒成为拥有者，即如果锁4和锁5是相容的，可以同时成为拥有者。

有了上述概念之后，我们首先来看表锁的互斥排队过程。表锁对表对象加锁，所以容纳表锁的ksqrs类型为TM。每个表锁是一个ktqdm结构，申请表锁时首先从ktqdm free list中申请一个ktqdm结构（ktqdm free list由dml allocation latch保护），然后将ktqdm结构附着到对应表的ksqrs结构上。ktqdm结构中关键成员有：

• sid ：锁对应的会话（session ）；
• lmode ：当前已经持有的锁模式；
• request ：当前正在请求的锁模式；
• ctime ：锁已经持有的时长或者等待的时长；

表6.2-4 表锁阻塞时序示例

图6.2-4 表锁阻塞队列示例

如表6.2-4所示，该表展示了一个针对表t1的时序示例，4个会话（s1、s2、s3、s4）同时对表t1加表锁。图6.2-4给出了T4时刻，表t1上的各表锁之间的阻塞情况。详细过程如下：

• 因为都是对表t1 加锁，所以相关的ktqdm 结构都附着在同一个ksqrs 结构上，ksqrs 的类型为TM ，id1=t1 （实际上是表t1 的object_id ），表示资源为表t1 ；
• T1 时刻：s1 和s2 两个会话同时对表t1 加row exclusive 锁，这两个锁是相容的，所以都在持有者队列中，通过ktqdm 结构中的link 链成双向链表，lmode=3 表示持有的锁模式为row exclusive ；
• T2 时刻：会话s2 尝试对表t1 加SRX （share row exclusive ），即将锁的强度从RX 升级为SRX 。由于s2 的SRX 与s1 的RX 是不相容的，所以s2 的ktqdm 结构从持有者链表中迁移到转换者链表中，lmode=3 表示s2 已经持有RX 锁，request=5 表示s2 正在申请SRX 锁，此时会话s2 阻塞；
• T3 、T4 时刻：会话s3 和s4 分别对表t1 加X 和RX 锁，这两个锁要么和持有者的锁不相容，要么和转换者的锁不相容，所以按照申请的顺序加入到等待者链表中，lmode=0 表示尚未持有任何锁，request=6/3 表示正在申请的锁模式，此时会话s3 和s4 阻塞；
• T5 时刻：会话s1 提交并释放锁，此时s2 从转换者链表迁移到持有者链表中，更新（sid=s2, lmode=5, request=0 ）表示锁升级为SRX ，此时会话s2 开始运行；
• T6 时刻：会话s2 提交并释放锁，此时持有者和转换者链表都为空，从等待者链表中将s3 迁移到持有者链表中，并更新(sid=s3, lmode=6, request=0) ，由于会话s4 的RX 和会话s3 的X 不相容，所以会话s4 仍然留在等待者链表中，此时会话s3 运行，会话s4 继续阻塞；
• T7 时刻：会话s3 提交并释放锁，会话s4 从等待者链表迁移到持有者链表中，开始运行；

至此，我们介绍了表锁的整个运行过程，回答了表锁相关的问题1和问题2，即通过ksqrs结构定位到并发阻塞的资源，通过ksqrs的持有者、转换者、等待者三个链表结合ktqdm结构完成排队、阻塞和唤醒。从中我们可以发现如下关键点：

• 一个会话对同一个表不管加多少次表锁，只会占用一个ktqdm 结构；
• 转换者链表中的元素优先级高于等待者链表中的元素，因为转换者中的元素已经持有锁，需要让它们尽快运行以尽快释放锁；
• 从等待者链表向持有者链表迁移时，是按照入链的顺序迁移的，即按照申请的顺序迁移的，体现了FIFO 的公平性；

下面我们开始介绍记录锁。对于问题1，记录锁是很容易解决的，每条记录的头部有lb标志，且记录锁只有X模式，所以记录锁的重点是解决问题2，即对有记录锁冲突的事务如何进行排队。记录锁的排队机制和表锁的排队机制是类似的，主要区别如下：

• 仍然通过ksqrs enqueue 排队，但ksqrs 的type 为TX ，id1 和id2 等于事务id ，即每个事务开启第一次写时会申请一个标识本事的TX 类型的ksqrs 结构，后继因为和本事务记录锁发生冲突的会话全部附着在该ksqrs 结构上；
• 不需要像表锁为每个锁申请一个kstqdm ，只需要为每个冲突的事务申请一个ktcxb 结构；

表6.2-5 记录锁阻塞时序示例

图6.2-5 记录锁阻塞队列示例

如表6.2-5所示，该表展示了两个事务（10.1.145和10.2.23）同时修改表t1和表t2中记录的情况，因为同时修改t1中的记录而发生记录锁冲突。图6.2-5展示了在T3时刻TX排队情况。详细过程如下：

• T1 时刻：会话s1 开启一个写事务（第一条语句就是更新表t1 的全表记录），申请一个ksqrs 结构，类型为TX ，id1=655361 （10*65536+1 ），id2=145 ，并加入到ksqrs enqueue hash 表中。同时申请一个ktcxb 结构，设置sid=s1 ，lmode=6 （记录锁只能是X 模式），request=0 ，并将标识本事务的ktxcb 附着在该ksqrs 的持有者链表上；
• T2 时刻：会话s2 开启一个写事务（第一条语句就是更新表t2 的全表记录），申请一个ksqrs 结构，类型为TX ，id1=655362 （10*65536+2 ），id2=23 ，并加入到ksqrs enqueue hash 表中。同时申请一个ktcxb 结构，设置sid=s2 ，lmode=6 ，request=0 ，并将标识本事务的ktxcb 附着在该ksqrs 的持有者链表上；
• T3 时刻：会话s2 更新t1 表的单条记录，通过检查该记录的记录头，发现该记录已经被事务10.1.145 锁住，申请一个ktcxb 结构，设置sid=s2 ，lmode=0 ，request=6 ，并将标识本会话的ktcxb 附着在事务10.1.145 的ksqrs 的等待者链表上，以等待事务10.1.145 释放该记录锁，此时会话s2 阻塞；
• T4 时刻：事务10.1.145 提交，唤醒ksqrs （TX ，id1=655361 ，id2=145 ）中等待者链表中的所有会话，然后释放ksqrs 结构（TX ，id1=655361 ，id2=145 ）和附着在该ksqrs 上的ktcxb 结构，此时s2 会话激活，继续执行对表t1 的记录更新；

至此，我们介绍了记录锁的整个运作过程，回答了记录锁相关的问题1和问题2，即在记录头部发现记录冲突，在通过ksqrs的持有者、等待者链表结合ktcxb完成排队、阻塞和激活。从中我们还可以发现如下关键点：

• 每个写事务都会申请一个ksqrs （类型为TX ）结构，并持有到事务结束，可见事务本身一种资源；
• 每个写事务都会申请一个或两个ktxcb 结构，可见ktcxb 结构的数量和修改的记录数无关，只可冲突的事务数相关；
• 所有和事务A 有记录冲突的事务都会申请一个ktxcb 结构，并将这些ktxcb 结构附着在事务A 的ksqrs 的等待者链表中；

TX事务锁除了用于记录锁的排队之外，还用于ITL Entry Shortage时事务的排队。当事务修改block中的数据时，首先需要在该block中占用一个ITL Entry。如果ITL Entry已经被用满，且无法动态扩展ITL时，本事务就需要阻塞等待。此时为本事务申请一个ktxcb结构，然后在本block的ITL中随机选择一个活跃事务，将ktxcb结构附着在该活跃事务的ksqrs结构的等待者链表上。这样当该活跃事务提交时，其占用的ITL Entry就会空出来，唤醒本事务复用该ITL Entry。

实际上，Oracle不仅仅将enqueue机制应用于表锁和记录锁，而是将enqueue机制通用化，当系统资源冲突或者不足时都采用enqueue机制进行排队。enqueue机制通用化时，都是通过ksqrs进行排队，只是enqueue type不同。同时不同的资源，用于排队的结构也不同，ktqdm用于表锁，ktcxb用于事务锁，ksqeq、kdnssf、ktatrfil、ktatrfsl、ktatl、ktstusc、ktstusg、ktstuss等等都是用于各种internal locks。不过不管是表锁、事务锁，还是各种internal locks，最终都是通过_enqueue_locks参数设置总lock的数量。

enqueue采用数组结构，同时又通过双向指针对数组中的结构进行分类管理。对于大小和属性相同的对象，Oracle一般采用数组这种数据结构进行管理。数组是采用分段方式进行分配和管理的，即Oracle初始只会分配一个容纳固定数量数据单元的内存块，然后在运行过程中动态分配更多的内存块。例如，x$ksqrs数组初始会申请一个较大的内存块，后继不够时再每次申请可容纳32个ksqrs结构的内存块，以此进行动态扩容。

死锁

Oracle的latch是通过对latch设置level属性在事前规避死锁，而lock的申请顺序和用户语句的执行时序强相关，无法通过事前规定lock的顺序来规避。因此，Oracle采用了事后检测的方法来解决死锁。当会话因为锁等待达到3秒后会醒来，这时会检查等待关系。如果存在循环等待表示存在死锁，否则进行下一个3秒周期的等待。如果检查发现存在死锁，就会触发ORA-60 deadlock detected错误，让应用参与决策。由于是事后超时检查死锁，所以一般是等待时间长的事务先报错。

MySQL设计原理

事务

MySQL数据库支持ANSI SQL定义的Read Uncommitted、Read Committed、Repeatable Read、Serializable四种隔离级别，默认隔离级别为Repeatable Read。MySQL采用的是索引组织表，表中的记录时按照索引键或主键存放的，这就为加断言锁提供了基础。实际上，MySQL就是通过间隙锁锁住记录之间的间隙，从而达到断言锁的目的，防止幻读。各隔离级别下，MySQL的并发控制机制如下：

• Read Uncommitted ：不使用一致性读，允许读取未提交事务的记录，因此会有脏读。只有更改记录或者用户强制lock read 才会加锁，且只对记录加record_lock ，不会间隙加锁；
• Read Committed ：使用一致性读，且总是读取最新提交的快照数据，允许不可重复读和幻读，在外键检查时对间隙加锁，其它情况只对记录加锁；
• Repeatable Read ：使用一致性读，且在同一个事务中读取的总是相同的历史快照数据，在更改记录或者用户强制lock read 时对记录和间隙加锁，这样避免不可重读和幻读（在某些情况下可以只对记录加锁，如唯一索引等）；
• Serializable ：不使用一致性读，所有更改和读取操作都会加锁，加锁机制和可重复读一致；

可见，MySQL的并发控制机制与“事务”章节介绍的Locking理论是最接近的，同时在Read Committed、Repeatable Read隔离级别下采用了一致性读机制（详细情况请参加“前像数据与回滚”章节），读不加锁，从而最大化地提高并发度。当然在Read Committed、Repeatable Read隔离级别下也可以通过lock read（select ... lock in share mode加共享锁，select ... for update加排它锁）主动对记录加锁，从而在较低隔离级别下也可以解决lost update、write skew等问题。

记录锁

表6.3-1 记录锁相容矩阵(行为已加锁类型，列为待加锁类型)

记录锁类型包括共享锁（LOCK_S）和排它锁（LOCK_X）两种类型。MySQL支持对间隙加锁，所以有如下不同的锁算法：

• LOCK_GAP ：间隙锁，仅对间隙加锁，锁住前一条记录和本条记录之间的间隙，但不包括本条记录和前一条记录本身；
• LOCK_REC_NOT_GAP ：记录锁，仅锁住本条记录；
• LOCK_ORDINARY ：Next_Key 锁，是LOCK_GAP 和LOCK_REC_NOT_GAP 的组合，锁住本条记录以及本条记录和前一条记录之间的间隙，但不包括前一条记录；
• LOCK_INSERT_INTENTION ：插入意向锁是一种特殊的间隙锁类型，又称为插入意向间隙锁（insertion intention gap lock ），这种锁在插入操作执行前产生。假设已经存在两个索引值4 和7 ，两个事务分别插入记录5 和6 ，每个事务在插入数据前都能在(4, 7) 中获得一个插入意向间隙锁，并且由于这两个事务插入的记录不相等而不会互相阻塞。但是，如果间隙(4, 7) 之前已经被其它事务加上间隙锁，插入意向间隙锁就会被阻塞，从而防止前事务幻读；

可见，MySQL支持两种锁类型，四种锁算法，这样共计可以组合出八种不同的锁，具体相容关系如表6.3-1所示，并从中可以发现如下规律：

• 不管是哪种锁算法，共享锁与共享锁之间都是相容的，即LOCK_S_* 和LOCK_S_* 是相容的；
• 不管已经持有的锁是哪种类型和算法，待加的LOCK_S_GAP 和LOCK_X_GAP 都是相容的，即GAP 锁（不含插入意向锁）和所有已经持有的锁都是相容的，因为GAP 锁主要用于防止将来其它事务的插入操作（避免幻读）；
• LOCK_S_REC_NOT_GAP 、LOCK_S_ORDINARY 、LOCK_X_REC_NOT_GAP 、LOCK_X_ORDINARY 之间的不相容主要发生在记录本身的共享与排它、排它与排它的不相容；
• LOCK_S_INSERT_INTENTION 和LOCK_X_INSERT_INTENTION 表示即将进行插入操作，所以不相容性主要发生在GAP 类的锁上，包括LOCK_S_GAP 、LOCK_X_GAP 、LOCK_S_ORDINARY 和LOCK_X_ORDINARY ；

表6.3-2 lock_t结构

图6.3-1 记录锁与记录之间的映射关系

和Oracle不同，MySQL是以独立的锁结构lock_t来管理锁信息的。最便捷的方式是为每个事务的每个记录锁申请独立的锁结构，但这样会引入数量庞大的锁结构，严重消耗内存资源，为此不得不采用多粒度锁机制，并进行复杂的锁升级。MySQL在速度和资源之间做了平衡，以每个事务处理的page为单位申请lock_t结构，即如果同一个事务对同一个page上多条记录加相同类型的锁，那么只需要申请一个lock_t结构。下面首先来看lock_t结构中最重要的lock_rec_t和lock_bitmap。如图6.3-1所示：

• lock_rec_t ：对应于一个page ，space 和page no 用于标识针对具体哪个page ，nbits 用于表达变长变量lock_bitmap 的长度，lock_bitmap 的字节数等于1+(nbits/8) ；
• lock_bitmap ：变长，和page 中的记录数强相关，MySQL 每条记录的ROW HEADER 结构中有一个REC_NEW_HEAP_NO （详细情况请参见“空间管理与数据布局”章节），用于对page 内每条记录生成唯一的编号。这样lock_bitmap 中的每个bit 位对应于page 中的一条记录，bit 位的位置就对应于记录的REC_NEW_HEAP_NO ，该bit 位为1 就表示对应的记录上有锁；

可见，MySQL是按照page为单位组织锁结构的。优点是节约了内存资源，不需要引入复杂的锁升级机制。缺点是判断某条记录上是否有锁的效率相对较低，首先找到该page相关的所有lock_t结构（事务、锁类型和算法不同，同一个page会有多个lock_t），遍历这些lock_t结构，并根据记录的REC_NEW_HEAP_NO检查每一个lock_t结构中的lock_bitmap，以核实该记录上是否有锁。除了lock_rec_t和lock_bitmap之外，lock_t结构中的详细情况如表6.3-2所示，其中重要的成员还有：

• trx ：指向本lock_t 归属的事务，由此可得到对应的事务结构；
• trx_locks ：双向链表，同一个事务可能申请多个lock_t 结构，通过该指针将同一个事务的lock_t 链接在一起；
• type_mode ：锁的状态、类型以及算法等信息；
• hash ：用于构建hash 链表，MySQL 会组建锁的hash 表，方便以page 为单位找到对应的lock_t 结构；

了解了锁的基本结构后，下面来看MySQL是如何组织lock_t的。MySQL中主要有两种情况查询锁：

• 情况1 ：事务需要知道本事务已经持有了哪些锁，阻塞在哪个锁上；
• 情况2 ：事务在扫描或修改某个page 中的记录时，需要知道该记录上是否有锁，以及锁的类型和算法是什么；

首先来看情况1，每个事务都会维护一个trx_lock_t结构，该结构包含如下关键成员：

• wait_lock ：一个指向lock_t 结构的指针，指向本事务当前等待的锁结构；
• trx_locks ：类型为UT_LIST_BASE_NODE(lock_t) ，指向链表的指针，结合每个lock_t 中的trx_locks 将属于本事务的所有lock_t 结构链接在一起，构成一个链表；
• wait_started ：锁等待的开始时间；
• lock_heap ：lock_t 结构是动态生成的，维护本事务所有动态锁的内存；

可见，通过wait_lock和trx_locks，事务将归属于本事务的所有lock管理起来。一个事务只可能阻塞等待在一个锁上，所以wait_lock只是一个指针。下面来看情况2，全局变量lock_sys会维护一个大的hash表（rec_hash）和因为锁等待而阻塞的线程（waiting_threads）。Rec_hash实际上就是按照space和page no对lock_t进行hash管理的大hash表。其中关键的成员有：

• array ：hash 表的桶数组；
• n_cells ：hash 表的桶数量，即桶数组的长度；
• sync_obj ：互斥量数组，用于保护并发访问hash 表；

这样根据space和page no算出具体的hash值，从而得到对应page 所在的桶，即array数组的下标。然后遍历该桶对应的哈希链，即由lock_t结构组成的链表，比较lock_t.lock_rec_t结构中的space和page no，从而找到对应的page。由于存在多个事务对同一个page的不同记录加锁，所以同一个page会有多个lock_t结构，需要遍历这些结构。对于每个lock_t结构，比较记录REC_NEW_HEAP_NO对应的位图，从而判断是否有锁。至于锁的类型和算法，则根据lock_t中的type_mode来判断。

图6.3-2 lock_t锁布局

如图6.3-2所示，每个事务维护一个trx_lock_t结构，通过该结构总额trx_locks和wait_lock以及每个lock_t的trx_locks指针，将属于某个事务的所有锁结构链接在一起。同时维护一张rec_hash表，将hash值相同的lock_t结构通过hash指针链接在一起，这就可以查询特定page的锁情况。多个用户线程会并发访问hash表，需要同步机制进行并发保护。考虑到并发性，会有多个mutexes（sync_obj），每个mutexes保护一段bucket数组以及后面的哈希链表，提高并发性。

表锁

表6.3-3 表锁之间的相容关系

表6.3-4 表锁之间的强度关系（Y表示行的强度大于列，N表示列的强度大于行）

MySQL的表锁和Oracle比较类似，也是通过多粒度锁解决效率问题，支持如下锁类型：

• LOCK_IS ：意向共享锁；
• LOCK_IX ：意向排它锁；
• LOCK_S ：共享锁；
• LOCK_X ：排它锁；
• LOCK_AUTO_INC ：自增长锁，含有自增长列的表才会加该类型的锁；

表锁之间的相容性如表6.3-3所示，之间的强度关系如表6.3-4所示。在实现上，表锁也是一个lock_t结构。和记录锁不同的是lock_t中的um_member不同，um_member是一个union结构。当lock_t为记录锁时，um_member为lock_rec_t结构。当lock_t为表锁时，um_member为lock_table_t结构。Lock_table_t结构中的关键成员有：

• table ：指向dict_table_t 类型的指针，表示本表锁归属于哪个表；
• locks ：组成lock_t 的链表，用于将归属于同一个表的所有lock_t 结构链接在一起；

图6.3-3 表锁布局

如图6.3-3所示，每个表在缓存中对应一个字典结构dict_table_t。Dict_table_t结构中的locks以及各个lock_t中的locks（实际上是um_member.lock_table_t.locks）将归属于同一个表的所有lock_t结构管理起来。Dict_table_t结构中的autoinc_lock将该表LOCK_AUTO_INC自增长锁独立出来，避免事务频繁地创建和释放该结构。表锁和记录锁都是lock_t结构，不同的是表锁不需位图结构，直接通过type_mode标识具体的锁类型。当然不管是表锁还是记录锁，从事务的角度来看，都是通过trx_locks和wait_lock进行管理的。

聚集索引和辅助索引

MySQL是索引组织表，索引又分为聚集索引和辅助索引，其加锁原则为：

• 通过主键进行加锁的场景，仅对聚集索引加锁；
• 通过辅助索引进行加锁的场景，先对辅助索引加锁，再对聚集索引加锁；

在加锁的过程中，加锁策略和隔离级别、扫描类型、索引的唯一性等强相关。总的来说，规则如下：

• 如果没有任何索引，需要全表扫描（或者覆盖索引扫描），所有记录全部加锁。RC 与RR 、Serialiable 的区别是只在记录上加锁，不在间隙上加锁。当然MySQL 出于性能的目的，对于不满足更改条件的记录会调用unlock_row 提前释放锁，一定程度上违反了2PL ；
• 如果是非唯一索引，在[index first key, index last key) 范围内加记录锁，如果是RR 或者Serialiable 隔离级别，间隙也需要加锁；
• 如果是唯一索引，在[index first key, index last key) 范围内加记录锁，如果是等值查询，即使是RR 或者Serialiable 隔离级别也不需要加间隙锁，因为唯一性已经保障不会出现幻读；

隐式锁与显式锁

虽然MySQL以page为粒度组织lock_t结构，以计算换空间（无法直接判断某行记录上是否有锁，需要遍历lock_t中的bitmap），一定程度上节约了内存资源。然而lock_t的量级仍然是事务数*page数*锁类型，锁资源的压力仍然非常大。为了节约锁资源，MySQL实现了一种称为隐式锁的延迟加锁机制。其核心思想是锁是非常消耗资源的，能不加锁就不加锁，只有在发生冲突时再加锁。显式锁是明确的锁，对应于lock_t对象，而隐式锁只是逻辑上的“锁”，没有lock_t对象，需要通过其它规则间接地发现该记录上有锁。

如何判断某条记录上是否有隐式锁？对于聚集索引来说比较简单，每条记录上都有该记录的事务id（trx_id），如果该事务id对应的事务仍然是活跃的，那么该记录上有隐式锁，否则没有隐式锁。辅助索引比较复杂，每个page上都有一个PAGE_MAX_TRX_ID（该域在PAGE HEADER结构中，详细情况请参考“空间管理与数据布局”章节），用于表示更新本page的最后一个事务id。如果PAGE_MAX_TRX_ID比最小活跃事务id还要小，说明该page上的所有记录都没有隐式锁，否则需要找到对应的主键记录进行更加复杂的判断。

图6.3-4 辅助索引与聚集索引的逻辑关系

如图6.3-4所示，现在需要判断辅助索引current_index_rec上是否有隐式索引，需要通过对应的聚集索引来判断。聚集索引结合undo日志可以构造出历史版本，包括聚集索引的历史版本和辅助索引的历史版本。有了这些历史版本之后，辅助索引上的隐式索引判断规则如下：

• current_trx 不是活跃事务（通过current_cluster_rec 中的隐藏事务id 获得），current_index_rec 上没有隐式锁；
• current_cluster_rec 没有历史记录，表示本条记录是current_trx 插入的，所以current_index_rec 上有隐式锁；
• current_index_rec=history1_index_rec ，但current_index_rec 和history1_index_rec 的delete flag 不同，表示current_index_rec 正在被current_trx 删除，所以current_index_rec 上有隐式锁；
• current_index_rec=history1_index_rec ，且current_index_rec 和history1_index_rec 的delete flag 相同，修改current_index_rec 的事务既可能已经提交了，也有可能没有提交。如果current_trx!=history1_trx 表示current_trx 没有修改current_index_rec ，所以没有隐式锁，否则要进一步判断history2 ；
• current_index_rec!=history1_index_rec ，且current_index_rec 和history1_index_rec 的delete flag 都为0 ，表示current_trx 修改了current_index_rec ，所以current_index_rec 上有隐式锁；
• current_index_rec!=history1_index_rec ，且current_index_rec 的delete flag 为1 ，修改current_index_rec 的事务既可能已经提交了，也有可能没有提交。如果current_trx!=history1_trx 表示current_trx 没有修改current_index_rec ，所以没有隐式锁，否则要进一步判断history2 ；

通过上述规则，MySQL就可以通过比较和计算发现辅助索引上是否有隐式锁。在后继事务的加锁过程中，如果发现某条记录有隐式锁，那么以前事务的名义为该记录申请加显式锁。可见，在隐式锁机制下，只有发生锁冲突时才会加锁，为系统节约了大量资源：

• 如果在原事务提交或回滚前，没有其它事务访问对应的记录，实际上所有的隐式锁都不会被转换为显式锁；
• 如果在原事务提交或回滚前，其它事务访问该记录的某些辅助索引，只有被访问到的辅助索引才会被转换为显式锁，其它辅助索引上隐式锁仍然不会被转换；

由于隐式锁只能通过规则和事务id进行判断，无法获取锁模式和锁类型等信息，所以隐式锁有如下限制：

• 隐式锁针对的是记录锁，不可能是间隙或Next-Key 类型；
• INSERT 操作只加隐式锁，不加显式锁（包括聚集索引）；
• UPDATE 、DELETE 在查询时，对查询用到的辅助索引和聚集索引加显式锁，其它二级索引使用隐式锁；

记录锁的维护

MySQL是以page为单位维护lock_t对象的，而page会随着数据的变化而变化，产生分裂、合并等现象。因此，lock_t对象也要随着page的分裂、合并而分裂、合并。分裂、合并的机制和原理基本一致，而分裂又分为左分裂和右分裂，其原理也是一致的，所以下面以右分裂为例来讲述记录锁的分裂维护。

假设某page中的记录为R1、R2、R3、R4、R5、R6、R7，那么可以锁定的范围有：

(infimum,R1](R1,R2](R2,R3](R3,R4](R4,R5](R5,R6](R6,R7](R7,supremum)

此时page需要进行右分裂，分裂点为记录R4，即记录R4~R7需要迁移到一个新的page中。那么需要生成一个新的lock_t对象（right）：

• left lock_t ：(infimum,R1](R1,R2](R2,R3](R3,supremum);
• right lock_t ：(infimum,R4](R4,R5](R5,R6](R6,R7](R7,supremum);

Right lock_t的supremum继承于原lock_t对象的supremum，同时left lock_t对象的supremum和right lock_t的infimum需要根据分裂前(R3, R4]进行设置，即(R3,supremum)和（infimum,R4]要等效于分裂前的(R3,R4]。

死锁

MySQL对死锁采用了主动检测机制，其检测原理就是有向循环图。记录锁的hash组织方式为有向循环图的检测提供了充分必要条件。当某事务在加锁时因为锁冲突要等待，就开始进行深度优先的递归遍历，检测是否存在有向循环图。如果存在循环就表示有死锁，寻找一个undo量最小的事务进行回滚。

PostgreSQL设计原理

事务

PostgreSQL数据库支持ANSI SQL定义的Read Uncommitted、Read Committed、Repeatable Read和Serializable四种隔离级别，默认隔离级别为Read Committed。在各隔离级别下PostgreSQL的并发控制机制分别如下：

• Read Uncommitted ：实际上就是Read Committed ；
• Read Committed ：使用一致性读，且总是读取最新提交的快照数据，允许不可重复读和幻读；
• Repeatable Read ：实际上是snapshot isolation ，使用一致性读，且在同一个事务中读取的总是相同的历史快照数据，允许写倾斜（write skew ）；
• Serializable ：实际上是serializable snapshot isolation ，使用一致性读，并在snapshot isolation 基础上加入SIREAD 锁和RW-Conflicts 机制，解决写倾斜异常，保证可序列化；

可见，PostgreSQL的并发控制机制与Oracle和MySQL有很大的不同，通过snapshot isolation和serializable snapshot isolation机制实现Repeatable Read和Serializable。同时PostgreSQL也采用了锁机制，解决表级冲突以及记录级的写冲突，也支持通过在select语句上指定for update或者for share强制加记录排它或者共享锁。因此，PostgreSQL综合运用了乐观控制和悲观控制方法，以达到最优的并发控制效率。

记录锁

图6.4-1 Tuple结构

正常情况下PostgreSQL直接在记录上设置标志位就可以完成对记录加记录锁，不需要申请独立的内存锁结构，从而提高内存资源利用率和锁效率。如图6.4-1所示，每条记录都有一个HeadTupleHeaderData（详细情况请参考“数据前像与回滚”章节），该头部包含了如下重要信息：

• x_min ：insert 本条记录的事务id ；
• x_max ：delete/update 本条记录的事务id ；
• t_infomask ：大量的组合标志位，通过综合这些标志完成记录锁的设置和判断，具体有HEAP_XMAX_KEYSHR_LOCK 、HEAP_XMAX_EXCL_LOCK 、HEAP_XMAX_LOCK_ONLY 、HEAP_XMAX_COMMITTED 、HEAP_XMAX_INVALID 、HEAP_XMIN_COMMITTED 、HEAP_XMIN_INVALID ；

图6.4-2 记录判断伪代码

1. FOR each row that will be updated by this UPDATE
2. WHILE TRUE
3. IF (row1 is being updated) THEN
4. WAIT for the termination of the transaction that update row1
5. IF (status of the terminated transaction is COMMITTED)
6. AND (this transaction is REPEATABLE READ or SERIALIZABLE) THEN
7. ABORT this transaction /*first-update-win*/
8. ELSE
9. GOTO step (2)
10. END IF
11. ELSE IF(row1 has been updated by another concurrent transaction) THEN
12. IF (this transaction is READ COMMITTED) THEN
13. UPDATE row1
14. ELSE
15. ABORT this transaction /*first-update-win */
16. END IF
17. ELSE
18. UPDATE row1 /*row1 is not yet modified or has been updated by a terminated transaction */
19. END IF
20. END WHILE
21. END FOR

了解了锁记录的标志位之后，我们以update语句为例来看PostgreSQL是如何基于锁进行并发控制的。如图6.4-2所示，判断过程要点如下：

• Step3 ：如果记录正在被更新，证明记录上有排它锁，有写写冲突，需要阻塞等待；
• Step5 ：当前事务被唤醒后，如果对方事务已经提交且隔离级别为Repeatable Read 或者Serielizable ，表示对方事务已经修改了当前记录，可能会引起Lost Update 异常，当前事务必须强制退出，否则跳转到第2 步，重新对本记录进行判断；
• Step11 ：如果记录已经被更新，更新该记录的事务已经提交，且该事务与当前事务是并发事务（即当前事务启动时该事务尚未提交）。如果当前事务的隔离级别为Read Committed 直接修改该记录，否则强制退出当前事务以防止Lost Update 异常；
• Step12 ：没有任何冲突，直接修改记录；

可见，通过记录上的标志位即可判断出是否有冲突。同时PostgreSQL也支持通过select语句指定for update或者for share提前设置标志，解决频繁强制事务退出的问题。当然上述机制仍然存在一个问题，当存在冲突时，如何有效地对阻塞事务进行排队，这些就需要显式地申请记录锁，详细情况请参考后面的“表锁与记录锁”章节。

表锁与记录锁

表6.4-1 语句与表锁模式的对应关系

表6.4-2 表锁模式相容矩阵(行为已加锁类型，列为待加锁类型)

和Oracle、MySQL一样，PostgreSQL出于效率考虑表锁也采用了多粒度机制，表锁的模式和相容矩阵如表6.4-1和6.4-2所示，不同的是PostgreSQL的VACCUM机制非常厚重，所以在表锁中需要引入相关的锁模式。在实现层面，不管是表锁还是显式的记录锁，都采用类似的机制，相关的结构分别为LOCKTAG、LOCK、PROCLOCKTAG、PROCLOCK、PGPROC、LOCKLOCKTAG、LOCALLOCK。需要注意的是，记录锁和表锁不同，记录锁只有共享锁和排它锁两种模式。

表6.4-3 LOCKTAG结构

LOCKTAG用于标识某个具体被锁定的资源对象，locktag_type和locktag_lockmethodid分别用于标识锁定对象的类型和方法。例如，当locktag_type等于LOCKTAG_TUPLE时，表示锁定一条记录，即记录锁，此时locktag_field1等库对象ID，locktag_field2等于表对象ID，locktag_field3等于PageNumber，表示哪个Page，locktag_field4等于OffsetNumber，表示page内记录的偏移。可见，通过4个locktag_field就可以唯一确定一条记录。当然有时不需要设置所有的locktag_field，例如，当locktag_type等于LOCKTAG_TRANSACTION时只需要将locktag_field1设置为xid。

图6.4-3 LOCK结构及与PGPROC、PROCLOCK间的关系

LOCK对象表示一个具体的锁对象，例如一个记录锁就是一个LOCK对象，一个表锁也是一个LOCK对象。如图6.4-3所示，LOCK对象详细描述了某个对象资源上的锁信息，具体情况如下：

• tag ：类型为LOCKTAG ，唯一地标识被锁定的某个资源对象；
• grantMask ：类型为LOCKMASK ，实际上就4 个字节，通过bitmap 标识已经在该资源对象上加了哪些锁模式，例如，如果第1 个bit 位设置为1 表示已经加上AccessShare 锁。通过1<<LockMode 可以标识加上多个锁模式；
• waitMask ：类型同grantMask ，grantMask 表示已经加上的锁模式，而waitMask 表示正在等待的锁模式；
• procLocks ：对tag 资源对象加锁的进程列表，指向PROCLOCK 对象，并通过PROCLOCK 对象中的locklink 指针将所有和本LOCK 对象相关的PROCLOCK 对象链接在一起；
• waitProcs ：当锁模式不相容时，相关进程就需要阻塞等待，waitProc 指向等待的PGPROC 对象，并通过PGPROC 对象的links 指针将所有阻塞在本LOCK 对象的PGPROC 对象链接在一起；
• Requested 、nRequested ：本LOCK 对象上各种锁模式被请求的次数，总次数，MAX_LOCKMODES 为当前系统支持的锁模式数量；
• granted 、nGranted ：本LOCK 对象上各种锁模式已经被授予的次数，总次数；

图6.4-4 PGPROC结构

通过LOCK对象及其哈希表可以从资源的角度找到任何锁对象，从而确定该资源上的锁情况，这是第一个维度。然而我们还需要从事务或者进程的角度查看锁的情况，这是第二个维度。在进入第二个维度之前，我们首先来看PGPROC结构。PostgreSQL是多进程设计，每个后台进程在共享内存中都有一个PGPROC对象。如图6.4-4所示，PGPROC对象中与锁强相关的信息如下：

• links ：和LOCK 对象中的waitProcs 指针相对应，用于将阻塞等待在同一个LOCK 对象上的PGPROC 链成一个链表；
• waitLock ：指向本进程正在阻塞等待的LOCK 对象；
• waitProcLock ：指向本进程正在阻塞等待的PROCLOCK 对象；
• waitLockMode ：本进程阻塞等待的锁模式；
• heldLocks ：本进程已经持有的锁模式；
• myProcLocks ：本进程拥有的所有PROCLOCK 对象，通过分区数组以及PROCLOCK 中的procLink 指针，将所有属于本进程的PROCLOCK 对象链接在一起；

图6.4-5 资源对象与进程之间的关系

表6.4-4 PROCLOCK结构

表6.4-5 PROCLOCKTAG结构

LOCK对象描述了某个具体资源对象的锁情况，PGPROC对象描述了某个具体进程的锁情况。如图6.4-5所示，某个资源可以被多个进程加锁，某个进程也可以对多个资源加锁，所以LOCK对象和PGPROC对象时多对多的关系。PostgreSQL设计了PROCLOCK对象以维护LOCK对象和PGPROC对象之间的对应关系。每个PROCLOCK对象代表一个LOCK对象和一个PGPROC对象的对应关系。详细情况如表6.4-4和6.4-5所示，其中的关键信息如下：

• tag ：唯一确定一个LOCK 对象和PGPROC 对象的对应关系；
• holdMask ：该进程在该对象上已经持有的锁模式；
• releaseMask ：该进程在该对象上可以被释放的锁模式；
• lockLink 和procLink ：分别按照Lock 对象维度和PGPROC 对象维度将相关的LOCKPROC 对象链接在一起；

表6.4-6 LOCALLOCK结构

表6.4-7 LOCALLOCKTAG结构

LOCK、LOCKPROC、PGPROC等对象都存放在共享内存中，运行时都访问共享内存，同时还要考虑互斥，代价比较高。为此，PostgreSQL的每个后台进程在本地维护了LOCALLOCK对象，更新LOCK、LOCKPROC、PGPROC等对象时同时更新LOCALLOCK对象。这样在访问锁时，如果LOCALLOCK对象已经满足要求，就可以不用访问共享内存，从而提高效率。例如，对同一个锁多次加锁或者释放只属于某个资源的锁。

死锁

对于死锁，PostgreSQL采用了事前预防和事后检测相结合的方式，具体包括：

• 当进程加锁冲突时，就会进入等待队列。如果在队列中已有其它进程请求本进程已经持有的锁，为了避免死锁，可以将本进程插入到该进程的前面；
• 当释放锁时，会尝试唤醒等待队列中的进程。如果某进程请求的锁与该进程前序进程的锁不相容，那么该进程不会被唤醒；

通过上述方式，在尽量保证先请求先处理的原则下，尽可能规避潜在的死锁。然而，上述方法只是进行了简单的规避，并不能彻底解决死锁，完全解决需要通过有向等待图来解决，但成本较高，PostgreSQL将这一过程放在了事后。

图6.4-6 死锁检测的触发过程

如图6.4-6所示，当阻塞等待超时后就开始进行死锁检测。不过PostgreSQL在有向循环图中引入了Soft Edge和Hard Edge的概念：

• Soft Edge ：进程A 和进程B 都在同一个锁的等待队列中。进程A 和进程B 的锁请求不相容，且进程A 在进程B 的后面，这时进程A 指向进程B 的有向边为Soft Edge ；
• Hard Edge ：进程A 请求的锁和进程B 已经持有的锁冲突，这时进程A 指向进程B 的有向边为Hard Edge ；

可见，Soft Edge是可以通过重新排队进行规避的，而Hard Edge已经形成，是无法改变的。有了Soft Edge和Hard Edge概念之后，我们来看看PostgreSQL是如何进行死锁检测的：

• 从每一个点出发，沿着有向循环图的有向边行进，如果能够回到起点，说明存在死锁；
• 在遍历过程中将Soft Edge 记录下来，如果存在死锁且没有Soft Edge ，直接终止本事务；
• 如果有Soft Edge 。对于每个Soft Edge ，递归枚举它的所有子集，尝试进行调整。调整方法采用拓扑进行排序，并遍历测试，如果通过测试表明可以规避死锁，直接结束。如果调整任何一个Soft Edge 都无法解决死锁，终止本事务；

SIREAD锁和RW-Conflicts

图6.4-7 写倾斜于依赖图

在Serializable隔离级别下，PostgreSQL可以解决所有异常，其采用的方法并不是读写都加断言锁和记录锁，而是采用SSI策略（详细情况请参考“事务”章节）。如图6.4-7所示，当依赖图（dependency graph）中存在循环，表示存在写倾斜异常，需要强制某个事务退出，从而打破循环，保证可序列化。可见，SSI的重点是标识rw关系和检测依赖图中是否有循环，为此PostgreSQL定义了SIREAD锁和RW-Conflicts两种数据结构。

为了构建RW-Conflicts，首先需要表示出哪些事务读取了哪些记录，这就是SIREAD锁的作用。当执行DML语句时，CheckTargetForConflictsOut函数会创建SIREAD锁。例如，当事务txid1读取记录tuple1时会创建SIREAD锁{tuple1, {txid1}}，之后事务txid2也读取记录tuple1时该SIREAD锁会更新为{tuple1, {txid1, txid2}}。可见，SIREAD锁是以记录为单位跟踪相关事务。然而在高并发下，SIREAD锁的数量会非常大，严重消耗系统资源。为此，PostgreSQL采用锁升级的机制来缓解资源消耗。SIREAD锁有tuple、page、relation三个层次。如果某个page的所有tuple都创建了SIREAD锁，那么升级为page级，即以page为单位创建SIREAD锁，原来属于该page的tuple级SIREAD锁全部释放。Relation级即表级，原理同page级。

RW-Conflicts是一个三元组，由读事务、写事务、记录（元组）组成。例如，事务txid1读取了记录tuple1，之后事务txid2更新了记录tuple1，那么就需要创建一个RW-Conflict，{txid1, txid2, {tuple1}}。在执行insert、update、delete命令时，CheckTargetForConflictsIn函数会检查相关SIREAD锁，从而判断是否存在RW-Conflicts。如果存在，就创建RW-Conflicts。

表6.4-8 写倾斜检测示例一

表6.4-9 写倾斜检测示例二

表6.4-10 写倾斜检测示例三

假设表t1，在id列上有主键索引。表6.4-8给出了写倾斜检测的详细过程，具体如下：

• T2 ：事务Tx_A 查询id 为2 的记录，由于涉及主键，所以CheckTargetForConflictsOut 创建了两个SIREAD Locks ，分别为L1 和L2 ；
• T3 ：事务Tx_B 查询id 为1 的记录，由于涉及主键，所以CheckTargetForConflictsOut 创建了两个SIREAD Locks ，分别为L3 和L4 ；
• T4 ：事务Tx_A 更新id 为1 的记录，CheckTargetForConflictsIn 检测SIREAD Locks ，发现存在RW-Conflicts ，所以创建RW-Conflicts C1;
• T5 ：事务Tx_B 更新id 为2 的记录，CheckTargetForConflictsIn 检测SIREAD Locks ，发现存在RW-Conflicts ，所以创建RW-Conflicts C2 。此时依赖图已经存在循环，即写倾斜已经产生，然而事务Tx_A 和Tx_B 都没有提交，所以CheckTargetForConflictsIn 无法基于“first-committer-win ”原则决策让哪个事务失败;
• T6 ：事务Tx_A 提交，PreCommit_CheckForSerializationFailure 函数检查发现Tx_A 和Tx_B 存在写倾斜，但Tx_B 事务仍然处于运行状态，所以事务Tx_A 提交成功；
• T7 ：事务Tx_B 提交，PreCommit_CheckForSerializationFailure 函数检查发现Tx_A 和Tx_B 存在写倾斜，但Tx_A 事务已经提交，所以事务Tx_B 提交失败；

从上述过程我们发现SIREAD Locks和RW-Conflicts不能在事务提交后立刻释放，需要存在一段时间，以确保相关事务的写倾斜检测能够正常进行。另外，并不意味着事务的倾斜异常只会发生在提交阶段。事实上，CheckTargetForConflictsIn和CheckTargetForConflictsOut都会进行依赖图检测，只要存在循环，且有一个事务已经提交，就会立刻让当前事务失败，例如表6.4-9和6.4-10。

CockroachDB设计原理

设计思路

CockroachDB是一种基于乐观机制的分布式数据库，其默认的隔离级别是可序列化快照（SS， Serializable Snapshot）。和PostgreSQL相比，CockroachDB不采用锁机制，而是将SS发挥到极致，其采用的并发控制有如下特征：

• 可序列化：执行结果和某种串行执行的结果是等价的；
• 可恢复：对于一系列并发执行的事务，有些事务执行成功，有些事务异常退出，仍然能够保证系统可恢复至一致性状态。原子性保证单个事务是可恢复的，严格的乐观调度策略保证任何事务的组合执行也是可恢复的；
• 无锁：执行期间不会在资源上加锁。如果某事务和可序列化、乐观调度机制相关冲突，通过强制该事务退出来保证正确性；
• 分布式：系统无集中的授时、协调或者其它服务；

可序列化图

在序列化理论中，冲突的发生条件是两个不同事务中的操作操作了相同的数据，且至少有一个操作是写操作。满足上述条件时，就可以说第二个操作和第一个操作相冲突。冲突有三种类型：

• 读写冲突（RW ）：第二个操作覆盖了第一个操作读取的结果；
• 写读冲突（WR ）：第二个操作读取了第一个操作写的结果；
• 写写冲突（WW ）：第二个操作覆盖了第一个操作写的结果；

图6.5-1 可序列化图示例

对于事务执行的任何历史，通过这些冲突可以建立一个可序列化图。如图6.5-1所示，将所有事务链接在一起的有向图有如下部分组成：

• 事务是图中的节点；
• 当某操作和另外一个事务的操作冲突时，就画一个从被冲突事务到冲突事务的有向边；

图6.5-2 循环可序列化图示例，该历史不可序列化

执行历史是可序列化的，当且仅当可序列化图是非循环的。图6.5-2中的示例就是不可序列化的。CockroachDB采用时间排序来保证可序列化图是非循环的，方法如下：

• 每个事务启动时都会赋予一个时间戳，此后该事务中的所有语句都使用此时间戳；
• 每个操作都可以独立地判断自己和其它事务的哪个操作冲突，以及被冲突操作的时间戳是什么；
• 允许操作和拥有更早时间戳的其它操作相冲突，但不允许和拥有更晚时间戳的操作相冲突；

由于在时间前进方向上不允许存在冲突，所以可序列化图就不存在循环。下面章节我们将介绍CockroachDB是如何检测和防止这些冲突的。

WR冲突与MVCC

WR冲突采用多版本来解决。CockroachDB不仅仅存储单值，而是存储了基于时间戳的多个版本值。写操作不会覆盖旧值，而是创建一个带新时间戳的新值。

图6.5-3 多版本值读示例

如图6.5-3所示，对某key的读操作将返回比读操作时间戳小的最新版本。因此，在CockroachDB中后继事务不会形成WR冲突，因此读操作不会使用更晚的时间戳。

RW冲突与时间戳缓存

任何读操作的时间戳都会缓存在时间戳缓存中。通过该缓存我们可以查询某个key最近进行了哪些读操作，以及这些读操作的时间戳是怎样的。

所有写操作在对key进行写时都需要查询时间戳缓存。如果返回的时间戳大于写操作的时间戳，表明RW和一个更晚的时间戳相冲突。这是不允许的，必须以一个更晚的时间戳重启写操作所在的事务。

时间戳缓存是一个区间缓存，也就是说其存储的是key的范围。如果某读操作读取了某段范围内的所有key（例如扫描），那么扫描的这些key都以范围的形式存在时间戳缓存中。

时间戳缓存完全缓存在内存中，采用LRU算法。当缓存大小达到设定的限制后，最老的时间戳条目就会被删除。为了处理不在缓存中的key，需要定义“低水位线”，其等价于所有key的最早时间戳。如果写操作查询的key不在时间戳缓存中，就返回低水位线。

WW冲突与只写最新版本

写操作尝试写某key时，该key的时间戳比操作本身的时间戳还要新，表明WW和一个更晚的时间戳相冲突。为了高正可序列化，必须以一个更晚的时间戳重启写操作所在的事务。通过时间排序，拒绝任何不满足排序要求的冲突，CockroachDB的SS可以保证执行结果是可序列化的。

严格调度与可恢复性

通过前面章节介绍的冲突规则可以保证执行历史是可序列化的。另一个问题是如何保证两个满足冲突规则的未提交事务是可恢复的。假设两个事务T1和T2，T1的时间戳小于T2的时间戳。T1写了key“A”，之后T2在T1提交前读取key“A”。该冲突是被时间排序规则所允许的。但T2应该从key“A”中读到哪一个值呢？

• 假设忽略掉T1 的未提交数据，读取数据的前一个版本。如果T1 和T2 都成功提交，这将引起WR 冲突，且和时间排序规则相冲突，因此不可序列化；
• 假设读取T1 的未提交数据。如果T2 提交成功，T1 回滚了，这和T1 的原子性相冲突（T1 回滚了，但仍然对数据库的状态产生了影响）；

上述两种情况都是不允许的。为了维护调户的可恢复性，在T1提交前T2不可以提交。

为此，CockroachDB采取了严格的调度策略处理此场景：读操作和覆盖操作只允许作用在已提交数据上，操作永远不允许在未提交数据上实施。为了实现原子性提交，key上的未提交数据都保存在意向记录中（Intent Record）。如图6.5-4所示，在MVCC存储结构中，key上的意向记录可以很容易地被查到。在并发环境中，意向记录意味着存在一个正在运行的并发事务。

图6.5-4 意向记录与MVCC

严格调度存在两种场景：读操作遇到一个时间戳更小的意向记录，或者写操作遇到一个意向记录（不管时间戳的大小）。对于这两种场景，CockroachDB有两种选择：

• 如果第二个事务的时间戳更大，该事务可以等待第一个事务提交或回滚完毕，然后再继续执行自己的操作；
• 强制其中一个事务退出；

作为一种乐观的系统（无等待），CockroachDB选择了强制退出其中一个事务。决策将哪个事务退出的过程如下：

• step1 ：第二个事务（遇到意向记录的那个事务）读取第一个事务的事务记录（CockroachDB 为每个活跃事务维护一条事务记录，以表征该事务的提交状态）；
• step2 ：如果第一个事务已经提交（意向记录还没有来得及清理），第二事务清理该意向记录，即将意向记录中的值当成正常值来处理；
• step3 ：如果第一个事务已经回滚，第二事务删除该意向记录，并将意向记录当成不存在处理；
• step4 ：如果第一个事务处于运行态（未提交），固定选择第一个或第二个事务都是不合理的。同时还存在两个事务同时处理对方，对于冲突的两个事务，胜利的一方最好是确定性的。为此，每个事务记录都赋予一个优先级，永远强制退出优先级地的那个事务。如果优先级相等，强制退出时间戳大的事务。

新事务启动时获取一个随机的优先级，当事务因为冲突而重启时，其新的优先级等于max(random, [导致本事务重启的哪个事务的优先级]-1)，最终事务在重启的过程中优先级会不断提升。

采用本方法，未提交事务之间的冲突可以通过强制退出其中一个事务而立刻得到解决。因此，严格调度确保了所有的事务执行历史都是可恢复的。优先级已经在概率上解决了导致异常事务的问题，即被异常打败的事务会不断地重启，且在重启的过程中优先级会不断地上升，最终获得胜利。

另外，CockroachDB在所有事务中增加了心跳。在运行过程中，活跃事务需要周期性地更新其事务记录中的心跳时间戳。如果其它事务碰到某事务的记录时，该事务的心跳时间戳超时，那么该事务被认为是异常事务，此时强制异常事务退出而不是比较优先级。

VoltDB设计原理

传统数据库的成本

Micheal Stonebraker等人在开源数据库Shore上进行了各种基准测试，以调研传统数据库中各组件的成本。测试环境为桌面系统，刚开始性能大约为640TPS。之后每次删除系统中的一个特征，并重新进行基准测试，直至仅剩下一个非常薄的查询内核，性能为12700TPS。这个内核是单线程、无锁、无恢复功能的全内存数据库。通过分解发现了4个影响性能的最大组件：

• Logging ：跟踪数据结构的所有变化并记录日志，拖慢了性能。如果可恢复性不是必须的，或者可通过集群中其它节点进行恢复，日志就不是必须的；
• Lock ：两阶段锁产生了相当大的负载，因为所有对数据的访问都要经过Lock Manager 这个单点组件；
• Latch ：在多线程数据库中，很多数据结构在被访问前都要先加上Latch ，通过单线程机制可以避免这个诉求，并获得可观的性能提升；
• BufferManager ：内存数据库不需要通过缓存池访问数据页，消除了访问每条记录的间接成本；

表6.6-1 传统数据库各组件指令数占比

图6.6-1 NewOrder下各组件指令占比

图6.6-1和表6.6-1给出了这些挑战对应的性能变化情况（测试模型为TPC-C下NewOrder事务和Payment事务，统计的是运行该事务的CPU指令数）。可见每个组件都占整个系统的10%~35%指令数（整个系统运行一遍NewOrder事务的指令数为1.73M）。“hand-coded optimizations”代表的是对B树进行一系列优化。“useful work”代表的是处理查询的实际工作，只占总工作的1/60。“buffer manager”下面的方框代码的是移除上面所有组件之后的性能，这时仍然支持事务，指令数只有总体的1/15，不过仍然是实际工作的4倍（两者之间的差距主要源于函数调用栈的深度，以及无法完全消除缓存管理和事务相关的所有代码）。

基于上述分析，Micheal Stonebraker在设计VoltDB时，期望通过裁减Buffer Manager、Latch和Lock等组件以获得更高的性能。因此，VoltDB是一款仅支持序列化隔离级别的分布式内存数据库。内存数据库可以降低Buffer Manager的成本，仅支持序列化隔离级别可以降低Latch和Lock的成本。本章重点讨论VoltDB的并发控制是如何避免Lock成本的。

图6.6-2 串行执行队列

假设只有单颗CPU和DRAM内存，我们应该设计一个怎样的程序，在单位时间内仅可能多地执行命令。这些命令可以是创建、查询或者更新结构化数据。如图6.6-2所示，解决方案之一就是将命令放在一个队列中。然后执行一个循环，不断地从队列中取命令并执行。显而易见的是此方法可以让单颗CPU充分运转起来，当然有几纳秒的时间周期用于从命令队列中取命令和将响应放入响应队列中。在循环中，CPU执行的任务基本上100%都是实际工作，而不是系统调度、锁控制、缓存控制等和实际工作不相关的工作。

在VoltDB中，用户的命令就是SQL执行计划、分布式分片上的执行计划、或者存储过程的调用，循环就对应于单个分片上的命令队列。

并发控制

VoltDB每次只会运行一个命令，命令之间无并行无重叠，从而提供了序列化的隔离性。在单颗CPU上高饱和地运行应用的实际工作。然而服务器上有多颗CPU，如何让多颗CPU都高饱和地运行起来？首先对数据进行分片，然后在每个分片上维护一个命令队列。这也是大部分分布式NoSQL数据库的设计思路：操作需要制定待操作数据的KEY。

VoltDB采用的是一致性哈希分片，用户需要为每个表指定分片列。这些分片列和NoSQL存储的KEY非常类似。根据分片列判断SQL语句或者存储过程涉及哪个分片，然后将其路由到对应分片的命令队列上。

集群中多个服务器或者服务器上多颗CPU，都可以通过增加分片的方法让各CPU繁忙起来，每颗CPU独立运行某个分片上的命令队列，各自提供ACID语义。可见：

• 在每个分片上串行地执行查询或者修改命令；
• 命令可以是SQL 、存储过程、SQL 执行计划的某个片段；
• 每个命令都提供ACID ；
• 表数据分布在各个分片上；
• 通过增加分片的方法在多CPU 、多服务器上获得扩展性；

事务

VoltDB将存储过程作为单独的事务来执行，SQL语句作为自动提交的事务来执行。单分片事务是在单个分片上直接执行的事务。单分片事务可以是只读事务，也可以是读写事务，每个单分片事务都完全满足ACID。

实际上单分片只读事务的执行过程可以进一步优化，即越过SPI，以负载均衡的方式直接路由到分片的某个副本上。VoltDB的副本间是以同步的方式执行读写事务，所以只读事务即使越过SPI，仍然可以读到前面事务的结果。此优化可以提升只读事务的吞度量，降低只读事务的延时，减轻SPI的工作量。

图6.6-3 只读事务在分片的副本间负载均衡

图6.6-3以示例的方式展示了优化的正确性，事务A和事务C为读写事务，事务B为只读事务，且应用的发起顺序为事务B先于事务C而后于事务A。事务B放在任何一个副本的序列化命令队列中都是正确的（不影响其它副本的结果）。

VoltDB支持事务在多分片上进行读写操作，这样的是称为多分片事务。SPI为单个分片实施序列化工作，MPI为跨分片事务实施序列化共诺。MPI会和相干分片的SPI交互，以将分解后的命令注入到对应分片的命令队列中。

图6.6-4 只读事务在分片的副本间负载均衡

图6.6-4示例了MPI执行多分片事务M的过程。SPI#1将事务M序列化在单分片事务C的后面执行，SPI#2将事务M序列化在单分片事务B的前面执行。从全局来看，事务的执行顺序为C、M、B。

为了执行多分片SQL，VoltDB的SQL执行计划生成器会将执行计划分解成多个片段，有些片段在多个分片上分布式执行，有些片段对分布式执行的结果进行汇总。多分片写事务在各分片间采用两阶段提交协议。在Prepare阶段，MPI将执行接话片段分发到各个分片执行。如果这些片段在各分片上执行成功，无约束性冲突，MPI通知所有分片进行提交。各分片不会执行命令队列中的任何其它命令，只到收到提交消息。

VoltDB中多分片事务的大部分案例是分布式读，要么是读取记录时不知道分片的取值，要么是进行汇聚分析。对于仅含只读工作的多分片事务，用户可以通过标签显式地表达出来，这样上述分布式过程就可以进行优化：

• SPI 可以将命令发给任何某个副本，而不需要在副本间同步；
• 分片执行完读操作后，可以立刻执行命令队列中的其它命令，而不是阻塞在那里等待提交消息；

总结与分析

并发控制的原则是在保证正确性的前提下尽可能地提高并发性，为此Oracle、MySQL、PostgreSQL、CockroachDB、VoltDB采用了不同的策略以提高并发性。

从并发控制算法的用户友好度和ANSI SQL隔离级别匹配度来看。MySQL支持ANSI SQL定义的四种隔离级别，在任何情况下都会加记录级写锁，避免了Dirty Write异常。在Read Committed级别下通过语句级一致性读解决了Dirty Read异常。在Repeatable Read级别下，通过事务级一致性读以及Next_key写锁解决了Fuzzy Read和Phantom异常，但由于读不加锁，仍然存在Lost Update和Write Skew异常。在Serializable级别下，读写都加Next_key锁，可以解决所有异常。

PostgreSQL真正意义上仅支持三种隔离级别（Read Uncommitted实际上就是Read Committed），在任何情况下都会加记录级写锁，避免了Dirty Write异常。在Read Committed级别下通过语句级一致性读解决了Dirty Read异常。在Repeatable Read级别下，通过事务级一致性读以及写锁解决了Lost Update、Fuzzy Read、Phantom异常，但由于读不加锁，Lost Update异常只能采取“First-Update-Win”原则，对用户不友好，而Write Skew异常仍然无法解决。在Serializable级别下，通过SSI算法进一步解决Write Skew异常，但解决的方法是一旦发现潜在的Write Skew，就强制某个事务退出，对用户并不友好。

Oracle仅支持Read Committed和Serializable两种隔离级别，在任何情况下都会将记录级写锁，避免了Dirty Write异常。在Read Committed级别下通过语句级一致性读解决了Dirty Read异常。在Serializable级别下，通过事务级一致性读和SCN比较，解决了Lost Update、Fuzzy Read和Phantom异常，读不加锁导致Lost Update只能通过报错来解决，对用户不友好，同时读不加锁导致Write Skew异常无法解决。

CockroachDB支持Snapshot Isolation和Serializable Snapshot Isolation隔离级别，通过多版本和时间戳排序达到可序列化要求。然而为了可恢复新采用了严格的调度策略，不管是读操作还是写操作一旦遇到比自己跟到且未提交的时间戳，必须强制一个事务退出，对用户不友好。VoltDB仅支持Serializable隔离级别，所有事务都串行执行，不存在任何异常。可见在ANSI SQL隔离级别匹配度上MySQL最高，然后依次是PostgreSQL、Oracle、CockroachDB和VoltDB。MySQL、PostgreSQL、Oracle都支持用户在select语句上指定加锁，这样即使在低隔离级别上也可以选择性地解决Lost Update和Write Skew异常。

从并发控制算法的效率上来看，Oracle没有设计独立的锁结构，仅在记录上通过1个字节的lb表达出锁信息，理论上锁资源是无穷的。Enqueue机制对等待的事务进行排队，并区分拥有者和等待者，进行非常精准的唤醒。MySQL和PostgreSQL的锁机制比较类似，正常情况下通过记录上的标志位进行判断（判断规则比较复杂），一旦出现冲突则转换为显式锁。在显式锁方面，MySQL以page为单位组织锁资源，在空间和时间上做了权衡。PostgreSQL采取了记录、page、表多粒度的方式组织锁资源。在冲突对事务进行排队时，两者相对Oracle都比较粗糙。和MySQL不同的是，PostgreSQL在SSI方面又引入了SIREAD锁和RW-Conflicts，对所有读操作、读写操作都要进行跟踪记录，并进行检索判断，成本非常高。CockroachDB需要对所有记录的读操作维护时间戳，成本较高。当然由于采用的是乐观控制，在低冲突场景下效率相对较高，在中高冲突下由于要频繁地重做，效率是极低的。VoltDB采用的是串行执行策略，效率非常高。但场景首先，需要以存储过程为事务执行单位，减少应用和数据库之间的来回交互，同时负载要有非常好的可切分性，每颗CPU负责一个分片，分片之间无相关性。可见，在效率上Oracle是最高的，MySQL和PostgreSQL相当。CockroachDB和VoltDB引入了新思路，但场景相对受限。

Oracle、MySQL、PostgreSQL采用了锁机制，存在死锁的情况，三者都采用有向循环图的检测方法。Oracle认为死锁检测的代价较大，只有在锁等待超时后才会检测死锁。MySQL在发生锁等待时提前进行死锁检测，提前解决死锁问题。PostgreSQL也采用了锁等待超时后进行检测的策略，但在事前和事后都做了一些小的优化，尽可能地避免死锁。

PDF版本下载地址：http://blog.itpub.net/69912723/viewspace-2725664/