唐金輝， 鐘 誠， 吳惜華， 莫英紅， 李效魯， 林 瑞

(廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西南寧 530004)

0 引 言

在諸如Web服務(wù)這種分布式計算環(huán)境中，許多系統(tǒng)采用對象復(fù)制技術(shù)來提高可用性。基于對象復(fù)制的容錯算法主要分為active復(fù)制和p rimary-backup復(fù)制2類[1]。在active算法中，所有的副本同時響應(yīng)客戶的請求，當(dāng)有副本失效時，其余副本在失效副本缺席的情況下繼續(xù)正常工作;它處理請求的速度快、失效恢復(fù)時間短，但是耗費系統(tǒng)較多資源。在primary-backup算法中，副本分為主副本和備份副本2種，只有主副本接受和處理客戶的請求，當(dāng)主副本失效時，從備份副本中選一個升級為主副本，繼續(xù)向客戶提供服務(wù)，因此，其請求處理時間和失效恢復(fù)時間長，系統(tǒng)負(fù)載不平衡，但是節(jié)約了系統(tǒng)資源。

已有的Web服務(wù)容錯算法大多只是對 active和prim ary-backup算法進(jìn)行某方面的改進(jìn)，很少致力于研究提高算法的性能[2]。文獻(xiàn)[3]提出了用Sem i Active方法來解決active算法中服務(wù)狀態(tài)的確定性問題。文獻(xiàn)[4]通過改變p rimary發(fā)送更新信息的時間和頻率來對 primarybackup算法進(jìn)行改進(jìn)。文獻(xiàn)[2]提出的RRR算法雖然使請求處理速度變快，但它是在犧牲可用性的基礎(chǔ)上獲得的。文獻(xiàn)[5]則探討了基于主動復(fù)制容錯技術(shù)的負(fù)載平衡層次模型。文獻(xiàn)[6]將組合Web服務(wù)選取問題轉(zhuǎn)化為最長路徑選取問題，給出了一種雙向動態(tài)規(guī)劃的求解策略。

本文給出一種基于對象復(fù)制機(jī)制的Web服務(wù)動態(tài)容錯算法(dynam ic object replication，簡稱DOR)，它的主要思想和貢獻(xiàn)是:①通過動態(tài)改變執(zhí)行請求的副本成員數(shù)，來縮短請求的響應(yīng)時間，但又不過多地占用系統(tǒng)資源;②算法根據(jù)副本的系統(tǒng)負(fù)載和網(wǎng)絡(luò)延時情況，動態(tài)選擇副本來執(zhí)行請求，既提高請求的處理速度又實現(xiàn)負(fù)載平衡;③在不改變算法可用性的前提下，加快請求處理速度。

1 系統(tǒng)模型

本文給出的算法是基于分布式面向?qū)ο笙到y(tǒng)設(shè)計的，系統(tǒng)中有多個相互連接的主機(jī)，主機(jī)之間通過廣域網(wǎng)進(jìn)行通信。服務(wù)有2種失效類型[7]: fail-stop類型和拜占庭類型。系統(tǒng)向客戶提供的每一個服務(wù)對象均由分布在不同主機(jī)上的副本來實現(xiàn)，而這些實現(xiàn)同一個服務(wù)對象的各個主機(jī)上不同的副本構(gòu)成一個相應(yīng)副本組，組中的每個副本稱為組的一個成員。

本文在文獻(xiàn)[8]中的系統(tǒng)框架基礎(chǔ)上，給出一個改進(jìn)的DOR復(fù)制算法框架，它主要由Administrator、Object Manager(OM)、Rep lica Manager (RM)和Result Agent(RA)4個模塊組成，如圖1所示。

圖1 DOR復(fù)制算法框架

