Paxos算法

維基百科，自由的百科全書

Paxos算法是萊斯利·蘭伯特（英語：Leslie Lamport，LaTeX中的「La」）於1990年提出的一種基於消息傳遞且具有高度容錯特性的共識（consensus）算法。[1]

需要注意的是，Paxos常被誤稱為「一致性算法」。但是「一致性（consistency）」和「共識（consensus）」並不是同一個概念。Paxos是一個共識（consensus）算法。[2]

問題和假設

分佈式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。基於消息傳遞通信模型的分佈式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複。在最普通的 Paxos 場景中，先不考慮可能出現「消息篡改」（即拜占庭錯誤的情況）。Paxos 算法解決的問題是在一個可能發生前述異常（即排除消息篡改之外的其他任何異常）的分佈式系統中，如何對某個值的看法相同，保證無論發生以上任何異常，都不會破壞決議的共識機制。一個典型的場景是，在一個分佈式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「共識算法」以保證每個節點看到的指令一致。一個通用的共識算法可以應用在許多場景中，是分佈式計算中的重要問題。因此從20世紀80年代起對於共識算法的研究就沒有停止過。

為描述Paxos算法，Lamport虛擬了一個叫做Paxos的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人願意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現，也無法承諾批准決議或者傳遞消息的時間。但是這裏假設沒有拜占庭將軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）；只要等待足夠的時間，消息就會被傳到。另外，Paxos島上的議員是不會反對其他議員提出的決議的。

對應於分佈式系統，議員對應於各個節點，制定的法律對應於系統的狀態。各個節點需要進入一個一致的狀態，例如在獨立Cache的對稱多處理器系統中，各個處理器讀內存的某個字節時，必須讀到同樣的一個值，否則系統就違背了一致性的要求。一致性要求對應於法律條文只能有一個版本。議員和服務員的不確定性對應於節點和消息傳遞通道的不可靠性。

算法

算法的提出與證明

首先將議員的角色分為 proposers，acceptors，和 learners（允許身兼數職）。proposers 提出提案，提案信息包括提案編號和提議的 value；acceptor 收到提案後可以接受（accept）提案，若提案獲得多數派（majority）的 acceptors 的接受，則稱該提案被批准（chosen）；learners 只能「學習」被批准的提案。劃分角色後，就可以更精確的定義問題：

  1. 決議（value）只有在被 proposers 提出後才能被批准（未經批准的決議稱為「提案（proposal）」）；
  2. 在一次 Paxos 算法的執行實例中，只批准（chosen）一個 value；
  3. learners 只能獲得被批准（chosen）的 value。
在 Leslie Lamport 之後發表的paper中將 majority 替換為更通用的 quorum 概念，但在描述classic paxos的論文  Paxos made simple（頁面存檔備份，存於互聯網檔案館） 中使用的還是majority的概念。

另外還需要保證 progress。這一點以後再討論。

作者通過不斷加強上述3個約束（主要是第二個）獲得了 Paxos 算法。

批准 value 的過程中，首先 proposers 將 value 發送給 acceptors，之後 acceptors 對 value 進行接受（accept）。為了滿足只批准一個 value 的約束，要求經「多數派（majority）」接受的 value 成為正式的決議（稱為「批准」決議）。這是因為無論是按照人數還是按照權重劃分，兩組「多數派」至少有一個公共的 acceptor，如果每個 acceptor 只能接受一個 value，約束2就能保證。

於是產生了一個顯而易見的新約束： 

P1：一个 acceptor 必须接受（accept）第一次收到的提案。

注意 P1 是不完備的。如果恰好一半 acceptor 接受的提案具有 value A，另一半接受的提案具有 value B，那麼就無法形成多數派，無法批准任何一個 value。

約束2並不要求只批准一個提案，暗示可能存在多個提案。只要提案的 value 是一樣的，批准多個提案不違背約束2。於是可以產生約束 P2： 

P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。

註：通過某種方法可以為每個提案分配一個編號，在提案之間建立一個全序關係，所謂「之後」都是指所有編號更大的提案。

如果 P1 和 P2 都能夠保證，那麼約束2就能夠保證。

批准一個 value 意味着多個 acceptor 接受（accept）了該 value。因此，可以對 P2 進行加強： 

