理解這兩點,也就理解了paxos協議的精髓

先學習過程中收集到的一些好資料

整個過程自己也在學習,如有不對的地方歡迎指出:)

收集到一些資料可以分享下,也相當於分享自己的學習過程:

1. 首先,推薦的是 @連城 推薦的知行學社的《分散式系統與Paxos演算法視頻課程》: ,視頻講的非常好,很適合入門,循序漸進慢慢推導,我自己看了不下5遍,視頻講解理解更深,推薦大家都看看,視頻末尾說有後續介紹,一直沒有找到,如果有哪位大俠找到了通知下我,不勝感激。

2. 推薦劉傑的《分散式系統原理介紹》 ,裡面有關於paxos的詳細介紹,例子非常多,也有包括paxos協議的證明過程,大而全,質量相當高的一份學習資料!

3. @吳鏑 推薦的一份高質量ppt《可靠分散式系統基礎 Paxos 的直觀解釋》,雖然是只是一份ppt沒有講解視頻,但看ppt也能理解整個的paxos介紹和推導過程,寫的很具體,配圖很清晰明了;

4. 微信的幾篇公眾號文章:《微信PaxosStore:深入淺出Paxos演算法協議》(微信PaxosStore:深入淺出Paxos演算法協議 )、《微信開源:生產級paxos類庫PhxPaxos實現原理介紹》(微信自研生產級paxos類庫PhxPaxos實現原理介紹 ),文章寫的都挺好,但是博文有個缺點是知識比較零散,不適合入門,需要有一定基礎才好理解;

5. 技術類的東西怎麼能只停留在看上面,肯定要看代碼啊,推薦微信開源的phxpaxos:https://github.com/tencent-wechat/phxpaxos,結合代碼對協議理解更深,很多時候說了一大堆看代碼就是一個if或者for循環,看了代碼豁然開朗。

6. 如果英文可以的話,一定要看看paxos作者Lamport《paxos made simple》的論文。


以下是自己的學習總結

什麼是paxos協議?

Paxos用於解決分散式系統中一致性問題。分散式一致性演算法(Consensus Algorithm)是一個分散式計算領域的基礎性問題,其最基本的功能是為了在多個進程之間對某個(某些)值達成一致(強一致);簡單來說就是確定一個值,一旦被寫入就不可改變。paxos用來實現多節點寫入來完成一件事情,例如mysql主從也是一種方案,但這種方案有個致命的缺陷,如果主庫掛了會直接影響業務,導致業務不可寫,從而影響整個系統的高可用性。paxos協議是只是一個協議,不是具體的一套解決方案。目的是解決多節點寫入問題。

paxos協議用來解決的問題可以用一句話來簡化:

將所有節點都寫入同一個值,且被寫入後不再更改。

paxos的幾個基本概念

一、兩個操作:

  1. Proposal Value:提議的值;
  2. Proposal Number:提議編號,可理解為提議版本號,要求不能衝突;

二、三個角色:

  1. Proposer:提議發起者。Proposer 可以有多個,Proposer 提出議案(value)。所謂 value,可以是任何操作,比如「設置某個變數的值為value」。不同的 Proposer 可以提出不同的 value,例如某個Proposer 提議「將變數 X 設置為 1」,另一個 Proposer 提議「將變數 X 設置為 2」,但對同一輪 Paxos過程,最多只有一個 value 被批准。
  2. Acceptor:提議接受者;Acceptor 有 N 個,Proposer 提出的 value 必須獲得超過半數(N/2+1)的 Acceptor批准後才能通過。Acceptor 之間完全對等獨立。
  3. Learner:提議學習者。上面提到只要超過半數accpetor通過即可獲得通過,那麼learner角色的目的就是把通過的確定性取值同步給其他未確定的Acceptor。

?三、協議過程

一句話說明是:

proposer將發起提案(value)給所有accpetor,超過半數accpetor獲得批准後,proposer將提案寫入accpetor內,最終所有accpetor獲得一致性的確定性取值,且後續不允許再修改。

