云原生分布式数据库事务隔离级别(下)

2022年01月14日 阅读数:4
这篇文章主要向大家介绍云原生分布式数据库事务隔离级别(下),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

在前文中,咱们已经介绍了事务的相关概念以及事务隔离的不一样级别,本文将着重介绍快照隔离的发展。算法

 

Part 3  快照隔离的发展

 

论文 A Critique of ANSI SQL Isolation Levels 中提出了快照隔离(Snapshot Isolation)的定义:sql

  • 事务的读操做从已提交(Committed)快照中读取数据,快照时间能够是事务的第一次读操做以前的任意时间,记为StartTimestamp;数据库

  • 事务准备提交时,获取一个CommitTimestamp,它须要比现存的StartTimestamp和CommitTimestamp都大;缓存

  • 事务提交时进行冲突检查,若是没有其余事务在[StartTS, CommitTS]区间内提交了与本身的WriteSet有交集的数据,则本事务能够提交;架构

  • 快照隔离容许事务用很旧的StartTS来执行,从而不被任何的写操做阻塞,或者读一个历史数据。并发

这里须要注意:分布式

  • 上述时间和空间没有交集的检查,主要是为了阻止LostUpdate的异常;post

  • 实现的时候一般利用锁和LastCommit Map,提交以前锁住相应的行,而后遍历本身的WriteSet,检查是否存在一行记录的LastCommit落在了本身的[StartTS, CommitTS]内;性能

  • 若是不存在冲突,就把本身的CommitTS更新到LastCommit中,并提交事务释放锁。优化

仔细考虑上述快照隔离的定义,考虑以下几个问题:

  1. CommitTS的获取:如何获得一个比现有的StartTS和CommitTS都大的时间戳,尤为是在分布式系统中;

  2. StartTS的获取:虽然上面提到的StartTS能够是一个很旧的时间,那么StartTS是否须要单调递增;

  3. 提交时进行的冲突检查是为了解决Lost Update异常,那么对于这个异常来讲,写写冲突检查是不是充分且必要的;

  4. 分布式、去中心的快照隔离级别该怎样实现。

针对上述问题,下面进行展开。这里将上述提到的快照隔离(SI)记为Basic SI。

 

分布式快照隔离

本节主要讲解HBase、Percolator以及Omid在快照隔离方面工程实践进展。

HBase

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。

HBase采用结构上解耦的方式实现分布式SI,全部的状态都存储到HBase中,每一个场景的需求都用不一样的表来实现,但这种解耦也带来了性能损失。这里将HBase实现的快照隔离记为HBaseSI。

 

Percolator

在2010年提出的Percolator在HBase的基础上更加工程化,将涉及到的多个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方案中的诸多冲突处理。这里将Percolator实现的快照隔离记为PercolatorSI。

 

Omid

Omid是Yahoo的做品,一样是基于HBaseSI,但和Percolator的Pessimistic方法相比,Omid是一种Optimistic的方式。其架构相对优雅简洁,工程化作得也不错,近几年接连在ICDE、FAST、PVLDB发表文章。

Percolator的基于Lock的方案虽然简化了事务冲突检查,可是将事务的驱动交给客户端,在客户端故障的状况下,遗留的Lock清理会影响到其余事务的执行,而且维护额外的lock和write列,显然也会增长不小的开销。而Omid这样的Optimistic方案彻底由中心节点来决定Commit与否,在事务Recovery方面会更简单;而且,Omid其实更容易适配到不一样的分布式存储系统,侵入较小。

ICDE 2014 的文章奠基Omid架构:

  • TSO(TimestampOracle):负责时间戳分配、事务提交;

  • 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事务返回给客户端,从而客户端可以直接判断一个事务是否已经提交,总体架构以下图所示。

在FAST 2017中,Omid对以前的架构进行了调整,作了一些工程上的优化:

  • commit log再也不存储于BookKeeper,而是用一张额外的HBase表存储;

  • 客户端再也不缓存committed信息,而是缓存到了数据表上;所以大部分时候,用户读数据时根据commit字段就可以判断这行数据是否已经提交了。

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

  • Commit Log再也不由TSO来写,而是offload到客户端,提升了扩展性,也下降了事务延迟;

  • 优化单行读写事务,在数据上增长一个maxVersion的内存记录,实现了单行的读写事务再也不须要进行中心节点校验。

 

