PostgreSQL
数据库中的对象是共享的，假如不同的用户同时修改某个对象，就会出现数据错乱，从而破坏数据库的数据一致性，违反事务的隔离性原则。
为了满足隔离性的要求，数据库需要实现并发控制机制。
并发控制机制可以采用不同的方法实现，概括地说，可以分成基于封锁的并发控制和基于时间戳的并发控制，不同的数据库在实现并发控制时会根据自身的特点对这两种技术进行改进。
PostgreSQL数据库采用两阶段锁（Two Phase Lock，2PL）和MVCC相结合的方法来满足事务的隔离性要求。
这里就来主要介绍两阶段锁的基本概念，并详细介绍PostgreSQL数据库中的锁及死锁检测的实现方法。

并发的异常现象

如果事务调度系统能够保证事务逐个执行而不交叉，那么就说事务符合可串行化的要求。
所谓的事务可串行化，指事务虽然是并发交叉执行的，但执行结果和串行执行的结果一致。
串行执行的效率比较低，为了提高系统的吞吐量，事务需要并发执行，因此在数据库中就需要实现并发控制机制，这样既能满足事务隔离性的要求，又能提高数据库的并发性能。
事务的并发控制机制主要是防止出现由于事务的并发执行导致的异常现象。因此，只有了解了这些异常现象，才能更好地理解事务并发控制实现的机制。
在ANSI SQL的标准文档中，规定了事务并发执行可能导致的3种异常现象，分别是脏读、不可重复读和幻读。
下面逐一看一下这些异常现象的定义。

P1：脏读

事务T1修改了一个元组，在事务T1提交之前，事务T2就读到了事务T1修改的这个元组。由于事务T1还没有提交，所以事务T2读到的元组是“脏”元组，如图1所示。
图1 脏读示意图

P2：不可重复读

事务T1读取了一个元组，然后事务T2修改或删除了这个元组，并且事务T2提交了。这时候事务T1如果再次读取这个元组，就会发现元组已经被修改了或者被删除了。
也就是说，事务T1重复读取一个元组却获得了不同的值，如图2所示。PostgreSQL数据库中的两阶段锁 - 图2
图2 不可重复读示意图

P3：幻读

事务T1按照某个谓词读取到一组元组的集合，然后事务T2插入一个新的元组。这个新元组同样满足事务T1中的谓词条件，元组被插入后，事务T2提交。
此时，如果事务T1再次按照同样的谓词读取元组，就会读取到不同的元组集合（新插入的元组被读到），事务T1的回滚有可能覆盖事务T2的修改，如图3所示。PostgreSQL数据库中的两阶段锁 - 图4
图3 幻读示意图
把异常现象定义成脏读、不可重复读、幻读是不充分的，一些专家对此也提出了异议，在论文A Critique of ANSI SQL Isolation Levels中对异常现象进行了更详细的划分，除了已经定义的3种异常，还定义了一些新的异常现象。

P0：脏写

事务T1修改了某个元组，在T1提交或回滚前，事务T2又修改这个元组，这就导致了脏写。假设事务T1最终回滚了，而事务T2的修改是基于事务T1的修改而做的，此时T2的执行结果是错误的，如图4所示。
图4 脏写示意图

P4：丢失更新

事务T1先是读取了元组中的某个值，然后事务T2修改了这个值，此时事务T1并不知道事务T2修改了这个值，它还是根据自己以前读到的值去做更新（例如做+1操作），这将会覆盖事务T2更新的值，产生了丢失更新异常，如图5所示。
图5 丢失更新示意图
丢失更新和脏写的最主要区别在于，丢失更新是基于先前读到的值进行更新的，而脏写则强调的是不同写操作之间对值的覆盖导致异常。
A5包含的是违反约束的两种异常现象，主要包括了读偏序和写偏序。

A5A：读偏序

假设x和y具有x+y>0的一致性约束，事务T1读取了元组x的值。这时事务T2同时更新了x和y的值，然后事务T2提交，事务T1再去读y的值，那么T1读到的x和y的值就可能违反了一致性约束，因为它读到的x是事务T2提交之前的值，而y则是事务T2提交之后的值。如图6所示，此时x+y=50+(-60)=-10<0，违反了一致性约束。
图6 读偏序示意图

