纯干货 | 一篇讲透如何理解数据库并发控制

01数据库并发控制的作用

1.1 事务的概念

在介绍并发控制前,首先需要了解事务。数据库提供了增删改查等几种基础操作,用户可以灵活地组合这几种操作,实现复杂的语义。在很多场景下,用户希望一组操作可以做为一个整体一起生效,这就是事务。事务是数据库状态变更的基本单元,包含一个或多个操作(例如多条SQL语句)。

经典的转账事务,就包括三个操作:(1)检查A账户余额是否足够。(2)如果足够,从A扣减100块。(3)B账户增加100块。

事务有个基本特性:这一组操作要么一起生效,要么都不生效,事务执行过程中如遇错误,已经执行的操作要全部撤回,这就是事务的原子性

如果失败发生后,部分生效的事务无法撤回,那数据库就进入了不一致状态,与真实世界的事实相左。例如转账事务从A账户扣款100块后失败了,B账户还未增加款项,如果A账户扣款操作未撤回,这个世界就莫名奇妙丢失了100块。原子性可以通过记日志(更改前的值)来实现,还有一些数据库将事务操作缓存在本地,如遇失败,直接丢弃缓存里的操作。

事务只要提交了,它的结果就不能改变了,即使遇到系统宕机,重启后数据库的状态与宕机前一致,这就是事务的持久性

数据只要存储非易失存储介质,宕机就不会导致数据丢失。因此数据库可以采用以下方法来保证持久性:(1)事务完成前,所有的更改都保证存储到磁盘上了。或(2)提交完成前,事务的更改信息,以日志的形式存储在磁盘,重启过程根据日志恢复出数据库系统的内存状态。一般而言,数据库会选择方法(2),原因留给读者思考。

数据库为了提高资源利用率和事务执行效率、降低响应时间,允许事务并发执行。但是多个事务同时操作同一对象,必然存在冲突,事务的中间状态可能暴露给其它事务,导致一些事务依据其它事务中间状态,把错误的值写到数据库里。需要提供一种机制,保证事务执行不受并发事务的影响,让用户感觉,当前仿佛只有自己发起的事务在执行,这就是隔离性

隔离性让用户可以专注于单个事务的逻辑,不用考虑并发执行的影响。数据库通过并发控制机制保证隔离性。由于隔离性对事务的执行顺序要求较高,很多数据库提供了不同选项,用户可以牺牲一部分隔离性,提升系统性能。这些不同的选项就是事务隔离级别

数据库反映的是真实世界,真实世界有很多限制,例如:账户之间无论怎么转账,总额不会变等现实约束;年龄不能为负值,性别最多只能有男、女、跨性别者三种选项等完整性约束。事务执行,不能打破这些约束,保证事务从一个正确的状态转移到另一个正确的状态,这就是一致性

不同与前三种性质完全由数据库实现保证,一致性既依赖于数据库实现(原子性、持久性、隔离性也是为了保证一致性),也依赖于应用端编写的事务逻辑。

1.2 事务并发控制如何保证隔离性

为了保证隔离性,一种方式是所有事务串行执行,让事务之间不互相干扰。但是串行执行效率非常低,为了增大吞吐,减小响应时间,数据库通常允许多个事务同时执行。因此并发控制模块需要保证:事务并发执行的效果,与事务串行执行的效果完全相同(serializability),以达到隔离性的要求。

为了方便描述并发控制如何保证隔离性,我们简化事务模型。事务是由一个或多个操作组成,所有的操作最终都可以拆分为一系列读和写。一批同时发生的事务,所有读、写的一种执行顺序,被定义为一个schedule,例如:

T1、T2同时执行,一个可能的schedule:
T1.read(A),T2.read(B),T1.write(A),T1.read(B),T2.write(A)

如果并发事务执行的schedule效果与串行执行的schedule(serial schedule)等价,就可以满足serializability。一个schedule不断调换读写操作的顺序,总会变成一个serializable schedule,但是有的调换可能导致事务执行的结果不一样。一个schedule中,相邻的两个操作调换位置导致事务结果变化,那么这两个操作就是冲突的。冲突需要同时满足以下条件:

  • 这两个操作来自不同事务
  • 至少有一个是写操作
  • 操作对象相同

因此常见的冲突包括:

  • 读写冲突。事务先A读取某行数据、事务B后修改该行数据,和事务B先修改某行事务、事务A后读该行记录两种schedule。事务A读到的结果不同。这种冲突可能会导致不可重复读异象和脏读异象。
  • 写读冲突。与读写冲突产生的原因相同。这种冲突可能会导致脏读异象。
  • 写写冲突。两个操作先后写一个对象,后一个操作的结果决定了写入的最终结果。这种冲突可能会导致更新丢失异象。

