数据库云原生分布式数据库事务隔离级别

　　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 . Transaction T2 then creates data items that satisfy T1’s and commits. If T1 then repeats its read with the same , 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]...c1P3: 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]c1H2: r1[x=50]r2[x=50]w2[x=10]r2[y=50]w2[y=90]c2r1[y=90]c1H3: 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] c2r1[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 Skew Suppose 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 Skew Suppose 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。Part 3 快照隔离的发展
　　论文 A Critique of ANSI SQL Isolation Levels 中提出了快照隔离（Snapshot Isolation)的定义：事务的读操作从已提交（Committed）快照中读取数据，快照时间可以是事务的第一次读操作之前的任意时间，记为StartTimestamp；事务准备提交时，获取一个CommitTimestamp，它需要比现存的StartTimestamp和CommitTimestamp都大；事务提交时进行冲突检查，如果没有其他事务在[StartTS, CommitTS]区间内提交了与自己的WriteSet有交集的数据，则本事务可以提交；快照隔离允许事务用很旧的StartTS来执行，从而不被任何的写操作阻塞，或者读一个历史数据。
　　这里需要注意：上述时间和空间没有交集的检查，主要是为了阻止LostUpdate的异常；实现的时候通常利用锁和LastCommit Map，提交之前锁住相应的行，然后遍历自己的WriteSet，检查是否存在一行记录的LastCommit落在了自己的[StartTS, CommitTS]内；如果不存在冲突，就把自己的CommitTS更新到LastCommit中，并提交事务释放锁。
　　仔细考虑上述快照隔离的定义，考虑如下几个问题：CommitTS的获取：如何得到一个比现有的StartTS和CommitTS都大的时间戳，尤其是在分布式系统中；StartTS的获取：虽然上面提到的StartTS可以是一个很旧的时间，那么StartTS是否需要单调递增；提交时进行的冲突检查是为了解决Lost Update异常，那么对于这个异常来说，写写冲突检查是否是充分且必要的；分布式、去中心的快照隔离级别该怎样实现。
　　针对上述问题，下面进行展开。这里将上述提到的快照隔离（SI）记为Basic SI。
　　分布式快照隔离
　　本节主要讲解HBase、Percolator以及Omid在快照隔离方面工程实践进展。
　　HBase
　　HBase中快照隔离是完全基于多个HBase表来实现的分布式SI：Version Table：记录一行数据的最后的CommitTS；Committed Table：记录CommitLog，事务提交时将commit log写到这张表中可认为Committed；PreCommit Table：用作检查并发冲突，可理解为锁表；Write Label Table：用于生成全局唯一的Write Label；Committed Index Table：加速StartTS的生成；DS：实际存储数据。
　　协议大致实现如下：StartTS：从Committed Table中遍历找到单调连续递增的最大提交时间戳，即前面不存在空洞（这里的空洞指的是事务拿了CommitTS但没有按照CommitTS顺序提交）；Committed Index：为了避免获取StartTS过程遍历太多数据，每个事务在获得StartTS之后会写到Committed Index Table中，之后的事务从这个时间戳开始遍历即可，相当于缓存了一下；read：需要判断一个事务的数据是否提交了，去VersionTable和Committed Table检查；precommit: 先检查Committed Table是否存在冲突事务，然后在PreCommit Table记录一行，再检查PreCommitTable中是否存在冲突的事务；commit：拿到一个commitTS，在CommittedTable写一条记录，更新PreCommit Table。
　　HBase采用结构上解耦的方式实现分布式SI，所有的状态都存储到HBase中，每个场景的需求都用不同的表来实现，但这种解耦也带来了性能损失。这里将HBase实现的快照隔离记为HBaseSI。
　　Percolator
　　在2010年提出的Percolator在HBase的基础上更加工程化，将涉及到的多个Table合并成了一个，在原有数据的基础上增加了lock、write列：lock：用作是WW冲突检查，实际使用时lock会区分Primary Lock和Secondary Lock；write：可理解为commit log，事务提交仍然走2PC，Coordinator决定Commit时会在write列写一条commit log，写完之后事务即认为Committed。
　　同时，作为一个分布式的SI方案，仍然需要依赖2PC实现原子性提交；而prewrite和commit过程，则很好地将事务的加锁和2PC的prepare结合到一起，并利用Bigtable的单行事务，来避免了HBaseSI方案中的诸多冲突处理。这里将Percolator实现的快照隔离记为PercolatorSI。
　　Omid
　　Omid是Yahoo的作品，同样是基于HBaseSI，但和Percolator的Pessimistic方法相比，Omid是一种Optimistic的方式。其架构相对优雅简洁，工程化做得也不错，近几年接连在ICDE、FAST、PVLDB发表文章。
　　Percolator的基于Lock的方案虽然简化了事务冲突检查，但是将事务的驱动交给客户端，在客户端故障的情况下，遗留的Lock清理会影响到其他事务的执行，并且维护额外的lock和write列，显然也会增加不小的开销。而Omid这样的Optimistic方案完全由中心节点来决定Commit与否，在事务Recovery方面会更简单；并且，Omid其实更容易适配到不同的分布式存储系统，侵入较小。
　　ICDE 2014 的文章奠定Omid架构：TSO（TimestampOracle）：负责时间戳分配、事务提交；BookKeeper: 分布式日志组件，用来记录事务的Commit Log；DataStore：用HBase存储实际数据，也可适配到其他的分布式存储系统。
　　TSO维护如下几个状态：时间戳：单调递增的时间戳用于SI的StartTS和CommitTS；lastCommit: 所有数据的提交时间戳，用于WW冲突检测，这里会根据事务的提交时间进行一定裁剪，使得在内存中能够存下；committed：一个事务提交与否，事务ID用StartTS标识，这里记录StartTS -> CommitTS的映射即可；uncommitted：分配了CommitTS但还未提交的事务；T_max：lastCommit所保留的低水位，小于这个时间戳的事务来提交时一律Abort。
　　这里的lastCommit即关键所在，表明了事务提交时不再采用和Percolator一样的先加锁再检测冲突的Pessimistic方式，而是：将Commit请求发到TSO来进行Optimistic的冲突检测；根据lastCommit信息，检测一个事务的WriteSet是否与lastCommit存在时间和空间的重叠。如果没有冲突，则更新lastCommit，并写commit log到BookKeeper；TSO的lastCommit显然会占用很多内存，并且成为性能瓶颈。为此，仅保留最近的一段lastCommit信息，用Tmax维护低水位，小于这个Tmax时一律abort。
　　另外提出了一个客户端缓存Committed的优化方案，减少到TSO的查询；在事务的start请求中，TSO会将截止到start时间点的committed事务返回给客户端，从而客户端能够直接判断一个事务是否已经提交，整体架构如下图所示。
　　在FAST 2017中，Omid对之前的架构进行了调整，做了一些工程上的优化：commit log不再存储于BookKeeper，而是用一张额外的HBase表存储；客户端不再缓存committed信息，而是缓存到了数据表上；因此大部分时候，用户读数据时根据commit字段就能够判断这行数据是否已经提交了。
　　在PLVDB 2018中，Omid再次进行了大幅的工程优化，覆盖了更多的场景：Commit Log不再由TSO来写，而是offload到客户端，提高了扩展性，也降低了事务延迟；优化单行读写事务，在数据上增加一个maxVersion的内存记录，实现了单行的读写事务不再需要进行中心节点校验。
　　去中心化快照隔离
　　上述都是针对分布式SI的实现，它们都有一个共同特征：保留了中心节点，或用于事务协调，或用于时间戳分配。对于大规模或者跨区域的事务系统来说，这仍然存在风险。针对这点，就有了一系列对去中心化快照隔离的探索。
　　Clock-SI
　　Clock-SI首先指出，Snapshot Isolation的正确性包含三点：Consistent Snapshot：所谓Consistent，即快照包含且仅包含Commit先于SnapshotTS的所有事务；Commit Total Order：所有事务提交构成一个全序关系，每次提交都会生成一个快照，由CommitTS标识；Write-Write Conflict: 事务Ti和Tj有冲突，即它们WriteSet有交集，且[SnapshotTS, CommitTS]有交集。
　　基于这三个点，Clock-SI提出了如下的算法：StartTS：直接从本地时钟获取。Read：当目标节点的时钟小于StartTS时，进行等待，即下图中的Read Delay；当事务处于Prepared或者Committing状态时，也进行等待；等待结束之后，即可读小于StartTS的最新数据；这里的Read Delay是为了保证Consistent Snapshot。CommitTS：区分出单Partition事务和分布式事务，单Partition事务可以使用本地时钟作为CommitTS直接提交；而分布式事务则选择max{PrepareTS}作为CommitTS进行2PC提交；为了保证CommitTS的全序，会在时间戳上加上节点的id，和Lamport Clock的方法一致。
　　Commit：不论是单partition还是多partition事务，都由单机引擎进行WW冲突检测。
　　Clock-SI有几点创新：使用普通的物理时钟，不再依赖中心节点分配时间戳。对单机事务引擎的侵入较小，能够基于一个单机的Snapshot Isolation数据库实现分布式的SI。区分单机事务和分布式事务，几乎不会降低单机事务的性能，分布式使用2PC进行原子性提交。
　　在工程实现中，还需考虑这几个问题：StartTS选择：可以使用较旧的快照时间，从而不被并发事务阻塞；时钟漂移：虽然算法的正确性不受时钟漂移的影响，但时钟漂移会增加事务的延迟，增加abort rate；Session Consistency：事务提交后将时间戳返回给客户端记为latestTS，客户端下次请求带上这个latestTS，并进行等待。
　　论文实验结果很突出，不过正确性论证较为简略，还有待进一步证明。
　　ConfluxDB
　　如果说Clock-SI还有什么不足，那可能就是依赖了物理时钟，在时钟漂移的场景下会对事务的延迟和abort rate造成影响。能否不依赖物理时钟，同时又能够实现去中心化呢？
　　ConfluxDB提出的方案中，仅仅依赖逻辑时钟来捕获事务的先于关系，基于先于关系来检测冲突：当事务Ti准备提交时，2PC的Coordinator向所有参与者请求事务的concurrent(Ti)列表，这里的concurrenct(Ti)定义为begin(Tj) < commit(Ti)的事务；Coordinator在收到所有参与者的concurrent(Ti)之后，将其合并成一个大的gConcurrent(Ti)，并发回给所有参与者；参与者根据gConcurrent(Ti)，检查是否存在一个事务Tj，dependents(Ti,Tj) ∧ (Tj ∈ gConcurrent(Ti)) ∧ (Tj ∈ serials(Ti))，即存在一个事务Tj，在不同的partition中有不同的先后关系，违背了Consistent Snapshot的规则；参与者将冲突检测的结果发回给Coordinator，Coordinator据此决定是Commit还是Abort；除此之外Coordinator需要给这个事务生成一个CommitTS，这里选择和ClockSI类似的方式，commitTS=max{prepareTS}，这里的prepareTS和commitTS会按照Logical Clock的方式在节点之间传递。
　　ConfluxDB的这种方案不需要依赖物理时钟，不需要任何wait，甚至不需要单机的事务引擎支持读时间点快照的功能。但是这个方案的不足是，可能Abort rate并不是很好，以及在执行分布式事务时的延迟问题。
　　Generalized SI
　　Generalized SI将Snapshot Isolation应用到Replicated Database中，使得事务的Snapshot可以从复制组的从节点读取。这带来的意义有两点，使用一个旧的快照，不会被当前正在运行的事务阻塞，从而降低事务延迟；而从Secondary节点读取数据，则可以实现一定程度上的读写分离，扩展读性能。
　　Parallel SI
　　上面的方案中，可以将读请求offload到Secondary节点，一定程度上能够扩展读性能。那么继续将这个思路延伸一下，能不能把事务的提交也交给Secondary节点来执行呢？
　　这就是Parallel Snapshot Isolation的思路，在跨区域复制的场景下，业务通常会有地理位置局部性的要求，在上海的用户就近把请求发到上海的机房，在广州的用户把请求发到广州的机房；并且在实际的业务场景中，往往可以放松对一致性和隔离性的要求。Parallel放弃了Snapshot Isolation中对Commit Total Order的约束，从而实现了多点的事务提交。在通用数据库中可能很难使用这样的方案，但实际的业务场景中会很有价值。
　　Serializable SI
　　Snapshot Isolation所区别于Serializable的是Write Skew异常，为了解决这个异常，可以基于Snapshot Isolation进行优化，并且尽量保留Snapshot Isolation的优秀性质，进而提出了Serializable SI。
　　论文 Serializable isolation for snapshot databases 是 Alan D. Fekete 和 Michael J. Cahill 在2009年发表的，是早期研究SSI的理论成果。
　　论文从串行化图理论说起，在Multi-Version的串行图中，增加一种称之为RW依赖的边，即事务T1先写了一个版本，事务T2读了这个版本，则产生RW依赖。当这个图产生环时，则违背了Serializable。
　　在论文中作者证明，SI产生的环中，两条RW边必然相邻，也就意味着会有一个pivot点，既有出边也有入边。那么只要检测出这个pivot点，选择其中一个事务abort掉，自然就打破了环的结构。算法的核心就在于动态检测出这个结构，因此会在每个事务记录一些状态，为了减少内存使用，使用inConflict和outConflict两个bool值来记录；在事务执行读写操作的过程中，会将与其他事务的读写依赖记录于这两个状态中。虽然用bool值减少了内存使用，但显然也增加了false positive，会导致一部分没有异常的事务被abort。据文中的实验结果表明，性能好于S2PL（严格两阶段锁，可实现串行化），abort较低，给Snapshot Isolation带来的开销也比较小。但据后来的PostgreSQL的SSI实现，为了减少内存占用仍需要不少的工作量，有兴趣可参考 Serializable Snapshot Isolation in PostgreSQL。
　　Write SI
　　Yabandeh在 论文 A critique of snapshot isolation 中提出Write-Snapshot Isolation。作者首先批判Basic SI，因为Basic SI给人造成了一种误导：进行写写冲突检测是必须的。文章开篇即提出，SI中的LostUpdate异常，不一定需要阻止WW冲突；换成RW检测，允许WW冲突，既能够阻止LostUpdate异常，同时能够实现Serializable，一举两得。
　　为何WW检测不是必须的？简要论证一下，在MVCC中，写冲突的事务写的是不同的版本，为何一定会有冲突？实际上只有两个事务都是RW操作时才有异常，如果其中一个事务只有W操作，并不会出现Lost Update；换言之，未必要检测WW冲突，RW冲突才是根源所在。
　　基于RW冲突检测的思想，作者提出Write Snapshot Isolation，将之前的Snapshot Isolation命名为Read Snapshot Isolation。如下图中：
　　TXNn和TXNc＂有冲突，因为TXNc＂修改了TXNn的ReadSet;TXNn和TXNc没有冲突，虽然他们都修改了r＂这条记录，Basic SI会认为有冲突，但Write SI认为TXNc没有修改TXNn的ReadSet，则没有RW冲突。
　　如何检测RW冲突：事务读写过程中维护ReadSet，提交时检查自己的ReadSet是否被其他事务修改过。但实际也不会这么简单，因为通常维护ReadSet的开销比WriteSet要大，且这个冲突检查如何做，难道加读锁？所以在原文中，作者只解释了中心化的Write SI如何实现（BadgerDB使用了这个算法，实现了支持事务的KV引擎）。至于去中心化的实现，可从CockroachDB找到一点影子。
　　不过RW检测会带来很多好处：只读事务不需要检测冲突，它的StartTS和CommitTS一样；只写事务不需要检测冲突，它的ReadSet为空；更重要的是，这种算法实现的隔离级别是Serializable而不是Snapshot Isolation。
　　综合上述内容，为实现串行化，传统上只能采用基于锁的并发控制，由于性能问题，很难在实际工程中应用。Serializable SI为高性能的实现可串行化，提供了一种新的路径。
　　以上内容主要参考 Snapshot Isolation综述。
　　写在最后
　　在wiki上PostgreSQL对SSI解释有这么一句话：Documentation of Serializable Snapshot Isolation (SSI) in PostgreSQL compared to plain Snapshot Isolation (SI). These correspond to the SERIALIZABLE and REPEATABLE READ transaction isolation levels, respectively, in PostgreSQL beginning with version 9.1。因此，在讨论任何一款数据库产品实现的隔离级别时，必须了解该隔离级别背后实现的算法原理。
　　文章来源：KaiwuDB_https://juejin.cn/post/7052496886061596709