概述

如何控制并发是数据库领域中非常重要的问题之一，不过到今天为止事务并发的控制已经有了很多成熟的解决方案，而这些方案的原理就是这篇文章想要介绍的内容，文章中会介绍最为常见的三种并发控制机制：

分别是悲观并发控制、乐观并发控制和多版本并发控制，其中悲观并发控制其实是最常见的并发控制机制，也就是锁；而乐观并发控制其实也有另一个名字：乐观锁，乐观锁其实并不是一种真实存在的锁，我们会在文章后面的部分中具体介绍；最后就是多版本并发控制（MVCC）了，与前两者对立的命名不同，MVCC 可以与前两者中的任意一种机制结合使用，以提高数据库的读性能。

串行调度

定义多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同，称这种调度策略为可串行化（serializable)调度。

可串行性（serializability)是并发事务正确调度的准则。按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

悲观并发控制

控制不同的事务对同一份数据的获取是保证数据库的一致性的最根本方法，如果我们能够让事务在同一时间对同一资源有着独占的能力，那么就可以保证操作同一资源的不同事务不会相互影响。

最简单的、应用最广的方法就是使用锁来解决，当事务需要对资源进行操作时需要先获得资源对应的锁，保证其他事务不会访问该资源后，在对资源进行各种操作；在悲观并发控制中，数据库程序对于数据被修改持悲观的态度，在数据处理的过程中都会被锁定，以此来解决竞争的问题。

封锁协议

封锁是实现并发控制的一个非常重要的技术。所谓封锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其他事务不能更新此数据对象。

确切的控制由封锁的类型决定。基本的封锁类型有两种：排他锁（exclusive locks,简称X锁）和共享锁（share locks,简称S锁）

排他锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁为止。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。

共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁为止。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。

一级封锁协议

一级封锁协议是指，事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT)和非正常结束（ROLLBACK)。

一级封锁协议可防止丢失修改，并保证事务T是可恢复的。

二级封锁协议

二级封锁协议是指，在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。

二级封锁协议除防止了丢失修改，还可进一步防止读“脏”数据.

三级封锁协议

三级封锁协议是指，在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。

三级封锁协议除了防止丢失修改和读“脏”数据外，还进一步防止了不可重复读。

上述三级协议的主要区别在于什么操作需要申请封锁，以及何时释放锁（即持锁时间）。不同的封锁协议使事务达到的一致性级别是不同的，封锁协议级别越高，一致性程度越高。

实现:两段锁协议

为了保证并发调度的正确性，数据库管理系统的并发控制机制必须提供一定的手段来保证调度是可串行化的。目前数据库管理系统普遍采用两段锁（TwoPhase Locking,简称2PL)协议的方法实现并发调度的可串行性，从而保证调度的正确性。

两阶段锁协议（2PL）是一种能够保证事务可串行化的协议，所谓“两段”锁的含义是，事务分为两个阶段，第一阶段是获得封锁，也称为扩展阶段，在这个阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁；第二阶段是释放封锁，也称为收缩阶段，在这个阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。

  1. 在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁；

  2. 在释放一个封锁之后，事务不再申请和获得任何其他封锁。

事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。

两阶段锁协议有两个加强版：严格两阶段锁协议和强两阶段锁协议

  • 严格两阶段锁协议：在两阶段锁协议的基础上，还要求事务持有的所有排他锁必须在事务提交之后方可释放。
  • 强两阶段锁协议：在两阶段协议的基础上，要求所有锁都必须在事务提交之后方可释放。

两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁.

活锁(饥饿)

如果事务T1封锁了数据R,事务T2又请求封锁R,于是T2等待；T3也请求封锁R，当T1释放了 R上的封锁之后系统首先批准了T3的请求，T2仍然等待；然后T4又请求封锁R，当T3释放了 R上的封锁之后系统又批准了T4的请求……T2有可能永远等待，这就是活锁的情形.

避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。

死锁

如果事务T1封锁了数据R1,T2封锁了数据R2，然后T1又请求封锁R2，因T2已封锁了 R2,于是T1等待T2释放R2上的锁；接着T2又申请封锁R1，因T1已封锁了R1,T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2,而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。

死锁的预防

有两种方式可以帮助我们预防死锁的出现，一种是保证事务之间的等待不会出现环，也就是事务之间的等待图应该是一张有向无环图，没有循环等待的情况或者保证一个事务中想要获得的所有资源都在事务开始时以原子的方式被锁定，所有的资源要么被锁定要么都不被锁定。

