月度归档:2018年06月

数据库事务隔离标准分析

1 概述与背景

这是数据库事务原理和工程实践系列文章的第一篇,本文主要在Jim Gray的论文<A Critique of ANSI SQL Isolation Levels>基础上分析关系数据库的事务隔离级别标准和不同隔离级别情况下的行为。第2节主要讨论ANSI标准的下的隔离级别,第3节主要讨论基于悲观锁实现的事务隔离级别,第4节主要讨论基于多版本技术的事务隔离,最后总结排序本文讨论到的各个隔离级别。
ACID是关系数据库的一组重要特性,其中Isolation(隔离性)描述了数据库允许多个并发事务同时对其数据进行读写和修改的能力,隔离性可以防止多个事务并发时由于交错执行而导致数据的不一致。在最极端的情况下,数据库完全串行化执行每一个事务,所有事务之间遵守全序关系,在这种情况下,不存在并发事务间的隔离问题,但是在实际工程实践中,处于对数据库性能吞吐量的考虑,允许多个事务之间按照一定的规则,打破串行话的全序关系,ANSI SQL Isolation Levels即规定了这种“规则”,通过将隔离性划分为4个级别,来换取多层级的事务间并发能力(即数据库的吞吐能力)。
注,本文内容融入了作者个人的理解,并没有严格遵守<A Critique of ANSI SQL Isolation Levels>原文的内容;其中cursor stability隔离级别将在后续文章中讨论,快照隔离级别与ANSI标准异象的比较也有所不同。

2 ANSI事务隔离级别

ANSI SQL-92标准(http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt)将数据库并发事务间的隔离性行为划分为3种”异象(phenomena)”,从低到高的自然语言定义依次为:
  1. P1 脏读 (“Dirty read”): SQL-transaction T1 modifies a row. SQL- transaction T2 then reads that row before T1 performs a COMMIT. If T1 then performs a ROLLBACK, T2 will have read a row that was never committed and that may thus be considered to have never existed.
  2. P2 不可重复读 (“Non-repeatable read”): SQL-transaction T1 reads a row. SQL- transaction T2 then modifies or deletes that row and performs a COMMIT. If T1 then attempts to reread the row, it may receive the modified value or discover that the row has been deleted.
  3. P3 幻读 (“Phantom”): SQL-transaction T1 reads the set of rows N that satisfy some <search condition>. SQL-transaction T2 then executes SQL-statements that generate one or more rows that satisfy the <search condition> used by SQL-transaction T1. If SQL-transaction T1 then repeats the initial read with the same <search condition>, it obtains a different collection of rows.
通过依次禁止这三种异象,ANSI确定了4种标准隔离级别,如下表所示:
级别 P1(脏读) P2(不可重复读) P3(幻读)
Read Uncommitted 允许 允许 允许
Read Committed 禁止 允许 允许
Repeatable Read 禁止 禁止 允许
(Anomaly) Serializable 禁止 禁止 禁止
Note: The exclusion of these penomena or SQL-transactions executing at isolation level SERIALIZABLE is a consequence of the requirement that such transactions be serializable.

如标准文档所述,禁止了P1/P2/P3异象的事务即满足Serializable级别,但矛盾的是,标准文档中对Serializable又做了如下说明:

The execution of concurrent SQL-transactions at isolation level SERIALIZABLE is guaranteed to be serializable. A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions

它要求多个并发事务执行的效果与某种串行化执行的效果一致,但是仅仅禁止P1/P2/P3异象,并不一定能够保证“serial execution”的效果,因此论文中将ANSI Serializable称为Anomaly Serializable。

P1/P2/P3的形式化描述

根据标准文档的定义,可以将这三种异象使用形式化语言描述如下,称为A1/A2/A3(其中w1[x]表示事务1写入记录x,r1表示事务1读取记录x,c1表示事务1提交,a1表示事务1回滚,r1[P]表示事务1按照谓词P的条件读取若干条记录,w1[y in P]表示事务1写入记录y满足谓词P的条件):

  • A1 脏读:w1[x] … r2[x] … (a1 and c2 in any order)
  • A2 不可重复读:r1[x] … w2[x] … c2 … r1[x] … c1
  • A3 幻读:r1[P] … w2[y in P] … c2 … r1[P] … c1

