[MOOCS][Golang]MIT6_824 Distributed Systems Week3- About Paxos Algorithm

July 2nd, 2015

前言:

由於之前無論文有點久遠，先把論文瞭解的部分先寫成文章．之後再來把Lab3寫出來…. 這一篇主要是講Paxos算法的部分

MIT 6.824 分散式系統 系列文章

6.824: Distributed Systems

##論文-Paxos

先拿出一張各種的consensus的解決方式比較圖．

image

論文的原文，Leslie Lamport，(就是 LaTeX 中的”La”)在1990提出該演算法後，由於太難懂沒有受到重視．於是他又寫了一篇來解釋自己的演算法其實很簡單． 很有趣….

共識問題

Paxose主要是要解決共識(consensus)的問題，這一個Quora舉了一個很有趣的案例討論什麼叫做共識(consensus)，就像是婚禮的誓詞一樣．

  神父: 新娘你願意嫁給新郎? 
  新娘: 願意
  神父: 新郎你願意娶新娘嗎?
  新郎: 願意
  神父: 那..我宣佈你們成為夫妻

2PC (Two Phase Commit)

類似這樣就叫做共識問題，而一開始提出的解法就是2PC(Two Phase Commit)

  • Vote-Phase: 由協調者(也可以稱為提案者，原本也是其中一個節點)提案所有節點(node)，是否同意某個數值(或是交易)．其中協調者需要詢問所有的節點，確認大家都是同意的．
  • Commit-Phase: 當協調者確認全部人同意後，他會執行這個動作．並且也告訴所有的節點，要執行這個部分（數值或是交易）

缺點:

  • 指令相當繁瑣，需要一共三次的溝通．如果有n個節點，就需要有3n的資訊往來．
    • 協調者 -> 節點 (是否同意?)
    • 節點 -> 協調者 (我同意)
    • 協調者宣布提案成立
  • 任何一個節點的失敗不會造成該提案失敗，但是如果在詢問的過程中協調者忽然離線了．其他的人就無法知道狀況與結果．

為了避免協調者離線的問題，於是乎有了3PC的方式 (Three Phase Commit)

3PC (Three Phase Commit)

  • Phase 1: 跟Vote-Phase一樣，協調者會問所有的節點．
  • Phase 2(新步驟): 協調者取得所有人的共識後，會發送一個”Prepare to Commit”的訊息給所有的節點．這個動作的重點是，告訴所有的節點我們已經取得所有人的共識．要開始執行提案．(表示該提案已經成立，不會退回)．此時所有節點也會回傳給協調者告知是否有收到．
  • Phase 3: 跟Commit-Phase一樣，協調者會執行提案後也告訴所有節點要執行該提案．

解決的問題

  • 如果在3PC的狀況下，如果在Phase 2發生了協調者離線(crash)，新的協調者只要重跑一次Phase2 即可，不需要重新詢問Phase 1．
  • 如果是在Phase 3發生crash，由於已經收到回應確認全部人都已經有收到Prepare to Commit．所以新的協調者繼續執行最後步驟即可．

缺點

雖然3PC解決了重大問題，但是還是存在一些問題如下:

  • 步驟變得更繁瑣，需要訊息量也從3n變成5n (2 + 2 + 1)
  • 無法解決如果網路發生問題造成某些節點以為還在第二步驟，某一些節點卻又到了第三步驟．

Paxos Algorithm

image

(Image comes from here)

為何我們需要Paxos Algorithm?
  • 雖然解決了協調者crash問題，但是無法結果Partition Failure．也就是由於某些網路問題造成數個節點離開．（或是中間節點鍛造成兩個子網路）這也是所謂的 Partition tolerant algorithm．(尤其現今網路的狀況，這種情況更容易發生)
  • 原來不論是在2PC或是3PC討論的都是協調者失效後，由其他人來替代的方案．但是現在要討論的是，節點失效後採取的復原方式與相關的處理．這樣會更有效用．根據原文也就是說 3PC是 fail-stop resilient但是比較需要的應該是fail-recover resilient．
關於Paxos的起源與假設

Paxos主要是根據Lamport所提出的一個寓言故事，也就說個古希臘愛琴海上的被稱為Paxos的小島的故事．根據該小島議會制度所提出的演算法，裡面有幾個主要的假設:

  • 小島上的人忙著經商，所以不會一直在議會裡面．也就是共識可能是在大家不一定全部都在的狀況下產生．所以他只需要大多數的人同意即可．
  • 不會有拜占庭將軍問題(也就是一個訊息被傳遞兩次的問題)．而且訊息不管要經過多久，都會被傳到．
  • Paxos小島上的人性本善，基本上提出的提案都會被同意．
主要運作原理:

某些層面跟2PC很類似，但是主要精神不同:

  • 選舉出一個leader(或是提案者)
  • 提案者提出一個提案(acceptor)傳給大家(這個訊息稱為acceptor-request)在一個限定的時間內(a given time)．
  • 不同於2PC，Paxos只需要大多數的人回覆同意即可繼續發送commit message給所有節點
如果leader(提案者)failure?

由於原本2PC方式沒有辦法處理leader錯誤的狀況．在這裏Paxos提供以下兩個機制來處理:

  • Assign an order to leaders: Paxos不像是 2PC ，他可以存在多個Leader．在他們發現leader failure的時候，其他節點就會推選出新的leader．並且給予每個leader一個順序．預防原本的leade又從failure recover回來．
  • Restricting leader’s choice in selecting value: 要如何能讓consensus的過程在新的leader上面繼續？ 就是要限制在這個時候被推選的leader的提案．必須是之前的acceptor (也就是說正在進行中的consensus的數值)．
Protocol Step:

以下的敘述，主要以議會的方式來解釋各個狀態：

  • 準備階段(Prepare Stage):
    • 被選為提案者提出了一個提案，其中Proposal 1的數學表示為 P1(x, y) (x: 提案的流水號， y: 提案的內容)
    • 如果是第一個提案，所有議員都會同意．而且同意該提案後．並且議員回覆自己上次同意的號碼給提案者．並且承諾之後所有提案流水號小於x的提案都會被拒絕
    • 議員大多數狀況下只會同意，但是在以下狀況會拒絕:
      • 該提案內容(v)與前一次的提案內容相同．
      • 該提案號碼小於之前同意的提案流水號．
  • 核准階段(Commit stage):
    • 提案者會在收到大多數的人回覆同意之後，將告知所有節點要把提案交付．並且把上一次的提案數據附上．如果沒有前一次數據，提案者可以自行加入任何數值．
    • 議員再收到交付的訊息後，為了不違背之前的承諾．都會把提案內容交付．

參考資料:

Buy Me A Coffee

Evan

Attitude is everything