数据库系统中的事务

本文主要讲述数据库中事务的控制模型、事务隔离等级和事务并发控制。

本文从分布式一致性和分布式共识协议一文中分离。

我们首先回顾一下非分布式系统上一致性的相关知识。

两种事务控制模型

ACID

对于关系型数据库,存在ACID事务控制模型维护事务的正确可靠性。

  1. 原子性(atomicity)
    事务中的所有操作要么全部完成,要么全部不完成(回滚),不会出现中间状态,也就是所谓的all-or-nothing。以转账为例,假设A向B转账200元,那么原子性要求事务不存在A的钱扣了,但是B的钱没到账。
    需要注意的是,原子性往往不蕴含并发的概念,后者由隔离性实际来处理。
    原子性实现需要REDO/UNDO。例如故障恢复时,如果我们决定回滚事务,我们就得参照UNDO来回滚;如果我们决定提交事务,我们就得根据REDO来提交。
  2. 一致性(consistency)
    在事务开始前和结束后完整性约束(不变量invariants)不被破坏。这里的“一致性常被称为“内部一致性”,以区别分布式系统中的外部一致性C。
    这里的不变量,往往是由上层应用程序来实际定义的。
  3. 隔离性(isolation)
    数据库支持多个并发事务同时进行增删改。以转账为例,假设A和B同时向C转账200元,那么结束后C应当收到400元,而不存在只收到200块的情况。
    在传统的数据库中,隔离性可以被形式化为Serializability,也就是说每个事物可以看作自己是整个数据库上唯一运行的事务。而事务提交的顺序,犹如他们是逐一运行一样。
    隔离性通过并发事务控制手段,如锁等解决。在很多数据库中,所谓的Serializability往往是一个称作Snapshot Isolation的隔离等级。
    【Q】如何唯一区分事务呢?例如,对一个有序的tcp连接,begin和commit之间的是一个事务,但如果涉及到重连的情况呢?所以往往我们要涉及生成一个唯一的事务ID。
  4. 持久性(durability)
    事务结束后对数据的修改是持久化的。例如系统发生宕机后,已提交的事务不应当消失。丢数据的一个常见例子是主从架构+异步复制,这种情况下durability难以保证。我们还可以考虑以下情况:
    1. 写入磁盘后,机器宕机
    2. 停电,此时对固态硬盘而言,可能fsync无法保证正常工作
    3. 硬盘上的数据随时间推移变得不可靠,SSD还会对温度敏感

BASE

BASE理论,即Basically Available、Soft State和Eventually Consistent,是相对于ACID准则的另一种事务控制模型,常被用在一些非RDBMS的事务控制的NoSQL中

在分布式系统的上下文下,BASE可以看做是对CAP理论做出的一种权衡,通常被以最终一致性的形式实现。我们将会在分布式一致性和分布式共识协议中进行讨论。

分布式事务

单对象事务和多对象事务

故障恢复

WAL

在关系数据库中常使用预写式日志Write ahead log(WAL)算法,WAL要求在数据实际写入之前先写日志,这样能够保证在故障发生后能通过日志进行恢复。相比于将数据实际插入数据库,WAL由于是顺序读写,所以相对来说要快很多。
事务有只有两种完成方式,提交即全做事务中的操作,和回滚即全不做事务中的操作。在事务的中间过程中可能对数据块的值进行修改,但最终这些修改必须要通过提交和回滚来实现持久化。
AI(后像,After Image),指的是每次更新时数据块的新值。对于一个已提交的事务,当故障发生时应当REDO它的后像。注意一旦事务提交,就不能UNDO它的前像,会破坏完整性约束;但是事务提交前任意的删改都可以通过UNDO来撤销。事务提交和往数据库写值(执行事务)是两个不同概念。
BI(前像,Before Image),指的是每次更新时数据块的旧值。对于一个未提交的事务或提交进行到一半,当故障发生时应当UNDO它的前像。
UNDO和REDO操作具有幂等性,即对前像UNDO或对后像REDO任意多次,结果都是相同的。

那么REDO操作和UNDO操作是不是缺一不可的呢?其实不然,需要和下面两个刷盘的策略组合起来看:

  1. Force
    表示事务在commit之后是否要立即刷盘。
    容易发现,如果不立即刷盘,则有丢失后像的风险,那么就必须要有REDO。
  2. Steal
    表示事务在uncommit时,是否可以刷盘。
    如果允许未提交就刷盘,那么磁盘上就可能存在脏数据,那么就必须要有UNDO。

