用戶指導的多層混合檢查點技術及性能優化

摘 要：檢查點機制是一種典型有效的軟件容錯技術。在對現有檢查點實現技術綜合研究的基礎上，設計了一個用戶指導的多層混合檢查點模型uHybcr，并在IA64 Linux系統中予以實現。最后，通過對比測試對引入用戶指導機制所帶來的性能優化進行了驗證。

關鍵詞：多層混合檢查點； IA64； 性能優化； 最小可恢復狀態集

中圖分類號：TP393 文獻標志碼：A

文章編號：1001-3695(2008)07-2097-03



User-defined hybrid checkpointing and optimization

LIU Yong-peng， WANG Xiao-ping， LI Gen

(School of Computer， National University of Defense Technology， Changsha 410073， China)



Abstract:Checkpoint is a typical and effective technique for fault tolerance. By analysis of current checkpointing technologies， this paper introduced a model of user-defined hybrid checkpoint and implemented it in the IA64 Linux. At last，it proved its optimization by the comparing test.

Key words：hybrid checkpoint; IA64; optimization; min restartable state set 

0 引言

檢查點（checkpoint）技術是一種典型有效的軟件容錯機制。當前主流的檢查點技術按其實現層次可分為應用級檢查點、用戶級檢查點和內核級檢查點三類。應用級檢查點是在應用中加入備份自身關鍵內容的檢查點代碼，可以根據應用具體特性進行優化，但無法在不同應用間通用。用戶級檢查點以系統用戶庫的形式向應用提供檢查點接口，無須改動操作系統，實現靈活、可移植性較高，但需修改應用程序以增加調用檢查點用戶庫的相關代碼，而且需要重新編譯。內核級檢查點對用戶應用透明，由操作系統內核實現，可充分利用平臺體系結構和操作內核特性進行優化，但修改內核實現復雜，移植性較差。用戶級檢查點和內核級檢查點可向系統中所有的應用提供檢查點服務，而非只針對某一特定應用，所以統稱為系統級檢查點。系統級檢查點保存應用的所有信息，無法根據應用特征來剔除進程冗余信息，影響檢查點的效率。三種檢查點技術各有優缺點。如何結合各種檢查點技術的優勢，既充分利用平臺體系結構和系統實現的特點，又能利用應用的自身特征，且實現靈活，使得檢查點系統簡潔高效，一直是檢查點技術領域的一個研究難點。

本文通過對應用級檢查點、用戶級檢查點和內核級檢查點這三種不同層次檢查點實現技術的分析與研究，設計了一個用戶指導的多層檢查點模型，并在IA64平臺的Linux操作系統上予以實現。最后，通過對比實驗對系統的性能進行評測，驗證了引入用戶指導機制所帶來的性能優化。

1 相關工作

系統級檢查點在目前已經有很多成功的實例。伯克利大學的BLCR^[1]是一個開源的內核級檢查點系統，基于Linux內核實現，支持i386、ppc64和x86_64平臺，并且計劃在未來開發內核級與用戶級混合的檢查點系統，但直到2007年3月發布的最新版本仍不支持IA64。TICK、CRAK、EPCKPT^[2~4]等具有代表性的檢查點系統也都在操作系統中實現。SGI于2004年底在其Altix 3300系統中實現了基于IA64 Linux的內核級檢查點，但其實現技術并未對外公開。Libckpt^[5]是一個開源的用戶級檢查點庫，支持檢查點的增量式保存，提出用戶定制檢查點的思想。Condor^[6]系統的檢查點機制也是一個典型的用戶庫級檢查點。應用級檢查點由應用程序員開發，一般集成在某一具體應用中，如各種數據庫系統中大都集成了檢查點功能。

2 用戶指導的多層混合檢查點模型

檢查點技術的基本思想是保存應用在某一時刻的運行狀態，回滾時基于保存的執行鏡像在該點恢復運行。在檢查點時，一般只有部分狀態是程序后續執行所必需的，而某些狀態與程序的后續執行無關。為了確切描述應用的狀態集合，本文作如下定義：

定義1 可運行狀態集（rerunnable state set，RSS)。程序代碼可以繼續運行的狀態集合，不包含用戶自定義的數據內容。應用程序代碼基于RSS可以繼續運行，但用戶數據內容不確定，計算結果可能不正確。

定義2 完整狀態集（complete state set，CSS）。進程的所有狀態組成的集合，包括完整CPU狀態和所有用戶應用數據，是應用相關狀態的最大集合。

定義3 最小可恢復狀態集（min restartable state set，MRSS）。應用回滾時可正確恢復執行所必須的狀態最小集合。

系統級檢查點由操作系統內核或系統用戶庫來保存應用程序的運行狀態，操作對象是用戶進程，無須任何應用程序的信息。但是，系統級檢查點和應用級檢查點則是應用程序本身包含保存和恢復自身關鍵內容的代碼。由于應用級檢查點是對應用本身的描述，程序員可以確定并只保存恢復自身所必需的MRSS，極大地降低了檢查點文件的大小。但是，應用級檢查點只能用于特定的應用，無法在不同的應用之間通用。

