聊聊实现分布式事务

2016-05-19

可串行化是指多个事务并发执行的结果,能够等价于某一个串行执行结果。

多个事务访问同一个对象,可能出现依赖关系。如果事务T1先写A,事务T2再读A,那么T2依赖T1。把这些依赖关系整理出来用数据结构中的图表示,其中顶点代表事务,边代表依赖关系。比如T2依赖T1则图中有一条从T1到T2的边。这样的一张图,叫做"可串行化图"。

多个事务并行执行的history,画出可串行化图。可串行化隔离级别,等价于可串行化图中不会形成环路。

只读事务之间,是不会发生冲突的。只有读写或者写写的事务才会冲突。冲突有多种形式:读写冲突,写读冲突,写写冲突。这里分别就用RW/WR/WW表示。如果觉得“冲突”这个词用得不好,我们可以换成“不安全的并发”。

读写(RW):事务T1先于T2,但T1读到了T2写的值,而不是T2写之前的值。这是一个“读未提交”。

写读(WR):事务T1先于T2,T1写了一个值,T2读到的不是T1写的值而是更早的值。这是一个“读脏”。

写写(WW):事务T1先于T2,两个都提交后,观察到的是T1写的那个值。这个是“丢失写”。

事务实现可串行化隔离级别的核心是阻止可串行化图中出现环。


接下来的这部分,讨论的是避免可串行化图中出现环的一种实现方式。

为每个事务分配一个版本。版本用来比较事务发生的谁先谁后。注意的是属于该事务的所有操作,都是这个版本。

这里用'版本'这个词,而不是时间戳,是怕误导大家的理解。其实是同一个概念,只是时间戳很容易联想到分布式系统的物理时钟,会有“时钟漂移”的问题。如果我说“大家要把时间戳理解是逻辑上的先后,物理时钟不能用来比较先后”,说法又不太严谨。干脆用'版本'。

同一个版本内的操作跨度的物理时间可能很长,因为事务从创建到提交要完成一系列的操作,会持续一段时间。但是这个事务执行的所有的操作,我们都是用创建时的版本来比较先后。

假设事件发生的真实时序:T1创建;T2创建;T2操作;T1操作;但我们比较的时候仍然会说T1操作是先于T2操作的。因为我们比较操作的先后用的是'版本'而不是时间。所有操作发生的时间,都是操作所属事务的'版本'创建时间。这里不容易理解。 注意事务是在创建时分配版本,而不是提交时,这也是一个要澄清的点。

这个算法阻止成环的方式就是避免与"将来"发生RW/WR/WW冲突,只有单向就不会成环了。我们具体的一个一个看。

读写:把最近一次的读操作的'版本'缓存下来。执行写操都要做判断,写的版本跟最近一次读操作版本的先后关系。如果读操作的版本比当前的写操作新,那么就是检测到RW冲突了。处理冲突的方式,需要abort掉冲突事务中的一个。

写读:数据都是MVCC的,每次写操作不会覆盖数据而是加一个版本。读操作总是读到版本时间小于它的最后一次写。

写写:写数据时遇到版本比自己更新的写操作,则意味着检测到了写写冲突。解决方式仍然是abort掉其中一个。

通过避免与“将来”发生RW/WR/WW冲突,来破坏可串行化图成环的条件。


上面的讨论只是在满足一个假设的条件下是成立的。其实忽略了一个场景,即事务不一定都会提交。

我们看写读。上面说读操作要读版本早于自己的最后一次写,这个说法有问题。分两种情况:

  1. 我们读了最后一次写数据,但是这个写操作的事务最后abort掉,写并没提交,那我们就读未提交了。
  2. 我们不要读最后一次写数据,而是读更早的已提交数据。但是最后一次写操作的事务成功了,那我们就读脏了。

这两种情况意味着,最后一次写数据我们读或者不读,都不行。因为现在还无法确定它将来会commit还是abort。怎么办呢?两种办法。一种是等!等写的结果出来,能确认最终状态了,就可以知道应该读到什么数据。另一种是不等,那就是abort掉冲突两者中的一个了。这分别是悲观和乐观的并发控制。