通过undo和redo的配合,能够提供性能更好的ACID特性。如果事务是Force的,那么就必须保证在提交的同时刷脏完成,这样会拖累性能。如果事务是No Steal的,那么对于大事务而言,我们就不能异步刷脏。我们在有关innodb介绍的这篇文章中会详细介绍。

Shadow paging

事务更新的两条规则

提交规则

后像必须在提交前写入非易失存储器(数据库或运行记录)中。当后像只写入日志而没写入数据库中也可以提交事务,因为出现故障之后可以REDO后像实现恢复。

先记后写规则

数据库中有先记后写原则,如果在事务提交前将后像写入数据库,则必须首先把前像记入日志。这样做的好处是在事务提交完成前如果出现故障,可以通过日志文件中的该前像进行UNDO。此时即使数据库没有被修改,也只是进行一次多余的UNDO操作。

事务的隔离等级

ANSI/ISO SQL-92定义了4个隔离级别,这个定义借助于三个禁止的操作子序列,被称作phenomena,也就是熟悉的脏读、不可重复读和幻读。

简写符号

在A Critique of ANSI SQL Isolation Levels列出了一些简写符号,我们在后面也考虑复用

  1. w1[x]
    表示事务1对x的写
  2. r2[y]
    表示事务2对y的读
  3. c1
    表示事务1提交
  4. a1
    表示事务1中止

常见并发问题

如下图所示P0…Pn列出了面临的一些并发问题。下图中的行为隔离等径,列为可能发生的phenomena。

【P1】脏读(Dirty Read)

读到未提交的数据。考虑下面的序列

  • A写入X值为x1
  • B读出X值为x1
  • A回滚
  • B读出的X=x1是不合法的

避免脏读意味着避免下面的情况:

  1. w1 [x] ... r2 [x] ... (a1 and c2 in either order)
  2. w1[x] ... r2[x] ... ((c1 or a1) and (c2 or a2) in any order)
    相比上一个,更为宽松,因为它并不规定事务1一定中止,事务2一定提交了,所以禁止了4种可能的事务结束方式。

【P0】脏写(Dirty Write)

如果两个事务同时写相同的对象,可以认为在无保护的情况下,后写入的会覆盖前写入的。但如果前写入的是尚未提交事务的一部分,那么后写入的会覆盖一个未提交事务的写,这就是所谓的脏写。解决脏写的方案就是延迟后面的写操作。

【P4】写丢失/丢失更新(Lost Update)

主要分为两种:

回滚丢失

SQL标准定义的所有隔离级别都不允许这种写丢失。

覆盖丢失/两次更新

当一个事务写入的值被并发事务中的后续提交写入覆盖时,就会发生这种情况。事实上,我们可以把写丢失认为一种特殊的写偏斜问题。
我们需要区分脏写和丢失更新(lost update)两个概念。丢失更新强调的是事务提交后的更新丢失,实际上还是一个不一致的状态。例如DDIA中图7-5所示,两个事务分别尝试将自增计数器从41增加到42并提交,自增计数器的最终值是42而不是43,违背了一致性,这就是一个更新丢失现象。

解决此类写丢失问题,通常有下面几种方案:

  1. 原子写

    1
    UPDATE counters SET value = value + 1 where key = 'foo'
  2. 显式锁定
    select for update会对select出来的每一行上加上排他锁(X锁)。

    1
    2
    3
    4
    begin transaction;
    select * from figures where name = 'robot' for update;
    update figures set position = 'c4' where id = 1234;
    commit;
  3. 由事务管理器进行检测,对造成写丢失的事务进行中止

  4. CAS

    1
    UPDATE counters SET value = new_value where key = 'foo' and value = old_value;

    这种方案需要考虑数据库是否支持,例如数据如允许where子句从旧快照中读取的话,那么这个语句就未必有效。

【P4C】Cursor Lost Update

【P2】不可重复读(Fuzzy Read)

不可重复读(Fuzzy Read)会导致事务A中两次同样的查询得到不同的结果,一次是事务B提交前的数据,一次是事物B提交后的数据。可以考虑下面的序列:

  • A读取X值为x1
  • B写入X为x2
  • B提交
  • A读取X值为x2!=x1
  • A提交失败

避免不可重复读意味着避免下面的情况(P2):

  1. r1[x] ... w2[x] ... c2 ... r1[x] ... c1
  2. r1[x] ... w2[x] ... ((c1 or a1) and (c2 or a2) in any order)

【A5A】读偏差

【Q】读偏差和不可重复读的区别是什么?

【A5B】写偏差(Write Skew)