檢查點作為容錯手段不能影響應用本身的正常運行，因而檢查點系統的性能就顯得尤為重要。系統級檢查點與應用級檢查點各有優缺點，如果既能利用平臺體現結構和操作系統實現特點進行優化，又不至于使系統內核實現臃腫，且能只保存應用程序的MRSS，將大大提高檢查點系統的性能。為此提出了一個由用戶在應用級進行應用程序特征指導，由用戶庫實現檢查點協議，由內核保存應用程序執行鏡像的多層檢查點系統uHybcr（user-defined hybrid checkpoint and restart）。它無法確定程序的應用特征，只能保存應用的CSS。

uHybcr在內核中實現進程狀態的保存和恢復，并以系統調用的方式為用戶庫提供服務。由于檢查點的核心工作在操作系統內核完成，除了應用對自身作檢查點外，作業管理系統也可以很自然地對系統中的任何應用進行檢查點操作。

用戶庫層以用戶庫的方式供用戶使用，負責定義檢查點系統的用戶使用接口，實現用戶對保存數據的定制、處理各種故障和異常，實現增量式數據保存以及其他各種檢查點策略。用戶庫最終調用內核提供的系統服務完成檢查點任務。

用戶應用在程序中加入相應的定制檢查點代碼，指導檢查點系統的行為。對于系統中已有的不便修改的應用，uHybcr也可以像標準內核級檢查點系統一樣，對其進行透明的檢查點操作。

為了支持用戶定制應用最小可恢復狀態集合，用戶庫維護一個用于描述用戶定制數據的數組。數組(addr，size)一個二元組。其中，addr表示需要保存的數據區的起始地址；size表示該段數據的字節數。用戶庫根據用戶的定制對數組的內容進行增刪和綜合，并在用戶調用檢查點時將該描述數組傳遞給內核。

3 IA64內核檢查點

IA64是一個面向未來的64位CPU體系結構，遵循EPIC規范，提供了豐富的指令集和大量的寄存器資源，引入預測（prediction）、控制推斷（speculation）、數據推斷、棧式寄存器、旋轉寄存器等諸多先進的體系結構技術。特別是棧式寄存器技術的引入大大提高了軟件執行效率。但正是由于IA64嶄新的技術特點和復雜而龐大的體系結構，使得基于IA64平臺的內核級檢查點技術面臨許多新的挑戰，目前仍處于研究階段。為了充分體現內核實現檢查點模塊對檢查點系統性能的影響，選擇IA64作為uHybcr的實現平臺，操作系統則選擇業界流行的內核源碼公開的Linux。

IA64大量新寄存器的引入對檢查點來說只是增加了CPU狀態的描述內容，而其棧式寄存器技術則不僅是新的體系機構描述，更重要的是改變了軟件的工作模式。棧式寄存器及其相關狀態的保存和恢復是IA64平臺內核檢查點需要克服的技術關鍵。

棧式寄存器實質上是一個由硬件實現重命名的寄存器窗口，它利用內存（稱為寄存器棧）來備份上一個函數調用者的棧式寄存器內容。棧式寄存器和寄存器棧之間的內容交換由專用部件RSE（register stack engine）控制。RSE維護一個寄存器緩存池，并將該緩存池分為三個區域：無效區（invalid）、臟區（dirty）和干凈區(clean)。CPU指令可見的棧式寄存器集合稱為幀。當重新分配棧式寄存器時，RSE將前一幀的數據放入臟區。當臟區中的內容被RSE寫回寄存器棧之后，臟區變為干凈區。RSE自主負責該緩存池的維護，自動控制寄存器緩存池與寄存器棧之間的數據交換。這種數據交換與CPU指令的執行異步，不占用CPU指令執行時的訪存帶寬。IA64提供相應的CPU指令來設置RSE的工作模式，并可以通過CPU指令顯式地控制寄存器棧和緩存池之間的數據交換^[7]。

用戶進程的內存棧和寄存器棧是用戶內存空間的一部分，可以通過保存用戶內存空間的方式保存。但是，IA64的寄存器棧與棧式寄存器、寄存器緩存之間的數據交換由RSE控制，與CPU指令的執行異步，因此，在保存寄存器棧之前必須作相應的同步，將用戶進程的緩存池臟區和當前幀的內容寫回內存^[8，9]。

檢查點系統處理用戶寄存器棧的關鍵步驟如圖2所示。圖中，（a）檢查點系統調用進核之前，執行flushrs指令將RSE緩存池臟區寫回用戶寄存器棧；（b）設置RSE為lazy工作模式，執行cover指令將當前幀的大小置為0；（c）將BSPStore指向內核寄存器棧的棧底；（d）執行flushrs指令，將應用程序進核時的當前幀寫入內核寄存器棧。經過這四步處理之后，檢查點系統即可以保存用戶內存空間的方式保存用戶寄存器棧，對于用戶進程進核時的當前幀，則必須顯式地保存flush入內核寄存器棧的對應內容。進程恢復時，用戶棧寄存器棧的恢復過程是上述過程的逆過程。

4 用戶指導的性能優化