上述A1/A2/A3形式化描述,根据标准定义的P1/P2/P3异象的自然语言描述转化而来,但是ANSI标准定义的异象只针对了单个记录或谓词描述,对于多条记录需满足业务一致性的场景并未能覆盖(比如两个账户间转账要求余额总和不变),举例如下:

  • H1:r1[x=50]w1[x=10] r2[x=10]r2[y=50] c2 r1[y=50]w1[y=90] c1
    • 事务1执行账户x向账户y转账40,事务2读取到了进行到了一半的事务1(Read Uncommitted),破坏了余额总和的一致性
    • 因为事务1并未回滚,H1的行为并不符合A1的形式化定义
  • H2:r1[x=50] r2[x=50]w2[x=10]r2[y=50]w2[y=90] c2 r1[y=90] c1
    • 事务2执行账户x向账户y转账40,事务1在事务2提交前后读取到了破坏余额总和一致性的数据(Unrepeatable Read)
    • 因为事务1并未重复读取记录x,H2的行为并不符合A2的形式化定义
  • H3:r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1
    • 事务2增加新雇员并更新雇员总数z,事务1在事务2提交前后读取到了破坏雇员列表与雇员总数的一致性的数据(Phantom)
    • 因为事务1并未重复读取谓词P指定的数据集合,H3的行为并不符合A3的形式化定义

因为要增强对上述H1/H2/H3异象的约束,论文将A1/A2/A3的形式化描述称为“狭义的描述(strict interpretations)”,然后增加了“广义的描述(broad interpretation)”,去除了strict interpretations中对事务提交、回滚和数据读取范围的约束,只保留事务之间读写的时序关系,即事务之间只要包含如下时序的操作,即可能产生包含H1/H2/H3在内的异象,如下:

  • P1 脏读:w1[x] … r2[x] … ((c1 or a1) and (c2 or a2) in any order)
  • P2 不可重复读:r1[x] … w2[x] … ((c1 or a1) and (c2 or a2) in any order)
  • P3 幻读:r1[P] … w2[y in P] … ((c1 or a1) and (c2 or a2) in any order)

在上述形式化描述下,禁止P1即可禁止H1,禁止P1/P2即可禁止H2,禁止P1/P2/P3即可禁止H3。至此,ANSI标准隔离级别定义的三种异象,可以被扩展为适用范围更广的的P1/P2/P3的形式化定义,这种隔离级别定义被论文称之为“phenomena-based”,即基于“异象”的隔离级别定义。

3 基于锁的事务隔离

在上一节的讨论中,P1/P2/P3这三种形式化定义指出了三个不同级别的异象,但是并没有与实际的工程实践相关联,在本小节中,我们将介绍基于锁(lock base)的事务隔离实现,并且将不同的加锁行为与上述三种异象关联起来讨论。
在讨论加锁行为之前,需要定义如下几种读写和锁的操作:
  • Predicate lock 谓词锁(gap锁):Locks on all data items satisfying the search condition
  • Well-formed Writes 合法write:Requests a Write(Exclusive) lock on each data item or predicate before writing
  • Well-formed Reads 合法read:Requests a Read(share) lock on each data item or predicate before reading
  • Long duration locks 长周期锁:Locks are held until after the transaction commits or aborts
  • Shord duration locks 短周期锁:Locks are released immediately after the action completes
通过组合上述读写锁操作,我们能够构建不同级别的事务隔离标准。因为“No Well-formed Writes”或“Short duration write locks”的保护等级可能造成dirty write,它的约束已经低到难以找到实际应用场景,我们将其忽略,因此所有写入操作都使用“Well-formed Writes, Long duration Write locks”,通过对读取操作应用不同的保护等级,得到4种隔离级别,使用locking前缀与ANSI隔离级别区分,如下表所示:
Read Lock Write Lock
Locking
Read Uncommited
none required
Well-formed Writes,
Long duration Write locks
Locking
Read Commited
Well-formed Reads,
Short duration read lock
Well-formed Writes,
Long duration Write locks
Locking
Repeatable Read
Well-formed Reads,
Long duration data-item Read locks,
Short duration Read Predicate locks
Well-formed Writes
Long duration Write locks
Locking
Serializable
Well-formed Reads,
Long duration Read locks
Well-formed Writes
Long duration Write locks
将locking标记的四种隔离级别与ANSI隔离级别对比:
  • Well-formed Reads, Short duration read lock 禁止了 P1发生,r2[x]将被读锁阻塞,直到事务1提交或回滚
  • Well-formed Reads, Long duration data-item Read locks, Short duration Read Predicate locks 禁止了P2发生,w2[x]将被写锁阻塞,直到事务1提交或回滚
    • 其中Short duration Read Predicate locks的作用论文中并没有说明,实际上它保护了r[P]的一致性,保证r[P]读取到的多行数据是一个“well-formed history”
  • Well-formed Reads, Long duration Read locks 禁止了P3发生,w2[y in P]将被谓词写锁阻塞,直到事务1提交或回滚