此时,两个并行事务都基于自己读到的数据集去覆盖另一部分数据集,在串行化情况下两个事务无论何种先后顺序,最终将达到一致性状态,但SI隔离级别下无法实现。
考虑事务P和Q。P试图执行x=y,Q试图执行y=x。从事务隔离性的观点来说,事务P和Q都期望最终x等于y。但是SI可能存在下面这种情况:

  1. P读y
    因为使用了SI,此时读到的是y的原值,不妨令为2。
  2. Q读x
    同理,读到x的原值1。
  3. P将读取的值2写入x
    现在x等于2了。
  4. Q将其读取的值1写入y
    现在y等于1了。

也就是说,x和y的值交换了。这个不仅不符合我们的期望,也破坏了完整性约束,从而导致数据库不满足一致性。我们还可以看到一些写偏差的例子:

  1. on call系统
    约束:至少有一个医生on call。
    假设A和B在同时开启申请不on call事务,可能发生:
    1. 事务P检查今晚有多少个医生可以on call,发现至少有两个医生A和B
    2. 事务P通过了A的请假
    3. 在快照隔离下,事务Q通过读取快照同样发现至少有两个医生
    4. 事务Q也通过了B的请假
    5. 违背了完整性约束:至少有一个医生on call
  2. 电影卖票
    如果使用SI,则可能一张电影票被卖两次。

写偏差可以看作写丢失(Lose Update)的一般化。如果两个事务读取相同的对象,然后各自更新一些对象(可能是不同的),那么就可能发生写偏差。特别地,如果它们更新的对象是相同的,那么可能发生脏写或者写丢失。

现在我们考虑之前解决写丢失的一些方案是否还能适用于解决写偏差:

  1. 原子写
    这个肯定不适用了,因为原子写只能涉及一个对象。
  2. 显式锁定
    这是可行的,但需要显示锁定事务所有依赖的行。
    例如,我们需要锁定x和y。
  3. 事务管理器
  4. 配置约束
    可以通过触发器或者物化视图来实现。
    例如,我们约束至少有一个医生on call。
  5. 更新隔离级别为S。

【P3】幻读

例如如果另一个事务在对其他的数据进行修改,例如在数据表中插入了一个新数据,在RR下会产生幻读现象,也就是一个事务的两次查询中数据笔数不一致。考虑下面的情况:

  1. P去insert一个id,但尚未提交
  2. Q去select这个id,发现没有
  3. Q去insert这个id,发现主键冲突,但是还是select不到,仿佛出现幻觉

幻读会引发写偏斜,并且会更加棘手,因为我们没办法通过显式锁定来解决这个问题:我们要锁的东西都不存在,该怎么加锁?

避免幻读,意味着我们要避免下面的情况:

  1. r1[P] ... w2[y in P] ... c2 ... r1[P] ... c1
  2. r1[P] ... w2[y in P] ... ((c1 or a1) and (c2 or a2) any order)

解决幻读可以从下面几个角度入手:

  1. 物化冲突
    刚才我们提到了“我们要锁的东西都不存在,该怎么加锁?”这个问题。
  2. 谓词锁
  3. Next key lock
    InnoDB可以通过间隙锁Next key lock解决了幻读的问题,因此实际上实现了串行化级别的效果,而且保留了比较好的并发性能
    【Q】间隙锁可以理解为一种物化冲突的手段么?
  4. 实现S隔离等级
    其实通过实现谓词锁,或者Next key lock等也能实现S隔离等级。当然也有诸如2PL直接加锁的办法。

介绍

在了解并发事务控制前,首先需要了解事务的隔离等级。
事务具有ACID的要求,隔离性I要求数据库能够支持并发事务。隔离性I的要求主要对应了四种隔离级别,分别是Read uncommitted、Read committed(Sql Server、Oracle等的默认隔离级别)、Repeatable read(MySQL的默认隔离级别)、Serializable,分别可以解决脏读、不可重复读(Nonrepeatable Read/Fuzzy Read)、幻读(Phantom Read)几类问题。

Read uncommitted(RU)

RU保证了不会脏写。

事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read Uncommitted隔离级别下可能产生脏读。

Read committed(RC)

相比于RU,RC提供了两个保证:

  • 不会脏读
    从数据库读的时候,不会看到没提交的数据。
  • 不会脏写
    写入数据库的时候,只会覆盖已写入的数据。
    这个其实RU也提供了。

如何预防脏写?很容易想到通过行锁。当要修改某个对象的时候,需要获得其所在行的行锁,并持有到事务提交或者中止。
如何预防脏读?偷懒的办法是也用同一个行锁。这样同一个对象只会同时被一个事务访问。可是这个方案性能太不好啦!为了提高性能,可以尝试多版本的方案,例如对于写入的每个对象,数据库会记住旧版本的值,即上一次被提交的值。同时,数据库也会维护当前持有锁的事务设置的新值。

