基于拜占庭容錯的Checkpoint協(xié)議

周 偉，陳 柳，2

(1.華中師范大學(xué)計算機學(xué)院，湖北 武漢 430079;2.武漢工程大學(xué)電氣信息學(xué)院，湖北 武漢 430073)

0 引言

隨著電子商務(wù)［1-2］和基于Web應(yīng)用的迅猛發(fā)展，越來越多的關(guān)鍵應(yīng)用使用Web服務(wù)來構(gòu)造，如支付網(wǎng)關(guān)、LBS［3-5］等。為了防止發(fā)生災(zāi)難性后果，在這些關(guān)鍵的分布式應(yīng)用程序中進行錯誤容忍是必須的。目前研究者們對高可用系統(tǒng)的研究一般集中在良性錯誤，如服務(wù)器崩潰、拒絕服務(wù)攻擊等，但缺乏對更為嚴重的惡意攻擊的研究，譬如軟件錯誤、錯誤操作、密鑰丟失、服務(wù)器被黑客控制等。這種由惡意攻擊引起的錯誤，被稱為拜占庭錯誤［6-9］。由Web服務(wù)組成的分布式應(yīng)用程序具有強自治、松耦合、多層架構(gòu)、跨平臺等特點，現(xiàn)有的拜占庭容錯協(xié)議不再適用。本文根據(jù)Web服務(wù)的新特點，對適用于Web服務(wù)的拜占庭容錯Checkpoint協(xié)議［10-11］展開研究，旨在為現(xiàn)有Web服務(wù)進行拜占庭容錯提供支持。

本文根據(jù)Web服務(wù)的特點，設(shè)計一種拜占庭容錯 Checkpoint協(xié)議［12-13］。Checkpoint協(xié)議在復(fù)制品中定期創(chuàng)建檢查點，將復(fù)制品都認可的穩(wěn)定狀態(tài)保存，這些檢查點可以在復(fù)制品進行狀態(tài)轉(zhuǎn)換［14-15］和前攝恢復(fù)時提供歷史數(shù)據(jù)。與其他的拜占庭容錯Checkpoint協(xié)議相比，該協(xié)議最大的改進在于允許Web服務(wù)改變自身的狀態(tài)，這一點對于Web服務(wù)，尤其是組合服務(wù)尤其重要。

1 算法描述

Checkpoint協(xié)議的主要功能是設(shè)置一些檢查點(Checkpoint)，檢查點的ID以該檢查點對應(yīng)的請求編號命名，當(dāng)前視圖中檢查點n被稱為穩(wěn)定的檢查點的前提是，視圖中至少2f+1(f是發(fā)生拜占庭錯誤的最大復(fù)制品數(shù))復(fù)制品已經(jīng)完成了編號小于n的所有請求。檢查點n穩(wěn)定后，復(fù)制品可以刪除日志中所有小于n的消息，從而保證日志不會無限增長。

進行Checkpoint協(xié)議時，需要服務(wù)復(fù)制品進入靜止?fàn)顟B(tài)，此狀態(tài)下復(fù)制品停止從消息隊列中取新的消息進行處理。設(shè)定復(fù)制品每從消息隊列中取出K個消息后進入靜止?fàn)顟B(tài)，進行Checkpoint協(xié)議，協(xié)議完成后，復(fù)制品重新開始從消息隊列中獲取消息進行處理。

檢查點之間的間隔時間必須合理設(shè)置，如果設(shè)置過長，一旦復(fù)制品出錯就會丟失很多的狀態(tài)信息，如果設(shè)置過短，又會給系統(tǒng)增加過多的負擔(dān)。設(shè)計Checkpoint協(xié)議時，設(shè)置K=Length/2，其中Length是復(fù)制品中消息隊列的長度。

假設(shè)服務(wù)復(fù)制品的集合 T={t1，t2，…，tn}，每個復(fù)制品的抽象狀態(tài)集合 S={s1，s2，…，sm}，這些抽象狀態(tài)存放在磁盤對應(yīng)的分區(qū)集合P={p1，p2，…，pm}中。

為了減少服務(wù)復(fù)制品之間發(fā)送消息的數(shù)量，協(xié)議指定一個復(fù)制品為Checkpoint協(xié)議的發(fā)起者，由它開始發(fā)送checkpoint消息。

Checkpoint協(xié)議過程描述如下:

Step1 服務(wù)復(fù)制品ti自上一個穩(wěn)定的檢查點后，執(zhí)行了K個請求進入靜止?fàn)顟B(tài)，準備建立新的穩(wěn)定的檢查點，并停止從消息隊列中取新的消息進行處理。ti計算新檢查點的編號n，n滿足如下條件:

M是復(fù)制品消息隊列中的消息編號集合，函數(shù)processed(i)判斷消息mi是否被復(fù)制品處理了。

如果是返回值為true，否則為false。

如果消息隊列中沒有消息，n的值為復(fù)制品最后處理的消息的編號。

Step2 ti將當(dāng)前的檢查點n的狀態(tài)信息存儲到本地磁盤。

