分布式容錯(cuò)檢查點(diǎn)算法研究與軟件設(shè)計(jì).pdf

1、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，分布式系統(tǒng)應(yīng)用的不斷拓展，分布式應(yīng)用對(duì)高可靠性和可用性的要求越來越迫切。一個(gè)高可用性的系統(tǒng)要求在任何情況下服務(wù)不會(huì)被中斷并且能夠提供正確的服務(wù)，因此，分布式系統(tǒng)的容錯(cuò)問題是目前分布式系統(tǒng)研究的熱點(diǎn)和難點(diǎn)，同時(shí)也是一個(gè)富有挑戰(zhàn)性的課題。由于分布式系統(tǒng)在地理區(qū)域分布的廣泛性，使得整個(gè)系統(tǒng)無法獲得一個(gè)統(tǒng)一的時(shí)鐘，而這又是直接影響分布式系統(tǒng)性能的關(guān)鍵因素，這就給分布式系統(tǒng)的容錯(cuò)問題帶來了巨大的挑戰(zhàn)。本文以2008年申請(qǐng)

2、的山東省自然科學(xué)基金項(xiàng)目為背景，以分布式系統(tǒng)容錯(cuò)檢查點(diǎn)算法作為出發(fā)點(diǎn)，針對(duì)豐富的檢查點(diǎn)設(shè)置策略和提高資源利用率和系統(tǒng)效率為目的，對(duì)分布式系統(tǒng)容錯(cuò)問題和檢查點(diǎn)算法進(jìn)行了深入的探索和研究。
　　 本文研究了分布式系統(tǒng)容錯(cuò)檢查點(diǎn)的設(shè)置和恢復(fù)算法，容錯(cuò)檢查點(diǎn)間隔設(shè)置的理論，方法和技術(shù)，探索將所研究的分布式容錯(cuò)檢查點(diǎn)算法與實(shí)際的分布式容錯(cuò)軟件相結(jié)合，提高分布式系統(tǒng)的可用性和算法的實(shí)用性，本文主要完成了如下工作：
　　 1.構(gòu)造分布

3、容錯(cuò)系統(tǒng)的層次結(jié)構(gòu)模型并列舉了該模型的主要特點(diǎn)，容錯(cuò)的概念和相關(guān)的定理,分析了分布式系統(tǒng)性能特性，并結(jié)合該性能提出分布式系統(tǒng)進(jìn)程模型。根據(jù)進(jìn)程通信模型進(jìn)一步指出，分布式容錯(cuò)系統(tǒng)由于時(shí)鐘自適應(yīng)特性而出現(xiàn)的檢查點(diǎn)通信問題，如孤兒報(bào)文、中途消息等。提出了如何消除這些非全局一致的檢查點(diǎn)狀態(tài)的條件和定理，給出了評(píng)價(jià)檢查點(diǎn)算法性能優(yōu)劣的指標(biāo)，即算法的時(shí)間開銷和空間開銷。
　　 2.根據(jù)分布式容錯(cuò)檢查點(diǎn)算法的原理，分析了同步檢查點(diǎn)算法的設(shè)置，

4、異步檢查點(diǎn)設(shè)置和消息日志檢查點(diǎn)算法的各自特點(diǎn)，深入理解了影響檢查點(diǎn)算法性能的瓶頸因素，即算法設(shè)計(jì)較復(fù)雜，實(shí)用性較差，時(shí)空開銷較大，對(duì)分布式系統(tǒng)性能的影響大。在此基礎(chǔ)上，參與研究了一種改進(jìn)的分布式容錯(cuò)檢查的算法，矩陣一致檢查點(diǎn)算法，該算法從容錯(cuò)的基本要素即進(jìn)程間通信出發(fā)，以進(jìn)程間通信的數(shù)目作為設(shè)計(jì)算法的核心思想，降低了算法的時(shí)空開銷，提高了系統(tǒng)的整體性能，經(jīng)演繹推理證明和實(shí)驗(yàn)驗(yàn)證，該檢查點(diǎn)算法簡(jiǎn)潔有效。
　　 3.通過研究檢查點(diǎn)算

5、法的性能瓶頸，我們發(fā)現(xiàn)檢查點(diǎn)間隔的設(shè)置和選取對(duì)于檢查點(diǎn)算法的性能同樣產(chǎn)生著重要的影響。在檢查點(diǎn)間隔的設(shè)置算法中，盡量減少檢查點(diǎn)機(jī)制所產(chǎn)生的時(shí)空開銷對(duì)提高計(jì)算效率具有重要意義。本文在已有的動(dòng)態(tài)檢查點(diǎn)間隔設(shè)置的基礎(chǔ)上，提出了一種新的動(dòng)態(tài)檢查點(diǎn)間隔的設(shè)置方法一隨機(jī)時(shí)間序列分析方法的Markov動(dòng)態(tài)檢查點(diǎn)間隔設(shè)置，該算法既可以減少回滾重復(fù)計(jì)算時(shí)間，又可以降低檢查點(diǎn)保存進(jìn)程狀態(tài)所需的存儲(chǔ)空間。經(jīng)Spin仿真實(shí)驗(yàn)結(jié)果表明，該動(dòng)態(tài)檢查點(diǎn)間隔算法與固定

6、檢查點(diǎn)算法和一般的動(dòng)態(tài)檢查點(diǎn)算法相比，平均檢查點(diǎn)間隔開銷率R(t)比傳統(tǒng)方法平均減少1.019％。
　　 4.分布式容錯(cuò)軟件平臺(tái)的設(shè)計(jì)技術(shù)。由于分布式系統(tǒng)的跨平臺(tái)特性，本文分別設(shè)計(jì)了Windows和Linux操作系統(tǒng)平臺(tái)下的容錯(cuò)軟件模塊的設(shè)計(jì)方式，前者主要采用了Detour Windows API技術(shù)，通過在系統(tǒng)的進(jìn)程中插入具有容錯(cuò)功能的線程來實(shí)現(xiàn)在Windows系統(tǒng)下的容錯(cuò)功能，并能根據(jù)保存的文件進(jìn)行容錯(cuò)的恢復(fù)。后者主要采用了