胡元元，袁順召

（長江航運總醫(yī)院，武漢　430015）

分布式任務(wù)管理系統(tǒng)中檢查點的設(shè)計

胡元元，袁順召

（長江航運總醫(yī)院，武漢430015）

0　引言

檢查點是任務(wù)執(zhí)行狀態(tài)的一個瞬態(tài)圖，使任務(wù)在必要時可以在同一點上重新開始執(zhí)行。當集群環(huán)境的某一部分出現(xiàn)故障時，正在運行的程序可以從中間某點重新開始，而不需要從頭開始。

在DMS系統(tǒng)中，有時會發(fā)生硬件或軟件故障，這就需要在系統(tǒng)中具有處理故障恢復(fù)的有效機制。檢查點就是這樣一種機制，檢查點將正在運行的任務(wù)的當前狀態(tài)保存在一個文件中?？梢允褂眠@個文件在故障點重新運行任務(wù)。這些文件通常存儲在可靠并共享的文件系統(tǒng)中。如果某個節(jié)點發(fā)生故障，任務(wù)可以在另一個有效的節(jié)點上繼續(xù)運行。在需要進行任務(wù)遷移時，使用檢查點可以使正在運行的任務(wù)先暫停，當任務(wù)遷移到另一個節(jié)點時再繼續(xù)執(zhí)行。

1　檢查點

檢查點技術(shù)是將正在運行的任務(wù)的狀態(tài)保存在一個文件中。文件中包括從檢查點處開始運行任務(wù)所需要的所有信息。文件中存儲的基本信息包括和任務(wù)相關(guān)的寄存器、棧和堆中的信息。一般情況下，文件應(yīng)包含等候信號、文件描述符、sockets和所有線程等信息。

當前主流的檢查點技術(shù)按其實現(xiàn)層次可分為應(yīng)用級檢查點、用戶級檢查點和內(nèi)核級檢查點［1-2］三類。這三種檢查點機制的透明度，效率和初始化檢查點并恢復(fù)的機制各不相同。

2　DMS系統(tǒng)構(gòu)成環(huán)境

計算機集群的出現(xiàn)和使用己經(jīng)有十幾年的歷史。作為最早的集群技術(shù)設(shè)計師之一，G.Pfister對集群的定義是，“一種并行或分布式的系統(tǒng)，由全面互連的計算機集合組成，可作為一個統(tǒng)一的計算資源使用”［3］。

將數(shù)臺服務(wù)器計算機組合成一個統(tǒng)一的集群，多臺服務(wù)器將可以在用戶或管理員不必了解細節(jié)的情況下分擔計算負載。例如，如果服務(wù)器集群中的任何資源發(fā)生了故障，則不論發(fā)生故障的組件是硬件還是軟件資源，作為一個整體的集群都可以使用集群中其他服務(wù)器上的資源來繼續(xù)向用戶提供服務(wù)［4］。

換言之，當資源發(fā)生故障時，和服務(wù)器集群連接的用戶可能經(jīng)歷短暫的性能下降現(xiàn)象，但不會完全失去對服務(wù)的訪問能力。當需要更高的處理能力時，管理員可以通過滾動升級過程來添加新資源。該過程中，集群在整體上將保持聯(lián)機狀態(tài)，它不僅可供用戶使用，而且在升級后，其性能也將得到改善。

集群中的成員結(jié)點可以是同構(gòu)的，也可以是異構(gòu)的，或是兩者的混合。一個集群可以被看成一個并行機，在批處理系統(tǒng)的參與下，集群中的一個結(jié)點可以運行多個任務(wù)，也可以將一個任務(wù)分布在多個結(jié)點上運行［5］。

組成這個集群系統(tǒng)的每一個計算機稱為結(jié)點（Node）。為了保證可靠性，每個結(jié)點通過冗余的網(wǎng)絡(luò)路徑進行通信，每個結(jié)點都擁有一定的集群資源。集群中的結(jié)點能夠?qū)@些資源進行控制，包括啟動、停止和資源轉(zhuǎn)移。

