實(shí)用拜占庭容錯(cuò)算法（PBFT）

1.游戲背景? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ?拜占庭帝國(guó)即東羅馬帝國(guó)，擁有巨大的財(cái)富藕溅，并對(duì)鄰邦垂誕已久，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)烦衣，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊脚仔∏谥冢基于一些原因，這10支軍隊(duì)不能集合在一起單點(diǎn)突破鲤脏，必須在分開的包圍狀態(tài)下同時(shí)攻擊们颜。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無勝算，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國(guó)猎醇。他們分散在敵國(guó)的四周窥突，依靠通信兵相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問題是硫嘶，他們不確定他們中是否有叛徒阻问，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下音半，拜占庭將軍們能否找到一種分布式的協(xié)議來讓他們能夠遠(yuǎn)程協(xié)商则拷，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問題【在分布式系統(tǒng)中指的是消息不僅可以被丟失曹鸠、延遲煌茬、重放，還可以被偽造】彻桃。

2.游戲介紹

? ? ? ? PBFT(Practical Byzantine Fault Tolerance)算法由Miguel Castro 和Barbara Liskov在1999年提出來的坛善，解決了原始拜占庭容錯(cuò)算法效率不高的問題，將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)邻眷，使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行眠屎。

? ? ? ? PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，一般包括三種協(xié)議:一致性協(xié)議(agreement)肆饶、檢查點(diǎn)協(xié)議(checkpoint)和視圖更換協(xié)議(view change)改衩。該算法要滿足以下兩個(gè)性質(zhì)：? ?

? ? ? ? 安全性(safety)：safety means nothing bad happens.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 活性(liveness)：liveness means that something good eventually happens.

? ? ? ? 在一個(gè)拜占庭系統(tǒng)里面，要容忍f個(gè)拜占庭節(jié)點(diǎn)錯(cuò)誤驯镊，則replica數(shù)量至少為3f+1葫督，這是滿足安全性的前提。因?yàn)榫W(wǎng)絡(luò)延遲或宕機(jī)板惑，系統(tǒng)存在f個(gè)節(jié)點(diǎn)不回復(fù)響應(yīng)（f個(gè)節(jié)點(diǎn)包括拜占庭節(jié)點(diǎn)和非拜占庭節(jié)點(diǎn)橄镜，最壞情況f個(gè)節(jié)點(diǎn)全是非拜占庭節(jié)點(diǎn)），剩下2f+1個(gè)響應(yīng)中可能有f個(gè)拜占庭節(jié)點(diǎn)冯乘，從而得到n-2f>f洽胶，即響應(yīng)中非拜占庭節(jié)點(diǎn)數(shù)目大于拜占庭節(jié)點(diǎn)數(shù)目（f+1>f）。

? ? ? ? 算法不依賴同步提供安全性裆馒，則必須依賴同步提供活性姊氓，否則違背FLP定理(在異步通信場(chǎng)景丐怯，即使只有一個(gè)進(jìn)程失敗了，沒有任何算法能保證非失敗進(jìn)程能夠達(dá)到一致性)他膳。在拜占庭節(jié)點(diǎn)不超過f响逢，并且delay(t)有界的情況下就能保證系統(tǒng)活性，delay(t)表示從消息發(fā)送到接受的時(shí)間間隔棕孙。

3.游戲規(guī)則

? ? ? ? 在一個(gè)view里面舔亭，會(huì)從replicas中選擇一個(gè)primary，其余的replicas則叫backups蟀俊。如果主節(jié)點(diǎn)行為發(fā)生異常钦铺，則進(jìn)行view change換主。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?游戲從client向primary發(fā)送請(qǐng)求 $<request,\omicron ,t,c>_{sig_{c} }$ 開始肢预。 $\omicron$ 狀態(tài)機(jī)操作矛洞， $t$ 時(shí)戳。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?游戲從client至少收到f+1個(gè)replicas的響應(yīng) $<request,\omicron ,t,c>_{sig_{c} }$ 結(jié)束烫映。 $v$ 視圖編號(hào)沼本， $t$ 時(shí)戳， $c$ 客戶端身份锭沟， $i$ replica編號(hào)抽兆， $r$ 請(qǐng)求結(jié)果∽寤矗【why f+1辫红？因?yàn)樵?f+1個(gè)committed中有f個(gè)拜占庭節(jié)點(diǎn)表面上同意請(qǐng)求，實(shí)際上根本不會(huì)回復(fù)請(qǐng)求】

3.1 重彩大戲------三階段協(xié)議

非主節(jié)點(diǎn)錯(cuò)誤下的PBFT流程

Pre-prepare:

? ? ? ? Primary為客戶端請(qǐng)求分配一個(gè)序列號(hào)n祝辣，向所有backups發(fā)現(xiàn)預(yù)準(zhǔn)備消息 $<<pre-prepare,v,n,d>_{sig_{p} },m>$ 贴妻。 $v$ 視圖編號(hào)， $d$ 消息 $m$ 的摘要蝙斜。

Prepare:

? ? ? ? 若滿足以下條件名惩，backups接受預(yù)準(zhǔn)備消息：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.客戶端請(qǐng)求和預(yù)準(zhǔn)備消息具有正確簽名。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.當(dāng)前視圖編號(hào)是v孕荠。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3.backups從未在當(dāng)前視圖v接收過序列號(hào)為n但摘要不同的預(yù)準(zhǔn)備請(qǐng)求绢片。? ? ? ? ? ? ? ? ? ? ? ? ? 4.h<n<H〉呵恚【防止一個(gè)拜占庭節(jié)點(diǎn)選擇一個(gè)大的序號(hào)來消耗序號(hào)空間】

? ? ? ? 如果上述條件滿足，backups接收預(yù)準(zhǔn)備消息巢株，進(jìn)入prepare階段槐瑞，向其他節(jié)點(diǎn)廣播準(zhǔn)備消息 $<prepare,v,n,d,i>_{sig_{i} }$ ，并將預(yù)準(zhǔn)備和準(zhǔn)備消息寫入日志阁苞。

commit:

? ? ? ?如果backups收到2f【包括自己】個(gè)與預(yù)準(zhǔn)備消息一致的準(zhǔn)備消息困檩，請(qǐng)求消息和預(yù)準(zhǔn)備消息具有相同的視圖v和序列號(hào)n祠挫，并且已將相關(guān)消息寫入日志，則進(jìn)入commit階段悼沿，向其他節(jié)點(diǎn)廣播一條確認(rèn)消息 $<commit,v,n,d,i>_{sig_{i} }$ 等舔。如果各節(jié)點(diǎn)收到2f+1條相同的commits消息，則向客戶端發(fā)送一條reply消息糟趾。

3.2 垃圾回收

? ? ? PBFT是一種狀態(tài)機(jī)副本復(fù)制算法慌植，replicas會(huì)將執(zhí)行過消息記錄在本地日志中，為了節(jié)省內(nèi)存义郑，需要一種機(jī)制來清理日志蝶柿。何時(shí)來清理？在每次操作完后執(zhí)行是不明智的非驮，因?yàn)楸容^耗資源交汤。可以定期清理劫笙，比如每100次清理一次芙扎。我們將請(qǐng)求后執(zhí)行的狀態(tài)稱為檢查點(diǎn)checkpoint；帶證明的檢查點(diǎn)稱為stable certificate填大，當(dāng)節(jié)點(diǎn)收到2f+1個(gè)checkpoint消息時(shí)戒洼，可證明穩(wěn)定檢查點(diǎn)是正確的。穩(wěn)定檢查點(diǎn)之前的日志消息均可刪除栋盹。? ? ? ? ? ? ? ? ? ? ? ?

? ? ? 當(dāng)清理檢查點(diǎn)時(shí)replica i向其他replicas廣播一條檢查點(diǎn)協(xié)議 $<checkpoint,n,d,i>_{sig_{i} }$ 施逾， $n$ 是最近一次正確執(zhí)行請(qǐng)求序號(hào)， $d$ 是其當(dāng)前狀態(tài)摘要例获。如果每一個(gè)replica收到2f+1個(gè)具有相同序號(hào) $n$ 和摘要 $d$ 的檢查點(diǎn)消息汉额，這時(shí)每一個(gè)replica可以清理序列號(hào) $<n,d,v>$ 小于等于n的日志信息。

? ? ? ?檢查點(diǎn)協(xié)議也用來更新水平線榨汤。低水平線 $h$ 等于最近穩(wěn)定檢查點(diǎn)的序號(hào)蠕搜，高水平線 $H=h+l$ ， $l$ 為日志大小收壕。

3.3 視圖更改

? ? ? ? 當(dāng)主節(jié)點(diǎn)掛掉妓灌，或者在commit階段有些節(jié)點(diǎn)收到2f+1個(gè)commit，有些沒有收到2f+1個(gè)commit蜜宪，導(dǎo)致狀態(tài)不一致虫埂，這些狀況都需要更改視圖來提供系統(tǒng)活性和安全性。

