帶你認識Paxos演算法是如何進行選舉的

語言: CN / TW / HK

知之為知之,不知為不知,是知也**”**

01、角色

Proposer提議者:負責提出議案,也就是value(vaue是paxos協議中將操作統一抽象為value)。

Acceptor批准者:負責處理proposer提出的議案,proposer提出的議案必須獲得半數以上的acceptor的批准才能通過。

Learner學習者:不參與選舉,主要引數相關的狀態同步流程。

02、選舉流程

流程圖如下:

具體實現:

1、Proposer生成唯一id(proposalID),然後攜帶自己的proposalID向acceptor傳送prepare請求。

2、Acceptor收到prepare請求,判斷proposalID是否比之前已響應的所有提案的proposalID大。

  • 如果是,則本地持久化proposalID,然後將proposalID填充到max_proposalid中,然後回覆請求,並且攜帶proposalID的value(第一次會為空),並且不會接受小於proposalID的提案了。

  • 如果否,則不回覆或者回復Error

3、經過一段時間Proposer收到一些prepare回覆

  • 如果回覆超過一半,且回覆的value都為空,則Proposer發出accept請求,並帶上自己的value(也就是自己要當選Leader了)。

  • 如果回覆超過一半,且value不為空,則Proposer發出accept請求,並帶上回復中的proposalID最大的value作為自己提案內容。

  • 若回覆數量小於一半,則嘗試更新生成更大的proposaID,然後返回準備階段重新執行。

4、Acceptor收到accept請求後會做出以下判斷

  • 如果收到的proposalID>=持久化的max_proposalid,則回覆給Proposer提交成功,然後持久化proposalID和value。

  • 若收到的proposalID<max_proposalid,則不回覆或者回復提交失敗。

5、過一段時間後Proposer收集到一些accept回覆

  • 如果回覆數量超過一半的Acceptor數量,那麼提交value成功,此時傳送一個廣播給所有的Proposer、Learner。通知他們已經提交的value。

  • 如果回覆數量<=一半的Acceptor數量,那麼再嘗試更新更大的proposalID,然後轉到準備階段。

  • 如果收到提交失敗的回覆,則也嘗試更新更大的proposalid,也轉到準備階段。

03、總結

從以上的流程中可以看到Proposer會發出prepare和accept兩次請求,

第一次的prepare請求主要是為了找出proposalID最大的Proposer

第二次的accept請求主要是為了將proposalID最大的Proposer的value傳送給所有的Proposer和Learner。