一個集群系統(tǒng)映射自己獨特的描述，這些特有的描述是用于客戶端訪問應(yīng)用于每個結(jié)點的應(yīng)用程序和服務(wù)程序，同時也被管理者用于進行管理集群系統(tǒng)［6］。由于擁有這些獨特的描述，使得結(jié)點之間可以透明的進行應(yīng)用程序的資源轉(zhuǎn)移，也可以增加一個新的結(jié)點，但是網(wǎng)絡(luò)客戶把整個系統(tǒng)當作一個單獨的服務(wù)器系統(tǒng)。圖1是DMS系統(tǒng)的架構(gòu)圖。

客戶端用來供用戶訪問Cluster的節(jié)點［7］，當用戶提交任務(wù)的節(jié)點發(fā)生任何故障時，它提供節(jié)點通信連接方式的自動轉(zhuǎn)換，并繼續(xù)完成任務(wù)，但用戶并不會感覺到任務(wù)運行位置的變遷。

管理器提供對Cluster的動態(tài)管理，包括增加和刪除節(jié)點，以及對運行節(jié)點的動態(tài)監(jiān)控。

圖1　DMS系統(tǒng)構(gòu)成環(huán)境

Cluster接收來自集群管理器的控制命令和信息，并管理Cluster節(jié)點上的資源，監(jiān)控資源運行狀態(tài)，控制故障任務(wù)的運行、停止和任務(wù)遷移。

共享磁盤陣列供任務(wù)運行時特有資源和恢復(fù)日志文件的存儲，同時還提供Cluster上各節(jié)點的共享存儲空間。本地磁盤存儲任務(wù)的臨時文件。

通常在集群環(huán)境中，檢查點存儲在共享磁盤中。由于節(jié)點可能常常發(fā)生故障，檢查點可以用來恢復(fù)任務(wù)繼續(xù)運行。在共享磁盤中存儲檢查點有一些性能缺陷。首先，檢查點可能非常大，這樣很容易堵塞私有網(wǎng)絡(luò)。這對使用私有網(wǎng)絡(luò)進行通信的并行任務(wù)可能會造成性能損失。在進行檢查點操作的過程中，任務(wù)可能會被阻塞，因此長時間的檢查點操作可能會對任務(wù)本身造成性能損失。

在DMS系統(tǒng)中，檢查點最主要的作用是進行容錯，任務(wù)搶占調(diào)度和任務(wù)遷移。

3　檢查點實現(xiàn)方法

同時使用共享磁盤和節(jié)點的本地磁盤存儲檢查點，可以降低網(wǎng)絡(luò)負載并減少檢查點操作的時間?；舅枷胧鞘褂脙煞N檢查點間隔。每隔一段較短的期間在本地磁盤上創(chuàng)建檢查點，每隔一段較長的期間創(chuàng)建共享磁盤上的檢查點。

檢查點在工作節(jié)點上建立。建立檢查點時，將檢查點的版本號作為檢查點文件的文件名的一部分。使用版本號有兩個好處，首先可以節(jié)省存儲空間，因為只需要存儲版本號最近的檢查點。其次，當同一個任務(wù)的多個檢查點在網(wǎng)絡(luò)上傳輸時，由于只需要存儲版本號最近的檢查點，所以可以不用傳輸版本號較舊的檢查點，可以節(jié)省帶寬。創(chuàng)建檢查點的速度可能會快于在網(wǎng)絡(luò)上傳輸檢查點和在共享磁盤上存儲檢查點的速度。在這種情況下，工作節(jié)點上會產(chǎn)生一個等待發(fā)送的檢查點的隊列。這個隊列實際上是一個優(yōu)先級隊列，在隊列中新檢查點的優(yōu)先級高于舊檢查點。同一個任務(wù)的新檢查點會將舊檢查點從隊列中刪除。通常情況下，使用一個單獨的線程傳送檢查點，這樣，在傳送檢查點時，用戶任務(wù)可以繼續(xù)執(zhí)行。但是，有時在任務(wù)繼續(xù)執(zhí)行之前，可能需要確定某個特定的檢查點已經(jīng)到達共享磁盤，這時，可以將檢查點設(shè)置為阻塞模式。當檢查點是阻塞模式時，只有當前一個檢查點被傳輸?shù)焦蚕泶疟P上，下一個檢查點請求才會被響應(yīng)。在非阻塞檢查點情況下，檢查點等待被發(fā)送的同時任務(wù)繼續(xù)執(zhí)行，很有可能在該檢查點發(fā)送之前又創(chuàng)建了新的檢查點，這時，刪掉之前建立的檢查點，只傳送新的檢查點以節(jié)省帶寬。檢查點可能會非常大，所以需要對存儲的所有檢查點文件進行檢查，只有最近的檢查點被保留下來。

