Paxos 算法與 ZooKeeper

分享 ? AIZero ? 于 2020-07-31 08:58:58 ? 536 閱讀
Paxos算法

解決分布式一致性問題,即一個分布式系統中的各個進程如何就某個值達成一致

Paxos中的角色

  1. Proposer: 提出提案 (Proposal)。Proposal信息包括提案編號 (Proposal ID) 和提議的值 (Value)。
  2. Acceptor:參與決策,回應Proposers的提案。收到Proposal后可以接受提案,若Proposal獲得多數Acceptors的接受,則稱該Proposal被批準。
  3. Learner:不參與決策,從Proposers/Acceptors學習最新達成一致的提案(Value)。

Paxon中通過決議的核心分為兩個階段

  1. 第一階段:Prepare階段。Proposer向Acceptors發出Prepare請求,Acceptors針對收到的Prepare請求進行Promise承諾。
  2. 第二階段:Accept階段。Proposer收到多數Acceptors承諾的Promise后,向Acceptors發出Propose請求,Acceptors針對收到的Propose請求進行Accept處理。


Paxos算法推導:分階段的原因

P0:當集群中,超過半數的Acceptor接受了一個議案,那么這個議案就被選定了

默認:每個提案都具備id和value,其中id是遞增的

第一層推導

問題分析

Proposal很多,Acceptor有人不接受議案,Acceptor接受的選擇并不集中,結果沒有任何一個議案形成多數派

問題處理

  1. 每個Acceptor必須接受一個議案
  2. 允許一個Acceptor接收多個議案,后接受的議案可以覆蓋掉之前接受的議案
第二層推導

問題分析

Acceptor接收了議案后,一個議案已經成為了多數派,但是后來又有議案提出覆蓋了之前接受的議案,導致一致性被破壞

問題處理

一次議案選舉必須只選定一個議案,一旦選定,不能更改

第三層推導

目標匯總

Target1:一次選舉必須要選定一個議案(不能出現所有議案被拒絕情況)

Target2:一次選舉必須只選定一個議案(不能出現兩個議案有不同的值但都被選定)

問題處理

P1:一個Acceptor必須接受它收到的第一個議案(容易處理)

P2:如果一個值為v的議案被選定,那么被選定的更大編號的議案,它的值必須是v

第四層推導

目標

如何實現一個值為v的議案被選定,被選定更大編號的議案,值必須是v

問題處理

P2a:一旦值為v的議案被選定,Acceptor接收更大編號的議案,它的值是v

P2b:一旦值為v的議案被選定,Proposer提出更大編號的議案必須值是v(更容易處理)

第五層推導

目標

值為v議案被選定,如何實現Proposer提出更大編號的議案的值必須是v

問題處理

P2c:在所有Acceptor中,任意選取半數以上的Acceptor集合,我們稱這個集合為S。Proposal新提出的議案(簡稱Pnew)必須符合下面兩個條件之一:
1)如果S中所有Acceptor都沒有接受過議案的話,Pnew的值可以是任意值。
2)如果S中有一個或多個Acceptor曾經接受過議案的話,要先找出其中編號最大的那個議案,假設它的編號為N,值為V。那么Pnew的編號必須大于N,Pnew的值必須等于V。

第六層推導

問題

確定議案的過程中呈現id大者決定一切,如果S集合之外有一個提案的ID大于所有S集合內的id,就會出現一致性破壞現象

問題分析

需要在議案提交前確定自己的編號是當前已經提出過議案的最大編號

問題處理

分階段的出現:需要在議案提交前向Acceptor確認當前自身id是否是議案的最大編號,然后再提交

第七層推導

目標

如何實現兩個階段:Prepare階段該確認ID是否為最大值,Accept階段提交議案

目標實現

  1. 議案(id,v)在提交前,將id通知給S集合的Acceptor。收到通知的Acceptor將id跟自己之前收到的議案進行比較,如果id小則不回復,如果id更大,就將id確認為最大編號,并回復
  2. Acceptor同時做出承諾:不再接受比n小的議案。
  3. 當Proposer收到回復的數量大于Acceptor總量的一半時,議案(id,v)才能正式提交。

細節解釋:只要保證一開始S集合中id最大即可,因為S集合的數量大于Acceptor數量的一半,所以S集合中id最大就是整個Acceptor中id最大

第八層推導

問題

Proposer1提交議案的過程中,如果另一個Proposer2進入Prepare階段,提交議案的id比之前更Proposer1更大,會出現議案提交后接受的Acceptor少于一半的情況,并沒有達成一致性

問題處理

提交回復:Acceptor接受議案后會給Proposer回復,如果Proposer收到的回復大于Proposer的一半時,則表示一致性達成,否則會再次進入Prepare階段。


算法流程總結

file


ZooKeeper

