共计 4514 个字符,预计需要花费 12 分钟才能阅读完成。
引言
在 Paxos、Raft 这类一致性算法的形容里,常常会看到 Majority、Quorum 这两个词,在以前我认为都是表白“半数以上”的含意,最近才发现两者有不小的区别。本文介绍这两者的区别,以及在 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 零碎中,这个冗余度就是零碎内半数以上节点。因为依据抽屉原理1,当写入到至多半数以上节点时,读操作与写操作肯定有重合的节点。
然而在一个 Read-Write Quorum System 中,这个条件变的更宽泛了,在这类零碎中,只须要满足以下条件即可认为读写胜利:
$r∈R, w∈W,r∩w≠0 $
用直观的大白话来说:在 Read-Write Quorum System 中,只有读、写汇合中的任意元素有重合即可。
咱们来具体看看 Majority 和 Read-Write Quorum System 这两个零碎的区别在哪里。
首先,Majority 零碎并没有辨别读、写两类不同的汇合,因为在它的视角里,读和写操作都要到半数以上节点能力达到统一。然而在 Read-Write Quorum System 零碎里,是严格辨别了读、写汇合的,只管可能在很多时候,这两类汇合是一样的。
再次,有了后面严格辨别的读、写汇合之后,以这个视角来看分布式系统中,一个数据达成统一的大前提是“读、写操作肯定有重合的节点”,这样就能保障:写入一个数据到写汇合中,最终会被读汇合读到。在 Majority 零碎里,读、写汇合都必须是半数以上节点的要求当然可能满足这个条件,然而这个条件太强了。如果只思考读、写汇合有重合这个条件,是能够适当放宽而且还不影响零碎的一致性的。
从以上的探讨,能够失去上面的论断:
• 分布式系统中,只有读、写汇合有重合,就能保证数据的一致性了。
• Majority 零碎是对上述条件的一个强实现,然而存在比这个实现更弱一些的实现,同样能保证数据的一致性。
• 以 Read-Write Quorum System 的定义和视角来看,Majority 零碎相当于在这两方面强化了 Read-Write Quorum System 零碎的要求:
1. 读、写汇合齐全一样,
2. 且都是半数以上节点汇合的 Read-Write Quorum System。
即能够认为 Majority 零碎,只是 Read-Write Quorum System 的一个子集。
讲了这么多,来看一个非 Majoiry 的 Read-Write Quorum System,上面的汇合 {a,b,c,d,e,f} 组成的网格(grid)被划分成了横竖两个读、写汇合:
在上图中,定义了一个 Read-Write Quorum System,Q={{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 成员变更算法
理论这几个问题,在之前的博客重读 Raft 论文中的集群成员变更算法(二):实际篇 – codedump 的网络日志 [2]2 中都有提及,不过这一次因为有了新的视角,再拿进去看看。
单步成员变更的问题
假如一种场景,机房中的某个节点 a 因为各种起因须要下线,替换成同一机房中的另一个节点 d,即 a、d 节点在同机房,而 b 和 c 在另外两个机房。
这意味着节点汇合要从 {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} 之后,如果 a、d 所在的机房与另外两个机房产生了网络隔离,那么此时就选不出一个新的 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 算法的形容中(见:重读 Raft 论文中的集群成员变更算法(一):实践篇 – codedump 的网络日志3),这个算法分为两阶段提交(假如旧的节点汇合为 $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 Blog4)
能够看到,计算出来的 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 Practical5 中,作者给出了一个 Python 库 quoracle:6,专门用于评估、计算不同的读、写汇合下零碎的可用性等指标。
参考资料
• TiDB 在 Raft 成员变更上踩的坑 – OpenACID Blog7
• 后分布式时代: 多数派读写的“少数派”实现 – OpenACID Blog8
• Read-Write Quorum Systems Made Practical9
对于 Databend
Databend 是一款开源、弹性、低成本,基于对象存储也能够做实时剖析的旧式数仓。期待您的关注,一起摸索云原生数仓解决方案,打造新一代开源 Data Cloud。
- Databend 文档:https://databend.rs/
- Twitter:https://twitter.com/Datafuse_…
- Slack:https://datafusecloud.slack.com/
- Wechat:Databend
- GitHub:https://github.com/datafusela…
- https://baike.baidu.com/item/… ↩
- https://www.codedump.info/pos… ↩
- https://www.codedump.info/pos… ↩
- https://blog.openacid.com/dis… ↩
- https://mwhittaker.github.io/… ↩
- https://github.com/mwhittaker… ↩
- https://blog.openacid.com/dis… ↩
- https://blog.openacid.com/alg… ↩
- https://mwhittaker.github.io/… ↩