数据库内核月报－ 2019/02 - Database · 原理介绍 · Snapshot Isolation 综述 - 《数据库内核月报》

前言
Basic SI
Distributed
Decentralized
- Clock-SI
- ConfluxDB
Replication
- Generalized SI
- Parallel SI
Serializable
- Serializable Isolation for Snapshot Database
- Write-SI
总结
参考

前言

Snapshot Isolation对于接触过数据库领域的同学来说，几乎是入门级的知识了。原因有几点：一来，谈到事务的隔离级别，必然会有所谓Read Uncommitted、Read Committed、Repeatable Read、Serializable，以及Snapshot Isolation；二来，主流的数据库，单机如MySQL、MongoDB，分布式如TiDB、OceanBase，几乎都实现了Snapshot Isolation这一隔离级别；三来，且在非形式化的定义中，Snapshot Isolation也很易于理解，易于实现。

但通过最近对Snapshot Isolatino的系统性研究，发现事情并不是这么简单，例如这几个问题：

Snapshot Isolation中所说的Snapshot指的是什么，需要满足Consistency约束吗？
SI对时钟系统的必要约束是什么？必须是一个单调递增的中心化时钟吗？
SI定义写写冲突，是为了解决什么问题？它是一个必要的约束吗？
事务隔离和复制一致性是什么关系？能否基于一个非线性一致的复制协议，实现一个SI？

本篇文章将围绕这几个问题，将时间从2019年拉回到1995年那个雷雨交加的夜晚，围观Hal Berenson等人在小木屋里提出的对ANSI SQL isolation level的critique；再跨越历史的长河，纵观诸多学者对Snapshot Isolation的研究，以望寻得对这些问题的解答。

希望本文能够对读者有所启发。受限于本人当前的技术水平，未尽之处还请指教。

Basic SI

1995年Hal Berenson等人在《A critique of ANSI SQL Isolation levels》中提出了Snapshot Isolation的概念，我们先来看下这里是如何定义SI的，为了不失真，这里只做一下翻译不做主观解读：

事务的读操作从Committed快照中读取数据，快照时间可以是事务的第一次读操作之前的任意时间，记为StartTimestamp
事务准备提交时，获取一个CommitTimestamp，它需要比现存的StartTimestamp和CommitTimestamp都大
事务提交时进行冲突检查，如果没有其他事务在[StartTS, CommitTS]区间内提交了与自己的WriteSet有交集的数据，则本事务可以提交；这里阻止了Lost Update异常
SI允许事务用很旧的StartTS来执行，从而不被任何的写操作阻塞，或者读一个历史数据；当然，如果用一个很旧的CommitTS提交，大概率是会Abort的

其正确性相对容易理解，这里不做赘述。简单提一下冲突检查：

这里的时间和空间没有交集的检查，主要是为了阻止LostUpdate的异常
实现的时候通常利用锁和LastCommit Map，提交之前锁住相应的行，然后遍历自己的WriteSet，检查是否存在一行记录的LastCommit落在了自己的[StartTS, CommitTS]内
如果不存在冲突，就把自己的CommitTS更新到LastCommit中，并提交事务释放锁

但仔细思考这里提出Snapshot Isolation，我们会发现存在几个疑问：

CommitTS的获取，如何得到一个比现有的StartTS和CommitTS都大的时间戳；尤其是在分布式系统中，生成一个全局单调递增的时间戳显然会是一个单点
StartTS的获取，这里提到的StartTS可以是一个很旧的时间，那么就不需要单调递增了？
提交时进行的冲突检查是为了解决Lost Update异常，那么对于这个异常来说，写写冲突的检查是充分且必要的吗？
如何实现分布式、甚至去中心化的Snapshot Isolation

接下来会围绕这几个方向进行展开。为了讨论方便，我们将这里提到的Snapshot Isolation实现方法记为Basic SI。

Distributed

分布式是一个很重要的方向，在2010年左右的HBaseSI、Percolator、Omid就对Distributed SI在学术和工程方面进行了探索。

HBase-SI

HBaseSI是完全基于HBase实现的分布式SI方案，注意到它是完全基于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

虽然方案的性能堪忧，但这种解耦的思路着实令人称奇。

Percolator