这里我们采用的方式是不等,abort掉了重启事务。读操作总是读最后一个已提交的值。如果发现有未提交的写,并且版本在这次读操作之前,则abort掉一个。写操作也是类似的,只允许覆盖已提交的数据,如果遇到尚未提交的写,则要处理冲突。

冲突的时候,具体的abort哪一个事务会用一个算法,加入一定随机性,并且被abort多次以后它不被abort的概率应该升高,这样保证事务不会永远执行不成功。

冲突有时不可避免,简单版本算法我们会abort冲突事务


级联的abort在这里应该是不会遇到,因为有多版本不会依赖未提交的写。前面说了可串行化的关键是无环,说了一个如何避免成环的算法以及如何处理冲突,接下来说一点实现相关的东西。

首先是事务状态。每个事务开始时都会建一个自己的记录,维护当前事务的状态。事务的状态可能是PENDING的,COMMIT或者ABORT的。PENDING是进行中的事务,后面两种是结束的事务。这个状态变量是一个最小粒度的记录,底层可以用raft之类的协议来保证一致性,做一个原子的提交。其实这个动作就是两阶段提交,第二阶段的提交操作:原子地改一个事务的记录状态,从PENDING到COMMIT,当然也可以是ABORT。

那前面从创建事务记录,到事务的各种操作,只要是不冲突都是可以进行下去的。这些过程其实就是两阶段提交的第一阶段,准备阶段。由于所有的写操作都是带版本的写,而不会覆盖原数据,事务之间是不会相互影响的。提交失败的也不需要专门做回滚,那些ABORT的事务制造的数据,周期性地做清理就行了。

对于OLTL类的数据库,可以让写不影响读,读总是读到最后一次已提交的版本,写事务在最后提交时刻如果检测到冲突就ABORT掉,读的吞吐就可以很高。

事务状态是用来做两阶段提交的,知识一定不要学得太死,提交仅仅就是改一个状态而已,两阶段提交也并不意味着吞吐低。

接下来是写意向(write intent)。事务去写一个数据时,不是直接的修改,是留下一个写的意向。意向要留在数据上面,并且有事务自己版本信息(其实就是多版本的概念)。这样子,当其它事务读或者写操作,遇到这个意向,它就知道有事务也正在操作相同的数据,需要避免冲突。

再澄清的概念是关于锁。锁是一个概念上的东西,大致就是用来对某个受保护东西提供排它性访问。如果从这个角度,我们可以说目前的读写操作都是无锁的。但是呢,当一个事务操作执行时遇到数据上存在写意向,那它面临着操作冲突。前面说过了解决冲突,一种是等,另一种是abort事务。如果采用的是等,那是不是又等价于锁的概念了呢?等价于“这个资源被锁保护了,我需要等待锁被释放”。如果是abort,大家可以类比CAS的概念,不断重试直到不发生冲突,这又是无锁了。所以说,锁是一个概念上的东西,知识不要学得太死。


然后讨论时间。

前面说过了,每个事务都要分配一个'版本',版本其实是时间戳。分布式系统里面,各台机器之前的时钟是无法保证同步的,因此无法直接使用本地时钟。

一种方式是timestap oracle。其实就是用中心化的时钟服务器来分配版本。当然有它不好的地方,单点问题和性能问题。好的地方就是容易理解。前文部分说的都是说的用中心化的时间做版本,应该很好看懂。

在之前的基础上,我们想优化两个点:一个是只读事务永不阻塞;另一个是去掉中心化时钟。

先说如何让只读事务不被阻塞。前面假定的是事务在创建的时候会分配一个时间戳(之前用的'版本',从现在开始可以用时间戳这个词了),用它来比较操作的先后。这个时间戳一旦分配了就不会变。现在我们去掉这个限制,即,事务分配的时间戳是可以变的。现在我们先假设机器之间时钟是一致的,然后我们可以使用本地时钟了。

