湯峰　張平　李方　黃致祥

(華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 廣東 廣州 510640)

基于PI反饋的分布式控制系統(tǒng)動(dòng)態(tài)負(fù)載均衡算法*

湯峰張平?李方黃致祥

(華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 廣東 廣州 510640)

摘要：針對(duì)分布式控制系統(tǒng)由于負(fù)載不均衡、網(wǎng)絡(luò)通信量大等引起的時(shí)延問題,文中設(shè)計(jì)了基于請(qǐng)求劃分的任務(wù)分配模型,提出了基于實(shí)時(shí)動(dòng)態(tài)比例積分(PI)反饋控制的負(fù)載均衡算法.該算法利用增量PI控制的思想,根據(jù)服務(wù)器節(jié)點(diǎn)性能的實(shí)時(shí)反饋值動(dòng)態(tài)調(diào)節(jié)服務(wù)器節(jié)點(diǎn)的分配權(quán)值,通過虛擬節(jié)點(diǎn)轉(zhuǎn)移算法局部調(diào)整虛擬節(jié)點(diǎn)的分配,以維護(hù)哈希空間的穩(wěn)定.仿真實(shí)驗(yàn)結(jié)果表明,該算法實(shí)現(xiàn)了分布式控制系統(tǒng)的動(dòng)態(tài)負(fù)載均衡,減小了服務(wù)器資源消耗及用于存取遠(yuǎn)程數(shù)據(jù)的通信開銷,提高了控制系統(tǒng)的實(shí)時(shí)性,具有良好的擴(kuò)展性和容錯(cuò)性.

關(guān)鍵詞：分布式控制系統(tǒng);負(fù)載均衡;哈希函數(shù);反饋控制

隨著計(jì)算機(jī)水平和控制需求的不斷提高,實(shí)時(shí)性、分布式已成為新一代開放式控制系統(tǒng)發(fā)展的趨勢(shì),分布式應(yīng)用將對(duì)控制系統(tǒng)起到越來越重要的作用[1].Akyildiz等[2]論述了分布式控制系統(tǒng)中分布式?jīng)Q策、任務(wù)分配等具有挑戰(zhàn)性的問題,指出任務(wù)的合理、均衡調(diào)度是分布式系統(tǒng)的技術(shù)核心之一.采取有效的負(fù)載均衡策略能有效地利用分布式系統(tǒng)的計(jì)算能力,提高控制系統(tǒng)的實(shí)時(shí)性能,因此,對(duì)分布式控制系統(tǒng)負(fù)載均衡模型的研究具有重要的意義.

負(fù)載均衡算法分為靜態(tài)負(fù)載均衡算法和動(dòng)態(tài)負(fù)載均衡算法.靜態(tài)負(fù)載均衡算法[3-8]僅根據(jù)事先規(guī)劃分配任務(wù),當(dāng)節(jié)點(diǎn)運(yùn)行時(shí)不能根據(jù)負(fù)載或性能的變化對(duì)任務(wù)分配進(jìn)行調(diào)整,由于沒有考慮負(fù)載的差異及各節(jié)點(diǎn)的性能變化,因此其資源利用率和可靠性較低,并且可能出現(xiàn)因節(jié)點(diǎn)達(dá)到性能瓶頸而使請(qǐng)求無法響應(yīng)的狀態(tài).因此,一些動(dòng)態(tài)調(diào)整負(fù)載分配的算法被陸續(xù)提出[9-10],但這些算法只根據(jù)請(qǐng)求差異進(jìn)行負(fù)載分配,沒有考慮服務(wù)器節(jié)點(diǎn)之間的性能差異.而動(dòng)態(tài)反饋負(fù)載均衡算法能夠根據(jù)各節(jié)點(diǎn)的性能差異及變化動(dòng)態(tài)調(diào)整請(qǐng)求任務(wù)的分配策略[11-12],但由于存在系統(tǒng)采集和重分配計(jì)算,因此算法復(fù)雜、系統(tǒng)開銷大、開發(fā)成本高、響應(yīng)時(shí)間長.為了能根據(jù)節(jié)點(diǎn)性能動(dòng)態(tài)調(diào)整請(qǐng)求任務(wù)的分配,并盡可能保持節(jié)點(diǎn)及負(fù)載的穩(wěn)定性,減少不必要的系統(tǒng)開銷,提高控制系統(tǒng)的實(shí)時(shí)性,文中提出了一種基于PI反饋的分布式控制系統(tǒng)動(dòng)態(tài)負(fù)載均衡策略.

1分布式系統(tǒng)架構(gòu)

1.1　架構(gòu)設(shè)計(jì)