HBaseSI在结构上可谓十分解耦，将所有的状态都下沉到了HBase中，每个场景的需求都用不同的表来实现；但这种解耦也带来了性能损失。同在2010年提出的Percolator就做的更加工程化，将以上的诸多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方案中的诸多race处理。

关于Precolator的解读在中文社区已经很多，这里就不再赘述。之前我也写过一篇解读。

Omid三部曲

Omid是Yahoo的作品，同样是基于HBase实现分布式SI，但和Percolator的Pessimistic方法相比，Omid是一种Optimistic的方式，正如其名：『Optimistically transaction Management In Datastores』。其架构相对优雅简洁，工程化做得也不错；近几年接连在ICDE、FAST、PVLDB上发了文章，也是学习分布式事务的优秀资料。

文中多次diss了Percolator，认为Percolator的基于Lock的方案虽然简化了事务冲突检查，但是将事务的驱动交给客户端，在客户端故障的情况下，遗留的Lock清理会影响到其他事务的执行，并且维护额外的lock和write列，显然也会增加不小的开销。而Omid这样的Optimistic方案完全由中心节点来决定Commit与否，在事务Recovery方面会更简单；并且，Omid其实更容易适配到不同的分布式存储系统，侵入较小。

令人好奇的是，Omid早期就是做Write-Snapshot Isolation那些人搞的系统，但后来的Omid发展过程中，并么有使用Write-Snapshot Isolation算法了。

这里的三部曲，分别对应了他们发的三篇文章：

ICDE 2014: 《Omid: Lock-free transactional support for distributed data stores》
FAST 2017：《Omid, reloaded: Scalable and highly-available transaction processing》
PVLDB 2018：《Taking omid to the clouds: fast, scalable transactions for real-time cloud analytics》

2014年的文章即奠定了Omid的架构：

TSO：负责时间戳分配、事务提交
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事务返回给客户端，从而客户端能够直接判断一个事务是否已经提交：

在FAST2017中，Omid对之前的架构进行了调整，做了一些工程上的优化：

commit log不再存储于BookKeeper，而是用一张额外的HBase表存储
客户端不再缓存committed信息，而是缓存到了数据表上；因此大部分时候，用户读数据时根据commit字段就能够判断这行数据是否已经提交了

而在PLVDB2018，Omid再次进行了大幅的工程优化，覆盖了更多的场景：

Commit Log不再由TSO来写，而是offload到客户端，提高了扩展性，也降低了事务延迟
优化单行读写事务，在数据上增加一个maxVersion的内存记录，实现了单行的读写事务不再需要进行中心节点校验

可以看到，中心化的分布式SI也可以取得非常优秀的性能。

Decentralized

上面提到了一众分布式SI的实现都有一个特征，他们仍然保留了中心节点，或用于事务协调，或用于时间戳分配；对于大规模或者跨区域的事务系统来说，这仍然是一个心头之痛。针对这个问题，就有了一系列对去中心化SI的探索。

Clock-SI

Clock-SI是2013年EPFL的作品，一作目前在Google工作（据Linkedin信息）。虽在国内没有什么讨论，但据悉，工业界已经有了实践。在PGCon2018的一个talk《Towards ACID scalable PostgreSQL with partitioning and logical replication》就提到，他们已经在应用Clock-SI的算法到PostgreSQL中，实现去中心化的SI；而MongoDB虽然未曾提及他们使用分布式事务算法，但据目前提交的代码来看，使用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冲突检测

ClockSI有几点创新：

使用普通的物理时钟，不再依赖中心节点分配时间戳
对单机事务引擎的侵入较小，能够基于一个单机的Snapshot Isolation数据库实现分布式的SI
区分单机事务和分布式事务，几乎不会降低单机事务的性能；分布式使用2PC进行原子性提交

在工程实现中，还需考虑这几个问题：

StartTS选择：可以使用较旧的快照时间，从而不被并发事务阻塞
时钟漂移：虽然算法的正确性不受时钟漂移的影响，但时钟漂移会增加事务的延迟，增加abort rate
Session Consistency：事务提交后将时间戳返回给客户端记为latestTS，客户端下次请求带上这个latestTS，并进行等待

实验结果自然是非常漂亮，不论是LAN还是WAN都有很低的延迟：

