08 | 底层硬核原理：从锁的思路来看并发控制的技术实现

新架构思考 2021-09-08

1273

你好，我是于文涛。回顾一下上节课的重点内容：

不同事务对同一个数据元素进行读—读操作是不冲突的；不同事务对不同数据元素的任何操作都是不冲突的；
任何一个调度，在保证冲突操作次序不变的情况下，不断交换相邻两个不冲突操作次序，就会产生一个冲突可串行化的调度；冲突可串行化的调度一定是正确的调度；可采用优先图来判断一个调度是否是冲突可串行化的；
实现冲突可串行化的方法有基于锁的方式和基于乐观的方式两种。

本节内容主要介绍基于锁的方式来实现并发控制。

什么是锁？

锁，作用在被操作的数据元素之上，是控制并发访问数据的一个工具。和现实中住户的房门锁一样，加了锁之后，就可以对被保护的对象加以有效的控制，避免被随意的访问和恶意破坏。

每一个数据元素都有一个锁，事务需要先向调度器申请获取锁，获取锁之后才能对数据进行读、写操作，操作完之后要释放锁。如果事务没有释放锁，其他事务是不能对该数据元素进行更新操作的。申请获取锁的过程就是加锁（Lock），释放锁的过程就是解锁(UnLock)。

锁的作用是什么？

