「分布式技术专题」并发系列一：基于加锁的并发控制

并发控制分类

数据库中如果出现了冲突，一般有几种情况。两个操作同时访问了相同的数据库条目， 并且他们中的任意一个是写操作，那么它们就是冲突的。

众所周知，读操作是不会相互冲突的，冲突的类型只有两种：读 -写（或写-读）和写-写冲突， 并且无论这两个操作是属于相同的事务还是属于不同的事务。

直观上，两个操作相冲突表明它们之间的执行顺序很重要，而两个读操作的顺序不重要。

从可串行化的角度来看的话，我们只需要处理事务中相互冲突的操作，而不是所有的操作。

为了实现并发，需要加入并发控制来避免冲突，一般的分类方式是基于同步原语的，可以依据它将并发控制分为两类：基于对共享数据进行互斥访问的（基于锁 )，以及基于将事务的执行根据一系列规则进行排序的(基于协议）。

另一个视角来看，就是悲观视角和乐观视角，悲观视角假设很多事务都会相互冲突， 而乐观视角则假设并没有太多的事务会相互冲突。

悲观视角会在并发事务执行周期的早期对它们进行同步；而乐观视角则会将这种同步推迟到事务提交之后。并发控制机制的总体分类如图所示：

concurrent1
在本文中主要讨论基于加锁的并发控制。

基于加锁的并发控制的基本思想是：如果多个冲突的操作会访问同一个数据项， 那么就保证这个数据项一次只被其中的一个访问。这可以由为每个锁单位分配一个锁来实现。一个锁会在开始访问事务的时候被设置，然后在使用过后重置。显然，如果一个锁单位已经被一个操作锁住，那么其他操作就不能访问它了。因此，当且仅当锁未被别的事务占用的时候，一个事务才能申领到锁。

由于要做的事是同步冲突事务中的冲突操作，因此将分配给每个锁单位的锁分为两种类型（锁模式）：读锁（ read lock）和写锁（write lock）。如果两个事务可以同时申请到锁，说明两个锁是相容的。就如前边提到的一样，所有的读锁都相容，读-写和写-写锁不相容。因此， 两个事务可以并发的读取同一数据项。

锁定义

分布式数据库会承担事务的锁管理的任务。在基于加锁的系统中，调度程序是一个锁管理程序。

concurrent2
如图，首先事务管理程序将数据库操作（读或者写）传递给锁管理器，并将相应的信息关联起来 (如被访问的数据项、发起数据库操作的事务标志符等)。

然后， 锁管理程序检查包含数据的锁单位是否已经上锁。如果已经上锁，并且锁模式与当前事务不相容， 那么久延迟处理当前数据库操作；否则的话，就要将锁单位设置为期望的锁模式， 并将数据库操作传递给数据处理程序以进行实际的数据访问。

事务管理程序会接收到操作结果的提示，而在当前事务终结之后，就可以释放相应的锁， 并且可以允许其他需要访问相同数据项的事务继续运行了。

遗憾的是，上述算法无法正常对事务执行进行同步。这是因为，为了生成可串行化的顺序， 事务的加锁和解锁操作同样需要与其他操作放在一起进行协调。
示例如下，有两个事务：
T1: BEGIN T2: BEGIN
A=A-100 A=A1.06
B=B+100 B=B1.06
COMMIT COMMIT
对于这个例子， A=1000,B=1000,T1和T2并发执行，如果T1->T2或者T2->T1的顺序执行， 对于最终结果都是正确的。
T1: T2:
BEGIN
A=A-100
BEGIN
A=A1.06
B=B+100
COMMIT
B=B1.06
COMMIT
这样也可以得到最终正确的结果。
T1: T2:
BEGIN
A=A-100
BEGIN
A=A1.06
B=B1.06
COMMIT
B=B+100
COMMIT
这时的执行顺序为：
T1: T2:
BEGIN
R(A)
W(A)
BEGIN
R(A)
W(A)
R(B)
W(B)
COMMIT
R(B)
W(B)
COMMIT
这时 A+B=2014,结果错误。

这里的问题是，加锁算法会在数据库命令（读或写）执行完后就立即释放与事务相应的锁。在这之后，锁单位 (比如x)就不会再被访问了。但是，x的锁被释放之后， 其他锁单位(比如y)上依然会有由该事务设置的锁。虽然这似乎有利于提高并发性， 但是会让事务之间相互影响，以至于丧失了隔离性和原子性。

这就是我们需要两阶段锁的原因。

两阶段锁的规则很简单，即：不允许事务在释放了它的任何一个锁之后请求新的锁， 直到能够确定一个事务不再请求新的锁，它已有锁才可以释放。
两阶段锁将事务执行分为两个阶段：增长阶段和收缩阶段。在增长阶段，事务会申请锁并访问数据项；在收缩阶段，事务会释放它的锁。人们已经证明， 任何一个遵守两阶段锁协议（ Eswaran et al., 1976）的并发控制算法生成的执行序列都是可串行化的。

concurrent3
在增长阶段之后不允许继续获得或者更新锁。对于数据项的访问一旦结束，锁管理器就会释放锁， 这样其他正在等待的事务就可以锁住该数据项并继续运行了，系统的并发性可以得到提高。

原理看起来挺简单，但实现起来还是有难度的，首先，怎么确定已经从增长阶段转到收缩阶段呢， 也就是需要锁管理器确定事务已经获得了所有需要的锁；其次，锁管理器也需要确定事务 不再访问某一数据项，这样，它就能及时释放锁，最后，如果事务在释放锁以后发生了取消操作， 那么访问过响应的解锁后的数据项的其他事务也需要取消。也就是级联取消。实现上涉及到事务中锁的声明周期管理，数据的访问，回滚的级联取消等等难点。
级联取消示例
T1: T2:
BEGIN
A=A-100
BEGIN
A=A1.06
B=B+100
ABORT
B=B1.06
COMMIT
这个顺序符合两阶段锁协议规则，但 T1的取消也会导致T2的取消，也就是导致了级联取消。

级联取消问题可以使用严格两阶段锁方式来解决，严格两阶段锁要求所有锁必须在事务终结时 （提交或取消）一同释放 ,要求事务写入的值在事务完成之前不能被其他事务读取或覆盖。严格两阶段锁的优点是不会引起级联取消，取消的事务可以通过恢复修改后的元组的原始值 来完成。

这里又存在一个问题，虽然两阶段锁算法生成的顺序都是冲突可串行化的， 但并不是所有的冲突可串行化的顺序都符合两阶段锁规则，如这个顺序： {W1(X),R2(X),W3(Y),W1(Y)}。这个顺序不符合两阶段锁规则， 因为在T1需要释放x写锁之后申请了一个Y的写锁。这里标号1-3代表事务，W代表写， R代表读，X,Y代表数据项。因此，在设计加锁算法时需要考虑加锁顺序，以便让顺序符合2PL, 例如将顺序变成T3->T1->T2。

由上边的例子可以看出，冲突操作的执行顺序和对冲突的预先检测同样重要。所以， 除了读锁（共享锁）和写锁（独占锁）外，还有第三种锁模式，有序共享锁（ ordered shared lock)。有序共享锁意味着读-写之间需要进行有序共享的方式进行相容。

