所以其實(shí)Paxos目標(biāo)是解決了拜占庭問(wèn)題的一個(gè)側(cè)面, 并不是完全語(yǔ)義下的拜占庭問(wèn)題. Paxos算法實(shí)際上解決了希臘Paxos島上的法律制定者們, 如何協(xié)調(diào)意見(jiàn), 通過(guò)法條的問(wèn)題.每個(gè)希臘參議員, 有自己的法律條目記事簿. 通過(guò)書(shū)記團(tuán)隊(duì)傳遞自己對(duì)于法條的修訂. 參議員會(huì)隨機(jī)離開(kāi)大廳, 書(shū)記團(tuán)隊(duì)也有可能不靠譜, 丟了紙條呀, 忽然離開(kāi)呀之類的. 和拜占庭問(wèn)題非常類似, 但是參議員不會(huì)偽造信息, 書(shū)記員不會(huì)遞送一部分信息. 這是顯著的不同.

Paxos是Google Chubby

3.2 Paxos的提交模式

• Paxos是一個(gè)兩段式提交過(guò)程, 涉及到三種不同的角色Proposer, Acceptor, Listener

• 第一階段, 由代表(Proposer)靈光一閃說(shuō)我要發(fā)起一個(gè)提議, 這個(gè)提議之前的討論結(jié)果和編號(hào)是xxx, 我提議的編號(hào)是zzz. 這提議必須通過(guò)書(shū)記官(Network), 廣播到半數(shù)以上的議員那里(Acceptor). 這些議員可能回饋說(shuō):

1. "我們當(dāng)前準(zhǔn)備好就這個(gè)法律進(jìn)行討論了, 堅(jiān)決擁護(hù)代表的選擇" . 說(shuō)明當(dāng)前參與討論的節(jié)點(diǎn)狀態(tài)一致
2. "這個(gè)提議的編號(hào)明明是 aaa, 你那里怎么會(huì)是xxx? 大雄消息真不靈通呢.jpg" 說(shuō)明Proposer有落后的信息, 它只能在同步最新信息后再次提議
3. "一個(gè)比你牛逼的哥們已經(jīng)提議 yyy了, 我不參與你的討論, bye~" 說(shuō)明另外一個(gè)Proposer同時(shí)發(fā)起了相同的key-value對(duì), 且根據(jù)策略, 它優(yōu)先獲得了大多數(shù)人口頭支持, 相當(dāng)于成為了執(zhí)政黨, 本次提議只能作廢.

• 第二階段, Proposer提出具體的條目, 這些準(zhǔn)備討論這個(gè)條款的議員們回饋, 當(dāng)然部分議員可能溜了, 消息也有可能送不到. 最后如果運(yùn)氣好, 超過(guò)半數(shù)通過(guò), 則這條法律立即生效. Proposer就可以確認(rèn)這條法律已經(jīng)落盤(pán)到了超過(guò)半數(shù)的議員的記事本上

• 希臘政治體系下的參議員也是公民, 參議員也可以發(fā)起討論. 所以Proposer, Listener, Acceptor可以是同一個(gè)節(jié)點(diǎn)

• 為了保證書(shū)記官不錯(cuò)漏, 讓參議員們可以跟蹤消息. 所有傳遞的信息必須有一個(gè)全局唯一遞增編號(hào). 1xx年希臘第x號(hào)參議員的第xxx號(hào)消息如下.... 這樣接受者可以知道過(guò)來(lái)的消息是討論哪個(gè)法條的. 也可以扔掉那條過(guò)時(shí)的消息和重復(fù)遞送的消息.

• 兩個(gè)代表同時(shí)提出相同的提案, 議員們的一般策略是只會(huì)Promise標(biāo)號(hào)大的那個(gè), 對(duì)于標(biāo)號(hào)小的那個(gè)直接就略過(guò).

3.3 Node的策略說(shuō)明

