論文筆記：Paxos Made Simple

Paxos 是一種分散式共識演算法，用於解決在非同步通信網路中存在節點失效且本地存儲可靠的情況下多個分散式節點達成一致的問題。文中的演算法只解決了決議一條法案（decree）的情況。如果需要決議多條法案，可以將該演算法執行多次，每次分別對應一條法案。可以想像，有可能存在一些步驟在多次決議時無需重複執行，因此在多次決議法案的情況下，該演算法可以進一步優化，但沒有在本文中進行具體展開。

演算法原理

為了確保演算法的正確性，我們需要以下 3 個基礎的 safety 性質：

1. Only a value that has been proposed may be chosen,
2. Only a single value is chosen, and
3. A process never learns that a value has been chosen unless it actually has been.

其中 1 排除了選中錯誤的提案的情況，2 排除了節點之間不一致的情況，3 排除了事先選中提案的情況（non-triviality）。

除了需要保證演算法的正確性，我們還需要保證演算法確實能夠進行到我們想要的狀態。但是在此時我們還無需精確地定義 liveness 條件，而是考慮如何在保證正確性的情況下，使得某一個值最終能被選中，並且一個進程最終能夠得知這一結果。

根據以上要求，我們引入 3 個角色：提議者（proposer），仲裁者（acceptor）和學習者（learner）。每個進程都可以扮演其中一個或多個角色。

最簡單的方法就是我們選定唯一一個仲裁者，所有提議者都向這一仲裁者提議，仲裁者只需接受第一個收到的提案即可滿足上述所有要求。但是這種方法一旦這唯一的仲裁者失效，我們就不能獲得任何進展了。因此我們必須設立多個仲裁者，集體進行多數表決。多數表決可以滿足上面提到的所有基礎 safety 性質，尤其是 2（反證法可證明）。

在不考慮節點失效和消息丟失的情況下，我們希望即便全局只存在 1 個提案，我們也能選中這一提案。這就要求我們滿足如下性質：

• P1 An acceptor must accept the first proposal that it receives.

但是這一要求會帶來這樣一個問題，每個提議者同時分別向一個不同的仲裁者提交不同的提案，此時每個仲裁者都接受了一個不同的提案，從而無法形成多數派。這一問題並非只能由非常罕見的情況觸發，例如即便是只有兩個提案同時分別被恰好一半的仲裁者所接受，此時由於一個仲裁者節點失效，導致剩下的仲裁者以同樣的數量分別支持兩個不同的提案，此時雖然有且僅有一個提案被選中了，我們卻不能得知這是哪個提案。

因此性質 P1 和多數表決選中提案的方式決定了我們必須允許仲裁者接受多個提案。為此我們將每一個不同的提案內容進行標號，使得每一個不同的提案內容都具有不同的標號，而標號具有全序關係。這樣，每個提案就都具有 (n,v) 這樣的形式。因此我們就可以允許仲裁者選中多個提案，只需保證這些提案具有相同的提案內容 v 即可。通過在提案編號上應用數學歸納法，我們可以用如下性質來保證這一點：

• P2 If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v .

一個提案想被選中，必須先由仲裁者接受。因此我們可以考慮在仲裁者接受提案時，對其加以約束以滿足性質 P2：

• P2a If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v .

由於通信是非同步的，就會存在某個仲裁者，其並不清楚其他某個仲裁者已經接受了一個提案這種情況。此時，如果這一仲裁者收到了一份新的提案，由於性質 P1，它必須接受這份提案，而這就有可能和性質 P2a 相違背。由於所有提案都是先由提議者提出的才被仲裁者接受的，因此我們可以考慮加強條件，由提議者保證這一性質：

• P2b If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

對提案編號 n 使用數學歸納法，可知滿足以下性質即可保證性質 P2b：

• P2c For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

為了滿足性質 P2c，提議者若想提議編號為 n 的提案，必須知道是否存在小於編號 n 的提案已經或者將要（在編號為 n 的提案被多數仲裁者所接受之前）被多數仲裁者所接受。我們可以獲知已經被接受的提案，但是很難預測將要發出的編號為 n 的提案被多數仲裁者接受之前是否還會有其他提案被多數仲裁者所接受。為了避免這一情況，我們可以提前要求仲裁者做出承諾，不去接受小於編號為 n 的任何提案。由於 P2c 蘊含 P2b，P2b 蘊含 P2a，P2a 蘊含 P2，我們可以使用如下的演算法來保證 P2c，進而滿足性質 P2：