協議分為兩大階段,每個階段又分為A/B兩小步驟:

  1. 準備階段(占坑階段)
    1. 第一階段A:Proposer選擇一個提議編號n,向所有的Acceptor廣播Prepare(n)請求。
    2. 第一階段B:Acceptor接收到Prepare(n)請求,若提議編號n比之前接收的Prepare請求都要大,則承諾將不會接收提議編號比n小的提議,並且帶上之前Accept的提議中編號小於n的最大的提議,否則不予理會。
  2. 接受階段(提交階段)
    1. 第二階段A:整個協議最為關鍵的點:Proposer得到了Acceptor響應
      1. 如果未超過半數accpetor響應,直接轉為提議失敗;
      2. 如果超過多數Acceptor的承諾,又分為不同情況:
        1. 如果所有Acceptor都未接收過值(都為null),那麼向所有的Acceptor發起自己的值和提議編號n,記住,一定是所有Acceptor都沒接受過值;
        2. 如果有部分Acceptor接收過值,那麼從所有接受過的值中選擇對應的提議編號最大的作為提議的值,提議編號仍然為n。但此時Proposer就不能提議自己的值,只能信任Acceptor通過的值,維護一但獲得確定性取值就不能更改原則;
    2. 第二階段B:Acceptor接收到提議後,如果該提議版本號不等於自身保存記錄的版本號(第一階段記錄的),不接受該請求,相等則寫入本地。

整個paxos協議過程看似複雜難懂,但只要把握和理解這兩點就基本理解了paxos的精髓

1. 理解第一階段accpetor的處理流程:如果本地已經寫入了,不再接受和同意後面的所有請求,並返回本地寫入的值;如果本地未寫入,則本地記錄該請求的版本號,並不再接受其他版本號的請求,簡單來說只信任最後一次提交的版本號的請求,使其他版本號寫入失效;

2. 理解第二階段proposer的處理流程:未超過半數accpetor響應,提議失敗;超過半數的accpetor值都為空才提交自身要寫入的值,否則選擇非空值里版本號最大的值提交,最大的區別在於是提交的值是自身的還是使用以前提交的。

下面通過具體案例來深刻理解這兩點。


協議過程舉例:

看這個最簡單的例子:1個processor,3個Acceptor,無learner。

目標:proposer向3個aceptort 將name變數寫為v1。

  • 第一階段A:proposer發起prepare(name,n1),n1是遞增提議版本號,發送給3個Acceptor,說,我現在要寫name這個變數,我的版本號是n1
  • 第一階段B:Acceptor收到proposer的消息,比對自己內部保存的內容,發現之前name變數(null,null)沒有被寫入且未收到過提議,都返回給proposer,並在內部記錄name這個變數,已經有proposer申請提議了,提議版本號是n1;
  • 第二階段A:proposer收到3個Acceptor的響應,響應內容都是:name變數現在還沒有寫入,你可以來寫。proposer確認獲得超過半數以上Acceptor同意,發起第二階段寫入操作:accept(v1,n1),告訴Acceptor我現在要把name變數協議v1,我的版本號是剛剛獲得通過的n1;
  • 第二階段B:accpetor收到accept(v1,n1),比對自身的版本號是一致的,保存成功,並響應accepted(v1,n1);
  • 結果階段:proposer收到3個accepted響應都成功,超過半數響應成功,到此name變數被確定為v1。

以上是正常的paxos協議提議確定流程,是不是很簡單,很容易理解呢?

確定你理解了上面的例子再往後看。


這是最簡單也最容易理解的例子,但真實情況遠比這個複雜,還有以下問題:

  • 如果其中的某個Acceptor沒響應怎麼處理?
  • 如果只寫成功了一個accpetor又怎麼處理,寫成功兩個呢?
  • 如果多個proposer並發寫會導致accpetor寫成不同值嗎?
  • learner角色是做什麼用?
  • 為什麼是超過半數同意?