事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read committed隔离级别下可能产生不可重复读,或者称为读偏差(Read Skew)。同理还有写偏差(Write Skew),相比于Spark语境中的Skew,这里的Skew含义是异常的时机。
RC隔离级别下,一个事务开始到提交之前,做出的修改对其他事务是不可见的。

Repeatable Read(RR)

在Repeatable Read隔离等级之下,事务A在访问数据时会加S锁,事务开始后其他事务就不能对该数据进行修改了,因此杜绝了不可重复读。

Snapshot Isolation(SI)

A Critique of ANSI SQL Isolation Levels这篇文章指出了ANSI SQL-92给出的四种隔离级别存在的问题,并提出了Snapshot Isolation。

在这篇文章中,作者提出SERIALIZABLE被描述成不会发生脏读、不可重复读以及幻读的一种隔离级别。但这和“可串行”并不等价,因为它存在Write skew的问题。Write skew指的是两个并行事务都基于自己读到的数据去覆盖另一部分数据,这个问题违反了可串行化。

Snapshot Isolation也是来解决2PL系列算法带来的并发度低的问题的

  1. 每一个数据有多个版本(MVCC)
    这相比RC是一个变化,因为RC只会维护两个版本,即上一次被提交的值,以及这次的性质。
    这是因为MVCC下,数据库需要维护某个对象的几个不同的提交版本,因此此时数据库中的并发事务可能看到数据库在不同时间点的状态。这也就是所谓的MVCC机制。
    容易看出,MVCC能够退化地实现RC隔离性。我们将在MVCC章节中看到基于MVCC对RC和RR的实现:即对RC,每个查询用独立的快照;对RR,整个事务用一个快照。
  2. 每个事务相当于看到数据的一个快照
    记事务开始时间戳为ST,事务提交的时间戳是CT。事务在开始时获得ST,在准备提交时获得CT。此时,该事务CT应当大于所有现存的ST和CT。具体时间戳的获取可以借助于TSO。在提交时,需要进行冲突检测,也就是说如果发现有并发事务在写同一个记录,那么至少要abort一个事务,否则会导致Lose Update。当然,我们也可以前置这个判断过程到写而不是提交的时候【Q】这是不是对应了SSI。abort的方式主要有FWW、LWW、FCW、LCW。
    【Q】这是根据并发事务的ST还是CT来判断呢?根据论文,是根据CT

    什么是冲突事务呢?如果有其他事务在[ST,CT]之间也写了我的WriteSet,那么这就是冲突事务了。如Percolator论文中Figure3所示。事务2看不见事务1的写,这是因为事务2的ST在事务1的CT之前。对应地,事务3能够看到事务1和2的修改。此时,我们称事务1和事务2是并发事务,如果并发事务都写同一个记录规则,可以保证不造成写丢失的情况。

    【Q】如果一个事务在执行过程中,那么它的CT会被设置为多少呢?我想应该是inf,看Percolator的实现也是inf。
  3. WW冲突还是需要加锁的,但是RW冲突就不会产生任何锁定了。R和W不会相互阻塞。
  4. 第一个得到行锁的事务可以进行,后面的写事务要么abort,要么block。

Snapshot Isolation相对于SERIALIZABLE的隔离级别要低一些,诸如Oracle宣称提供的SERIALIZABLE实际上也是Snapshot Isolation。降低了的隔离级别,带来了更好的读性能。这是显然的,想想S的实现方式吧,无论是真的串行(没有任何并行),还是2PL加锁(读和写都要加锁),都会导致读和写的竞争。

Snapshot Isolation中不会存在Repeatable Read中的幻读问题了,这是显然的。我们始终读取某个历史版本的状态,那么每次读都是一样的。

Snapshot Isolation可能带来写偏斜(write skew)问题,从而不能满足SERIALIZABLE级别。可是为啥会有这个问题呢?
我们回想上文讲述的PQ分别运行x=yy=x的例子。在这个例子中,我们发现Snapshot Isolation并没有管读和读之间的问题。

为什么Repeatable Read不会有Write Skew问题呢?根据这篇文章,RR会在读取行的时候加读锁。

RR和SI的区别和联系

在1975年定义SQL的隔离级别的时候,尚未发明SI这个级别。

MVCC和SI的区别和联系