如上所述,Lock Base的隔离级别能够完全覆盖ANSI基于异象的隔离级别约束,论文中也称“phenomena-based”是“disguised versions of locking”。

4 基于快照的事务隔离

对于基于锁实现事务隔离的数据库,读写、写写事务之间也可能因为锁冲突而被阻塞,数据库的整体吞吐能力受到比较大的限制,特别是在目前多核的CPU条件下,难以充分发挥计算能力。因此现代关系型数据库和NewSQL,比如MySQL/Oracle/PostgreSQL/OceanBase/TiDB等,都使用多版本并发控制(mvcc)技术,来实现事务隔离,它的核心设计思想是,为数据的每次修改保存一个用时间戳标记的版本,数据读取不需要加锁,而是在读取事务开始的时候获取当前时间戳(snapshot),对于每条数据,将版本号小于snapshot的最大已提交版本的内容作为读取结果返回。
Snapshot Isolation保证只读事务与读写事务相互不阻塞,只读事务通过读取合法的历史快照,保证了读取到的数据的一致性,我们在快照隔离下与A1/A2/A3逐个对比分析:
  • P1描述的w1[x] … r2[x] …操作时序不可能出现,因为在快照隔离下,实际的操作时序为w1[x] … r2[last version of x] …,因此可知快照隔离禁止P1
  • P2描述的r1[x] … w2[x] … 它实际的操作时序为r1[x] … w2[new version of x] …,可以知道快照隔离也禁止了P2。至此,我们可以确定快照隔离的效果至少大于Read Committed
  • P3描述的r1[P] … w2[y in P] … 它实际的操作时序为r1[P] … w2[new version of y in P] …,可以知道快照隔离也禁止了P3,达到了第2小节中ANSI的Anomaly Serializable级别
但是,从上一小节基于锁的隔离级别定义来分析,快照隔离的安全级别可能并没有那么高,我们来看如下两种异象的形式化描述:
  • A5A Read Skew: r1[x]…w2[x]…w2[y]…c2…r1[y]…(c1 or a1)
  • A5B Writer Skew: r1[x]…r2[y]…w1[y]…w2[x]…(c1 and c2 occur)
    • 扩展的Write Skew(并非来自原文):r1[P]…r2[P]…w1[x]…w2[y]…(c1 and c2 occur)
快照隔离性高于Read Committed:第一,考虑到快照隔离读已提交的数据版本的特性,禁止了P1,因此保证至少不低于Read Committed。第二,A5A的Read Skew异象符合P2的定义,并且从一致性的角度分析,事务1对x和y的读取的两个值不在线性的历史中,可能会违背某种外部约束(比如保证x+y的和为一个常量),因此Read Committed隔离级别下允许A5A Read Skew异象。总和以上两点,我们可以得出结论,快照隔离性高于Read Committed。
快照隔离性与Repeatable Read不相容:考虑到快照隔离能够保证读取到的数据在一个一致的历史快照上,禁止了P1/P2/P3,因此保证不低于ANSI的Anomaly Serializable级别;但是,另一方面,经典的快照隔离对于多写冲突是基于First- committer-wins的处理方式,依赖冲突的事务间至少修改同一条记录(现代快照隔离有更优的SSI,我们将在后续的文章中介绍)无法避免上述A5B Write Skew的两种异象,而基于锁事项的Repeatable Read级别却可以禁止A5B。快照隔离与Repeatable Read双方禁止的异象,有可能在对方出现,因此他们的隔离性无法相比较。

5 总结

从前面几个小节的隔离性分析来看,我们可以得到如下几种隔离级别的关系:
Read Uncommitted < Read Committed < (Repeatable Read >< Snapshot) < Serializable
本文首先介绍了ANSI基于“异象”的隔离级别标准,并分析了其狭义和广义的描述;然后介绍了基于锁的隔离级别标准,与ANSI隔离级别进行了比较;最后分析快照隔离级别,在ANSI隔离级别标准基础上,提出了两种新的“异象”,得出快照隔离在几种标准隔离级别特性中的位置。

Loading