前面说写读冲突,当读操作发现在它之前有未提交写就是冲突了,解决冲突有两种,一种是等,另一种是abort。当时我们说的是采用abort。去掉事务时间戳不可变的限制以后,我们有了另一种处理办法:把冲突的写操作的那个事务时间戳往后推。这其实是等的一种变种,不过不是让读操作等写操作提交,而是读操作不阻塞,推迟写操作。

理解'把事务的时间戳往后推'特别关键,这句话好好读几遍。可串行化要求的是和某一种串行执行的顺序等价,至于和哪一种等价我们并不介意。一个包含写操作的事务可能由于时间戳被推过很多次,推过之后顺序就跟创建事务时变了,不过没关系。如果事务T1读到了T2写的值,那么T1的时间戳肯定是大于T2的,即使T1事务其实先于T2启动:可能是这种情况,T1启动,T2启动,T2写操作,T1发现T2已写但尚未提交的数据,于是把T2的事务时间戳推后。

可以把事务时间戳往后推之后,我们达到了这种效果:读操作永不阻塞,也不会因为跟写操作冲突而被abort。写可能需要等待读,或者被abort。事务的提交时间戳将是被推多次后最终那个时间戳。我们完成了第一个优化,只读事务不阻塞。接着再看第二个优化,机器之间时钟其实是有漂移的时候,如何使用本地时钟。

Google的TrueTime,这是个很屌东西,它就是用本地机器上的物理时钟来比较时序。能这么做是因为它用硬件保证了,各机器之间的误差在一个上限,大概是前后7ms的样子。有了这个保证之后,比如说我们看到一个事务A的时间戳比事务B小了7ms以上,那事务A肯定是比B先的。再比如说读事务遇到了冲突的写,我们将写的那个事务时间戳推到未来的7ms之后,它就肯定是在读后面了。算法上其实用NTP也能做,但是NTP的时间误差上限保证不了,或者说为了处理时间戳先后问题要等几百毫秒,那性能就不可接受了。

我们看一看可以推事务的时间戳,使用本地时钟以后,现在RW/WR/WW冲突是怎么样的。

  • 读操作遇到了写的时间戳在遥远的将来,可安全地读,无冲突。
  • 读操作遇到了写在较近的将来,这种情况要小心,因为考虑到时钟漂移,写操作可能其实已经发生了。所以只好abort掉这个写事务了。
  • 读操作遇到写,时间戳在过去。我们需要查事务的状态,如果是已提交,那么就读到这个值。如果是未提交,那么可以把这个写的时间戳往后推。
  • 写遇到未提交的写,那肯定是冲突,要abort掉其中一个的。
  • 写遇到已提交的写,并且对方时间戳比自己新。abort自己,重启。
  • 写遇到了时间戳在将来的读,把自己推到读时间戳之后。

还有一个问题是如何为只读事务选取一个时间戳。我们需要读的时间戳,大于所有已提交的包含写的事务的时间戳,这样才能保证读到一个安全的快照。那么会遇到一个问题是读需要等待,等待到真实时间走到比已知的最大时间戳大7ms。

我们不想让读等待,有一种变通的处理办法是推后写事务的提交时间,即本来写已经完成了并提交了,但是会推迟一点点才释放锁。亦是指本来事务完成的时间是T,但是记录事务的完成时间戳会是T+7ms,这样就可以消除时钟漂移的影响,读可以直接用本地时间读不用等待。

以上就是去掉了中心化的时钟,允许推事务时间戳以后的算法,实现了只读事务不阻塞。


最后是本文的总结。本文是关于分布式事务的实现,其实是Google的Spanner那一套。从简单的可串行化开始,接着用预先分配事务时间戳的算法来帮助理解,然后去掉中心化时钟的限制,讲了一个读不阻塞的可串行化的分布式事务。

  • 事务实现可串行化隔离级别的核心是阻止可串行化图中出现环
  • 通过避免与“将来”发生RW/WR/WW冲突,来破坏可串行化图成环的条件
  • 冲突有时不可避免,简单版本算法我们会abort冲突事务
  • 复杂版去掉了中心化的时钟,允许推事务时间戳以后,实现了只读事务不阻塞
transaction分布式spanner可串行化