用戶指導(dǎo)的多層混合檢查點(diǎn)技術(shù)及性能優(yōu)化

摘 要：檢查點(diǎn)機(jī)制是一種典型有效的軟件容錯(cuò)技術(shù)。在對現(xiàn)有檢查點(diǎn)實(shí)現(xiàn)技術(shù)綜合研究的基礎(chǔ)上，設(shè)計(jì)了一個(gè)用戶指導(dǎo)的多層混合檢查點(diǎn)模型uHybcr，并在IA64 Linux系統(tǒng)中予以實(shí)現(xiàn)。最后，通過對比測試對引入用戶指導(dǎo)機(jī)制所帶來的性能優(yōu)化進(jìn)行了驗(yàn)證。

關(guān)鍵詞：多層混合檢查點(diǎn)； IA64； 性能優(yōu)化； 最小可恢復(fù)狀態(tài)集

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：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 引言

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

本文通過對應(yīng)用級檢查點(diǎn)、用戶級檢查點(diǎn)和內(nèi)核級檢查點(diǎn)這三種不同層次檢查點(diǎn)實(shí)現(xiàn)技術(shù)的分析與研究，設(shè)計(jì)了一個(gè)用戶指導(dǎo)的多層檢查點(diǎn)模型，并在IA64平臺的Linux操作系統(tǒng)上予以實(shí)現(xiàn)。最后，通過對比實(shí)驗(yàn)對系統(tǒng)的性能進(jìn)行評測，驗(yàn)證了引入用戶指導(dǎo)機(jī)制所帶來的性能優(yōu)化。

1 相關(guān)工作

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

2 用戶指導(dǎo)的多層混合檢查點(diǎn)模型

檢查點(diǎn)技術(shù)的基本思想是保存應(yīng)用在某一時(shí)刻的運(yùn)行狀態(tài)，回滾時(shí)基于保存的執(zhí)行鏡像在該點(diǎn)恢復(fù)運(yùn)行。在檢查點(diǎn)時(shí)，一般只有部分狀態(tài)是程序后續(xù)執(zhí)行所必需的，而某些狀態(tài)與程序的后續(xù)執(zhí)行無關(guān)。為了確切描述應(yīng)用的狀態(tài)集合，本文作如下定義：

定義1 可運(yùn)行狀態(tài)集（rerunnable state set，RSS)。程序代碼可以繼續(xù)運(yùn)行的狀態(tài)集合，不包含用戶自定義的數(shù)據(jù)內(nèi)容。應(yīng)用程序代碼基于RSS可以繼續(xù)運(yùn)行，但用戶數(shù)據(jù)內(nèi)容不確定，計(jì)算結(jié)果可能不正確。

定義2 完整狀態(tài)集（complete state set，CSS）。進(jìn)程的所有狀態(tài)組成的集合，包括完整CPU狀態(tài)和所有用戶應(yīng)用數(shù)據(jù)，是應(yīng)用相關(guān)狀態(tài)的最大集合。

定義3 最小可恢復(fù)狀態(tài)集（min restartable state set，MRSS）。應(yīng)用回滾時(shí)可正確恢復(fù)執(zhí)行所必須的狀態(tài)最小集合。

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

檢查點(diǎn)作為容錯(cuò)手段不能影響應(yīng)用本身的正常運(yùn)行，因而檢查點(diǎn)系統(tǒng)的性能就顯得尤為重要。系統(tǒng)級檢查點(diǎn)與應(yīng)用級檢查點(diǎn)各有優(yōu)缺點(diǎn)，如果既能利用平臺體現(xiàn)結(jié)構(gòu)和操作系統(tǒng)實(shí)現(xiàn)特點(diǎn)進(jìn)行優(yōu)化，又不至于使系統(tǒng)內(nèi)核實(shí)現(xiàn)臃腫，且能只保存應(yīng)用程序的MRSS，將大大提高檢查點(diǎn)系統(tǒng)的性能。為此提出了一個(gè)由用戶在應(yīng)用級進(jìn)行應(yīng)用程序特征指導(dǎo)，由用戶庫實(shí)現(xiàn)檢查點(diǎn)協(xié)議，由內(nèi)核保存應(yīng)用程序執(zhí)行鏡像的多層檢查點(diǎn)系統(tǒng)uHybcr（user-defined hybrid checkpoint and restart）。它無法確定程序的應(yīng)用特征，只能保存應(yīng)用的CSS。

uHybcr在內(nèi)核中實(shí)現(xiàn)進(jìn)程狀態(tài)的保存和恢復(fù)，并以系統(tǒng)調(diào)用的方式為用戶庫提供服務(wù)。由于檢查點(diǎn)的核心工作在操作系統(tǒng)內(nèi)核完成，除了應(yīng)用對自身作檢查點(diǎn)外，作業(yè)管理系統(tǒng)也可以很自然地對系統(tǒng)中的任何應(yīng)用進(jìn)行檢查點(diǎn)操作。