加锁的方式可能会造成系统的死锁，这是因为允许对资源的独占访问，两个访问相同数据项的事务 是可以以相反的顺序对数据项进行加锁的，这会造成其中一个事务无限等待另一个事务释放锁， 从而引发死锁。

在数据库中锁还需要考虑数据库的层次结构，因为数据库都是由库，表，元组，属性等级别组成， 可以看做一个树形结构，比如说在表级别加锁，表的叶子节点（元组以及属性）是否需要锁定。这里就有意向锁（ intention lock）,意图锁允许更高级别的树节点被锁定在共享或独占锁模式中， 而不必检查所有的子节点。而意向锁又分为Intention-Shared（IS)、Intention-Exclusive （IX）、Shared-Intention-Exclusive（SIX）等，主要就是在对于这个层级结构的 的不同级别使用独占、共享等锁模式的不同来进行分类，这里不再展开。意向锁可以有效的提高数据库的并发。意向锁在传统关系型数据库中是非常有用的，甚至在各类数据库中可以显式的定义锁（非SQL标准)， 例如在PostgreSQL、Oracle、DB2中，显示锁定表：

LOCK TABLE

IN MODE。

分布式两阶段算法

上一节所提到的两阶段锁可以很容易的扩展到分布式数据库环境中。分布式两阶段锁可分为：
• 集中式两阶段锁
• 分布式两阶段锁

