Paxos算法

維基百科,自由的百科全書
跳至導覽 跳至搜尋

Paxos算法萊斯利·蘭伯特(英語:Leslie LamportLaTeX中的「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覺得同行無法接受他的幽默感,於是用容易接受的方法重新表述了一遍。