P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 acceptor 再次接受（accept）的提案必须具有 value v。

由於通信是異步的，P2a 和 P1 會發生衝突。如果一個 value 被批准後，一個 proposer 和一個 acceptor 從休眠中甦醒，前者提出一個具有新的 value 的提案。根據 P1，後者應當接受，根據 P2a，則不應當接受，這種場景下 P2a 和 P1 有矛盾。於是需要換個思路，轉而對 proposer 的行為進行約束： 

P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 proposer 提出的提案必须具有 value v。

由於 acceptor 能接受的提案都必須由 proposer 提出，所以 P2b 蘊涵了 P2a，是一個更強的約束。

但是根據 P2b 難以提出實現手段。因此需要進一步加強 P2b。

假設一個編號為 m 的 value v 已經獲得批准（chosen），來看看在什麼情況下對任何編號為 n（n>m）的提案都含有 value v。因為 m 已經獲得批准（chosen），顯然存在一個 acceptors 的多數派 C，他們都接受（accept）了v。考慮到任何多數派都和 C 具有至少一個公共成員，可以找到一個蘊涵 P2b 的約束 P2c： 

P2c：如果一个编号为 n 的提案具有 value v，该提案被提出（issued），那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 
的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

可以用數學歸納法證明 P2c 蘊涵 P2b：

假設具有value v的提案m獲得批准，當n=m+1時，採用反證法，假如提案n不具有value v，而是具有value w，根據P2c，則存在一個多數派S1，要麼他們中沒有人接受過編號小於n的任何提案，要麼他們已經接受的所有編號小於n的提案中編號最大的那個提案是value w。由於S1和通過提案m時的多數派C之間至少有一個公共的acceptor，所以以上兩個條件都不成立，導出矛盾從而推翻假設，證明了提案n必須具有value v；

若（m+1）..（N-1）所有提案都具有value v，採用反證法，假如新提案N不具有value v，而是具有value w',根據P2c，則存在一個多數派S2，要麼他們沒有接受過m..（N-1）中的任何提案，要麼他們已經接受的所有編號小於N的提案中編號最大的那個提案是value w'。由於S2和通過m的多數派C之間至少有一個公共的acceptor，所以至少有一個acceptor曾經接受了m，從而也可以推出S2中已接受的所有編號小於n的提案中編號最大的那個提案的編號範圍在m..（N-1）之間，而根據初始假設，m..（N-1）之間的所有提案都具有value v，所以S2中已接受的所有編號小於n的提案中編號最大的那個提案肯定具有value v，導出矛盾從而推翻新提案N不具有value v的假設。根據數學歸納法，我們證明了若滿足P2c，則P2b一定滿足。

P2c是可以通過消息傳遞模型實現的。另外，引入了P2c後，也解決了前文提到的P1不完備的問題。

算法的內容

要滿足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的提案。

現在已經可以提出完整的算法了。

決議的提出與批准

通過一個決議分為兩個階段：

  1. prepare階段：
    1. proposer選擇一個提案編號n並將prepare請求發送給acceptors中的一個多數派；
    2. acceptor收到prepare消息後，如果提案的編號大於它已經回復的所有prepare消息(回復消息表示接受accept)，則acceptor將自己上次接受的提案回復給proposer，並承諾不再回復小於n的提案；
  2. 批准階段：
    1. 當一個proposer收到了多數acceptors對prepare的回覆後，就進入批准階段。它要向回復prepare請求的acceptors發送accept請求，包括編號n和根據P2c決定的value（如果根據P2c沒有已經接受的value，那麼它可以自由決定value）。
    2. 在不違背自己向其他proposer的承諾的前提下，acceptor收到accept請求後即批准這個請求。

這個過程在任何時候中斷都可以保證正確性。例如如果一個proposer發現已經有其他proposers提出了編號更高的提案，則有必要中斷這個過程。因此為了優化，在上述prepare過程中，如果一個acceptor發現存在一個更高編號的提案，則需要通知proposer，提醒其中斷這次提案。

實例

用實際的例子來更清晰地描述上述過程：

有A1, A2, A3, A4, A5 5位議員，就稅率問題進行決議。議員A1決定降稅率,因此它向所有人發出一個草案。這個草案的內容是： 