? ? ? ? 當(dāng)請(qǐng)求超時(shí)圃验，備份節(jié)點(diǎn)進(jìn)入視圖v+1掉伏，廣播視圖更改消息 $<view-change,v+1,n,C,P,i>$ 。 $n$ 穩(wěn)定檢查點(diǎn)序列號(hào)， $C$ 是穩(wěn)定檢查點(diǎn)證明斧散， $P$ 是一個(gè)集合供常，包含對(duì)請(qǐng)求 $m$ （請(qǐng)求的序列號(hào)大于 $n$ ）相關(guān)消息集合 $P_{m}$ 。 $P_{m}$ 包含2f+1個(gè)相同的準(zhǔn)備消息鸡捐。

? ? ? ? ?當(dāng)視圖v+1的主節(jié)點(diǎn)收到2f個(gè)相同個(gè)視圖更改消息栈暇，向其他副本廣播新視圖消息 $<new-view,v+1,V,O>$ ， $V$ 是2f+1個(gè)視圖更改消息箍镜， $O$ 的計(jì)算規(guī)則如下：? ? ? ? 1.確定序列號(hào) $min_s$ 和 $max_s$ 源祈。其中 $min_s$ 等于 $V$ 中穩(wěn)定檢查點(diǎn)序列號(hào), $max_s$ 等于 $V$ 中最大prepare消息序列號(hào)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.主節(jié)點(diǎn)為 $min_s$ 和 $max_s$ 之間的每一個(gè)序列號(hào)n分配pre-prepare消息鹿寨。如果 $V$ 中包含n對(duì)應(yīng)的 $P$ 組合新博，則對(duì)應(yīng)的預(yù)準(zhǔn)備消息為 $<pre-prepare,v+1,n,d>$ （也就是說序列號(hào)n對(duì)應(yīng)的請(qǐng)求有2f+1個(gè)prepare消息，在新視圖中依然提交這個(gè)請(qǐng)求）脚草。如果 $V$ 中不包含n對(duì)應(yīng)的 $P$ 組合赫悄，則提交null消息為 $<pre-prepare,v+1,n,d<null> >$ ，即不做任何處理馏慨。

? ? ? ? 副本收到新視圖消息后埂淮，廣播一次prepare消息，進(jìn)入v+1写隶，視圖更換完成倔撞。

最后編輯于：2018.11.05 17:04:11

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市慕趴，隨后出現(xiàn)的幾起案子痪蝇，更是在濱河造成了極大的恐慌，老刑警劉巖冕房，帶你破解...
沈念sama閱讀 218,386評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件躏啰，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡耙册，警方通過查閱死者的電腦和手機(jī)给僵，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,142評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來详拙，“玉大人帝际，你說我怎么就攤上這事∪恼蓿” “怎么了蹲诀？”我有些...
開封第一講書人閱讀 164,704評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)弃揽。經(jīng)常有香客問我侧甫，道長(zhǎng)珊佣，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,702評(píng)論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任披粟，我火速辦了婚禮，結(jié)果婚禮上冷冗，老公的妹妹穿的比我還像新娘守屉。我一直安慰自己，他們只是感情好蒿辙，可當(dāng)我...
茶點(diǎn)故事閱讀 67,716評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布拇泛。她就那樣靜靜地躺著，像睡著了一般思灌。火紅的嫁衣襯著肌膚如雪俺叭。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,573評(píng)論 1贊 305
城市分裂傳說
那天泰偿，我揣著相機(jī)與錄音熄守，去河邊找鬼。笑死耗跛，一個(gè)胖子當(dāng)著我的面吹牛裕照，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播调塌，決...
沈念sama閱讀 40,314評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼晋南，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了羔砾？” 一聲冷哼從身側(cè)響起负间，我...
開封第一講書人閱讀 39,230評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎姜凄，沒想到半個(gè)月后政溃，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,680評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡檀葛，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,873評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年玩祟，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片屿聋。...
茶點(diǎn)故事閱讀 39,991評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡空扎，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出润讥，到底是詐尸還是另有隱情转锈，我是刑警寧澤，帶...
沈念sama閱讀 35,706評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布楚殿，位于F島的核電站撮慨，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜砌溺，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,329評(píng)論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一影涉、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧规伐，春花似錦蟹倾、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,910評(píng)論 0贊 22
一樁弒父案鲜棠，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至培慌，卻和暖如春豁陆，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背吵护。一陣腳步聲響...
開封第一講書人閱讀 33,038評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來泰國(guó)打工盒音，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人何址。一個(gè)月前我還...
沈念sama閱讀 48,158評(píng)論 3贊 370
代替公主和親
正文我出身青樓里逆，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親用爪。傳聞我的和親對(duì)象是個(gè)殘疾皇子原押，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,941評(píng)論 2贊 355

實(shí)用拜占庭容錯(cuò)算法（PBFT）

1.游戲背景? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2.游戲介紹

3.游戲規(guī)則

推薦閱讀更多精彩內(nèi)容