数据库并发控制协议

全文主要参考数据库系统概念一书以及mooc上战德臣老师的数据库课程
　　事务最基本的特性之一是隔离性，当数据库中有多个事务并发执行的时候，隔离性不一定能保持。为了保持事务的隔离性，系统必须对并发事务之间的相互作用加以控制，这是被称为并发控制机制来实现的。本文讲述的机制都是保证调度是可串行化的。最常用机制有两阶段封锁和快照隔离。

关于串行化与一致性的关系：数据库并发控制的基本目标是确保事务的并发执行不会导致数据库一致性的丢失。可以利用可串行性概念来达到这一目标，因为所有可串行化的调度都能保持数据库的一致性。然而，并非所有保证数据库一致性的调度都是可串行化的。(也存在着允许非可串行化调度的并发控制机制，详见数据库系统概念25章)

一、基于锁的协议

确保串行化的方法之一就是要求对数据项的访问以互斥的方式进行。也就是说当一个事务访问某个数据项时，其他任何=事务都不能修改该数据项。实现该需求最常用的方法是只允许事务访问当前该事务持有该数据项的锁的数据项。

1.共享锁和排他锁

给数据项加锁的方式有多种，这一节只考虑两种(这两种也正是MySQL默认引擎(InnoDB)在行级锁定时所使用的)

1. 共享锁：如果事务Ti获得了数据项Q的共享型锁(记为S)，则Ti可读但不能写Q。
2. 排他锁：如果事务Ti获得了数据项Q的排他型锁(记为X)，则Ti既可读又可写Q。

       每个事务都要根据将对数据项Q进行的操作类型申请适当的锁。该请求发送给并发控制管理器，只有并发控制管理器授予所需锁后，事务才能继续其操作。
　　相容：假设事务Ti请求对数据项Q加A类型的锁，而事务Tj(i不等于j)已在Q上拥有B类型的锁。如果事务Ti仍能立即获得在数据项Q上A类型的锁，则说A类型的锁和B类型的锁相容。相容矩阵如下所示：
 

即共享型锁与共享型锁相容，而与排他型锁不相容。在任何时候，一个具体的数据项上可能同时有(被不同的事务持有的)多个共享锁。如事务在访问一数据项时而在数据项上已经存在可不相容类型的锁，那么只能等待该数据上所有不相容的锁被释放才能获得锁从而对数据项进行访问。
　　注意：一个事务只要还在访问一个数据项，那么它就必须拥有该数据项上的锁。另外，让事务对一个数据项作最后一次访问后立即释放该数据项上的锁也未必是可取的，因为这可能破坏串行化。如下图例子所示，事务T2看到了不一致的状态(A+B的值)，而串行化就是为了事务开始和结束之间的中间状态不会被其他事务看到。所以我们下面的讨论都是建立在不会在结束访问一个数据项后立即释放锁的情况下的(如两阶段锁协议下的)。这也就会导致了死锁发生的可能性的存在，但死锁可以通过回滚事务来解决，出现死锁比出现不一致状态好得多。

2.死锁与饿死

加锁可能会出现两个事务都在等待对方解除它所占用数据项上的锁(也可能是多个事务之间的循环等待)，这种现象称为死锁。当死锁发生时，系统必须回滚两个事务中的一个。一旦某个事务回滚，该事务锁住的数据项就被解锁，其他事务就可以访问这些数据项，继续自己的执行例如下图所示就必须回滚：

饥饿(饿死)：当一个事务想要对一个数据项上加排他锁，因为该数据项上已经有其他事务所加的共享锁了，因此必须等待。而在等待期间又有其他事务对该数据项加上了共享锁，之前的那个事务对一段时间后解除了共享锁，但当前事务还是要继续等待，就这样不断地出现对该数据项加共享锁的其他事务，那么该事务则会一直处于等待状态，永远不可能取得进展，这称为饥饿或者饿死。

避免饿死的方法：合适的并发控制器授权加锁的条件可以规避饿死情况的发生。如，当事务Ti申请对数据项Q加M型锁时，并发控制管理器授权加锁的条件是