集中式两阶段锁

一种方式是将锁管理的任务交给一个单独的节点来完成，这意味着所有的节点， 只有一个拥有锁管理程序，其他节点中事务管理程序只是相互通信， 而不是与各自的锁管理器通信 (它们不存在锁管理器）。这种方式被称为主节点2PL （primary site 2PL)。
依据集中式 2PL，在执行一个事务的时候，站点之间的通信是在事务发起节点的事务管理程序 (称为协调事务管理器coordinating TM)、中心节点上的锁管理器™以及 其他节点中的数据处理程序(DP)之间进行的。

concurrent4
在图中标明了各个消息的顺序。协调 TM作为语句入口，主锁TM进行锁管理，数据库操作 在各数据节点上存储的数据项中进行。

集中式两节点锁又一个公认的缺点是：主节点会很快成为整个系统的瓶颈。另外， 主节点外的节点失效或无法访问会造成系统的严重故障，从而导致系统变得很不可靠。如果事务量不大时还不明显，这一瓶颈在事务数量增多的时候会显得越发明显。

分布式两阶段锁

分布式两阶段锁要求每个站点都有一个锁管理器，依据分布式两阶段锁协议， 事务在执行时各节点之间的通信如图。

concurrent5
与中心两阶段锁类似，但有两个改动：
• 发送给中心节点的锁管理程序消息变成发送给所有参与节点的锁管理程序
• 数据操作不在由协调事务管理程序发送给数据处理程序，而是由多个调度节点进行传递。
这意味着协调事务管理程序不再需要等待锁请求已批准了。这里有个变种是，参与节点不需要 等待所有参与节点告知协调 TM操作结束由协调节点发送释放锁消息，而是， 每个数据处理程序只向它自己的锁管理程序发送消息，而每个锁管理程序负责释放锁， 并通知协调事务管理程序。
由于有多个调度节点，分布式两阶段锁需要使用选举投票的方式来决定 COMMIT和ABORT， 优点也显而易见，没有了单点瓶颈。

总结

本文介绍了基于锁的并发控制，基于锁的并发控制有效的保证了数据操作的原子性，但想要设计一套好的分布式两阶段算法， 并进行工程化并不简单，需要考虑很多因素。

例如以下几个维度：
• 故障，可以容忍节点故障和通信故障(网络分区、超时)等
• 阻塞，例如进程在不确定区间超时，或者通信进程不确定导致的阻塞。
• 时间复杂度，传统关系型数据库可以把读写控制在1ms以下，分布式包含更多的通信， 选举投票，每一步耗时过长都会有影响。
• 消息复杂度，假设参与者数目为n，两阶段提交每轮都有n个消息被发送，在没有故障的情况下，协议就会产生3n个消息。
所以，实现分布式两阶段提交，并持续优化，是一个很大的课题。

 

以上为基于加锁的并发控制， 「分布式技术专题」是国产数据库 hubble 团队精心整编，专题会持续更新，欢迎大家保持关注。