数据库系统中的事务

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

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

两种事务控制模型

ACID

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

  1. 原子性
    原子性(atomicity)表现为事务中的所有操作要么全部完成,要么全部不完成(回滚),不会出现中间状态。以转账为例,假设A向B转账200元,那么原子性要求事务不存在A的钱扣了,但是B的钱没到账。
  2. 一致性
    一致性(consistency)表现为在事务开始前和结束后完整性约束(不变量)不被破坏。这里的“一致性常被称为“内部一致性”,以区别分布式系统中的外部一致性C。
  3. 隔离性
    隔离性(isolation)表现为数据库支持多个并发事务同时进行增删改。以转账为例,假设A和B同时向C转账200元,那么结束后C应当收到400元,而不存在只收到200块的情况。
  4. 持久性
    持久性(durability)表现为事务结束后对数据的修改是持久化的。例如系统发生宕机后,已提交的事务不应当消失。丢数据的一个常见例子是主从架构+异步复制,这种情况下durability难以保证。

BASE

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

在分布式系统的上下文下,BASE可以看做是对CAP理论做出的一种权衡,通常被以最终一致性的形式实现,参考下文。

故障恢复

WAL

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

Shadow paging

事务更新的两条规则

提交规则

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

先记后写规则

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

事务的隔离等级

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

  1. Read uncommitted(RU)
    事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read Uncommitted隔离级别下可能产生脏读。考虑下面的序列。

    • A写入X值为x1
    • B读出X值为x1
    • A回滚
    • B读出的X=x1是不合法的
  2. Read committed(RC)
    事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read committed隔离级别下可能产生不可重复读。RC隔离级别下,一个事务开始到提交之前,做出的修改对其他事务是不可见的。不可重复读会导致两次同样的查询得到不同的结果,可以考虑下面的序列。

    • A读取X值为x1
    • B写入X为x2
    • B提交
    • A读取X值为x2!=x1
    • A提交失败
  3. Repeatable Read(RR)
    在Repeatable Read隔离等级之下,事务A在访问数据时,事务开始后其他事务就不能对该数据进行修改了,因此杜绝了不可重复读。但是如果另一个事务在对其他的数据进行修改,例如在数据表中插入了一个新数据,那么会产生幻读现象,也就是一个事务的两次查询中数据笔数不一致。
    幻读的一个典型常场景就是事务t1去insert一个id,但没有commit,这时候事务t2去select一个id,发现没有,那么他就也insert这个id,发现主键冲突了。但select还是select不到,就好像出现幻觉一样。

  4. Serializable(S)
    等同于在每个读的数据行上加S锁,从而解决了幻读的问题。但这种方法具有很差的并发性,会导致大量超时和锁竞争。
    就我理解而言,RU/RC/RR这三个事务等级都是对于一个记录R而言的,但是S隔离等级涉及多个记录R。我们可以类比记录到变量?
    InnoDB可以通过MVCC(又有说间隙锁Next key lock)解决了幻读的问题,因此并不需要S。

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

死锁

下面两个事务的执行就容易进入死锁。

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;

数据库实现了死锁检测和死锁超时机制。以InnoDB为例,死锁发生时会选择将持有最少行级X锁的事务进行回滚。

并发事务控制

为了保证并发执行的事务在某一隔离级别上的正确执行的机制,我们需要并发事务控制。并发控制可以根据乐观程度分为基于Lock(如2PL)、Timestamp(如Basic T/O)和Validation(OCC系列算法)。

2PL

我们知道死锁有四个条件:互斥、占有且申请、不可抢占和循环等待。而为了解决死锁问题,一个方案就是一次性获得所有的锁,这样实际上破坏了占有且申请的条件。不过这样一次性锁协议牺牲了并发性。为此我们引入了2PL,2PL将加解锁过程分为两个阶段,在第一阶段只能加锁或者操作数据,不能解锁;在第二阶段只能解锁或者操作数据,不能加锁。相比于1PL并发度提高了,但是存在死锁问题了。

意向锁

意向锁的产生是为了提高执行效率,它要求如果我们对一个下层节点加锁,那么我们会对上层节点加意向锁。我们考虑一个数据表中有一些行正在被锁定,而我们现在试图加一个表级锁,这显然是要被阻塞的,但阻塞前我们需要遍历数据表的每一行才知道我们表中有些行被锁定了。为此意向锁要求在锁定行时对数据表也维护一个状态,表示当前数据表中有些行时被锁定的,因此你意向是获得表锁,那么请原地阻塞,别往下找了,现在是不可能的。
以意向共享锁IS为例,如果我们想对一行加S锁,那么我们先要对表加IS锁,表示我们对表中的某一行有加共享锁的意向。此外,如果把上下层节点组合起来看,能组合成四种锁的类型即SIS、SIX、XIS、XIX。以共享意向排他锁SIX为例,对数据表加S锁,说明要读取整个表,对数据表加IX锁,表示要更新数据表中的一些行。除了SIX,其他的锁并没有提高强度,可以退化为一个表级锁或者行级锁。以SIS为例,我们要读取整个表,对表加S锁,然后要读取其中一行,对表加IS锁,实际上可以简化为一个对表加S锁的操作。

T/O

OCC

MVCC

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