關(guān)注公眾號(hào) MageByte，設(shè)置星標(biāo)獲取最新干貨。公眾號(hào)后臺(tái)回復(fù) “加群” 進(jìn)入技術(shù)交流群獲更多技術(shù)成長(zhǎng)甲脏。
——本文由 MageByte 團(tuán)隊(duì)的「青葉」編寫
Paxos 算法是一種提高分布式系統(tǒng)系統(tǒng)容錯(cuò)性的一致性算法 。對(duì)于一個(gè)一致性算法 有以下特點(diǎn)：
- 在所有被提出的提案中妹笆，只有一個(gè)會(huì)被選定块请。
- 如果沒有提案被選出，就不會(huì)有選定的提案拳缠。
- 當(dāng)一個(gè)提案被選定后负乡，所有的節(jié)點(diǎn)進(jìn)程都可以獲取到被選定的提案信息。
- 一旦 “接受者” 接受了提議脊凰，就不能再接受其他提議內(nèi)容抖棘。
算法過程
在該一致性算法中有三種參與角色。分別為 “提議者（Proposer 向 “接受者” 提出提案）”狸涌、“接受者（Acceptor 收到 “提議者” 的提議后切省，向提議者表達(dá)自己的意見）”、“學(xué)習(xí)者（Learner 天被確定后帕胆，學(xué)習(xí)者獲取被確定的提議）”
- 第一階段：因?yàn)榇嬖诙鄠€(gè) “提議者” 朝捆，如果都提出提案，那么 “接受者” 接受誰的不接受誰的懒豹？太混亂了芙盘。所以要先明確具有領(lǐng)袖權(quán)的提議者才有權(quán)提出提案驯用。所以規(guī)定一些有領(lǐng)導(dǎo)權(quán)力的 “提案者” 可以提出提案。 “接受者” 們就主要去處理這個(gè) “提案者” 的提案了儒老。（這樣蝴乔，才可以在提案提出時(shí)就盡量讓意見統(tǒng)一，謀求盡早形成多數(shù)派）驮樊。
- 第二階段：由以上階段選出來的主 “提議者” 提出提案薇正，“接受者” 反饋意見。如果多數(shù) “接受者” 接受了一個(gè)提案（達(dá)到半數(shù)以上）囚衔，那么提案就通過了挖腰。
提案者選定與意見處理
- 怎么明確意見領(lǐng)袖呢？通過編號(hào)练湿。每個(gè)“提議者”在第一階段先報(bào)個(gè)號(hào)猴仑，誰的號(hào)大，誰就是意見領(lǐng)袖肥哎。如果不好理解宁脊，可以想象為賄選。每個(gè)提議者先拿著鈔票賄賂一圈“接受者”贤姆，誰給的錢多榆苞，第二階段“接受者”就聽誰的。（注：這里和下文提到的“意見領(lǐng)袖”霞捡，并不是一個(gè)新的角色坐漏，而是代表在那一輪賄賂成功的“提議者”。所以碧信，請(qǐng)把意見領(lǐng)袖理解為賄賂中勝出的“提議者”即可）赊琳。
- 有個(gè)跟選舉常識(shí)不一樣的地方，就是每個(gè) “提案者” 不會(huì)執(zhí)著讓自己的提案通過砰碴，而是每個(gè) “提案者” 會(huì)執(zhí)著于讓提議盡快達(dá)成一致意見躏筏。所以為了這個(gè)目標(biāo)，如果 “提案者” 在賄賂的時(shí)候發(fā)現(xiàn) “接受者” 已經(jīng)接受了前面意見領(lǐng)袖的提議呈枉，即便 “提議者” 賄賂成功趁尼，也會(huì)默默地把自己提案修改成前面意見領(lǐng)袖的提議（這樣就會(huì)更快的達(dá)到多數(shù)派）。
- 錢的多少很重要猖辫，若果錢少了酥泞，無論第一還是第二階段 “接受者” 都不會(huì)接受，直接拒絕啃憎。
- 上面 2 中提到如果 “提案者” 在賄賂的時(shí)候發(fā)現(xiàn)前面已經(jīng)有意見領(lǐng)袖的提議芝囤，那就將自己的提議默默地改成意見領(lǐng)袖的提議。但是這里有一種情況，如果你是 “提議者” 悯姊，在賄賂的時(shí)候羡藐， “接受者n” 回復(fù)你說 “他收到的意見領(lǐng)袖的提案是 方案 n ”，而 “接受者 n + 1” 回復(fù)你說 “他收到的意見領(lǐng)袖提議的方案是 n + 1”悯许。這時(shí)候我們?cè)撛趺崔k仆嗦。原則很簡(jiǎn)單，還是： “錢的多少重要岸晦！”欧啤，你就判斷下 “是接受者 n ” 見過的意見領(lǐng)袖有錢還是 “接受者 n + 1” 見過的領(lǐng)袖提議者有錢睛藻。你就把自己的提議改成意見領(lǐng)袖錢多的那個(gè) 提議启上。
- 在整個(gè)選舉過程中，每個(gè)提案者誰先來后到店印，“接受者” 什么時(shí)候收到 “提案者” 的提議是完全不可控的冈在。所以有可能一個(gè)意見領(lǐng)袖已經(jīng)產(chǎn)生了，但是由于這個(gè)意見領(lǐng)袖的第二階段才剛剛開始按摘，很多 “接受者” 還沒有收到這個(gè)意見領(lǐng)袖的提案包券。這時(shí)候突然來了一個(gè)新的土豪 “提案者” ，那么這個(gè)土豪也是有可能讓自己提案勝出炫贤。會(huì)出現(xiàn)這樣的博弈現(xiàn)象：
- 上一個(gè)意見領(lǐng)袖要趕在土豪 “提案者” 賄賂到 “接受者” 前接受自己的提案溅固，否則會(huì)因?yàn)樽约褐百V賂的錢少于土豪被拒絕。
- 土豪 “提案者” 要趕在上一個(gè)意見領(lǐng)袖者將提議傳達(dá)給 “接受者” 前賄賂到 “接受者”兰珍，否則土豪 “提議者” 基石賄賂成功侍郭，也要默默地將自己的提議改成前任領(lǐng)袖的提議內(nèi)容。不管怎么樣掠河，最終先得到多數(shù) “接受者” 的認(rèn)可亮元，那么這個(gè)提議就勝出了。
總結(jié)
- Paxos 算法包括兩個(gè)階段：第一階段主要就是賄賂唠摹，還沒有提出提議爆捞；第二個(gè)階段就是根據(jù)第一階段的結(jié)果，明確接受誰的提議勾拉，并且明確提議的內(nèi)容（這個(gè)提議可能是賄賂選取勝出的 “提案者” 自己的提議煮甥，也可能是前任意見領(lǐng)袖的提議）。
- 編號(hào)（賄賂金額大信涸蕖）很重要苛秕，無論哪個(gè)階段，編號(hào)小的都會(huì)被拒絕找默。
- 在第一階段中艇劫，一旦 “接受者” 已經(jīng)接受了前面的意見領(lǐng)袖的提議，后面再來找這個(gè) “接受者” 的 “提議者” ，即便是賄賂勝出店煞，也要老實(shí)的把自己的提案內(nèi)容改成前面領(lǐng)袖提議的內(nèi)容蟹演，這點(diǎn)尤為重要。接著這個(gè) “提案者” 也會(huì)在第二階段提出改變后的提議（為了一件快速達(dá)成一致）顷蟀。如果 “接受者” 之前沒有接收過任何提議酒请，那賄賂成功的 “提議者” 就可以提出自己的提議了。
簡(jiǎn)單示例說明
有兩個(gè) “提案者” 和三個(gè) “接受者”
-
首先 “提案者1” 賄賂了 3個(gè) “接受者”鸣个。也就是第一階段 image.png
三個(gè) “接受者” 記下賄賂的金額大小羞反，目前只有一個(gè) “提案者” 出價(jià)賄賂，因此 $1就是最高的囤萤，所以 3 個(gè) “接受者” 返回 “提案者1” 賄賂成功昼窗。另外，因?yàn)闆]有任何先前的意見領(lǐng)袖提出提議涛舍，因此 “接受者” 們告訴 “提案者1” 之前沒有接受過提議澄惊，自然也就沒有上一個(gè)意見領(lǐng)袖賄賂金額了。
“提案者1” 準(zhǔn)備執(zhí)行第二階段： 向 “接受者1” 提出了自己的提議：內(nèi)容為 1 號(hào)提議富雅，并告訴自己之前賄賂的金額$1掸驱。
“接受者1” 檢查了下，目前賄賂的金額就是 $1没佑，于是就接受了 這個(gè)提議毕贼，并且把 1號(hào)提議的內(nèi)容記錄在案。
-
在 “提議者1” 向 “接受者2”蛤奢、“接受者3” 發(fā)起提議之前鬼癣，土豪 “提議者2” 出現(xiàn)了，他開始使用 $2賄賂 “接受者1“ 和 “接受者2”远剩。 image.png
“接受者1” 和 “接受者2” 就被土豪 “提議者2” 收買了扣溺，將賄賂金額改成了 $2，但是瓜晤，不同的是 “接受者1” 告訴響應(yīng) “提案者2” 锥余，之前已經(jīng)接受過 “提案者1” 提出的1號(hào)提議了。而 “接受者2” 告訴 “提案者2” 之前沒有收到過其他領(lǐng)袖的提議痢掠。
這時(shí)候 “提案者1” 回神了驱犹，他向 “接受者2” 和 “接受者3” 發(fā)起 1號(hào)內(nèi)容提議，并且攜帶之前賄賂過金額 $1的信息足画。
“接受者2” 和 “接受者3” 開始回復(fù)：“接受者2” 檢查了下自己記錄的金額
2了，而你之前出的
1，于是就接受了這個(gè)提議內(nèi)容，并且把1號(hào)提議記錄在案蔬将。
到這里爷速，“提案者1” 已經(jīng)獲得了兩個(gè)接受者的贊同，達(dá)到了 半數(shù)通過的場(chǎng)景霞怀。于是 “提案者1” 確定了一號(hào)提議內(nèi)容最終通過惫东。
我們?cè)倩氐?“提案者2” ，之前賄賂了 “接受者1” 和 “接受者2”毙石，并且被 “接受者1” 告知： “之前已經(jīng)接受過一號(hào)提議了廉沮，并且最高金額是￥1。這個(gè)時(shí)候 “提案者2” 拿到信息后判斷一下徐矩，目前就是1號(hào)提議內(nèi)容滞时，就默默地把自己的提議內(nèi)容改成了 1號(hào)。然后向 “接受者1” 和 “接受者2” 發(fā)起提議丧蘸，提議內(nèi)容已經(jīng)變成 1號(hào)漂洋。并且攜帶信息之前已經(jīng)賄賂過金額 $2遥皂。
“接受者1” 和 “接受者2” 收到 “提案者2” 的提議后力喷，繼續(xù)按照之前流程 對(duì)比下賄賂金額，記錄的是之前賄賂的金額 $2,所以就接受了提議演训，其實(shí)就是 “提案者1” 提出的內(nèi)容弟孟。就這樣最終1號(hào)提議內(nèi)容通過。
歡迎加群與我們分享样悟，我們第一時(shí)間反饋拂募。關(guān)注公眾號(hào)，后臺(tái)回復(fù) 加群即可獲取個(gè)人微信窟她。