数据库只要保证,并发事务的schedule,保持冲突操作的执行顺序不变,只调换不冲突的操作,可以成为serial schedule,就可以认为它们等价。

这种等价判断方式叫做conflict equivalent:两个schedule的冲突操作顺序相同。例如下图的例子,T1 write(A)与T3 read(A)冲突,且T1先于T3发生。T1 read(B)和 T2 write(B)冲突,且T2先于T1,因此左图事务执行的schedule,与T2,T1,T3串行执行的serial schedule(右图) 等价。左图的执行顺序满足conflict serializablity。
纯干货 | 一篇讲透如何理解数据库并发控制
纯干货 | 一篇讲透如何理解数据库并发控制
再分析一个反例:T1 read(A)与T2 write(A)冲突且T1先于T2,T2 write(A)与T2 write(A)冲突且T2先于T1。下图这个个schedule无法与任何一个serial schedule等价,是一个不满足conflict serializablity的执行顺序,会造成更新丢失的异象。
纯干货 | 一篇讲透如何理解数据库并发控制
总体来说,serializability是比较严格的要求,为了提高数据库系统的并发性能,很多用户愿意去降低隔离性的要求以寻求更好的性能。数据库系统往往会实现多种隔离级别,供用户灵活选择,关于事务隔离级别,可以参看这篇文章。

并发控制的要求清楚了,如何实现呢?后文将依据冲突检测的乐观程度,一一介绍并发控制常见的实现方法。

02基于两阶段锁的并发控制

2.1 2PL

既然要保证操作按正确的顺序执行,最容易想到的方法就是加锁保护访问对象。数据库系统的锁管理器模块,专门负责给访问对象加锁和释放锁,保证只有持有锁的事务,才能操作相应的对象。锁可以分为两类:S-Lock和X-Lock,S-Lock是读请求使用的共享锁,X-Lock是写请求使用的排他锁。它们的兼容性如下:操作同一个对象,只有两个读请求相互兼容,可以同时执行,读写和写写操作都会因为锁冲突而串行执行。
纯干货 | 一篇讲透如何理解数据库并发控制
2PL(Two-phase locking)是数据库最常见的基于锁的并发控制协议,顾名思义,它包含两个阶段:

  • 阶段一:Growing,事务向锁管理器请求它需要的所有锁(存在加锁失败的可能)。
  • 阶段二:Shrinking,事务释放Growing阶段获取的锁,不允许再请求新锁。

为什么加锁和放锁要泾渭分明地分为两个阶段呢?

2PL并发控制目的是为了达到serializable,如果并发控制不事先将所有需要的锁申请好,而是释放锁后,还允许再次申请锁,可能出现事务内两次操作同一对象之间,其它事务修改这一对象(如下图所示),进而无法达到conflict serializable,出现不一致的现象(下面的例子是lost update)。
纯干货 | 一篇讲透如何理解数据库并发控制
2PL可以保证conflict serializability,因为事务必须拿到所有需要的锁才能执行。例如正在执行的事务A与事务B冲突,事务B要么已经执行完,要么还在等待。因此那些冲突操作的执行顺序,与BA或AB串行执行时冲突操作执行顺序一致。

所以,数据库只要采用2PL就能保证一致性和隔离性了吗?来看一下这个例子:
纯干货 | 一篇讲透如何理解数据库并发控制
以上执行顺序是符合2PL的,但T2读到了未提交的数据。如果此时T1回滚,则会引发级联回滚(T1的更改,不能被任何事务看到)。因此,数据库往往使用的是加强版的S(trong)S(trict)2PL,它相较于2PL有一点不同:shrinking阶段,只能在事务结束后再释放锁,完全杜绝了事务未提交的数据被读到。

2.2 死锁处理

并发事务加锁放锁必然绕不开一个问题--死锁:事务1持有A锁等B锁,事务2持有B锁等A锁。目前解决死锁问题有两种方案:

  • Deadlock Detection:

数据库系统根据waits-for图记录事务的等待关系,其中点代表事务,有向边代表事务在等待另一个事务放锁。当waits-for图出现环时,代表死锁出现了。系统后台会定时检测waits-for图,如果发现环,则需要选择一个合适的事务abort。
纯干货 | 一篇讲透如何理解数据库并发控制

  • Deadlock Prevention:

