Paxos 算法與 Raft 算法

Paxos 問題是指分佈式的系統中存在故障(crash fault),但不存在惡意(corrupt)節點的場景(即可能消息丟失或重複,但無錯誤消息)下的共識達成問題。這也是分佈式共識領域最為常見的問題。因為最早是 Leslie Lamport 用 Paxon 島的故事模型來進行描述,而得以命名。解決 Paxos 問題的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 算法

1990 年由 Leslie Lamport 在論文《The Part-time Parliament》中提出的 Paxos 共識算法,在工程角度實現了一種最大化保障分佈式系統一致性(存在極小的概率無法實現一致)的機制。Paxos 算法被廣泛應用在 Chubby、ZooKeeper 這樣的分佈式系統中。Leslie Lamport 作為分佈式系統領域的早期研究者,因為相關傑出貢獻獲得了 2013 年度圖靈獎。

論文中為了描述問題編造了一個虛構故事:在古希臘的 Paxon 島,議會如何通過表決來達成共識。議員們通過信使傳遞消息來對議案進行表決。但議員可能離開,信使可能走丟,甚至重複傳遞消息。

Paxos 是首個得到證明並被廣泛應用的共識算法,其原理類似 兩階段提交 算法,進行了泛化和擴展,通過消息傳遞來逐步消除系統中的不確定狀態。

作為後來很多共識算法(如 Raft、ZAB 等)的基礎,Paxos 算法基本思想並不複雜,但最初論文中描述比較難懂,甚至連發表也幾經波折。2001 年,Leslie Lamport 還專門發表論文《Paxos Made Simple》進行重新解釋。

基本原理

算法中存在三種邏輯角色的節點,在實現中同一節點可以擔任多個角色。

  • 提案者(Proposer):提出一個提案,等待大家批准(Chosen)為結案(Value)。系統中提案都擁有一個自增的唯一提案號。往往由客戶端擔任該角色。

  • 接受者(Acceptor):負責對提案進行投票,接受(Accept)提案。往往由服務端擔任該角色。

  • 學習者(Learner):獲取批准結果,並幫忙傳播,不參與投票過程。可為客戶端或服務端。

算法需要滿足安全性(Safety) 和存活性(Liveness)兩方面的約束要求。實際上這兩個基礎屬性也是大部分分佈式算法都該考慮的。

  • Safety:保證決議(Value)結果是對的,無歧義的,不會出現錯誤情況。

    • 只有是被提案者提出的提案才可能被最終批准;

    • 在一次執行中,只批准(chosen)一個最終決議。被多數接受(accept)的結果成為決議;

  • Liveness:保證決議過程能在有限時間內完成。

    • 決議總會產生,並且學習者能獲得被批准的決議。

基本思路類似兩階段提交:多個提案者先要爭取到提案的權利(得到大多數接受者的支持);成功的提案者發送提案給所有人進行確認,得到大部分人確認的提案成為批准的結案。

Paxos 並不保證系統總處在一致的狀態。但由於每次達成共識至少有超過一半的節點參與,這樣最終整個系統都會獲知共識結果。一個潛在的問題是提案者在提案過程中出現故障,這可以通過超時機制來緩解。極為湊巧的情況下,每次新一輪提案的提案者都恰好故障,又或者兩個提案者恰好依次提出更新的提案,則導致活鎖,系統會永遠無法達成共識(實際發生概率很小)。

