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

　　Part1事务简介
　　事务的定义
　　事务（transaction）是数据库系统中保证一致性与执行可靠计算的基本单位。当确定了查询的执行策略并将其翻译成数据库操作原语后，将以事务为单位执行查询。
　　区分数据库一致性（databaseconsistency）与事务一致性（transactionconsistency）：
　　数据库一致性：如果一个数据库服从定义于其上的所有一致性（完整性）限制，则数据库处于一致性状态。修改、插入、删除（统称更新）都会造成状态的改变。理想是保证数据库不会进入不一致状态。虽然事务在执行过程中数据库有可能会暂时变得不一致，但是当事务执行完毕后数据库必须恢复到一致的状态。
　　事务一致性：涉及到并发事务的行为，理想是多个用户同时访问（读或写）的时候保持一致状态。考虑到数据库中数据复制，对用户访问的处理变得复杂。对于复制数据库，若一个数据项的所有拷贝都具有相同的值，称这个复制数据库处于相互一致状态（mutuallyconsistencystate）。这种情况称为单拷贝等价（onecopyequivalence），在事务都执行结束时所有复制的拷贝都被强制处于同一状态。
　　事务是一致性与可靠计算的基本单位。直观上一个事务会通过执行某个操作将数据库从一个版本变成一个新版本，由此造成数据库状态转移。通过事务可以保证如果数据库在执行事务之前是一致的，那么它在执行完事务后依然是一致的，无论过程中是否有其他事务并行或是发生系统故障。
　　如果事务成功地完成了它的任务，称这个事务已提交（commit）；如果事务没有完成任务却中途停止了，称它已取消（abort）。事务会由于多种原因被取消。此外，死锁等其他原因也会令DBMS将事务取消。当事务被取消的时候，所有正在执行的动作都会停止，所有已经执行过的动作都将反做（undo），数据库会回退到执行该事务之前的状态。这一过程被称为回滚（rollback）。
　　事务的性质
　　事务ACID四个性质：原子性（atomicity）：事物的所有操作要么全部被执行，要么就一个都不执行，又被称为AllorNothing性质。
　　注意这里把原子性的概念从单独的一个个操作扩展到整个事务了。如果一个事务的执行过程被某种故障所打断，那么事务的原子性就要求DBMS能够响应这个故障，并能够决定如何将事务从中恢复回来。当然，这里有两种恢复方式：要么完成余下的操作，要么反做所有已经完成的操作。
　　一般事务在执行时会遇到两种故障。第一种故障是由输人数据错误、死锁等原因造成的。在这种情况下，事务要么自己将自己取消，要么在死锁等情况出现的时候由DBMS将其取消。在这种故障下维护事务的原子性的操作称为事务恢复（transactionrecovery）。第二种故障通常源于系统瘫痪，例如存储介质故障、处理器故障、通信线路损毁、供电中断等。在这种情况下保障事务的原子性的操作称为瘫痪恢复（crashrecovery）。上述两种故障的一个重要区别是，在某些系统瘫痪故障中，存储在易失性存储器中的信息可能会丟失或不可访问。这两类恢复操作属于处理可靠性问题的一部分。一致性（consistency）：事务是能够正确的将数据库从一个一致状态变换到另一个一致状态的程序。验证一个事务是否具有一致性是完整性实施所涉及到的工作。如何保证事务一致性是并发控制机制的目的。隔离性（isolation）：在事务提交前，一个执行中的事务不能向其他并发事务透露自己的执行结果。保证事务隔离性的一个原因在于，保护事务的一致性。持久性（durability）：如果一个事务已经提交，那么它产生的结果是永久的，这一结果不能从数据库中抹去。持久性会引入数据库恢复（databaserecovery）问题。
　　这四个性质通常并不是互相独立而是互相依赖的。
　　事务的类型
　　这里仅简单介绍几种事务类型：平面事务（flattransaction）：有一个起始点（Begintransaction）和一个结束点（Endtransaction）。嵌套事务（nestedtransaction）：一个事务中包含其他具有单独的起始点和提交点的事务。工作流（workflowmodel）：实际含义暂没有清晰与统一的定义，目前一个可行定义：为了完成某个商业过程而组织起来的一组任务。
　　以上主要参考PrinciplesofDistributedDatabaseSystems（ThirdEdition）。Part2事务的隔离级别
　　隔离级别的定义
　　ANSI（美国国家标准协会）给出的SQL92中隔离级别是根据现象（phenomena）来定义的，下面给出三个现象的解释：P1（DirtyRead）：TransactionT1modifiesadataitem。AnothertransactionT2thenreadsthatdataitembeforeT1performsaCOMMITorROLLBACK。IfT1thenperformsaROLLBACK，T2hasreadadataitemthatwasnevercommittedandsoneverreallyexisted。P2（NonrepeatableorFuzzyRead）：TransactionT1readsadataitem。AnothertransactionT2thenmodifiesordeletesthatdataitemandcommits。IfT1thenattemptstorereadthedataitem，itreceivesamodifiedvalueordiscoversthatthedataitemhasbeendeleted。P3（Phantom）：TransactionT1readsasetofdataitemssatisfyingsome。TransactionT2thencreatesdataitemsthatsatisfyT1’sandcommits。IfT1thenrepeatsitsreadwiththesame，itgetsasetofdataitemsdifferentfromthefirstread。
　　在论文ACritiqueofANSISQLIsolationLevels中作者指出ANSI给出的现象是不明确的，即使在最宽松的解释中也不排除执行历史中可能出现的一些异常行为，会导致一些反直觉的结果。并且，基于锁的隔离级别与等效ANSIphenomena有不同的特性，而商业数据库系统通常使用锁实现隔离级别。此外，ANSI的现象不能区分出商业系统中许多类流行的隔离级别的行为。
　　由于ANSI给出的现象在语义上存在模糊性，因此可以对现象进行广义的解释以及狭义的解释。
　　广义的解释记为P，狭义解释记为A。事务1满足谓词P的读取和写入一组记录分别由r1〔P〕和w1〔P〕表示。事务1的提交（COMMIT）和中止（ROLLBACK）分别被记为c1和a1。上述三个现象重新表述如下：P1：w1〔x〕。。。r2〔x〕。。。（（c1ora1）and（c2ora2）inanyorder）A1：w1〔x〕。。。r2〔x〕。。。（a1andc2inanyorder）P2：r1〔x〕。。。w2〔x〕。。。（（c1ora1）and（c2ora2）inanyorder）A2：r1〔x〕。。。w2〔x〕。。。c2。。。r1〔x〕。。。c1P3：r1〔P〕。。。w2〔yinP〕。。。（（c1ora1）and（c2ora2）anyorder）A3：r1〔P〕。。。w2〔yinP〕。。。c2。。。r1〔P〕。。。c1
　　根据现象给出隔离级别的定义。
　　ANSISQL定义了四个级别的隔离，每个隔离级别的特征是事务中禁止发生的现象（广义或狭义的表述），具体如表1所示：
　　但是，ANSISQL规范没有仅根据这些现象来定义可串行化（SERIALIZABLE）隔离级别。ANSISQL指出，可串行化隔离级别必须提供共识的完全可串行化的执行。与这个必要条件相比，表1导致了一个常见的误解，即不允许三个现象发生就意味着可串行化。不允许在表1中出现的三种现象应该被称为异常可串行化（ANOMALYSERIALIZABLE）（注：异常可串行化意为基于禁止异常（或phenomena）的可串行化，并非真正的可串行化）。基于锁机制的隔离级别
　　大多数SQL产品都使用基于锁的隔离。因此，尽管存在某些问题，但从锁方面表征ANSISQL隔离级别是有效的。
　　事务在基于锁调度下执行的读写会请求数据项或数据项集合上读（共享）和写（独占）锁（readlockandwritelock）。在两个不同的事务下的锁对应着同一个数据项的情况下，当至少一个是写锁的时候会冲突。
　　读取（或写入）的谓词锁（给定的搜索条件确定的一组数据项下）（readwritepredicatelock）实际上是对满足搜索条件的所有数据项的锁。这可能是一个无限集，因为它包括数据库中存在的数据以及当前不在数据库中的所有幻影（phantom）数据项（如果它们被插入，或者当前数据项被更新以满足搜索条件）。在SQL术语中，谓词锁覆盖满足谓词的所有数据项以及INSERT，UPDATE或DELETE后满足谓词的所有数据项。不同事务的两个谓词锁中如果一个是写锁，并且两个锁覆盖了相同的（可能是幻影）数据项，则两个谓词锁相冲突。数据项（item）锁（记录锁）是一个谓词锁，其中谓词指定特定记录。
　　事务具有好形式的写（读）（wellformedwritesreads）要求在写（读）该数据项或谓词定义的数据项集之前，每个数据项或谓词请求写锁（读锁）（译者注：也就是说在读（写）时对指定数据项集进行有且仅有一次的加读（写）锁）。事务是好形式（wellformed）的，要求事务有好形式的读与写。事务具有两阶段写（读）（twophasewritesreads）要求在释放写（读）锁之后，在数据项上没有设置新的写（读）锁。事务是两阶段（twophase）的，要求事务在释放一些锁之后不会请求任何新的锁（读或写锁）。
　　长锁（longduration）要求锁到事务提交或中止为止。否则，为短锁（shortduration）。短锁通常在操作完成后立即释放。
　　如果一个事务持有一个锁，另一个事务请求一个冲突的锁，那么在前一个事务的冲突锁已经被释放之前，新的锁请求是不被授予的。
　　表2根据锁定范围（数据项项或谓词），模式（读或写）及其持续时间（短或长）定义了多个隔离类型。基于锁的隔离级别：锁读未提交、锁读已提交、锁可重复读、锁可串行化是满足ANSISQL隔离级别要求的，但表2与表1完全不同，必须将基于锁定义的隔离级别与基于ANSISQL现象的隔离级别进行区分。为了区分，表2中的级别标有Locking前缀，而不是表1的ANSI前缀。
　　ANSISQL现象的修正
　　下面重点分析锁隔离级别与ANSISQL的要求。这里先给出P0定义：
　　P0（DirtyWrite）：TransactionT1modifiesadataitem。AnothertransactionT2thenfurthermodifiesthatdataitembeforeT1performsaCOMMITorROLLBACK。IfT1orT2thenperformsaROLLBACK，itisunclearwhatthecorrectdatavalueshouldbe。
　　形式化表达为：P0：w1〔x〕。。。w2〔x〕。。。（（c1ora1）and（c2ora2）inanyorder）
　　脏写不好的一个原因是它可以违反数据库一致性，并且在没有P0保护的情况下，系统无法通过恢复映像（image）来撤消更新（事务回滚）。因此，ANSISQL隔离应修改为要求所有隔离级别至少避免P0现象。
　　论文指出应该对ANSISQL三个现象给出广义的定义。先回顾ANSISQL三个现象狭义解释：A1：w1〔x〕。。。r2〔x〕。。。（a1andc2ineitherorder）（DirtyRead）A2：r1〔x〕。。。w2〔x〕。。。c2。。。r1〔x〕。。。c1（FuzzyorNonRepeatableRead）A3：r1〔P〕。。。w2〔yinP〕。。。c2。。。。r1〔P〕。。。c1（Phantom）
　　给出三个狭义解释不能囊括如下银行转账的场景：H1：r1〔x50〕w1〔x10〕r2〔x10〕r2〔y50〕c2r1〔y50〕w1〔y90〕c1H2：r1〔x50〕r2〔x50〕w2〔x10〕r2〔y50〕w2〔y90〕c2r1〔y90〕c1H3：r1〔P〕w2〔insertytoP〕r2〔z〕w2〔z〕c2r1〔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更加合理。同时，ANSISQL隔离现象定义的不完整，还有一些异常仍然可能出现，必须定义新的现象来完成锁的定义。此外，必须重新进行定义P3。广义现象解释如下：P0：w1〔x〕。。。w2〔x〕。。。（c1ora1）（DirtyWrite）P1：w1〔x〕。。。r2〔x〕。。。（c1ora1）（DirtyRead）P2：r1〔x〕。。。w2〔x〕。。。（c1ora1）（FuzzyorNonRepeatableRead）P3：r1〔P〕。。。w2〔yinP〕。。。（c1ora1）（Phantom）
　　注意，ANSISQL中P3只禁止对谓词插入（和更新），而上面的P3的定义禁止任何满足谓词的写被读取，这里的写可以是插入，更新或删除。
　　根据上面定义的现象，将ANSISQL隔离级别重新定义，如表3所示：
　　对于单版本历史，容易得出P0，P1，P2，P3现象是假的锁版本现象。实际，禁止P0排除了在第一个事务写入数据项后第二个事务的写，相当于在数据项（和谓词）上持有长写锁。所以脏写是不可能的。类似地，禁止P1相当于对数据项进行了好形式的读取。禁止P2表示数据项加上长读锁。最后，禁止P3意味着持有长谓词读锁。因此，表3中基于上述现象定义的隔离级别与表2的锁隔离级别是相同的。换句话说，P0，P1，P2和P3是对于锁版本隔离级别的重新定义。
　　其他隔离类型
　　首先是游标稳定（cursorstability），游标稳定旨在防止丢失更新现象。P4（LostUpdate）：ThelostupdateanomalyoccurswhentransactionT1readsadataitemandthenT2updatesthedataitem（possiblybasedonapreviousread），thenT1（basedonitsearlierreadvalue）updatesthedataitemandcommits。将上述历史转化为：P4：r1〔x〕。。。w2〔x〕。。。w1〔x〕。。。c1（LostUpdate）（注意P4只是基于P0脏写和P1脏读，从锁隔离的角度上来说只是持有短读锁和长写锁，没有达到锁可重复读P2（也就是说不持有长读锁））H4：r1〔x100〕r2〔x100〕w2〔x120〕c2w1〔x130〕c1
　　如历史H4所示，问题是即使T2提交，T2的更新也会丢失。x的最终值为T1写入的130，P4至少在读已提交隔离级别，因为禁止P0（事务执行第一次写操作的数据项被另一个事务第二次写入）或P1（写后提交前被读取）的情况下允许出现H4。当然，禁止P2也排除了P4，因为P2是r1〔x〕，w2〔x〕，（c1ora1），包括了P4。因此，P4可用于作为区分读已提交和可重复读强度中间的隔离级别。即READCOMMITTEDCursorStabilityREPEATABLEREAD。
　　游标稳定扩展了读已提交隔离级别下对于SQL游标的锁行为。其提出游标上的Fetching操作rc（readcursor）。rc要求在游标的当前数据项上保持长读锁，直到游标移动或关闭（可能通过提交关闭）。当然，游标上的Fetching事务可以更新行（readcursor），即使游标在随后的Fetch上移动，写锁也将保持在行上直到事务提交。rc1〔x〕和以后的wc1〔x〕排除了介入的w2〔x〕。因此，针对游标上的情况，提出现象P4C：P4C：rc1〔x〕。。。w2〔x〕。。。w1〔x〕。。。c1（LostUpdate）
　　其次是快照隔离（SnapshotIsolation）。
　　在快照隔离下执行的事务始终从事务开始时起的数据（已提交）的快照中读取数据。事务开始时获取的时间戳称为其开始时间戳（StartTimestamp）。这一个时间戳可能为事务第一次读之前的任何时间。事务运行在快照隔离中时，只要可以维护其开始时间戳对应的快照数据，在就不会阻塞读。事务的写入（更新，插入和删除）也将反映在此快照中，如果事务第二次访问（即读取或更新）数据，则能再次读到。这个事务开始时间戳之后的其他事务的更新对于本次事务是不可见的。
　　快照隔离是一种多版本并发控制（MultiversionConcurrencyControl，MVCC）。当事务T1准备好提交时，它将获得一个提交时间戳（CommitTimestamp），该值大于任何现有的时间戳。当其他事务T2提交了数据的提交时间戳在T1事务的间隔〔StartTimestamp，CommitTimestamp〕中，只有T1与T2数据不重叠，事务才成功提交。否则，T1将中止。这个功能叫做先提交者成功（FirstCommitterWins），防止丢失更新（P4）。当T1提交时，其更改对于开始时间戳大于T1的提交时间戳的所有事务都可见。
　　快照隔离是一种多版本（MV）方法，因此单版本（SV）历史不能正确地反映时间上的操作序列。在任何时候，每个数据项可能有多个版本，由活动的和已提交的事务写入。事务必须读取合适的版本。考虑上面提到的历史H1，其表明在单值执行中需要P1。在快照隔离下，相同的操作序列将导致多值历史：
　　H1。SI：
　　r1〔x050〕w1〔x110〕r2〔x050〕r2〔y050〕c2r1〔y050〕w1〔y190〕c1
　　将MV历史映射到SV历史是在隔离层次中放置快照隔离的关键。例如，可以将H1。SI映射成的单值历史：H1。SI。SV：r1〔x50〕r1〔y50〕r2〔x50〕r2〔y50〕c2w1〔x10〕w1〔y90〕c1
　　快照隔离是不可串行化的，因为事务的读在一个时刻，写在另一个时刻。例如，考虑单值历史：H5：r1〔x50〕r1〔y50〕r2〔x50〕r2〔y50〕w1〔y40〕w2〔x40〕c1c2
　　H5是不可串行化的，并且具有与快照隔离下事务相同的事务间数据流（事务读取的版本没有选择）。这里假设为x和y写入一个新值的每个事务有保持xy0的约束，而T1和T2两者都是隔离的，所以约束不能保持在H5中。
　　约束违反（Constraintviolation）是一种通用和重要的并发异常类型。个别数据库满足多个数据项的约束（例如，键的唯一性，引用完整性，两个表中的行的复制关系等）。
　　它们一起形成数据库不变量约束谓词C（DB）。如果数据库状态DB与约束一致，则不变量为TRUE，否则为FALSE。事务必须保留约束谓词以保持一致性：如果数据库在事务启动时保持一致，则事务提交时数据库将一致。如果事务读取到违反约束谓词的数据库状态，则事务将受到约束违反并发异常的影响。这种约束违反在〔DAT〕中称为不一致分析（inconsistentanalysis）。
　　给出了几个相关的定义。A5（DataItemConstraintViolation）。SupposeC（）isadatabaseconstraintbetweentwodataitemsxandyinthedatabase。这里提出两个由于违反约束引起的现象。A5AReadSkewSupposetransactionT1readsx，andthenasecondtransactionT2updatesxandytonewvaluesandcommits。IfnowT1readsy，itmayseeaninconsistentstate，andthereforeproduceaninconsistentstateasoutput。Intermsofhistories，wehavetheanomaly：A5A：r1〔x〕。。。w2〔x〕。。。w2〔y〕。。。c2。。。r1〔y〕。。。（c1ora1）（ReadSkew）A5BWriteSkewSupposeT1readsxandy，whichareconsistentwithC（），andthenaT2readsxandy，writesx，andcommits。ThenT1writesy。Iftherewereaconstraintbetweenxandy，itmightbeviolated。Intermsofhistories：A5B：r1〔x〕。。。r2〔y〕。。。w1〔y〕。。。w2〔x〕。。。（c1andc2occur）（WriteSkew）
　　不可重复度P2是读倾斜的退化形式，其中令xy。更典型地，事务读取两个不同但相关的项目（如引用完整性）。写倾斜（A5B）可能来自银行业务语义的约束，如只要总共持有的余额保持非负，账户余额才能变为负值。如历史H5中出现的异常。
　　在排除P2的历史中，A5A和A5B都不会出现，因为A5A和A5B都有T2写入一个先前未被提交的T1读取的数据项的情况。因此，现象A5A和A5B仅用于区分低于可重复读取的隔离级别。
　　对于快照隔离，比读已提交更强，即READCOMMITTEDSnapshotIsolation。
　　证明：在快照隔离中，firstcommitterwins排除了P0（脏写入），并且时间戳机制阻止了P1（脏读），因此快照隔离不比读已提交弱。此外，A5A可能在读已提交下，但不在快照隔离与时间戳机制下。因此READCOMMITTEDSnapshotIsolation。
　　在单版本现象中，难以描述快照隔离历史如何违反现象P2。异常A2不能发生，因为快照隔离下的事务即使在另一个事务更新数据项之后也会只读取数据项的相同版本对应的值。然而偏写（A5B）显然会发生在快照隔离下（比如H5），并且在单值历史解释中已经提到，禁止了P2也会排除A5B。因此，快照隔离承认可重复读没有历史异常。
　　快照隔离下不会发生A3异常（幻读）。在一个事务更新数据项集时，另一个事务多次谓词读的将始终看到相同的旧数据项集。但是可重复读隔离级别可能会遇到A3异常。快照隔离禁止具有异常A3的历史，但允许A5B，而可重复读则相反（允许A3禁止A5B）。因此，REPEATABLEREADSnapshotIsolation。
　　但是，快照隔离（能排除A3）并不排除P3（谓词读事务提交前谓词范围内被另一事务写入）。考虑一个约束，表示由谓词确定的一组作业任务不能有大于8的小时数。T1读取此谓词，确定总和只有7小时，并添加1小时持续时间的新任务，而并发事务T2做同样的事情。由于两个事务正在插入不同的数据项（以及不同的索引条目（如果有的话）），因此FirstCommitterWins不排除此情况，并且可能发生在快照隔离中。但是在任何等价的串行历史中，在这种情况下会出现P3现象。
　　另外，快照隔离没有幻读（在ANSISQL中狭义定义下的A3），因为每个事务都不会看到并发事务的更新。快照隔离历史排除了现象A1，A2和A3。因此，在表1中的异常可串行化（ANOMALYSERIALIZABLE）的解释语境下：ANOMALYSERIALIZABLESNAPSHOTISOLATION。
　　快照隔离的乐观并发控制方法对于只读事务具有明显的并发优势，但其对更新事务的好处仍然存在争议。
　　表4展示了上述提到的所有的隔离级别以及对应的现象：
　　综上，作者认为原始ANSISQL隔离级别的定义存在严重问题。英文文字上的定义是模糊和不完整的，脏写P0没有被排除。同时建议ANSISQL隔离级别替换为对应锁隔离级别。同时将各种商业数据库中实现的隔离级别进行比对，对应关系如图2所示：
　　以上内容主要参考论文ACritiqueofANSISQLIsolationLevels。Part3快照隔离的发展
　　论文ACritiqueofANSISQLIsolationLevels中提出了快照隔离（SnapshotIsolation）的定义：事务的读操作从已提交（Committed）快照中读取数据，快照时间可以是事务的第一次读操作之前的任意时间，记为StartT事务准备提交时，获取一个CommitTimestamp，它需要比现存的StartTimestamp和CommitTimestamp都大；事务提交时进行冲突检查，如果没有其他事务在〔StartTS，CommitTS〕区间内提交了与自己的WriteSet有交集的数据，则本事务可以提交；快照隔离允许事务用很旧的StartTS来执行，从而不被任何的写操作阻塞，或者读一个历史数据。
　　这里需要注意：上述时间和空间没有交集的检查，主要是为了阻止LostUpdate的异常；实现的时候通常利用锁和LastCommitMap，提交之前锁住相应的行，然后遍历自己的WriteSet，检查是否存在一行记录的LastCommit落在了自己的〔StartTS，CommitTS〕内；如果不存在冲突，就把自己的CommitTS更新到LastCommit中，并提交事务释放锁。
　　仔细考虑上述快照隔离的定义，考虑如下几个问题：CommitTS的获取：如何得到一个比现有的StartTS和CommitTS都大的时间戳，尤其是在分布式系统中；StartTS的获取：虽然上面提到的StartTS可以是一个很旧的时间，那么StartTS是否需要单调递增；提交时进行的冲突检查是为了解决LostUpdate异常，那么对于这个异常来说，写写冲突检查是否是充分且必要的；分布式、去中心的快照隔离级别该怎样实现。
　　针对上述问题，下面进行展开。这里将上述提到的快照隔离（SI）记为BasicSI。
　　分布式快照隔离
　　本节主要讲解HBase、Percolator以及Omid在快照隔离方面工程实践进展。
　　HBase
　　HBase中快照隔离是完全基于多个HBase表来实现的分布式SI：VersionTable：记录一行数据的最后的CommitTS；CommittedTable：记录CommitLog，事务提交时将commitlog写到这张表中可认为CPreCommitTable：用作检查并发冲突，可理解为锁表；WriteLabelTable：用于生成全局唯一的WriteLCommittedIndexTable：加速StartTS的生成；DS：实际存储数据。
　　协议大致实现如下：StartTS：从CommittedTable中遍历找到单调连续递增的最大提交时间戳，即前面不存在空洞（这里的空洞指的是事务拿了CommitTS但没有按照CommitTS顺序提交）；CommittedIndex：为了避免获取StartTS过程遍历太多数据，每个事务在获得StartTS之后会写到CommittedIndexTable中，之后的事务从这个时间戳开始遍历即可，相当于缓存了一下；read：需要判断一个事务的数据是否提交了，去VersionTable和CommittedTable检查；precommit：先检查CommittedTable是否存在冲突事务，然后在PreCommitTable记录一行，再检查PreCommitTable中是否存在冲突的事务；commit：拿到一个commitTS，在CommittedTable写一条记录，更新PreCommitTable。
　　HBase采用结构上解耦的方式实现分布式SI，所有的状态都存储到HBase中，每个场景的需求都用不同的表来实现，但这种解耦也带来了性能损失。这里将HBase实现的快照隔离记为HBaseSI。
　　Percolator
　　在2010年提出的Percolator在HBase的基础上更加工程化，将涉及到的多个Table合并成了一个，在原有数据的基础上增加了lock、write列：lock：用作是WW冲突检查，实际使用时lock会区分PrimaryLock和SecondaryLwrite：可理解为commitlog，事务提交仍然走2PC，Coordinator决定Commit时会在write列写一条commitlog，写完之后事务即认为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其实更容易适配到不同的分布式存储系统，侵入较小。
　　ICDE2014的文章奠定Omid架构：TSO（TimestampOracle）：负责时间戳分配、事务提交；BookKeeper：分布式日志组件，用来记录事务的CommitLDataStore：用HBase存储实际数据，也可适配到其他的分布式存储系统。
　　TSO维护如下几个状态：时间戳：单调递增的时间戳用于SI的StartTS和CommitTS；lastCommit：所有数据的提交时间戳，用于WW冲突检测，这里会根据事务的提交时间进行一定裁剪，使得在内存中能够存下；committed：一个事务提交与否，事务ID用StartTS标识，这里记录StartTSCommitTS的映射即可；uncommitted：分配了CommitTS但还未提交的事务；Tmax：lastCommit所保留的低水位，小于这个时间戳的事务来提交时一律Abort。
　　这里的lastCommit即关键所在，表明了事务提交时不再采用和Percolator一样的先加锁再检测冲突的Pessimistic方式，而是：将Commit请求发到TSO来进行Optimistic的冲突检测；根据lastCommit信息，检测一个事务的WriteSet是否与lastCommit存在时间和空间的重叠。如果没有冲突，则更新lastCommit，并写commitlog到BookKTSO的lastCommit显然会占用很多内存，并且成为性能瓶颈。为此，仅保留最近的一段lastCommit信息，用Tmax维护低水位，小于这个Tmax时一律abort。
　　另外提出了一个客户端缓存Committed的优化方案，减少到TSO的查询；在事务的start请求中，TSO会将截止到start时间点的committed事务返回给客户端，从而客户端能够直接判断一个事务是否已经提交，整体架构如下图所示。
　　在FAST2017中，Omid对之前的架构进行了调整，做了一些工程上的优化：commitlog不再存储于BookKeeper，而是用一张额外的HBase表存储；客户端不再缓存committed信息，而是缓存到了数据表上；因此大部分时候，用户读数据时根据commit字段就能够判断这行数据是否已经提交了。
　　在PLVDB2018中，Omid再次进行了大幅的工程优化，覆盖了更多的场景：CommitLog不再由TSO来写，而是offload到客户端，提高了扩展性，也降低了事务延迟；优化单行读写事务，在数据上增加一个maxVersion的内存记录，实现了单行的读写事务不再需要进行中心节点校验。
　　去中心化快照隔离
　　上述都是针对分布式SI的实现，它们都有一个共同特征：保留了中心节点，或用于事务协调，或用于时间戳分配。对于大规模或者跨区域的事务系统来说，这仍然存在风险。针对这点，就有了一系列对去中心化快照隔离的探索。
　　ClockSI
　　ClockSI首先指出，SnapshotIsolation的正确性包含三点：ConsistentSnapshot：所谓Consistent，即快照包含且仅包含Commit先于SnapshotTS的所有事务；CommitTotalOrder：所有事务提交构成一个全序关系，每次提交都会生成一个快照，由CommitTS标识；WriteWriteConflict：事务Ti和Tj有冲突，即它们WriteSet有交集，且〔SnapshotTS，CommitTS〕有交集。
　　基于这三个点，ClockSI提出了如下的算法：StartTS：直接从本地时钟获取。Read：当目标节点的时钟小于StartTS时，进行等待，即下图中的ReadD当事务处于Prepared或者Committing状态时，也进行等待；等待结束之后，即可读小于StartTS的最新数据；这里的ReadDelay是为了保证ConsistentSnapshot。CommitTS：区分出单Partition事务和分布式事务，单Partition事务可以使用本地时钟作为CommitTS直接提交；而分布式事务则选择max｛PrepareTS｝作为CommitTS进行2PC提交；为了保证CommitTS的全序，会在时间戳上加上节点的id，和LamportClock的方法一致。
　　Commit：不论是单partition还是多partition事务，都由单机引擎进行WW冲突检测。
　　ClockSI有几点创新：使用普通的物理时钟，不再依赖中心节点分配时间戳。对单机事务引擎的侵入较小，能够基于一个单机的SnapshotIsolation数据库实现分布式的SI。区分单机事务和分布式事务，几乎不会降低单机事务的性能，分布式使用2PC进行原子性提交。
　　在工程实现中，还需考虑这几个问题：StartTS选择：可以使用较旧的快照时间，从而不被并发事务阻塞；时钟漂移：虽然算法的正确性不受时钟漂移的影响，但时钟漂移会增加事务的延迟，增加SessionConsistency：事务提交后将时间戳返回给客户端记为latestTS，客户端下次请求带上这个latestTS，并进行等待。
　　论文实验结果很突出，不过正确性论证较为简略，还有待进一步证明。
　　ConfluxDB
　　如果说ClockSI还有什么不足，那可能就是依赖了物理时钟，在时钟漂移的场景下会对事务的延迟和abortrate造成影响。能否不依赖物理时钟，同时又能够实现去中心化呢？
　　ConfluxDB提出的方案中，仅仅依赖逻辑时钟来捕获事务的先于关系，基于先于关系来检测冲突：当事务Ti准备提交时，2PC的Coordinator向所有参与者请求事务的concurrent（Ti）列表，这里的concurrenct（Ti）定义为begin（Tj）commit（Ti）的事务；Coordinator在收到所有参与者的concurrent（Ti）之后，将其合并成一个大的gConcurrent（Ti），并发回给所有参与者；参与者根据gConcurrent（Ti），检查是否存在一个事务Tj，dependents（Ti，Tj）（TjgConcurrent（Ti））（Tjserials（Ti）），即存在一个事务Tj，在不同的partition中有不同的先后关系，违背了ConsistentSnapshot的规则；参与者将冲突检测的结果发回给Coordinator，Coordinator据此决定是Commit还是A除此之外Coordinator需要给这个事务生成一个CommitTS，这里选择和ClockSI类似的方式，commitTSmax｛prepareTS｝，这里的prepareTS和commitTS会按照LogicalClock的方式在节点之间传递。
　　ConfluxDB的这种方案不需要依赖物理时钟，不需要任何wait，甚至不需要单机的事务引擎支持读时间点快照的功能。但是这个方案的不足是，可能Abortrate并不是很好，以及在执行分布式事务时的延迟问题。
　　GeneralizedSI
　　GeneralizedSI将SnapshotIsolation应用到ReplicatedDatabase中，使得事务的Snapshot可以从复制组的从节点读取。这带来的意义有两点，使用一个旧的快照，不会被当前正在运行的事务阻塞，从而降低事务延迟；而从Secondary节点读取数据，则可以实现一定程度上的读写分离，扩展读性能。
　　ParallelSI
　　上面的方案中，可以将读请求offload到Secondary节点，一定程度上能够扩展读性能。那么继续将这个思路延伸一下，能不能把事务的提交也交给Secondary节点来执行呢？
　　这就是ParallelSnapshotIsolation的思路，在跨区域复制的场景下，业务通常会有地理位置局部性的要求，在上海的用户就近把请求发到上海的机房，在广州的用户把请求发到广州的机房；并且在实际的业务场景中，往往可以放松对一致性和隔离性的要求。Parallel放弃了SnapshotIsolation中对CommitTotalOrder的约束，从而实现了多点的事务提交。在通用数据库中可能很难使用这样的方案，但实际的业务场景中会很有价值。
　　SerializableSI
　　SnapshotIsolation所区别于Serializable的是WriteSkew异常，为了解决这个异常，可以基于SnapshotIsolation进行优化，并且尽量保留SnapshotIsolation的优秀性质，进而提出了SerializableSI。
　　论文Serializableisolationforsnapshotdatabases是AlanD。Fekete和MichaelJ。Cahill在2009年发表的，是早期研究SSI的理论成果。
　　论文从串行化图理论说起，在MultiVersion的串行图中，增加一种称之为RW依赖的边，即事务T1先写了一个版本，事务T2读了这个版本，则产生RW依赖。当这个图产生环时，则违背了Serializable。
　　在论文中作者证明，SI产生的环中，两条RW边必然相邻，也就意味着会有一个pivot点，既有出边也有入边。那么只要检测出这个pivot点，选择其中一个事务abort掉，自然就打破了环的结构。算法的核心就在于动态检测出这个结构，因此会在每个事务记录一些状态，为了减少内存使用，使用inConflict和outConflict两个bool值来记录；在事务执行读写操作的过程中，会将与其他事务的读写依赖记录于这两个状态中。虽然用bool值减少了内存使用，但显然也增加了falsepositive，会导致一部分没有异常的事务被abort。据文中的实验结果表明，性能好于S2PL（严格两阶段锁，可实现串行化），abort较低，给SnapshotIsolation带来的开销也比较小。但据后来的PostgreSQL的SSI实现，为了减少内存占用仍需要不少的工作量，有兴趣可参考SerializableSnapshotIsolationinPostgreSQL。
　　WriteSI
　　Yabandeh在论文Acritiqueofsnapshotisolation中提出WriteSnapshotIsolation。作者首先批判BasicSI，因为BasicSI给人造成了一种误导：进行写写冲突检测是必须的。文章开篇即提出，SI中的LostUpdate异常，不一定需要阻止WW冲突；换成RW检测，允许WW冲突，既能够阻止LostUpdate异常，同时能够实现Serializable，一举两得。
　　为何WW检测不是必须的？简要论证一下，在MVCC中，写冲突的事务写的是不同的版本，为何一定会有冲突？实际上只有两个事务都是RW操作时才有异常，如果其中一个事务只有W操作，并不会出现LostU换言之，未必要检测WW冲突，RW冲突才是根源所在。
　　基于RW冲突检测的思想，作者提出WriteSnapshotIsolation，将之前的SnapshotIsolation命名为ReadSnapshotIsolation。如下图中：
　　TXNn和TXNc有冲突，因为TXNc修改了TXNn的ReadSTXNn和TXNc没有冲突，虽然他们都修改了r这条记录，BasicSI会认为有冲突，但WriteSI认为TXNc没有修改TXNn的ReadSet，则没有RW冲突。
　　如何检测RW冲突：事务读写过程中维护ReadSet，提交时检查自己的ReadSet是否被其他事务修改过。但实际也不会这么简单，因为通常维护ReadSet的开销比WriteSet要大，且这个冲突检查如何做，难道加读锁？所以在原文中，作者只解释了中心化的WriteSI如何实现（BadgerDB使用了这个算法，实现了支持事务的KV引擎）。至于去中心化的实现，可从CockroachDB找到一点影子。
　　不过RW检测会带来很多好处：只读事务不需要检测冲突，它的StartTS和CommitTS一样；只写事务不需要检测冲突，它的ReadSet为空；更重要的是，这种算法实现的隔离级别是Serializable而不是SnapshotIsolation。
　　综合上述内容，为实现串行化，传统上只能采用基于锁的并发控制，由于性能问题，很难在实际工程中应用。SerializableSI为高性能的实现可串行化，提供了一种新的路径。
　　以上内容主要参考SnapshotIsolation综述。
　　写在最后
　　在wiki上PostgreSQL对SSI解释有这么一句话：DocumentationofSerializableSnapshotIsolation（SSI）inPostgreSQLcomparedtoplainSnapshotIsolation（SI）。ThesecorrespondtotheSERIALIZABLEandREPEATABLEREADtransactionisolationlevels，respectively，inPostgreSQLbeginningwithversion9。1。因此，在讨论任何一款数据库产品实现的隔离级别时，必须了解该隔离级别背后实现的算法原理。
　　文章来源：KaiwuDBhttps：juejin。cnpost7052496886061596709