两阶段提交详解

​ 要了解分布式事务的实现,首先要了解单机事务的实现;要了解两阶段提交,首先应该了解单机原子性提交。化繁就简,天之道也。

单机原子提交的实现

数据库中,原子提交一般都是由存储引擎实现的。例如一个客户向一个数据库提交一个事务时,数据库首先把该事务写入write-ahead log(WAL, 即常说的redo log); 然后更新状态机(例如MySQL中,即更新B+树); 更新状态机成功后写提交日志 commit log。只有完成了写commit log, 这个事务才算真正完成。如果在更新状态机时,机器突然宕机, 在该机器宕机重启时,会读取commit log和write-ahead log,回滚未完成的事务,恢复数据库到该事务执行前的一致性状态。

简单总结一下,一个事务在数据库上执行的过程主要是:

写redo log $\longrightarrow$执行状态机(例如:更新B+树) $\longrightarrow$写commit log

并发控制

加锁

对于并发事务请求,最简单的控制方式便是加锁了。 锁分为读锁和写锁,同一个元素一般可以加多个读锁,但是只能加一个写锁,而且写事务将会阻塞读事务。 这里所说的元素可以是一行,一个数据块,也可以是一个表。例如如果事务只操作某一行的数据,可以对这一行加行锁;如果事务处理多行数据,则需要锁住整个这些行的范围。

写时拷贝(copy-on-write)

image-20190728180021109

加锁控制并发事务,会影响数据库的读取性能。因为读事务需要等待写事务完成,写锁释放后,才能成功添加读锁,进行数据读取。 一般的在线服务,读取次数明显高于写入次数。使用写时拷贝(Copy-On-Write)技术,能极大的提高读取性能。

如上图所示,使用写时拷贝技术对B+树进行写操作的步骤如下:

  1. 拷贝: 将所要变更的节点所在的路径,从叶子节点到根路径上的所有节点拷贝一份出来。

  2. 修改: 在拷贝出的节点上执行相应的写操作(变更操作)。

  3. 提交:原子性的切换根节点的指针,使得它指向新的节点。

    Note: 对于存在节点合并和分裂的情况,方法和上面的方法类似,只是受影响的节点可能不再只是一条路径,而是一个子树。

如果读取操作发生在上面第3步之前,那么该读操作将从旧节点上读取数据;如果读取操作发生在上面的第3步提交之后,该读取请求将从新节点上读取到数据。另外,写时拷贝技术还涉及到引用计数,对于每个节点都维护了一个引用计数,表示被多少请求所引用,如果引用计数为0,说明已经没有请求在读取旧节点,此时这些旧节点可以被垃圾回收。

写时复制技术原理也很简单,但问题是每次写操作都需要拷贝从叶子节点到根节点路径上的所有节点(涉及节点分裂和合并时会更多),拷贝的开销比较高。另外,多个写操作之间仍然是互斥的,需要顺序串行执行。

多版本并发控制(MVCC, Multi-Version Concurrency Control)

和写时拷贝技术一样,MVCC也能够实现读事务无需加锁。MVCC技术可以对每行数据维护多个版本,一个读事务可能读取某个版本(相当于快照),无论这个读取事务有多长,MVCC总是能够提供与该读取事务开始时刻一致的数据。

MySQL的InnoDB存储引擎为每一行数据维护了两个隐含的列,其中一列存储行被修改的逻辑时间, 另外一列存储行被删除的逻辑时间,注意,这里所说的逻辑时间并不是真实的时间戳,而是事务ID。每当一个事务开始时,InnoDB都会给该事务分配一个递增的事务ID。 对于针对每一行的查询语句,InnoDB都会比较查询语句的事务ID,与这一行的事务ID(修改ID,删除ID)分别进行比较,然后结合不同的事务隔离级别,决定是否返回这一行的数据。分别以SELECT, DELETE, INSERT,UPDATE为例进行具体说明:

  1. SELECT: 对于SELECT语句,只有同时满足以下两个条件,才能返回。 (1) 行的修改ID小于该SELECT事务ID。(2) 行的删除ID要么不存在,要么大于该SELECT事务ID。(可重复读隔离级别)
  2. INSERT: 插入数据时,把该行的修改ID更新为该INSERT事务ID。
  3. DELETE:删除行时,把改行的删除ID置为该DELETE事务ID,即标记删除了改行,而并没有真正的物理删除。
  4. UPDATE: 更新一行数据时,InnoDB会先把原来的行复制一份,并且把该UPDATE的事务ID设置为该行数据(复制的行)的修改ID。

