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

1. single quorum

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

這樣帶來的好處是, 因為Q1 階段選主階段, 這個選主階段執行的次數遠遠比同步數據階段要來的少很多. 所以我們可以讓 Q1 > Q2 && Q1 + Q2 > N, 來實現選主階段有比較多的節點, 而同步數據階段至少少量節點就可以. 當然也可以讓Q1 節點個數比Q2 多, 但是這種同步需要更多的成本, 其實意義不大. 其實可以看出 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 換取性能的做法

1. grid quorum

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