• 不存在 已在数据项Q上持有与M型锁冲突的锁 的其他事务
• 不存在 等待对数据项Q加锁并且先于Ti申请加锁 的其他事务(即按照顺序来)

       在这样的授权加锁条件下，一个加锁请求就不会被气候的加锁申请阻塞。

3.两阶段锁协议

保证可串行性的一个协议是两阶段锁协议。该协议要求每个事务分两个阶段提出加锁和解锁申请：

1. 增长阶段：事务可以获得锁，但不能释放锁
2. 缩减阶段：事务可以释放锁，但不能获得锁

例如事务T3和T4是两阶段的，T1和T2不是两阶段的。两阶段锁协议可以保证冲突可串行化，但无法避免死锁的出现。在两阶段对的事务中最后加锁的位置称为锁点(lock point)。
　　两阶段锁协议有两个加强版：严格两阶段锁协议和强两阶段锁协议

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

二、基于时间戳的协议

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

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

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

时间戳的访问顺序

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

时间戳特点

时间戳协议和两段锁协议相似，都是保证了冲突可串行化，但两者都是保证的冲突可串行化的两个不同的真子集，存在满足两阶段锁协议却不能满足时间戳协议的调度，反之亦然。时间戳协议保证冲突可串行化的原因在于：冲突操作是按时间戳顺序进行处理的。
　　死锁：时间戳协议保证了无死锁，因为不存在等待的事务。
　　饿死：当一系列的短事务引起长事务反复重启时，可能导致长事务饿死的现象。解决方式：如果发现一个事务反复重启，与之冲突的事务应当暂时阻塞，以使该事务能够完成。

三、多版本和快照隔离

通过维护数据项的多个版本，一个事务允许读取一个旧版本的数据项，而不是被另一个未提交或者在串行化序列中应该排在后面的事务写入的新版本的数据项。有许多多版本并发控制技术，其中一个是实际中广泛应用的称为快照隔离的技术。
　　在快照隔离中，我们可以视为每个事务开始时都有其自身的数据库版本或者快照(实际实现中不会复制整个数据库，只有被改变的数据项才会保留多个版本)。事务从这个私有版本中读取数据，因此和其他事务所做的更新隔离开，如果事务更新数据库，更新只出现在其私有版本中，而不是实际的数据库本身中。当事务提交时，和更新有关的信息将保存，使得更新被写入真正的数据库。
　　当一个事务T进入提交状态后，只有在 没有其他并发事务已经修改该事务想要更新的数据项 的情况下，事务进入提交状态。而不能提交的事务则终止。
　　快照隔离可以保证读数据的尝试永远无需等待(不像锁协议那样要读的数据项上面被加了排他锁就只能等待)。只读事务不会终止。只有修改数据的事务才有微小的终止风险。由于每个事务读取它自己的数据库版本或快照，因此读数据不会导致此后其他事务的更新尝试被迫等待(不像锁协议要写的数据项中被加了共享锁后就只能等待甚至有饿死的情况)。因为大部分事务是只读的，并且大多数其他事务读数据的情况多于更新，所以这是与锁相比往往能带来性能改善的主要原因。
　　矛盾在于，快照隔离带来的问题是它提供了太多的隔离。考虑两个事务T和T',在一个串行化调度中，要么T看到T'所做的所有更新，要么T'看到T所做的所有更新，因为在串行化顺序中一个必须在另一个之后。在快照隔离下，任何事务都不能看到对方的更新，这是在串行化调度中不会出现的。在许多(事实上，大多数)情况下，两个事务的数据访问不会冲突，因此没有什么问题。DNA一旦T读取的是T'要更新的数据项，T'读取的是T'要更新的数据项，则可能两个事务都无法读取到对方的更新。结果可能导致数据库的不一致状态。
　　详情参看数据库系统概念第六版中的15.5基于有效性检查的协议、15.6多版本机制、15.7快照隔离。
　　注意：根据论文，快照隔离能排除掉严格版本的幻读A3，但对于宽泛版本的P3(实际上使得隔离性更严格了)是不能排出的，此外还存在写偏斜(write skew)的异常。

