區(qū)塊鏈課程13共識(shí)層：PBFT共識(shí)算法

1、PBFT算法Cuiting Shi, OneThing Tech LTD.Thursday, December 6, 2018 TOC o 1-5 h z HYPERLINK l bookmark13 o Current Document 背景-1 HYPERLINK l bookmark16 o Current Document PBFT算法模型3 HYPERLINK l bookmark22 o Current Document 2.1基本概念3三階段協(xié)議-4 HYPERLINK l bookmark38 o Current Document pre-prepare 階段6 HYPERLI

2、NK l bookmark46 o Current Document prepare 階段-7 HYPERLINK l bookmark53 o Current Document commit 階段8算法優(yōu)化9 HYPERLINK l bookmark62 o Current Document 4.1檢查點(diǎn)協(xié)議9 HYPERLINK l bookmark69 o Current Document 4.2視圖變更協(xié)議11 HYPERLINK l bookmark72 o Current Document 4.2.1維持計(jì)時(shí)器11 HYPERLINK l bookmark75 o Current

3、Document 4.2.2請(qǐng)求視圖變更12 HYPERLINK l bookmark80 o Current Document 4.2.3切換到新視圖13 HYPERLINK l bookmark85 o Current Document PBFT算法應(yīng)用15 HYPERLINK l bookmark88 o Current Document 參考161.背景通常情況下，分布式系統(tǒng)由很多節(jié)點(diǎn)組成，系統(tǒng)的可靠性要求系統(tǒng)必須具備應(yīng)付異常節(jié)點(diǎn)發(fā) 送過(guò)來(lái)的不一致消息的能力。分布式的這個(gè)場(chǎng)景最早由Lamport，Shostak和Pease于 1982年形象地描述為拜占庭將軍問(wèn)題(1Leslie Lam

4、port 1982)，即多個(gè)拜占庭將軍各自率 領(lǐng)了小分隊(duì)駐扎在敵方城市之外，他們需要對(duì)是否進(jìn)攻敵軍達(dá)成統(tǒng)一的作戰(zhàn)計(jì)劃，但是這些 將軍之間存在反叛者，他們可能會(huì)篡改、延遲或者丟棄其他將軍的命令，迷惑其他可信將 軍。拜占庭將軍問(wèn)題就是要找到一個(gè)算法來(lái)保證可信將軍之間能夠達(dá)成一致的作戰(zhàn)計(jì)劃。Lamport他們證明了對(duì)于拜占庭將軍問(wèn)題，系統(tǒng)中如果存在f個(gè)不可信節(jié)點(diǎn)，那么只有總節(jié) 點(diǎn)數(shù)不少于3f + 1才存在一個(gè)算法解決該問(wèn)題。下面我們來(lái)簡(jiǎn)單地證明這個(gè)問(wèn)題解的不可能 性，假設(shè)系統(tǒng)中總共有3個(gè)節(jié)點(diǎn)，Commander是提議者，記為C，Lieutenant 1和 Lieutenant 2是驗(yàn)證節(jié)點(diǎn)，記為L(zhǎng)T

5、1和LT2。這三個(gè)節(jié)點(diǎn)中存在一作惡節(jié)點(diǎn)，下面我們 證明在存在一個(gè)作惡節(jié)點(diǎn)的情況下，無(wú)論是提議者還是驗(yàn)證節(jié)點(diǎn)，系統(tǒng)均無(wú)法達(dá)成統(tǒng)一的共 識(shí)。如圖1-1所示，假設(shè)C是作惡節(jié)點(diǎn)，另外兩個(gè)節(jié)點(diǎn)是可信節(jié)點(diǎn)。C向節(jié)點(diǎn)LT1和LT2發(fā)送 了相互矛盾的命令一進(jìn)攻和撤退，那么LT1在接收到C發(fā)送過(guò)來(lái)的進(jìn)攻命令和LT2轉(zhuǎn)發(fā)過(guò) 來(lái)的命令撤退，那么它就無(wú)法確定是要進(jìn)攻還是撤退。Commander圖1-1提議者是作惡節(jié)點(diǎn)C said retreatretreatLieutenant2如圖1-2所示，假設(shè)LT2是作惡節(jié)點(diǎn)，節(jié)點(diǎn)C和LT1是可信節(jié)點(diǎn)，C要求LT1和LT2進(jìn) 攻，但是LT2在轉(zhuǎn)發(fā)C的命令給LT1的時(shí)候作假，告訴