用戶庫層以用戶庫的方式供用戶使用，負(fù)責(zé)定義檢查點(diǎn)系統(tǒng)的用戶使用接口，實(shí)現(xiàn)用戶對保存數(shù)據(jù)的定制、處理各種故障和異常，實(shí)現(xiàn)增量式數(shù)據(jù)保存以及其他各種檢查點(diǎn)策略。用戶庫最終調(diào)用內(nèi)核提供的系統(tǒng)服務(wù)完成檢查點(diǎn)任務(wù)。

用戶應(yīng)用在程序中加入相應(yīng)的定制檢查點(diǎn)代碼，指導(dǎo)檢查點(diǎn)系統(tǒng)的行為。對于系統(tǒng)中已有的不便修改的應(yīng)用，uHybcr也可以像標(biāo)準(zhǔn)內(nèi)核級檢查點(diǎn)系統(tǒng)一樣，對其進(jìn)行透明的檢查點(diǎn)操作。

為了支持用戶定制應(yīng)用最小可恢復(fù)狀態(tài)集合，用戶庫維護(hù)一個(gè)用于描述用戶定制數(shù)據(jù)的數(shù)組。數(shù)組(addr，size)一個(gè)二元組。其中，addr表示需要保存的數(shù)據(jù)區(qū)的起始地址；size表示該段數(shù)據(jù)的字節(jié)數(shù)。用戶庫根據(jù)用戶的定制對數(shù)組的內(nèi)容進(jìn)行增刪和綜合，并在用戶調(diào)用檢查點(diǎn)時(shí)將該描述數(shù)組傳遞給內(nèi)核。

3 IA64內(nèi)核檢查點(diǎn)

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

IA64大量新寄存器的引入對檢查點(diǎn)來說只是增加了CPU狀態(tài)的描述內(nèi)容，而其棧式寄存器技術(shù)則不僅是新的體系機(jī)構(gòu)描述，更重要的是改變了軟件的工作模式。棧式寄存器及其相關(guān)狀態(tài)的保存和恢復(fù)是IA64平臺內(nèi)核檢查點(diǎn)需要克服的技術(shù)關(guān)鍵。

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

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

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

4 用戶指導(dǎo)的性能優(yōu)化

系統(tǒng)級檢查對應(yīng)用透明，不了解進(jìn)程的應(yīng)用特性無法確定MRSS。為了確保正確性，只能保存應(yīng)用的CSS，檢查點(diǎn)信息存在冗余。要確定應(yīng)用的MRSS，必須有應(yīng)用自身的參與。為了支持應(yīng)用根據(jù)自身特點(diǎn)確定MRSS，實(shí)現(xiàn)檢查點(diǎn)內(nèi)容的最小化和性能的最優(yōu)化，uHybcr引入用戶指導(dǎo)機(jī)制。

uHybcr系統(tǒng)在用戶庫中提供檢查點(diǎn)內(nèi)容的用戶定制接口，分析用戶定制的合法性，綜合用戶多次定制，緩存用戶的定制信息。內(nèi)核檢查點(diǎn)模塊根據(jù)用戶庫傳遞的用戶指導(dǎo)信息，剔除不必要的進(jìn)程狀態(tài)，保存應(yīng)用的最小可恢復(fù)狀態(tài)集。

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

假設(shè)檢查點(diǎn)系統(tǒng)最后保存的狀態(tài)集合為C，include模式下用戶的定制為Ui，exclude模式下用戶的定制為Ue，則

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

uHybcr系統(tǒng)中用戶定制接口為用戶庫函數(shù)define_mode和define_data。

1)int define_mode(int mode)

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

參數(shù)說明：

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

返回值：原工作模式。

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

功能：定制數(shù)據(jù)內(nèi)容。

參數(shù)說明：

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

addr，數(shù)據(jù)區(qū)的起始地址。

size，數(shù)據(jù)區(qū)的字節(jié)數(shù)。

返回值：該操作的錯(cuò)誤碼。

本文以科學(xué)運(yùn)算中的基本測試用例矩陣乘法matmul來測試引入用戶指導(dǎo)機(jī)制對于檢查點(diǎn)系統(tǒng)的性能影響。下面為并行計(jì)算matmul中內(nèi)嵌檢查點(diǎn)的算法示例代碼。Matmul在循環(huán)iter每次迭代都重新計(jì)算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

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

5 結(jié)束語

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

參考文獻(xiàn)：

［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.

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