在本文的方法中，為DMS系統(tǒng)設(shè)計了三類檢查點：容錯檢查點，在任務(wù)搶占式調(diào)度后不進行進程遷移的檢查點和在任務(wù)搶占式調(diào)度后進行進程遷移的檢查點。下面各節(jié)具體描述每一種檢查點方法。在下面的各圖中，實線表示檢查點操作，虛線表示恢復(fù)任務(wù)繼續(xù)運行的操作。

3.1容錯檢查點

為了實現(xiàn)容錯功能，需要定期記錄任務(wù)的檢查點。記錄檢查點的時間段取決于任務(wù)本身。如果任務(wù)需要運行幾個月，合理的間隔期間應(yīng)該是幾個小時。相反地，較短的任務(wù)需要較短的期間。當任務(wù)的運行需要大量內(nèi)存時，期間的選擇必須非常謹慎，因為檢查點操作也需要花費一些時間。

圖2是這容錯檢查點的處理方法。檢查點操作分為兩個期間：TS和TL。期間TS一個較短的期間，它定義了兩次檢查點操作之間的時間間隔，TS存儲在本地磁盤中（圖2中的（1））。期間TL一段較長的期間，它定義了若干次檢查點操作的時間間隔，TL存儲在共享磁盤中（圖2中的（2））。期間TL也可以表示為若干段較短的期間。使用本地磁盤可以降低網(wǎng)絡(luò)負載，并且提高了檢查點處理的速度。

如果一個節(jié)點失敗了，查看檢查點是多久之前存儲的。如果是最近版本的檢查點，從這個檢查點開始在另外的可用的節(jié)點上恢復(fù)運行任務(wù)（圖2的（3））。否則，等待一段時間來確定失敗的節(jié)點是否會恢復(fù)。如果節(jié)點恢復(fù)了，任務(wù)在初始分配的節(jié)點上繼續(xù)執(zhí)行（圖2的（4））。如果節(jié)點沒有恢復(fù)，任務(wù)在另一個可用的節(jié)點上恢復(fù)運行，從在共享磁盤中存儲的最后一個檢查點處開始執(zhí)行（圖2的（3））。

圖2　容錯性檢查點極其恢復(fù)

3.2不進行任務(wù)遷移的搶占式調(diào)度

在沒有任務(wù)遷移的搶占式調(diào)度中，當要進行搶占調(diào)度時，首先記錄被搶占的任務(wù)的檢查點然后停止該任務(wù)。此后，一個新任務(wù)會在原來的節(jié)點上運行，當新任務(wù)完成后，原先的任務(wù)在該節(jié)點上恢復(fù)運行。被搶占的任務(wù)不能被遷移到其他節(jié)點上繼續(xù)運行。當用戶指定要使用某個節(jié)點而這個節(jié)點上正運行著其他的任務(wù)時會發(fā)生這種搶占調(diào)度。

圖3　沒有遷移的任務(wù)搶占調(diào)度極其恢復(fù)

3.3任務(wù)遷移檢查點

在任務(wù)遷移的情況下，對任務(wù)進行檢查點操作后，停止任務(wù)的運行并且在另一個節(jié)點上恢復(fù)運行任務(wù)（圖4）。如前所述，在任務(wù)搶占調(diào)度和負載平衡時會發(fā)生任務(wù)遷移。

在這種情況下，當遷移發(fā)生時，把檢查點存儲在共享磁盤中（圖4的（1））。由于任務(wù)被遷移到另一個節(jié)點上（圖4的（2）），所以只需要在共享磁盤中存儲檢查點。

圖4　任務(wù)遷移的檢查點極其恢復(fù)

在這種情況下，只在本地磁盤上存儲檢查點（圖 2的（1））。當新任務(wù)完成后，從本地磁盤系統(tǒng)中恢復(fù)先前的任務(wù)（圖 3的（2））。由于任務(wù)不能被遷移到其他的節(jié)點上，所以沒有必要將檢查點存儲在共享磁盤中。這種方法明顯的降低了網(wǎng)絡(luò)負載。另外，提高檢查點操作速度的同時也提高了搶占式任務(wù)調(diào)度的速度。

