在前文中，咱们曾经介绍了事务的相干概念以及事务隔离的不同级别，本文将着重介绍快照隔离的倒退。
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…)