现有的税率是什么?如果没有决定，我来决定一下. 提出时间：本届议会第3年3月15日;提案者：A1

在最簡單的情況下，沒有人與其競爭;信息能及時順利地傳達到其它議員處。

於是, A2-A5回應： 

我已收到你的提案，等待最终批准

而A1在收到2份回復後就發佈最終決議： 

税率已定为10%,新的提案不得再讨论本问题。

這實際上退化為二階段提交協議。

現在我們假設在A1提出提案的同時, A5決定將稅率定為20%: 

现有的税率是什么?如果没有决定，我来决定一下.时间：本届议会第3年3月16日;提案者：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的行為將決定批准哪一個。

在討論之前我們要明確一點，提案是全局有序的。在這個示例中，是說每個提案提出的日期都不一樣。即第3年3月15日只有A1的提案；第3年3月16日只有A5的提案。不可能在某一天存在兩個提案。

情況一

假設A1的提案先送到A3處，而A5的侍從決定放假一段時間。於是A3接受並派出了侍從. A1等到了兩位侍從，加上它自己已經構成一個多數派，於是稅率10%將成為決議. A1派出侍從將決議送到所有議員處： 

税率已定为10%,新的提案不得再讨论本问题。

A3在很久以後收到了來自A5的提案。由於稅率問題已經討論完畢，開始討論某些議員在第3年3月17日提出的議案。因此這個3月16日提出的議案他不去理會。他自言自語地抱怨一句： 

这都是老问题了，没有必要讨论了。
情況二

依然假設A1的提案先送到A3處，但是這次A5的侍從不是放假了，只是中途耽擱了一會。這次, A3依然會將"接受"回復給A1.但是在決議成型之前它又收到了A5的提案。則：

1.如果A5提案的提出時間比A1的提案更晚一些，這裏確實滿足這種情況，因為3月16日晚於3月15日。，則A3回覆： 

我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。

於是, A1和A5都收到了足夠的回覆。這時關於稅率問題就有兩個提案在同時進行。但是A5知道之前有人提出稅率為10%.於是A1和A5都會向全體議員廣播： 

 税率已定为10%,新的提案不得再讨论本问题。

共識到了保證。

2. 如果A5提案的提出時間比A1的提案更早一些。假設A5的提案是3月14日提出，則A3直接不理會。 

 A1不久后就会广播税率定为10%.

決議的發佈

一個顯而易見的方法是當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中消息流的圖形表示

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算法申請了專利[3]。但專利中公開的技術和本文所描述的不盡相同。

谷歌公司（Google公司）在其分佈式鎖服務（英語：Distributed lock manager）中應用了Multi-Paxos算法[4]。Chubby lock應用於大表（Bigtable），後者在谷歌公司所提供的各項服務中得到了廣泛的應用[5]。

谷歌公司（Google公司）在其分佈式數據庫spanner中使用Multi-Paxos作為分佈式共識保證的基礎組件 [6]

Apache ZooKeeper 使用一個類Multi-Paxos的共識算法作為底層存儲協同的機制。

參考文獻

  1. ^ Lamport本人在http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos （頁面存檔備份，存於互聯網檔案館） 中描寫了他用9年時間發表這個算法的前前後後
  2. ^ （[//web.archive.org/web/20180712150920/http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/past/03F/notes/paxos-simple.pdf 頁面存檔備份，存於互聯網檔案館） Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.]
  3. ^ 中国专利局的相关页面. [2020-09-26]. （原始內容存檔於2009-08-26）. 
  4. ^ The Chubby lock service for loosely-coupled distributed systems (PDF). [2007-08-10]. （原始內容存檔 (PDF)於2008-08-28）. 
  5. ^ Bigtable: A Distributed Storage System for Structured Data (PDF). [2007-08-10]. （原始內容存檔 (PDF)於2009-12-13）. 
  6. ^ Spanner: Google's Globally-Distributed Database. [2018-12-30]. （原始內容存檔於2018-12-30）. 

外部連結

註：這是該算法第一次公開發表。
註：Lamport覺得同行無法接受他的幽默感，於是用容易接受的方法重新表述了一遍。
取自 "https://zh.wikipedia.org/w/index.php?title=Paxos算法&oldid=71833763"