• 作為一個(gè)活著的node, 我在自己的小本本上記錄, 當(dāng)前最大編號(hào)MaxN, 所有已經(jīng)通過(guò)的法條Accept Key Value, 我正在參與的討論的編號(hào) PromiseN. 同時(shí)我保持一個(gè)特別樸素的想法, 誰(shuí)的編號(hào)大我就認(rèn)誰(shuí).

• 如果大佬Proposer告訴我一個(gè)Key Value改了, 并且這條信息編號(hào)比本地的大, 我就更新它, 甚至根據(jù)具體的系統(tǒng)設(shè)計(jì)我還會(huì)擴(kuò)散這條信息

• 如果我已經(jīng)承諾了一個(gè)大佬, 我會(huì)參與了 一個(gè)事項(xiàng)的討論, 比如該不該削弱蟲(chóng)族, 并且大佬告訴我這是今年的第45號(hào)法案. 那么所有邀請(qǐng)我討論這個(gè)事情, 并且編號(hào)小于45的一律拒絕, 因?yàn)槲覜](méi)時(shí)間.

• 經(jīng)過(guò)漫長(zhǎng)的討論, 大佬告訴我暴雪決定削弱蟲(chóng)族了, 我就記下來(lái)第45號(hào)法案通過(guò), 馬上削弱小狗的攻擊頻率.

• 忽然一個(gè)新的大佬Serral出現(xiàn)了, 告訴我說(shuō)黃旭東奶了暴雪一口, 暴雪決定加強(qiáng)蟲(chóng)族, 而且這條法案的編號(hào)高達(dá)97.... 我立馬記下來(lái)這條信息覆蓋掉45號(hào)法案, 廣播這條信息, 并潛伏起來(lái)等待神族的黎明來(lái)臨.

• 由于兩段式確認(rèn)過(guò)程都需要超過(guò)半數(shù)node參與, 根據(jù)抽屜原理. 最終必然至少有一個(gè)node參與了全程.

4. Zab

http://img.bigdatabugs.com/Zab%20High-performance%20broadcast%20for%20primary-backup%20systems@www.bigDataBugs.com.pdf

4.1 Zab協(xié)議和Paxos的共性包括:

• 都需要一個(gè)大佬(Leader / Propoer)來(lái)發(fā)布提案
• 發(fā)布的提案在一個(gè)議會(huì)中(Quoram)的一定數(shù)量的人(Follower / Acceptor)都認(rèn)同后才算提交完成
• 為了操作冪等, 所有提案包括一個(gè)唯一的自增ID

4.2 Zab和Paxos的不同

Zab協(xié)議關(guān)注的是主從備份問(wèn)題(primary backup)
Paxos協(xié)議關(guān)注的是狀態(tài)機(jī)的備份(state machine replication)

4.3 state machine replication

作為圖靈機(jī)的數(shù)學(xué)模型, state machine作為一條無(wú)限長(zhǎng)的紙袋. 任何兩條紙袋, 只要接收相同的action queue, 一定達(dá)到相同的結(jié)果.
一個(gè)state machine replication需要保證每個(gè)狀態(tài)機(jī)都按照特定的順序執(zhí)行客戶端發(fā)過(guò)來(lái)的action.
即使client端是并發(fā)發(fā)送的這些action(本身無(wú)序), 網(wǎng)絡(luò)拓?fù)錈o(wú)法保證消息的傳遞按照發(fā)送的先后熟順序(中間件不保序列), 部分action可能會(huì)重發(fā)(冪等性)
當(dāng)leader掛掉, 新的leader可以為那些尚未提交的action進(jìn)行任意重排序, 這不會(huì)影響最終結(jié)果的語(yǔ)義正確性. \

核心問(wèn)題是如何讓所有節(jié)點(diǎn)對(duì)客戶端請(qǐng)求理解一致