狀態(tài)信息由以下部分組成:

(1)服務(wù)的抽象狀態(tài);

(2)請求者編號、請求的編號和結(jié)果。

服務(wù)的抽象狀態(tài) si存放在狀態(tài)文件 n.ckp.si中，已經(jīng)處理完畢的請求者編號、請求編號和結(jié)果存放在文件 n.ckp.resulti中。

計算每一個抽象狀態(tài)si的狀態(tài)文件n.ckp.si的摘要值 D(n.ckp.si)，將這些摘要值放入文件n.ckp.s中，并計算得到n.ckp.s的摘要值 ds，如圖 1所示。

圖1 計算服務(wù)的狀態(tài)摘要

對保存的過往請求和結(jié)果摘要文件n.ckp.result計算其摘要值dres=D(n.ckp.result)。計算服務(wù)狀態(tài)和過往計算結(jié)果的摘要值是為了快速比較2個服務(wù)的狀態(tài)是否相同。

如果服務(wù)復(fù)制品ti是Checkpoint協(xié)議的發(fā)起者，ti計算出檢查點n的狀態(tài)摘要值后，向其他復(fù)制品廣播發(fā)送checkpoint消息mchkptti=〈CHECKPOINT，v，n，ds，dres，ti〉σti。

發(fā)送checkpoint消息后，ti啟動計時器。如果計時器到期，ti沒有收到f+1個相同的checkpoint-response消息，將計時器的時間變?yōu)樵瓉淼?倍，再次發(fā)送checkpoint消息。

Step3 復(fù)制品tj在進入靜止?fàn)顟B(tài)后，啟動計時器。如果在計時器超時前，復(fù)制品tj收到Checkpoint協(xié)議的發(fā)起者ti發(fā)送的mchkptti=〈CHECKPOINT，v，n，ds，dres，ti〉σti消息，驗證消息未被修改且來自于 ti后，就發(fā)送checkpoint-response消息mchkreptj=〈CHECK-RESPONSE，v，n'，d's，d'res，tj〉σtj給 ti，其中n'是tj準備建立的檢查點序號，d's和d'res是n'對應(yīng)的狀態(tài)文件摘要。

如果計時器超時前，復(fù)制品tj未收到ti發(fā)送的mchkptti消息，tj向其他復(fù)制品廣播發(fā)送 checkpoint消息mchkpttj=〈CHECKPOINT，v，n'，d's，d'res，tj〉σtj。Step4 如果復(fù)制品ti收到2f+1個具有相同〈v，n'，d's，d'res〉的 checkpoint-response 消息，說明檢查點n'可以成為穩(wěn)定的檢查點。

如果 n=n'∧ds=d's∧dres=d'res，ti向其他復(fù)制品廣播checkpoint-stable消息mchkstbti=〈CHECK-STABLE，v，n，ds，dres，ti〉σti，ti刪除日志中消息編號小于n的所有消息，刪除上一個穩(wěn)定檢查點的狀態(tài)文件，退出靜止?fàn)顟B(tài)，開始從消息隊列中取新的消息進行處理，然后等待下一個檢查點的到來，如圖2所示。

圖2 Checkpoint協(xié)議過程

如果 n=n'∧(ds≠d's∨dres≠d'res)，說明 ti處理消息的過程與其他復(fù)制品相同，但狀態(tài)有缺失，需要調(diào)用State Transfer協(xié)議進行狀態(tài)轉(zhuǎn)換。

如果n＜n'，說明ti處理消息的進度落后于其他復(fù)制品，也需要進行State Transfer協(xié)議進行狀態(tài)轉(zhuǎn)換，使其與其他復(fù)制品的狀態(tài)和進度相同。

如果n＞n'，說明ti處理消息的進度快于其他復(fù)制品，此時可以先不保存此檢查點。

Step5 如果復(fù)制品tj收到checkpoint-stable消息mchkstbti=〈CHECK-STABLE，v，n，ds，dres，ti〉σti，驗證該消息未被修改且來自于ti后，tj知道n成為穩(wěn)定的檢查點，刪除日志中消息編號小于n的所有消息，刪除上一個穩(wěn)定檢查點的狀態(tài)文件。tj退出靜止?fàn)顟B(tài)，開始從消息隊列中取新的消息進行處理，然后等待下一個檢查點的到來，轉(zhuǎn)到 Step1重新開始的Checkpoint周期。

2 實驗結(jié)果與分析

本節(jié)詳細描述在筆者選擇的軟硬件環(huán)境下實現(xiàn)Checkpoint協(xié)議后的測試結(jié)果，檢驗算法的效率。實驗的硬件平臺如表1所示。

表1 硬件平臺配置

進行測試的軟件平臺配置如表2所示。

表2 軟件配置

Checkpoint各階段所需要的平均時間、checkpoint消息、checkpoint-response消息和checkpoint-stable消息的大小相同，加密和解密的時間也取值相同，如表3所示。

表3 Checkpoint各階段平均時間

