周刊(第17期):Read-Write Quorum System及在Raft中的实践

2022-05-28
8分钟阅读时长

引言:在Paxos、Raft这类一致性算法的描述里,经常会看到MajorityQuorum这两个词,在以前我以为都是表达“半数以上”的含义,最近才发现两者有不小的区别。本文介绍这两者的区别,以及在Raft中实践中的问题。有了Quorum的视角,能更好得理解一致性算法。


Read-Write Quorum System

首先来在数学上给出Read-Write Quorum System的定义。

一个Read-Write Quorum System(读写法定系统)是两个集合组成的元组,即Q=(R,W),其中:

  • 集合R被称为Read Quorum(读法定集合),即可以认为读操作都是读的集合R中的元素;

  • 集合W被称为Write Quorum(写法定集合),即可以认为写操作都是写入到集合W中的元素。

  • $r∈R, w∈W,r∩w≠0 $,即任从读集合中取一个成员r,以及任从写集合中取一个成员w,这两个集合一定有交集。

都知道在分布式系统中,一个写入操作要达成一致,读写操作一定要有一定的冗余度,即:

  • 写入多份数据成功才能认为写入成功,
  • 从多个节点读到同一份数据才认为读取成功。

Majority系统中,这个冗余度就是系统内半数以上节点。因为根据抽屉原理,当写入到至少半数以上节点时,读操作与写操作一定有重合的节点。

但是在一个Read-Write Quorum System中,这个条件变的更宽泛了,在这类系统中,只需要满足以下条件即可认为读写成功:

$r∈R, w∈W,r∩w≠0 $

用直观的大白话来说:在Read-Write Quorum System中,只要读、写集合中的任意元素有重合即可。

我们来详细看看MajorityRead-Write Quorum System这两个系统的区别在哪里。

首先,Majority系统并没有区分读、写两类不同的集合,因为在它的视角里,读和写操作都要到半数以上节点才能达到一致。但是在Read-Write Quorum System系统里,是严格区分了读、写集合的,尽管可能在很多时候,这两类集合是一样的。

再次,有了前面严格区分的读、写集合之后,以这个视角来看分布式系统中,一个数据达成一致的大前提是“读、写操作一定有重合的节点”,这样就能保证:写入一个数据到写集合中,最终会被读集合读到。在Majority系统里,读、写集合都必须是半数以上节点的要求当然能够满足这个条件,但是这个条件太了。如果只考虑读、写集合有重合这个条件,是可以适当放宽而且还不影响系统的一致性的。

从以上的讨论,可以得到下面的结论:

  • 分布式系统中,只要读、写集合有重合,就能保证数据的一致性了。
  • Majority系统是对上述条件的一个强实现,但是存在比这个实现更弱一些的实现,同样能保证数据的一致性。
  • Read-Write Quorum System的定义和视角来看,Majority系统相当于在这两方面强化了Read-Write Quorum System系统的要求:
    • 读、写集合完全一样,
    • 且都是半数以上节点集合的Read-Write Quorum System

即可以认为Majority系统,只是Read-Write Quorum System的一个子集。

quorum

讲了这么多,来看一个非MajoiryRead-Write Quorum System,下面的集合{a,b,c,d,e,f}组成的网格(grid)被划分成了横竖两个读、写集合:

grid

在上图中,定义了一个Read-Write Quorum SystemQ={{abc}∪{def},{ab}∪{bc}∪{ac}},其中:

  • 读集合为{abc}∪{def},即横着的两个集合{abc}{def}组成了读集合。
  • 写集合为{ab}∪{bc}∪{ac},即竖着的三个集合{ab}{bc}{ac}组成了写集合。

显然这个划分是能够满足前面的条件:$r∈R, w∈W,r∩w≠0 $ 的,因为任选一个读集合中的集合如{abc},写集合中任选的一个集合如{bc},这两个集合中的元素都会有重合。

假设是这样构成的一个分布式系统,那么写操作只需要写入写集合中的任意一个集合即可认为成功,可以看到一个写集合最小可以只有两个节点构成,这个数量是小于Majority的。

有了对Read-Write Quorum System系统及与Majority的区分和联系,以这个视角来看看raft的成员变更算法。

Read-Write Quorum视角下的Raft成员变更算法

实际这几个问题,在之前的博客周刊(第14期):重读Raft论文中的集群成员变更算法(二):实践篇 - codedump的网络日志中都有提及,不过这一次因为有了新的视角,再拿出来看看。