6、LT1它接收到C發(fā)過(guò)來(lái)的命令是撤 退，那么LT1在就無(wú)法判斷到底是要進(jìn)攻還是撤退。圖1-2 Lieutenant 2是作惡節(jié)點(diǎn)從上述論證中我們可以直觀地覺(jué)察到3個(gè)節(jié)點(diǎn)的情況下，即使只有一個(gè)作惡節(jié)點(diǎn)，也無(wú)法達(dá) 成共識(shí)。但如果系統(tǒng)中多一個(gè)可信節(jié)點(diǎn)LT3，則LT1可以收到可信節(jié)點(diǎn)Commander發(fā)出 的和LT3轉(zhuǎn)發(fā)的進(jìn)攻命令，即使LT2節(jié)點(diǎn)發(fā)出撤退命令，LT1也可以正確選擇跟大多數(shù)節(jié) 點(diǎn)一致的進(jìn)攻命令，這樣系統(tǒng)能達(dá)成共識(shí)。我們可以將這個(gè)結(jié)論進(jìn)行推廣，即對(duì)于存在f個(gè) 作惡節(jié)點(diǎn)的分布式系統(tǒng)，當(dāng)節(jié)點(diǎn)總數(shù)不超過(guò)3f的時(shí)候，是不存在一個(gè)可以達(dá)成共識(shí)的解的， 嚴(yán)格的數(shù)學(xué)證明大家可以參考Lamport另夕卜一篇

7、關(guān)于拜占庭錯(cuò)誤的論文(2M. Pease 1980)。學(xué)者們陸續(xù)提出了解決該問(wèn)題的拜占庭容錯(cuò)算法BFT，不是只能用于同步系統(tǒng)，就是性能太 差，難以在生產(chǎn)環(huán)境中廣泛運(yùn)用。為了解決BFT的實(shí)際運(yùn)用問(wèn)題，MIT計(jì)算機(jī)實(shí)驗(yàn)室的 Castro和Liskov于1999年在OSDI會(huì)議上提出了能夠在異步網(wǎng)絡(luò)環(huán)境中工作的PBFT算 法(3Miguel Castro 1999),在借鑒分布式系統(tǒng)的狀態(tài)機(jī)復(fù)制和quorum的基礎(chǔ)上設(shè)計(jì)了 三階段協(xié)議來(lái)解決一致性問(wèn)題，同時(shí)引入了優(yōu)化項(xiàng)，算法的復(fù)雜度由原來(lái)的指數(shù)級(jí)降低為多 項(xiàng)式級(jí)別。下面我們會(huì)講解PBFT算法的模型、算法流程、優(yōu)化，其中算法流程即三階段協(xié) 議是PBFT