如圖1所示的分布式系統(tǒng)架構(gòu)采用基于請(qǐng)求劃分的任務(wù)分配模型.負(fù)載均衡器采用基于哈希算法的負(fù)載分配策略,根據(jù)服務(wù)器性能值計(jì)算服務(wù)器節(jié)點(diǎn)的哈希值,確定其虛擬節(jié)點(diǎn)在哈?？臻g的分布,并對(duì)服務(wù)器節(jié)點(diǎn)性能進(jìn)行監(jiān)控以動(dòng)態(tài)調(diào)整服務(wù)器節(jié)點(diǎn)的哈希空間分布,當(dāng)節(jié)點(diǎn)的哈?？臻g有更新時(shí),負(fù)載均衡器將服務(wù)器節(jié)點(diǎn)的哈?？臻g分布發(fā)送給服務(wù)請(qǐng)求端,服務(wù)請(qǐng)求端計(jì)算自身請(qǐng)求消息的哈希值,并映射到哈?？臻g的某個(gè)服務(wù)器節(jié)點(diǎn)上,將請(qǐng)求消息發(fā)送至該服務(wù)器節(jié)點(diǎn).數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)存儲(chǔ)著系統(tǒng)中所有流程和服務(wù)的信息.當(dāng)服務(wù)器節(jié)點(diǎn)需要查詢的服務(wù)處理信息在本地緩存中時(shí),將不需要訪問后端存儲(chǔ)節(jié)點(diǎn),只需直接根據(jù)緩存中的服務(wù)信息對(duì)服務(wù)消息進(jìn)行處理.只有當(dāng)前服務(wù)對(duì)應(yīng)的信息不在本地緩存上時(shí),才需要訪問后端的存儲(chǔ)節(jié)點(diǎn),從存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)庫中獲取服務(wù)信息并更新本地緩存上的信息表.由于數(shù)據(jù)庫的訪問開銷遠(yuǎn)遠(yuǎn)大于本地緩存的訪問開銷,所以提高緩存命中率對(duì)提高分布式控制系統(tǒng)的實(shí)時(shí)性能有著重要的影響.

圖1　分布式系統(tǒng)架構(gòu)圖Fig.1　Architecture of distributed system

由于控制系統(tǒng)的控制任務(wù)被封裝成多個(gè)服務(wù)分布在不同的網(wǎng)絡(luò)節(jié)點(diǎn)中,因此,文中控制系統(tǒng)屬于分布式控制系統(tǒng)范疇.文中提出了將控制與負(fù)載均衡相分離的策略,如圖2所示,負(fù)載均衡策略不是將任務(wù)集中于某個(gè)節(jié)點(diǎn),而是分散到各個(gè)節(jié)點(diǎn)上,以減輕負(fù)載集中現(xiàn)象.該策略的具體步驟如下:

(1)各服務(wù)器節(jié)點(diǎn)計(jì)算本節(jié)點(diǎn)的負(fù)載均衡分配權(quán)值,權(quán)值有更新時(shí)發(fā)送給負(fù)載均衡器;

(2)負(fù)載均衡器周期性采集各服務(wù)器節(jié)點(diǎn)的狀態(tài)信息,檢測(cè)節(jié)點(diǎn)的可用性,并根據(jù)節(jié)點(diǎn)權(quán)值變化采用負(fù)載均衡算法計(jì)算各節(jié)點(diǎn)在哈希空間中的分布;

(3)當(dāng)哈?？臻g有更新時(shí)負(fù)載均衡器發(fā)送更新信息給服務(wù)請(qǐng)求端;

(4)服務(wù)請(qǐng)求端根據(jù)均衡策略選擇服務(wù)器節(jié)點(diǎn),并直接向該服務(wù)器節(jié)點(diǎn)發(fā)送服務(wù)控制消息.

圖2　控制與負(fù)載均衡相分離的策略Fig.2　Separation strategy for controlling and load balancing

由于控制任務(wù)中的服務(wù)控制消息不經(jīng)過負(fù)載均衡器而直接發(fā)送給服務(wù)器節(jié)點(diǎn),因此,該負(fù)載均衡算法并不增加控制任務(wù)的負(fù)擔(dān),即控制流程僅需由服務(wù)器節(jié)點(diǎn)來處理,減少了因增加負(fù)載均衡層節(jié)點(diǎn)轉(zhuǎn)發(fā)而引起的通信開銷,提高了控制系統(tǒng)的實(shí)時(shí)性.

1.2　通信開銷分析

通信開銷包括控制任務(wù)所產(chǎn)生的通信開銷和用于節(jié)點(diǎn)管理的通信開銷.