去中心化快照隔离

上述都是针对分布式SI的实现,它们都有一个共同特征:保留了中心节点,或用于事务协调,或用于时间戳分配。对于大规模或者跨区域的事务系统来讲,这仍然存在风险。针对这点,就有了一系列对去中心化快照隔离的探索。

 

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冲突检测。

Clock-SI有几点创新:

  • 使用普通的物理时钟,再也不依赖中心节点分配时间戳。

  • 对单机事务引擎的侵入较小,可以基于一个单机的Snapshot Isolation数据库实现分布式的SI。

  • 区分单机事务和分布式事务,几乎不会下降单机事务的性能,分布式使用2PC进行原子性提交。

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

  • StartTS选择:可使用较旧的快照时间,从而不被并发事务阻塞;

  • 时钟漂移:虽然算法的正确性不受时钟漂移的影响,但时钟漂移会增长事务的延迟,增长abort rate;

  • Session Consistency:事务提交后将时间戳返回给客户端记为latestTS,客户端下次请求带上这个latestTS,并进行等待。

论文实验结果很突出,不过正确性论证较为简略,还有待进一步证实。

 

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,甚至不须要单机的事务引擎支持读时间点快照的功能。可是这个方案的不足是,可能Abort rate并非很好,以及在执行分布式事务时的延迟问题。

 

Generalized SI

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

 

Parallel SI

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

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

 

Serializable SI

Snapshot Isolation所区别于Serializable的是Write Skew异常,为了解决这个异常,能够基于Snapshot Isolation进行优化,而且尽可能保留Snapshot Isolation的优秀性质,进而提出了Serializable SI。

论文 Serializable isolation for snapshot databases 是 Alan D. Fekete 和 Michael J. Cahill 在2009年发表的,是早期研究SSI的理论成果。

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

在论文中做者证实,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

Yabandeh在 论文 A critique of snapshot isolation 中提出Write-Snapshot Isolation。做者首先批判Basic SI,由于Basic SI给人形成了一种误导:进行写写冲突检测是必须的。文章开篇即提出,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会认为有冲突,但Write SI认为TXNc没有修改TXNn的ReadSet,则没有RW冲突。

如何检测RW冲突:事务读写过程当中维护ReadSet,提交时检查本身的ReadSet是否被其余事务修改过。但实际也不会这么简单,由于一般维护ReadSet的开销比WriteSet要大,且这个冲突检查如何作,难道加读锁?因此在原文中,做者只解释了中心化的Write SI如何实现(BadgerDB使用了这个算法,实现了支持事务的KV引擎)。至于去中心化的实现,可从CockroachDB找到一点影子。

不过RW检测会带来不少好处:

  • 只读事务不须要检测冲突,它的StartTS和CommitTS同样;

  • 只写事务不须要检测冲突,它的ReadSet为空;

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

综合上述内容,为实现串行化,传统上只能采用基于锁的并发控制,因为性能问题,很难在实际工程中应用。Serializable SI为高性能的实现可串行化,提供了一种新的路径。

以上内容主要参考 Snapshot Isolation综述

 


 

写在最后

 

在wiki上PostgreSQL对SSI解释有这么一句话:Documentation of Serializable Snapshot Isolation (SSI) in PostgreSQL compared to plain Snapshot Isolation (SI). These correspond to the SERIALIZABLE and REPEATABLE READ transaction isolation levels, respectively, in PostgreSQL beginning with version 9.1。所以,在讨论任何一款数据库产品实现的隔离级别时,必须了解该隔离级别背后实现的算法原理。

 

参考文献

1. (https://book.douban.com/subject/26851605/)

2. (https://cs.uwaterloo.ca/~ddbook/)

3. (https://cs.uwaterloo.ca/~ddbook/)

4. (https://dl.acm.org/doi/abs/10.1145/568271.223785)

5. (https://zhuanlan.zhihu.com/p/54979396)

6. (https://zhuanlan.zhihu.com/p/37087894)

7. (https://dgraph.io/blog/post/badger-txn/)

8. (https://wiki.postgresql.org/wiki/SSI)