数据库内核月报 - 2019 / 02

Database · 原理介绍 · Snapshot Isolation 综述

前言

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,它需要比现存的StartTimestampCommitTimestamp都大
  • 事务提交时进行冲突检查,如果没有其他事务在[StartTS, CommitTS]区间内提交了与自己的WriteSet有交集的数据,则本事务可以提交;这里阻止了Lost Update异常
  • SI允许事务用很旧的StartTS来执行,从而不被任何的写操作阻塞,或者读一个历史数据;当然,如果用一个很旧的CommitTS提交,大概率是会Abort的

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

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

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

  • CommitTS的获取,如何得到一个比现有的StartTSCommitTS都大的时间戳;尤其是在分布式系统中,生成一个全局单调递增的时间戳显然会是一个单点
  • 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:实际存储数据

image.png image.png

协议的细节较多,简单概括一下:

  • 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,合并成了一个。

image.png

在原来的一列数据的基础上,增加了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存储实际数据,也可适配到其他的分布式存储系统

image.png

TSO维护了几个状态:

  • 时间戳:单调递增的时间戳用于SI的StartTSCommitTS
  • 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事务返回给客户端,从而客户端能够直接判断一个事务是否已经提交: undefined

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

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

undefined

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

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

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的正确性包含三点:

  • Consistent Snapshot:所谓Consistent,即快照包含且仅包含Commit先于SnapshotTS的所有事务
  • Commit Total Order:所有事务提交构成一个全序关系,每次提交都会生成一个快照,由CommitTS标识
  • Write-Write Conflict: 事务Ti和Tj有冲突,即它们WriteSet有交集,且[SnapshotTS, CommitTS]有交集

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有几点创新:

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

在工程实现中,还需考虑这几个问题:

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

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

undefined

不过较为遗憾的是,此文对正确性的证明较为简略,后续笔者会对此算法进行详细分析。如果正确性得到保证,不出意外的话这几年会涌现出不少基于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的约束,从而实现了多点的事务提交。在通用数据库中可能很难使用这样的方案,但实际的业务场景中会很有价值。

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掉,自然就打破了环的结构。算法的核心就在于动态检测出这个结构,因此会在每个事务记录一些状态,为了减少内存使用,使用inConflictoutConflict两个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冲突才是根源所在。

image.png

基于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.