節(jié)點(diǎn)管理的通信開銷跟系統(tǒng)采用的架構(gòu)及運(yùn)行狀態(tài)相關(guān).當(dāng)系統(tǒng)不存在故障時(shí),其通信開銷主要是檢測(cè)節(jié)點(diǎn)狀態(tài)的開銷,當(dāng)系統(tǒng)發(fā)生故障時(shí),通信開銷還包括故障通知以及各節(jié)點(diǎn)間用于協(xié)商故障處理的開銷.假設(shè)有N個(gè)服務(wù)器節(jié)點(diǎn),狀態(tài)信息大小為L,檢測(cè)信息的發(fā)送周期為D,故障節(jié)點(diǎn)數(shù)為M,則文中架構(gòu)在正常狀態(tài)下用于管理的通信開銷為NL/D,在故障情況下會(huì)增加故障處理信息通信量ML/D,正常情況下服務(wù)器節(jié)點(diǎn)不會(huì)收到故障處理信息.

2負(fù)載均衡策略

分布式控制系統(tǒng)負(fù)載均衡策略設(shè)計(jì)中的兩個(gè)重要問題是控制的有序性和實(shí)時(shí)性.控制消息的亂序可能會(huì)導(dǎo)致整個(gè)系統(tǒng)的失控,為了保證控制系統(tǒng)的有序性以及系統(tǒng)的高緩存命中率,應(yīng)盡量使同一流程的子服務(wù)在一個(gè)服務(wù)器節(jié)點(diǎn)上處理,哈希負(fù)載均衡算法可以通過對(duì)請(qǐng)求的哈希映射來滿足這個(gè)需求.另一方面,控制系統(tǒng)的高實(shí)時(shí)性需求,使得在設(shè)計(jì)負(fù)載均衡算法時(shí)不宜采用復(fù)雜度太高的算法,一致性哈希的實(shí)現(xiàn)非常高效,平均算法復(fù)雜度為O(1),即在常量時(shí)間內(nèi)就可以完成服務(wù)器節(jié)點(diǎn)的選擇,保證了控制系統(tǒng)的實(shí)時(shí)性.

文獻(xiàn)[13]所述的多重映射的加權(quán)一致性哈希算法(MMWCH)是對(duì)經(jīng)典一致性哈希算法[14]的一種改進(jìn),MMWCH考慮了物理節(jié)點(diǎn)本身的性能以及訪問的熱點(diǎn)問題[13],但其加權(quán)調(diào)度算法的權(quán)值是靜態(tài)的,權(quán)值固定可能導(dǎo)致節(jié)點(diǎn)性能與請(qǐng)求分配相背離,使節(jié)點(diǎn)處于性能瓶頸而影響請(qǐng)求的響應(yīng)實(shí)時(shí)性.因此,需要結(jié)合實(shí)時(shí)動(dòng)態(tài)調(diào)整策略對(duì)算法進(jìn)行優(yōu)化.但一般的動(dòng)態(tài)性能分配算法是根據(jù)服務(wù)器節(jié)點(diǎn)的性能參數(shù)動(dòng)態(tài)分配任務(wù),反復(fù)計(jì)算降低了系統(tǒng)的穩(wěn)定性,占用了較多的系統(tǒng)資源,使系統(tǒng)響應(yīng)時(shí)間惡化.

基于系統(tǒng)高資源利用和高可靠性的需求,文中根據(jù)增量PI控制原理設(shè)計(jì)了實(shí)時(shí)動(dòng)態(tài)PI反饋控制負(fù)載均衡策略(PIDLBA),該策略以MMWCH為基礎(chǔ),結(jié)合動(dòng)態(tài)調(diào)整策略,根據(jù)節(jié)點(diǎn)性能偏差調(diào)節(jié)負(fù)載分配,并設(shè)計(jì)了虛擬節(jié)點(diǎn)轉(zhuǎn)移算法,用于局部調(diào)整虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)的映射關(guān)系,避免因哈希空間的重映射而引起的系統(tǒng)開銷,同時(shí)減少重映射造成的大量任務(wù)被發(fā)往不同節(jié)點(diǎn)的現(xiàn)象,提高系統(tǒng)的穩(wěn)定性和緩存命中率,降低請(qǐng)求的響應(yīng)時(shí)間.

2.1　基于PI反饋的服務(wù)器節(jié)點(diǎn)分配權(quán)值計(jì)算

服務(wù)器節(jié)點(diǎn)每隔一個(gè)采集周期對(duì)本節(jié)點(diǎn)的CPU、內(nèi)存和網(wǎng)絡(luò)帶寬使用情況進(jìn)行采集,并計(jì)算性能指標(biāo)值,然后通過PI反饋控制算法得到該節(jié)點(diǎn)的分配權(quán)值,分配權(quán)值被服務(wù)器節(jié)點(diǎn)推送給負(fù)載均衡器以實(shí)現(xiàn)負(fù)載任務(wù)的分配.