8、算法的核心算法流程，是我們的重點(diǎn)講解對(duì)象。2. PBFT算法模型PBFT算法本質(zhì)上是一個(gè)狀態(tài)機(jī)復(fù)制算法，能夠用于實(shí)現(xiàn)帶有狀態(tài)和特定操作的任意確定性 狀態(tài)復(fù)制服務(wù)，它的目的是讓所有的可信節(jié)點(diǎn)執(zhí)行相同的序列。此外，PBFT算法使用安全 的哈希函數(shù)對(duì)消息做摘要、使用公私鑰對(duì)消息進(jìn)行簽名和驗(yàn)簽、同時(shí)增加了消息驗(yàn)證碼，保 證了消息的完整性和不可篡改性。在作惡節(jié)點(diǎn)總數(shù)不超過(guò)系統(tǒng)節(jié)點(diǎn)總數(shù)的1的情況下，PBFT3算法能夠保證系統(tǒng)的安全性和活性。PBFT算法主要包含三類基本協(xié)議：三階段協(xié)議：解決如何達(dá)成共識(shí)檢查點(diǎn)協(xié)議：類似于操作系統(tǒng)的還原點(diǎn)，主要用于垃圾回收視圖變更協(xié)議：用于解決主節(jié)點(diǎn)失效下不工作的情況2.1基

9、本概念首先我們了解一下PBFT算法的基本概念：主節(jié)點(diǎn)primary :負(fù)責(zé)對(duì)請(qǐng)求進(jìn)行排序，發(fā)起新的請(qǐng)求副節(jié)點(diǎn)backup :負(fù)責(zé)驗(yàn)證請(qǐng)求是否有效客戶端client :負(fù)責(zé)提出請(qǐng)求，要求節(jié)點(diǎn)執(zhí)行某個(gè)操作，通常跟主節(jié)點(diǎn)合二為一序列號(hào)sequence number :請(qǐng)求的編號(hào)視圖view : 一個(gè)主節(jié)點(diǎn)和多個(gè)備份節(jié)點(diǎn)形成一個(gè)視圖檢查點(diǎn)checkpoint :如果某個(gè)序列號(hào)對(duì)應(yīng)的請(qǐng)求收到了超過(guò)2的節(jié)點(diǎn)的確認(rèn)，則稱為一個(gè)檢查點(diǎn)。3根據(jù)前面的討論，我們知道PBFT算法是用于解決拜占庭將軍問(wèn)題的，所以系統(tǒng)要能夠容忍 /個(gè)作惡節(jié)點(diǎn)，則系統(tǒng)的總節(jié)點(diǎn)數(shù)不少于3f + 1個(gè)。假定系統(tǒng)中包含1個(gè)主節(jié)點(diǎn)和2f + 1

10、個(gè) 副節(jié)點(diǎn)。三階段協(xié)議三階段協(xié)議是PBFT算法的核心流程，用于解決系統(tǒng)的一致性問(wèn)題，保證所有可信節(jié)點(diǎn)在給 定狀態(tài)和參數(shù)組的條件下，按照相同的順序執(zhí)行完請(qǐng)求后能夠取得相同的狀態(tài)。三階段分別 為pre-prepare、prepare和commit階段，具體的執(zhí)行流程圖如圖3-1所示，下面是正 常的流程：客戶端c在時(shí)間為t發(fā)送請(qǐng)求REQUEST, of t,叱給主節(jié)點(diǎn)，要求執(zhí)行操作。Pre-prepare階段：主節(jié)點(diǎn)0對(duì)請(qǐng)求分配序列號(hào)：完成排序后將請(qǐng)求廣播給所有的 副節(jié)點(diǎn)prepare階段：副節(jié)點(diǎn)i驗(yàn)證在接受到主節(jié)點(diǎn)的請(qǐng)求后，需要驗(yàn)證請(qǐng)求和序列號(hào)在當(dāng) 前的視圖中是否有效，將投票結(jié)果發(fā)給其他節(jié)點(diǎn)com

