Paxos演算法是分布式一致性的代名詞，可以說是最難理解的演算法。 本文試圖用通俗易懂的語言解釋 Paxos 演算法。
Paxos 演算法是由 Grandmaster Lamport 提出的一種基於訊息的分布式共識演算法，該演算法獲得了 2013 年圖靈獎。
Paxos 於 1998 年由 Lamport 首次發表在 The Part-Time Parliament** 上，最初的描述以希臘的 Paxos 島為隱喻來描述在 Paxos 島上通過決議的過程，並以此命名演算法，但描述難以理解。 後來，在 2001 年，Lamport 覺得他的同齡人無法理解他的幽默感，於是他重新發布了乙個嚴肅的演算法描述版本 Paxos Made **
Paxos 自成立以來就壟斷了分布式共識演算法，Paxos 一詞幾乎是分布式一致性的代名詞。 Google 的許多大型分布式系統都使用 PaxOS 演算法來解決分布式一致性問題，例如 Chubby、MegaStore 和 Spanner。 開源 ZooKeeper 和 MySQL 5為取代傳統主從複製而推出的MySQL Group Replication，採用了PaxOS演算法來解決分布式一致性問題。
然而，PaxOS最大的特點是難，不僅難理解，而且難實現。
PaxOS演算法解決的問題恰恰是分布式一致性問題，即分布式系統中的程序如何就某個值（解像度）達成一致。
PaxOS 演算法在非同步系統中執行，該系統允許停機，不需要可靠的訊息傳遞，並且可以容忍訊息丟失、延遲、亂序和重複。 它利用多數機制來確保 2f+1 容錯，即 2f+1 系統允許多達 f 個節點同時發生故障。
乙個或多個提案者可以發起提案，Paxos演算法可以在所有流程中就所有提案中的乙個達成一致。 系統中的大多數人同時同意該提案，即同意該提案。 至多應就一項已確定的提案達成一致意見。
Paxos 將系統中的角色分為提議者、接受者和學習者
proposer：提出建議。 提案資訊包括提案 ID 和提案的值。 acceptor：參與決策，回應提案人的建議。 提案收到後即可被接受，如果提案被多數接受者接受，則稱該提案獲得批准。 learner：不參與決策，向投標人、接受者了解最新商定的提案價值。 在多副本狀態機中，每個副本同時具有三個角色：提議者、接受者和學習者。
Paxos 演算法中的角色。
PaxOS 演算法通過解像度將 Paxos 演算法分為兩個階段（解像度在學習階段之前形成）：
第 1 階段：準備階段。 提議人向受理人提出準備請求，接受人對收到的準備請求作出承諾。 第 2 階段：接受階段。 提議人收到大多數接受人的承諾後，向接受人傳送提議請求，接受人接受收到的提議請求。 第 3 階段：學習階段。 提案人收到大多數接受者的接受後，標誌著接受成功，並形成決議，並將形成的決議傳送給所有學習者。 
Paxos 演算法流程。
PaxOS 演算法流程中的每條訊息描述如下：
prepare：提議者生成乙個全域性唯一且遞增的提議 ID（您可以使用時間戳和伺服器 ID）向所有接受者傳送準備請求。 promise：接受者收到準備請求後，做出“兩個承諾，乙個回答”。 兩個承諾：
準備提案 ID 小於或等於（注意：此處為 <= 此處）的請求，不再接受當前請求。 提案 ID 小於（注意：此處<）的提案請求將不再被接受。 乙個答案：
在不違反先前承諾的情況下，回覆已接受提案中提案 ID 最大的提案的值和提案 ID，如果沒有，則返回 null 值。
propose：提議者收到大多數接受者的承諾響應後，從回覆中選擇提案 ID 最大的提案值作為要發起的提案。 如果所有響應的提案值為空，則可以隨意決定提案值。 然後攜帶當前提案 ID，並向所有接受者傳送提案請求。 accept：接受方收到提案請求後，在不違反其先前承諾的情況下接受並保留當前提案 ID 和提案值。 learn：提案人獲得大多數接受者的接受後，形成決議，並將形成的決議傳送給所有學習者。 Paxos 演算法偽**描述如下：
Paxos 演算法偽**。
獲取提案ID n，為了保證提案ID唯一，可以通過時間戳+伺服器ID生成; 提議者向所有接受者廣播準備（n）請求; 接受者比較 n 和 minproposal，如果 n>minproposal， minproposal=n，則返回 acceptedproposal 和 acceptedvalue; 在收到超過一半的回覆後，如果提議者發現返回了 acceptedValue，則所有回覆中 AcceptedProposal 最大的 AcceptedValue 將作為提案的值，否則可以任意確定提案的值。 從這裡可以進入第二階段，向所有節點廣播接受（n，value）; 接受者比較 n 和 minproposal，如果 n>=minproposal，則 acceptedproposal=minproposal=n，acceptedvalue=value，區域性持久化後返回; 否則，將返回 minproposal。 在收到一半以上的請求後，如果提議者發現結果>n的返回值，則表示有更新的提案，跳轉到1;否則，該值是商定的。 以下是一些示例，示例 1 如下所示：
Paxos 演算法示例 1
在圖中，p 表示準備階段，a 表示接受階段。 3.1 表示提案 ID 為 31，其中 3 是時間戳，1 是伺服器 ID。 x 和 y 表示建議值。
第 3 頁中的示例 11 獲得多數，其值 （x） 被接受，然後 p 45 學習 value（x） 並接受。
Paxos 演算法示例 2
例項 2 中的第 3 頁1 不被多數人接受（只有 S3 接受），但 P 45 學習，第 4 頁5 將其值替換為 y 和 x， accept（x）。
Paxos 演算法示例 3
第 3 頁中的例項 31 不被多數人接受（只有 S1 接受），也不被 P 4 接受5 學會了。 由於第 4 頁5 提出，如果沒有返回值，則 p 45 可以接受自己的值 （y）。 後續工作 p 3接受 1 的 （x） 將失敗，已經接受的 s1 將被覆蓋。
PaxOS 演算法可以形成永無止境的活鎖，如以下示例所示：
PaxOS 演算法形成乙個活鎖。
回顧這兩個承諾之一，接受方不再回答提案 ID 小於或等於當前請求的準備請求。 表示如果提案 ID 大於當前請求，則需要應答 Prepare 請求。
兩個提議者交替準備成功和接受失敗，形成乙個活鎖。
基本的Paxos演算法只能在乙個值上形成乙個解析，而解析的形成至少需要兩次網路往返，在高併發的情況下，可能需要更多的網路往返，在極端情況下，甚至可能形成活鎖。 如果要確定連續的多個值，Basic PaxOS 將無法解決問題。 因此，Basic PaxOS 幾乎完全用於理論研究，而不是直接應用於實際工程。
在實踐中，幾乎總是需要連續確定多個值，並且希望提高效率。 Multi-Paxos 就是為了解決這個問題而設計的。 Multi-PaxOS 基於 Basic PaxOS，並進行了兩項改進：
對於要確定的每個值，執行 Paxos 演算法的例項以形成解像度。 每個 PaxOS 例項都使用唯一的例項 ID 進行標識。 在所有提案者中選出一名領導者，領導者將提案唯一地提交給接受者進行投票。 這消除了提議者的競爭，解決了活鎖問題。 如果系統中只有乙個領導者提交乙個值，則可以跳過準備階段，從而將兩個階段變成乙個階段並提高效率。 
Multi-Paxos 程序。
Multi-PaxOS 首先需要選出乙個領導者，而乙個領導者的確定也是決策的形成，所以可以執行乙個基本的 Paxos 例項來選舉領導者。 領導當選後，只有領導才能提交提案，領導下台後服務暫時不可用，需要連任才能繼續服務。 如果系統中只有一位領導者提交提案，則可以跳過準備階段。
Multi-PaxOS 將準備階段的範圍改為後續 leader 提交的所有例項，讓 leader 的後續提交只需要執行一次準備階段，後續階段只需要執行接受階段，將兩個階段變成乙個階段，提高效率。 為了區分連續提交的多個例項，每個例項都由乙個例項 ID 標識，該 ID 由領導者在本地遞增。
Multi-PaxOS 允許多個自認為領導者的節點在不影響其安全性的情況下同時提交提案，這是對 Basic PaxOS 的降級。
Chubby 和 Boxwood 都使用 Multi-Paxos。 ZooKeeper 使用的 zab 也是 multi-paxos 的變體。
PaxOS演算法的設計過程從正確性開始，對於分布式一致性問題，很多程序提出（提出）不同的值，共識演算法保證最後只選擇乙個值，安全性表示如下：
只能選擇建議的值。 只一選擇值。 該過程將僅被告知已確認選擇的值。 Paxos 的設計就以這些約束為出發點，只要演算法最終滿足這些約束，就不需要證明正確性。 PaxOS 演算法中有三種型別的參與者：提議者、接受者和學習者，實現中的每個過程通常同時扮演所有三個角色。
投標人向承兌人提出建議，以保證最多只有一提案必須被半數以上的接受者接受，每個接受者只能接受乙個值。
為了正常執行（必須接受乙個值），Paxos 演算法：
p1：接受者必須接受它收到的第乙個提案。
先到先得，價格合理。 但這就產生了乙個問題，如果乙個以上的提案人同時提出，很可能不會達成一致，因為沒有乙個提議被超過一半的接受者接受，因此，接受者必須能夠接受多個提案，不同的提案用不同的數字來區分，當乙個提案被超過一半的接受者接受時， 這個提案被選中了。
由於接受者被允許接受多個提案，因此最終可能會選擇多個不同的值，這違反了安全要求
P2：如果選擇了值為 V 的提案，則任何具有較高數字的選定提案也必須具有 V 值。
只要演算法同時滿足p1跟p2，安全有保障。 p2這是乙個寬泛的約定，根本沒有演算法細節，我們將進一步擴充套件它：
P2A：如果選擇值為 V 的提案，那麼對於所有接受者來說，他們接受的任何具有較高數字的提案也必須具有 V 值。
如果滿意p2a那麼你一定滿意p2，顯然，因為只有先被接受才有可能最終被選中。 但p2a它仍然很難實現，因為接受者很可能不知道之前選擇的提案（恰好在接受它的大多數人之外），所以它走得更遠：
P2B：如果選擇值為 V 的提案，那麼對於所有提案者來說，任何具有更高數字的提案也必須具有 V 值。
再往前走：
P2C：為了提出乙個值為 v 且數量為 n 的提案，必須有一組包含一半以上接受者的 s，滿足 （1） s 中沒有乙個接受者接受過數量小於 n 的提案，或 （2） v 並且 s 中的接受者接受了數量少於 n 的提案數量最多。
滿意p2c即滿意p2b即滿意p2a即滿意p2。至此，Paxos 提出了 Proposer 的執行流程，以滿足：p2c
提議者選擇乙個新的數字 n 並向超過一半的接受者傳送請求資訊，接受者回覆：（a） 承諾不接受數量小於 n 的提案，以及 （b） 它接受的人數小於 n 的最大提案（如果有的話）。 該請求稱為準備請求。 如果提議者收到半數以上接受者的答覆，則可以提出乙個提案價值的提案，該提案的價值是收到的答覆中編號最多的，如果沒有這樣的價值，它可以自由提出任何價值。 向收到回覆的接受者傳送接受請求，要求他們接受提議的提案。 仔細看看 Proposer 的執行過程，它非常適合p2c，但你可能也注意到了，當多個提議者同時執行時，可能會出現無法成功接受提案的情況（第一步是隨著數量的增加交替完成），這就是 Paxos 演算法的活體問題，或者說是“livelock”，建議通過向提議者介紹主演算法來選擇傑出的提議者，以提出解決這個問題的提案， 但即使在多個提議者同時提出的情況下，Paxos 演算法也可以保證安全。
讓我們來看看接受者的執行過程，以及我們對此的處理p2做和我們一樣的事情p1進行擴充套件：
p1a：當且僅當接受者沒有回覆具有較大數字的準備訊息時，接受者才能接受編號為 n 的提案。
容易看到，p1a是的p1，對於接受者：
當收到準備請求時，如果其編號 n 大於先前收到的準備訊息，則會回覆該請求。 當收到接受請求時，它接受提案，並且僅當它沒有回覆具有較大數字的準備訊息時才進行回覆。 以上涵蓋了滿意度p1a跟p2b一整套一致性演算法。