(1)

式中,KP為比例系數(shù),KI為積分系數(shù).式(1)是一個(gè)負(fù)反饋公式,最終會(huì)使分配權(quán)值達(dá)到一個(gè)穩(wěn)定點(diǎn).服務(wù)器節(jié)點(diǎn)根據(jù)式(1)計(jì)算出k時(shí)刻的Wi(k)和ΔWi(k),并推送給負(fù)載均衡器.

2.2　負(fù)載均衡器的任務(wù)分配策略

負(fù)載均衡器啟動(dòng)時(shí)開啟兩個(gè)進(jìn)程分別對(duì)服務(wù)器節(jié)點(diǎn)和服務(wù)請(qǐng)求端進(jìn)行監(jiān)控.服務(wù)器節(jié)點(diǎn)的監(jiān)控進(jìn)程主要完成服務(wù)器節(jié)點(diǎn)的哈希值映射工作:首先根據(jù)服務(wù)器節(jié)點(diǎn)提供的分配權(quán)值計(jì)算各物理節(jié)點(diǎn)的虛擬節(jié)點(diǎn)數(shù),通過哈希函數(shù)計(jì)算虛擬節(jié)點(diǎn)哈希值,并將其映射到哈?？臻g上;隨后每隔一個(gè)負(fù)載均衡計(jì)算周期,負(fù)載均衡器判斷節(jié)點(diǎn)是否需要調(diào)整,若是,則采用虛擬節(jié)點(diǎn)轉(zhuǎn)移算法對(duì)其進(jìn)行動(dòng)態(tài)調(diào)整.綜合考慮分配的均衡性、時(shí)間消耗等因素,文中采用Toeplitz哈希[15]作為Hash函數(shù).服務(wù)器節(jié)點(diǎn)監(jiān)控進(jìn)程如圖3所示,具體過程詳述如下.

圖3　服務(wù)器節(jié)點(diǎn)監(jiān)控進(jìn)程Fig.3　Monitoring process of server nodes

3)若有服務(wù)器節(jié)點(diǎn)分配權(quán)值發(fā)生變化,則調(diào)用虛擬節(jié)點(diǎn)轉(zhuǎn)移算法,該算法的核心是把性能較差的服務(wù)器節(jié)點(diǎn)的虛擬節(jié)點(diǎn)轉(zhuǎn)移給性能較優(yōu)的服務(wù)器,通過調(diào)節(jié)服務(wù)器與虛擬節(jié)點(diǎn)之間的映射關(guān)系來調(diào)節(jié)負(fù)載的分配.虛擬節(jié)點(diǎn)轉(zhuǎn)移算法描述如下:

(2)計(jì)算當(dāng)前k時(shí)刻比上一負(fù)載均衡周期k-1時(shí)刻服務(wù)器節(jié)點(diǎn)i的虛擬節(jié)點(diǎn)數(shù)增量ΔNv,i=Nv,i(k)-Nv,i(k-1).

(3)N個(gè)服務(wù)器節(jié)點(diǎn)按其虛擬節(jié)點(diǎn)數(shù)增量升序排列Ranknodes(ΔNv,1,ΔNv,2,…,ΔNv,N).

(4)計(jì)算虛擬節(jié)點(diǎn)數(shù)增量的平均值ΔNv,avg=(ΔNv,1+ΔNv,2+…+ΔNv,N)/N.

(5)計(jì)算虛擬節(jié)點(diǎn)數(shù)增量與其平均值之差,ΔNv,avg-ΔNv,i>0表示該服務(wù)器節(jié)點(diǎn)需要減少虛擬節(jié)點(diǎn),ΔNv,i-ΔNv,avg>0表示該服務(wù)器節(jié)點(diǎn)可以增加虛擬節(jié)點(diǎn).為了減少哈希值及其映射的變化,可以把需要減少的虛擬節(jié)點(diǎn)轉(zhuǎn)移給可以增加虛擬節(jié)點(diǎn)的服務(wù)器節(jié)點(diǎn),轉(zhuǎn)移規(guī)則從請(qǐng)求任務(wù)量最小的虛擬節(jié)點(diǎn)開始轉(zhuǎn)移,其偽代碼如下:

{i=1;j=n;

while(ΔNv,avg-ΔNv,i>0 && ΔNv,j-ΔNv,avg>0)

if ΔNv,avg-ΔNv,i>=ΔNv,j-ΔNv,avgthen

Transmitvi(i,j,ΔNv,j-ΔNv,avg);

∥將服務(wù)器節(jié)點(diǎn)i的ΔNv,j-ΔNv,avg個(gè)任務(wù)量最小的虛擬節(jié)點(diǎn)轉(zhuǎn)移給服務(wù)器節(jié)點(diǎn)j,并記錄服務(wù)器節(jié)點(diǎn)i和j的虛擬節(jié)點(diǎn)數(shù)的變化

Upadatevi(ΔNv,i);

∥更新ΔNv,i=ΔNv,i+ΔNv,j-ΔNv,avg

j--;

∥服務(wù)器節(jié)點(diǎn)i的虛擬節(jié)點(diǎn)依次向虛擬節(jié)點(diǎn)數(shù)增量次高ΔNv,j-1的服務(wù)器節(jié)點(diǎn)轉(zhuǎn)移

elseif ΔNv,avg-ΔNv,i<ΔNv,j-ΔNv,avgthen

Transmitvi(i,j,ΔNv,avg-ΔNv, j);

∥將服務(wù)器節(jié)點(diǎn)i的ΔNv,avg-ΔNv, j個(gè)任務(wù)量最小的虛擬節(jié)點(diǎn)轉(zhuǎn)移給服務(wù)器節(jié)點(diǎn)j,并記錄服務(wù)器節(jié)點(diǎn)i和j的虛擬節(jié)點(diǎn)數(shù)的變化

Upadatevi(ΔNv, j);

∥更新ΔNv, j=ΔNv,i+ΔNv, j-ΔNv,avg

i++;

∥服務(wù)器節(jié)點(diǎn)j還需要從虛擬節(jié)點(diǎn)數(shù)增量次低ΔNi+1的服務(wù)器節(jié)點(diǎn)獲取虛擬節(jié)點(diǎn)

end while}

4)若虛擬節(jié)點(diǎn)有更新,則更新哈希環(huán)上虛擬節(jié)點(diǎn)分布.負(fù)載均衡器繼續(xù)監(jiān)聽服務(wù)器節(jié)點(diǎn)的狀態(tài)信息.

服務(wù)請(qǐng)求端監(jiān)控進(jìn)程主要實(shí)現(xiàn)請(qǐng)求任務(wù)的分配.根據(jù)服務(wù)器節(jié)點(diǎn)監(jiān)控進(jìn)程中的虛擬節(jié)點(diǎn)哈希值,服務(wù)請(qǐng)求端查找與服務(wù)請(qǐng)求哈希值相匹配的服務(wù)器節(jié)點(diǎn).服務(wù)請(qǐng)求端把服務(wù)請(qǐng)求的元組(流程ID,服務(wù)ID,函數(shù)ID)作為Toeplitz哈希函數(shù)的鍵值,映射到哈希環(huán)上某個(gè)點(diǎn),如果該點(diǎn)沒有對(duì)應(yīng)的服務(wù)器節(jié)點(diǎn),那么沿哈希環(huán)順時(shí)針查找,找到第1個(gè)有映射服務(wù)器節(jié)點(diǎn)的虛擬節(jié)點(diǎn)并將請(qǐng)求任務(wù)分配給此虛擬節(jié)點(diǎn)對(duì)應(yīng)的服務(wù)器.

3實(shí)驗(yàn)與結(jié)果分析

3.1　 負(fù)載均衡性測(cè)試

圖4　N=10時(shí)執(zhí)行105次隨機(jī)流程的服務(wù)器節(jié)點(diǎn)負(fù)載Fig.4　Loads of server nodes after executing 105random process when N=10

表1　服務(wù)器節(jié)點(diǎn)的最大、最小訪問量Table 1　Maximum and minimum access of server nodes

由圖4可看出:輪詢算法具有絕對(duì)的負(fù)載均衡性;PIDLBA 和MMWCH算法的負(fù)載均衡性遠(yuǎn)遠(yuǎn)優(yōu)于取模哈希算法和隨機(jī)算法;PIDLBA算法的負(fù)載均衡性稍優(yōu)于MMWCH算法,這是因?yàn)楫?dāng)節(jié)點(diǎn)性能超出預(yù)期時(shí)會(huì)自動(dòng)調(diào)節(jié)分配權(quán)值,使負(fù)載達(dá)到平衡.

3.2　緩存命中率測(cè)試