11、mit階段：每個(gè)節(jié)點(diǎn)在收到超過(guò)2/個(gè)副節(jié)點(diǎn)的投票信息之后，如果請(qǐng)求、序列 號(hào)和視圖均匹配，則生成一個(gè)提交信息發(fā)送給其他節(jié)點(diǎn)，表明接收了對(duì)應(yīng)的請(qǐng)求。每個(gè)節(jié)點(diǎn)在收到超過(guò)f + 1個(gè)節(jié)點(diǎn)的提交信息后，將請(qǐng)求的發(fā)起時(shí)間仁請(qǐng)求的執(zhí)行 結(jié)果廠和當(dāng)前的視圖號(hào)v發(fā)送給客戶端c :REPLY, v, t, c,睥八?？蛻舳嗽诮邮軋?zhí)行結(jié)果r之前，需要阻塞等待/ + 1個(gè)節(jié)點(diǎn)白的響應(yīng)，要求各個(gè)副本節(jié) 點(diǎn)i對(duì)于客戶端C的請(qǐng)求的響應(yīng)中的簽名氣必須有效，同時(shí)這些響應(yīng)中的各個(gè)結(jié)果 r以及請(qǐng)求的時(shí)間戳t需要相同。如果客戶端超時(shí)沒(méi)有收到響應(yīng)，客戶端會(huì)廣播請(qǐng)求給系統(tǒng)中的所有節(jié)點(diǎn)。節(jié)點(diǎn)接收到重復(fù)的 請(qǐng)求的時(shí)候，如果已經(jīng)處理過(guò)該請(qǐng)求

12、的話，那么會(huì)將響應(yīng)再次發(fā)送給客戶端。同時(shí)，副本會(huì) 記錄下自己最近一次發(fā)送給客戶端的響應(yīng)消息。此外，如果節(jié)點(diǎn)不是主節(jié)點(diǎn)的話，需要把請(qǐng) 求轉(zhuǎn)發(fā)給主節(jié)點(diǎn)。如果主節(jié)點(diǎn)不將請(qǐng)求廣播給副節(jié)點(diǎn)，當(dāng)有足夠的副節(jié)點(diǎn)懷疑主節(jié)點(diǎn)是作惡 節(jié)點(diǎn)的時(shí)候，亦會(huì)引發(fā)視圖變更，將主節(jié)點(diǎn)替換掉。圖3-1 PBFT算法流程圖pre-prepare 階段主節(jié)點(diǎn)在收到客戶端的請(qǐng)求后，會(huì)基于當(dāng)前的視圖u對(duì)請(qǐng)求分配編號(hào)n，將視圖號(hào)貝請(qǐng)求 序列號(hào)九、請(qǐng)求摘要d、簽名。封裝成pre-prepare消息PRE - PREPARE, vm,d、，記錄 到本地的消息日志中，然后將pre-prepare消息連同客戶端原始請(qǐng)求m發(fā)送給其他的副節(jié) 點(diǎn)，同

13、時(shí)追加到自己的消息日志中。注意，pre-prepare消息中，是不包含客戶端原本的請(qǐng) 求消息m的，而只是包含了該請(qǐng)求的摘要而已。pre-prepare階段主要是用來(lái)對(duì)請(qǐng)求進(jìn)行 絕對(duì)排序，將請(qǐng)求傳輸和請(qǐng)求排序進(jìn)行解耦，同時(shí)還可以證明在視圖變更協(xié)議中，主節(jié)點(diǎn)在 視點(diǎn)為u的時(shí)候把請(qǐng)求編號(hào)為n。. backup (PRE - PREPA RE, v,n, d舄，m)*I backupf I backup圖 3-2 pre-prepare 階段當(dāng)副節(jié)點(diǎn)接受到主節(jié)點(diǎn)的pre-prepare消息的時(shí)候，在滿足如下的條件的情況下會(huì)接受該 消息。當(dāng)前的視圖號(hào)也是u，即表明pre-prepare消息的發(fā)起者確實(shí)是