4　檢查點放置算法

4.1兩個狀態(tài)大小的檢查點放置算法

檢查點的開銷取決于放置檢查點的任務(wù)執(zhí)行點。更具體的，檢查點的開銷取決于任務(wù)在該點的狀態(tài)的大小。任務(wù)的狀態(tài)大小隨著內(nèi)存的分配和釋放而改變，檢查點的開銷也根據(jù)一些進程隨著時間而改變。因此，固定期間的放置策略并不是最優(yōu)的。

雖然不能預(yù)知任務(wù)的狀態(tài)大小，但是可以通過監(jiān)視內(nèi)存的分配和釋放來跟蹤任務(wù)的狀態(tài)大小。通過監(jiān)視內(nèi)存操作，可以知道任務(wù)當前的狀態(tài)大小。因此，可以估算在當前放置檢查點的開銷。

本文的算法的主要思想是在任務(wù)的執(zhí)行過程中尋找一點使得在這一點放置檢查點最有益。該算法找到任務(wù)的狀態(tài)大小較小的點，并使用這些點作為檢查點。如果找到了這樣的點，用較小的間隔在這些點上設(shè)置檢查點，這樣，故障后的再處理時間比較短。如果在一段時間內(nèi)沒有找到這樣的點，在較高代價的點上設(shè)置檢查點以避免需要較長的再處理時間。在這種情況下，檢查點之間的間隔應(yīng)該設(shè)置的比較長，以減少檢查點開銷。

下面的例子說明了對于檢查點代價的了解可以改善檢查點性能。設(shè)任務(wù)有兩個可能的狀態(tài)大小，S1和S2，令S1＜S2。設(shè)任務(wù)的狀態(tài)大小為Si時，檢查點的代價為Ci（C1＜C2）。任務(wù)的狀態(tài)大小根據(jù)一個兩狀態(tài)的Markov鏈改變。

該算法的工作方式如下：定義兩個時間點，t1和t2，令t1＜=t2。該算法根據(jù)下面的規(guī)則決定是否要在t點放置檢查點，t是從上次檢查點到當前時刻的時間：

（1）如果t1點的狀態(tài)大小是s1，那么在t1點放置一個檢查點。該檢查點的代價是C1。

（2）如果t1點的狀態(tài)大小是s2，系統(tǒng)等待直到狀態(tài)大小變?yōu)閟1，并在這一點放置檢查點。該檢查點的代價是C1。

（3）如果t1點的狀態(tài)大小是S2，并且直到t2點，狀態(tài)大小始終沒有改變，那么在t2點放置一個檢查點。這種情況下的檢查點開銷是C2。

為了避免檢查點開銷過高，檢查點不能在t1點之前放置。同樣，為了避免從檢查點再處理時間過長，不能在t2點之后放置檢查點。t1和t2的值會影響算法的性能。通過分析算法的開銷比，可以找到使得開銷比最小的t1和t2的值。

4.2多個狀態(tài)大小的檢查點放置算法

兩狀態(tài)大小的檢查點放置算法可以被擴展為多狀態(tài)大小的檢查點放置算法。

假定任務(wù)可能的狀態(tài)大小是S1，S2，…，Sn，并且狀態(tài)大小為si時，檢查點開銷是Ci，這里C1＜=C2＜=…＜= Cn。每個狀態(tài)大小si有一個與之相關(guān)的時間期間ti。該算法根據(jù)下面的規(guī)則決定是否在時間t放置一個檢查點，t是從上一個檢查點到當前時刻的時間。

（1）不在區(qū)間［0，ti）放置檢查點。

（2）如果在某一點時區(qū)間［ti，ti+1）的狀態(tài)大小為S1，S2，…，Si，在該點放置檢查點。

（3）在tn時刻放置檢查點，不考慮該點的狀態(tài)大小。

4.3實現(xiàn)問題

在系統(tǒng)中實現(xiàn)時，使用計時器來決定放置下一個檢查點的時間，每次狀態(tài)大小改變時更新計時器。放置了一個檢查點后，計時器被初始化為ti，si是放置檢查點時的狀態(tài)大小，計時器開始減數(shù)計時。當每次內(nèi)存分配或釋放操作使得任務(wù)的狀態(tài)大小從si變?yōu)閟j時，計時器的值增加一個tj-ti。當計時器的值小于或等于0時放置檢查點。

