分布式文件系统中快照隔离的实现方案

SI & MVCC

快照隔离（SI,Snapshot Isolation）是讨论隔离性时常见的术语，可以做两种的解读，一是具体的隔离级别，SQL Server、CockroachDB都直接定义了这个隔离级别；二是一种隔离机制用于实现相应的隔离级别，在Oracle、MySQL InnoDB、PostgreSQL等主流数据库中普遍使用。多版本并发控制（MVCC，multiversion concurrency control）是通过记录数据项历史版本的方式提升系统应对多事务访问的并发处理能力，例如避免单值（Single-Valued）存储情况下写操作对读操作的锁排斥。MVCC和锁都是SI的重要实现手段，当然也存在无锁的SI实现。

SI 运作方式

事务（记为T1）开始的瞬间会获取一个时间戳Start Timestamp（记为ST），而数据库内的所有数据项的每个历史版本都记录着对应的时间戳Commit Timestamp（记为CT）。T1读取的快照由所有数据项版本中那些CT小于ST且最近的历史版本构成，由于这些数据项内容只是历史版本不会再次被写操作锁定，所以不会发生读写冲突，快照内的读操作永远不会被阻塞。

其他事务在ST之后的修改，T1不可见。当T1 commit的瞬间会获得一个CT，并保证大于此刻数据库中已存在的任意时间戳（ST或CT），持久化时会将这个CT将作为数据项的版本时间戳。T1的写操作也体现在T1的快照中，可以被T1内的读操作再次读取。当T1 commit后，修改会对那些持有ST大于T1 CT的事务可见。

如果存在其他事务（T2），其CT在T1的运行间隔【ST，CT】之间，与T1对同样的数据项进行写操作，则T1 abort，T2 commit成功，这个特性被称为First-committer-wins，可以保证不出现Lost update。事实上，部分数据库会将其调整为First-write-wins，将冲突判断提前到write操作时，减少冲突的代价。类似CAS，从而阻止了更新异常(Lost Update)的出现。

简单提一下冲突检查的方式：

实现的时候通常利用锁和LastCommit Map，提交之前锁住相应的行，然后遍历自己的WriteSet，检查是否存在一行记录的LastCommit落在了自己的[ST, CT]内。
如果不存在冲突，就把自己的CommitTS更新到LastCommit中，并提交事务释放锁。

这个过程不是某个数据库的具体实现，事实上不同数据库对于SI实现存在很大差别。
例如，PostgreSQL会将历史版本和当前版本一起保存通过时间戳区分，而MySQL和Oracle都在回滚段中保存历史版本。
MySQL的RC与RR级别均使用了SI，如果当前事务（T1）读操作的数据被其他事务的写操作加锁，T1转向回滚段读取快照数据，避免读操作被阻塞。

实际上，我们可以对于上述运行过程提问：

提交时进行的冲突检查是为了解决Lost Update异常，那么对于这个异常来说，写写冲突的检查是充分且必要的吗？
答案在Write-SI一节中。
很显然SI是绝对依赖于时间戳的，那么对于分布式系统，如果获得这样的时间戳呢？
答案参考：Distributed System Clocks分布式系统时钟解决方案

SI & Write Skew

事实上SI不能保证完整的串行化效果，无法处理Write Skew（写偏序），这是一致性约束下的异常现象，即两个并行事务都基于自己读到的数据集去覆盖另一部分数据集。

下图的“黑白球”常常被用来说明写偏序问题。

在相关论文《Serializable Isolation for Snapshot Database》一文中，Fekete证明，SI产生的环中，两条RW边必然相邻，也就意味着会有一个pivot点，既有出边也有入边。那么只要检测出这个pivot点，选择其中一个事务abort掉，自然就打破了环的结构。

所以算法的核心在于：

动态检测出环结构

因此，为了检测出这个环结构，需要在每个事务中记录一些状态，为了减少内存的使用，简单的用 inConflict和outConflict两个bool类型变量来做记录：在事务执行读写操作的过程中，会将与其他事务的读写依赖记录到这两个状态中。

而由于只是用了bool变量来记录节点的“出入”(入度/出度)，虽然能减少内存使用，但是过于简单的配置可能会造成一部分没有异常的事务被abort (据文中的实验结果表明，性能好于S2PL，abort较低，给Snapshot Isolation带来的开销也比较小)。

从理论模型看，SSI性能接近SI，远远好于S2PL。2012年，PostgreSQL在9.1版本中实现了SSI，可能也是首个支持SSI的商业数据库，验证了SSI的实现效果。CockroachDB也从Cahill的论文获得灵感，实现SSI并将其作为其默认隔离级别。

随着技术的发展，SI/SSI已经成为主流数据库的隔离技术，尤其是后者的出现，无需开发人员在代码通过显式锁来避免异常，从而降低了人为错误的概率。

Write-SI

Write-Snapshot Isolation来自Yabandeh的《A critique of snapshot isolation》，名字可谓语不惊人死不休。在工业界也造成一定反响：CockroachDB的文章里提到，WSI的思路对他们产生了很大启发；而Badger则是直接使用了这个算法，实现了支持事务的KV引擎。

之所以critique snapshot isolation，因为Basic Snapshot Isolation给人造成了一种误导：进行写写冲突检测是必须的。