Paxos算法

問題和假設

分布式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。基於消息傳遞通信模型的分布式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複，在基礎 Paxos 場景中，先不考慮可能出現消息篡改即拜占庭錯誤的情況。Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性算法」以保證每個節點看到的指令一致。一個通用的一致性算法可以應用在許多場景中，是分布式計算中的重要問題。因此從20世紀80年代起對於一致性算法的研究就沒有停止過。
為描述Paxos算法，Lamport虛擬了一個叫做Paxos的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人願意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現，也無法承諾批准決議或者傳遞消息的時間。但是這裡假設沒有拜占庭將軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）；只要等待足夠的時間，消息就會被傳到。另外，Paxos島上的議員是不會反對其他議員提出的決議的。
對應於分布式系統，議員對應於各個節點，制定的法律對應於系統的狀態。各個節點需要進入一個一致的狀態，例如在獨立Cache的對稱多處理器系統中，各個處理器讀內存的某個字節時，必須讀到同樣的一個值，否則系統就違背了一致性的要求。一致性要求對應於法律條文只能有一個版本。議員和服務員的不確定性對應於節點和消息傳遞通道的不可靠性。

算法的內容

要滿足P2c的約束，proposer提出一個提案前，首先要和足以形成多數派的acceptors進行通信，獲得他們進行的最近一次接受（accept）的提案（prepare過程），之後根據回收的信息決定這次提案的value，形成提案開始投票。當獲得多數acceptors接受（accept）後，提案獲得批准（chosen），由acceptor將這個消息告知learner。這個簡略的過程經過進一步細化後就形成了Paxos算法。
在一個paxos實例中，每個提案需要有不同的編號，且編號間要存在全序關係。可以用多種方法實現這一點，例如將序數和proposer的名字拼接起來。如何做到這一點不在Paxos算法討論的範圍之內。
如果一個沒有chosen過任何proposer提案的acceptor在prepare過程中回答了一個proposer針對提案n的問題，但是在開始對n進行投票前，又接受（accept）了編號小於n的另一個提案（例如n-1），如果n-1和n具有不同的value，這個投票就會違背P2c。因此在prepare過程中，acceptor進行的回答同時也應包含承諾：不會再接受（accept）編號小於n的提案。這是對P1的加強：
P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案。
現在已經可以提出完整的算法了。

實例

用實際的例子來更清晰地描述上述過程：
有A1, A2, A3, A4, A5 5位議員，就稅率問題進行決議。議員A1決定將稅率定為10%,因此它向所有人發出一個草案。這個草案的內容是：
现有的税率是什么?如果没有决定，则建议将其定为10%.时间：本届议会第3年3月15日;提案者：A1
在最簡單的情況下，沒有人與其競爭;信息能及時順利地傳達到其它議員處。
於是, A2-A5回應：
我已收到你的提案，等待最终批准
而A1在收到2份回復後就發布最終決議：
税率已定为10%,新的提案不得再讨论本问题。
這實際上退化為二階段提交協議。
現在我們假設在A1提出提案的同時, A5決定將稅率定為20%:
现有的税率是什么?如果没有决定，则建议将其定为20%.时间：本届议会第3年3月15日;提案者：A5
草案要通過侍從送到其它議員的案頭. A1的草案將由4位侍從送到A2-A5那裡。現在，負責A2和A3的侍從將草案順利送達，負責A4和A5的侍從則不上班. A5的草案則順利的送至A4和A3手中。
現在, A1, A2, A3收到了A1的提案; A4, A3, A5收到了A5的提案。按照協議, A1, A2, A4, A5將接受他們收到的提案，侍從將拿著
我已收到你的提案，等待最终批准
的回覆回到提案者那裡。
而A3的行為將決定批准哪一個。

情況一