不过较为遗憾的是，此文对正确性的证明较为简略，后续笔者会对此算法进行详细分析。如果正确性得到保证，不出意外的话这几年会涌现出不少基于ClockSI的分布式数据库实现。

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，甚至不需要单机的事务引擎支持读时间点快照的功能；这意味着，是不是可以基于单机的XA来实现全局一致的快照，MySQL再也不用哭了。但是这个方案的阴暗面是，可能Abort rate并不是很好，以及在执行分布式事务时的延迟问题。

Replication

Replication看起来和事务是独立的两个东西，但实际上他们之间存在一些关联。

Generalized SI

Generalized SI将Snapshot Isolation应用到Replicated Database中，使得事务的Snapshot可以从复制组的从节点读取。这带来的意义有两点，使用一个旧的快照，不会被当前正在运行的事务阻塞，从而降低事务延迟；而从Secondary节点读取数据，则可以实现一定程度上的读写分离，扩展读性能。

GSI首先重新定义SI：

snapshot(Ti): 事务获取快照的时间
start(Ti): 事务的第一个操作
commit(Ti): 事务的提交时间
abort(Ti): 事务Abort时间
end(Ti): 事务结束时间

• D1. (GSI Read Rule) 
∀Ti,Xj such that Ri(Xj) ∈ h : 
1. Wj(Xj) ∈ h and Cj ∈ h; 
2. commit(Tj) < snapshot(Ti); 
3. ∀Tk such that Wk(Xk),Ck ∈ h : 
     [commit(Tk) < commit(Tj) or snapshot(Ti) < commit(Tk)].
• D2. (GSI Commit Rule) 
∀Ti,Tj such that Ci,Cj ∈ h : 
4. ¬(Tj impacts Ti).

这段话翻译一下，就是说：

如果事务Ti读到了Tj，说明不存在一个事务Tk，其commit(Tk)在[commit(Tj), snapshot(Ti)]之间
事务提交时，不存在两个事务的WriteSet有交集且时间有交集

基于这个定义，Generalized SI可以允许读任意的Snapshot；但实际应用中，我们总是对数据的新旧存在一些要求，因此基于GSI的定义，又衍生出Prefix-Consistent SI，即满足Prefix-Consistency的事务：

5. ∀Tk such that Wk(Xk),Ck ∈ h and Ti ∼ Tk: 
     [commit(Tk) < commit(Tj) or start(Ti) < commit(Tk)].

这里的Ti ~ Tk，意味着Ti和Tk存在先于关系，那么在[commit(Tj), start(Ti)]内就不允许有事务提交，否则就应该被事务Tj读到。换言之，事务的快照需要满足Prefix-Consistency的条件，能读到自己提交过的数据。

文章的算法相对朴素，但至少给我们带来一点启发：事务的读操作可以发到从节点，而写操作buffer在客户端，最后提交时发到主节点。相应的代价是，由于[snapshot, commit]窗口更大可能会增加abort rate。另外有意思的是，Azure CosmosDB也实现了PrefixConsistency:

Parallel SI

上面的方案中，可以将读请求offload到Secondary节点，一定程度上能够扩展读性能。那么继续将这个思路延伸一下，能不能把事务的提交也交给Secondary节点来执行呢？

这就是Parallel Snapshot Isolation的思路，在跨区域复制的场景下，业务通常会有地理位置局部性的要求，在上海的用户就近把请求发到上海的机房，在广州的用户把请求发到广州的机房；并且在实际的业务场景中，往往可以放松对一致性和隔离性的要求。Parallel放弃了Snapshot Isolation中对Commit Total Order的约束，从而实现了多点的事务提交。在通用数据库中可能很难使用这样的方案，但实际的业务场景中会很有价值。

Serializable

Snapshot Isolation所区别于Serializable的是Write Skew异常，为了解决这个异常，可以基于Snapshot Isolation进行优化，并且尽量保留Snapshot Isolation的优秀性质。

Serializable Isolation for Snapshot Database

本文发于2009年，是较为早期的对Serializable SI的研究，来自Alan D. Fekete和Michael J. Cahill的作品。