1. A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:
1. A promise never again to accept a proposal numbered less than n, and
2. The proposal with the highest number less than n that it has accepted, if any.
2. If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses, or is any value selected by the proposer if the responders reported no proposals.

這一方法實際上違背了性質 P1。考慮到性質 P1 適用於只發起 accept 請求的情況，而我們的演算法實際上存在兩種請求：prepare 和 accept。收到一個 prepare 請求意味著接下來還會收到一個具有相同提案編號的 accept 請求，因此如果我們收到一個不同編號的 accept 請求時，總是可以忽略這一請求，同時不違背我們至少可以保證還有一個提案可以接受這一性質。由此我們可以得到性質 P1 的加強形式：

• P1a An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

由於 P1a 蘊含 P1 ，我們就得到了一個能夠滿足所有 safety 性質的演算法。對其細節進行一些優化，可以得到以下版本：

Phase 1

1. A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
2. If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Phase 2

1. If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
2. If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

提議者只需遵循上述演算法，就允許發起多個提議。提議者也可以在任何時間放棄一個已經發起的提案而不影響正確性。一個仲裁者如果因為已經承諾不再接受更低編號的提案而忽略（ignore）一個提議時，儘管不影響正確性，但是為了性能考慮，最好告訴該提議者目前已知的最大提案編號。

這一演算法可以正確的選中一個提案，但是還需要學習者使得所有進程都知道這一結果。儘管可以讓所有的仲裁者在自己選中某一提案的時候都將這一結果告知所有的學習者，這一方案需要多次（兩個集合的笛卡兒積的大小）廣播，性能較低。此時只需選擇幾個 distinguished learner 告知，再由它們告知所有 learner 即可。需要考慮到，由於消息可能丟失，可能所有的 distinguished learner 都不能得知當前被選中的提案。此時只需令提議者再次發起提案，直到有一個提案被選中，即可知道被選中的提案是什麼。

這一演算法雖然可以保證正確性，但是不能保證在演算法結束前時時都有進展，即不能保證最終一定能達到一致決議的狀態。例如兩個提議者交替的提議新的提案，每個提案編號都比對方的提案編號高，這樣每次的 prepare 請求都會成立，但是 accept 請求都會被拒絕，使得演算法不能停機。為了保證演算法能夠停機，我們需要選出一個唯一的 distinguished proposer，（此處開始到本自然段結束不確定）只有這個提議者會在發現自己的提議被多數仲裁者忽略（ignore）時，重新選擇一個新的足夠大的提案號重新提交提案（其他提議者在消息丟失時可以用原來的提案號重發來保證多數仲裁者能夠收到這個提案，但是被仲裁者拒絕時不重新提交提案）。這意味著，在決議衝突的情況下，總是令 distinguished proposer 獲勝。此外也可以採用計算機網路中衝突避免的方式來解決這一問題，比如說發生衝突時乘性增加重新提交提案的時間間隔，不衝突時加性減少時間間隔。這樣就可以實現完全不需要 leader 的情況，但是潛在的風險就是 latency 增加。

如果系統中足夠多的部分（包括提議者，仲裁者和通信網路等組件）工作正常，那麼選舉出唯一的 distinguished proposer 即可保證 liveness。（原文並沒有證明這一點，不過據說在 [4] 中有一個關於 liveness 的證明，目測在 [3] 中含有一個不太正式的證明，在 [5] 中有一個對該演算法加強形式的演算法的證明，但是我都還沒有看）論文 [2] 中蘊含了這樣一個結論，一個可靠的選舉演算法必須依賴於隨機性或 real time（比如說 timeout 機制）。無論選舉的結果如何，本論文中提到的演算法的正確性都是可以保證的。（無論是否有 distinguished proposer，無論是否只有一個 distinguished proposer，都可以保證演算法的正確性）

其他細節

演算法需要保證每個不同的提案都有不同的提案編號，這可以通過事先給每個提議者分別指定一個不相交的數集來做到。例如，一共有 3 個提議者，則提議者 1 的提案編號只能從除以 3 余 0 的非負整數集合中取。