当事务去请求一个已经被持有的锁时,数据库系统为防止死锁,杀死其中一个事务(一般持续越久的事务,保留的优先级越高)。这种防患于未然的方法不需要waits-for图,但提高了事务被杀死的比率。

2.3 意向锁

如果只有行锁,那么事务要更新一亿条记录,需要获取一亿个行锁,将占用大量的内存资源。

我们知道锁是用来保护数据库内部访问对象的,这些对象根据大小可能是:属性(Attribute)、记录(Tuple)、页面(Page)、表(Table),相应的锁可分为行锁、页面锁、表锁(没人实现属性锁,对于OLTP数据库,最小的操作单元是行)。对于事务来讲,获得最少量的锁当然是最好的,比如更新一亿条记录,或许加一个表锁就足够了。

层次越高的锁(如表锁),可以有效减少对资源的占用,显著减少锁检查的次数,但会严重限制并发。层次越低的锁(如行锁),有利于并发执行,但在事务请求对象多的情况下,需要大量的锁检查。数据库系统为了解决高层次锁限制并发的问题,引入了意向(Intention)锁的概念:

  • Intention-Shared (IS):表明其内部一个或多个对象被S-Lock保护,例如某表加IS,表中至少一行被S-Lock保护。
  • Intention-Exclusive (IX):表明其内部一个或多个对象被X-Lock保护。例如某表加IX,表中至少一行被X-Lock保护。
  • Shared+Intention-Exclusive (SIX):表明内部至少一个对象被X-Lock保护,并且自身被S-Lock保护。例如某个操作要全表扫描,并更改表中几行,可以给表加SIX。读者可以思考一下,为啥没有XIX或XIS

意向锁和普通锁的兼容关系如下所示:
纯干货 | 一篇讲透如何理解数据库并发控制
意向锁的好处在于:当表加了IX,意味着表中有行正在修改。

(1)这时对表发起DDL操作,需要请求表的X锁,那么看到表持有IX就直接等待了,而不用逐个检查表内的行是否持有行锁,有效减少了检查开销。(2)这时有别的读写事务过来,由于表加的是IX而非X,并不会阻止对行的读写请求(先在表上加IX,再去记录上加S/X),事务如果没有涉及已经加了X锁的行,则可以正常执行,增大了系统的并发度。

3303基于Timing Order(T/O)的并发控制

为每个事务分配timestamp,并以此决定事务执行顺序。当事务1的timestamp小于事务2时,数据库系统要保证事务1先于事务2执行。timestamp分配的方式包括:(1)物理时钟;(2)逻辑时钟;(3)混合时钟。

3.1 Basic T/O

基于T/O的并发控制,读写不需加锁, 每行记录都标记了最后修改和读取它的事务的timestamp。当事务的timestamp小于记录的timestamp时(不能读到”未来的”数据),需要abort后重新执行。假设记录X上标记了读写两个timestamp:WTS(X)和RTS(X),事务的timestamp为TTS,可见性判断如下:
读:

  • TTS < WTS(X):该对象对该事务不可见,abort事务,取一个新timestamp重新开始。
  • TTS > WTS(X):该对象对事务可见,更新RTS(X) = max(TTS,RTS(X))。为了满足repeatable read,事务复制X的值。
  • 为了防止读到脏数据,可以在记录上做特殊标记,读请求需等待事务提交后再去读。

写:

  • TTS < WTS(X) || TTS < RTS(X):abort事务,重新开始。
  • TTS > WTS(X) && TTS > RTS(X):事务更新X,WTS(X) = TTS。

这里之所以要求TTS > RTS(X),是为了防止如下情况:读请求的时间戳为rts,已经读过X,时间戳设为RTS(X)=rts,如果新事务的TTS < RTS(X),并且更新成功,则rts读请求再来读一次就看到新的更改了,违反了repeatable read,因此这是为了避免读写冲突。记录上存储了最后的读写时间,可以保证conflict serializable

这种方式也能避免write skew,例如:初始状态,X和Y两条记录,X=-3,Y=5,X+Y >0,RTS(X)=RTS(Y)=WTS(X)=WTS(Y)=0。事务T1的时间戳为TTS1=1,事务T2的时间戳TTS2=2。
纯干货 | 一篇讲透如何理解数据库并发控制
它缺陷包括:

  • 长事务容易饿死,因为长事务的timestamp偏小,大概率会在执行一段时间后读到更新的数据,导致abort。
  • 读操作也会产生写(写RTS)。

04基于Validation(OCC)的并发控制

