Paxos算法
此條目需要補充更多來源。 (2019年12月21日) |
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島上的議員是不會反對其他議員提出的決議的。
對應於分布式系統,議員對應於各個節點,制定的法律過程對應於系統的狀態。各個節點需要儘量保持一致的狀態,對應各議員推進法律決議推進。議員和服務員的不確定性對應於節點和消息傳遞通道的不可靠性。
算法
[編輯]算法的提出與證明
[編輯]首先將議員的角色分為 proposers,acceptors,和 learners(允許身兼數職)。proposers 提出提案,提案信息包括提案編號和提議的 value;acceptor 收到提案後可以接受(accept)提案,若提案獲得多數派(majority)的 acceptors 的接受,則稱該提案被批准(chosen);learners 只能「學習」被批准的提案。劃分角色後,就可以更精確的定義問題:
- 決議(value)只有在被 proposers 提出後才能被批准(未經批准的決議稱為「提案(proposal)」);
- 在一次 Paxos 算法的執行實例中,只批准(chosen)一個 value;
- 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的提案。
現在已經可以提出完整的算法了。
決議的提出與批准
[編輯]通過一個決議分為兩個階段:
- prepare階段:
- proposer選擇一個提案編號n並將prepare請求發送給acceptors中的一個多數派;
- acceptor收到prepare消息後,如果提案的編號大於它已經回復的所有prepare消息(回復消息表示接受accept),則acceptor將自己上次接受的提案回復給proposer,並承諾不再回復小於n的提案;
- 批准階段:
- 當一個proposer收到了多數acceptors對prepare的回覆後,就進入批准階段。它要向回復prepare請求的acceptors發送accept請求,包括編號n和根據P2c決定的value(如果根據P2c沒有已經接受的value,那麼它可以自由決定value)。
- 在不違背自己向其他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公司)在其分布式鎖服務中應用了Multi-Paxos算法[4]。Chubby lock應用於大表(Bigtable),後者在谷歌公司所提供的各項服務中得到了廣泛的應用[5]。
谷歌公司(Google公司)在其分布式數據庫spanner中使用Multi-Paxos作為分布式共識保證的基礎組件 [6]
Apache ZooKeeper 使用一個類Multi-Paxos的共識算法作為底層存儲協同的機制。
參考文獻
[編輯]- ^ Lamport本人在http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos (頁面存檔備份,存於網際網路檔案館) 中描寫了他用9年時間發表這個算法的前前後後
- ^ ([//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.]
- ^ 中国专利局的相关页面. [2020-09-26]. (原始內容存檔於2009-08-26).
- ^ The Chubby lock service for loosely-coupled distributed systems (PDF). [2007-08-10]. (原始內容存檔 (PDF)於2008-08-28).
- ^ Bigtable: A Distributed Storage System for Structured Data (PDF). [2007-08-10]. (原始內容存檔 (PDF)於2009-12-13).
- ^ Spanner: Google's Globally-Distributed Database. [2018-12-30]. (原始內容存檔於2018-12-30).
外部連結
[編輯]- The Part-Time Parliament(頁面存檔備份,存於網際網路檔案館) ── Lamport於1998年發表在ACM Transactions on Computer Systems。
- 註:這是該算法第一次公開發表。
- Paxos Made Simple(頁面存檔備份,存於網際網路檔案館),2001年。
- 註:Lamport覺得同行無法接受他的幽默感,於是用容易接受的方法重新表述了一遍。