演算法中的提案內容 v 可能需要多次傳遞，因此也應該保證其大小不會過大。但是有的時候確實需要對一個較大的對象達成共識，比如說 block replica。個人認為可以使用類似於 GFS 中的控制流和數據流相分離的策略 [6]，通過流式傳輸以節點鏈的順序將較大的值事先標記並傳播到每一個節點上，各個節點使用 LRU 之類的策略緩存這一內容，然後通過 Paxos 演算法進行決議，這樣提案內容 v 只需能夠索引到這一較大的值即可。

之前的演算法只能對單一法令（decree）進行決議。在實際使用中，我們經常需要使用這樣的演算法維護分散式節點中每個節點的狀態一致 [7]。為此我們可以令每個節點保存最近的若干條狀態機的指令，對指令日誌進行 replica 的方式來保證狀態機狀態的一致。這樣，我們只需確定每一條狀態機指令在這個日誌中的位置，即可保證狀態機的一致性，即對指令日誌中的每個位置運行一次 single-decree Paxos 演算法。（此處開始到本自然段結束為個人理解）令每個進程都同時扮演提議者，仲裁者和學習者這三種角色。由於我們同時需要至少一個 distinguished learner 和唯一一個 distinguished proposer，因此不妨通過選主演算法在這些進程中選出一個 leader，同時扮演 distinguished learner 和 distinguished proposer。所有的狀態機指令總是發給 leader。如果狀態機指令發給了其他節點，由於在決議衝突中總是 leader 獲勝，將會導致該指令總是失敗。每個節點保持運行固定數量的 single-decree Paxos 演算法實例（instance），比如說 α 個。在沒有接收到任何狀態機指令的時候，這些演算法實例即可完成演算法的 Phase 1，並且總是 leader 獲勝。當 leader 收到狀態機指令時，只需將該指令確定位置，並令對應該位置的 Paxos 演算法實例進行 Phase 2 即可（原作者說這應該是共識演算法的複雜度下界，貌似論文 [8] 證明了這一點，但是我還沒看）。由於通信是非同步的，因此可能會導致狀態機指令中編號靠前的指令還沒有提交完成 Phase 2，但是後面的指令已經提交完成 Phase 2。此時，若 leader 失效，重新選主，就會在狀態機指令日誌中留下一些空洞。而且由於原來的 leader 失效，也沒有其他節點能夠知道對應該位置的狀態機指令是什麼。為了不使整個狀態機的運行卡住，新的 leader 可以選擇在這些位置填入空指令來跳過這些空洞位置，使得整個過程繼續運行下去。上面提到的針對狀態機指令進行 replica 的演算法，只適用於固定的節點集合。如果需要在運行時調整節點集合，最簡單的方法就是將調整集合的指令也作為一條狀態機指令，當前的節點集合作為狀態機所維護的狀態。

從兩階段提交（2PC）的角度理解 Paxos：Phase 1 要求多數節點做 Promise（prepare），Phase 2 要求這些節點 Commit（accept）。從 Quoraum 的角度理解：已經選出 Leader 的情況下，直接執行 Phase 2，此時只需寫成功多數節點即可。

Reference

[1] Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News 32, 4 (2001), 51–58. DOI:https://doi.org/10.1145/568425.568433

[2] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:https://doi.org/10.1145/3149.214121

[3] Leslie Lamport. 1998. The Part-Time Parliament. ACM Trans. Comput. Sys-tems 16, 2 (1998), 133–169. DOI:https://doi.org/10.1145/279227.279229

[4] Roberto De Prisco, Butler Lampson, and Nancy Lynch. 2000. Revisiting the paxos algorithm. Theor. Comput. Sci. 243, 1–2 (2000), 35–91. DOI:https://doi.org/10.1016/S0304-3975(00)00042-6

[5] Leslie Lamport. 2005. Generalized Consensus and Paxos. April (2005), 60. DOI:https://doi.org/MSR-TR-2005-33

[6] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. Proc. Ninet. ACM Symp. Oper. Syst. Princ. - SOSP 』03 (2003), 29. DOI:https://doi.org/10.1145/945449.945450

[7] Fred B. Schneider and Fred B. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22, 4 (December 1990), 299–319. DOI:https://doi.org/10.1145/98163.98167

[8] Leslie Lamport. 2006. Lower bounds for asynchronous consensus. Distrib. Comput. 19, 2 (2006), 104–125. DOI:https://doi.org/10.1007/s00446-006-0155-x