本文的算法假設(shè)任務(wù)的狀態(tài)大小處于一個有限的離散的集合中。事實上，任務(wù)的狀態(tài)大小是連續(xù)變化的。這一問題可以通過量化來解決［8］，可以將狀態(tài)大小量化為最接近的大小。如果量化誤差不大，量化對于算法性能的影響可以達到最小。

5　結(jié)語

檢查點對于支持容錯功能的系統(tǒng)是十分重要的功能。在網(wǎng)絡(luò)作業(yè)管理系統(tǒng)環(huán)境中，為了實現(xiàn)作業(yè)搶占調(diào)度和作業(yè)遷移，必須進行檢查點操作。

本文首先描述了網(wǎng)絡(luò)作業(yè)管理系統(tǒng)中進行檢查點操作會產(chǎn)生的兩個主要問題，即網(wǎng)絡(luò)負載和檢查點操作所造成的性能損失。然后，提出了避免這些問題的方法，就是使用節(jié)點的本地磁盤存儲檢查點。

［1］Neil Cafferkey，Philip D.Healy，David A.Power and John P.Morrison.Job Management in WebCom.Sixth International Symposium on Parallel and Distributed Computing（ISPDC'07）.

［2］Adam Jamison Oliner.Cooperative Checkpointing for Supercomputing Systems.Submitted to the Department of Electrical Engineering and Computer Science，on May 19，2005，in Partial Fulfillment of the Requirements for the Degree of Master of Engineering in Computer Science and Engineering.

［3］Norihiro Fujii，Nobuhiko Koike.Multi-user/Multi-Test-Bed Remote Hardware Laboratory with Job Management System.2007 IEEE International Conference on Microelectronic Systems Education（MSE'07）.

［4］LUAN Cui-ju，SONG Guang-hua，ZHENG Yao.A Flexible Architecture for Job Management in a Grid Environment，Luan et al.Zhejiang Univ Sci A 2007 8（1）：95-105，Sept.28，2006.J.

［5］Antonio Cunei Jan Vitek.A New Approach To Real-Time Checkpointing，VEE'06 June 14-16，2006，Ottawa，Ontario，Canada.

［6］Bidyut Gupta，Shahram Rahimi.A Novel Roll-Back Mechanism for Performance Enhancement of Asynchronous Checkpointing and Recovery，Informatica 31，2007，1-13.

［7］Greg Bronevetsky，Daniel Marques，Keshav Pingali，Application-level Checkpointing for Shared Memory Programs，ASPLOS'04，October 9-13，2004，Boston，Massachusetts，USA.

［8］Jonathan M.Smith，A Survey of Process Migration Mechanisms，Computer Science Department，Columbia University，22 May 2001.

Distributed；Business；Checkpoint；Cluster

The Checkpoint Design of Distributed Business Management System

HU Yuan-yuan，YUAN Shun-zhao
（General Hospital of Yangtze River shipping，Wuhan 430015）

1007-1423（2015）31-0003-05

10.3969/j.issn.1007-1423.2015.31.001

胡元元（1983-），女，湖北當陽人，碩士，工程師，從事領(lǐng)域為軟件工程

袁順召（1986-），男，湖北利川人，碩士，從事領(lǐng)域為行政管理

通過對檢查點的設(shè)計，提高分布式任務(wù)管理系統(tǒng)的性能。介紹檢查點及DMS系統(tǒng)構(gòu)成環(huán)境，然后提出檢查點實現(xiàn)的三種方法，即容錯檢查點，不進行任務(wù)遷移的搶占式調(diào)度，及任務(wù)遷移檢查點。設(shè)計兩個狀態(tài)大小的檢查點放置算法和多個狀態(tài)大小的檢查點放置算法，降低網(wǎng)絡(luò)負載和檢查點操作所造成的性能損失。

分布式；任務(wù)；檢查點；集群

Performance of Business Management System Distributed（DMS）is improved by the design of Checkpoint.Introduces the Checkpoints and the DMS system，and then proposes three methods，namely，fault tolerance Checkpoint，preemptive scheduling of tasks，and task migration Checkpoint.Designs two state size checking points placement algorithm and multiple state size，reduces the performance loss caused by network load and checkpoint operation.