Paxos 能保證在超過一半的節點正常工作時,系統總能以較大概率達成共識。讀者可以試著自己設計一套非拜占庭容錯下基於消息傳遞的異步共識方案,會發現在滿足各種約束情況下,算法過程總會十分類似 Paxos 的過程。這也是為何 Google Chubby 的作者 Mike Burrows 說:“這個世界上只有一種一致性算法,那就是 Paxos(There is only one consensus protocol, and that's Paxos)”。

下面,由簡單情況逐步推廣到一般情況來探討算法過程。

單個提案者+多接受者

如果系統中限定只允許某個特定節點是提案者,那麼共識結果很容易能達成(只有一個方案,要麼達成,要麼失敗)。提案者只要收到了來自多數接受者的投票,即可認為通過,因為系統中不存在其他的提案。

但此時一旦提案者故障,則整個系統無法工作。

多個提案者+單個接受者

限定某個特定節點作為接受者。這種情況下,共識也很容易達成,接受者收到多個提案,選第一個提案作為決議,發送給其它提案者即可。

缺陷也是容易發生單點故障,包括接受者故障或首個提案者節點故障。

以上兩種情形其實類似主從模式,雖然不那麼可靠,但因為原理簡單而被廣泛採用。

當提案者和接受者都推廣到多個的情形,會出現一些挑戰。

多個提案者+多個接受者

既然限定單提案者或單接受者都會出現故障,那麼就得允許出現多個提案者和多個接受者。問題一下子變得複雜了。

一種情況是同一時間片段(如一個提案週期)內只有一個提案者,這時可以退化到單提案者的情形。需要設計一種機制來保障提案者的正確產生,例如按照時間、序列、或者大家猜拳(出一個參數來比較)之類。考慮到分佈式系統要處理的工作量很大,這個過程要儘量高效,滿足這一條件的機制非常難設計。

另一種情況是允許同一時間片段內可以出現多個提案者。那同一個節點可能收到多份提案,怎麼對他們進行區分呢?這個時候採用只接受第一個提案而拒絕後續提案的方法也不適用。很自然的,提案需要帶上不同的序號。節點需要根據提案序號來判斷接受哪個。比如接受其中序號較大(往往意味著是接受新提出的,因為舊提案者故障概率更大)的提案。

如何為提案分配序號呢?一種可能方案是每個節點的提案數字區間彼此隔離開,互相不衝突。為了滿足遞增的需求可以配合用時間戳作為前綴字段。

同時允許多個提案,意味著很可能單個提案人無法集齊足夠多的投票;另一方面,提案者即便收到了多數接受者的投票,也不敢說就一定通過。因為在此過程中投票者無法獲知其它投票人的結果,也無法確認提案人是否收到了自己的投票。因此,需要實現兩個階段的提交過程。

兩階段的提交

提案者發出提案申請之後,會收到來自接受者的反饋。一種結果是提案被大多數接受者接受了,一種結果是沒被接受。沒被接受的話,可以過會再重試。即便收到來自大多數接受者的答覆,也不能認為就最終確認了。因為這些接受者自己並不知道自己剛答覆的提案可以構成大多數的一致意見。

很自然的,需要引入新的一個階段,即提案者在第一階段拿到所有的反饋後,需要再次判斷這個提案是否得到大多數的支持,如果支持則需要對其進行最終確認。

Paxos 裡面對這兩個階段分別命名為準備(Prepare)和提交(Commit)。準備階段通過鎖來解決對哪個提案內容進行確認的問題,提交階段解決大多數確認最終值的問題。

準備階段

  • 提案者發送自己計劃提交的提案的編號到多個接受者,試探是否可以鎖定多數接受者的支持。

  • 接受者時刻保留收到過提案的最大編號和接受的最大提案。如果收到提案號比目前保留的最大提案號還大,則返回自己已接受的提案值(如果還未接受過任何提案,則為空)給提案者,更新當前最大提案號,並說明不再接受小於最大提案號的提案。

提交階段

  • 提案者如果收到大多數的回覆(表示大部分人聽到它的請求),則可準備發出帶有剛才提案號的接受消息。如果收到的回覆中不帶有新的提案,說明鎖定成功。則使用自己的提案內容;如果返回中有提案內容,則替換提案值為返回中編號最大的提案值。如果沒收到足夠多的回覆,則需要再次發出請求。

  • 接受者收到接受消息後,如果發現提案號不小於已接受的最大提案號,則接受該提案,並更新接受的最大提案。

一旦多數接受者接受了共同的提案值,則形成決議,成為最終確認。

Raft 算法

Paxos 算法的設計並沒有考慮到一些優化機制,同時論文中也沒有給出太多實現細節,因此後來出現了不少性能更優化的算法和實現,包括 Fast Paxos、Multi-Paxos 等。最近的有 Raft 算法,算是對 Multi-Paxos 的重新簡化設計和實現,相對也更容易理解。

Raft 算法由斯坦福大學的 Diego Ongaro 和 John Ousterhout 於 2014 年在論文《In Search of an Understandable Consensus Algorithm》中提出。Raft 算法面向對多個決策達成一致的問題,分解了領導者選舉、日誌複製和安全方面的考慮,並通過約束減少了不確定性的狀態空間。

算法包括三種角色:領導者(Leader)、候選者(Candidate) 和跟隨者(Follower),決策前通過選舉一個全局的領導者來簡化後續的決策過程。領導者角色十分關鍵,決定日誌(log)的提交。日誌只能由領導者向跟隨者單向複製。

典型的過程包括兩個主要階段:

  • 領導者選舉:開始所有節點都是跟隨者,在隨機超時發生後未收到來自領導者或候選者消息,則轉變角色為候選者,提出選舉請求。最近選舉階段(Term)中得票超過一半者被選為領導者;如果未選出,隨機超時後進入新的階段重試。領導者負責從客戶端接收 log,並分發到其他節點;

  • 同步日誌:領導者會找到系統中日誌最新的記錄,並強制所有的跟隨者來刷新到這個記錄,數據的同步是單向的。

注:此處日誌並非是指輸出消息,而是各種事件的發生記錄。

Last updated