MVCC和锁都是SI的实现手段,当然,也可以有一些方案完全无锁地实现SI。
数据行可见性的区别

  1. MVCC
    事务T1的快照记录是在生成快照时的活跃事务集合。这个集合的时间区间是[min, max],其中所有比min小的事务都被提交了,所有比max大的事务都没有启动。如果落在这个区间内,我们还需要去真正比较是否在这个集合中。详见对MVCC的介绍。
  2. Percolator
    保证能够读到R.start_ts > W.commit_ts。也就是说,当事务W提交完,才能被事务R读到。
    【Q】这个是不是和SI不太一样?SI貌似是CT2和[ST1,CT1]比较的。

Serial Snapshot Isolation(SSI)

该理论用来解决Write Skew问题。基本思想是冲突检测发生在事务运行阶段,而不是事务的提交阶段

Write Snapshot isolation需要保证一个事务读的数据的最近一个版本的提交时间要早于事务的开始时间。即下面的两个事务不能同时提交成功:

  1. 读写在空间上的重叠
    事务A的写和事务B读属于同一行
  2. 读写在时间上的重叠
    例如下面的顺序
    1
    start(A) < commit(j) < commit(i)

但是Serial Snapshot Isolation还是没能解决全序问题。解决这个问题,可以依靠Lamport的逻辑时钟。

Serializable(S)

等同于在每个读的数据行上加S锁,从而解决了幻读的问题。但这种方法具有很差的并发性,会导致大量超时和锁竞争。
【Q】就我理解而言,RU/RC/RR这三个事务等级都是对于一个记录R而言的,但是S隔离等级涉及多个记录R。我们可以类比记录到变量?

S的实现通常有下面几种方案:

  1. literally去串行执行
    也就是在单线程上一次只执行一个事务,理由是:
    1. RAM便宜了,现在可以完整存储活跃事务集
    2. OLTP事物通常较短,并且只涉及少量读写
      例如VoltDB/Redis等数据库中实现了这种方案。
  2. 2PL
    这是一个非常common的选择。我们会在专门的章节进行讨论。
  3. 一些乐观并发技术,例如上面提到的SSI

MySQL可以通过SET TRANSACTION ISOLATION LEVEL设置隔离级别。

Demo

考虑下面的代码Case1

1
2
3
4
5
6
7
Ta                                  Tb
begin
select x from table, x=10
begin
update table set x = 20
commit
select x from table, x=?

对于:

  1. RU、RC
    读到的是20
  2. RR、S
    读到的是10

再考虑下面的代码Case2

1
2
3
4
5
6
7
Ta                                  Tb
begin
select x from table, x=10
begin
update table set x = 20
select x from table, x=?
commit

对于:

  1. RU
    读到的是20
  2. RC、RR、S
    读到的是10

并发事务控制

为了保证并发执行的事务在某一隔离级别上的正确执行的机制,我们需要并发事务控制。并发事务控制实际上是解决并发事务之间隔离性的问题。
并发控制的主要思想可以根据乐观程度进行分类:

  1. Lock
    这个方法是最悲观的,也就是在访问资源之前,需要加锁。如果获取不到锁,就阻塞事务。
    如2PL
  2. Timestamp
    在每个事务开始时,获得时间戳,并期望事务按照时间戳的顺序执行。如果发现冲突,可以选择阻塞或者回滚。
    如Basic T/O
  3. Validation
    事务提交时,再进行验证。如果发生冲突,只能回滚。
    如OCC系列算法

容易发现,越乐观的策略下,对冲突的检查就越迟。从最悲观的访问资源之前加锁,到最乐观的Commit前验证,并发的能力是加强的,但是失败回滚的可能性也就越来越大。

需要注意的是,以上的策略都有单版本和多版本的实现。这个应该是能比较容易理解的,对于MVCC,因为一次对数据库的修改都会生成一个新的版本,所以实际上在处理隔离性上会更加的灵活。因为我们成功把问题转化到了如何选取版本和管理版本上。

可串行性和冲突可串行性(Conflict Serializability)

可串行性要求事务并发执行的效果和事务单独执行的效果是一样的。

关于这一点,我们可以类比到CPU并行编程里面的内存模型。如下图所示,左边的是串行调度,因为事务和事务之间都是串行的了。右边的是不可串行调度,因为右边的结果和左图(先T1再T2)不一样,并且和先T2再T1也不一样。中间的图并不是串行调度,因为T1和T2是彼此交织的,但是它的结果和左边的图是一样的,所以是可串行调度

和并发编程里面一样,除了读读操作,诸如读写、写读、写写之类的操作都是冲突操作

一个调度S在保证冲突操作的次序不变的前提下,通过交换非冲突操作的次序得到另一个调度S’,同时如果S’是可串行的,那么我们就说S是一个冲突可串行化的调度。一个调度是冲突可串行化的,那么它一定是可串行化的调度。

