系列文章:

快照隔离在一些分布式系统中的实现 (1) - 什么是快照隔离
快照隔离在一些分布式系统中的实现 (2) - Omid1

最近在读一篇描述快照隔离的文章的时候,我发现自己已经差不多忘了之前读的论文里提到的各种分布式系统是怎么实现快照隔离的了。我不得不又重温了一下那些论文,但是这次要写几篇博客来总结一下。

老生常谈的 ACID

ACID 可以说是计算机专业学生的必学概念,同时也是互联网公司面试的常客。讨论快照隔离自然也没法绕开 ACID。ACID 是以下四个概念的缩写。

  1. Atomic:原子性。一个事务的所有写操作要么全部完成(i.e. Commit),要么全部失败(i.e. Abort)。注意这里的原子性和并发编程中的原子性的区别。并发编程中的原子性是指一个过程是“不可分割的”,其他线程无法看到这个过程进行到一半的状态(但是如果机器突然断电了,那么这个过程可能只完成了一部分)。
  2. Consistent:一致性。这是一个业务概念,表示数据库的状态永远都是合法的。这个一致性,是通过 ACID 中的其他属性保证的。
  3. Isolation:隔离性。若干个并发事务不应该互相影响,它们如果都提交成功,那么数据库的状态应该和他们以某种顺序依次执行后的状态相同,这是狭义上的隔离性,也被称作是 Serializable Isolation。在实际业务中,我们往往不需要这么强的隔离性保证。通过放松隔离性要求,我们往往可以获得更高的并发量,从而获得更高的吞吐量。
  4. Durable:持久性。每一个提交成功的事务包含的所有写操作都必须持久化的保存下来,即使数据库进程突然终止。

上面的四个概念中,A,C,D 并没有什么可以变化的地方。而剩下的 I 则有很多变种。在介绍 I 的变种之前,我们需要先讨论这些 I 的变种到底是为什么被发明出来。

并发事务可能带来的问题

如果没有了强隔离性的保证,并发事务可能会带来各种各样的问题。我们用教科书级的例子来描述各种可能出错的情况。假设我们有一张表 Accounts,它的 Schema 长这样:

1
2
3
4
5
6
CREATE TABLE Accounts (
UserId varchar(255),
Type varchar(255),
Balance int,
PRIMARY KEY (UserId, Type)
)

脏读 Dirty Read

Dirty Read 是指当两个并发事务 Txn1 和 Txn2 执行时,Txn1 读取到了 Txn2 还没有提交的改动,不管 Txn2 之后实际是提交了还是没有提交。考虑这个例子,当用户 1 执行转账任务 (Txn 2) 的同时查询自己的账户余额 (Txn 1),他会发现自己的余额总数不对。这是因为 Txn 1 读取了一个进行中的事务修改后的值。

Dirty Read

脏写 Dirty Write

Dirty Write 是指当两个并发事务 Txn1 和 Txn 2 执行时,一个事务的写操作覆盖了另一个事务的未提交的写操作,导致两个事务都提交之后,数据库的状态不满足一致性。比如下面这里例子,当两个修改文件数据和元数据的事务并发执行后,元数据中的最后修改人,和文件的最新内容不匹配。

Dirty Write

写丢失 Lost Update

Lost Update 和 Dirty Write 类似,也是两个并发的写操作造成的 conflict。但是 Lost Update 有些不同,它没有覆盖未提交的写操作。比如下面这个例子,用户 1 的公司同时给用户 1 的账户发了奖金和工资,然而这两个事务由于出现了写丢失,导致用户 1 最终只收到了其中的一笔钱。

Lost Update

不可重复读 Unrepeatable Read / Fuzzy Read / Read Skew

Unrepeatable Read 是指一个事务 Txn1 中读取的数据被另一个并发事务 Txn2 修改了。在 Txn2 提交之后,Txn1 之前读取的数据已经失效,如果再重新读一次就会读到不同的值。然而,Txn1 往往不会重新读一次,而是会读取其他的被 Txn2 修改的数据。这样,Txn1 会同时读到 Txn2 提交前后两个不同版本的部分数据,从而破坏一直性。比如下面这个例子,在用户 1 执行转账的同时,他查询余额总数会得到不正确的结果。注意和 Dirty Read 的区别,Txn1 每次读取的数据都是已提交的数据。

Unrepeatable Read

写偏斜 Write Skew

