回卷恢復簡介20130925

1、回卷恢復容錯技術簡介湖南大學dx.yutian.cc3 4 /bjdxb 5 ? 39. 1內(nèi)容 回卷恢復技術介紹 回卷恢復中的基本概念 進程檢查點 通信模式 度量指標 研究方向及其代表性論文dxb.qnw.cc 3 /bjdxb 39. /2回卷恢復容錯技術介紹單進程應用的檢查點和事件日志系統(tǒng)內(nèi)部系統(tǒng)外部輸入事件1輸出事件1輸入事件2檢查點1檢查點2故障點時間回卷前滾3回卷恢復容錯技術介紹(cont.)分布式應用的檢查點和消息日志外部輸入事件輸出事件系統(tǒng)內(nèi)部系統(tǒng)外部進程1進程2進程3進程間消息全局檢查點全局檢查點4回卷恢復容錯技術回卷恢復技術是實現(xiàn)容錯計算，提高系統(tǒng)可靠性的一種常用方法。它的

2、應用范圍已越來越廣。除了容錯計算之外，在并行軟件和長時間運行軟件調(diào)試、負載平衡、移動計算、系統(tǒng)安全、云計算領域得到了廣泛應用。是這些領域的一項重要支撐技術?；鼐砘謴图夹g是一項實用性很強的技術。與其它容錯技術相比，它具有成本低，開銷小，簡單實用的特點。5并行計算編程接口MPI并行計算編程接口MPI，及支持庫：在Unix /Linux平臺上: MPICH2 library: 在Windows平臺上， MPICH1.2 library： MPICH: A Portable Implementation of MPI. 容錯的MPI：MPI_V: FT_MPI: Open MPI : 6MPI 消息傳

3、遞函數(shù) 同步消息傳遞函數(shù)：int MPI_Send( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm);int MPI_Recv(void *buf, int count, MPI_Datatype datatype，int source, int tag, MPI_Comm comm, MPI_Status *status) ;異步消息傳遞函數(shù)：MPI_Isend() and MPI_Irecv(). 多了一個變量mpi_Request *request 隨后可使用MPI_Test (

4、mpi_Request *request, int *flag, MPI_Status *status) 探詢操作是否完成；反應在status變量中； MPI_Wait (mpi_Request *request, int *flag, MPI_Status *status)；7非確定性例子 for (i = 0; i nb_recv; i+) MPI_Irecv (Ti, ., ANY_SOURCE, ANY_TAG,.);For (i=0; nb_recv; i+) MPI_Waitany(.)；這個代碼的好處是提高資源利用率，只要有請求到達，不管來自哪個進程，就處理，避免等待；可能導致問

5、題：同一個應用程序的多次執(zhí)行，每次消息到達的先后順序可能不相同，導致處理的先后順序不同，導致處理后的進程狀態(tài)不同；8回卷恢復實現(xiàn)技術檢查點系統(tǒng)：在Unix /Linux平臺上: libckpt, BLCR等.在Windows平臺上: Winckp ,NT-SwiFT，ChaRM-NT，Intel-NT, NT-MPCKPT等。分布式系統(tǒng)的回卷恢復系統(tǒng)：在Unix /Linux平臺上：FT-MPI, MPI-V, LAM-MPI, OPEN MPI等在Windows平臺上： NT-SwiFT ，ChaRM-NT, WINDAR等。 9回卷恢復容錯技術應用實例 Bell 實驗室的NT-SwiFT，

6、用于應用軟件運行監(jiān)控和故障恢復。 Intel公司使用檢查點系統(tǒng)用于電路設計仿真軟件的容錯和故障恢復。 Bell 實驗室的libft，用于電信應用系統(tǒng)的快速故障恢復。 清華大學的的ChaRM-NT，群機系統(tǒng)的可靠性和和故障恢復；分布式軟件的軟件調(diào)試。微軟公司的SPIDER, 用于Windows系統(tǒng)配置故障(注冊表)的定位和排除。Illonis大學的Chameleon，用于系統(tǒng)可靠性性能指標測量和系統(tǒng)可靠性性能評估；入侵后的系統(tǒng)恢復。10分布式回卷恢復中的基本概念基本概念：全局一致狀態(tài)；全局不一致狀態(tài)，中途消息Before happen relation: ei ej全局檢查點p1p2p3進程間消

7、息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m511分布式系統(tǒng)的回卷恢復孤兒消息全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m512分布式系統(tǒng)的回卷恢復丟失消息：不僅要有消息內(nèi)容，還要提交順序；全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m513分布式系統(tǒng)的回卷恢復重復消息：假定m10, m11的內(nèi)容和提交順序都保存了全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m

8、514分布式系統(tǒng)的回卷恢復檢查點全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m515分布式系統(tǒng)的回卷恢復協(xié)同檢查點: 同步/異步全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m516分布式系統(tǒng)的回卷恢復消息日志，基于發(fā)送者/接受者, 悲觀/樂觀，因果全局檢查點p1p2p3進程間消息m8m9m12m7m10m11GC1GC2GC3GC4m6m1m0m2m3m4m517進程檢查點時間t抽象簡單容易應用層支持庫層內(nèi)核層復雜細節(jié)文件數(shù)據(jù)表磁盤數(shù)據(jù)代碼數(shù)據(jù)存儲寄存器內(nèi)存外存A

9、PI層與層之間數(shù)據(jù)的相互關聯(lián)性代碼與數(shù)據(jù)分開嗎？代碼為只讀內(nèi)容，數(shù)據(jù)才是變化的18通信通道應用層MPI層TCP層應用層MPI層TCP層假定機器無故障有故障時，即使接收者已經(jīng)處理了該消息，但是后面故障時恢復時還需要該消息19進程狀態(tài)stackheapModuleImage棧幀對象全局變量代碼靜態(tài)變量寄存器:EAX, ECXESP, EBPEIP把支持庫和操作系統(tǒng)做無狀態(tài)化處理，簡化其檢查點/重啟如何識別應用層數(shù)據(jù)？20回卷恢復的開銷正常執(zhí)行時開銷（防備開銷）：檢查點開銷Tc： 協(xié)同（同步開銷），檢查點數(shù)據(jù)量；消息日志開銷Tm：協(xié)同（同步開銷），通信開銷，故障恢復開銷：回卷開銷Ts ；前滾至故障點

10、開銷Tr；防備開銷和恢復開銷彼此關聯(lián)，互為矛盾。21研究的方向 對應用的源程序進行分析，找出通信模式，分析不確定性，特點1）減少消息依賴跟蹤；減少消息日志；2）實現(xiàn)故障恢復時的快速前滾：并發(fā)前滾，跳越前滾減少檢查點數(shù)據(jù)量； 區(qū)分有狀態(tài)的功能模塊；和無狀態(tài)的功能模塊；區(qū)分對待；無檢查點技術與檢查點技術的結合：編碼技術；22研究方向的代表性論文 對MPI源程序的分析，找出通信模式，分析不確定性，特點On communication determinism in parallel HPC applications HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications減少檢查點數(shù)據(jù)量； The design and implementation of Berkeley Labs linux checkpoint/restartUser-level Checkpointing for LinuxThreads Programs.Libckpt: Transparent Checkpointing Under UNIX.無檢查點技術與檢查點技術的結合：編