假設A1的提案先送到A3處，而A5的侍從決定放假一段時間。於是A3接受並派出了侍從. A1等到了兩位侍從，加上它自己已經構成一個多數派，於是稅率10%將成為決議. A1派出侍從將決議送到所有議員處：
税率已定为10%,新的提案不得再讨论本问题。
A3在很久以後收到了來自A5的提案。由於稅率問題已經討論完畢，他決定不再理會。但是他要抱怨一句：
税率已在之前的投票中定为10%,你不要再来烦我!
這個回復對A5可能有幫助，因為A5可能因為某種原因很久無法與與外界聯繫了。當然更可能對A5沒有任何作用，因為A5可能已經從A1處獲得了剛才的決議。

情況二

依然假設A1的提案先送到A3處，但是這次A5的侍從不是放假了，只是中途耽擱了一會。這次, A3依然會將"接受"回復給A1.但是在決議成型之前它又收到了A5的提案。這時協議有兩種處理方式：
1.如果A5的提案更早，按照傳統應該由較早的提案者主持投票。現在看來兩份提案的時間一樣（本屆議會第3年3月15日）。但是A1是個惹不起的大人物。於是A3回覆：
我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。
於是, A1和A5都收到了足夠的回覆。這時關於稅率問題就有兩個提案在同時進行。但是A5知道之前有人提出稅率為10%.於是A1和A5都會向全體議員廣播：
 税率已定为10%,新的提案不得再讨论本问题。
一致性得到了保證。
2. A5是個無足輕重的小人物。這時A3不再理會他, A1不久後就會廣播稅率定為10%.

情況三

在這個情況中，我們將看見，根據提案的時間及提案者的權勢決定是否應答是有意義的。在這裡，時間和提案者的權勢就構成了給提案編號的依據。這樣的編號符合"任何兩個提案之間構成偏序"的要求。
A1和A5同樣提出上述提案，這時A1可以正常聯繫A2和A3; A5也可以正常聯繫這兩個人。這次A2先收到A1的提案; A3則先收到A5的提案. A5更有權勢。
在這種情況下，已經回答A1的A2發現有比A1更有權勢的A5提出了稅率20%的新提案，於是回復A5說：
我已收到您的提案，等待最终批准。
而回復了A5的A3發現新的提案者A1是個小人物，不予理會。
A1沒有達到多數，A5達到了，於是A5將主持投票，決議的內容是A5提出的稅率20%.
如果A3決定平等地對待每一位議員，對A1做出"你之前有人提出將稅率定為20%"的回覆，則將造成混亂。這種情況下A1和A5都將試圖主持投票，但是這次兩份提案的內容不同。
這種情況下, A3若對A1進行回復，只能說：
有更大的人物关注此事，请等待他做出决定。
另外，在這種情況下, A4與外界失去了聯繫。等到他恢復聯繫，並需要得知稅率情況時，他（在最簡單的協議中）將提出一個提案：
现有的税率是什么?如果没有决定，则建议将其定为15%.时间：本届议会第3年4月1日;提案者：A4
這時，（在最簡單的協議中）其他議員將會回覆：
税率已在之前的投票中定为20%,你不要再来烦我!

決議的發布

一個顯而易見的方法是當acceptors批准一個value時，將這個消息發送給所有learners。但是這個方法會導致消息量過大。
由於假設沒有Byzantine failures，learners可以通過別的learners獲取已經通過的決議。因此acceptors只需將批准的消息發送給指定的某一個learner，其他learners向它詢問已經通過的決議。這個方法降低了消息量，但是指定learner失效將引起系統失效。
因此acceptors需要將accept消息發送給learners的一個子集，然後由這些learners去通知所有learners。
但是由於消息傳遞的不確定性，可能會沒有任何learner獲得了決議批准的消息。當learners需要了解決議通過情況時，可以讓一個proposer重新進行一次提案。注意一個learner可能兼任proposer。

Progress的保證