A5B：写偏序

假设x和y具有x+y>0的一致性约束，事务T1读取了x = 50和y=50，然后事务T2读取x=50和y=50。
事务T2更新x的值为-40，此时它认为x+y = 10 > 0，满足一致性约束。
事务T1更新了y的值为-40，此时它也认为x+y = 10 > 0 满足一致性约束。
但两个事务提交之后，x+y = -80 < 0，违反了一致性约束（注：严格的两阶段提交，即S2PL，不会出现这种异常，因为在事务T1和T2读取x、y的值时会加读锁，并且读锁会持续到事务提交，由于读写冲突，S2PL能保证两个事务无法同时更新x、y的值，会出现锁等待或者死锁，在SSI相关的章节中会继续介绍写偏序异常，因为在MVCC机制下，读写互相不阻塞，需要借助SSI方法解决该异常），如图7所示。
图7 写偏序示意图

调度

事务的并发执行需要保证同一事务中的操作顺序是固定不变的，但不同事务的操作可以交叉执行，这种操作的交叉执行可能会破坏数据的一致性状态。
如果要保证事务并发执行的正确性，可以要求所有的事务串行执行，也就是逐个执行，事务的执行不存在交叉，称这种调度为事务的串行调度。假设有N个事务并发执行，那么就存在N！种串行调度。
串行调度能够保证不破坏数据库的一致性状态，但是，串行调度并不是最好的调度策略。
随着CPU核数的不断增加，事务之间的并发执行越来越重要，串行调度很难充分利用CPU资源。
为了提高计算资源的利用率、提高数据库的执行效率，事务必须要并发执行。
事务并发执行会引发各种异常现象，事务的调度就需要在并发执行的基础上避免这些异常现象的产生。
如果存在这样一种调度：事务之间的操作存在交叉执行，但是最终的执行结果和某个串行调度的执行结果相同，那么这个调度被称为可串行化调度。
为了方便研究，把事务中的操作抽象成读操作和写操作，事务1中对A对象的读操作和写操作可以如下表示。

  • R1(A)：事务1中对A对象做读操作。
  • W1(A)：事务1中对A对象做写操作。

根据读写操作的顺序不同，又可以抽象出以下4种操作序列。

  • 读-读操作：读操作和读操作是不冲突的，读操作不会改变元组的值，交换相邻读操作的顺序不会影响读取的结果，例如R1(A)R2(A)和R2(A)R1(A)的执行结果是等价的。
  • 读-写操作：读操作读到的值会被写操作修改，因此它们之间的顺序不能随意调换。也就是说，读、写操作是冲突的，相邻的读、写操作不能交换顺序。
  • 写-读操作：和读-写操作类似，写操作的值可能会被读操作读取，因此它们之间也是冲突的，相邻的写、读操作不能交换顺序。
  • 写-写操作：两个写操作的顺序不同，会对这个调度的执行结果有影响，因此两个相邻的写操作是冲突的。

需要注意的是，假设以上4种操作序列中读写的都是相同的对象。
这样可以得到冲突（Conflict）的定义：如果两个分属于不同事务的操作中有一个是写操作，且两个操作针对的是同一个数据库对象，那么这两个操作是冲突的。
冲突的操作不能交换执行顺序，不冲突的操作可以交换执行顺序（根据调度的定义，同一事务内的操作顺序是固定的，因此不考虑同一事务的操作交换执行顺序），因此可以通过交换不冲突的操作来获得等价的执行序列。
假设有多个事务并发执行，一个调度S通过交换其中不冲突的操作得到一个等价的新的调度S’，就称S和S’是冲突等价的。
如图8所示，调度S中的R1(x)和R2(x)是不冲突的，因为它们都是读操作；R1(x)和R2(y)也是不冲突的，因为它们操作的不是同一个数据库对象（当然也因为它们都是读操作）；R1(x)和W2(y)也是不冲突的，因为它们操作的不是相同的数据库对象，因此可以把R1(x)通过3次交换，交换到S’调度的尾部。
图8 冲突等价的示例
如果一个调度和某一个串行调度是冲突等价的，那么这个调度就是冲突可串行化的。假设有一组事务，如果两个事务中含有冲突的操作，那么可以根据冲突操作的先后关系画出一条边。
如果将事务看作图的顶点，那么这组事务就可以按照冲突操作的先后顺序构成一个优先图。如果优先图中没有环，则认为这一组事务的当前调度是冲突可串行化的。
如图9所示，有事务序列T1和T2，在并发执行的情况下存在调度S和调度S’。
图9 冲突可串行化示例
从图中可以看出，调度S中的R1(x)和W2(x)是冲突的，因此有一条T1->T2的边；W1(y)和R2(y)是冲突的，也有一条T1->T2的边；可以看出调度S的优先图中没有环，因此调度S是冲突可串行化的。而调度S’中R2(y)和W1(y)是冲突的，因此有一条T2->T1的边；R1(x)和W2(y)是冲突的，有一条T1->T2的边；可以看出调度S’是有环的，因此调度S’不是冲突可串行化的。