故事从串行化图理论说起，在Multi-Version的串行图中，增加一种称之为RW依赖的边，即事务T1先写了一个版本，事务T2读了这个版本，则产生RW依赖。当这个图产生环时，则违背了Serializable。

Fekete证明，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

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

之所以critique snapshot isolation，因为Basic Snapshot Isolation给人造成了一种误导：『进行写写冲突检测是必须的』。文章开篇即提出，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会认为有冲突，但WriteSI认为TXNc没有修改TXNn的ReadSet，则没有RW冲突

如何检测RW冲突：事务读写过程中维护ReadSet，提交时检查自己的ReadSet是否被其他事务修改过，over。但实际也不会这么简单，因为通常维护ReadSet的开销比WriteSet要大，且这个冲突检查如何做，难道加读锁？所以在原文中，作者只解释了中心化的WSI如何实现，至于去中心化的实现，可从Cockroach找到一点影子。

不过RW检测会带来很多好处：

只读事务不需要检测冲突，它的StartTS和CommitTS一样
只写事务不需要检测冲突，它的ReadSet为空

更重要的是，这种算法实现的隔离级别是Serializable而不是Snapshot Isolation。

总结

近年来，Snapshot Isolation围绕着Distributed、Decentralized、Replicated、Serializable这几个方向进行了很多探索，并且也围绕着实际的应用场景进行了特定的优化，例如对一致性、隔离性的放宽。较为遗憾的是，还没有看到一个Understandable的定义，更多的文章中仍然是非形式化的定义，众说纷纭。按照历史进步的轨迹，想必已经有同学在In search of understandable snapshot isolation algorithm，来解决这个纷乱的局面。

本文是今年对领域进行系统性学习的第一次文章总结，旨在通过系统视角，克服视野的局限性；后续会按照感兴趣的领域继续展开，希望在有限的职业生涯，对一个或多个领域有更深刻的认识。

参考

Berenson H, Bernstein P, Gray J, et al. A critique of ANSI SQL isolation levels[C]//ACM SIGMOD Record. ACM, 1995, 24(2): 1-10.
Yabandeh M, Gómez Ferro D. A critique of snapshot isolation[C]//Proceedings of the 7th ACM european conference on Computer Systems. ACM, 2012: 155-168.
Zhang C, De Sterck H. Hbasesi: Multi-row distributed transactions with global strong snapshot isolation on clouds[J]. Scalable Computing: Practice and Experience, 2011, 12(2): 209-226.
Peng D, Dabek F. Large-scale Incremental Processing Using Distributed Transactions and Notifications[C]//OSDI. 2010, 10: 1-15.
Bortnikov E, Hillel E, Keidar I, et al. Omid, reloaded: Scalable and highly-available transaction processing[C]//15th {USENIX} Conference on File and Storage Technologies ({FAST} 17). 2017: 167-180.
Ferro D G, Junqueira F, Kelly I, et al. Omid: Lock-free transactional support for distributed data stores[C]//2014 IEEE 30th International Conference on Data Engineering (ICDE). IEEE, 2014: 676-687.
Shacham O, Gottesman Y, Bergman A, et al. Taking omid to the clouds: fast, scalable transactions for real-time cloud analytics[J]. Proceedings of the VLDB Endowment, 2018, 11(12): 1795-1808.
Du J, Elnikety S, Zwaenepoel W. Clock-SI: Snapshot isolation for partitioned data stores using loosely synchronized clocks[C]//Reliable Distributed Systems (SRDS), 2013 IEEE 32nd International Symposium on. IEEE, 2013: 173-184.
Chairunnanda P, Daudjee K, Özsu M T. Confluxdb: multi-master replication for partitioned snapshot isolation databases[J]. Proceedings of the VLDB Endowment, 2014, 7(11): 947-958.
Cahill M J, Röhm U, Fekete A D. Serializable isolation for snapshot databases[J]. ACM Transactions on Database Systems (TODS), 2009, 34(4): 20.
Sovran Y, Power R, Aguilera M K, et al. Transactional storage for geo-replicated systems[C]//Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011: 385-400.
Elnikety S, Pedone F, Zwaenepoel W. Database replication using generalized snapshot isolation[C]//Reliable Distributed Systems, 2005. SRDS 2005. 24th IEEE Symposium on. IEEE, 2005: 73-84.