分布式任務管理系統中檢查點的設計

胡元元，袁順召

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

分布式任務管理系統中檢查點的設計

胡元元，袁順召

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

0　引言

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

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

1　檢查點

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

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

2　DMS系統構成環(huán)境

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

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

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

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

組成這個集群系統的每一個計算機稱為結點（Node）。為了保證可靠性，每個結點通過冗余的網絡路徑進行通信，每個結點都擁有一定的集群資源。集群中的結點能夠對這些資源進行控制，包括啟動、停止和資源轉移。

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

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

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

圖1　DMS系統構成環(huán)境

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

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

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

在DMS系統中，檢查點最主要的作用是進行容錯，任務搶占調度和任務遷移。

3　檢查點實現方法

同時使用共享磁盤和節(jié)點的本地磁盤存儲檢查點，可以降低網絡負載并減少檢查點操作的時間。基本思想是使用兩種檢查點間隔。每隔一段較短的期間在本地磁盤上創(chuàng)建檢查點，每隔一段較長的期間創(chuàng)建共享磁盤上的檢查點。

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

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

3.1容錯檢查點

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

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

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

圖2　容錯性檢查點極其恢復

3.2不進行任務遷移的搶占式調度

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

圖3　沒有遷移的任務搶占調度極其恢復

3.3任務遷移檢查點

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

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

圖4　任務遷移的檢查點極其恢復

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

4　檢查點放置算法

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

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

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

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

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

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

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

（2）如果t1點的狀態(tài)大小是s2，系統等待直到狀態(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)大小的檢查點放置算法。

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

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

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

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

4.3實現問題

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

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

5　結語

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

本文首先描述了網絡作業(yè)管理系統中進行檢查點操作會產生的兩個主要問題，即網絡負載和檢查點操作所造成的性能損失。然后，提出了避免這些問題的方法，就是使用節(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-），女，湖北當陽人，碩士，工程師，從事領域為軟件工程

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

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

分布式；任務；檢查點；集群

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.