唐金輝， 鐘 誠(chéng)， 吳惜華， 莫英紅， 李效魯， 林 瑞

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

0 引 言

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 OM模塊算法

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

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

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

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

OM模塊算法如下:

2.2 RM模塊算法

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

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

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

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

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

RM模塊算法如下:

2.3 組成員失效的處理

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

2.4 算法分析

2.4.1 一致性分析

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

2.4.2 性能分析

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

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

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

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

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

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

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

3 實(shí) 驗(yàn)

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

本文初稿首次刊登于《計(jì)算機(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] 孟玉明，張修如，劉玲霞.一種基于主動(dòng)復(fù)制的動(dòng)態(tài)容錯(cuò)算法[J].計(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] 周明輝，郭長(zhǎng)國(guó)，吳泉源，等.基于CORBA的容錯(cuò)對(duì)象復(fù)制算法[J].計(jì)算機(jī)研究與發(fā)展，2002，39(3):290-294.

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

[6] 袁小玲，李心科.基于雙向動(dòng)態(tài)規(guī)劃質(zhì)量有保障的組合服務(wù)選取[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(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] 錢(qián) 方，賈 焰，黃 杰，等.提高冗余服務(wù)性能的動(dòng)態(tài)容錯(cuò)算法[J].軟件學(xué)報(bào)，2001，12(6):928-935.