执行过程中,每个事务维护自己的写操作(Basic T/O在事务执行过程中写就将数据写入DB)和相应的RTS/WTS,提交时判断自己的更改是否和数据库中已存在的数据冲突,如果不冲突才写入DB。OCC分为三个阶段:

  • Read & Write Phase:即读写阶段,事务维护读的结果和即将提交的更改,以及写入记录的RTS和WTS。
  • Validation Phase:检查事务是否与数据库中的数据冲突。
  • Write Phase:不冲突就写入,冲突就abort,restart。

Read & Write Phase结束,进入Validation Phase相当于事务准备完成,进入提交阶段了,进入Validation Phase的时间被选做记录行的时间戳,来定序。不用事务开始时间是因为:事务执行时间可能较长,导致后开始的事务可能先提交,这会加大事务冲突的概率,较小时间戳的事务后写入数据库,肯定会abort。

Validation过程

假设当前只有两个事务T1和T2,并修改了相同数据行,T1的时间戳 < T2的时间戳(即validation顺序:T1 < T2,对用户而言,T1先发生于T2),则有如下情况:

(1)T1在validate阶段,T2还在Read & Write Phase。此时只要T1和T2已经发生的读写没有冲突,就可以提交。

  • 如果WS(T1) ∩ (RS(T2) ∪ WS(T2)) = ∅,说明T2和T1写的记录无冲突,validation通过,可以写入。
  • 否则,T2与T1之间存在读写冲突或写写冲突,T1需要回滚。读写冲突:T2读到了T1写之前的版本,T1提交后,它可能读到T1写的版本,不可重复读。写写冲突:T2有可能在旧版本基础上更新,再次写入,造成T1的更新丢失。

(2)T1完成validate阶段,进入write阶段直到提交完成,这已经是不可逆的了。T2在T1进入write phase之前的读写,肯定和T1的操作不冲突(因为T1 validation通过了)。T2之后继续的读写操作,有可能冲突与T1要提交的操作,因此T2进入validate阶段:

  • 如果WS(T1) ∩ RS(T2)= ∅,说明T2没读到T1写的记录,validation通过,T2可以写入。(为什么不验证WS(T2)了呢?WS(T1)已经提交了,且它的时间戳小于WS(T2),WS(T2)里之前的一部分肯定没有冲突,之后的一部分,因为没有读过T1的写入的对象,写进去也没问题,不会覆盖WS(T1)的写)
  • 否则,T2与T1之间存在读写冲突和写写冲突,T2需要回滚。读写冲突:T2读到了T1写之前的版本,T1提交后,它可能读到T1写的版本,不可重复读。写写冲突:T2有可能在旧版本基础上更新,再次写入,造成T1的更新丢失。

05基于MVCC的并发控制

数据库维护了一条记录的多个物理版本。事务写入时,创建写入数据的新版本,读请求依据事务/语句开始时的快照信息,获取当时已经存在的最新版本数据。它带来的最直接的好处是:写不阻塞读,读也不阻塞写,读请求永远不会因此冲突失败(例如单版本T/O)或者等待(例如单版本2PL)。对数据库请求来说,读请求往往多于写请求。主流的数据库几乎都采用了这项优化技术。

MVCC是读和写请求的优化技术,没有完全解决数据库并发问题,它需要与前述的几种并发控制技术组合,才能提供完整的并发控制能力。常见的并发控制技术种类包括:MV-2PL,MV-T/O和MV-OCC,它们的特点如下表:
纯干货 | 一篇讲透如何理解数据库并发控制
MVCC还有两个关键点需要考虑:多版本数据的存储和多余多版本数据的回收。

多版本数据存储方式,大致可以分为两类:

(1)Append only的方式,新旧版本存储在同一个表空间,例如基于LSM-Tree的存储引擎。

(2)主表空间记录最新版本数据,前镜像记录在其它表空间或数据段,例如InnoDB的多版本信息记录在undo log。多版本数据回收又称为垃圾回收(GC),那些没有机会再被任何读请求获取的旧版本记录,应该被及时删除。

06总结

本文依据冲突处理的时机(乐观程度),依次介绍了基于锁(在事务开始前预防冲突)、基于T/O(在事务执行中判断冲突)和基于Validation(在事务提交时验证冲突)的事务并发控制机制。

不同的实现适用于不同的workload,并发冲突小的workload,当然适合更乐观的并发控制方式。而MVCC可以解决只读事务和读写事务之间相互阻塞的问题,提高了事务的并发读,被大多数主流数据库系统采用。

上一篇:阿里云峰会AIoT发布停车管理黑科技,边缘AI解锁道路停车精细化管理


下一篇:通信黑科技:窄带物联网NB- IoT激活物联网