Ｐ２Ｐ存儲系統拜占庭容錯機制研究
2009-01-01 00:00:00楊磊黃浩李仁發李肯立
計算機應用研究 2009年1期
（湖南大學 計算機與通信學院， 長沙 410082）
摘 要：綜述了近年來P2P存儲系統拜占庭錯誤冗余相關技術的研究成果；概述了P2P存儲系統容錯的要求與技術，對現有拜占庭錯誤冗余技術進行了總結；詳細分析對比了目前各種典型拜占庭容錯系統的容錯方式，探討了P2P存儲系統中拜占庭容錯技術需要改進的關鍵問題，并對未來的研究方向進行了討論；最后，給出了一個實際環境下的解決方案框架。
關鍵詞：存儲系統； 拜占庭錯誤； Quorum系統； 冗余； 錯誤檢測
中圖分類號：TP309.3 文獻標志碼：A
文章編號：10013695(2009)01000405
Byzantine fault tolerant mechanism in P2P storage
YANG Lei， HUANG Hao， LI Renfa， LI Kenli
（College of Computer Communication， Hunan University， Changsha 410082， China）
Abstract:This paper surveyed Byzantine fault tolerant productions of P2P storage system in recent years. Then it summarized the fault tolerant demands and techniques in P2P storage system， and the existing techniques of Byzantine fault tolerance. It analyzed and compared fault tolerant techniques of some typical P2P storage systems in detail and explored some key issues of P2P storage system， which should be improved， and discussed the trend of the development of Byzantine fault tolerance systems. Finally， it proposed a possible scheme framework in practical storage system.
Key words：storage system; Byzantine failure; Quorum system; redundancy; failure detection
近年來，P2P存儲系統獲得極大發展。由于采用對等互連技術，P2P存儲系統相對于傳統存儲系統具有較大優勢。雖然P2P存儲系統具有與生俱來的高容錯性，但建立在大規模網絡上的P2P系統對于新加入節點是否為惡意節點尚無有效方法鑒別，這將對系統的可靠性造成重大影響。從整個系統來看，系統中不斷有節點頻繁或永久地加入/退出，導致存儲節點時刻變化，使某些節點在任意時刻可能表現出隨意性的錯誤，致使數據的不一致，即Byzantine錯誤[1]，這將直接影響系統可靠性與數據一致性，使系統readwrite操作錯誤。為了提高P2P存儲系統對Byzantine錯誤冗余能力，使用BFT(Byzantine fault tolerance)容錯機制屏蔽此類錯誤對系統可靠性與數據一致性的影響成為近年來研究的熱點。
本文概述了P2P存儲系統BFT容錯技術，從BFT容錯副本（replication）、糾錯碼（erasurecode）Quorum系統及副本Quorum系統容錯三方面分析了BFT容錯技術，比較和分析了知名BFT容錯存儲系統，并對存在的問題和研究方向進行了討論，提出一種實際環境下的P2P網絡BFT框架。
1P2P存儲系統中的BFT技術
P2P存儲系統容錯一般采用冗余的方法來消除故障的影響。其要求有四個方面：a）系統可靠性。系統在時間t沒有永久丟失數據的概率。b)數據可用性。數據在時間t可以被訪問到的概率。c)系統安全性。系統偶然出現故障的情況下仍能正確運行而不會導致系統崩潰。d)系統可維護性。發生故障后系統修復的難易程度。
在P2P存儲系統中，根據導致故障原因的不同，可將故障分為三類:a)永久性故障。表現出穩定性及持續性的特征。b)間歇性故障。表現出不穩定性及對系統狀態具有依賴性的特征。c)瞬時性故障。由偶然原因引起的短暫故障。間歇性故障中包含一種隨意性故障（Byzantine錯誤），表現為存儲節點在任意時間產生隨意響應，存儲節點可能產生它從來沒有過的輸出響應。更壞的情況是，發生故障的節點惡意地與其他節點共同工作而產生對系統不利的惡意錯誤結果。產生Byzantine錯誤后，要保證系統正常運行，就需使用Byzantine容錯技術。目前，Byzantine將軍算法是解決該問題的有效機制。該算法實質是一種信息安全技術，由Lamport等人[2]提出，他們證明了在系統中，對于f個Byzantine錯誤節點，需3f+1個或以上副本的冗余才能使系統冗余Byzantine錯誤。
2 P2P存儲系統中的BFT容錯相關技術研究
目前解決P2P存儲系統Byzantine錯誤的系統很多，使用的方法也不盡相同，如何對使用的容錯方式分類也沒有統一的標準。由于對Byzantine錯誤的冗余需對系統所存儲數據進行冗余備份，本文以備份方式的不同將Byzantine容錯技術分為三類：a）BFT副本容錯技術，典型代表有Pond[3]、Zyzzyva[4]和PBFT[5]，以及AbdElMalek等人[6]提出的；b）BFT糾錯碼Quorum容錯技術，典型代表有Agile store[7]、Reperasure[8]，以及Goodson等人[9]和Cooley等人[10]提出的；c）BFT副本Quorum容錯技術，典型代表有HQ[11]、Antiquity[12]。
2.1 BFT副本容錯
BFT副本容錯實質是副本（復制）算法與Byzantine將軍算法結合來冗余Byzantine錯誤。由于P2P存儲系統中節點頻繁加入/退出系統，若不對存儲數據進行冗余處理，在有存儲節點失效的情況下，其上存儲的數據將無法恢復。副本的冗余方式可分為兩種：對要存儲的數據保存多個完整的副本；將要保存的數據分成碎片，對每個碎片保存多個完整的副本，再將這些副本分發到其他節點上。當出現節點失效時，通過訪問存儲這些副本的節點實現對數據的冗余。當這些存儲副本的節點發生Byzantine錯誤時，通過使用Byzantine將軍算法，在節點副本數據不一致時能實現對該錯誤的冗余，保持系統可靠性、節點數據一致性和系統安全性。該容錯方式在穩定的環境中（節點處于機房或服務商提供），假設系統中每個存儲節點都等概率地失效，采用隨機過程的方法建模分析[3，5]表明，使用該方式的系統對Byzantine錯誤有較好的容錯能力。
2.2 BFT糾錯碼Quorum容錯
該方法是糾錯碼算法與Quorum系統、Byzantine將軍算法相結合冗余P2P存儲系統中的Byzantine錯誤。
2.2.1 Quorum系統
Quorum系統是一種以冗余設計為基礎的集合系統，每個Quorum由多個節點構成，這些節點之間通過相互通信和數據復制保持數據操作的一致性。同時，各個Quorum之間又通過相交節點把各自的Quorum內部數據復制給其他Quorum的所有節點。當某些節點發生不可預測的錯誤時，系統通過執行特殊協議，從有效節點所保留的冗余信息中獲得正確的結果。
Quorum系統容錯協議可分為兩類：互斥協議和選舉協議[13]。互斥協議主要用于Quorum系統中數據write操作出現同步或沖突的處理，有時也執行從不包含失效節點的單個有效Quorum的節點中獲取有效數據來冗余read操作的錯誤。當有一個節點同時要被兩個write操作使用時，若是對該節點存儲的同一數據執行write操作，則系統比較兩個write操作的時間戳或優先權[14]。選舉協議主要是從含有失效節點的Quorum中獲取有效數據冗余read操作的錯誤。它將系統節點存儲數據進行很多備份，當有節點失效時，只要當前Quorum有效節點所包含的正確數據足夠多，客戶仍將可以從系統節點返回的數據中獲得有效信息。
Quorum系統性能的評判主要包括：a）系統的規模（size），即Quorum系統中全部節點個數。系統容納節點數越多，其內部節點之間通信代價越高，冗余Byzantine錯誤響應時間越長。系統容納節點數越少，內部節點之間通信代價越低，但由于存有有效數據的節點數目少，對Byzantine錯誤的冗余未必有效。b）系統可靠性，即假設Quorum系統中每個節點等概率P失效，當發生節點失效時，剩下的有效節點仍能組成一個有效Quorum系統的概率。該概率越高，說明系統越可靠，系統的容錯性能就越好。c）系統代價（cost），即實現容錯Quorum系統的開銷。它主要由系統所需副本總數和副本的應用狀態決定[4，5，11，15，16]。d）最大可失效節點個數f，即Quorum系統在有效運行時最大可失效的節點個數。f越大，系統能容納的失效節點數就越多，系統容錯性越強。其中f可以是定值[3]，也可隨Quorum系統的運行動態調整[11，12，15]。另外一些研究者也考慮到吞吐量（throughput），即單位時間內流經被測存儲系統的數據流量[4，17]。
2.2.2 BFT糾錯碼Quorum容錯
糾錯碼[18]是將要存儲的數據先切分為M個部分，然后通過編碼算法將這M個部分變換為N個部分，其中任意N*(N*≥M)個部分用于修復原始數據。如圖1所示，當N*=M時，稱該編碼算法具有最大分割性質。糾錯碼可分為兩大類：低密度校驗碼[19]和ReedSolomon碼[20]。BFT糾錯碼Quorum容錯實質上是用錯碼方式對數據進行冗余備份，再結合BFT和Quorum系統對P2P存儲系統的容錯方法。該系統假設各個Quorum之間邏輯相鄰節點包含足夠的數據備份，在發生拜占庭錯誤時，系統可從這些有效節點的數據備份中取得有效信息冗余該錯誤。其組織方式是：若系統最大可失效節點個數為f，其有效節點個數大于等于2f+1條件下的Quorum系統組織方式。在此組織方式下， f/(2f+1)＞50%，系統的有效可信度永遠大于50%。
2.3 BFT副本Quorum容錯
BFT副本Quorum容錯實質上是用副本方式對數據進行冗余備份，再結合BFT和Quorum系統對P2P存儲系統的容錯方法。該方法是近年來采用的新技術[11，12]，相對于糾錯碼冗余的方式，完全副本冗余所需計算量較小，對于系統設計實現和維護的復雜度更低。在實際的高動態環境運行的系統中，節點的可用性高時，具有最低碎片數的全數據副本方式比糾錯碼冗余更有優勢，可提高系統的可靠性和數據的可用性[21]。文獻[12]還給出了失效節點數在未達最大可失效節點數時，對必須即時修復的重大故障進行立即修復的方法，提高了系統的可靠性。
3 基于BFT容錯的知名P2P存儲系統述評
3.1 MIT的PBFT（practical Byzantine fault tolerance）
PBFT[5]構建了高可靠性的P2P存儲系統冗余Byzantine錯誤。系統中副本和客戶機運行在分布式系統的不同節點中，BFT執行狀態機副本。系統提供實時服務。為了提升系統安全性能，系統在鑒別消息時使用對稱性加密技術。在該技術和數據冗余方式下結合BFT將軍算法，使得錯誤節點很難偽造身份，在對手攻擊時，通過鑒別管道，可為系統提供安全保障。系統使用以下方法優化性能：a）對稱加密技術MACs鑒別消息；b）分類回復；c）試探執行；d）只讀操作；e）請求定量（batching）。實驗結果表明，該方法可構建實際環境中的拜占庭容錯系統。
3.2 Zyzzyva
Zyzzyva[4]實質上是對sync for BFT[22]的再改進。其使用speculation方法降低系統開銷，簡化了BFT副本狀態機制的設計復雜度。系統執行三個子協議：a）Agreement。該協議通過副本順序化回復客戶請求。b）View change。該協議在當前主節點（primary）失效或系統運行緩慢時采用選舉協議產生一個新主節點。c）Checkpoint。該協議限制了通過副本必須被存儲的狀態，并且降低了view change協議執行的代價。系統運行時，當客戶請求必須回復時，采用對大量命令請求進行排序后再回復客戶請求或立即回復客戶請求。實驗表明，該方法使Zyzzyva降低了副本的overheads，使其接近理論的最小值3f+1且增加了吞吐量的最大值，通信時延也接近理論上的最低值。
3.3 Agile store
Agile store[7]是一種高效BFT 糾錯碼Quorum存儲系統。其數據冗余采用糾錯碼機制。它提出可重配置的Quorum技術，允許系統規模和最大可失效節點個數f依系統實際運行而動態變化。系統由三個部分組成：a）提供文件系統服務的服務器節點；b）使用文件系統的客戶機節點；c）向存儲系統提供錯誤檢測的服務。Byzantine容錯編碼位于服務器節點中。系統中客戶代理是一用戶空間，該空間輸出NFS文件服務器接口到客戶機。客戶代理通過元數據服務與數據服務器的交互完成NFS請求。元數據服務執行BFT狀態機制[23]。Agile原型系統使用CastroLiskov協議[24]。為了保證在有代理服務器失效時read操作和write操作的一致性，MACs被使用于請求和回復。
3.4 Q/U
Q/U[6]為一種高效的BFT副本Quorum協議。Q/U系統提供一個基于操作的接口，該接口用于維護類似狀態副本機。系統允許對象輸出窄接口，該接口可限制發生錯誤的客戶機隨意修改存儲數據。Q/U系統在異步模式可容忍發生Byzantine錯誤的客戶機和服務器節點，使系統安全運行。Queris操作和update操作使用obstructionfree[25]方法，嚴格執行讀寫互斥協議。系統還添加了多種技術優化容錯性能：通過在versioning使用非損壞性結構更新，使update操作有效解決更新沖突或更新失敗；結合使用邏輯時間戳和對象狀態，平衡化versioning功能；使用高效的加密技術維護數據私密性。在此設計下，系統可冗余更多錯誤，但系統代價與其他方法相比需正確的服務器節點數量有所增加：Q/U協議需要5f+1個服務器來容忍f個發生Byzantine錯誤的服務器；而大部分方法只需3f+1個服務器。
3.5 HQ
HQ[11]綜合文獻[5，6]方法的優點，提出一種新的BFT執行方式。整個系統在最大可失效節點個數f動態變化的情況下運行，用3f+1個副本冗余f個Byzantine錯誤。系統編碼作為代理服務器運行在客戶機和服務器端口，服務器編碼用于維護副本的狀態。未發生沖突時，HQ使用一個改進的Byzantine Quorum協議；當沖突發生時，它使用PBFT狀態機副本算法[5]處理沖突。Readwrite協議采用互斥協議。其實驗主要結論是：P2P存儲系統中，如果低沖突和低時延是主要問題，且使用5f+1個副本可接受，則Q/U為最佳選擇，否則HQ為最佳選擇；否則，在此情況下，PBFT為最佳選擇；除此之外，HQ為最佳選擇。
3.6 Antiquity
Antiquity[12]是OceanStore[3，26，27]系統的繼續發展，系統構建在較穩定的服務商提供的節點集合上。其Pond[3]原型系統在穩定環境下采用BFT副本容錯協議抵抗Byzantine錯誤。經改進的Antiquity可在動態的環境中保持系統可靠性、數據一致性和高可用性。Antiquity使用安全日志保持數據完整性，并備份每個日志到可靠的服務器，使用BFT Quorum 協議確保副本一致性。該協議與HQ基本一致，可對最大可失效節點個數f進行動態調整。但HQ方式必須達到最大可失效節點個數f時系統才進行修復。這可能錯失發生重大錯誤需立即修復的時機。Antiquity允許系統未達最大可失效節點個數，在發生需立即修復的錯誤時即時開始修復。為此，存儲服務器中存儲soundness proofness，并包含最后一次修復成功時的soundness proofness，以標示需立即修復的存儲數據。Antiquity在WAN和LAN上通過實驗驗證了性能：在所有服務器節點不停變化的動態環境中，所有數據日志均可被長期維持。
3.7 P2P存儲系統BFT容錯小結
本文總結了上述典型P2P存儲系統Byzantine容錯相關技術（表1）。不難發現：各個系統所設計的工作環境不同；對采用副本或糾錯碼數據冗余方式偏好不同；對是否使用Quorum系統也不一致。但從總體上看，使用副本和糾錯碼冗余數據結合Quorum系統方式逐漸成為主流。另外，其他知名BFT存儲系統還包括SafeStore[28]、Explode[29]，以及Li[30]、Singh[31]、Martin等人[32]提出的，本文不再逐一介紹。
表1 P2P存儲系統容錯對比
系統適應環境冗余方式最大可失效節點個數系統代價總副本數吞吐量代理服務器安全技術讀寫協議
PBFT實際環境BFT副本-3f+1[2+(8f+1)]/f否對稱加密HMACs互斥協議
Zyzzyva穩定BFT副本-3f+1（2+3f）/f否MACs互斥協議
Agile穩定BFT糾錯碼Quorum可變3f+1-是MACs選舉協議
Q/U穩定BFT副本Quorum固定5f+12+8f否對稱加密HMACs互斥協議
HQ穩定BFT副本Quorum可變3f+14+4f是MACsauthenticator互斥協議
Antiquity高動態BFT副本Quorum可變3f+14+4f是安全日志數字簽名數據校驗加密關鍵字選舉協議
4 存在問題和研究方向討論
4.1 BFT適應環境
由以上分析不難發現，當前使用BFT的P2P存儲系統大多運行于穩定的環境中，在此基礎上對Byzantine錯誤的冗余取得了較好的研究成果，但實際網絡環境是一個高動態的環境（節點頻繁加入/退出系統或永久退出系統、系統規模動態擴大/縮小）。目前的研究基于穩定環境中系統節點等概率失效的條件下進行研究和性能分析，建立的容錯概率模型一般是泊松過程和馬爾可夫過程模型[4，11]。實際環境中系統節點是永久離開還是暫時離開，將直接影響對是否為Byzantine錯誤的判斷及系統如何修復錯誤[33，34]。此時，系統節點應為非等概率失效。如何建立數據服務處理和容錯概率模型，使該BFT操作滿足特殊系統失效概率模型下處理的要求；能否將現有的安全日志和快照（snapshot）技術（加入該技術可有效降低系統容錯的復雜度，對系統性能的影響也小）、對稱和非對稱的加密技術運用于實際動態環境中都值得考慮。今后該方面的研究將重點集中在動態環境中如何設計非等概率節點失效BFT模型及現有穩定環境中有效的各種技術能否成功應用于實際動態環境。
4.2 數據冗余方法選擇
如前所述，數據冗余方法的選擇直接影響到P2P存儲系統容錯的性能。目前數據冗余方法主要為糾錯碼和副本冗余，兩者各有優缺點。OceanStore的研究者Weatherspoon等人[35]用量化的方法分析了糾錯碼和副本方式冗余對系統可靠性和數據可用性的影響：在較為穩定的環境中，假設存儲節點等概率失效的情況下，如果取得相同系統可靠性和數據可用性時，相對于副本冗余，使用糾錯碼冗余可降低系統代價，節省存儲空間。Rodrigues等人[36]從系統的可靠性和可維護性角度比較了這兩種冗余方式，指出了糾錯碼方式在動態環境中的局限性。廣泛使用的BFT副本方式盡管提供了高系統可靠性和數據可用性，系統維護較簡便，但副本所占存儲空間代價很大，而且系統的參數不能動態變化。
筆者認為：在穩定環境中，為了容忍最壞情況，BFT Quorum副本系統相較于糾錯碼系統常保守地選擇一個較大數值作最大可失效節點個數，導致系統中副本數目遠大于實際需要。另外，當存儲系統的Quorum規模固定時，很難動態地反映存儲節點加入與退出系統的情況[37~39]。明顯地，在基于P2P的廣域存儲系統的實際動態環境中，選擇何種冗余方式進行數據冗余修復節點的失效，能否在存儲系統數據冗余中綜合糾錯碼和副本冗余方式的優點以提升系統的性能，是廣域存儲系統BFT今后研究的關鍵問題之一。
4.3 最大可失效節點個數f
在存儲系統規模不變的情況下，最大可失效節點f越大，系統能冗余的Byzantine錯誤就越多。但對系統而言，并非f值越大越好。若f值越大，則系統中出現的Byzantine錯誤越多，修復這些錯誤系統所需的代價越大，最終可能導致失去對發生重大錯誤或系統關鍵信息受損即時修復的時機，系統無法負擔而崩潰[12]。f值的動態變化雖然提高了系統的可靠性和容錯能力，但對系統計算量要求很大，設計實現的復雜度大，動態環境中f值估算困難；而f值固定方式系統實現簡單，更易于維護[40]。更重要的是，目前各原型系統均是在系統規模較小時取得的結果，當系統運行于實際環境存儲節點規模極大時，以上原型系統容錯協議很難滿足大規模系統各方面性能的要求。
筆者認為：能否將大規模系統劃分為小規模系統分區管理，即將大規模系統按一定方式進行初始化分組，將每個分組按適當的現有BFT機制組織。此時各分組規模較小，又選擇了適合的容錯方式，故各分組系統容錯性能將與現有原型系統性能相近，從而使完整系統容錯性能更優，使完整系統總的最大可失效節點個數更大。按照這種思想，采用何種方法進行分區以及分區后各區的管理和協作機制以提高系統性能將是今后研究的熱點之一。
4.4 Byzantine錯誤判定
存儲系統的故障有多種，每種故障修復方式都不同。因此，如何判斷節點失效是否為Byzantine錯誤對于系統容錯十分重要，其直接影響到對錯誤的修復策略。目前判斷節點失效的方法主要有兩種，即定期心跳和失效廣播。定期心跳是指每個存儲節點定期向其對應目錄節點報告自己的狀態，如果對應目錄節點一段時間內沒有收到心跳則認為該節點失效。失效廣播是當系統中一個節點失效后，認為其鄰近節點會發現這個事件，它通過存儲網絡廣播機制將這個事件通知其他節點。Byzantine錯誤是存儲節點在任意時刻表現出的隨意性錯誤，其錯誤檢測十分困難。Douceur等人[41]提出了一種檢測和隔離Byzantine錯誤的方法。劉剛等人[42]使用BFT糾錯碼Quorum容錯，提出了一種使用時間戳和失效節點集方式檢測Byzantine錯誤的方法，在實驗中取得了很好的效果。但該系統假設的容錯機制為存儲系統的安全模式，已能對客戶機惡意攻擊存儲節點有效抵制，且系統元數據服務器與管理服務器不會發生任何失效，一個正確的存儲節點將對所有請求作出正確響應。可見作者的假設為一種穩定的理想環境，在實際的高動態環境中能否取得良好實驗結果還值得觀察。在實際環境中節點失效故障類型的有效判定，是今后研究的主要方面之一。
5 一種實際環境下P2P存儲網絡BFT框架
5.1 基于異構BFT的分層P2P存儲網絡劃分
由于實際P2P網絡是一個大規模高動態的組織環境，使用以上三種BFT容錯技術之一很難取得到較好的性能。為適應實際需求，擬對大規模系統進行劃分，方法如下：從實際系統中隨機選取一個節點，以該點為中心，一定閾值（該值可根據此劃分需采用的哪種P2P存儲BFT容錯系統規模最適合大小進行動態調整）為半徑內的所有節點組成一個節點集，將此節點集按現有三種P2P存儲BFT容錯系統中能較好滿足其性能要求的BFT容錯系統方式組織，形成一個BFT網絡劃分。以此方法，可將整個存儲系統劃分為幾個較小的部分。對于每個劃分，從中選出少數性能較強的節點作為超節點，這些超節點以內部環的形式組織，各劃分又通過各自超節點互連在一起，形成一個兩層的覆蓋網絡，如圖2所示。
由于劃分中節點為隨機選擇，可能實際系統中仍存在極少數節點未加入各劃分。此時，逐一計算剩余節點到各個劃分節點集各超節點距離的平均值，將剩余節點歸入距離平均值最小的劃分中，從而整個系統中節點都進入相應劃分節點集，所有節點劃分完畢，即可有效地利用現有成熟系統的優點提升實際環境下P2P網絡系統的性能。
5.2 混合冗余方式的層次副本生成機制
對于使用BFT糾錯碼Quorum的劃分，由于糾錯碼方式下修復一個失效的碎片就需要一個完整的副本，會造成帶寬嚴重浪費。采用糾錯碼與副本方式結合的兩層冗余方法：首先對存儲數據作糾錯碼冗余，然后對每個冗余碎片作副本冗余，這樣丟失一個碎片就只需從另一個碎片的副本處讀取同樣大小的數據修復即可。該方法可提高此劃分的帶寬利用率并有效降低通信時延，從而在一定程度上提升整個系統的性能。
5.3 日志與快照技術相結合的數據持久存儲
采用日志結構的P2P存儲系統一般具有更好的Byzantine容錯性能，為了保證系統所存儲數據的完整性和持久性，對系統中各劃分的每個從節點建立一個日志，并將其日志備份到相應劃分超節點上，而各劃分超節點的日志信息則在彼此之間進行備份，用該方法來維持所有節點在系統中現有數據與原始數據的改變信息，各節點通過它來查找所需數據及修改數據。由于使用日志結構在最壞的情況下查找某節點可能需遍歷整個系統，為避免此狀況，采用快照技術：每個節點維持一個私有快照，該快照用于保存其經常訪問節點日志地址的指針。使用該方法可提高系統查詢命中的幾率，避免需遍歷整個節點日志的最壞情況，且快照方式存儲的是節點日志地址的指針，所占存儲空間較小，在有節點頻繁加入/退出系統時對地址備份的替換方便。當有節點要求加入系統時，可按照處理剩余節點的方法確定其加入的劃分。此時，將新節點性能與所處劃分中超節點性能進行比較。若新節點性能優于超節點，則用其替換與其所比較的超節點；反之，新節點成為此超節點的從節點，并建立相應日志。當有節點退出時，在其對應超節點中刪除此節點日志信息即可。在實際P2P存儲系統使用上述方法時，系統對Byzantine錯誤冗余性能應有較大提高。
6 結束語
P2P存儲系統近年來得到迅速發展，顯示了其在未來廣泛的應用前景。雖然P2P存儲系統在冗余和檢測Byzantine錯誤方面仍有難題，但隨著研究的深入，使用BFT冗余機制的P2P存儲系統必將成為一種重要的存儲組織模式。本文對已有典型原型系統技術應用環境及性能優劣進行了比較。可以看到：在穩定的環境中，BFT各種冗余機制對P2P存儲系統節點故障的冗余已表現出良好性能，然而在實際動態環境中，BFT冗余機制的使用還有待深入探討。因此，針對實際動態環境，需要盡快對P2P存儲系統結構設計和BFT冗余策略作進一步研究，使得P2P存儲系統在實際動態環境中Byzantine容錯取得突破性進展。
參考文獻：
［1］LEWIS C S， SAIA J. Scalable Byzantine agreement[R]. New Mexico: University of New Mexico， 2004.
[2]LAMPORT L， SHOSTAK R， PEASE M.The Byzantine generals problem[J].ACM TOPLAS，1982，4(3):382401.
[3]RHEA S， EATON P， GEELS D，et al. Pond: the Ocean Store prototype[C]//Proc of USENIX FAST. 2003.
[4]KOTLA R， ALVISI L， DAHLIN M，et al.Zyzzyva：speculative Byzantine fault tolerance，UTCSTR0740[R]. Austin:University of Texas， 2007.
[5]CASTRO M， LISKOV B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Trans on Computer Systems，2002，20(4):398461.
[6]ABDELMALEK M， GANGER G R， GOODSON G R，et al. Faultscalable Byzantine fault tolerant services[C]//Proc of the 20th ACM Symposium on Operating Systems Principles. 2005:5974.
[7]KONG Lei，MANOHAR D J， SUBBIAH A， et al. Agile store: experience with Quorumbased data replication techniques for adaptive Byzantine fault tolerance[C]//Proc of the 24th IEEE Symposium on Reliable Distributed Systems.2005:143154.
[8]ZHANG Zeng， LIAN Qiao. Reperasure: replication protocol using erasurecode in peertopeer storage network[C]//Proc of the 21st IEEE Symposium on Reliable Distributed Systems. 2002:330335.
[9]GOODSON R G，WYLIE J J， GANGER G R，et al. Efficient Byzantinetolerant erasurecoded storage[C]//Proc of International Conference on Dependable Systems and Networks. 2004.
[10]COOLEY J A，MINEWEASER J L，SERVI L D，et al. Softwarebased erasure codes for scalable distributed storage[C]//Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies. 2003:157164.
[11]COWLING J， MYERS D， LISKOV B，et al. HQ replication: a hybrid Quorum protocol for Byzantine fault tolerance[C]//Proc of OSDI. 2006.
[12]WEATHERSPOON H， EATON P， CHUN B G，et al.Antiquity：exploting a secure log for widearea distrbuted storage[C]//Proc of EuroSys’07. 2007.
[13]KIM J M， MANABE Y. A Byzantine fault tolerant mutual exclusion algorithm and its application to Byzantine fault tolerant storage systems[C]//Proc ofthe 25th IEEE Conference on Distributed Computing Systems. 2005.
[14]BAZZI R， DING Ying. Nonskipping timestamps for Byzantine data storage systems[C]//Proc of the 18thInternational Symposium on Distributed Computing.[S.l.]: SpringerVerlag， 2004:405419.
[15]RODRIGUES R. Robust services in dynamic systems[D]. Massachusetts: MIT， 2005.
[16]CACHIN C， TESSARO S. Optimal resilience for erasurecoded Byzantine distributed storage[C]//Proc of International Conference on Dependable Systems and Networks.[S.l.]: IEEE Computer Society， 2006:115124.
[17]KOTLA R， DAHLIN M. High throughput Byzantine fault tolerance[C]//Proc ofInternational Conference on Dependable Systems and Networks.[S.l.]:IEEE Computer Society， 2004:575584.
[18]KIM S. Efficient erasure code for wireless sensor networks[EB/OL].(2004).http://www.eecs.berkeley.edu/~bine tude/course/cs270/paper.pdf.
[19]MITZENMACHER M. Digital fountains: a survey and look forward[C]//Proc of Information Theory Workshop. 2004:271276.
[20]PLANK J S. A tutorial on ReedSolomon coding for faulttolerance in RAIDlike systems[J]. Software Practice and Experience， 1997，27(9):9951012.
[21]LIN W K， CHIU D M， LEE Y B. Erasure code replication revisited[C]//Proc ofthe 4th International Conference on PeertoPeer Computing. 2004:9097.
[22]NIGHTINGALE E B， VEERARAGHAVAN K， CHEN P M，et al.Rethink the sync[C]//Proc of the 7th OSDI. 2006.
[23]MARTIN J P， ALVISI L. A framework for dynamic Byzantine storage[C]//Proc of DSN. 2004.
[24]CASTRO M， LISKOV B. Proactive recovery in a Byzantine fault tolerant system[C]//Proc of the 4th OSDI. 2000.
[25]HERLIHY M， LUCHANGCO V， MOIR M. Obstructionfree synchronization: doubleended queues as an example[C]//Proc of International Conference on Distributed Computing Systems.[S.l.]:IEEE Press， 2003:522529.
[26]WELLS C. The OceanStore archive: goals， structures， and selfrepair[D]. Berkeley UC:University of California， 2002.
[27]KUBIATOWICZ J， DAVID B， CHEN Yan，et al. OceanStore: an architecture for globalscale persistent storage[C]//Proc of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems. 2000:190201.
[28]KOTLA R， ALVISI L， DAHLIN M. SafeStore: a durable and practical storage system[C]//Proc ofUSENIX Annual Technical Conference. Monterey， CA:[s.n.]，2007.
[29]YANG Junfeng， SAR C， ENGLER D. Explode: a lightweight， general system for finding serious storage system errors[C]//Proc of OSDI. 2006.
[30]LI Jinyuan， MAZIRES D. Beyond onethird faulty replicas in Byzantine fault tolerant services[C]//Proc ofNSDI. 2007.
[31]SINGH A， MANIATIS P， DRUSCHEL P，et al.Conflictfree Quorumbased BFT protocols， Technical Report 20071[R].[S.l.]:Max Planck Institute for Software Systems， 2007.
[32]MARTIN J P， ALVISI L. Fast Byzantine consensus[C]//Proc ofInternational Conference on Dependable Systems and Networks.[S.l.]: IEEE Press， 2005:402411.
[33]WEATHERSPOON H， CHUN B G，SO C W，et al.Longterm data maintenance in widearea storage systems: a quantitative approach[C]//Proc of the 1st International Warkshop on PeertoPeer Systems. 2005.
[34]SIT E， HAEBERLEN A， DABEK F，et al.Proactive replication for data durability[C]//Proc of the 5th International Workshop on PeertoPeer Systems. Santa Barbara:[s.n.]， 2006.
[35]WEATHERSPOON， KUBIATOWICZ J D. Erasure coding vs replication: a quantitative comparison[C]//Proc ofIPTPS. Berlin:Springer， 2002.
[36]RODRIGUES R， LISKOV B. High availability in DHTs: erasure coding vs replication[C]//Proc of the 4th International Workshop on PeertoPeer Systems. Berlin:springer， 2005:226239.
[37]CHUN B G， DABEK F， HAEBERLEN A，et al. Efficient replica maintenance for distributed storage systems[C]//Proc of the 3rd Symposium on Networked Systems Design and Implementation. Berkeley，CA: USENIX Association， 2006.
[38]HENDRICKS J，GANGER G R，REITER M K. Lowoverhead Byzantine fault Tolerant storage[C]//Proc of SOSP’07. New York: ACM Press， 2007:7386.
[39]PREGUICA N， LOURENCO J， RODRIGUES R. Byzantium: eficient Byzantine faulttolerant database replication[EB/OL].(2006).http://citi.di.fct.unl.pt/project/project.php?id=60.
[40]LISKOV B， RODRIGUES R. Tolerating Byzantine faulty clients in a Quorum system[C]//Proc of the 26th International Conference on Distributed Computing Systems.Washington DC: IEEE Computer Society， 2006:3443.
[41]DOUCEUR J R， HOWELL J. Byzantine fault isolation in the farsite distributed file system[C]//Proc of the 5th IPTPS. 2006.
[42]劉鋼，周敬利，秦磊華，等.糾錯碼拜占庭容錯Quorum中錯誤檢測機制[J].計算機科學，2007，34(5):7578.