并发控制

并发控制还可以分为乐观并发控制和悲观并发控制，这两种控制思想是从“何时检测冲突”的角度来定义的。
乐观并发控制属于事后检测冲突的并发控制，通常分为以下3个阶段。

  • 读阶段（Read Phase）：事务维护一个读集合和一个写集合，并且将对对象的写操作存放到私有空间中。
  • 有效性确认阶段（Validation Phase）：在事务提交时，每个事务都需要检查自己的读集合和写集合，这两个集合记录了事务运行的历史信息，如果发现某个事务违反了可串行化原则，那么这个事务终止。
  • 写阶段（Write Phase）：在有效性确认之后，对事务在私有空间中的数据进行应用，事务提交成功。

悲观并发控制则在事先检测冲突，它在识别到冲突的操作后，就可以尝试阻塞冲突的一方，从而实现事务的冲突可串行化。
例如，两阶段锁技术就属于悲观并发控制的范畴，它在读取数据库对象时给对象加共享锁，而在修改数据库对象时对对象加排他锁，这样就能保证事务在并发的过程中不会出现各种异常现象。

两阶段锁

要实现冲突可串行化的调度，可以采用对数据库对象封锁的方式。
当读取一个数据库对象时，可以对这个对象加共享锁（S锁）。
当修改一个数据库对象时，可以对这个对象加排他锁（X锁）。
加锁操作需要在访问数据库对象之前执行，而放锁的时机就比较微妙了。
如果要实现一个真正的可串行化调度，那么需要借助两阶段锁机制。两阶段锁协议将事务的封锁过程分成了以下两个阶段。

  • 增长阶段（Growing Phase）：事务可以尝试申请任何类型的锁，但是这个阶段不允许释放锁。
  • 收缩阶段（Shrinking Phase）：事务可以放锁，但是禁止再申请新的锁。

可以借助反证法来证明两阶段锁的正确性，从两阶段锁的描述中可以看出，它的增长阶段和收缩阶段是严格区分的，也就是说加锁和放锁不会穿插进行。
因此可以假设有一组事务{T1, T2, T3,…,Tn}，该组事务采用两阶段锁的方法对本事务的操作进行控制。再假设它的优先图是有环的，也就是说该组事务的当前调度不是冲突可串行化的，如图10所示。
图10 通过反证法证明2PL的正确性
由优先图的关系可以得知，T1->T2有冲突依赖，即这两个事务在同一个对象上有冲突操作，那么必须是T1先释放锁，T2才被允许操作（读或写）这个对象（即对这个对象加锁）。
如果T1和T2都遵守两阶段锁协议，那么，T1处于收缩阶段之后，T2处于增长阶段；进而可知，当T2处于收缩阶段时，T3则处于增长阶段。依此类推。
由于优先图有环，也就是存在Tn->T1的冲突依赖，所以当Tn处于收缩阶段时，T1才能处于增长阶段。
而已经假设T1处于收缩阶段了，这违背了两阶段锁协议。由此可知，优先图中如果有环，就不满足两阶段锁协议的要求。
PostgreSQL中的封锁协议在2PL的基础上又有所增强，它基于S2PL（Strict-2PL）进行封锁。S2PL和2PL的主要区别在于放锁的时间，S2PL在事务提交时统一放锁。