云原生分布式数据库事务隔离级别（上）
Part 1 事务简介 事务的定义 事务（transaction）是数据库系统中保证一致性与执行可靠计算的基本单位。当确定了查询的执行策略并将其翻译成数据库操作原语后，将以事务为单位执行查询。 区分数据库一致性（database consistency）与事务一致性（transaction consistency）： 数据库一致性：如果一个数据库服从定义于其上的所有一致性（完整性）限制，则数据库处于一致性状态。修改、插入、删除（统称更新）都会造成状态的改变。理想是保证数据库不会进入不一致状态。虽然事务在执行过程中数据库有可能会暂时变得不一致，但是当事务执行完毕后数据库必须恢复到一致的状态。 事务一致性：涉及到并发事务的行为，理想是多个用户同时访问（读或写）的时候保持一致状态。考虑到数据库中数据复制，对用户访问的处理变得复杂。对于复制数据库，若一个数据项的所有拷贝都具有相同的值，称这个复制数据库处于相互一致状态（mutually consistency state）。这种情况称为单拷贝等价（one-copy equivalence），在事务都执行结束时所有复制的拷贝都被强制处于同一状态。 事务是一致性与可靠计算的基本单位。直观上一个事务会通过执行某个操作将数据库从一个版本变成一个新版本，由此造成数据库状态转移。通过事务可以保证如果数据库在执行事务之前是一致的，那么它在执行完事务后依然是一致的，无论过程中是否有其他事务并行或是发生系统故障。 如果事务成功地完成了它的任务，称这个事务已提交(commit)；如果事务没有完成任务却中途停止了，称它已取消(abort)。事务会由于多种原因被取消。此外，死锁等其他原因也会令DBMS将事务取消。当事务被取消的时候，所有正在执行的动作都会停止，所有已经执行过的动作都将反做(undo)，数据库会回退到执行该事务之前的状态。这一过程被称为回滚(rollback)。 事务的性质 事务ACID四个性质： 原子性(atomicity)：事物的所有操作要么全部被执行，要么就一个都不执行，又被称为“All or Nothing”性质。 注意这里把原子性的概念从单独的一个个操作扩展到整个事务了。如果一个事务的执行过程被某种故障所打断，那么事务的原子性就要求DBMS能够响应这个故障，并能够决定如何将事务从中恢复回来。当然，这里有两种恢复方式:要么完成余下的操作，要么反做所有已经完成的操作。 一般事务在执行时会遇到两种故障。第一种故障是由输人数据错误、死锁等原因造成的。在这种情况下，事务要么自己将自己取消，要么在死锁等情况出现的时候由DBMS将其取消。在这种故障下维护事务的原子性的操作称为事务恢复(transaction recovery)。第二种故障通常源于系统瘫痪，例如存储介质故障、处理器故障、通信线路损毁、供电中断等。在这种情况下保障事务的原子性的操作称为瘫痪恢复(crashrecovery)。上述两种故障的一个重要区别是，在某些系统瘫痪故障中，存储在易失性存储器中的信息可能会丟失或不可访问。这两类恢复操作属于处理可靠性问题的一部分。 一致性(consistency):事务是能够正确的将数据库从一个一致状态变换到另一个一致状态的程序。验证一个事务是否具有一致性是完整性实施所涉及到的工作。如何保证事务一致性是并发控制机制的目的。 隔离性( isolation) ：在事务提交前，一个执行中的事务不能向其他并发事务透露自己的执行结果。保证事务隔离性的一个原因在于，保护事务的一致性。 持久性(durability)：如果一个事务已经提交，那么它产生的结果是永久的，这一结果不能从数据库中抹去。持久性会引入数据库恢复（database recovery）问题。 这四个性质通常并不是互相独立而是互相依赖的。 事务的类型 这里仅简单介绍几种事务类型： 平面事务（flat transaction）：有一个起始点（Begin_transaction）和一个结束点（End_transaction）。 嵌套事务（nested transaction）：一个事务中包含其他具有单独的起始点和提交点的事务。 工作流（workflow model）：实际含义暂没有清晰与统一的定义，目前一个可行定义：为了完成某个商业过程而组织起来的一组任务。 以上主要参考 Principles of Distributed Database Systems (Third Edition)。 Part 2 事务的隔离级别 隔离级别的定义 ANSI（美国国家标准协会）给出的SQL-92 中隔离级别是根据现象（phenomena）来定义的，下面给出三个现象的解释： P1 (Dirty Read): Transaction T1 modifies a data item. Another transaction T2 then reads that data item before T1 performs a COMMIT or ROLLBACK. If T1 then performs a ROLLBACK, T2 has read a data item that was never committed and so never really existed. P2 (Non-repeatable or Fuzzy Read): Transaction T1 reads a data item. Another transaction T2 then modifies or deletes that data item and commits. If T1 then attempts to reread the data item, it receives a modified value or discovers that the data item has been deleted. P3 (Phantom): Transaction T1 reads a set of data items satisfying some<search condition>. Transaction T2 then creates data items that satisfy T1’s<search condition>and commits. If T1 then repeats its read with the same<search condition>, it gets a set of data items different from the first read. 在论文A Critique of ANSI SQL Isolation Levels中作者指出 ANSI 给出的现象是不明确的，即使在最宽松的解释中也不排除执行历史中可能出现的一些异常行为，会导致一些反直觉的结果。并且，基于锁的隔离级别与等效 ANSI phenomena 有不同的特性，而商业数据库系统通常使用锁实现隔离级别。此外，ANSI 的现象不能区分出商业系统中许多类流行的隔离级别的行为。 由于 ANSI 给出的现象在语义上存在模糊性，因此可以对现象进行广义的解释以及狭义的解释。 广义的解释记为P，狭义解释记为A。事务1满足谓词P的读取和写入一组记录分别由“r1[P]”和“w1[P]”表示。事务1的提交（COMMIT）和中止（ROLLBACK）分别被记为“c1”和“a1”。上述三个现象重新表述如下： P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order) A1: w1[x]...r2[x]...(a1 and c2 in any order) P2: r1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order) A2: r1[x]...w2[x]...c2...r1[x]...c1 P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order) A3: r1[P]...w2[y in P]...c2...r1[P]...c1 根据现象给出隔离级别的定义。 ANSI SQL 定义了四个级别的隔离，每个隔离级别的特征是事务中禁止发生的现象（广义或狭义的表述），具体如表1所示： 但是，ANSI SQL规范没有仅根据这些现象来定义可串行化（SERIALIZABLE）隔离级别。ANSI SQL 指出，可串行化隔离级别必须提供“共识的完全可串行化的执行”。与这个必要条件相比，表1导致了一个常见的误解，即不允许三个现象发生就意味着可串行化。不允许在表1中出现的三种现象应该被称为异常可串行化（ANOMALY SERIALIZABLE）（注：异常可串行化意为基于禁止异常（或phenomena）的可串行化，并非“真正的”可串行化）。 基于锁机制的隔离级别 大多数SQL产品都使用基于锁的隔离。因此，尽管存在某些问题，但从锁方面表征ANSI SQL隔离级别是有效的。 事务在基于锁调度下执行的读/写会请求数据项或数据项集合上读（共享）和写（独占）锁（read lock and write lock）。在两个不同的事务下的锁对应着同一个数据项的情况下，当至少一个是写锁的时候会冲突。 读取（或写入）的谓词锁（给定的<搜索条件>确定的一组数据项下）（read/write predicate lock）实际上是对满足<搜索条件>的所有数据项的锁。这可能是一个无限集，因为它包括数据库中存在的数据以及当前不在数据库中的所有幻影（phantom）数据项（如果它们被插入，或者当前数据项被更新以满足<搜索条件> ）。在SQL术语中，谓词锁覆盖满足谓词的所有数据项以及INSERT，UPDATE或DELETE后满足谓词的所有数据项。不同事务的两个谓词锁中如果一个是写锁，并且两个锁覆盖了相同的（可能是幻影）数据项，则两个谓词锁相冲突。数据项（item）锁（记录锁）是一个谓词锁，其中谓词指定特定记录。 事务具有好形式的写（读）（well-formed writes/reads）要求在写（读）该数据项或谓词定义的数据项集之前，每个数据项或谓词请求写锁（读锁）（译者注：也就是说在读（写）时对指定数据项集进行有且仅有一次的加读（写）锁）。事务是好形式（well-formed）的，要求事务有好形式的读与写。事务具有两阶段写（读）（two-phase writes/reads）要求在释放写（读）锁之后，在数据项上没有设置新的写（读）锁。事务是两阶段（two-phase）的，要求事务在释放一些锁之后不会请求任何新的锁（读或写锁）。 长锁（long duration）要求锁到事务提交或中止为止。否则，为短锁（short duration）。短锁通常在操作完成后立即释放。 如果一个事务持有一个锁，另一个事务请求一个冲突的锁，那么在前一个事务的冲突锁已经被释放之前，新的锁请求是不被授予的。 表2根据锁定范围（数据项项或谓词），模式（读或写）及其持续时间（短或长）定义了多个隔离类型。基于锁的隔离级别：“锁读未提交”、“锁读已提交”、“锁可重复读”、“锁可串行化”是满足ANSI SQL隔离级别要求的，但表2与表1完全不同，必须将基于锁定义的隔离级别与基于 ANSI SQL 现象的隔离级别进行区分。为了区分，表2中的级别标有“Locking”前缀，而不是表1的“ANSI”前缀。 ANSI SQL 现象的修正 下面重点分析锁隔离级别与ANSI SQL的要求。这里先给出P0定义： P0 (Dirty Write): Transaction T1 modifies a data item. Another transaction T2 then further modifies that data item before T1 performs a COMMIT or ROLLBACK. If T1 or T2 then performs a ROLLBACK, it is unclear what the correct data value should be. 形式化表达为： P0: w1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order) 脏写不好的一个原因是它可以违反数据库一致性，并且在没有P0保护的情况下，系统无法通过恢复映像（image）来撤消更新（事务回滚）。因此，ANSI SQL隔离应修改为要求所有隔离级别至少避免P0现象。 论文指出应该对 ANSI SQL 三个现象给出广义的定义。先回顾ANSI SQL三个现象狭义解释： A1: w1[x]...r2[x]...(a1 and c2 in either order) (Dirty Read) A2: r1[x]...w2[x]...c2...r1[x]...c1 (Fuzzy or Non-Repeatable Read) A3: r1[P]...w2[y in P]...c2....r1[P]...c1 (Phantom) 给出三个狭义解释不能囊括如下银行转账的场景： H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2 r1[y=50]w1[y=90]c1 H2: r1[x=50]r2[x=50]w2[x=10]r2[y=50]w2[y=90]c2r1[y=90]c1 H3: r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1 表1中展示，“读已提交”隔离的历史禁止现象A1，“可重复读”隔离的历史禁止现象A1和A2，“可串行化”隔离的历史禁止现象A1，A2和A3。考虑上面银行转账场景： 场景1（H1）：事务T1将40元从x转移到y，要求保持余额总数为100，但T2读到了总余额为60的不一致状态。历史H1不违反任何异常A1，A2或A3。但是广义解释的P1解决这个问题。 场景2（H2）：事务T2看到总余额为140，交易都没有读取脏（即未提交）的数据。因此P1满足。并且，没有任何数据项被读取两次，也没有谓词范围内的数据被更改。H2的问题是，当T1读取y时，x的值已过期。如果T2再次读取x，则会被更改。但由于T2不会读两次，A2不适用。但是广义解释的P2解决这个问题。 场景3（H3）：事务T1执行<搜索条件>以找到雇员的列表。然后T2执行新的员工的插入，然后更新公司中的员工数量z。此后，T1将员工的数量读出，并看到差异。这个历史显然是不可串行化的，但由于谓词范围没有被访问两次，所以它是被A3所允许的。但是广义解释的P3解决这个问题。 综上，狭义解释的A1，A2和A3有意想不到的缺点，因此广义解释的P1，P2和P3更加合理。同时，ANSI SQL隔离现象定义的不完整，还有一些异常仍然可能出现，必须定义新的现象来完成锁的定义。此外，必须重新进行定义P3。广义现象解释如下： P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write) P1: w1[x]...r2[x]...(c1 or a1) (Dirty Read) P2: r1[x]...w2[x]...(c1 or a1) (Fuzzy or Non-Repeatable Read) P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom) 注意，ANSI SQL 中P3只禁止对谓词插入（和更新），而上面的P3的定义禁止任何满足谓词的写被读取，这里的写可以是插入，更新或删除。 根据上面定义的现象，将 ANSI SQL 隔离级别重新定义，如表3所示： 对于单版本历史，容易得出P0，P1，P2，P3现象是“假”的锁版本现象。实际，禁止P0排除了在第一个事务写入数据项后第二个事务的写，相当于在数据项（和谓词）上持有长写锁。所以脏写是不可能的。类似地，禁止P1相当于对数据项进行了好形式的读取。禁止P2表示数据项加上长读锁。最后，禁止P3意味着持有长谓词读锁。因此，表3中基于上述现象定义的隔离级别与表2的锁隔离级别是相同的。换句话说，P0，P1，P2和P3是对于锁版本隔离级别的重新定义。 其他隔离类型 首先是游标稳定（cursor stability），游标稳定旨在防止丢失更新现象。 P4 (Lost Update): The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits. 将上述历史转化为： P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update) （注意P4只是基于P0脏写和P1脏读，从锁隔离的角度上来说只是持有短读锁和长写锁，没有达到锁可重复读P2（也就是说不持有长读锁）） H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1 如历史H4所示，问题是即使T2提交，T2的更新也会丢失。x的最终值为T1写入的130，P4至少在读已提交隔离级别，因为禁止P0（事务执行第一次写操作的数据项被另一个事务第二次写入）或P1（写后提交前被读取）的情况下允许出现H4。当然，禁止P2也排除了P4，因为P2是r1[x],w2[x]，（c1 or a1），包括了P4。因此，P4可用于作为区分读已提交和可重复读强度中间的隔离级别。即 READ COMMITTED « Cursor Stability « REPEATABLE READ。 游标稳定扩展了读已提交隔离级别下对于SQL游标的锁行为。其提出游标上的Fetching操作rc（read cursor）。rc要求在游标的当前数据项上保持长读锁，直到游标移动或关闭（可能通过提交关闭）。当然，游标上的Fetching事务可以更新行（read cursor），即使游标在随后的Fetch上移动，写锁也将保持在行上直到事务提交。rc1[x] 和以后的 wc1[x] 排除了介入的 w2 [x]。因此，针对游标上的情况，提出现象P4C： P4C：rc1[x] ... w2[x] ... w1[x] ... c1（Lost Update） 其次是快照隔离（Snapshot Isolation)。 在快照隔离下执行的事务始终从事务开始时起的数据（已提交）的快照中读取数据。事务开始时获取的时间戳称为其开始时间戳（Start-Timestamp）。这一个时间戳可能为事务第一次读之前的任何时间。事务运行在快照隔离中时，只要可以维护其开始时间戳对应的快照数据，在就不会阻塞读。事务的写入（更新，插入和删除）也将反映在此快照中，如果事务第二次访问（即读取或更新）数据，则能再次读到。这个事务开始时间戳之后的其他事务的更新对于本次事务是不可见的。 快照隔离是一种多版本并发控制（Multiversion Concurrency Control，MVCC）。当事务T1准备好提交时，它将获得一个提交时间戳（Commit-Timestamp），该值大于任何现有的时间戳。当其他事务T2提交了数据的提交时间戳在T1事务的间隔[Start-Timestamp，Commit-Timestamp]中，只有T1与T2数据不重叠，事务才成功提交。否则，T1将中止。这个功能叫做先提交者成功（First-Committer-Wins），防止丢失更新（P4）。当T1提交时，其更改对于开始时间戳大于T1的提交时间戳的所有事务都可见。 快照隔离是一种多版本（MV）方法，因此单版本（SV）历史不能正确地反映时间上的操作序列。在任何时候，每个数据项可能有多个版本，由活动的和已提交的事务写入。事务必须读取合适的版本。考虑上面提到的历史H1，其表明在单值执行中需要P1。在快照隔离下，相同的操作序列将导致多值历史： H1.SI： r1[x0=50] w1[x1=10] r2[x0=50] r2[y0=50] c2 r1[y0=50] w1[y1=90] c1 将MV历史映射到SV历史是在隔离层次中放置快照隔离的关键。例如，可以将H1.SI映射成的单值历史： H1.SI.SV：r1[x=50] r1[y=50] r2[x=50] r2[y=50] c2 w1[x=10] w1[y=90] c1 快照隔离是不可串行化的，因为事务的读在一个时刻，写在另一个时刻。例如，考虑单值历史： H5：r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2 H5是不可串行化的，并且具有与快照隔离下事务相同的事务间数据流（事务读取的版本没有选择）。这里假设为x和y写入一个新值的每个事务有保持x + y>0的约束，而T1和T2两者都是隔离的，所以约束不能保持在H5中。 约束违反（Constraint violation）是一种通用和重要的并发异常类型。个别数据库满足多个数据项的约束（例如，键的唯一性，引用完整性，两个表中的行的复制关系等）。 它们一起形成数据库不变量约束谓词C（DB）。如果数据库状态DB与约束一致，则不变量为TRUE，否则为FALSE。事务必须保留约束谓词以保持一致性：如果数据库在事务启动时保持一致，则事务提交时数据库将一致。如果事务读取到违反约束谓词的数据库状态，则事务将受到约束违反并发异常的影响。这种约束违反在[DAT]中称为不一致分析（inconsistent analysis）。 给出了几个相关的定义。 A5 (Data Item Constraint Violation). Suppose C() is a database constraint between two data items x and y in the database. 这里提出两个由于违反约束引起的现象。 A5A Read SkewSuppose transaction T1 reads x, and then a second transaction T2 updates x and y to new values and commits. If now T1 reads y, it may see an inconsistent state, and therefore produce an inconsistent state as output. In terms of histories, we have the anomaly: A5A: r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1) (Read Skew) A5B Write SkewSuppose T1 reads x and y, which are consistent with C(), and then a T2 reads x and y, writes x, and commits. Then T1 writes y. If there were a constraint between x and y, it might be violated. In terms of histories: A5B: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur) (Write Skew) 不可重复度P2是读倾斜的退化形式，其中令x=y。更典型地，事务读取两个不同但相关的项目（如引用完整性）。写倾斜（A5B）可能来自银行业务语义的约束，如只要总共持有的余额保持非负，账户余额才能变为负值。如历史H5中出现的异常。 在排除P2的历史中，A5A和A5B都不会出现，因为A5A和A5B都有T2写入一个先前未被提交的T1读取的数据项的情况。因此，现象A5A和A5B仅用于区分低于可重复读取的隔离级别。 对于快照隔离，比读已提交更强，即 READ COMMITTED « Snapshot Isolation。 证明：在快照隔离中，first-committer-wins排除了P0（脏写入），并且时间戳机制阻止了P1（脏读），因此快照隔离不比读已提交弱。此外，A5A可能在读已提交下，但不在快照隔离与时间戳机制下。因此 READ COMMITTED « Snapshot Isolation。 在单版本现象中，难以描述快照隔离历史如何违反现象P2。异常A2不能发生，因为快照隔离下的事务即使在另一个事务更新数据项之后也会只读取数据项的相同版本对应的值。然而偏写（A5B）显然会发生在快照隔离下（比如H5），并且在单值历史解释中已经提到，禁止了P2也会排除A5B。因此，快照隔离承认可重复读没有历史异常。 快照隔离下不会发生A3异常（幻读）。在一个事务更新数据项集时，另一个事务多次谓词读的将始终看到相同的旧数据项集。但是可重复读隔离级别可能会遇到A3异常。快照隔离禁止具有异常A3的历史，但允许A5B，而可重复读则相反（允许A3禁止A5B）。因此，REPEATABLE READ »« Snapshot Isolation。 但是，快照隔离（能排除A3）并不排除P3（谓词读事务提交前谓词范围内被另一事务写入）。考虑一个约束，表示由谓词确定的一组作业任务不能有大于8的小时数。T1读取此谓词，确定总和只有7小时，并添加1小时持续时间的新任务，而并发事务T2做同样的事情。由于两个事务正在插入不同的数据项（以及不同的索引条目（如果有的话）），因此First-Committer-Wins不排除此情况，并且可能发生在快照隔离中。但是在任何等价的串行历史中，在这种情况下会出现P3现象。 另外，快照隔离没有幻读（在 ANSI SQL 中狭义定义下的A3），因为每个事务都不会看到并发事务的更新。快照隔离历史排除了现象A1，A2和A3。因此，在表1中的异常可串行化（ANOMALY SERIALIZABLE）的解释语境下：ANOMALY SERIALIZABLE « SNAPSHOT ISOLATION。 快照隔离的“乐观”并发控制方法对于只读事务具有明显的并发优势，但其对更新事务的好处仍然存在争议。 表4展示了上述提到的所有的隔离级别以及对应的现象： 综上，作者认为原始 ANSI SQL隔离级别的定义存在严重问题。英文文字上的定义是模糊和不完整的，脏写P0没有被排除。同时建议 ANSI SQL 隔离级别替换为对应锁隔离级别。同时将各种商业数据库中实现的隔离级别进行比对，对应关系如图2所示： 以上内容主要参考论文A Critique of ANSI SQL Isolation Levels。 （to be continued.）