14、主節(jié)點(diǎn)客戶端請(qǐng)求m的摘要確實(shí)是pre-prepare消息中帶的摘要d，pre-prepare消息的簽名 是有效的。在當(dāng)前視圖u中，序列號(hào)正還沒(méi)有被用過(guò)，即該節(jié)點(diǎn)沒(méi)有接受過(guò)編號(hào)同樣為n、但是請(qǐng)求 不是m的pre-prepare消息。序列號(hào)正不能過(guò)小、也不能過(guò)大，即nehtH，這個(gè)是為了防止一個(gè)主節(jié)點(diǎn)作惡，選擇 一個(gè)過(guò)大的序列號(hào)來(lái)惡意消耗完序列號(hào)空間。prepare 階段每個(gè)副節(jié)點(diǎn)在上一個(gè)階段驗(yàn)證主節(jié)點(diǎn)的pre-prepare消息有效之后，會(huì)進(jìn)入到prepare階段，生成一個(gè)prepare消息PREPARE, v,幾d,私記錄到本地，表明自己已經(jīng)接受了主節(jié)點(diǎn) 的提議，同意在視圖u中把序列號(hào)九分配給

15、了客戶端請(qǐng)求m，保證自己在這個(gè)視圖中不會(huì)再將序列號(hào)分配給其他的客戶端請(qǐng)求，然后把prepare消息發(fā)送給其他節(jié)點(diǎn)。. r primary蜘叩5.5史瓜j叩I backup圖3-3準(zhǔn)備階段對(duì)于各個(gè)節(jié)點(diǎn)發(fā)送過(guò)來(lái)的prepare消息PREPARE, v,幾d,凱，包括主節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn)接受該消息的條件是：prepare消息的簽名氣正確當(dāng)前節(jié)點(diǎn)的視圖號(hào)是/在視圖號(hào)u中，客戶端請(qǐng)求的編號(hào)不能過(guò)大過(guò)小，即neh,H算法的pre-prepare和prepare階段保證了系統(tǒng)中可信節(jié)點(diǎn)在視圖v中對(duì)于請(qǐng)求m的絕 對(duì)排序取得了共識(shí)。commit 階段當(dāng)各個(gè)節(jié)點(diǎn)做好準(zhǔn)備之后，即本地消息日志中記錄了摘要為d的請(qǐng)求m

16、、記錄了主節(jié)點(diǎn)對(duì)請(qǐng) 求血進(jìn)行排序的pre-prepare消息，同時(shí)接收到了超過(guò)2f個(gè)其他節(jié)點(diǎn)發(fā)過(guò)來(lái)的有效的 prepare消息，各個(gè)節(jié)點(diǎn)會(huì)進(jìn)入下一個(gè)階段，即commit階段。各個(gè)節(jié)點(diǎn)會(huì)生成一個(gè)視圖 為貝請(qǐng)求序列號(hào)為九、請(qǐng)求摘要為D(m)、簽名為氣的commit消息 COMMIT,v,n,D(rn)，mi追加到本地消息日志文件中，同時(shí)廣播給系統(tǒng)內(nèi)的其他節(jié)點(diǎn)。圖3-4提交階段對(duì)于各個(gè)節(jié)點(diǎn)發(fā)送過(guò)來(lái)的commit消息，接受該消息的條件是：COMMIT消息的簽名是正確的當(dāng)前節(jié)點(diǎn)的視圖號(hào)是v對(duì)于客戶端請(qǐng)求m的編號(hào)n e h, H上一個(gè)階段請(qǐng)求的摘要也是D(rn)，對(duì)這個(gè)請(qǐng)求的編號(hào)也是n提交階段保證了可信節(jié)

