漫話分散式系統共識協議: Paxos篇

來自專欄 完備空間

可能和很多人的印象相反, Paxos其實是一個異常簡潔而精巧的演算法. 解讀一遍Paxos演算法其實只需要5分鐘. 本文將集中在經典的basic Paxos上, 而不會涉及其各種變種(實在也太多了).

前言

本文是「漫話分散式系統共識協議」這個系列的第二篇. 前一篇"2PC/3PC篇"介紹了分散式共識演算法中最早的2PC和3PC兩位老前輩. 各位老司機迫不及待的催我趕緊開車, 寫一寫Paxos. 然後就有了從三番飛到北京的飛機上敲出來的這一篇.

一提起Paxos, 各位老司機可能已經虎軀一震, 畢竟江湖上關於Paxos的傳聞太多. 比如當年Leslie Lamport的蒂花之秀: 在提出Paxos演算法後先是把演算法寫成了一部古希臘神話背景的小說, 導致發表了7,8年也沒人看的懂他想說什麼(Lamport: "皮一下很開心, 你管我?");

比如後來Lamport實在看不下去了(Lamport: "哎, 愚蠢的地球人啊"), 把小說回爐重新整理成了一篇學術論文叫"Paxos Made Simple", 而其摘要只有短短一句話"The Paxos algorithm, when presented in plain English, is very simple" (Lamport: "要是道歉有用, 要警察幹嗎?");

再比因為Lamport穩重帶皮的操作, 導致大家口口相傳Paxos理解和實現起來有多困難多複雜, 導致出現了Raft這種改良版等等.

敲黑板: Paxos其實是一個異常簡潔而精巧的演算法. 解讀一遍Paxos演算法其實只需要5分鐘. 真正複雜的地方在於想清楚Paxos演算法在各種failure情形下如何依然"正確"的工作. 只有明白了這一層, 才算練成了Paxos的心法, 才能真正欣賞Paxos演算法的精妙設計, 讚歎Lamport的天才思維. 在我看來, Paxos演算法(連同Lamport的其他如BFT, Vector Clock等成就)是上個世紀八十/九十年代的經典分散式系統研究中最純粹最優美, 也是整棟大廈底座最堅實的那一部分.

插點題外話: 我第一次認真接觸和學習Paxos是在CMU時TA分散式系統(15-440, Fall 2012: Distributed Systems). 當時也真是現學現賣, 看完短短十來行的偽代碼後, 硬是花了幾天的時間才想清楚演算法里各種變化, 然後最後從各種變化中找了最坑爹的一種作為期末考試題(各位同學抱歉啊). 然而值得一提的是, 當年這門課的大作業里很多同學用當時才剛剛發布不久的golang實現了一個簡單的分散式Paxos系統. 這在當時一個很大膽的嘗試, 但最後學生們的反饋非常好, 大約是從某種程度上證明(1) golang的系統抽象足夠方便, 來搭建分散式系統可以很好的專註在演算法層面上 (2) Paxos 也沒那麼恐怖.

Paxos演算法描述

考慮一個簡化了的Paxos系統: 只有leader和acceptor兩種角色.

1. Prepare階段

• (1a) leader的節點給所有其他acceptor節點發送消息"proposal(n)"---n是該節點為這個提議選擇的一個數字, 姑且理解為一個方案編號. 並期待該提議獲得所有節點中的簡單多數(Paxos的Quorum)的許可.
• (1b) 每一個接受到proposal的acceptor節點: 如果這是它接受到的第一個proposal, 回答"promise". 代表該節點許諾將會保持承認該proposal發送方為leader, 除非收到其他優先順序更高的proposal; 如果已經有接收到並accepted(注: 這是下一階段可能會發生的動作)其他的proposal(n,v)--n是該proposal的方案號而v是提議的共識:

* 如果 n < n, 之前accept的提議有更高優先順序, 對新接受的提議回答"reject", 以兌現之前的許諾.

* 如果 n > n, 回答"promise"的並同時附上舊的提議,proposal(n, v). 這樣在認可新的leader身份的同時, 也告訴了新的leader過去的被簡單多數認可過的提議