如果一个事务对某一个数据元素加了锁(排它锁），其他事务只能等待该锁的释放，延迟了对该数据元素的读写操作。所以，调度器是可以使用锁来保证冲突可串行性的。

加完锁之后，任何情况下都能够保证冲突可串行性么？

并不是这样，锁只是一个手段和工具。对锁如何使用是更为关键的，也就是对锁的使用协议的不同，决定了能否达成该目标。

锁协议包括哪些方面的内容？

锁的协议（Locking Protocol）是指对数据元素进行锁操作时约定的一系列规则。它需要考虑几个方面，包括锁的类型的选择、锁的相容性考虑、加锁和解锁的时机、锁的粒度大小等内容。

锁的类型，锁有哪些类型？

共享锁，Shared locks（又称读锁，S锁）	一个事务加了共享锁之后，其他事务仍然可以对该数据元素加共享锁，也就是所有事务都可以读该数据元素，但都不可以写。
排它锁，eXclusive locks（又称写锁，X锁）	一个事务对数据元素加排它锁之后，只有该事务可以读、写；其他任何事务都不能再加排它锁，也就不可以读、写。更新
更新锁（Update locks，U锁）	初始是读锁，以后可以升级为写锁。为了避免读锁升级写锁过程中产生死锁问题，可以使用更新锁。关于更新锁的内容详细解释，参考：更新锁
增量锁（Incremental locks，I锁）	增量更新时候使用该锁，比如i=i+x;操作，如果一个事务对i变量增量加x；其他事务对该变量增量加y，这些操作之间顺序是可以交换的。

在加锁的时候，通过锁的类型区分，我们就知道了可以去加哪些类型的锁。而锁与锁是什么样的关系，需要通过锁的相容性矩阵来考虑。

锁的相容性矩阵，授予锁的规则是怎样的？

什么是锁的相容性？锁的相容性是指当一个事务已经持有了某一个数据元素的锁之后，其他事务如果也想对该数据元素进行加锁操作，是否允许其同时加锁请求的规则。这个规则可以用矩阵的方式来表示：

锁是否相容	新申请锁的类型
共享锁	排它锁	更新锁
已持有锁的类型	共享锁	是	否	是
排它锁	否	否	否
更新锁	否	否	否

可以看出：

如果一个事务已经持有了共享锁，其他事务是可以继续申请共享锁和更新锁的，这样，多个事务就可以同时对同一个数据元素进行读取操作，提高了事务读与读操作的并发度。一般用于SELECT对数据无变更的操作中。
如果持有排它锁，其他事务是不可以申请任何形式的锁的，这样，就可以提高事务的一致性，同时也降低了事务读-写和写-读的并发度。一般用于INSERT、DELETE 或 UPDATE对数据有变更的操作中。

通过锁的相容性矩阵的了解，就知道了一个事务已加完锁之后，其他事务是否可以继续加锁，以及加什么类型的锁；

还有一个重要问题没有解决，就是什么时机加锁？所加的锁存在多长时间？以及什么时机解锁？

这就引出了封锁协议，不同的协议规定了不同的加锁和解锁的时机。

加锁和解锁的时机是怎样的？

根据加锁和解锁的时机不同，分为不同的封锁协议，包括：0级协议、一级协议、二级协议、三级协议、四级协议。随着协议级别越高，对锁的使用越严格，一致性也越高。

不同协议的加、解锁的时机，区别如下：

封锁协议	加锁时机	解锁时机	一致性保证	对应隔离级别
何时加X锁	何时加S锁	何时释放X锁	何时释放 S锁	不允许异常	允许异常
0级协议	写操作前对数据元素加X锁	不加S锁	写操作完立刻对数据元素释放X锁	无S锁释放	丢失修改	脏读、不可重复读、幻读	未提交读
一级协议	写操作前对数据元素加X锁	不加S锁	写操作完不立刻释放X锁，事务COMMIT或者ROBACK时再释放X锁	无S锁释放	丢失修改；同时保证事务是可恢复的；	脏读、不可重复读、幻读	未提交读
二级协议	写操作前对数据元素加X锁	读操作前对数据元素加S锁	写操作完不立刻释放X锁，事务COMMIT或者ROBACK时再释放X锁	读操作完立刻释放S锁	丢失修改、脏读	不可重复读、幻读	提交读
三级协议	写操作前对数据元素加X锁	读操作前对数据元素加S锁	写操作完不立刻释放X锁，事务COMMIT或者ROBACK时再释放X锁	读操作完不立刻释放S锁，事务COMMIT或者ROBACK时再释放S锁	丢失修改、脏读、不可重复读	幻读	可重复读
四级协议	实现方式比如对整个表加锁，不允许任何其他事务对该表进行同时操作	丢失修改、脏读、不可重复读、幻读等	任何都不允许	可序列化

隔离级别和锁的协议，虽然大致有上述的对应关系，但并不十分精确，具体实际中还需要根据不同的数据库，采用不同的技术实现。

关于事务的隔离级别的更多介绍，参考经典论文：

Generalized Isolation Level Definitions

前面的锁的类型、锁的相容是针对锁本身而言的；

加锁和解锁的时机是针对锁的时间维度而言的；

而锁的粒度是针对锁的作用范围而言的。

锁的粒度多大合适？

锁的粒度大小决定了锁作用的数据元素对象的大小。

一般从大到小，范围可以分为：

整个数据库->整个关系表->多条记录行->单条记录行->某行的属性值

随着锁的粒度逐渐变小，并发度也逐渐增大，但是锁的开销也越大。

上面讲的锁的相容性矩阵只是简单的锁之间的关系，实际中还有其他类型的锁，比如意向锁。

意向锁的锁定粒度是表级锁，也就是锁定整个关系表，它的含义是指，后续需要对表中的行加哪种类型的锁，是共享锁还是排他锁。

关于意向锁以及间隙锁的更多内容，请参考：Intention Locks

前面我们已经回答了并不是任何情况下，加完锁之后都能保证调度的冲突可串行性。也介绍完了锁的协议需要考虑的四方面的内容。下面就介绍具体的可以保证冲突可串行化的锁协议。

什么样的锁协议可以保证冲突可串行性呢？

什么的锁协议可以保证冲突可串行性呢？

答案是2PL: 两阶段锁协议（Two-Phase Locking Protocal）。

学术界已经证明，并发事务都满足二阶段锁协议，对这些事务的任何并发调度都一定是冲突可串行化的（反之不然），因此不需要再对这些调度进行冲突的检测，最终调度执行的结果也一定是正确的。

更多信息参考Kapali Eswaran and Jim Gray在1976年写的论文 The Notions of Consistency and Predicate Locks in a Database System

两阶段锁协议的内容

两阶段锁协议的具体内容如下：

事务写数据元素之前一定要先加排他锁，写完之后进行解锁。
事务读数据元素之前一定要先加共享锁，读取完之后进行解锁。
2PL要求每个事务（所有事务）的加锁操作（排它锁或共享锁）都要放在所有的解锁操作之前，任意一个解锁操作之后都不能有新的加锁操作。
因此，所有的事务操作被分成了两个阶段:

第一阶段是锁数量不断增长的阶段，称为锁扩张阶段 (expanding phase)。

第二阶段是锁数量逐渐减少的阶段，称为锁收缩阶段(shrinking phase)。

在锁扩张阶段中，事务可以申请获取任何数据元素的锁，但是不能有解锁操作。在锁收缩阶段中，事务可以释放任何数据元素的锁，但不能有加锁操作。

举例如下图所示：

在这个图里面，事务T1,T2,Tx的加锁操作L1(A),L1(B),L2(A),L2(B),Lx(A),Lx(B)全都在加锁阶段里，该阶段里没有任何的解锁操作。

同样，事务T1,T2,Tx的解锁操作U1(A),U1(B),U2(A),U2(B),Ux(A),Ux(B)也都处在解锁阶段里面，该阶段没有任何的加锁操作。

两阶段锁协议的变种

两阶段锁协议虽然可以保证冲突可串行化，但是不能避免级联回滚和死锁的问题。

“ The above mentioned type of 2-PL is called Basic 2PL. To sum it up it ensures Conflict Serializability but does not prevent Cascading Rollback and Deadlock.”

详细内容参考：Two Phase Locking Protocol

因此两阶段协议有了新的协议的变种：

严格两阶段锁协议-S2PL（Strict Two-Phase Locking Protocal）

严格两阶段锁协议，除了满足2PL的要求外，加了另外的限制：

要求排它锁不能在事务提交（或撤销）之前释放；
必须在事务提交（或者撤销）之后，同时释放所有锁。

这就是说，在事务没有提交时，排他锁是不能释放的，这就保证了该事务对数据的修改是不能被其他事务所读取和修改的，因此S2PL避免了级联回滚的问题。

对于死锁问题，严格两阶段锁跟两阶段锁一样，也是不能避免的，这是因为，解决死锁的方法—一次封锁法，需要一次性将所需要的数据元素全部加锁，这两个协议并不强制要求事先把所有数据元素全部加锁，所以跟一次封锁法是不同的。

强两阶段锁协议-SS2PL （Strong Strict Two-Phase Locking Protocal）

强两阶段锁协议，不仅要满足严格两阶段锁协议的内容，还加了新的限制：

共享锁和排它锁都不能在事务提交之前释放。

强两阶段锁跟严格两阶段锁相同点：都解决了级联回滚问题，但是都无法避免死锁问题；
两者的不同点：强两阶段锁的限制更严格一些，但实现起来更容易一些。

注意：

2PL跟2PC很像，要注意区分，2PC是表示两阶段提交，跟本文中的两阶段锁是有很大不同的。关于2C的内容，我们在“第09讲：彻底搞懂两阶段提交协议和三阶段提交协议”中讲解。

总结：

回顾一下本文的内容。我们本文中介绍的是基于悲观的思路，也就是基于锁的方式来实现的并发控制。

我们开始对锁的各种类型，相容性矩阵和锁的协议要考虑的几方面内容进行了介绍，接着重点介绍了两阶段锁这个可以保证冲突可串行化的协议，同时介绍了SS2PL协议。

SS2PL技术在数据库产品中应用广泛，Oracle,Mysql,PostgreSQL,DB2，SQL Server数据库都采用了SS2PL+MVCC结合的实现方式。

限于篇幅内容，还有很多锁的细节内容，本文没有展开，文中也给出了很多参考资料和英文论文。这需要大家在课后仔细研究学习，由于涉及的内容比较深，如果有遇到问题，欢迎留言，把你的问题提出来。

关于MVCC的内容，我会在下一讲“第08讲：从乐观的思路来看并发控制的技术实现”中详细介绍，同时该讲也会介绍其他的并发控制方法。到时见！