四、死锁的处理

如果存在一个事务集，该集合中的每个事务都在等待该集合中的另一个事务，那么我们说系统处于死锁状态。更确切地说，存在一个等待事务集{T0,T1,...,Tn}，使得T0正等待被T1锁住的数据项，T1正等待被T2锁住的数据项，....，Tn-1正等待被Tn锁住的数据项，且Tn正等待被T0锁住的数据项。在这种情况下，没有一个事务能够取得进展。
　　此时系统的唯一补救措施就是采取激烈的动作，如回滚某些陷于死锁的事务。事务有可能只部分回滚，即事务回滚到 它得到锁的点 之前，这样就释放了锁从而解决死锁。
　　处理死锁有两种主要的方法：我们可以使用死锁预防协议来保证系统永不进入死锁状态。另一种方法是，我们允许系统进入死锁状态，然后试着用死锁检测与死锁恢复机制进行恢复。两种方法均有可能引起事务回滚。如果事务进入死锁状态概率相对比较高，则通常使用死锁预防机制，否则使用检测与恢复机制。
　　注意：检测与恢复机制所带来的各种开销，不仅包括在运行时维护必要信息及执行检测算法的代价，还要包括从死锁中恢复所固有的潜在损失。

1.死锁预防

预防死锁主要有两种思路：

1. 第一种思路是：通过对加锁请求进行排序(顺序封锁法) 或 要求同时获得所有的锁从而来保证不会发生循环等待(一次封锁法)(就不会发生占着一个数据项的锁还在等着另一个数据项的锁的情况，要么就一起占着要么就都不占)。

       一次封锁法就是要求每个事务在开始之前封锁它的所有的数据项，此外，要么一次全部封锁，要么全不封锁。
　　一次封锁协议主要的缺点是：(1)在事务开始前通常很难预知哪些数据项需要封锁。(2)数据项的使用率可能很低，因为很多数据项可能封锁很长时间却用不到。
　　顺序封锁法是对所有的数据项强加一个次序，同时要求按次序规定的顺序对数据项进行加锁。
　　顺序封锁法存在的问题：维护成本高。数据库系统中可封锁的数据对象极其众多，并且随数据的插入、删除等操作而不断地变化，要维护这样极多而且变化的资源的封锁顺序非常困难，成本很高。

2. 第二种思路比较接近死锁恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。
       这种思路的实现方式是使用抢占和事务回滚。在抢占机制中，若事务Tj所申请的锁已经被事务Ti所持有，则授予Ti的锁可能通过回滚事务Ti被抢占，并将锁授予Tj。为控制抢占，我们给每个事务赋予一个唯一的时间戳，系统仅用时间戳来决定事务应当等待还是回滚。并发协议仍使用封锁协议，若一个事务回滚，则该事务重启时保持原有的时间戳。
　　根据此思路提出的两种相反的预防机制：

• wait-die机制：当事务Ti申请的数据项被Tj持有，仅当Ti的时间戳小于Tj的时间戳时，允许Ti等待。否则Ti回滚。即如老可等
• wound-wait机制：当事务Ti申请的数据项被Tj持有，仅当Ti的时间戳大于Tj的时间戳时，允许Ti等待。否则Tj回滚。(Tj被Ti伤害)即如少可等，如老伤少

       两种机制的缺点都是：可能会发生不必要的回滚。

3. 还有一种额外的思路是锁超时机制，申请锁的事务至多等待一段给定的时间。若此时间内为授予该事务锁，则称该事务超时，则该事务会进行回滚并重启。该机制介于死锁预防(不会发生死锁)和死锁检与恢复之间。
　　锁超时机制实现起来及其容易，但其缺点在于很难确定一个事务超时之前应等待多长时间，过长则会在死锁时造成延迟，过短则会造成不必要的回滚。所以仅应用于事务主要是短事务并且长时间的等待极可能是死锁造成的情况下。

2.死锁恢复挖坑待填