周刊(第14期):重读Raft论文中的集群成员变更算法(二):实践篇

2022-05-07
6分钟阅读时长

引言:以前阅读Raft大论文的时候,对“集群变更”这部分内容似懂非懂。于是最近又重读了大论文这部分的内容,以下是重读时做的一些记录。这部分内容打算分为两篇文章,上篇讲解成员变更流程的理论基础,下篇讲解实践中存在的问题。


重读Raft论文中的集群成员变更算法(二):实践篇

单步成员变更存在的问题

正确性问题

单步变更成员时,可能出现正确性问题。如下面的例子所示,最开始时,系统的成员是{a,b,c,d}这四个节点的集合,要将节点uv加入集群,按照单步变更成员的做法,依次会经历:{a,b,c,d}->{a,b,c,d,u}->{a,b,c,d,u,v}的变化,每次将一个节点加入到集群里。

上面的步骤看起来很美好,但是考虑下面的例子,在变更过程中leader节点发生了变化的情况:

C₀ = {a, b, c, d}
Cᵤ = C₁ ∪ {u}
Cᵥ = C₁ ∪ {v}

Lᵢ: Leader in term `i`
Fᵢ: Follower in term `i`
☒ : crash

    |
 u  |         Cᵤ                  F₂  Cᵤ
--- | ----------------------------------
 a  | C₀  L₀  Cᵤ  ☒               L₂  Cᵤ
 b  | C₀  F₀          F₁          F₂  Cᵤ
 c  | C₀  F₀          F₁  Cᵥ          Cᵤ
 d  | C₀              L₁  Cᵥ  ☒       Cᵤ
--- | ----------------------------------
 v  |                     Cᵥ                  time
    +-------------------------------------------->
          t₁  t₂  t₃  t₄  t₅  t₆  t₇  t₈

(引用自TiDB 在 Raft 成员变更上踩的坑 - OpenACID Blog

上面的流程中,纵坐标是集群中的节点,横坐标是不同的时间(注意不是任期),Li表示在任期i时候的leader节点,Fi表示在任期i时候的follower节点。

上图的流程阐述如下:

  • t1:a节点被选为任期0的leader,而b、c节点为follower。
  • t2:将节点u加入集群,但是这条加入集群的日志,仅达到了a和u节点,由于这条日志并没有半数以上通过,所以这时候节点u还并未成功加入集群。
  • t3:节点a宕机。
  • t4:由于原先的leader宕机,于是集群需要选出新的leader,选出来的新leader是节点d,这是任期1时候的leader。
  • t5:节点v加入集群,加入集群的日志,到达了节点c、d、v上面,可以看到由于这条日志到了此时集群的半数以上节点上(因为这时候节点a宕机,因此只有三个节点在服务,于是只有有2个节点同意就认为可被提交),所以实际是已经提交的,即v加入集群的操作是成功的。
  • t6:leader d宕机。
  • t7:宕机的节点a恢复服务,看到本地有将节点u加入到集群的日志,于是它认为节点u、b是这个任期的follower节点。
  • t8:此时节点d恢复服务,而leader a将之前把节点u加入集群的日志同步给当前集群的所有节点,这造成了之前v加入集群且已被提交的日志丢失。

出现这个问题,本质是因为:上一任leader的变更日志,还未同步到集群半数以上节点就宕机,这时候新一任leader就进行成员变更,这样导致了形成两个不同的集群,产生脑裂将已经提交的日志被覆盖。

Raft作者在bug in single-server membership changes描述了这一现象。

解决的办法也很简单:即每次新当选的leader不允许直接提交在它本地的日志,而必须先提交一个no-op日志,才能开始同步。这个问题的描述,在之前的博客有描述:为什么Raft协议不能提交之前任期的日志? - codedump的网络日志

可用性问题

除了以上正确性问题,单步变更还有可能出现可用性问题:当需要替换的节点在同一机房的时候,如果这个机房网络与集群中其他机房的网络断开,就会导致无法选出leader,以致于集群无法提供服务。来看下面的例子。

availability

在上图中,原先集群中有三个节点分别位于三个机房:机房1的节点a、机房2的节点b、机房3的节点c。现在由于各种原因,想把机房1的节点a下线,换成同机房的节点d到集群中继续服务。

可以看到,这个替换操作涉及到一个节点的加入和一个节点的离开,可能有如下两种可能的步骤:

  • 先加入新节点d再删除节点a:{a,b,c}->{a,b,c,d}->{b,c,d}
  • 先删除节点a再加入新节点d:{a,b,c}->{b,c}->{b,c,d}

两种步骤各有优劣,第二种方案的问题是:中间只有两个节点在服务,一旦这时候又发生宕机,则集群就不可用了。

第一种方案中,按照上图中的例子,如果正好要替换的a、d节点都位于同一个机房里面,那么假如这个机房的网络也与其它机房隔离,那么只有两个节点在服务,这时候在四节点(中间步骤)的条件下也无法服务。

以上是单步变更中可能出现的两类问题。可以看到,尽管单步变更算法看起来实现简单,但是实则有很多细节需要注意。虽然Raft论文中认为单步变更是更简单的办法,但是现在主流的实现都使用了Joint Consensus(联合共识)算法。

Joint Consensus算法如何解决可用性问题

针对上面提到的:替换同一机房中的不同节点,中间过程中可能由于这个机房被网络隔离,导致的集群不可用(选不出leader)问题,来看看Joint Consensus算法是如何解决的。

先来回顾一下步骤,如果使用Joint Consensus算法,需要经历两阶段提交:

  • 首先提交C_Old$\bigcup$ C_New
  • 然后提交C_New

把集合换成这里的例子,就是:

  • 首先提交{a,b,c} $\bigcup$ {a,b,c,d}
  • 然后提交 {a,b,c,d}

来看这两阶段中可能出现宕机的情况:

  • 第一阶段时leader节点宕机,这个leader节点只有可能是两种情况,其集群配置还是C_Old,或者已经收到了C_Old$\bigcup$ C_New
    • C_Old:由于这时候这个leader并没有第一阶段提交的C_Old$\bigcup$ C_New节点集合变更,因此那些已有C_Old$\bigcup$ C_New节点集合的follower这部分的日志将被截断,成员变更失败,回退回C_Old集合。
    • C_Old$\bigcup$ C_New:这意味这个leader已经有第一阶段提交的C_Old$\bigcup$ C_New节点集合变更,可以继续将未完成的成员变更流程走完。

类似的,在第二阶段时leader节点宕机,也不会导致选不出leader的情况,可以类似推导。

可见:直接使用Joint Consensus算法并不会存在单步变更时的可用性问题。

总结

  • Raft集群的单步变更算法,虽然看起来”简单“,但是实践起来有不少细节需要注意。
  • 虽然论文里提到单步变更算法比之Joint Consensus算法更为简单,很多开源的Raft实现都已经以Joint Consensus算法做为默认的实现了。

(之前写过etcd 3.5版本的实现解析,见:etcd 3.5版本的joint consensus实现解析 - codedump的网络日志

参考资料

邮件订阅

微信公众号

wechat-account-qrcode