但是这种方式有两个问题，在事务一开始时很难判断哪些资源是需要锁定的，同时因为一些很晚才会用到的数据被提前锁定，数据的利用率与事务的并发率也非常的低。一种解决的办法就是按照一定的顺序为所有的数据行加锁，同时与 2PL 协议结合，在加锁阶段保证所有的数据行都是从小到大依次进行加锁的，不过这种方式依然需要事务提前知道将要加锁的数据集。

另一种预防死锁的方法就是使用抢占加事务回滚的方式预防死锁，当事务开始执行时会先获得一个时间戳，数据库程序会根据事务的时间戳决定事务应该等待还是回滚，在这时也有两种机制供我们选择:

等待-死亡方案（Wait-die Scheme）

该方案是基于非剥夺方法。当事务A请求的资源正被事务B占有时，只有当A的时间戳比事务B的时间戳小时，即A比B老时，A才能等待。否则A被卷回（roll-back），即死亡。

一个事务死亡后会释放他所占用的所有资源。在这里假定死亡的事务将带着同样的时间戳重新运行。由于具有较小时间戳的事务才等待具有较大时间戳的事务，因此很显然死锁不会发生。当事务在等待特定的资源时，不会释放资源。一旦一个事务释放一个资源，与这个资源相联系的等待队列中的一个事务将被激活。

伤害-等待方案（Wound-wait Scheme）

它是一种基于剥夺的方法。当事务A请求的资源正被事务B占有时，只有当事务A的时间戳比事务B的时间戳大时，即A比B年轻时，A才能等待。否则B被卷回（roll-back），即死亡。只要被卷回的事务重新启动时，使用原有的时间戳，这两种方案都能避免死锁和饿死现象。由于时间戳总是增加的，被卷回的事务最终将具有最小的时间戳。

两种方法都会造成不必要的事务回滚，由此会带来一定的性能损失，更简单的解决死锁的方式就是使用超时时间，但是超时时间的设定是需要仔细考虑的，否则会造成耗时较长的事务无法正常执行，或者无法及时发现需要解决的死锁，所以它的使用还是有一定的局限性。

死锁的检测

诊断死锁一般使用超时法或事务等待图法。

超时法

如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。超时法实现简单，但其不足也很明显，一是有可能误判死锁，如事务因为其他原因而使等待时间超过时限，系统会误认为发生了死锁；二是时限若设置得太长，死锁发生后不能及时发现。

等待图法

事务等待图是一个有向图G=(T,U), T为结点的集合，每个结点表示正运行的事务；U为边的集合，每条边表示事务等待的情况。若T1等待T2，则在T1、T2之间画一条有向边，从T1指向T2。

事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如每隔数秒）生成事务等待图，并进行检测。如果发现图中存在回路，则表示系统中出现了死锁。

死锁的恢复

如何从死锁中恢复其实非常简单，最常见的解决办法就是选择整个环中一个事务进行回滚，以打破整个等待图中的环，在整个恢复的过程中有三个事情需要考虑：

每次出现死锁时其实都会有多个事务被波及，而选择其中哪一个任务进行回滚是必须要做的事情，在选择牺牲品（Victim）时的黄金原则就是最小化代价，所以我们需要综合考虑事务已经计算的时间、使用的数据行以及涉及的事务等因素；当我们选择了牺牲品之后就可以开始回滚了，回滚其实有两种选择一种是全部回滚，另一种是部分回滚，部分回滚会回滚到事务之前的一个检查点上，如果没有检查点那自然没有办法进行部分回滚。

在死锁恢复的过程中，其实还可能出现某些任务在多次死锁时都被选择成为牺牲品，一直都不会成功执行，造成饥饿（Starvation），我们需要保证事务会在有穷的时间内执行，所以要在选择牺牲品时将时间戳加入考虑的范围。

锁的粒度

所谓粒度，即细化的程度。锁的粒度越大，则并发性越低且开销大；锁的粒度越小，则并发性高且开销小。

