但是在一个 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 系统的要求:
• 读、写集合完全一样,• 且都是半数以上节点集合的 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的成员变更算法。
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}}
从以上的分析来看,从 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 [5] 中,作者给出了一个 Python 库 quoracle:[6],专门用于评估、计算不同的读、写集合下系统的可用性等指标。
参考资料
参考资料
• TiDB 在 Raft 成员变更上踩的坑 - OpenACID Blog[7]
• 后分布式时代: 多数派读写的’少数派’实现 - OpenACID Blog[8]
• Read-Write Quorum Systems Made Practical [9]
引用链接
引用链接
[1]抽屉原理: https://baike.baidu.com/item/%E6%8A%BD%E5%B1%89%E5%8E%9F%E7%90%86/233776 [2]重读Raft论文中的集群成员变更算法(二):实践篇 - codedump的网络日志: https://www.codedump.info/post/20220507-weekly-14/ [3]重读Raft论文中的集群成员变更算法(一):理论篇 - codedump的网络日志: https://www.codedump.info/post/20220417-weekly-13/#%E4%B8%80%E6%AC%A1%E5%8F%98%E6%9B%B4%E5%A4%9A%E4%B8%AA%E8%8A%82%E7%82%B9 [4]TiDB 在 Raft 成员变更上踩的坑 - OpenACID Blog: https://blog.openacid.com/distributed/raft-bug/ [5]Read-Write Quorum Systems Made Practical : https://mwhittaker.github.io/publications/quoracle.pdf [6]quoracle::https://github.com/mwhittaker/quoracle[7]TiDB 在 Raft 成员变更上踩的坑 - OpenACID Blog:https://blog.openacid.com/distributed/raft-bug/[8]后分布式时代: 多数派读写的’少数派’实现 - OpenACID Blog: https://blog.openacid.com/algo/quorum/ [9]Read-Write Quorum Systems Made Practical : https://mwhittaker.github.io/publications/quoracle.pdf
关于 Databend
关于 Databend
Databend 是一款开源、弹性、低成本,基于对象存储也可以做实时分析的新式数仓。期待您的关注,一起探索云原生数仓解决方案,打造新一代开源 Data Cloud。