圖1中OM模塊的主要工作是管理服務(wù)副本組、分發(fā)和管理客戶請求。客戶申請某個服務(wù)時向相應(yīng)的OM發(fā)送服務(wù)請求，由它將請求轉(zhuǎn)發(fā)給副本組中所有的成員。因此，對于客戶而言，整個服務(wù)的過程是透明的。為了實現(xiàn)相應(yīng)的管理功能，OM擁有2個列表:客戶請求列表(request_ list)和副本組列表(rep lica_list)，其中客戶請求列表存儲了客戶發(fā)送過來的請求編號、客戶名、方法名、參數(shù)和請求類型等請求信息，副本組列表存儲的是其管理成員的主機(jī)地址和狀態(tài)信息。

RM模塊的主要工作是負(fù)責(zé)接受OM發(fā)送過來的請求并根據(jù)一定的機(jī)制決定是否執(zhí)行客戶的請求，以及把返回的結(jié)果發(fā)送給OM。RM駐留在每一個副本組成員所在的主機(jī)上，并且含有主機(jī)當(dāng)前的負(fù)載情況(current_load)、負(fù)載閾值(max_load)、網(wǎng)絡(luò)延時情況(current_delay)和延時閾值(max_delay)以及等待執(zhí)行的請求隊列(instance_queue)、等待隊列(w aiting_queue)和結(jié)束列表(executed_list)。當(dāng)RM接受到某個請求后，根據(jù)當(dāng)前主機(jī)的負(fù)載情況和網(wǎng)絡(luò)延時情況，來決定是否馬上執(zhí)行此請求，并把暫時不能執(zhí)行的請求放入等待隊列。

Administrator模塊通過不斷地向 OM 和RM發(fā)送檢測請求來監(jiān)控整個系統(tǒng)以及其中各個副本和主機(jī)的情況，并對失效的OM和RM進(jìn)行恢復(fù)。RA模塊負(fù)責(zé)接受從OM傳送過來的請求的結(jié)果，將處理的最終結(jié)果發(fā)送給客戶，并把更新信息返回給OM。針對服務(wù)的拜占庭失效，RA會根據(jù)客戶自定義的測試機(jī)制對結(jié)果進(jìn)行處理。

2 Web服務(wù)動態(tài)容錯算法

算法的核心思想是，副本組中每個成員都接受OM模塊發(fā)送過來的請求，但并不是所有的副本都立即執(zhí)行請求，而是根據(jù)成員的系統(tǒng)負(fù)載情況和網(wǎng)絡(luò)延時情況來決定是否執(zhí)行。因此，隨著系統(tǒng)負(fù)載和網(wǎng)絡(luò)延時的變化，副本中處理請求的成員也會動態(tài)變化。OM模塊在接收到客戶發(fā)送來的請求后，把請求放入客戶請求列表中，并向副本組中的每個成員發(fā)送這個請求。每個成員的RM收到請求后，就根據(jù)主機(jī)的系統(tǒng)負(fù)載和網(wǎng)絡(luò)延時情況決定是否執(zhí)行請求，如果系統(tǒng)負(fù)載比較輕而且網(wǎng)絡(luò)延時比較低，那么立即創(chuàng)建一個新線程來處理請求，否則就按照FIFO的順序?qū)⒄埱蠓湃氲却龍?zhí)行請求隊列中。當(dāng)副本處理完請求后，將結(jié)果發(fā)送給OM，OM再把結(jié)果發(fā)送給RA統(tǒng)一處理，RA將處理過的最終結(jié)果發(fā)送給客戶。有些客戶的請求是寫請求，會改變副本的狀態(tài)，因此RA會返回一個更新信息來維護(hù)各個副本的狀態(tài)一致性。

系統(tǒng)中共有5種信息類型:

(1)request_message(RequestId，M ethod-Name，parmeters，Reqest_Type)，表示客戶發(fā)送給OM和OM發(fā)送給RM的請求信息。

(2)reponse_message(RequestId，Result，Reqest_Type，update)，這是副本組成員發(fā)送給OM和OM發(fā)送給RA的信息。

(3)receipt_message(RequestId，Reqest_ Type，update)，這是將處理結(jié)果發(fā)送給客戶后，RA發(fā)送給OM的確認(rèn)信息。