• (1c) 如果proposer的提議受到了簡單多數的"reject", 競爭leader宣告失敗, 可以放棄這一提議; 如果接受到了簡單多數的"promise", 則該proposer成為leader, 它需要從收到的promise里附帶的之前accepted的提議中選取方案號(n值)最高的對應的共識; 如果歷史上沒有被accept過的提議, leader可以自己選取一個共識v.

2. Accept階段

• (2a) leader會對所有acceptor發送"accept-request(n,v)", 請求所有acceptor接受編號為n的共識v的提議
• (2b) 每一個接收到該提議的acceptor節點: 如果沒有接受過編號比n更高的提議, 則返回"accept"表示接受這一共識提議; 否則返回"reject"
• (2c) 如果簡單多數的acceptor返回了"accept", 則共識達成; 否則共識失敗, 重啟Paxos協議.

請注意幾點以幫助理解協議:

1. 第一階段競爭的並不是共識本身, 而是在爭取坐實leader身份獲得簡單多數的認可
2. 方案編號n本身並不是共識, 而是提議的一個優先順序, 在多個節點競爭leader身份時可以區分優先順序. 共識本身(v)會在下一階段leader身份確認後由leader添加進提議;
3. 雖然這一輪上只會有一個leader獲得簡單多數的認可產生, 但可能有多個"糊塗"節點認為自己應該做leader, 見後面的分析;

在我看來, Paxos對2PC和3PC有幾點重要的改進.

第一，分離共識的提議者proposer以及幫助提議最終通過的leader這兩個角色. Paxos里, 即使一個leader身份被批准, 它也需要尊重歷史上其他被同意過的提議. 換言之leader本身只是一個服務性的角色, 未必有機會自己提出共識. 回憶一下上一篇介紹的2PC和3PC這兩個協議當中, coordinator不僅負責提出最後的共識協議, 同時也負責服務所有節點保證它的共識被通過. 而正是因為Paxos中把coordinator的職責解耦合成了proposer和leader, 使得整個演算法更加robust.就算前任leader宕機了, 後面新產生leader也可以繼承前任的"遺志"來完成一個Paxos協議.

第二，對簡單多數的巧妙應用. 第一階段里選舉leader要求的簡單多數保證了選舉出來的leader一定不會錯過之前被accept過的提議---所以就算那個提議最初的proposer掛了, 也會至少被一個acceptor發給新的leader來繼承. 而第二階段里要求的達成共識的簡單多數保證了有多個"自以為是"的leader出現時(比如一個leader掉線, 新leader選出, 舊leader重新上線), 一定只會有一個最後通過. 看過一個精彩的評論, 說Paxos其實就是連續運用兩次"抽屜原理", 其實非常準確.

Paxos與2PC/3PC的關係

Paxos如何克服2PC的問題: 2PC的問題在於不能處理最簡單的fail-stop錯誤模式.

• 2PC中coordinator是唯一而固定的, 如果coordinator宕機, 那麼就會有情形導致coordinator之前propose的提議的投票結果丟失. 就算啟動新的後備coordinator, 沒有機制可以學習以前的投票結果.
• Paxos因為分離了提議和leader, 從演算法上保證總可以選舉出後備leader並接替前任leader的工作.

Paxos如何克服3PC的問題: 3PC改進了2PC的fail-stop的問題, 但是不能處理fail-recover類型的錯誤.

• 3PC發生的問題在於當有多個"自認的leader"出現時, 並不能有效的解決coordinator之間的競爭---誰是真正的coordinator.
• 而Paxos通過Quorum的運用, 保證了多了個leader之間可以互相發現.

Paxos的局限性

就像2PC以及3PC一樣, Paxos也有其局限性.

1 活鎖問題.

Paxos理論上存在一個不能終結協議的活鎖競爭問題. 比如一個proposer提交的提議因為編號過低被拒絕時, 此proposer可能重啟Paxos而提高編號重新提交. 如果同時有兩個proposer都發現自己的方案編號過低, 從而輪流提出更高編號的proposal而導致對方被拒, 可能會導致死循環(或活鎖).

2 惡意節點.

目前為止2PC, 3PC, Paxos均是假設所有節點都遵守協議的規定. 當存在惡意的, 可能發送任何導致協議停止或者出錯的消息的節點存在時, 就需要有更強的共識演算法在"守法節點"間達成共識. Lamport 的BFT(拜占庭將軍問題)了解一下.