本篇主要是讲述CockroachDB 事务隔离级别SSI的理论依据，由此我们可以更加深入理解cockroachDB的事务实现逻辑。

CockroachDB SSI隔离级别来源于论文Serializable Isolation for Snapshot Databases。在论文中作者分析当前的数据库系统，主流的数据库系统大多采用SI隔离级别，SI很好的解决了并发读写的问题（MVCC，First-Committer-Wins原则），不过也存在一个问题，那就是Write Skew。业务上为了规避这些问题使用了一种并发控制算法strict two-phase locking（S2PL），不过作者认为这个算法性能仍然不令人满意。

作者提供的算法具备如下特点：

1.算法确保每一个执行都是串行的（等同于），无关业务逻辑。

2.算法保证读事务永远不被延迟，同时并发写事务不会因为读事务延迟。

3.在一个范围条件下（主要是针对传统数据库中的where），吞吐接近SI隔离级别下的吞吐，但是远好于S2PL。

4.算法很容易在具备SI隔离级别的DB上实施。

MVSG

多版本序列化图（Multiversion serialization graph），简称MVSG。作者利用它分析SI的写偏序问题。

       MVSG˙中有一个理论：如果一个MVSG中没有环，说明这些事务是可串行化的。这个工具常常用来分析SI的并发控制。Adya证明在SI中任何环都有两个rw-dependency的边。Fekete进一步证明这两个边是连续的，并且位于两个并发的事务。

作者定义处于两个事务交叉点的事务称为pivot事务，有理论表明：在任何SI隔离级别下的非串行化的事务集合中存在这样的pivot事务。下面作者举例：

假设三个事务

T0: r(y) w(x)

T1: w(y) w(z)

TN: r(x) r(z)

假如没有TN，那么T0和T1是串行化的，因为根据MVSG，两个事务之间存在一个边。但是有了TN之后问题就复杂了。作者列举了两种可能存在场景，如下图F4(a)，所有的读都发生在写之后，F4(b)，TN读取x发生在T0写x之前。

SSI

于是作者提出自己的算法，核心就是在过程中发现潜在的产生环的边，通过终止其中一个事务达到破坏环，进而达到串行化的目的。

因此作者给事务增加了两个布尔标记.

T.inConflict：表示是否存在一个从其他事务到事务T的rw-dependency边

T.outConflict：表示是否存在一个从事务T到其他事务的rw-dependnecy边

如果这两个标记都是true，那么这个事务T中止。

作者利用lock管理来实现获得rw-dependency。一般SI数据库中都存在一个WRITE lock，这个lock用来保证SI的First-Committer-Wins原则。同时作者创造了另一个锁SIREAD，这个锁记录所有被事务读取的item的version，获取SIREAD lock并不会发生阻塞，同时SIREAD lock并不会延迟WRITE lock。这里有一点不同的是，SIREAD lock并不会随着事务T的结束而释放，它会在所有与事务T并发执行的事务都结束后才释放。

作者为了简化算法，约定了如下假设（这些假设是合理的）

1. 对于任意的item x，我们高效的获得所有作用在x上lock信息

2. 对于任意的lock L，我们可以高效的获得L.owner。

3. 对于item x任意的版本xt，我们可以高效的获得xt.creator（创建这个版本的事务）

4. 对于tiem x给定一个版本，我们可以高效的获得x所有其他大于给定版本的版本信息。

算法如下：

算法正确定论述

1. SI下非串行化事务集合一定有一个包含两个连续的rw-dependencies的环

2. 算法检测每一个rw-dependency

3. 如果检测到两个连续的rw-dependencies，至少其中一个事务要被中止以破坏这个环。

算法缺点

这个算法采用比较保守的环检测手段，因此会出现中止那些本不应该中止的事务情况。

这个图无环，但是根据算法T0的两个标记都是true，因此T0会被中止。

测试

作者基于Berkeley DB改造以支持他的SSI算法，并进行测试，测试结果如下：