黨紅恩　趙爾平　雒偉群

摘要：檢查點算法作為一種有效的故障技術及容錯手段，已廣泛地運用在網(wǎng)格、分布式和云計算系統(tǒng)中。該文提出了一種非阻塞協(xié)調檢查點算法，該算法增加了系統(tǒng)的可靠性，并允許檢查點靈活設置，充分縮減了同步信息數(shù)量，加速了檢查點形成時間。和典型的相關算法比較，該文提出的算法使用更少的同步控制消息，具有更低的費用，引入同步控制消息的時間復雜度由一般的[O（n2）]降到[O（n）]，且同步消息數(shù)僅僅為[n-1]。

關鍵詞：檢查點；分布式系統(tǒng)；云計算系統(tǒng)；容錯

中圖分類號：TP302 文獻標識碼：A 文章編號：1009-3044（2014）10-2394-03

Abstract： The technology of checkpoint as an effective method of fault tolerance has been widely used in grid ，distributed and cloud systems. In this paper， a non-blocking cooperative checkpoint algorithm， which increases the reliability of the system and set up checkpoints flexible. At the same time， it fully reduces the synchronization information quantity， speeds up the formation checkpoint time， fully reduced the amount of information synchronized， the checkpoint accelerated development time. When compared to noted recent algorithms， the proposed algorithm uses less synchronous control messages with lower overhead. While the time complexity of control message during synchronous phase is reduced from O（n2） to O（n）， the algorithms controlling messages are reduced to n-1.

Key words： checkpoint； distributed system； cloud computing systems； fault-tolerant

眾所周知，檢查點和回卷恢復技術是實現(xiàn)容錯和處理故障的有效方式，已廣泛地運用在網(wǎng)格、分布式、普適計算和云計算系統(tǒng)中。K. MANI采用了一種新穎的可保障全局性能穩(wěn)定的算法[1]，但必須首先獲取全局狀態(tài)一致的點。文獻[2]提出一種低開銷的適用于錯誤恢復的協(xié)調檢查點算法，允許頻率檢查點僅由可靠性來確定。文獻[3，5]針對特殊應用提出了自己的算法，文獻[3]提出的檢查點算法，適用于共享內存式系統(tǒng)而并非分布式或者云計算系統(tǒng)。文獻[4，5]提出了一種能很好獲取全局狀態(tài)的檢查點算法，能有效驅趕孤兒消息和中途消息。而S.Monnet[6]提出一種混合式同異步檢查點算法，能夠實現(xiàn)獲取的并行性。G.CAO[7]采用經(jīng)典的兩階段提交算法，其總時間耗費有一定的降低。汪東升[8]采用輔助信息計數(shù)的同步運算，其同步信息數(shù)為[3n]。

1 系統(tǒng)模型

本文算法可應用于開放的網(wǎng)格、云計算、P2P等分布式系統(tǒng)，因此做文獻[9，10]的相同假設，對底層硬件和軟件不做特別要求。[Pn]為分布式系統(tǒng)中的進程，各進程有自己的運行速度，利用通信信道交換信息，它們之間的傳輸延遲是有限的、任意的。

另外一些術語定義： [Sflag=0 相應進程未發(fā)送應用消息 1 相應進程發(fā)送了應用消息 ；][CiN]、[SiN]代表進程[Pii=1，2，…，n]的序號。C（N）表示算法執(zhí)行，S（N）表示消息成功發(fā)送 。[Ci，x]表示進程Pi的第[x]個進程節(jié)點。[MAapplication message]：應用消息， 通過通信實現(xiàn)計算目標；[MCcontrol message]：控制信息， 負責[Pk] 行為的協(xié)調運行。[ORM] ：孤兒信息（orphan message）。[msg]：表示進程發(fā)送的[M（A）] ，[msgn]：表示[Pk] 發(fā)出的第[n] 個[M（A）] 。

2 協(xié)調檢查點算法

2.1 算法描述

本文的檢查點算法將進程分為啟動進程IPR（initiator process）和應用進程APR（application process）兩種。IPR用于算法的啟動，而APR用于應用程序中涉及的其它進程，二者通過[M（C）]相互作用。[Pk] 數(shù)目和[M（C）]在同一數(shù)量級，從而使得算法的復雜度有一定的降低，進而提升系統(tǒng)效率。

算法是一種特殊的高效能的單級非阻塞算法，能有效地保障并提高執(zhí)行效率。技術層面的表現(xiàn)就是可以直接訪問，不用經(jīng)過臨時檢查點階段，另外算法獲取永久檢查點的方式靈活多變，全局一致，可謂低耗費高效能。算法描述如下：

4 結論

本文根據(jù)分布式云計算系統(tǒng)中并行任務的特點，提出一種低費用、高效能的非阻塞協(xié)調檢查點算法。算法中，[ORM]的確定完全是由[M（C）]的進程來實現(xiàn)，這使得接收消息進程無任何后顧之憂。各[Pk] 在獲取檢查點的方式上具有獨立性、魯棒性和可擴展性，提高了效率并同時降低了算法負載。算法同時還具有較好的自律性，整個費用較小等優(yōu)點。后續(xù)研究可能會更多地關注檢查點算法設置優(yōu)化升級和優(yōu)化回卷恢復算法。

參考文獻：

[1] CHANDY K M，Leslie L.Distributed Snapshots： Determining Global States of Distributed Systems[J].ACM Transactions on Computer Systems， 1985，3（1）： 63-75.

[2] Lin Yi-Bing.Per-User Checkpointing for Mobility Database Failure Restoration[J].IEEE TRANSACTIONS ON MOBILE COMPUTING，2005，4（1）：1-6.

[3] Janakiraman G，Yuval Tamir.Coordinated Checkpointing-Rollback Error Recovery for Distributed Shared Memory Multicomputers[C].Proceedings of the13th Symposium on Reliable Distributed Systems Dana Point，1994： 42-51.

[4] Bidyut G，Shahram R，Ziping Liu.Design of High Performance Distributed Snapshot Recovery Algorithms for Ring Networks[J].Journal of Computing and Information Technology， 2008，16（1）：23-28.

[5] Mani C K，Leslie L.Distributed Snapshots： Determining Global States of Distributed Systems[J]. ACM Transactions on Computer Systems，1985，3（1）： 63-75.

[6] Monnet S，Morin C，Badrinath R.Hybrid checkpointing for parallel applications in cluster federations[C].CCGRID2004. Chicago：4th IEEE International Symposium on Cluster Computing and the Grid，2004： 773-782.

[7] G Cao，M Singhal.Mutable checkpoints： a new checkpointing approach for mobile computing systems [J].IEEE Transactions on Parallel and Distributed Systems，2001，12（2）：157–172.

[8] 汪東升，邵明瓏.具有 O（n）消息復雜度的協(xié)調檢查點設置算法[J].軟件學報，2003，14（1）：43-48.

[9] 劉國良，陳蜀宇，常光輝.基于動態(tài)分組的兩級檢查點算法[J].華南理工大學學報：自然科學版，2011，39（2）：141-147.

[10] 劉國良.分布式系統(tǒng)中回卷恢復技術研究[D].重慶：重慶大學，2012：10-21.