锁的粒度主要有以下几种类型：

  1. 行锁，行锁是粒度中最小的资源。行锁就是指事务在操作数据的过程中，锁定一行或多行的数据，其他事务不能同时处理这些行的数据。行级锁占用的数据资源最小，所以在事务的处理过程中，允许其它事务操作同一表的其他数据。

  2. 页锁，一次锁定一页。25个行锁可升级为一个页锁。

  3. 表锁，锁定整个表。当整个数据表被锁定后，其他事务就不能够使用此表中的其他数据。使用表锁可以使事务处理的数据量大，并且使用较少的系统资源。但是在使用表锁时，会延迟其他事务的等待时间，降低系统并发性。

  4. 数据库锁，防止任何事务和用户对此数据库进行访问。可控制整个数据库的操作。

实现:基于时间戳

另一类实现可串行化的技术是为每个事务分配一个时间戳，这个时间戳通常就是事务的开始的时间。对于每个数据项，系统维护两个时间戳，一个读时间戳和一个写时间戳。数据项的读时间戳记录读该数据项的的事务的最大(即最近的)时间戳，数据项的写时间戳记录写入该数据项当前值的事务的时间戳。时间戳用来确保在访问冲突情况下，事务按照时间戳的顺序来访问数据项。当按照时间戳的顺序，一事务不能访问时，该事务会被中止，并且分配一个新的时间戳重新开始。

时间戳的实现机制有两种:

  1. 使用系统时钟的值作为时间戳，即事务的时间戳等于该事务进入系统这里包括后面的系统一词指的都是数据库系统时的时钟值。
  2. 使用逻辑计数器，每赋予一个时间戳，计数器增加计数，即事务的时间戳等于该事务进入系统时的计数器值。

时间戳的访问顺序:

  1. 对于一个进行读取数据项的事务，只有在当前事务的时间戳大于等于数据项上的写时间戳时，才能进行读取，并将数据项的读时间戳更新为当前时间戳。
  2. 对于一个进行写入数据项的事务，只有在当前事务的时间戳大于等于数据项上的读时间戳以及写时间戳，才能进行写入操作，并将数据项的写时间戳更新为当前时间戳。
  3. 当事务不能满足时间戳顺序要求进行访问操作时，则事务会被回滚，由系统赋予它新的时间戳并重新启动。

时间戳特点:

时间戳协议和两段锁协议相似，都是保证了冲突可串行化，但两者都是保证的冲突可串行化的两个不同的真子集，存在满足两阶段锁协议却不能满足时间戳协议的调度，反之亦然。时间戳协议保证冲突可串行化的原因在于：冲突操作是按时间戳顺序进行处理的。

乐观并发控制

除了悲观并发控制机制 - 锁之外，我们其实还有其他的并发控制机制，乐观并发控制（Optimistic Concurrency Control）。乐观并发控制也叫乐观锁，但是它并不是真正的锁，很多人都会误以为乐观锁是一种真正的锁，然而它只是一种并发控制的思想。

乐观并发控制其实本质上就是基于验证的协议，因为在多数的应用中只读的事务占了绝大多数，事务之间因为写操作造成冲突的可能非常小，也就是说大多数的事务在不需要并发控制机制也能运行的非常好，也可以保证数据库的一致性；而并发控制机制其实向整个数据库系统添加了很多的开销，我们其实可以通过别的策略降低这部分开销。

而验证协议就是我们找到的解决办法，它根据事务的只读或者更新将所有事务的执行分为两到三个阶段：

在读阶段，数据库会执行事务中的全部读操作和写操作，并将所有写后的值存入临时变量中，并不会真正更新数据库中的内容；在这时候会进入下一个阶段，数据库程序会检查当前的改动是否合法，也就是是否有其他事务在 RAED PHASE 期间更新了数据，如果通过测试那么直接就进入 WRITE PHASE 将所有存在临时变量中的改动全部写入数据库，没有通过测试的事务会直接被终止。

为了保证乐观并发控制能够正常运行，我们需要知道一个事务不同阶段的发生时间，包括事务开始时间、验证阶段的开始时间以及写阶段的结束时间；通过这三个时间戳，我们可以保证任意冲突的事务不会同时写入数据库，一旦由一个事务完成了验证阶段就会立即写入，其他读取了相同数据的事务就会回滚重新执行。

作为乐观的并发控制机制，它会假定所有的事务在最终都会通过验证阶段并且执行成功，而锁机制和基于时间戳排序的协议是悲观的，因为它们会在发生冲突时强制事务进行等待或者回滚，哪怕有不需要锁也能够保证事务之间不会冲突的可能。

乐观锁的实现方式主要有两种：CAS机制和版本号机制,下面详细介绍。

