Flexible Paxos-Quorum intersection revisited


FPaxos

Flexible Paxos is the simple observation that it is not necessary to require all quorums in Paxos to intersect. It is sufficient to require that the quorum used by the leader election phase will overlap with the quorums used by previous replication phases. Majority quorums are one such way to meet this requirement, but many more exist. Thus, Paxos is just a single point on a broad spectrum of possibilities for safely reaching distributed consensus.

fpaxos 主要提出并且证明了其实在multi-paxos 的两个阶段(选主阶段+normal 阶段)里面, 只需要这两个阶段的quorum 有交集就行, 并不需要两个阶段的quorum 都是集群中的大多数, 因此提出了3中quorum 策略.

定义集群中有n 个节点, Q1 是paxos 第一阶段选主需要达成的 quorum 的个数, Q2 是第二阶段normal, 也就是同步数据阶段需要通过的quorum 的个数.

  1. majority quorum

    就是我们最常见的quorum 策略, 那么Q1 > n/2 + 1, Q2 > n/2 + 1

  2. single quorum

    single quorum 定义主要是 Q1 + Q2 > N

    这样带来的好处是, 因为Q1 阶段选主阶段, 这个选主阶段执行的次数远远比同步数据阶段要来的少很多. 所以我们可以让 Q1 > Q2 && Q1 + Q2 > N, 来实现选主阶段有比较多的节点, 而同步数据阶段至少少量节点就可以. 当然也可以让Q2 节点个数比Q1 多, 但是这种同步需要更多的成本, 其实意义不大. 其实可以看出 majority quorum 是 single quorum 的一个泛化的模型.

    那么single quorum 可以容忍的节点宕机数是: min(Q1, Q2) - 1, 而majority quorum 可以容忍的节点宕机数是 n/2

    可以看出single quorum 可以容忍的节点宕机数是小于 majority quorum, 但是single quorum 的性能是优于majority quorum, 因为single quorum 在数据同步阶段可以只需要确认少量的节点就可以给用户返回, 可以认为是一个availability 换取性能的做法

  3. grid quorum

    Imgur

    grid quorum 将所有的N 个节点放入到一个N1 * N2 = N 的一个矩阵里面. 那么我们这里定义的 Q1 可以是其中的一行, Q2 可以定义的是其中的一列. 因为Q1 和 Q2 必然有交叠, 那么这样的quorum 其实是也可以满足paxos 的需求, 这样带来的好处是Q1 + Q2 不需要大于N, 比如在上图的这个例子里面, Q1 和 Q2 其实只有5 + 4 - 1 = 8 个节点, 远远小于20.

    那么grid quorum 可以容忍节点宕掉的个数是从min(n1, n2) (也就是每一个行, 或者每一列都宕掉一个) 到 (n1 - 1)*(n2 -1)(可以想象成只剩下最后一行, 和最后一列, grid quorum 仍然可以执行) 之间. 所以这里不能强行比较说grid quorum 可以容忍的宕机节点比majority quorum 来得多. 因为比如这里在 majority quorum 里面, 可以容忍宕机的节点数是 9.

    这里主要原因是grid quorum 相比于majority quorum 对每一个节点宕机处理是不一样的, grid quorum 更多是看待具体宕机的节点, 而不是宕机的个数, 只需要保存完整的一行一列, grid quorum 仍然是可以执行的

总结:

有了这几个不同的quorum 策略, 我们在使用的时候有哪些应用场景呢?

比如simple quorum 在节点数比较多的时候, 可以根据需求动态调整Q1, Q2 的节点个数, 以满足我们对可用性和性能的一个权衡

grid quorum 可以用来描述在跨机房, 每个机房有多个节点场景下的模型, 但是grid quorum 有一个比较大的问题是, 如果我们把某一列描述成一个机房的机器, 那么很容易一个机房不可用, 导致整个集群不可用, 那么这个问题怎么解决呢?

这篇论文有介绍:

https://www.cse.buffalo.edu//tech-reports/2017-03.pdf

下一篇博客我们也会介绍

reference

https://fpaxos.github.io

https://arxiv.org/pdf/1608.06696v1.pdf