海洋法系系統(tǒng): 一群大法官無(wú)論以任何順序討論法條, 無(wú)論同時(shí)討論多少個(gè)法條, 只要在某個(gè)最終時(shí)刻, 所有法官對(duì)法條的理解一致就可以了. 如果在討論過(guò)程中, 發(fā)起討論的法官去吃飯了. 接手的法官其實(shí)并不需要理解剛才那位的想法, 他只要保證討論能繼續(xù), 并且最終一致就完了.

4.4. primary backup

在這種系統(tǒng)里, Follower Node接收到的是從Primary Node發(fā)過(guò)來(lái)的排好序的增量更新. 這里的增量更新必須嚴(yán)格和primary執(zhí)行順序一致, 每個(gè)follower也必須嚴(yán)格的和leader處于完全相同的初始狀態(tài). 如果leader宕機(jī)了, 新選舉的leader不能隨意的安排未提交操作的順序, 也不能從一個(gè)不同的初始狀態(tài)來(lái)更新.

核心問(wèn)題是如何讓主從保持完全一致

大陸法系系統(tǒng): 人大作出了最終的法律決策, 投票通過(guò)了一個(gè)法條. 所有省級(jí)人民法院, 市級(jí)人民法院層層遞推, 把法條落實(shí)到自己的工作中. 因?yàn)槟炒瓮ｋ姽收? 人大不得不換了個(gè)地方重新開(kāi)會(huì). 停電前的投票計(jì)數(shù)不能終止, 已經(jīng)計(jì)數(shù)的結(jié)果不能丟失.

4.5 Paxos的局限性

• 惡性競(jìng)爭(zhēng)鎖
  兩個(gè)Proposer提出完全相同的議案, 并爭(zhēng)取多數(shù)議員支持. 我們剛才說(shuō)過(guò), 一般系統(tǒng)設(shè)計(jì)類, 議員的策略很簡(jiǎn)單, 就是誰(shuí)號(hào)大聽(tīng)誰(shuí)的. 于是這兩個(gè)Proposer就不斷的提升自己的議案編號(hào), 議員不斷的接收到遞增的Prepare請(qǐng)求, 并立即拒絕上一個(gè). 導(dǎo)致兩個(gè)Proposer都無(wú)法獲得絕對(duì)多數(shù)支持, 從而誰(shuí)都通不過(guò)信息.

• 同時(shí)發(fā)起的議案不保序
  一個(gè)議長(zhǎng)Proposer同時(shí)發(fā)起多個(gè)不同的議案, 然后發(fā)起后他就去吃飯了. 接班的議長(zhǎng)并不知道剛剛發(fā)起的多個(gè)議案相互之間的先后順序, 就有可能導(dǎo)致這些議案的通過(guò)順序不同. 如果這些議案恰好不是正交的, 那么最后會(huì)得出不同的結(jié)論.

例如議長(zhǎng)先后發(fā)起的兩個(gè)語(yǔ)義正交的議案, 酒醉駕車違法, 家暴違法. 然后去吃飯了, 新來(lái)的哥們主持后邊的會(huì)議是沒(méi)有問(wèn)題的.

但如果前任議長(zhǎng)發(fā)起的議案在語(yǔ)義上不正交, 必須保序. 比如 F91必須在WCS上穿女裝, F91必須在WCS上換一次衣服. 根據(jù)繼任者的理解不同, 可能F91會(huì)先女裝,然后換裝, 偏離了初衷.

4.6 Zab協(xié)議

論文中的Zab的解釋圖

加上選舉階段, 可以認(rèn)為正常流程包含4個(gè)階段, 依次為

• Leader Election
  Peers在這個(gè)階段初始化, 對(duì)于一個(gè)ZK 進(jìn)程來(lái)說(shuō), 它處于leader, election, follower三種狀態(tài)中的一種. 經(jīng)過(guò)選舉階段, 最終一個(gè)peer為被標(biāo)記為establish Leader候選人, 其它peers也都從election狀態(tài)切換到follower裝填