Checkpoint協(xié)議的發(fā)起者ti完成Checkpoint協(xié)議所需總時間Tchk可由式(1)得到:

化簡可得:

根據(jù)表3、式(1)和式(2)，可以計算出f=1，…，5時的預(yù)測的Checkpoint周期。

實驗時，設(shè)置每個復(fù)制品消息隊列長度Length=512，檢查點之間的間隔k=Length/2=256。設(shè)置f=1，…，5，記錄下 Checkpoint協(xié)議發(fā)起者 ti的 50次Checkpoint周期，計算其平均值，與預(yù)測的Checkpoint周期進行比較，如圖3所示。

從圖3可以看出，實際周期比預(yù)測值稍大，這是因為實際執(zhí)行時復(fù)制品需要比較收到的〈v，n，ds，dres〉是否與自己的相同，這部分時間因為沒法度量沒有加到預(yù)測值中。

圖3 Checkpoint周期

進行Checkpoint協(xié)議時，復(fù)制品需要進入靜止?fàn)顟B(tài)，不會處理請求，這必然會降低系統(tǒng)的吞吐率。實驗時設(shè)置復(fù)制品總數(shù)為3，復(fù)制品消息隊列長度Length=512，檢查點的間隔K值發(fā)生變化，記錄下1000次請求的平均響應(yīng)周期，如圖4所示。

圖4 K值變化時的平均響應(yīng)周期

從圖4可以看到，K值越小，系統(tǒng)的平均響應(yīng)周期就越大。

3 結(jié)束語

本文根據(jù)Web服務(wù)的特點，提出了一種基于拜占庭容錯的Checkpoint協(xié)議。該協(xié)議的主要功能是設(shè)置一些檢查點和設(shè)置檢查點之間的合理時間間隔值K，為恢復(fù)協(xié)議提供正確的時間點。

本文根據(jù)協(xié)議的過程，進行了理論分析，計算出協(xié)議整個過程所需要的周期，并與實驗結(jié)果進行了比較，結(jié)果說明了協(xié)議的有效性。

［1］Castro M，Liskov B.Byzantine fault tolerance can be fast［C］//International Conference on Dependable Systems and Networks.Redmond，WA，USA，2001:513-518.

［2］Microsoft Inc.Bing Maps Now Easier Than Ever［EB/OL］.http://www.microsoft.com/maps/，2011-03-01.

［3］Mastercard.MasterCard Payment Gateway Overview［EB/OL］.https://www.mastercardpaymentgateway.com/mpgpublic/welcome.do，2013-07-08.

［4］Zhao W.Byzantine fault tolerant coordination for Web services atomic transactions［C］//Proceedings of the 5th International Conference on Service-oriented Computing.2007:307-318.

［5］Leslie Lamport，Robert Shostak，Marshall Pease.The Byzantine generals problem［J］.ACM Transactions on Programming Languages and Systems，1982，4(3):382-401.

［6］Aghdaie N，Tamir Y.Implementation and evaluation of transparent fault-tolerant Web Service with kernel-level support［C］//Proceeding of the IEEE International Conference on Computer Communications.2002.

［7］Santos G T，Lung L C，Montez C.FTWeb:A fault tolerant infrastructure for Web services［C］//Proceeding of the 20059th IEEE International EDOC Enterprise Computing Conference(EDOC’05).Enscheda，Netherlands，2005:95-105.

［8］Ramakrishna Kotla，Allen Clement，Edmund Wong，et al.Zyzzyva:Speculative Byzantine fault tolerance［C］//Proceeding of the 21th ACM Symposium on Operating System Principles(SOSP).Stevenson，Washington，2007:45-58.

［9］Allen Clement，Edmund Wong，Lorenzo Alvisi，et al.Making Byzantine fault tolerant systems tolerate Byzantine faults［C］//Proceedings of the 6th USENIX symposium on Networked Systems Design and Implementation.2009:153-168.

［10］OASIS.Web Services Reliable Messaging［EB/OL］.http://docs.oasis-open.org/ws-rx/wsrm/200702，2009-02-02.

［11］孫周軍，易鋒，肖文名，等.基于拜占庭協(xié)議構(gòu)建具有入侵容忍能力的Web服務(wù)研究［J］.微電子學(xué)與計算機，2008，25(3):35-37.

［12］王天鍔，張大方，楊金民.基于代理的Byzantine一致性算法的研究［J］.計算機工程與科學(xué)，2005(4):57-59.

［13］余發(fā)江，張煥國.可信安全計算平臺的一種實現(xiàn)［J］.武漢大學(xué)學(xué)報:理學(xué)版，2004，50(1):69-73.

［14］張煥國，羅捷，金剛，等.可信計算研究進展［J］.武漢大學(xué)學(xué)報:理學(xué)版，2006，52(5):513-518.

［15］Pallemulle S L，Thorvaldsson H D，Goldman K J.Byzantine fault-tolerant Web services for n-tier and service oriented architectures［C］//The 28th International Conference on Distributed Computing Systems.Washington，2008:260-268.