MVCC在读取数据时无需加锁,每个查询事务都会通过事务ID的检查,获取到所需要的数据版本,因此并发度大大提高。当然,为了实现多版本,必须对每一行数据存储的多版本相关的数据,这会增加一些磁盘开销。此外,MVCC存储引擎,还需要定期删除不再需要的版本,从而及时回收磁盘空间。

两阶段提交

单机原子性提交,只能针对一个节点。 当同一个事务,要在两台或多台机器上保持原子性,一致性时(即要么每个节点都执行成功,要么每个节点都失败回滚),最常用的方式就是两阶段提交。

上面已经描述了单机原子提交的过程: 写redo log $\longrightarrow$执行状态机(例如:更新B+树) $\longrightarrow$写commit log。 两阶段提交,顾名思义,就是把提交分成两个阶段: <1>. 协调者询问每个参与者(数据库节点),是否可以提交(数据库一旦回复可以提交,这个承诺就必须兑现)。 <2>. 协调者根据所有参与者的回答,做出决定,即只有全部参与者都回复(承诺)可以提交时,协调者才决定提交。即使只有一个参与者回复不能提交,协调者也要发送回滚请求给所有参与者,回滚事务。

image-20190728234719508

如上图所示,两阶段提交是把提交过程分成了prepare和commit两个阶段。两阶段提交中有两种角色,一种是协调者,一种是参与者。协调者通常被实现成函数库,和参与者运行在同一应用进程中,当然也可以是单独的节点。

两阶段提交的整个流程如下:

  1. 当一个请求到达,开始一个分布式事务时,协调者会为该事务生成一个全局唯一的事务ID。
  2. 然后协调者把该事务写入redo log, 发送该事务给每个参与者,每个参与者接收到该事务后在本地执行该事务:写入redo log,执行状态机。如果此时,由于网络中断,超时,或者某个参与者宕机,此时协调者可以决定中止该事务,回滚该事务。
  3. 如果上面的步骤执行顺利,此时就开始了两阶段提交阶段。协调者询问每个参与者,是否可以提交该事务(即写commit log), 如果此时调用超时,或者某个参与者宕机,或者回复不能提交,协调者向所有参与者发生中止该事务的消息,回滚该事务。
  4. 参与者接到协调者的询问(prepare)请求时,需要检查本地资源是否一定能够提交该事务,一旦给出可以提交的承诺,在任何情况下都得保证提交能成功执行。不管遇到机器宕机,磁盘不够用,掉电等任何情况。一旦给出承诺,就不能反悔。
  5. 当协调者收到所有参与者的回复之后,协调者根据参与者的回复做出决定,决定是否提交该事务(只有所有参与者都给出肯定的承诺,才会决定提交该事务)。此时,协调者必须把这个决定写入磁盘,以防协作者宕机,写磁盘的这个时间点叫做提交点(commit point)
  6. 当协调者把决定写入磁盘后 , 他发送提交或者中止请求给每个参与者。参与者接收到协调者发送的提交请求后,提交该事务(写入commit log),回复协调者提交成功。如果在接收到协调者的提交请求之前,有参与者宕机,或者网络中断。此时,协调者会一直重传提交请求给该参与者,直到该参与者恢复正常,提交该事务后给协调者回复提交成功。

如果协调者宕机,由于协调者在宕机之前已经把决定写入了本地磁盘,因此协调者恢复时,能恢复出当时所做的决定。然后给每个参与者发送该决定。在协调者宕机期间,参与者唯一能做的就是等待协调者恢复。如果协调者在把决定写入磁盘之前宕机(即commit point之前),当协调者恢复时,发送中止该事务的请求给所有参与者,回滚该事务,因此commit point是一个很关键的时间点。当所有参与者都回复提交成功后,协调者完成该该事务的提交,写commit log。

由上面的描述很容易可以看出,两阶段提交虽然实现了事务的分布式原子性和一致性,但是即使是只有一台机器宕机,不论是协调者还是参与者,整个两阶段提交的过程都会被阻塞住,直到宕机的机器恢复为止。因此,两阶段提交虽然保证了一致性,但是可用性并不好。

其实很多时候我们也不是非得在每个节点上都成功执行事务,保证每个节点的一致性。往往,我们只需要大多数节点保持一致性就好了,也就是说大部分的节点能提交成功就行了。例如五个参与者,有三个参与者承诺可以提交事务,我们就认为可以提交事务了。这就逐渐引申出了两个著名的分布式共识协议: raft协议和paxos协议。