17、點(diǎn)就本地提交的客戶端請(qǐng)求的序列號(hào)取得了共識(shí)，即便這些客戶端請(qǐng) 求在每個(gè)節(jié)點(diǎn)是在不同的視圖號(hào)中提交的，保證了所有的可信節(jié)點(diǎn)按照給定的順序執(zhí)行了所 有的客戶端請(qǐng)求，從而實(shí)現(xiàn)了安全性。當(dāng)節(jié)點(diǎn)收到超過(guò)/ + 1個(gè)不同節(jié)點(diǎn)發(fā)送過(guò)來(lái)的 commit消息之后，會(huì)執(zhí)行客戶端請(qǐng)求m中所要求的服務(wù)操作，同時(shí)將執(zhí)行結(jié)果發(fā)送給客戶 端，這個(gè)保證了在可信節(jié)點(diǎn)中提交的任意一個(gè)客戶端請(qǐng)求，最終都會(huì)在另夕卜f + 1個(gè)節(jié)點(diǎn)中 被提交到本地的。算法優(yōu)化4.1檢查點(diǎn)協(xié)議PBFT通過(guò)三階段協(xié)議來(lái)對(duì)請(qǐng)求達(dá)成共識(shí)，但是各個(gè)階段產(chǎn)生的消息如果不進(jìn)行垃圾回收的 話，系統(tǒng)的存儲(chǔ)資源將會(huì)不堪重負(fù)。為此，PBFT算法設(shè)計(jì)了檢查點(diǎn)協(xié)議來(lái)丟棄本地的

18、消息 日志文件中的舊消息。垃圾回收的設(shè)計(jì)需要考慮何時(shí)該刪除消息，同時(shí)保證某個(gè)消息在可信 節(jié)點(diǎn)中都被刪除之后，某個(gè)節(jié)點(diǎn)在缺失這些消息的情況下在同步到最新的狀態(tài)后能夠證明這 個(gè)狀態(tài)是正確的。根據(jù)前面的三階段協(xié)議，我們可以知道客戶端收到某個(gè)請(qǐng)求的執(zhí)行結(jié)果的時(shí)候，表明該請(qǐng)求 已經(jīng)被至少/ + 1個(gè)節(jié)點(diǎn)提交過(guò)了，這個(gè)時(shí)候就可以刪除該消息了。對(duì)于第二個(gè)問(wèn)題，檢查 點(diǎn)協(xié)議是通過(guò)提供額外的證據(jù)，checkpoint消息來(lái)證明這個(gè)狀態(tài)是正確的。但是如果每次 執(zhí)行完一個(gè)客戶端請(qǐng)求之后都生成上述要求的證據(jù)，那么這個(gè)操作將是非常昂貴的。實(shí)際 上，PBFT的檢查點(diǎn)協(xié)議是周期性地生成這些證明，比如當(dāng)請(qǐng)求的序列號(hào)整除周期T

19、的時(shí) 候。圖4-1檢查點(diǎn)協(xié)議如圖4-1所示，檢查點(diǎn)協(xié)議的的工作流程如下所示：當(dāng)周期T到達(dá)的時(shí)候，各個(gè)節(jié)點(diǎn)會(huì)生成一個(gè)內(nèi)容為最近一次執(zhí)行的請(qǐng)求的摘要義請(qǐng)求編號(hào)為九、簽名為氣的checkpoint消息(CHECKPOINT, n, d, i)，追加到本地日志記錄 中，然后廣播給系統(tǒng)內(nèi)的其他節(jié)點(diǎn)。氣各個(gè)節(jié)點(diǎn)接受到checkpoint消息后，驗(yàn)證有效后會(huì)追加到本地的日志消息中。當(dāng)各個(gè)節(jié)點(diǎn)在其消息日志中收集到了 2/ + 1個(gè)不同節(jié)點(diǎn)發(fā)送過(guò)來(lái)的有效的且狀態(tài)相同的 checkpoint消息的時(shí)候，那么表明這是一個(gè)穩(wěn)定的檢查點(diǎn)stablecheckpoint，即2f + 1 個(gè)節(jié)點(diǎn)他們最后一次執(zhí)行的請(qǐng)求都是一

