在前文中，咱们曾经介绍了事务的相干概念以及事务隔离的不同级别，本文将着重介绍快照隔离的倒退。
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。因而，在探讨任何一款数据库产品实现的隔离级别时，必须理解该隔离级别背地实现的算法原理。
参考文献
- (https://book.douban.com/subje...)
- (https://cs.uwaterloo.ca/~ddbook/)
- (https://cs.uwaterloo.ca/~ddbook/)
- (https://dl.acm.org/doi/abs/10...)
- (https://zhuanlan.zhihu.com/p/...)
- (https://zhuanlan.zhihu.com/p/...)
- (https://dgraph.io/blog/post/b...)
- (https://wiki.postgresql.org/w...)