分布式控制系統(tǒng)的負(fù)載均衡算法必須具有良好的擴(kuò)展性,即節(jié)點(diǎn)緩存命中率不能隨著服務(wù)器節(jié)點(diǎn)數(shù)的增加而大幅下降.為分析算法的節(jié)點(diǎn)擴(kuò)展性,文中通過調(diào)節(jié)服務(wù)器節(jié)點(diǎn)數(shù),比較系統(tǒng)在106次隨機(jī)訪問下的緩存命中率,實(shí)驗(yàn)結(jié)果如圖5所示.由圖可見,PIDLBA、MMWCH和取模哈希算法都具有良好的擴(kuò)展性,緩存命中率無明顯的下降,而隨機(jī)算法和輪詢算法的緩存命中率由2個(gè)節(jié)點(diǎn)時(shí)的98%下降到1 000個(gè)節(jié)點(diǎn)時(shí)的不及5%.這是因?yàn)槿∧９Ｋ惴ǖ脑L問節(jié)點(diǎn)與數(shù)據(jù)相關(guān),節(jié)點(diǎn)數(shù)量的影響不大.而PIDLBA和MMWCH算法的緩存命中率略低于取模哈希算法,主要是由于設(shè)定了多重映射.PIDLBA 算法的緩存命中率稍低于MMWCH算法,這是由于PIDLBA 算法在節(jié)點(diǎn)性能超出預(yù)期時(shí)會(huì)發(fā)生局部虛擬節(jié)點(diǎn)轉(zhuǎn)移,導(dǎo)致其緩存命中率微降.

圖5　節(jié)點(diǎn)擴(kuò)展對(duì)緩存命中率的影響Fig.5　Effect of node expansion on the hit rate of cache

當(dāng)系統(tǒng)架構(gòu)及控制任務(wù)確定后,與控制任務(wù)相關(guān)的控制信息及用于節(jié)點(diǎn)管理的通信開銷隨之確定,文中主要分析由不同負(fù)載均衡算法引起的與緩存命中率相關(guān)的遠(yuǎn)程數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)的通信開銷.

設(shè)與遠(yuǎn)程數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)通信傳輸數(shù)據(jù)包大小為256B,圖6為遠(yuǎn)程數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)的通信開銷,從圖中可見,通信開銷最小的是取模哈希算法,其次是MMWCH和PIDLBA 算法,隨機(jī)算法和輪詢算法因緩存命中率的降低而導(dǎo)致其遠(yuǎn)程數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)的通信開銷非常大.

圖6　遠(yuǎn)程數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)的通信開銷Fig.6　Communication overhead of the remote data storage nodes

3.3　容錯(cuò)性測(cè)試

為了比較各算法的容錯(cuò)能力,文中模擬在一個(gè)擁有100個(gè)服務(wù)器節(jié)點(diǎn)的分布式系統(tǒng)中,隨機(jī)把其中一個(gè)服務(wù)器節(jié)點(diǎn)設(shè)為不可用(其請(qǐng)求數(shù)為0),并比較各算法在105次隨機(jī)訪問中的緩存命中率變化情況,結(jié)果如圖7所示.

圖7　某節(jié)點(diǎn)失效時(shí)的緩存命中率變化情況Fig.7　Changes of the hit rate on the cache when a node fails

由圖7可見,在某個(gè)服務(wù)器節(jié)點(diǎn)不可用的情況下，PIDLBA、MMWCH、隨機(jī)算法和輪詢算法的緩存命中率都沒有發(fā)生大的波動(dòng),具有良好的容錯(cuò)能力，只有取模哈希算法的緩存命中率幾乎為0,然后隨著請(qǐng)求數(shù)的增加不斷提升到90%以上,這是因?yàn)楣?jié)點(diǎn)數(shù)的變化影響了絕大多數(shù)數(shù)據(jù)與緩存之間的映射關(guān)系,所以出現(xiàn)了大量緩存不命中的情況,顯然,取模哈希算法不具有良好的容錯(cuò)性.

3.4　系統(tǒng)響應(yīng)時(shí)間測(cè)試

實(shí)時(shí)性是衡量控制系統(tǒng)性能的一個(gè)重要指標(biāo),反映控制系統(tǒng)對(duì)指令的響應(yīng)速度和執(zhí)行效率.為了測(cè)量各負(fù)載均衡算法對(duì)服務(wù)請(qǐng)求平均響應(yīng)時(shí)間的影響,文中啟動(dòng)一個(gè)簡(jiǎn)單測(cè)試流程由消息發(fā)送方發(fā)送消息給4個(gè)性能相同的服務(wù)器節(jié)點(diǎn)進(jìn)行處理,消息大小是256B,服務(wù)器節(jié)點(diǎn)處理完成后發(fā)送信息給消息接收端;然后改變測(cè)試流程的并發(fā)數(shù),測(cè)試過程中給服務(wù)器節(jié)點(diǎn)1加1個(gè)負(fù)載干擾,使該節(jié)點(diǎn)性能達(dá)到0.85以上,記錄各服務(wù)器節(jié)點(diǎn)的性能變化情況,如圖8(a)所示.由圖8(a)可知,服務(wù)器節(jié)點(diǎn)1的性能過大時(shí),由負(fù)反饋算法減小該節(jié)點(diǎn)的分配權(quán)值(4個(gè)服務(wù)器節(jié)點(diǎn)的分配權(quán)值如圖8(b)所示),使分配給該節(jié)點(diǎn)的負(fù)載減少,而其他節(jié)點(diǎn)的負(fù)載增加(4個(gè)服務(wù)器節(jié)點(diǎn)的負(fù)載量如圖8(c)所示),因此,當(dāng)節(jié)點(diǎn)1負(fù)載干擾取消時(shí),其性能值略低于其他3個(gè)節(jié)點(diǎn)的性能,當(dāng)請(qǐng)求負(fù)載增加到一定量時(shí),節(jié)點(diǎn)性能接近極限,系統(tǒng)達(dá)到飽和狀態(tài).