Write Skew 是指两个事务并发读取一个数据集之后,同时修改不相干的两部分数据,造成的数据库不一致的问题。这个描述有些抽象,我们看下图的这个(可能并不自然的)例子。用户 1 同时刷了信用卡和申请贷款触发了两个事务。这两个事务都读取了该用户的余额总额,发现总额足够 100 之后,各自在 credit 和 loan 两个账户下扣除了 100 元。可以看到,Write Skew 归根结底,也是两个并发的写操作造成的 conflict。

Write Skew

如何解决上述问题

上面的这些问题都是用于多个事务的并发执行导致的。为了解决这些问题,我们需要使用适当的隔离等级来约束事务的执行顺序/策略。例如,如果我们用最傻的办法,即全局锁,来实现所有事务都依次执行,我们就达成了 Serializable Isolation,显然上面的这些问题都不会发生。如果我们只需要解决其中的部分问题,我们可以使用更弱的隔离等级。下面会一一介绍几种常见的隔离等级,它们能解决的问题,以及它们的实现思路。注意,不同的数据库系统中,同一个名称的隔离等级表达的含义可能不同,大家使用的时候需要去读一下对应的文档。

Read Committed

Read Committed 解决了 Dirty Read 和 Dirty Write 这两个问题。其中 Dirty Read 这个问题实在太严重了,几乎所有的(如果不是全部的)隔离等级都保证不会读取到未提交的数据。Read Committed 做的事情就和它的名字一样,保证读操作只能读取到提交了的数据。

常见的实现 Read Committed 的方式是通过读写锁。当写一个数据的时候,为数据上写锁(排他锁)。当读取一个数据的时候,为数据上读锁(共享锁)。这样,任何一个事务在读取的一个未提交的事务修改的数据时,会阻塞直到该事务提交。当然,这样简单的实现方式性能并不太理想,尤其是在一个事务需要用户同意时,会长时间的占用一个写锁,从而阻塞其他事务。一个比较简单的优化是,在事务上写锁之前,记录下该数据的当前值。其他的事务可以直接读取记录下的值,避免被写操作阻塞。

Snapshot Isolation

Snapshot Isolation 解决了 Unrepeatable Read 和 Lost Update 的问题。它的思路是在一个事务执行过程中,数据库为它展示一个数据库在某个时间点的快照,这个快照包含了这个时间点之前所有提交的事务的执行结果。这样事务读取到的数据一定是一致的,Unrepeatable Read 的问题也就不存在了。除此之外,为了解决 Lost Update 的问题,每一个事务在提交之前,会检查自己修改的数据是否在提交之前被其他已经提交的事务修改了。如果已经被修改了,当前事务就必须被 Abort。

Snapshot Isolation 的常见实现是使用 MVCC,为同一份数据维护多个版本。当一个事务开始时为它分配一个时间戳 Tstart,这个事务的所有读取操作只会读这个时间戳之前的版本的数据,以此来达到快照的效果。同时,每一个事务会维护它修改的数据集合。在提交之前会分配一个时间戳 Tcommit,然后判断所有修改集合中的数据是否被提交时间在 (Tstart, Tcommit) 区间内的事务修改。如果没有才可以提交。注意这里的时间戳是单调递增的逻辑时间戳。

Serializable

Serializable 解决了所有的问题,因为它在观察者眼中,和所有事务依次执行是等价了。这是最强的隔离等级,所有的事务都互相“隔离”了。

Serializable 有多种实现方式。除了使用全局锁来事实上依次执行之外,实际使用的实现方式往往有:

  1. Two-Phase Lock,通过锁的形式保证。除了读写锁之外,还需要对索引范围,甚至整张表上锁。它的实现非常复杂,性能很差,并且非常容易出现死锁。
  2. Serializable Snapshot Isolation,和 Snapshot Isolation 类似。但是除了像 Snapshot Isolation 一样检查两个写操作的冲突,还会检查读操作和写操作之间的冲突(维护读取的数据集合,如果集合中有数据在提交前被其他事务修改,也需要 Abort 事务)。

快照隔离

上面已经介绍了快照隔离的大概实现思路,这里再总结一下:

  1. 数据存储层会维护每个数据的多个版本。
  2. 事务开始前会分配一个开始时间戳 Tstart
  3. 事务会记录自己修改的所有数据集合。
  4. 事务提交之前先会分配一个提交时间戳 Tcommit
  5. 分配完时间戳之后会检查是否有事务和自己的修改数据集合有交集,并且该事务的提交时间戳在 (Tstart, Tcommit) 之间。