• Discovery
  在這個(gè)階段, leader會(huì)從follower那里收集所有最近的提交信息(transaction), 圖中的CEPOCH . 這一操作保證了leader可以discovery最近所有被提交的更改, 并且知道更改的先后順序. 以保證它和前任leader擁有完全相同的初始狀態(tài).
  之后它向所有的follower發(fā)送圖中NEWEPOCH并搜集回饋ACK-E, 保證多數(shù)的follower都認(rèn)它做老大. 此時(shí)如果前任老大斷網(wǎng)重連, 也會(huì)因?yàn)?code>EPOCH不符合當(dāng)前多數(shù)follower的記錄只能做小弟.

• Synchronization
  這個(gè)極端其實(shí)包含了錯(cuò)誤恢復(fù)部分, leader昭告所有follower它的Proposing Transaction, 以繼續(xù)前任可能未盡的事業(yè), 并確立自己的地位, 圖中NEWLEADER信息傳遞部分. 當(dāng)多數(shù)follower確認(rèn)ACT-LD 了已經(jīng)與leader保持一致后, establish Leader正式加冕為王, 可以開(kāi)始提議案了

• Broadcast
  只要系統(tǒng)中沒(méi)有出現(xiàn)重大故障, 系統(tǒng)會(huì)一直處于這個(gè)工作狀態(tài)下. 這里才是正常的zookeeper工作狀態(tài). leader從客戶端接受信息, 然后非常類似paxos的進(jìn)行propose act commit 兩段式記錄. 區(qū)別在之前提過(guò)的, leader會(huì)為propose添加唯一遞增編號(hào), 以保證恢復(fù)時(shí)的有序性.

4.7 選舉 Fast Leader Election

在老leader掉線后, 整個(gè)集群必須在有限時(shí)間內(nèi)選舉出一個(gè)新leader, 并且這個(gè)新leader必須和老leader的數(shù)據(jù)完全一致. 這里的狀態(tài)一致不但包含了已經(jīng)commit的數(shù)據(jù), 甚至還要求哪些Propose了但沒(méi)Commit的部分也要有記錄.這樣它才能繼承前者的遺志, 把隊(duì)伍帶好

根據(jù)抽屜原理, 只要整個(gè)系統(tǒng)還活著(存活peers大于一半), 必然有一個(gè)peer滿足條件, 然后我們要把這個(gè)點(diǎn)選出來(lái)做話事人

由于所有的Propose帶唯一遞增編號(hào), 所以peers就可以相互交換自己已經(jīng)知道的歷史. 如果一個(gè)peers發(fā)現(xiàn)自己記錄的歷史信息比其它人都要全, 它投票給自己, 并把自己置位到leader狀態(tài),反之, 置位到folower狀態(tài).
在投票中可以制定一個(gè)規(guī)則, 在歷史記錄不同的情況下, 誰(shuí)記錄的多我就投給誰(shuí)(most update). 在歷史記錄一樣的情況下, 誰(shuí)年輕(max peer id), 我就投給誰(shuí).

由于網(wǎng)絡(luò)可能存在時(shí)延\掉包, 整個(gè)選舉過(guò)程可能要來(lái)上幾輪. 在peer與peer交換信息的過(guò)程, 一個(gè)peer會(huì)使用 (vote, id, state, round)來(lái)描述自己投給誰(shuí), 自己是誰(shuí), 自己的裝填, 自己當(dāng)前所在的投票輪數(shù). 經(jīng)過(guò)多輪投票后, 只要整個(gè)系統(tǒng)中有多數(shù)peer存活, 且這些存活的多數(shù)peer均可以和真正的leader通信(無(wú)網(wǎng)絡(luò)分區(qū)錯(cuò)誤), 最終會(huì)有l(wèi)eader被選出, 然后正常的后續(xù)流程.