如下面这一组图所示。图1就是一个冲突可串行化的调度,因为它可以通过交换顺序得到图3。但是图4就不是一个可串行化。

2PL

2PL用户实现InnoDB和SQL Server中的S级别,以及DB2中的RR级别。这个方案的思路是通过为每个对象加锁来解决冲突。这些锁可以是共享的,也可以是排他的,具体来说:

  1. 如果需要读取,那么可以使用共享锁
  2. 如果需要写入,必须使用排它锁
  3. 如果先读后写,需要将共享锁升级为排它锁,升级过程如同重新获得排它锁
  4. 获得锁之后,必须持有锁到事务提交或者中止
    这应该是S2PL和SS2PL的规定。

我们知道死锁有四个条件:互斥、占有且申请、不可抢占和循环等待。而为了解决死锁问题,一个方案就是一次性获得所有的锁,这样实际上破坏了占有且申请的条件。如何避免死锁?我在文章中进行了较为详尽的讨论。避免死锁的一个可行的办法就是一次性请求所有锁(1PL),但这个对数据库来说很困难,因为我们很难知道我们具体要那些资源,并且这样一次性锁协议牺牲了并发性。
为此我们引入了2PL,2PL将加解锁过程分为两个阶段,在第一阶段只能加锁或者操作数据,不能解锁;在第二阶段只能解锁或者操作数据,不能加锁。
2PL不能避免死锁,如下所示。两个事务按照2PL加锁,假定第一个事务1请求到了4,第二个事务请求到了3,那么1和2就会陷入死锁。那么我们就必须干掉其中一个事务。

1
2
3
4
5
6
7
8
9
START TRANSACTION;
UPDATE StockPrice SET close = 45 WHERE stock_id = 4;
UPDATE StockPrice SET close = 19 WHERE stock_id = 3;
COMMIT;

START TRANSACTION;
UPDATE StockPrice SET close = 22 WHERE stock_id = 3;
UPDATE StockPrice SET close = 44 WHERE stock_id = 4;
COMMIT;

【Q】我们知道指定加锁顺序,可以避免死锁。例如我们在遍历链表的时候,始终沿着同一个方向遍历等。但是2PL这里的顺序并不是锁的顺序,例如我们先获取第一个锁,然后才能获取第二个锁,而是强调所有的加锁工作必须在解锁工作完成前完成,那么显然这里是不能避免死锁的。既然如此,为什么还需要引入2PL呢?
2PL的目的是为了保证可串行性,进而是为了保证隔离性。如果不满足2PL,那么可串行性就可能出问题。考虑下面的Case

1
2
3
4
5
6
7
8
9
10
Ta                                  Tb
begin
x-lock(A)
write(A)
release(A)
x-lock(A)
write(A)
release(A)
s-lock(A)
read(A)

容易看出,Ta先后申请并释放了两次A的锁,在这过程中,Tb修改了A的值,结果第二次对A的读取就是有问题的了。

我们需要注意的是,即使遵守2PL,还可能会出现问题。考虑下面的Case

1
2
3
4
5
6
7
8
9
10
11
12
Ta                                  Tb
begin
x-lock(A)
write(A)
read(B)
release(A)
x-lock(A)
read(A)
write(A)
write(B)
release(B)
commit

Tb出现了RU的情况。如果此时Ta回滚,那么Tb也要回滚,这称为级联回滚。所以一般数据库会有S2PL和SS2PL,分别要求写锁和读写锁在事务Commit后再释放。

数据库实现了死锁检测和死锁超时机制。以InnoDB为例,如果启动死锁检测(innodb_lock_wait_timeout),那么会在死锁发生时会选择将持有最少行级X锁的事务进行回滚。当然也可以选择等待(innodb_lock_wait_timeout)超时。

意向锁

数据库里面至少有表和行两个层级,我们考虑对某张表里面的一万行加锁,我们有锁表和分别锁一万行两个选择:

  1. 表锁
    会降低并发度。
  2. 行锁
    对内存的消耗比较大,同时大量时间会消耗在检查锁。

意向锁的产生就是为了解决这个问题。意向锁要求如果对一个下层节点加锁,那么我们会对上层节点加意向锁。

考虑一个数据表中有一些行正在被锁定,而现在试图加一个表级锁,这显然是要被阻塞的。但阻塞前我们需要遍历数据表的每一行才知道我们表中有些行被锁定了。为此意向锁要求在锁定行时对数据表也维护一个状态,表示当前数据表中有些行时被锁定的,因此你意向是获得表锁,那么请原地阻塞,别往下找了,现在是不可能的。这样在试图加表锁的时候,就不要逐一遍历检查是不是有行被锁住了