paxos特殊情況下的處理

第一種情況:Proposer提議正常,未超過accpetor失敗情況

問題:還是上面的例子,如果第二階段B,只有2個accpetor響應接收提議成功,另外1個沒有響應怎麼處理呢?

處理:proposer發現只有2個成功,已經超過半數,那麼還是認為提議成功,並把消息傳遞給learner,由learner角色將確定的提議通知給所有accpetor,最終使最後未響應的accpetor也同步更新,通過learner角色使所有Acceptor達到最終一致性。

第二種情況:Proposer提議正常,但超過accpetor失敗情況

問題:假設有2個accpetor失敗,又該如何處理呢?

處理:由於未達到超過半數同意條件,proposer要麼直接提示失敗,要麼遞增版本號重新發起提議,如果重新發起提議對於第一次寫入成功的accpetor不會修改,另外兩個accpetor會重新接受提議,達到最終成功。

情況再複雜一點:還是一樣有3個accpetor,但有兩個proposer。

情況一:proposer1和proposer2串列執行

proposer1和最開始情況一樣,把name設置為v1,並接受提議。

proposer1提議結束後,proposer2發起提議流程:

第一階段A:proposer1發起prepare(name,n2)

第一階段B:Acceptor收到proposer的消息,發現內部name已經寫入確定了,返回(name,v1,n1)

第二階段A:proposer收到3個Acceptor的響應,發現超過半數都是v1,說明name已經確定為v1,接受這個值,不在發起提議操作。

情況二:proposer1和proposer2交錯執行

proposer1提議accpetor1成功,但寫入accpetor2和accpetor3時,發現版本號已經小於accpetor內部記錄的版本號(保存了proposer2的版本號),直接返回失敗。

proposer2寫入accpetor2和accpetor3成功,寫入accpetor1失敗,但最終還是超過半數寫入v2成功,name變數最終確定為v2;

proposer1遞增版本號再重試發現超過半數為v2,接受name變數為v2,也不再寫入v1。name最終確定還是為v2

情況三:proposer1和proposer2第一次都只寫成功1個Acceptor怎麼辦

都只寫成功一個,未超過半數,那麼Proposer會遞增版本號重新發起提議,這裡需要分多種情況:

  1. 3個Acceptor都響應提議,發現Acceptor1{v1,n1} ,Acceptor2{v2,n2},Acceptor{null,null},Processor選擇最大的{v2,n2}發起第二階段,成功後name值為v2;
  2. 2個Acceptor都響應提議,
    1. 如果是Acceptor1{v1,n1} ,Acceptor2{v2,n2},那麼選擇最大的{v2,n2}發起第二階段,成功後name值為v2;
    2. 如果是Acceptor1{v1,n1} ,Acceptor3{null,null},那麼選擇最大的{v1,n1}發起第二階段,成功後name值為v1;
    3. 如果是Acceptor2{v2,n2} ,Acceptor3{null,null},那麼選擇最大的{v2,n2}發起第二階段,成功後name值為v2;
  3. 只有1個Acceptor響應提議,未達到半數,放棄或者遞增版本號重新發起提議

可以看到,都未達到半數時,最終值是不確定的!


總結

Paxos協議是用來解決分散式系統中一致性問題的其中一種解決方案。協議過程看似羞澀難懂,只要理解accpetor接收階段的不同處理流程和proposer提議階段的處理流程,也就基本掌握了paxos協議的精髓,處理流程也不複雜,只是異常條件分支較多,只要一個個去理解也沒什麼難度,比我們寫的業務流程簡單多了。

最最後,如果有哪裡寫的不對的地方,歡迎指出共同學習,共同進步!


推薦閱讀:

分散式 tensorflow 指南
成為HBase Committer後
分散式系統理論 - 從放棄到入門
CAP 理論常被解釋為一種「三選二」定律,這是否是一種誤解?
zhh-2015在分散式系統和資料庫領域研究水平和工程能力怎樣?

TAG:Paxos | 分布式系统 |