数据库内核月报

数据库内核月报 － 2019 / 02

Database · 原理介绍 · Snapshot Isolation 综述

Author: moyi

前言

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

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

本篇文章将围绕这几个问题，将时间从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的，为了不失真，这里只做一下翻译不做主观解读：

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

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

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

Distributed

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

HBase-SI

HBaseSI是完全基于HBase实现的分布式SI方案，注意到它是完全基于HBase，甚至没有其他的系统组件。

它使用了多个HBase表来完成SI的需求：

image.png image.png

协议的细节较多，简单概括一下：

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

Percolator

HBaseSI在结构上可谓十分解耦，将所有的状态都下沉到了HBase中，每个场景的需求都用不同的表来实现；但这种解耦也带来了性能损失。同在2010年提出的Percolator就做的更加工程化，将以上的诸多Table，合并成了一个。

image.png

在原来的一列数据的基础上，增加了lock、write列：

同时，作为一个分布式的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算法了。

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

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

image.png

TSO维护了几个状态：

这里的lastCommit即关键所在，表明了事务提交时不再采用和Percolator一样的先加锁再检测冲突的Pessimistic方式；而是：

另外提出了一个客户端缓存Committed的优化方案，减少到TSO的查询；在事务的start请求中，TSO会将截止到start时间点的committed事务返回给客户端，从而客户端能够直接判断一个事务是否已经提交： undefined

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

undefined

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

undefined

可以看到，中心化的分布式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的正确性包含三点：

undefined

基于这三个要求，Clock-SI提出了如下的算法：

  1. StartTS：直接从本地时钟获取
  2. Read：当目标节点的时钟小于StartTS时，进行等待，即上图中的Read Delay；当事务处于Prepared或者Committing状态时，也进行等待；等待结束之后，即可读小于StartTS的最新数据；这里的Read Delay是为了保证Consistent Snapshot
  3. CommitTS：区分出单Partition事务和分布式事务，单Partition事务可以使用本地时钟作为CommitTS直接提交；而分布式事务则选择max{PrepareTS}作为CommitTS进行2PC提交；为了保证CommitTS的全序，会在时间戳上加上节点的id，和Lamport Clock的方法一致
  4. Commit：不论是单partition还是多partition事务，都由单机引擎进行WW冲突检测

ClockSI有几点创新：

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

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

undefined

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

ConfluxDB

如果说Clock-SI还有什么不足，那可能就是依赖了物理时钟，在时钟漂移的场景下会对事务的延迟和abort rate造成影响。能否不依赖物理时钟，同时又能够实现去中心化呢？

ConfluxDB提出的方案中，仅仅依赖逻辑时钟来捕获事务的先于关系，基于先于关系来检测冲突：

ConfluxDB的这种方案不需要依赖物理时钟，不需要任何wait，甚至不需要单机的事务引擎支持读时间点快照的功能；这意味着，是不是可以基于单机的XA来实现全局一致的快照，MySQL再也不用哭了。但是这个方案的阴暗面是，可能Abort rate并不是很好，以及在执行分布式事务时的延迟问题。

Replication

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

Generalized SI

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

GSI首先重新定义SI：

• 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).

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

基于这个定义，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的约束，从而实现了多点的事务提交。在通用数据库中可能很难使用这样的方案，但实际的业务场景中会很有价值。

undefined

Serializable

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

Serializable Isolation for Snapshot Database

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

image.png

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

Fekete证明，SI产生的环中，两条RW边必然相邻，也就意味着会有一个pivot点，既有出边也有入边。那么只要检测出这个pivot点，选择其中一个事务abort掉，自然就打破了环的结构。算法的核心就在于动态检测出这个结构，因此会在每个事务记录一些状态，为了减少内存使用，使用inConflict和outConflict两个bool值来记录；在事务执行读写操作的过程中，会将与其他事务的读写依赖记录于这两个状态中。

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冲突才是根源所在。

image.png

基于RW冲突检测的思想，作者提出Write Snapshot Isolation，将之前的Snapshot Isolation命名为Read Snapshot Isolation。例如图中：

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

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

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

总结

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

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

参考