主要角色

  1. 領導者(leader同Paxos中Proposer):負責進行投票的發起和決議,更新系統狀態(數據同步),發送心跳。事務請求唯一調度者和處理者,保證集群事務處理的順序性

  2. 跟隨者(follower同Paxos中Acceptor):用于接受客戶端請求、向客戶端返回結果,在選主過程中參與投票。收到寫事務請求直接轉發給Leader

  3. 觀察者(Observer同Paxos中Learner):可以接受客戶端請求,將寫請求轉發給leader,但Observer不參加投票過程,只同步leader的狀態,observer的目的是為了擴展系統,提高讀取速度。

Paxos算法的活鎖問題:ZooKeeper只有一個leader的原因

Paxos中分為Prepare階段和Accept階段,但在運行的過程中,會存在一種極端情況,兩個Proposer依次提出一系列編號遞增的議案,就會陷入死循環,無法完成Accept階段,如圖
file

核心:ZAB協議

專有術語

  • 服務器ID(SID):標識一臺ZooKeeper集群中的機器,SID和myid值一樣,不能重復
  • 事務ID(ZXID):標記唯一一次服務器狀態的變更,某一時刻,集群中的每臺機器的ZXID不一定都一致

兩種模式:恢復模式(發現階段+同步階段),廣播模式(廣播階段)

發現階段:選舉

  1. 集群中機器出現故障,則進入選舉過程,切換到LOCKING狀態
  2. 選舉規則:第一優先級:ZXID大者,第二優先級:SID大者

同步階段

完成Leader選舉后,正式工作之前,Leader服務器會首先確保事務日志中所有的Proposal是否已經被過半的服務器Commit。

  • Leader服務器會為每一個Follower服務器都準備一個隊列

  • 將那些沒有被同步的事務以Proposal消息的形式逐個發送給Follower服務器

  • 然后每一條Proposal消息之后都緊接著Commit消息表示該事務已被提交

等到Follower服務器都將未同步的事務從Leader服務器同步過來并成功應用到本地數據庫后,Leader服務器會將該Follower服務器加入真正可用的Follower列表中

廣播階段
file

  1. leader首先把proposal發送到FIFO隊列里
  2. FIFO取出隊頭proposal給Follower
  3. Follower首先會以事務日志的形式寫入到本地磁盤,成功后反饋一個ACK給隊列
  4. 隊列把ACK交給leader
  5. leader收到半數以上ACK,就會發送commit指令給FIFO隊列
  6. FIFO隊列把commit給Follower,所有服務器完成事務的提交


ZAB與Paxos算法的聯系和區別

兩者之間的聯系

  • 兩者都存在類似Leader進程的角色,向其負責協調多個Follower進程的運行
  • Leader進程都會等待超過半數的Follower做出正確的反饋后,才將下一個提案提交
  • 在ZAB協議中,每個Proposal中都包含一個epoch值,用來代表當前的Leader周期,在Paxos算法中,同樣存在這樣的標識,只是名字變成了Ballot

區別

在Paxos算法設計的基礎上,ZAB協議添加了同步階段,新的Leader會確保存在過半的Follower已經提交了之前Leader周期中所有事務Proposal。能夠有效保證Leader在新的周期提出Proposal之前,所有的進程都已經完成了對之前的Proposal的提交。其余兩個階段兩者類似。

總的來講

ZAB協議和Paxos算法的本質區別在于,兩者的設計目標不太一樣,ZAB協議主要用于構建一個高可用的分布式數據主備系統,如ZooKeeper,而Paxon算法則是用于構建一個分布式的一致性狀態機系統。



僅個人總結,歡迎指正,部分圖片來自互聯網

參考《從Paxos到Zookeeper 分布式一致性原理與實踐》

版權聲明:原創作品,允許轉載,轉載時務必以超鏈接的形式表明出處和作者信息。否則將追究法律責任。來自海牛部落-AIZero,http://hainiubl.com/topics/75253
本帖已被設為精華帖!
本帖由 青牛 于 3月前 加精
回復數量: 0
    暫無評論~~
    • 請注意單詞拼寫,以及中英文排版,參考此頁
    • 支持 Markdown 格式, **粗體**、~~刪除線~~、`單行代碼`, 更多語法請見這里 Markdown 語法
    • 支持表情,可用Emoji的自動補全, 在輸入的時候只需要 ":" 就可以自動提示了 :metal: :point_right: 表情列表 :star: :sparkles:
    • 上傳圖片, 支持拖拽和剪切板黏貼上傳, 格式限制 - jpg, png, gif,教程
    • 發布框支持本地存儲功能,會在內容變更時保存,「提交」按鈕點擊時清空
    Ctrl+Enter
    上海麻将垃圾胡技巧 864822523363673441459768995464982537976634730351063057114918930637737916181479099407383967539167 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();