系統級檢查對應用透明，不了解進程的應用特性無法確定MRSS。為了確保正確性，只能保存應用的CSS，檢查點信息存在冗余。要確定應用的MRSS，必須有應用自身的參與。為了支持應用根據自身特點確定MRSS，實現檢查點內容的最小化和性能的最優化，uHybcr引入用戶指導機制。

uHybcr系統在用戶庫中提供檢查點內容的用戶定制接口，分析用戶定制的合法性，綜合用戶多次定制，緩存用戶的定制信息。內核檢查點模塊根據用戶庫傳遞的用戶指導信息，剔除不必要的進程狀態，保存應用的最小可恢復狀態集。

實際應用中，用戶有時無法確定后續程序必需的數據，卻可以確定后續程序不再需要的數據。為此，uHybcr提供兩種定制模式，即include和exclude。其中，include模式用戶定制必須保存的數據；exclude模式則定制不需要保存的數據。

假設檢查點系統最后保存的狀態集合為C，include模式下用戶的定制為Ui，exclude模式下用戶的定制為Ue，則

為了保證檢查點的正確性，必須滿足CMRSS。如果用戶沒有進行定制，C即為CSS。另外，用戶還可以對檢查點內容進行多次定制，uHybcr負責對用戶的多次定制進行沖突判定和綜合。

uHybcr系統中用戶定制接口為用戶庫函數define_mode和define_data。

1)int define_mode(int mode)

功能：查詢或設置uHybcr的工作模式。

參數說明：

mode，檢查點定制模式。其中：0表示查詢當前模式；1表示切換為include模式；2表示切換為exclude模式；其他值保留。

返回值：原工作模式。

2)long define_data(int op， void* addr， long size)

功能：定制數據內容。

參數說明：

op，用戶操作的類型。其中：0表示清空所有定制；1表示增加定制項；-1，刪除定制項；其他值保留。

addr，數據區的起始地址。

size，數據區的字節數。

返回值：該操作的錯誤碼。

本文以科學運算中的基本測試用例矩陣乘法matmul來測試引入用戶指導機制對于檢查點系統的性能影響。下面為并行計算matmul中內嵌檢查點的算法示例代碼。Matmul在循環iter每次迭代都重新計算c，因此c可以不用被保存。

double precision a(N，N)，b(N，N)，c(N，N)

do iter=1，num

call define_mode(2)

call define_data(1，c，N*N*sizeof(double))

parallel do

do 100 j=1，N

do 100 i=1，N

c(i，j)=0.0e+00

do 100 k=1，N

100c(i，j)=c(i，j)+a(i，k)*b(k，j)

……

end do

在本例中，就檢查點保存的數據量而言，三個二維共享數組是檢查點保存的主要數據。定制前，需要保存共享數組a、b和c。指定數組c不需要保存后，需要保存的數據量下降了1/3。圖3給出了定制前后上述程序checkpoint的空間開銷和時間開銷。實驗結果顯示，檢查點總文件大小從852 MB減少到了592 MB，空間節約了31%，而檢查點的執行時間也從0．72 s降低到0.62 s，降低了14%。

5 結束語

本文提出一種用戶指導的多層檢查點模型uHybcr，并在IA64平臺Linux系統上予以實現，最后還對系統的性能進行了評測。最小可恢復狀態集MRSS的確定是影響檢查點系統性能的一個重要因素，而在用戶指導下形成的檢查點數據集合與理想的MRSS之間必然存在一定的誤差。如何判定用戶指導的正確性、如何更智能地確定MRSS都是需要進一步深入研究的課題。

參考文獻：

［1］DUELL J， HARGROVE P， ROMAN E. The design and implementation of berkeley lab’s Linux checkpoint/restart， LBNL-54941[R].[S.l.]:Lawrence Berkeley National Laboratory，2003.

[2]ROMAN E.A survey of checkpoint/restart implementations， LBNL-54942 [R]. [S.l.]:Lawrence Berkeley National Laboratory，2002.

[3]ZHONG Hua，NIEN J.Crak:Linux checkpoint/restart as a kernel module， CUCS-014-01[R].New York:Columbia University，2001.

[4]PINHEIRO E.EPCKPT[EB/OL]. (2002-23-09)[2006].http://www.research.rutgers.edu/~edpin/epckpt.

[5]PLANK J，BECK M， KINGSLEY G， et al. Libckpt: transparent checkpointing under UNIX[C]//Proc of USENIX Technical Conference.Berkeley:USENIX Association， 1995:213-223.

[6]LITZKOW M，TANNENAUM T，BASNEY J，et al. Checkpoint and migration of UNIX Processes in the Condor distributed processing system， CS-TR-199701346[R].Madison:University of Wisconsin，1997.

[7]Intel Corporation.Intel Itanium architecture software developer’s ma-nual volume 2:system architecture revision 2.2，SKU 245318.005[R].[S.l.]:Intel Corporation，2006.

[8]MOSBERGER D，ERANIAN S.IA-64 Linux kernel design and implementation[M].New Jersey:Prentice Hall PTR， 2002: 93-116.

[9]LI Peng，WANG Dong-sheng. Process checkpointing and rollback recovery on the IA-64 architecture[R].Beijing:Tsinghua University，2002.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”