Paxos Made Simple 中文翻译
目錄
1.?引言
2. 共識算法
2.1 問題
2.2 選擇一個 value
2.3 獲知選定的?value
2.4 可進行性
2.5 實現
3. 實現狀態機
Paxos Made Simple
基礎概念
業界一般將 Lamport 論文里最初提出的分布式算法稱之為 Basic Paxos，這是 Paxos 最基礎的算法思想。Basic Paxos 算法的最終目標是通過嚴謹和可靠的流程來使得集群基于某個提案（Proposal）達到最終的共識。以下是該論文中涉及的一些概念：
- value：提案值，是一個抽象的概念，這里不能把它簡單的理解為數值。而應該理解為對某一數據或數據庫某一行的某一列的一系列操作。
- number：提案編號，全局唯一，單調遞增。
- proposal：集群需要達成共識的提案，擁有?number?和?value。
proposal 中的 value 就是在 Paxos 算法完成之后需要達成共識的值。
?
Paxos 算法中有三個核心角色：
- Proposer：生成提案編號?n?和?value v，然后向 Acceptors 廣播該提案，接收 Acceptors 的回復，如果有超過半數的 Acceptors 同意該提案，則選定該提案，否則放棄此次提案并生成更新的提案重新發起流程，提案被選定之后則通知所有 Learners 獲取該最終選定的提案值（也可以由 Acceptor?來通知，看具體實現）。Basic Paxos 中允許有多個 Proposers。
- Acceptor：接收 Proposer?的提案并參與提案的表決過程，把各自的決定回復給 Proposer?進行統計。Acceptor?可以接受來自多個 Proposers 的多個提案。
- Learner：不參與決策過程，只獲取最終選定的提案?value。
?
?
1.?引言
可能是因為之前的描述對許多讀者而言太過 Greek 了，Paxos?作為一種實現容錯的分布式系統的算法被認為是難以理解的。但事實上，它是簡單明了的分布式算法之一。其核心是一個共識算法——即?"The part-time parliament"?中提到的?"synod"?算法。下一節將展示該一致性算法幾乎滿足了所有我們想要的特性。最后一節將呈現完整的?Paxos?算法，通過直接應用協商一致的狀態機構建分布式系統——這種方法應該是廣為人知的，因為這可能是分布式系統理論中被引用最多的領域。
?
?
2. 共識算法
2.1 問題
假設有一些進程可以提出 value。共識算法保證在所有提出的?value 中只有一個會被選中。如果沒有?value 被提出，則不會選擇任何?value。如果已經選擇了一個?value，那么其他的進程應該能夠獲取被選擇的?value。共識算法的要求是：
我們不會嘗試指定確切的要求，但目標是確保總有一些提出的?value 最終會被選擇。并且，如果一個?value 已經被選擇了，那么其他進程最終都能夠獲取該 value。我們的共識算法中有三類 Agent：Proposer（提議者）、Acceptor（接受者）和?Learner（學習者）。在具體的實現中，一個進程可能扮演不止一類 Agent，但是在這里我們并不關心進程 Agent 的變換。
假設?Agent 之間可以通過發送?message 相互通信。我們通常使用異步的非拜占庭模型，其中：
①：Agent 以任意速度運行，可能發生故障，也可能會重啟。由于所有的 Agent 都可能在一個 value 被選中之后發生故障并重啟，因此一般的方法是不可行的，除非 Agent 能記住一些信息，即使發生了故障或重啟也能恢復之前的狀態。
②：message 可能需要任意長的時間來傳遞，可能重復，也可能丟失，但它們不會被破壞，即消息內容不會被篡改（非拜占庭問題）。
?
2.2 選擇一個 value
只擁有一個?Acceptor 是最簡單的選擇 value 的方法。Proposer?向?Acceptor?發送提議，Acceptor?選擇它收到的第一個提議?value 。雖然簡單，但這種解決方案并不能滿足分布式系統的需求，因為唯一的 Acceptor?發生故障將導致接下來的操作無法進行。因此我們嘗試另一種選擇?value 的方式。我們將使用多個而不是一個 Acceptor。Proposer?將提議的?value 發送給?Acceptor?集合。Acceptor?可以接受提議的?value，當足夠多的?Acceptor?接受它時，選擇該?value。
那么怎樣才算足夠大呢？為了確保只有一個?value 被選中，我們可以認為一個足夠大的Agent 集合由任意的大多數Agent組成。因為任意兩個這樣的集合都至少有一個公共的 Agent，因此如果一個?Agent 最多只能接受一個?value，這種方法就能奏效。在沒有故障或 message 丟失的情況下，我們希望一個?value 被選中，即使只有一個Proposer?提出了一個 value。這就需要滿足以下要求：
P1.?Acceptor必須接受它收到的第一個提議。
?
但是這個要求引出了一個問題。不同的?Proposer?可能幾乎同時提出好幾個不同的 value，這將導致這樣種情況：每個 Acceptor?都接受了一個?value，但沒有一個?value 被大多數?Agent 接受。即使只提出了兩個?value，如果每個?value 都被一半的?Acceptor?所接受，任意單個?Acceptor?的故障可能會使我們無法獲取它選擇了哪個?value。
P1 和 value 只有被大多數的 Acceptor 接受才算被選中的要求，意味著必須允許Acceptor 接受一個以上的 proposal。我們通過為每個 proposal 分配一個編號來追蹤 Acceptor 可能接受的不同的 proposal，因此 proposal 由 proposal number 和 value 組成。為了防止出現歧義，我們要求不同的?proposal 要有不同的?number。這里我們僅僅只是做出假設，具體的實現可能有所不同。當一個 proposal 被大多數?Acceptor?接受時，我們就認為該 value 被選中了。在這種情況下，我們說這個 proposal（同時包括它的 value）被選中了。我們可以允許多個?proposal 被選中，但是我們必須保證所有被選中的?proposal 具有相同的?value。通過歸納?proposal number，足以保證：
P2.?如果一個 value 為 v 的 proposal 被選中，那么所有被選中的高編號（high-numbered）的?proposal 都包含 value v。
?
由于?number 是有序的，條件?P2?保證了只有單一的 value 被選中的重要特性。為了能夠被選中，proposal 必須至少被一個?Acceptor?接受。因此，我們可以通過滿足以下條件來滿足?P2：
P2(a).?如果一個 value 為?v?的?proposal 被選中，那么任何?Acceptor?接受的每個高編號的?proposal 都有?value v。
譯注：如果此時系統收到 client 需要修改數據的請求，有 3 個 proposal（編號分別為n1、n2 和 n3，且 n1 < n2 < n3），此時編號為 n1 的 proposal 已經被選中。n1 是將 x 的值置為 1，n2 是將 x 和 y 的值分別置為 1 和 2。n3 是將 z 的值置為 3。那么接下來 Acceptor?只會接受 n2，只有這樣才能達成一致。
我們仍然需要滿足 P1，從而確保有 proposal 被選中。因為交互是異步的，一個?proposal可能被一些特定的、沒有接受過任何 proposal 的 Acceptor?C所接受。假設一個新的?Proposer?"蘇醒"，并且發送了一個帶有不同 value 的高編號的 proposal。P1?要求?C 接受這個?proposal，但卻違反了?P2(a) 的規定。為了同時滿足 P1?和?p2(a)，需要加強?P2(a)：
P2(b).?如果一個?value 為?v?的?proposal 被選中，那么之后每個 Proposer?提議的高編號的?proposal 都有?value v。
譯注：如果上述譯注中的編號為 n3 的 proposal 想被選中。則 n3 需要包含將 x 置為 1 的操作。若此時 n2 已經被選中了，那么 n3 需要包含設置 x 和 y 的操作才有可能被 Acceptor?接受。由于一個 proposal 必須由?Proposer?提出，才能被?Acceptor?接受。因此滿足 P2(b)就滿足了 P2(a)，也就滿足了 P2。
為了滿足?P2(b)，我們考慮如何證明它成立。我們先假設某個編號為?m，且?value?為?v 的?proposal?已經被選定，然后證明任何編號為?n（n?> m）的?proposal?也都擁有?value v。我們可以通過對?n?采用數學歸納法以使證明過程更輕松，于是在以下額外的假設下可證明編號為?n?的?proposal?擁有?value v：
歸納假設：每一個編號在 [m...(n-1)] 之間的 proposal 都擁有 value v，這里的 [i...j] 的記法代表從 i 到 j 的一組編號。
由于編號為?m?的?proposal?已經被選定，那就必然存在一個由?"大多數"?Acceptor?組成的集合?C，且集合里的每一個?Acceptor?都接受了這個?proposal。結合這個（推理）以及前面的歸納假設，m?被選定的假設則意味著：
集合 C 里的每個 Acceptor 都接受了編號在 [m...(n-1)] 之間的一個 proposal，并且被任何一個 Acceptor 所接受的每一個編號在 [m...(n-1)] 之間的 proposal 都擁有 value v。
由于任意一個由大多數?Acceptor?組成的集合?S?都必然包含集合?C?的至少一個元素，我們可以通過維護以下不變性以保證編號為?n?的?proposal?擁有?value v：
P2(c). 對于任意的?v?和?n，如果一個編號為?n?且擁有?value v的?proposal?被提出，則存在一個由大多數?Acceptor?組成的集合?S?滿足這里其中一個條件：
- （a）集合?S?里沒有?Acceptor?接受了任何一個編號小于?n?的?proposal；或者是：
- （b）v?是集合?S?中的?Acceptor?已經接受過的所有編號小于?n?的?proposal?中編號最高的?proposal?的?value。
因此我們可以通過維護?P2(c) 的不變性來滿足?P2(b) 的條件。
?
為了維護?P2(c) 的不變性，想要提議編號為?n?的?proposal?的?Proposer?必須獲知編號小于?n?的最大編號的?proposal，如果存在這樣的?proposal?的話，那它肯定是已經或者即將被大多數?Acceptor?所接受的?proposal。獲知已經被接受的?proposal?是足夠簡單的，但是預測未來哪些?proposal?會被接受則是困難的。與其嘗試去預測未來，不如讓?Proposer?通過獲取一個?"將不會存在任何一個這樣的接受"?的承諾來控制這個過程。換句話說，Proposer?請求?Acceptor?們不再接受任何編號比?n?小的?proposal。這就引出了以下用于提議過程的算法：
1.?一個?Proposer?選擇一個新的?proposal?編號?n，然后給由某些?Acceptor?組成的集合中的每一個成員發送一個請求，要求它響應以下信息：
- a. 一個承諾：不再接受任何一個編號比?n?小的?proposal，并且
- b. 如果它已經有接受過?proposal?的話，則還要返回它已經接受過的編號比?n?小的最大編號的?proposal。
我把這樣一個請求稱之為對編號?n?的?prepare?請求。
2.?如果?Proposer?從大多數的?Acceptor?成功收到期待的響應，則它可以接著提議一個編號為?n?且?value 為?v?的?proposal，這里?v?就是它從?1b 中收到的響應里最大編號的?proposal?的?value，如果所有響應都表明沒有接受過任何?proposal，則?Proposer?可以自由選擇一個?value 。
Proposer?通過向?Acceptor?集合發送一個請求來提議?proposal。（這里的?Acceptor集合并不需要和響應?request?請求的?Acceptor?集合一致）。讓我們把這個請求稱之為?accept?請求。
?
前面這些內容描述了?Proposer?的算法，但是對于?Acceptor?而言又該是怎樣子的呢？它可以接收來自?Proposer?的兩種請求：prepare?請求和?accept?請求。Acceptor?可以忽略任何請求而不影響安全性。所以，我們需要討論只在哪些情況下它可以響應請求。它總會響應?prepare?請求；它也可以響應?accept?請求，接受?proposal，只要它沒有承諾不這樣做。換句話說：
P1(a).?Acceptor?可以接受編號為?n?的?proposal，只要它沒有響應過編號大于?n?的prepare?請求。
可見 P1(a)?包含了 P1。
現在我們已經得到了一個足以滿足安全性的用于選定?value 的完整算法——在假設?proposal?編號唯一的基礎上。最終的算法還需要通過額外的優化來得到。
假設一個?Acceptor?收到了一個編號為?n?的?prepare?請求，但是它已經響應過一個編號比?n?大的?prepare?請求，因此也就承諾了不再接受任何編號為?n?的新的?proposal。于是?Acceptor?沒有理由要去響應這個新的?prepare?請求，因為它并不會考慮接受編號為?n?的?proposal，也就是?Proposer?想要提議的?proposal。所以我們讓?Acceptor?直接忽略這樣一個?prepare?請求。我們也讓?Acceptor?直接忽略它已經接受的?proposal?的?prepare?請求。
經過這樣的優化以后，Acceptor?只需要記錄它已經接受過的最高編號的?proposal?以及它已經響應過的最高編號的?prepare?請求的編號即可。因為無論失敗與否，P2(c) 都必須保持不變，所以?Acceptor?必須能夠記錄這些信息，哪怕它可能出現故障，以及重啟。注意?Proposer?總是可以放棄某個?proposal?并且裝作什么都沒有發生過——只要?Proposer?不會嘗試用相同的編號提議另一個?proposal。
?
將?Proposer?和?Acceptor?的行為都放在一起，我們可以看到這個算法的流程可以分為以下兩個階段：
Phase 1：
- (a) Proposer?選擇一個?proposal?編號?n，向?"大多數"?Acceptor?發送一個帶有編號?n的?prepare?請求；
- (b) 如果?Acceptor?收到一個編號為?n?的?prepare?請求，且?n?比它已經響應過的任何一個?prepare?請求的編號都大，則它會向這個請求回復響應，內容包括：一個不再接受任何編號小于?n?的?proposal?的承諾，以及它已經接受過的最大編號的?proposal（假如有的話）。
Phase 2：
- (a) 如果?Proposer?從"大多數"?Acceptor?收到了對它前面發出的?prepare?請求的響應，它就會接著給這些 Acceptor?發送一個編號為?n?且?value 為?v?的?proposal?的?accept請求，而?v?就是它所收到的響應中最大編號的?proposal?的?value ，或者是它在所有響應都表明沒有接受過任何?proposal?的前提下自由選擇的?value v；
- (b) 如果?Acceptor?收到了一個編號為?n?的?proposal?的?accept?請求，它就會接受這個請求，除非它之前已經響應過編號大于?n?的?request?請求。
Proposer?可以提議多個?proposal，只要它在每一個?proposal?中都遵循上面的算法。它也可以在協議中間的任何時刻丟棄?proposal。（正確性還會被保持，哪怕是對廢棄?proposal?的請求或者響應可能在?proposal?被丟棄很久之后才到達目的地）。在某些?Proposer?已經開始嘗試提議更高編號的?proposal?的情況下，（盡早）放棄（當前較低編號的）proposal?或許是一個好的主意。所以，如果?Acceptor?由于它自身已經收到了更高編號的?prepare?請求而選擇忽略當前的?prepare?或者?accept?請求，那它應該通知?Proposer，Proposer?應該在收到通知后放棄proposal。總體而言，這是一個不會影響正確性的性能優化。
?
2.3 獲知選定的?value
為了獲知一個被選定的 value，Learner?必須找出某個已經被大多數?Acceptor?接受的proposal。最顯而易見的算法就是讓每一個?Acceptor?一旦接受了?proposal，就響應給所有?Learner，并給它們發送接受了的?proposal?信息。這種方法允許?Learner?們盡可能快地找出被選定的value ，但這種方法也要求每個?Acceptor?要響應每個?Learner——響應的數量等于?Acceptor?數量和?Learner?數量的乘積。
沒有拜占庭失敗的假設使得一個?Learner?可以很容易地通過其他的?Learner?來獲知某個?value 已被接受的事實。我們可以讓?Acceptor?將它們的接受事件響應給某個特定的?Learner，這個特定的?Learner?要負責在每一個?value 被選定之后通知其他的?Learner。這種方法要求所有的?Learner?花費額外的一輪時間用于獲知被選定的?value，也降低了可靠性，因為那個特定的?Learner?可能會出現故障。但是這個方法要求的響應數量只等于?Acceptor?的數量和?Learner?的數量之和。
更一般的，Acceptor?可以將它們的接受事件響應給由多個特定的?Learner?組成的某個集合，集合中的每個?Learner?都會在每一個?value 被選定之后通知所有的?Learner。使用這樣一個較大的特定的?Learner?組成的集合可以提供更高的可靠性。
由于?message 丟失，value 可能在?Learner?無法發現的情況下被選定。Learner?可以詢問?Acceptor：現在已經接受了什么?proposal？但是?Acceptor?的失效可能導致無法知道是否有一個大多數的?Acceptor?已經接受了某個特定的?proposal。在那種場景下，Learner?只能在一個新的?proposal?被選定的情況下才能找出哪個?value?被選定了。如果?Learner?需要知道一個?value 是否已經被選定，它可以讓?Proposer?使用上面描述的算法提議一個?proposal?即可。
?
2.4 可進行性
很容易構建這樣一個場景：兩個?Proposer?相繼提議一系列遞增編號的?proposal，但是沒有哪一個?proposal?能被選定。Proposer?p?完成了編號?n1?的?proposal?的?Phase 1，接著另一個?Proposer?q?也完成了編號n2（n2>n1）的?proposal?的?Phase 1。由于?Acceptor?已經承諾不會再接受任何編號小于?n2?的新?proposal，所以?Proposer?p在?Phase 2發送的?accept?請求會被忽略。所以，Proposer?p?又接著開始并且完成了一個新的?proposal?n3（n3>n2）的?Phase 1，導致?proposal?q?的?Phase 2?的?accept?請求也被忽略了，如此反復進行。
為了保證流程的執行，我們必須選出一個特定的 Proposer，作為唯一的 proposal?發送者。如果這個特定的?Proposer?可以成功地和大多數?Acceptor?通信，并且它使用了編號比任何已經使用的編號大的?proposal，那么它將會成功完成提議，也就是說，proposal?會被接受。通過在發現某個請求已經使用了更高的?proposal?編號的情況下主動放棄?proposal?然后重試（Phase 1），這個特定的?Proposer?終將能夠選到一個足夠高的?proposal?編號。
如果系統有足夠多的組件（?Proposer、Acceptor?以及通信網絡）正常工作，那么就可以通過選舉一個特定的?Proposer?來保持系統的活力。Fischer, Lynch?和?Patterson?的著名實驗結果指出：選舉一個?Proposer?的可靠算法必須使用隨機性或者實時性——比如，使用超時機制。無論如何，不管選舉成功或者失敗，安全性都是可以保證的。
?
2.5 實現
Paxos算法假設了一個由許多進程構成的網絡。在這個一致性算法里，每個進程同時扮演了?Proposer、Acceptor和?Learner。這個算法也會選定一個?Leader，由它同時扮演特定的?Proposer?和特定的?Learner。Paxos?一致性算法正是上面描述的算法，其中請求和響應都作為普通消息發送。（響應的消息都會用對應的?proposal?的編號做標記，以防混淆）我們需要使用持久化存儲在故障時發揮作用，用于維護?Acceptor?必須記住的信息。?Acceptor?需要在真正發出響應之前在持久化存儲上記錄它的響應。
接下來的所有內容都將用于描述如何保證兩個 proposal?不會有相同的編號。只要不同的Proposer?從不相交的編號集合中選擇編號，這兩個不同的?Proposer?提議的?proposal?就一定不會擁有相同的編號。每個?Proposer?在持久化存儲上記錄各自已經嘗試提議的最高編號的?proposal，然后使用一個比它使用過的編號更高的?proposal?編號再次開始?Phase 1?的過程。
?
?
3. 實現狀態機
實現一個分布式系統的簡單方式就是 client 集合向一個 central server（中央服務器）發送命令。可以將?server 描述為一個按照時序執行?client 命令的確定性狀態機（deterministic state machine）。這個狀態機擁有一個當前的狀態，它通過接受一個命令作為輸入來執行一個步驟，然后產生一個相應的輸出以及一個新的狀態。舉個例子：一個分布式的銀行系統的?client 可能是出納員，而所有用戶的賬號余額可以看做狀態機的狀態。一個取款操作可以通過執行一個狀態機命令來完成：這個命令當且僅當余額大于取款數量的時候才可以扣除賬戶余額，并生成新的余額作為輸出。
使用?central server的實現方案會隨著?server 的崩潰而失效。于是，我們想到了可以使用一組?server，每個?server 彼此獨立地實現同樣的狀態機。由于狀態機是確定的，所以如果所有?server 都執行了相同的一系列命令，那么所有?server 都將會產生同樣的一系列狀態以及輸出。一個發出命令的?client 則可以任意選取一臺?server 生成的輸出。
為了保證所有?server 執行相同的狀態機命令序列，我們需要實現?Paxos?一致性算法的一系列獨立的實例，被第?i?個實例選定的?value 作為序列中的第?i?個狀態機命令。每個?server 都在每個實例中扮演這個算法的所有角色（Proposer、Acceptor和Learner）。就現在而言，我假設?server 的集合是固定的，所以這個一致性算法的所有實例使用相同的?Agent 集合。
在正常操作中，一個單獨的?server 被選舉為了?leader，由它在這個一致性算法的所有實例中扮演特定的?Proposer（只有它會嘗試提議?proposal）。client 發送命令到?leader，leader?決定每個命令的順序。假如?leader?決定某條?client 命令應該是第 135 個命令，那么它就會嘗試通過這個一致性算法的第?135?個實例來提議選定一個?proposal，命令本身就是這個?proposal?的?value。這個過程通常會順利完成。但它也可能因為故障而失敗，或者因為有另一個?server 認為它自己才是?leader?并且它認為第 135 個命令應該另有他?value。但是這個一致性算法確保第 135 位上最多只有一個命令能夠被選定。
Paxos?一致性算法的效率關鍵在于直到?Phase 2?之前都不對提出的 value 進行選擇。回想一下，在完成?Phase 1?之后才知道要發送的 value，要么可以確定要提議的 value，要么 Proposer?可以自由提議任何 value。我現在將要描述?Paxos?狀態機是怎么工作的。之后，我也將會討論我們可能會遇到什么問題。我考慮的是在前一個?leader?剛發生故障而新的?leader?已經被選舉出來的時候，會有什么事情發生。（系統啟動是一個特殊場景，這個時候還沒有任何命令被提議）
這個新的?leader?也是這個一致性算法的所有實例中的?Learner，它應該知道大多數已經被選定的命令。假設它知道 1-134、138 以及 139 號命令，也就是一致性算法的 1-134、138 以及 139 號實例的?value。（我們稍后將會看到命令序列中的這樣的 gap 是如何產生的）。然后它執行實例?135-137?以及所有大于?139?的實例的?Phase 1，假設這些操作的執行結果只確定了實例 135 和 140 中提議的?value，但是其他實例的 value 還是未確定的。leader 執行實例 135 和 140 的?Phase 2，并因此可以選定 135 和 140 號命令。
?
leader?以及那些獲取了 leader 已知的所有 command 的 server 現在可以執行命令 1-135。因為?136?號和?137?號命令還沒有被選定，所以它還不能運行 138-140 號的命令，盡管它知道 138-140 號命令。于是，我們讓它通過提議將一個特殊的不會導致狀態機狀態切換的?"noop"?命令作為第?136?號和?137?號命令（它可以通過執行一致性算法的 136 號和 137 號實例的?Phase?2?來完成），以此快速填補空缺。一旦這些?noop?命令被選定，那 138-140 號命令就可以被執行了。
現在從 1 到 140 的命令都被選定了。leader?也完成了一致性算法中所有大于 140 的實例的?Phase?1，并且可以在這些實例的?Phase 2?中自由地提出任何的?value。它為 client 發送的下一個請求分配命令編號為 141，并且將它作為一致性算法實例 141 的 value。之后再將 client 的下一個請求作為命令 142，以此類推。
leader 可以在它獲知已經提議的命令?141 被選定之前提議命令?142。可能發送命令?141 的所有消息都會丟失，而第 142 號命令會在其他?server獲知到?leader?提議的第 141 號命令之前被選定。當?leader?在實例 141 中沒有收到對它的?Phase 2?的預期響應時，它將會重發這些消息。如果一切順利，它提議的命令會被選定。然而，在一開始可能會發生故障，從而在已選中的命令序列中留下一個 gap。一般來說，假設一個 leader 可以提前獲得?a 個命令——也就意味著，它可以在 1 到 i?號命令被選定的前提下提議?i+1?到?i+a 號命令。一個多達?a-1?個命令的?gap 可能隨之形成。
一個新的被選定的 leader 執行一致性算法的無數個實例的?Phase 1?——在上面的場景中，就是實例 135-137，以及所有大于139的實例。讓所有實例使用一樣的?proposal?編號，它可以通過向其他的?server 發送一個短消息來實現這一點。在?Phase 1中，Acceptor?當且僅當已經收到了某個?Proposer?的?Phase 2?的消息的時候，它就會不僅僅回復一個簡單的?OK。（在這個場景里，這是僅針對實例 135 和 140 的例子）所以，一個?server（作為 Acceptor）可以用一個短消息回復所有的實例。因此，在無數個實例的 Phase 1 這樣執行不會產生任何問題。
由于 leader 的故障和新 leader 的選舉理應很少發生，因此執行狀態機命令的開銷——即 command/value 達成一致的過程——主要是一致性算法?Phase 2?的執行開銷。可以看出，Paxos?一致性算法的?Phase 2 在存在故障的情況下，其達成協議的代價是所有算法中最小的。于是，Paxos?算法基本上是最優的。
對于系統正常運行的討論中假設除了當前 leader 發生故障，新的 leader 還未選出的短暫時間外，總是存在一個單一的 leader。在異常情況下，leader?選舉可能失敗。如果沒有?server 擔任 leader，也就沒有新的命令會被提議。如果多個?server 認為它們自己都是?leader，則它們可以對一致性算法的同一個實例發送 value，這可能妨礙任何 value 被選擇。盡管如此，安全性還是保證的——兩個不同的?server 永遠不會對已經被選為第 i 個狀態機命令的 value 存在分歧。單一 leader?的選舉僅僅只是為了保證流程的執行。
如果?server 的集合是可以改變的，我們必須要有辦法確定哪些 server 實現了一致性算法的哪些實例。實現這個最簡單的方法就是通過狀態機它自己。當前的?server 集合可以作為狀態的一部分，并且可以通過普通的狀態機命令而變化。在執行第?i?個狀態機命令后，我們可以允許?leader?提前獲得?a 個命令，通過用狀態指定一組執行一致性算法的第?i+a 號實例的 servers。這允許簡單的實現任意復雜的重新配置算法。
總結
以上是生活随笔為你收集整理的Paxos Made Simple 中文翻译的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Amazon Aurora：高吞吐量云原
- 下一篇： 操作系统中的同步和异步