根據上述過程當一個proposer發現存在編號更大的提案時將終止提案。這意味著提出一個編號更大的提案會終止之前的提案過程。如果兩個proposer在這種情況下都轉而提出一個編號更大的提案，就可能陷入活鎖，違背了Progress的要求。一般活鎖可以通過 隨機睡眠-重試 的方法解決。這種情況下的解決方案是選舉出一個leader，僅允許leader提出提案。但是由於消息傳遞的不確定性，可能有多個proposer自認為自己已經成為leader。Lamport在The Part-Time Parliament一文中描述並解決了這個問題。

Multi-Paxos

Paxos的典型部署需要一組連續的被接受的值（value），作為應用到一個分布式狀態機的一組命令。如果每個命令都通過一個Basic Paxos算法實例來達到一致，會產生大量開銷。
如果Leader是相對穩定不變的，第1階段就變得不必要。 這樣，系統可以在接下來的Paxos算法實例中，跳過的第1階段，直接使用同樣的Leader。
為了實現這一目的，在同一個Leader執行每輪Paxos算法時，提案編號 I 每次遞增一個值，並與每個值一起發送。Multi-Paxos在沒有故障發生時，將消息延遲(從propose階段到learn階段)從4次延遲降低為2次延遲。

Multi-Paxos 沒有失敗的情況

在下面的圖中，只顯示了基本Paxos協議的一個實例(或「執行」)和一個初始Leader(Proposer)。注意，Multi-Paxos使用幾個Basic Paxos的實例。
Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
式中V = (Va, Vb, Vc) 中最新的一個。

跳過階段1時的Multi-Paxos

在這種情況下，Basic Paxos的後續實例(由I+1表示)使用相同的Leader，因此，包含在Prepare和Promise的階段1(Basic Paxos協議的這些後續實例)將被跳過。注意，這裡要求Leader應該是穩定的，即它不應該崩潰或改變。
Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Fast-Paxos

Fast-Paxos將Basic-Paxos進行了推廣，以減少端到端消息延遲。在Basic-Paxos中，從客戶端發起請求開始，到Learn階段結束的消息延遲是3個消息延遲。而Fast-Paxos允許2個消息延遲，但要求：
(1)系統由3f+ 1個Acceptor組成，以容忍最多f個錯誤(而不是Basic-Paxos的2f+1)；
(2)客戶端需要直接將請求發送到多個目標。
直觀上，如果Leader沒有提議任何value，那麼客戶可以直接發送Accept消息到向接收方發。Acceptor會像Basic-Paxos一樣運行，向Leader和每個Learner發送Accepted的消息，從而實現從客戶端到Learner的兩消息延遲。
如果Leader檢測到衝突，它通過發起新一輪投票，並發送Accept消息來解決衝突，通常是一個Accepted消息。這種有協調者參與的衝突恢復機制需要4個從客戶端到Learner的消息延遲。
如果Leader提前指定了一種衝突恢復機制，就可以實現另一種優化，它允許Acceptors自己執行衝突恢復。因此，無協調的衝突恢復可能實現三個消息延遲(如果所有的Learner都是接收者，那麼只有兩個消息延遲)。

消息流: Fast-Paxos，無衝突

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

消息流:Fast-Paxos，衝突的建議

有協調這參與的衝突恢復。注意:協議沒有指定如何處理被丟棄的客戶端請求。
Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
無協調者參與的相衝突恢復：
Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

消息流:無協調者的衝突恢復、角色崩潰的Fast-Paxos

(合併的Acceptor/Learner)
Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

應用 

微軟公司為簡化的Paxos算法申請了專利。但專利中公開的技術和本文所描述的不盡相同。
谷歌公司（Google公司）在其分布式鎖服務中應用了Multi-Paxos算法。Chubby lock應用於大表（Bigtable），後者在谷歌公司所提供的各項服務中得到了廣泛的應用。
谷歌公司（Google公司）在其分布式資料庫spanner中使用Multi-Paxos作為分布式一致性保證的基礎組件 
Apache ZooKeeper 使用一個類Multi-Paxos的一致性算法作為底層存儲協同的機制。