分布式系統(tǒng)中回卷恢復(fù)技術(shù)研究.pdf

1、分布式系統(tǒng)具有用戶投資風(fēng)險小、結(jié)構(gòu)可擴展性好、用戶可繼承原有的軟硬件資源、構(gòu)造簡單等特點，其應(yīng)用領(lǐng)域越來越廣泛。包括大規(guī)?？茖W(xué)計算系統(tǒng)、天氣預(yù)報系統(tǒng)、分時電話系統(tǒng)、飛機訂票系統(tǒng)、銀行系統(tǒng)、股票系統(tǒng)、購物系統(tǒng)等。隨著系統(tǒng)規(guī)模的不斷擴大，其在計算過程中發(fā)生故障的幾率也在指數(shù)增長，系統(tǒng)一旦失效，可能帶來災(zāi)難性的后果，因此迫切需要為分布式計算系統(tǒng)提供容錯機制。檢查點與回卷恢復(fù)(Checkpoint and Rollback-Recovery)技

2、術(shù)是一類重要的軟件容錯技術(shù)，具有實現(xiàn)和使用簡單，對資源要求低等特點，適合在分布式計算環(huán)境中應(yīng)用。
　　分布式計算環(huán)境中，不確定的通信帶寬、存儲空間限制、節(jié)點的動態(tài)性、頻繁的斷開連接等特點決定了為單機系統(tǒng)開發(fā)的回卷恢復(fù)技術(shù)不能直接地應(yīng)用到分布式計算系統(tǒng)中。在保證系統(tǒng)一致性的前提下，減少檢查點和消息日志的存儲開銷、減少回卷恢復(fù)機制引入的通信開銷、提高節(jié)點的自治性(autonomy)、減少由于進程間依賴關(guān)系造成的節(jié)點間藕合、實現(xiàn)回卷恢復(fù)

3、機制對節(jié)點的透明，是分布式環(huán)境下回卷恢復(fù)技術(shù)研究的核心問題。本文圍繞以上內(nèi)容展開研究，主要創(chuàng)新點如下。
　?。?）提出了一種分布式環(huán)境下非阻塞協(xié)調(diào)檢查點及回卷恢復(fù)算法。在分布式計算環(huán)境的實際應(yīng)用中，節(jié)點的自治性很強，希望的容錯機制是一種透明的服務(wù)。提出的檢查點算法基于發(fā)送進程來確保不會產(chǎn)生孤兒消息，不需要接收進程的任何信息，算法每次獲得的檢查點均是全局一致檢查點，直接獲得永久檢查點，跳過臨時檢查點階段，加快了檢查點的形成時間，一個

4、進程是否獲得檢查點與其他進程無關(guān)，算法是否獲得檢查點只與發(fā)送標志有關(guān)，確保了算法的高并行性。某節(jié)點失效后，只需要通過進程廣播一條同步消息，其他進程收到同步消息后，根據(jù)算法做獨立處理，不需要其他進程的額外消息，從而實現(xiàn)了節(jié)點間透明、并行地執(zhí)行回卷恢復(fù)算法。通過算法性能分析和仿真實驗，驗證了算法無故障運行和回卷恢復(fù)階段的低開銷性。
　?。?）提出了一種基于動態(tài)分組的兩級檢查點及回卷恢復(fù)容錯算法。就包含多個結(jié)點的應(yīng)用而言，結(jié)點間交換信息

5、的頻率是不一樣的，甚至相差很大，因此需要一種機制來適應(yīng)分布式系統(tǒng)中進程動態(tài)協(xié)作的特點。提出的算法根據(jù)結(jié)點間通信的頻率、通信時延、通信帶寬及分組中結(jié)點數(shù)等指標來實現(xiàn)動態(tài)分組，實現(xiàn)分組的高內(nèi)聚低耦合。組內(nèi)通信時延小、結(jié)點數(shù)不多，適合協(xié)調(diào)檢查點算法，因此在組級采用協(xié)調(diào)檢查點算法。組間通常是由高時延、低帶寬的網(wǎng)絡(luò)相互連接，并且組間的通信頻率較低，提出的系統(tǒng)級檢查點算法充分考慮了這些特點，每個分組是否獲得檢查點，與其他分組無關(guān)，各個分組可以獨立地

6、，以并行方式獲得系統(tǒng)級檢查點；通過發(fā)送分組來確保分組間不會產(chǎn)生孤兒消息，每次獲得的系統(tǒng)級檢查點均是全局一致檢查點，避免了多米諾效應(yīng)的發(fā)生。算法一方面動態(tài)適應(yīng)了應(yīng)用自身的要求，提高了資源的整體效能，另一方面通過發(fā)送分組來確保分組間不會產(chǎn)生孤兒消息，實現(xiàn)了由傳統(tǒng)的兩階段提交算法到單階段算法的轉(zhuǎn)變。實驗結(jié)果表明，算法執(zhí)行時間較低，相對于傳統(tǒng)的兩階段提交算法，時間復(fù)雜度由通常的O(n2)降低到O(n)。
　?。?）基于XMPP協(xié)議構(gòu)建一個

7、通用的消息傳遞機制。已有檢查點及回卷恢復(fù)算法，都是自定義算法，消息傳遞方式各不相同，沒有通用性可言。我們根據(jù)分布式系統(tǒng)的特點及檢查點算法傳遞的消息特點，構(gòu)建一個通用的消息傳遞機制，該機制基于XMPP協(xié)議，實現(xiàn)了消息的跨平臺、準實時傳輸。對XMPP協(xié)議中XML標簽進行擴展，實現(xiàn)了多種檢查點消息傳輸格式的統(tǒng)一，提高了程序的重用性。
　?。?）原型系統(tǒng)的設(shè)計與實現(xiàn)。在理論研究基礎(chǔ)上，進行系統(tǒng)原型設(shè)計及實現(xiàn)，驗證理論的可實現(xiàn)性，是從理論研