(4)executed_message((RequestId)，表示OM發(fā)送給RM的請求執(zhí)行結(jié)束的信息。

(5)update_message(RequestId，update)，表示OM發(fā)送給RM的狀態(tài)更新信息。

2.1 OM模塊算法

OM模塊的主要工作是管理服務(wù)副本組、分發(fā)和管理客戶請求:

(1)當(dāng)接收到客戶發(fā)送過來的請求信息后，先在request_list中添加一個記錄，然后把請求廣播給所有的副本組成員。

(2)當(dāng)接收到某個副本發(fā)送過來的應(yīng)答信息，直接發(fā)送給RA處理。

(3)當(dāng)接收到RA發(fā)送過來的確認(rèn)信息后，如果請求類型是寫操作，那么生成一個更新信息并發(fā)送給所有的副本組成員;否則，生成一個結(jié)束信息發(fā)送給所有的成員。

OM模塊算法如下:

2.2 RM模塊算法

RM模塊在接受到信息后，根據(jù)不同的信息做出相應(yīng)的處理:

(1)當(dāng)接收到OM發(fā)送過來的請求信息后，根據(jù)主機(jī)的系統(tǒng)負(fù)載和網(wǎng)絡(luò)延時情況，決定把請求信息放入等待隊列還是執(zhí)行等待隊列。也就是說，如果主機(jī)系統(tǒng)負(fù)載值小于負(fù)載閾值，并且網(wǎng)絡(luò)延時值也小于延時閾值，那么將請求放入執(zhí)行等待隊列;否則，將請求放入等待隊列。

(2)當(dāng)接收到副本發(fā)送過來的請求處理結(jié)果后，搜索結(jié)束列表是否有與其相同ID的結(jié)束信息。如果有，那么丟棄這個結(jié)果;否則，在列表中添加一個新的結(jié)束信息并將結(jié)果發(fā)送回OM。

(3)當(dāng)接收到OM發(fā)送過來的結(jié)束信息后，搜索等待隊列是否有與其相同ID的結(jié)束信息。如果有，那么刪除此請求信息并添加新的結(jié)束信息到結(jié)束隊列;否則，搜索結(jié)束列表是否有與其相同ID的結(jié)束信息，如果有則丟棄該結(jié)束信息，若沒有則將該結(jié)束信息添加進(jìn)結(jié)束隊列。

(4)當(dāng)接收到OM發(fā)送過來的更新信息后，搜索等待隊列是否有與其相同ID的結(jié)束信息。若有則將更新信息替換此請求信息;否則搜索結(jié)束列表是否有與其相同ID的結(jié)束信息，如果有則丟棄該更新信息，沒有則將新的結(jié)束信息添進(jìn)結(jié)束隊列。

RM模塊算法如下:

2.3 組成員失效的處理

因為DOR復(fù)制算法中每一個副本都可以參與客戶請求的處理，所以個別或部分副本組成員的失效并不會影響整個算法的執(zhí)行，只有當(dāng)所有的成員同時都失效時，才會對算法的進(jìn)程有影響，但是并不影響算法的正確性。當(dāng)檢測到某個副本失效時，Administrator將根據(jù)其它副本的狀態(tài)和請求列表對失效副本進(jìn)行恢復(fù)。

2.4 算法分析

2.4.1 一致性分析

副本組中成員的狀態(tài)都由它處理過的請求來決定，在算法中每個成員都按照相同的順序接收OM發(fā)送過來的請求，并按照相同的順序處理請求。RA在選舉出最終結(jié)果后，會返回一個確認(rèn)信息receip t_message給OM。本算法對寫操作和讀操作分別進(jìn)行處理，當(dāng)請求是讀操作時，OM在接收到確認(rèn)信息后只返回一個結(jié)束信息executed_message給每個成員;而如果是寫操作時，OM返回一個更新信息update_message給每個成員。因為讀操作并不會改變成員的狀態(tài)，所以只對處理寫操作的部分進(jìn)行分析。在成員接收到更新信息時，它可能處于正在、已經(jīng)或者尚未處理該請求3種情況。當(dāng)成員正在處理該請求時收到更新信息，添加一個結(jié)束信息到結(jié)束隊列。請求處理完畢后，若發(fā)現(xiàn)結(jié)束隊列中存在該請求的結(jié)束信息，則丟棄該處理結(jié)果，此時該成員與其它成員狀態(tài)一致。對于已經(jīng)處理完請求的情況，算法直接丟棄該更新信息，此時該成員與其它成員狀態(tài)一致。當(dāng)成員尚未處理該請求時，算法將更新替換請求信息，成員執(zhí)行完更新信息后，也與其它成員狀態(tài)一致。綜上所述，本文的算法能夠保證副本組中的每個成員狀態(tài)保持一致。

2.4.2 性能分析

主要對DOR復(fù)制算法與active復(fù)制算法、primary-backup復(fù)制算法的平均響應(yīng)時間進(jìn)行分析比較。

假設(shè)系統(tǒng)中副本組有n個成員，成員失效的概率為f，檢測失效的時間為t t，恢復(fù)失效副本的時間為t r，正常成員執(zhí)行一個請求的平均時間為t e。這樣，Web服務(wù)容錯復(fù)制算法的平均響應(yīng)時間為:

其中，f n為系統(tǒng)正常工作的概率;t為請求的平均執(zhí)行時間;ff為系統(tǒng)出現(xiàn)故障的概率。

在active復(fù)制算法中，每個副本都響應(yīng)客戶的請求，系統(tǒng)中只要有一個正常成員，客戶請求就可以得到響應(yīng)，因此，系統(tǒng)正常工作的概率為1-f n;t a為active算法中正常執(zhí)行請求的平均響應(yīng)時間，因此，active復(fù)制算法中請求的平均響應(yīng)時間為:

在p rim ary-backup復(fù)制算法中，所有請求都由主副本串行執(zhí)行，系統(tǒng)正常工作的概率為1-f，t p為primary-backup算法中正常執(zhí)行請求的平均響應(yīng)時間，因此primary-backup復(fù)制算法中請求的平均響應(yīng)時間為:

在DOR復(fù)制算法中，系統(tǒng)正常工作的概率與active復(fù)制算法一樣，t d為DOR復(fù)制算法中正常執(zhí)行請求的平均響應(yīng)時間，因此DOR復(fù)制算法請求的平均響應(yīng)時間為:

通過以上的分析比較可知，ˉt p≥ˉt a和ˉt p≥ˉt d;而ˉt a和ˉt d之間的關(guān)系可以通過比較 t a和t d得出。對于active復(fù)制算法，t a是由所有成員處理請求所需時間的最大值決定，因為結(jié)果的協(xié)調(diào)需要等待所有的成員都處理完請求之后才能進(jìn)行。DOR復(fù)制算法根據(jù)系統(tǒng)的負(fù)載和網(wǎng)絡(luò)延時的情況選擇輕載的成員處理請求，并把處理結(jié)果返回給客戶，而不必等待所有成員都處理完請求，因此t d是由這些被選擇的成員的處理時間最大值決定的。這些表明，t a≥t d，即ˉt a≥ˉt d。因此，DOR復(fù)制算法的請求平均響應(yīng)時間是以上3種復(fù)制算法中最短的。

3 實 驗

實驗平臺為Pentium IV CPU 3.0 GH z、512M B RAM的HP個人計算機(jī)，運(yùn)行的操作系統(tǒng)是Red Hat Linux 9.0，使用NS2對DOR復(fù)制算法進(jìn)行仿真實驗。在實驗中，利用NS2的網(wǎng)絡(luò)組件進(jìn)行廣域網(wǎng)的仿真，并直接從TclOb ject類繼承類ObjectRep lication來表示對象復(fù)制算法的組件，通過繼承App lication類來生成客戶端與服務(wù)器端程序的仿真程序。在此基礎(chǔ)上，分別對DOR復(fù)制算法、active復(fù)制算法和primary-backup復(fù)制算法進(jìn)行仿真實驗性能對比。

在副本冗余為3且無失效的情況下，DOR復(fù)制算法、active復(fù)制算法和primary-backup復(fù)制算法的平均響應(yīng)時間隨請求頻率變化的結(jié)果，如圖2所示。

從圖2可以看出，隨著請求頻率的增加，請求的響應(yīng)時間也逐漸加大，與active復(fù)制算法、pri-mary-backup復(fù)制算法相比，DOR復(fù)制算法無論在輕載還是重載的情況下，其響應(yīng)速度最快、所需的響應(yīng)時間最短，這與性能分析的結(jié)果一致。

圖2 3種算法響應(yīng)時間隨請求頻率的變化

當(dāng)請求頻率為20/s且副本冗余為5時，DOR復(fù)制算法、active復(fù)制算法和primary-backup復(fù)制算法的平均響應(yīng)時間隨副本失效率變化的情況，如圖3所示。

圖3 3種算法響應(yīng)時間隨副本失效率的變化

從圖3可以看出，隨著副本失效率的增長，3種算法的請求響應(yīng)時間也逐漸加大，其中本文的DOR復(fù)制算法的響應(yīng)時間最低，p rimary-backup復(fù)制算法受失效率的影響最大，這與性能分析中各算法平均響應(yīng)時間的結(jié)果是一致的。

當(dāng)請求頻率為20/s且副本冗余為5時，DOR復(fù)制算法、active復(fù)制算法和primary-backup復(fù)制算法的平均響應(yīng)時間隨失效副本數(shù)量變化的情況，如圖4所示。

圖4的結(jié)果表明，隨著失效副本數(shù)量的增加，p rim ary-backup復(fù)制算法響應(yīng)時間增幅最大。這是因為primary-backup復(fù)制算法需恢復(fù)失效副本進(jìn)行才能正常工作，而其它2個算法不需要對失效副本進(jìn)行恢復(fù)也能正常工作，因此，副本的失效對DOR復(fù)制算法和active復(fù)制算法響應(yīng)時間的影響較小。

圖4 3種算法響應(yīng)時間隨失效副本數(shù)量的變化

4 結(jié)束語

本文提出的基于對象復(fù)制機(jī)制的Web服務(wù)動態(tài)容錯算法，能根據(jù)副本的系統(tǒng)負(fù)載和網(wǎng)絡(luò)延時情況，動態(tài)改變執(zhí)行請求的副本成員數(shù)，在不浪費系統(tǒng)資源和不改變算法的可用性的前提下，縮短了請求的響應(yīng)時間。下一步的工作是研究拓展本文提出的算法，使其適用于Web服務(wù)組合。

本文初稿首次刊登于《計算機(jī)技術(shù)與應(yīng)用進(jìn)展?2010》。

[1] Rachid G，Andre S.Software-based replication for fault tolerance[J].IEEE Compu ter，1997，30(4):68-74.

[2] 孟玉明，張修如，劉玲霞.一種基于主動復(fù)制的動態(tài)容錯算法[J].計算機(jī)技術(shù)與發(fā)展.2007，17(12):48-52.

[3] Pow ell D.Delta 4:a generic architecture for dependable distribu ted computing[M].New York:Springer-Verlag，1991:1-484.

[4] 周明輝，郭長國，吳泉源，等.基于CORBA的容錯對象復(fù)制算法[J].計算機(jī)研究與發(fā)展，2002，39(3):290-294.

[5] 王俊嶺，汪 蕓.基于主動復(fù)制容錯技術(shù)的負(fù)載平衡模型[J].計算機(jī)工程，2005，31(11):56-58.

[6] 袁小玲，李心科.基于雙向動態(tài)規(guī)劃質(zhì)量有保障的組合服務(wù)選取[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2009，32(4): 465-469，499.

[7] Birman K P.Building secu re and reliable netw ork applications[M].New York:Mannning Publication Co，1997: 162-164.

[8] 錢 方，賈 焰，黃 杰，等.提高冗余服務(wù)性能的動態(tài)容錯算法[J].軟件學(xué)報，2001，12(6):928-935.