20、樣的，而且都分配了序號(hào)隊(duì)當(dāng)一個(gè)檢查點(diǎn)被證明是有效、穩(wěn)定之后，那么節(jié)點(diǎn)會(huì)把本地消息日志中的消息中客戶端 請(qǐng)求序列號(hào)小于或者等于打的消息(pre-prepare、prepare, commit消息)都刪掉。 同時(shí)，它會(huì)刪掉舊的檢查點(diǎn)和checkpoint消息。檢查點(diǎn)協(xié)議除了用于垃圾回收外，還用于更新請(qǐng)求序列號(hào)的有效范圍，序列號(hào)的最低值h設(shè) 為最近一次檢查點(diǎn)里面的請(qǐng)求序列號(hào)，序列號(hào)的最高值設(shè)為H = h + K,其中k需要設(shè)置得大 點(diǎn)，比checkpoint的周期要大，不然節(jié)點(diǎn)收到序列號(hào)較大的請(qǐng)求之后需要阻塞等待到下 個(gè)檢查點(diǎn)才能處理。比如說(shuō)，如果檢查周期是100個(gè)請(qǐng)求，那么k可以設(shè)置成200。4.

21、2視圖變更協(xié)議前面我們提到過(guò)，一些拜占庭算法不能解決主節(jié)點(diǎn)出故障的問(wèn)題。PBFT算法是通過(guò)視圖變 更協(xié)議來(lái)允許系統(tǒng)在主節(jié)點(diǎn)出故障的情況下仍能夠正常運(yùn)轉(zhuǎn)，從而保證了系統(tǒng)的活性。視圖 變更協(xié)議實(shí)際上是通過(guò)超時(shí)機(jī)制觸發(fā)的，通過(guò)超時(shí)機(jī)制，我們可以避免主節(jié)點(diǎn)不工作的情況 下，副節(jié)點(diǎn)無(wú)限期地等待客戶端請(qǐng)求被執(zhí)行。假定系統(tǒng)當(dāng)前狀態(tài)如圖4-2所示，視圖號(hào)為兀圖4-2視圖變更初始視圖v卜面我們來(lái)具體闡述一下視圖變更協(xié)議的具體工作流程。4.2.1維持計(jì)時(shí)器副節(jié)點(diǎn)會(huì)針對(duì)視圖能隹持一個(gè)計(jì)時(shí)器。當(dāng)在收到主節(jié)點(diǎn)發(fā)送過(guò)來(lái)的一個(gè)有效的請(qǐng)求而且沒(méi)有 執(zhí)行的時(shí)候，如果是針對(duì)當(dāng)前視圖的計(jì)時(shí)器還沒(méi)有啟動(dòng)的話，那么節(jié)點(diǎn)會(huì)啟動(dòng)一個(gè)新的計(jì)

22、時(shí) 器。如果節(jié)點(diǎn)還在執(zhí)行其他請(qǐng)求的話，那么節(jié)點(diǎn)會(huì)重置該請(qǐng)求的計(jì)時(shí)器。如果節(jié)點(diǎn)不再等待 執(zhí)行該請(qǐng)求的時(shí)候，會(huì)停止視圖u的計(jì)時(shí)器。4.2.2請(qǐng)求視圖變更如圖4-3所示，當(dāng)副節(jié)點(diǎn)的視圖u的計(jì)時(shí)器如果超時(shí)了，就會(huì)生成一個(gè)view-change消 息，記錄到本地日志文件中，同時(shí)廣播給其他節(jié)點(diǎn)，要求替換掉主節(jié)點(diǎn)，變更到下一個(gè)視圖 u + 1。注意，在視圖變更期間，除了 checkpoint, view-change和newview消息之外， 備份節(jié)點(diǎn)i是不會(huì)接受其他消息的。圖4-3視圖變更計(jì)時(shí)器超時(shí)，發(fā)起視圖變更view-change消息的具體內(nèi)容為以W - CHANGE, v + 1,n, , P, i