如果把上下层节点组合起来看,能组合成四种锁的类型即SIS、SIX、XIS、XIX。介绍如下:

  1. 意向共享锁IS
    如果我们想对一行加S锁,那么我们先要对表加IS锁,表示我们对表中的某一行有加共享锁的意向。
  2. 意向排它锁IX
    同理。如果我们发现一张表加了IX锁,说明里面有一或者若干行被X锁保护。
  3. 共享意向排他锁SIX
    表明内部至少一个对象被X-Lock保护,并且自身被S-Lock保护。例如某个操作要全表扫描,并更改表中几行,可以给表加SIX。

其他的一些锁的形式并不常见,原因是除了SIX之外其,他的锁并没有提高强度,实际上可以退化为一个表级锁或者行级锁。以SIS为例,我们要读取整个表,对表加S锁,然后要读取其中一行,对表加IS锁,实际上可以简化为一个对表加S锁的操作。

Wait-Die和Wound-Wait

这两个策略都是用来解决在锁冲突时,如何
共同点:

  1. 总是牺牲较新的事务,这里牺牲的意思就是回滚
    这是因为老事务往往会持有较多的锁,并且作了不少对数据库的修改,回滚老事务的成本比较大
  2. 这个策略是公平的
    当事务重新开始的时候,应当保留自己的时间戳。
    最终,被牺牲的事务会变得足够老。

不同点:

  1. Wait-Die策略在新事务发请求时将新事务杀死
    这里发请求指的是请求lock,这个锁被老事务持有
  2. Wound-Wait策略在老事务发请求时将新事务杀死
    这里发请求指的也是请求lock,这个锁被新事务持有

我们比较一下两者的性能:

  1. Wait-Die会导致较多的回滚,但是这些回滚的事务只会进行很少的修改
  2. Wound-Wait会回滚较少的事务,但这些回滚事务可能已经进行了比较多的修改了

Timing Order(T/O)

基于TO的并发事务控制,也就是给每个事务分配一个timestamp,用它来决定事务的执行顺序,其中timestamp较小的事务优先执行。这里的timestamp可以是物理时钟,也可以是逻辑时钟。

下面我们以Basic T/O为例介绍。和MVCC类似,每条记录里面也要增加一些标记,这一次增加的是最近一次读和写记录X的事务的时间戳,记为WTS(X)和RTX(X)。我们再令当前事务的时间戳是TTS。

考虑读:

  1. TTS < WTS(X)
    即有一个比TTS更新的事务写了X记录。那么这个X对TTS是不可见的,我们要abort掉TTS。
  2. TTS > WTS(X)
    记录X对事务TTS是可见的,更新RTS(X) = max(TTS, RTS(X))。

考虑写:

  1. TTS < WTS(X)或TTS < RTS(X)
    需要abort掉。
    为什么要求TTS大于WTS(X)呢?这个很简单,我们不能覆盖更新的写。
    为什么要求TTS大于RTS(X)呢?我们不妨思考什么时候出现TTS < RTS(X)这个情况?这说明在这个事务之后,有事务(令为Tb)已经读取了X的值了。如果我现在修改X的值,就会破坏RR的约束。因为如果Tb再次读X,会发现和之前的结果是不一样的。
  2. 否则
    可写,并且更新WTS(X) = TTS

OCC

MVCC

多版本并发控制(Multi-Version Concurrency Control, MVCC)是相对于单版本的概念, 有不同方式的实现,如基于锁的MV2PL,基于时间戳的MVTO,基于乐观并发控制(Optimistic Concurrency Control, OCC)的MVOCC。MVCC是为了提高数据库的读性能产生的一种思路,是一种解决读写冲突的无锁并发控制方式

根据Wikipedia,MVCC意图解决读写锁造成的多个、长时间的读操作饿死写操作问题。
每个事务读到的数据项都是一个snapshot并依赖于实现的隔离级别。写操作不覆盖已有数据项,而是创建一个新的版本,直至所在操作提交时才变为可见。快照隔离使得事务看到它启动时的数据状态。

具体来说:

  1. 当事务Ti读取对象P时,只有比Ti时间戳更早的最新对象版本是可见的。
  2. 当事务Ti写入对象P时,如果Tk要写同一对象,那么Ti必须早于Tk才能成功。【Q】这个说法就很奇怪,那对称地,Tk不是也要早于Ti么?

MVCC实现(InnoDB)

我们主要讨论RC和RR下的MVCC。至少对于InnoDB而言,RU和S是不兼容MVCC的。容易想到,RU始终读取最新的记录,并不需要考虑版本,而S默认要加锁,并不需要考虑并发。