单步成员变更的问题

假设一种场景,机房中的某个节点a由于各种原因需要下线,替换成同一机房中的另一个节点d,即ad节点在同机房,而bc在另外两个机房。

availability

这意味着节点集合要从{a,b,c}变为{b,c,d},根据Raft的单步成员变更算法,要经历如下两次单步变更:

  • 加入节点d,即从{a,b,c}变成{a,b,c,d}
  • 删除节点a,即从{a,b,c,d}变成{b,c,d}

假设当集群变为{a,b,c,d}之后,如果ad所在的机房与另外两个机房发生了网络隔离,那么此时就选不出一个新的leader,写入数据也不能达成一致了。个中原因,是因为在这种情况下,以Majority的视角看来,无论读、写都没法满足“半数以上”这个条件了。

如果换成前面的Read-Write Quorum视角,将系统重新定义一个新的读和写quorum集合,如下:

  • 读 quorum 集合:仍然保持之前的Majority集合,即认为要读到半数以上节点才能认为是读成功。
  • 写 quorum 集合:在之前的Majority集合之外,再加入由{b,c}两个节点组成的集合。

即对于这个新的Read-Write Quorum System而言,以最开始的数学定义来看:

Q(R,W) = Q(M(Q), M(Q) ∪ {b,c})。

其中M(Q)为取集合Q的半数以上的节点集合,以{a,b,c,d}组成的集合来说,M(Q)={{a,b,c},{a,c,d},{b,c,d},{a,b,c,d}}

显然,这里的读quorum集合和写quorum集合,是可以满足之前的条件的,即: $r∈R, w∈W,r∩w≠0 $ ,这是因为 $M(Q)∩{b,c}≠0 $ 。

对于这个改造后的系统,可以认为:

  • 读操作,仍然需要读到集群中至少半数以上的节点才能算读成功。
  • 写操作,只要写入{b,c}(由于{b,c}已经包含在半数以上节点中,这里就不单独强调写半数以上节点这个条件了)就可以认为写成功了。

这样改造之后,即便系统出现了前面的机房隔离问题,也没有问题。

Read-Write Quorum视角下的joint consensus算法

与单步成员变更不同的是,joint consensus算法允许一次提交多个节点的变化,在之前对joint consensus算法的描述中(见:周刊(第13期):重读Raft论文中的集群成员变更算法(一):理论篇 - codedump的网络日志),这个算法分为两阶段提交(假设旧的节点集合为$C_Old$,而新的节点集合为$C_New$):

  • 首先提交一个$C_Old ∪ C_New$的配置。
  • 如果上述配置提交成功,再提交一个$C_New$的配置。

在上面的例子中,$C_Old = {a,b,c}$,而$C_New = {b,c,d}$。

Read-Write Quorum的视角下来看看为什么joint consensus算法可以很好的工作,而不用像单步成员变更算法那样担心网络隔离导致的问题。来计算一下集合${a,b,c} ∪ {b,c,d}$的Majority值:

M(abc) x M(bcd) = {
    ab ∪ bc,
    ab ∪ cd,
    ab ∪ bd,
    bc ∪ bc,
    bc ∪ cd,
    bc ∪ bd,
    ac ∪ bc,
    ac ∪ cd,
    ac ∪ bd,
} = {
    abc,
    abcd,
    abd,
    acd,
    bc,
    bcd,
} = {M(a,b,c,d),{b,c}}

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

可以看到,计算出来的Majority集合刚好就是前面提到的M(a,b,c,d)∪ {b,c}

换言之,从数学角度来看,以上证明了joint consensus算法即便在网络隔离的条件下,以Majority的条件来要求这个算法,也是能很好的工作的。这也就是为什么这个算法会比单步变更算法更为健壮的数学依据。

quorum改造的启示

从以上的分析来看,从Read-Write Quorum视角来看,写Quorum集合Majority视角下的W(Q)=M(Q)={{a,b,c},{a,c,d},{b,c,d},{a,b,c,d}},扩展为W(Q)=M(Q)∪{b,c}来提升系统的可用性。

未来,是不是可以针对Raft的写操作,都能这样改造写Quorum集合,这会是一个有意思的方向,我还没有对这个方向思考的更多,先把问题放在这里:)

在论文Read-Write Quorum Systems Made Practical 中,作者给出了一个Python库quoracle:,专门用于评估、计算不同的读、写集合下系统的可用性等指标。

参考资料