23、)，其中最近一次的穩(wěn)定 檢查點(diǎn)對(duì)應(yīng)的請(qǐng)求的序列號(hào)， 是證明該檢查點(diǎn)穩(wěn)定性的2/ + 1個(gè) checkpoint消息的集 合，/是Pm的集合，其中血是副節(jié)點(diǎn)i中的序列號(hào)大于打的等待提交和執(zhí)行的客戶端請(qǐng)求m。每個(gè)九包含了如下的信息：不包含原始請(qǐng)求m的pre-prepare消息，不過(guò)不包含原始的客戶端請(qǐng)求m ,2f個(gè)由其他副節(jié)點(diǎn)簽名的跟pre-prepare消息匹配的、有效的prepare消息(匹配 有效指的是prepare消息中的簽名有效，在視圖u中分配給請(qǐng)求的序列號(hào)一致，客戶 端請(qǐng)求摘要D(rn)相同)各個(gè)節(jié)點(diǎn)收到view-change消息后，會(huì)檢驗(yàn)該消息是否有效，如果有效的話，會(huì)追加到本 地的

24、日志文件中。4.2.3切換到新視圖如圖4-4所示，當(dāng)新視圖v + 1對(duì)應(yīng)的新的主節(jié)點(diǎn)接收到2/個(gè)節(jié)點(diǎn)的發(fā)送過(guò)來(lái)的有效的 view-change消息之后，會(huì)向其他節(jié)點(diǎn)發(fā)送一個(gè)帶上自己簽名。，的new-view消息，提 議系統(tǒng)內(nèi)所有節(jié)點(diǎn)切換到下一個(gè)視圖u + 1，同時(shí)接受自己成為新的主節(jié)點(diǎn)。這個(gè)new- view 消息的另夕卜一個(gè)作用是找到所有節(jié)點(diǎn)的共同的穩(wěn)定檢查點(diǎn)，同時(shí)針對(duì)那些攜帶了尚未 提交執(zhí)行的請(qǐng)求的prepare消息重新生成相應(yīng)的pre-prepare消息，這個(gè)主要是在切換到 新視圖之后，新的主節(jié)點(diǎn)需要重新對(duì)這些未處理的請(qǐng)求分配序列號(hào)，然后對(duì)這些請(qǐng)求再次執(zhí) 行一遍三階段協(xié)議。其中，new-

25、view消息的具體格式為NEW VIEW, v + 1,V, 0):V是主節(jié)點(diǎn)加本地日志中保留的所有要求由視圖U變更為視圖U + 1的有效vew- change消息的集合。0是一個(gè)沒(méi)有攜帶客戶端原始請(qǐng)求m的pre-prepare消息的集合，這些preprepare 消息中對(duì)應(yīng)的請(qǐng)求都是在上一個(gè)視圖u都是有效的，但是還沒(méi)有處理完的。圖4-4視圖變更新的主節(jié)點(diǎn)發(fā)起新視圖副節(jié)點(diǎn)在收到要求將視點(diǎn)變更為v + 1的new-vew消息之后，在確認(rèn)消息有效之后，會(huì)接 受該new-view消息，記錄到本地消息文件中，同時(shí)將視點(diǎn)更換到新的視點(diǎn)u + 1。此外， 副節(jié)點(diǎn)還會(huì)new-view中攜帶的由新的主節(jié)點(diǎn)重新生成的pre-prepare消息都追加記錄到 本地的消息日志中，并按照檢查點(diǎn)協(xié)議進(jìn)行垃圾回收，刪除比較老的消息。然后，對(duì)于 new-vew消息中集合。中攜帶的所有由新主節(jié)點(diǎn)生成的新的pre-prepare消息，備份節(jié)點(diǎn) 都會(huì)生成相應(yīng)的prepare消息，記錄到本地日志文件中，轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)，即對(duì)這些未處 理的請(qǐng)求在新的視圖中重新執(zhí)行一遍三階段協(xié)議，保證視圖切換過(guò)程中未處理的請(qǐng)求能夠重 新被處理。5. PBFT