记录结构

在使用MVCC时,InnoDB需要对每一条记录多存储一些字段:

  1. trx_id
    标记最近一次修改这个记录的事务的ID。
  2. db_roll_ptr
    回滚指针,指向Undo。

因此,一次UPDATE事务的流程可以如下所示

  1. 事务begin
  2. 对记录申请X锁
  3. 写REDO
  4. 写UNDO
  5. 实际修改Record
    除了修改值之外,还需要修改trx_id指向当前事务,修改db_roll_ptr指向UNDO。

RC下的MVCC

【首先介绍观察一致性快照的可见性规则】,具体来说,就是当事务在读取时,通过它的事务ID,决定哪些对象对它来说是可见的,哪些对象是不可见的。基本原则是:

  1. 【原则1】在事务开始时列出所有活跃事务(尚未commit或者abort)的列表。我们要忽略这些事务的提交。
  2. 【原则2】所有被abort的事务的写入要被忽略。
  3. 【原则3】所有在当前事务创建之后创建的事务的写入都需要被忽略。
  4. 【原则4】所有其他写入可见。

根据上面说的原则,下面列出具体的实现方案。在ReadView中维护一个列表m_ids,里面存放了所有当前活跃事务的ID,可以和每条记录里面的trx_id对应,其中trx_id能够代表事务开启的先后顺序。令其中最小值是low,最大值是up。
假设我们现在需要访问某一条记录,我们根据活跃事务集的范围[low,up]进行一次初筛,对于可能落在活跃事务集中的,在进行一次细筛。如下所示

  1. 被访问的trx_id小于low
    说明生成该版本的事务在ReadView创建前就提交了,所以可以被访问。
  2. 被访问的trx_id大于up
    对应了【原则3】
    说明该事务在ReadView创建后在生成,所以不能被当前事务访问。需要通过Undo Log找到上一个版本,再判断一次可见性。
    【Q】这个规则有点奇怪,例如对于上面的Case1而言,这里应该是返回新值的。但这个规则导致新值不能被使用。
  3. 如果trx_id落在[low,up]之间
    【细筛】
    需要判断trx_id是不是在m_ids中。
    如果在,说明在ReadView创建时,生成这个版本对应的事务还是活跃的。因此不能访问,需要回溯Undo Log。
    否则,说明在创建时,这个事务已经提交了。【Q】那为啥trx_id还会落在low和up之间呢?我想可能是因为这个事务非常短,例如同时有123事务开启,然后2就结束了,但是1和3一直延续到ReadView创建时。

在RC下,每一个SELECT都会生成一个ReadView。

RR下的MVCC

在RR下,在第一次读的时候创建一个ReadView,在创建ReadView之后,即使有其他事务提交,也不会对ReadView的内容造成影响。

例如,事务Ta的ID是200,在没有提交时,事务Tb开始查询。假如事务Tb的ID是300,此时生成ReadView的m_ids[200,300]。那么一直到这个事务结束前,m_ids都不变化了。假设现在Ta提交了,但由于它的ID在m_ids中,所以事务Tb还是只能回溯访问版本链中的记录,对应的值是10。

S下的MVCC

不需要MVCC,因为一定要加锁了。

Reference

  1. https://houbb.github.io/2018/09/01/sql-2pl
  2. https://draveness.me/database-concurrency-control/
    讲解了并发事务控制
  3. http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/8-recv+serial/deadlock-compare.html
    讲解了wait-die和wound-wait
  4. https://www.huaweicloud.com/articles/15e862d136110a0b026c911ace78caa7.html
    MVCC等
  5. https://zhuanlan.zhihu.com/p/91208953
    事务隔离级别,以及MVCC的实现和比较
  6. https://zhuanlan.zhihu.com/p/130242140
    介绍了TO和OCC
  7. https://csruiliu.github.io/blog/20180215-db-serialization/
    介绍可串行性
  8. http://blog.kongfy.com/2019/03/serializable/
    介绍另一种隔离级别的认知
    介绍了各个主要数据库的隔离性
  9. http://www.nosqlnotes.com/technotes/mvcc-snapshot-isolation/
    介绍Snapshot Isolation
  10. https://pingcap.com/blog-cn/take-you-through-the-isolation-level-of-tidb-1/
    tidb对事务隔离等级的论述
  11. DDIA
    DDIA对事务隔离的论述,在事务章节中
  12. https://developer.aliyun.com/article/77965
    对A Critique of ANSI SQL Isolation Levels这篇论文的翻译
  13. https://cloud.tencent.com/developer/news/330343
    介绍了各个isolation 问题