圖8　各服務(wù)器節(jié)點(diǎn)的性能比較Fig.8　Performance comparison of each server node

記錄消息發(fā)送端的發(fā)送時(shí)間和接收端接收到消息的時(shí)間,并比較各個(gè)算法的服務(wù)請(qǐng)求平均響應(yīng)時(shí)間，結(jié)果見圖9.可以看出,PIDLBA 算法的服務(wù)請(qǐng)求平均響應(yīng)時(shí)間變化曲線平滑遞增,在服務(wù)器節(jié)點(diǎn)1有負(fù)載干擾時(shí),其分配權(quán)值降低,被分配到的負(fù)載量減少,因此響應(yīng)時(shí)間未受到大的影響.當(dāng)請(qǐng)求負(fù)載增加到一定量(2 400個(gè)請(qǐng)求附近)時(shí),響應(yīng)時(shí)間的變化出現(xiàn)抖動(dòng),表明系統(tǒng)即將達(dá)到飽和狀態(tài).MMWCH與PIDLBA算法的服務(wù)請(qǐng)求平均響應(yīng)時(shí)間接近,但會(huì)有較大的波動(dòng),這是因?yàn)镸MWCH算法只能靜態(tài)分配權(quán)值,當(dāng)服務(wù)器節(jié)點(diǎn)遇到干擾性能發(fā)生變化時(shí),不能及時(shí)地調(diào)整請(qǐng)求的分配,導(dǎo)致服務(wù)器節(jié)點(diǎn)1達(dá)到性能瓶頸,延長了其消息的響應(yīng)時(shí)間.隨機(jī)算法、輪詢算法和取模哈希算法的服務(wù)請(qǐng)求平均響應(yīng)時(shí)間較大,請(qǐng)求的分配不均衡造成了某些服務(wù)器節(jié)點(diǎn)性能急劇惡化,從而導(dǎo)致服務(wù)請(qǐng)求的等待和處理時(shí)間延長,其響應(yīng)時(shí)間及變化波動(dòng)增大.

圖9　幾種負(fù)載均衡算法的服務(wù)請(qǐng)求平均響應(yīng)時(shí)間比較Fig.9　Comparison of average response time of service request among several load balancing algorithms

4結(jié)論

文中設(shè)計(jì)了基于請(qǐng)求劃分的分布式控制系統(tǒng)負(fù)載均衡模型,提出了一種動(dòng)態(tài)反饋式負(fù)載均衡算法PIDLBA,該算法通過PI反饋控制由服務(wù)器節(jié)點(diǎn)的性能偏差反映節(jié)點(diǎn)的分配權(quán)值,進(jìn)而確定物理節(jié)點(diǎn)的虛擬節(jié)點(diǎn)變化量,然后通過虛擬節(jié)點(diǎn)轉(zhuǎn)移算法調(diào)整服務(wù)請(qǐng)求的分配,實(shí)現(xiàn)分布式控制系統(tǒng)的動(dòng)態(tài)負(fù)載均衡.對(duì)控制系統(tǒng)的擴(kuò)展性、容錯(cuò)性、實(shí)時(shí)性的仿真實(shí)驗(yàn)結(jié)果表明,該模型較好地實(shí)現(xiàn)了負(fù)載動(dòng)態(tài)平衡,具有良好的擴(kuò)展性、容錯(cuò)性和實(shí)時(shí)性.

參考文獻(xiàn):

[1]Stumpfegger Thomas,Tremmel Andreas,Tarragona Christian,et al.A virtual robot control using a service-based architecture and a physics-based simulation environment [R].Augsburg:KUKA Roboter GmbH,2007.

[2]Akyildiz I F,Kasimoglu I H.Wireless sensor and actor networks:research challenges [J].Ad Hoc Networks,2004,2(4):351-367.