实现:CAS机制

CAS操作包括了3个操作数：

需要读写的内存位置(V) 进行比较的预期值(A) 拟写入的新值(B) CAS操作逻辑如下：如果内存位置V的值等于预期的A值，则将该位置更新为新值B，否则不进行任何操作。许多CAS的操作是自旋的：如果操作不成功，会一直重试，直到操作成功为止。

这里引出一个新的问题，既然CAS包含了Compare和Swap两个操作，它又如何保证原子性呢？答案是：CAS是由CPU支持的原子操作，其原子性是在硬件层面进行保证的。

实现:版本号机制

多版本并发控制(MVCC)

到目前为止我们介绍的并发控制机制其实都是通过延迟或者终止相应的事务来解决事务之间的竞争条件（Race condition）来保证事务的可串行化；虽然前面的两种并发控制机制确实能够从根本上解决并发事务的可串行化的问题，但是在实际环境中数据库的事务大都是只读的，读请求是写请求的很多倍，如果写请求和读请求之前没有并发控制机制，那么最坏的情况也是读请求读到了已经写入的数据，这对很多应用完全是可以接受的。

在这种大前提下，数据库系统引入了另一种并发控制机制 - 多版本并发控制（Multiversion Concurrency Control），每一个写操作都会创建一个新版本的数据，读操作会从有限多个版本的数据中挑选一个最合适的结果直接返回；在这时，读写操作之间的冲突就不再需要被关注，而管理和快速挑选数据的版本就成了 MVCC 需要解决的主要问题。

MVCC 并不是一个与乐观和悲观并发控制对立的东西，它能够与两者很好的结合以增加事务的并发量，在目前最流行的 SQL 数据库 MySQL 和 PostgreSQL 中都对 MVCC 进行了实现；但是由于它们分别实现了悲观锁和乐观锁，所以 MVCC 实现的方式也不同。

MySQL 与 MVCC

MySQL 中实现的多版本两阶段锁协议（Multiversion 2PL）将 MVCC 和 2PL 的优点结合了起来，每一个版本的数据行都具有一个唯一的时间戳，当有读事务请求时，数据库程序会直接从多个版本的数据项中具有最大时间戳的返回。

更新操作就稍微有些复杂了，事务会先读取最新版本的数据计算出数据更新后的结果，然后创建一个新版本的数据，新数据的时间戳是目前数据行的最大版本 ＋1：

数据版本的删除也是根据时间戳来选择的，MySQL 会将版本最低的数据定时从数据库中清除以保证不会出现大量的遗留内容。

PostgreSQL 与 MVCC

与 MySQL 中使用悲观并发控制不同，PostgreSQL 中都是使用乐观并发控制的，这也就导致了 MVCC 在与乐观锁结合时的实现上有一些不同，最终实现的叫做多版本时间戳排序协议（Multiversion Timestamp Ordering），在这个协议中，所有的的事务在执行之前都会被分配一个唯一的时间戳，每一个数据项都有读写两个时间戳：

当 PostgreSQL 的事务发出了一个读请求，数据库直接将最新版本的数据返回，不会被任何操作阻塞，而写操作在执行时，事务的时间戳一定要大或者等于数据行的读时间戳，否则就会被回滚。

这种 MVCC 的实现保证了读事务永远都不会失败并且不需要等待锁的释放，对于读请求远远多于写请求的应用程序，乐观锁加 MVCC 对数据库的性能有着非常大的提升；虽然这种协议能够针对一些实际情况做出一些明显的性能提升，但是也会导致两个问题，一个是每一次读操作都会更新读时间戳造成两次的磁盘写入，第二是事务之间的冲突是通过回滚解决的，所以如果冲突的可能性非常高或者回滚代价巨大，数据库的读写性能还不如使用传统的锁等待方式。

总结

从上面对两种控制机制的介绍，我们知道两种控制机制各有优缺点，不可认为一种好于另一种，像乐观控制机制适用于写比较少的情况下（多读场景），即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。但如果是多写的情况，一般会经常产生冲突，这就会导致上层应用会不断的进行retry，这样反倒是降低了性能，所以一般多写的场景下用悲观控制机制就比较合适。

参考:
https://blog.csdn.net/wxl612/article/details/53008579 http://www.voidcn.com/article/p-mlfasteu-ber.html https://www.jianshu.com/p/fbac0c0471f5