[3]Thanalapati T,Dandamudi S.An efficient adaptive schedu-ling scheme for distributed memory multicomputers [J]. IEEE Transactions on Parallel and Distributed Systems,2001,12(7):758-768.

[4]Rai Idris A,Alanyali Murat.Uniform weighted round robin scheduling algorithms for input queued swithes [C]∥Pro- ceedings of IEEE International Conference on Communications.Helsinki:IEEE,2001:2028-2032.

[5]Aumasson J P,Henzen L,Meier W,et al.Quark:a lightweight hash [J].Journal of Cryptology,2013,26(2):313-339.

[6]Moharil S,Lee S.Load balancing of parallel simulated annealing on a temporally heterogeneous cluster of workstation [C]∥Proceedings of the 21st International Symposium on Parallel Distributed Processing.Long Beach:IEEE,2007:1-8.

[7]Moallem A,Ludwig S.Using artificial life techniques for distributed grid job scheduling [C]∥Proceedings of ACM Symposium on Applied Computing.Honolulu:ACM,2009:1091-1097.

[8]Zomaya A,Teh Y.Observation on using genetic algorithms for dynamic load balancing [J].IEEE Transactions on Parallel and Distributed Systems,2001,12(9):899-911.

[9]Bryhni H,Klovning E,Kure O.A comparison of load ba-lancing techniques for scalable web servers [J].IEEE Network,2000,14(4):58-64.

[10]Casal icchio E,Tucci S.Static and dynamic scheduling algorithm for scalable web server farm [C]∥Procee-dings of the 9th Euromicro Worshop on Parallel and Distributed Processing.Mantova:IEEE,2001:369-376.

[11]Lin W,Wang J Z,Liang C,et al.A threshold-based dynamic resource allocation scheme for cloud computing [J].Procedia Engineering,2011,23:695-703.

[12]Song B,Hassan M M,Huh E.A novel heuristic-based task selection and allocation framework in dynamic collaborative cloud service platform [C]∥Proceedings of the 2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis:IEEE,2010:360-367.

[13]Decandia Guiseppe,Hastorun Deniz,Jampani Madan,et al.Dynamo:Amazon’s highly available key-value store [C]∥Proceedings of the 21st ACM Symposium on Operating Systems Principles.Washington:ACM,2007:205-220.

[14]Karger David,Lehman Eric.Consistent Hashing and random trees:distributed cache protocols for relieving hot spots on the World Wide Web [C]∥Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing.New York:ACM,1997:654-663.

[15]Krawczyk H.New hash functions for message authentication [C]∥Advances in Cryptology-Eurocrypt’95.Berlin/Heidelberg:Springer,1995:301-310.

[16]Karger David,Sherman Alex,Berkheimer Andy,et al.Web caching with consistent hashing [J].Computer Networks,1999,31(11):1203-1213.

PI Feedback-Based Dynamic Load-Balancing Algorithm for Distributed Control System

TangFengZhangPingLiFangHuangZhi-xiang

(School of Computer Science and Technology, South China University of Technology, Guangzhou 510640, Guangdong, China)

Abstract:In order to solve the problem of slow response caused by the load imbalance and the communication overhead in distributed control systems, a task allocation model is constructed on the basis of the request division, and a dynamic load-balancing algorithm is proposed on the basis of the real-time dynamic proportional integral (PI) feedback control. This algorithm adopts the PI control method to dynamically adjust the allocation weight of server nodes according to the real-time feedback values of the performance of the nodes, and then employs the virtual node transfer algorithm to partially adjust the distribution of virtual nodes, so as to maintain the stability of Hash space. Simulation results show that the proposed algorithm realizes the dynamic load balancing of distributed control system, reduces the communication overhead and improves the real-time performance of the control system, and that the proposed algorithm is of a high expansion and an excellent fault tolerance.

Key words:distributed control systems; load balancing; Hash functions; feedback control

中圖分類號(hào)：TP273

doi：10.3969/j.issn.1000-565X.2015.09.013

作者簡(jiǎn)介：湯峰(1979-),女,博士生,工程師,主要從事機(jī)器人控制研究.E-mail: fengtang@scut.edu.cn? 通信作者： 張平(1964-),男,博士,教授,主要從事機(jī)器人控制研究.E-mail: pzhang@scut.edu.cn

*基金項(xiàng)目：廣東省科技計(jì)劃項(xiàng)目(2014B090921007)；廣州市科技計(jì)劃項(xiàng)目(20150810068);廣州市海珠區(qū)科技計(jì)劃項(xiàng)目(2014-cg-02)

收稿日期：2015-01-22

文章編號(hào)：1000-565X(2015)09-0081-07

Foundation item： Supported by the Science and Technology Planning Projects of Guangdong Province(2014B090921007)