周 岳，陳慶奎

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)(*通信作者電子郵箱chenqingkui@usst.edu.cn)

0 引言

隨著計(jì)算機(jī)信息技術(shù)與互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)資源呈現(xiàn)爆發(fā)式增長。文獻(xiàn)[1-2]研究表明，日益增長的數(shù)據(jù)，會(huì)對(duì)服務(wù)平臺(tái)的接收、處理和存儲(chǔ)數(shù)據(jù)的能力帶來巨大壓力。面對(duì)快速增長的數(shù)據(jù)量，有必要進(jìn)一步提高服務(wù)平臺(tái)的接收能力。分布式系統(tǒng)通過網(wǎng)絡(luò)組織廉價(jià)計(jì)算機(jī)，來完成單臺(tái)服務(wù)器無法接收、處理和存儲(chǔ)的任務(wù)。分布式系統(tǒng)中的應(yīng)用程序可以分成多個(gè)任務(wù)，分別執(zhí)行在不同的計(jì)算機(jī)節(jié)點(diǎn)上，各個(gè)任務(wù)可以并發(fā)執(zhí)行。實(shí)踐表明，分布式系統(tǒng)能夠顯著提升服務(wù)平臺(tái)接收、處理和存儲(chǔ)數(shù)據(jù)的能力。

文獻(xiàn)[3]指出，由于分布式系統(tǒng)內(nèi)存在任務(wù)的多樣性和各節(jié)點(diǎn)性能的差異性，導(dǎo)致集群內(nèi)存在負(fù)載不平衡現(xiàn)象。負(fù)載的不平衡性導(dǎo)致分布式系統(tǒng)無法充分發(fā)揮其并行處理的性能。如果負(fù)載差異過大，還會(huì)進(jìn)一步導(dǎo)致系統(tǒng)的處理速度下降、網(wǎng)絡(luò)延遲增加、任務(wù)的響應(yīng)速度下降等。

當(dāng)前對(duì)于負(fù)載平衡的研究有很多，如文獻(xiàn)[4-6]，分別提出了不同的解決方案，這些研究都取得了不錯(cuò)的成果，但是仍然遺留很多問題有待解決。目前負(fù)載平衡系統(tǒng)仍然還存在文獻(xiàn)[7]中提及的問題：1)平衡系統(tǒng)各節(jié)點(diǎn)角色固定，系統(tǒng)不具有自適應(yīng)性。當(dāng)前分布式系統(tǒng)是通過節(jié)點(diǎn)冗余來實(shí)現(xiàn)系統(tǒng)的魯棒性，要求在負(fù)載平衡系統(tǒng)中對(duì)不同功能節(jié)點(diǎn)都要進(jìn)行備份冗余。該方案造成資源開銷過大。通過節(jié)點(diǎn)角色自適應(yīng)，能有效減少備份節(jié)點(diǎn)數(shù)目，降低資源的消耗。2)模型的通用性不高，大部分負(fù)載平衡系統(tǒng)的研究都是針對(duì)特定的應(yīng)用場(chǎng)景。負(fù)載平衡模型適用場(chǎng)景有限。當(dāng)一個(gè)大型系統(tǒng)中存在多種子系統(tǒng)時(shí)，系統(tǒng)往往需要為每個(gè)子系統(tǒng)單獨(dú)設(shè)計(jì)負(fù)載平衡系統(tǒng)。這就導(dǎo)致系統(tǒng)過于復(fù)雜，而且影響系統(tǒng)的可擴(kuò)展性。3)任務(wù)整體遷移導(dǎo)致資源大量消耗，而且平衡周期過長等問題。當(dāng)前任務(wù)遷移具有指向性，在負(fù)載平衡任務(wù)遷移過程中，負(fù)載較輕的節(jié)點(diǎn)短期內(nèi)會(huì)被大量遷入任務(wù)，導(dǎo)致這類節(jié)點(diǎn)負(fù)載過重再次觸發(fā)負(fù)載平衡；這樣周期往復(fù)的震蕩性，嚴(yán)重影響系統(tǒng)的性能。

針對(duì)這些問題，本文提出了混合式負(fù)載遷移平衡算法。算法設(shè)計(jì)以最小化遷移任務(wù)為目標(biāo)，盡量減少任務(wù)的遷移，節(jié)約系統(tǒng)資源；同時(shí)為了減少備份冗余造成節(jié)點(diǎn)資源的浪費(fèi)，該負(fù)載平衡方案采取節(jié)點(diǎn)自適應(yīng)策略，各個(gè)節(jié)點(diǎn)互為備份節(jié)點(diǎn)。實(shí)驗(yàn)表明，系統(tǒng)具有負(fù)載平衡周期短、任務(wù)響應(yīng)時(shí)延短等特點(diǎn)。

1 相關(guān)工作

一般來說，現(xiàn)行的負(fù)載平衡控制模式有3種：集中式控制模式、分布式控制模式和混合式控制模式。

集中式控制模式指定一個(gè)節(jié)點(diǎn)來負(fù)責(zé)全系統(tǒng)的任務(wù)調(diào)度和監(jiān)督收集各節(jié)點(diǎn)的運(yùn)行狀況，如圖1(a)所示。集中式控制模式比較簡單，系統(tǒng)全局資源利用率最高；但是該模式容易造成控制節(jié)點(diǎn)計(jì)算量大、內(nèi)存開銷大、易產(chǎn)生瓶頸，且該模式不利于系統(tǒng)擴(kuò)展。文獻(xiàn)[8]研究表明集中式控制模式一般用于小型系統(tǒng)中，不適合使用在大規(guī)模分布式系統(tǒng)中。隨著系統(tǒng)規(guī)模的擴(kuò)大，集中式控制模式往往不可行。

在分布式控制模式中，每個(gè)節(jié)點(diǎn)自主完成任務(wù)調(diào)度，如圖1(b)所示。分布式控制模式中，每個(gè)節(jié)點(diǎn)與周圍若干個(gè)節(jié)點(diǎn)相連，并收集周圍節(jié)點(diǎn)的運(yùn)行狀況。分布式控制模式容錯(cuò)性較強(qiáng)，且易于擴(kuò)展，但是分布式負(fù)載平衡控制模式比較復(fù)雜。目前這種負(fù)載平衡策略分為3種：第一類是基于市場(chǎng)學(xué)的遷移策略，如Izakian等[9]提出的連續(xù)雙次競(jìng)爭(zhēng)(Continuous Double Auction， CDA)分配任務(wù)方法。該方法通過計(jì)算遷移任務(wù)后系統(tǒng)的整體性能收益，來決定是否進(jìn)行任務(wù)遷移。第二類是基于社會(huì)學(xué)的遷移策略，如Wang等[10]提出的貪婪算法。在該算法中負(fù)載節(jié)點(diǎn)在其相連的局域網(wǎng)內(nèi)使用貪婪算法，選擇局部最優(yōu)的方案進(jìn)行任務(wù)遷移。第三類是通過一些其他方式來進(jìn)行負(fù)載分配的方案，如文獻(xiàn)[11]提出的自適應(yīng)負(fù)載分配方案、文獻(xiàn)[12]提出的資源競(jìng)爭(zhēng)負(fù)載分配方案等。分布式模式的負(fù)載平衡面臨較高的負(fù)載計(jì)算成本，且負(fù)載通信占用大量網(wǎng)絡(luò)帶寬。

圖1 3種控制模式結(jié)構(gòu)

為了克服以上兩種控制模式的缺點(diǎn)，混合式控制模式應(yīng)運(yùn)而生。如圖1(c)所示，資源節(jié)點(diǎn)與周圍若干個(gè)節(jié)點(diǎn)相連的同時(shí)，又與其所在局部網(wǎng)絡(luò)內(nèi)的中心節(jié)點(diǎn)相連。在局部網(wǎng)絡(luò)內(nèi)使用集中控制模式，實(shí)現(xiàn)每個(gè)局域網(wǎng)資源利用率最大化，進(jìn)而實(shí)現(xiàn)資源全局利用最大化。在整個(gè)集群內(nèi)使用分布式模式，提高系統(tǒng)的可擴(kuò)展性。通過這種方式能夠有效結(jié)合集中控制模式和分布式控制模式的優(yōu)點(diǎn)，提升系統(tǒng)的整體性能。

雖然以上模型提供了很好的性能，但是仍然存在系統(tǒng)中節(jié)點(diǎn)角色固定、模型通用性差和系統(tǒng)負(fù)載周期長等問題。為了解決這些問題，本文提出了混合式負(fù)載平衡策略。

2 接入系統(tǒng)模型

為了提高服務(wù)平臺(tái)系統(tǒng)的接收能力，本文對(duì)接入系統(tǒng)進(jìn)行了優(yōu)化設(shè)計(jì)。如圖2所示，接入系統(tǒng)分為三層：數(shù)據(jù)接收層、業(yè)務(wù)處理層和數(shù)據(jù)存取層。為了實(shí)現(xiàn)各層之間的解耦合，各個(gè)層次不直接交互，數(shù)據(jù)共享通過數(shù)據(jù)緩沖區(qū)實(shí)現(xiàn)。各層可以部署在不同機(jī)器上，也可以部署在同一臺(tái)機(jī)器上。不同的是部署在不同機(jī)器上時(shí)，數(shù)據(jù)的共享通過網(wǎng)絡(luò)傳輸實(shí)現(xiàn)。因?yàn)楝F(xiàn)有的分布式處理系統(tǒng)和分布式存儲(chǔ)系統(tǒng)相對(duì)成熟，所以在這兩層，本文直接使用現(xiàn)有技術(shù)。下面重點(diǎn)討論數(shù)據(jù)接收層。

圖2 接入系統(tǒng)結(jié)構(gòu)

2.1 數(shù)據(jù)接收層

在數(shù)據(jù)接收層，本文使用用戶數(shù)據(jù)報(bào)協(xié)議(User Datagram Protocol， UDP)。使用UDP的原因是：1)實(shí)時(shí)性高，UDP注重的是數(shù)據(jù)包的吞吐量，這和追求的高數(shù)據(jù)接收能力吻合。2)與傳輸控制協(xié)議(Transmission Control Protocol， TCP)相比，UDP在數(shù)據(jù)傳輸前不需要先建立連接，這意味著便于通信擴(kuò)展，且節(jié)約系統(tǒng)資源。但是UDP通信協(xié)議不是一個(gè)可靠的通信協(xié)議，針對(duì)這一問題，本文在UDP通信協(xié)議的基礎(chǔ)上設(shè)計(jì)了一個(gè)可靠的傳輸協(xié)議。該傳輸協(xié)議通過數(shù)據(jù)包重傳技術(shù)確保通信可靠。

為了實(shí)現(xiàn)重傳，首先使得計(jì)算機(jī)能夠區(qū)分每個(gè)數(shù)據(jù)包來源，及數(shù)據(jù)包到達(dá)的先后順序。協(xié)議為每個(gè)數(shù)據(jù)包添加一個(gè)標(biāo)識(shí)(Identification， ID)字段，用來標(biāo)識(shí)數(shù)據(jù)源，并在數(shù)據(jù)包中添加包序號(hào)字段，來區(qū)分?jǐn)?shù)據(jù)包到達(dá)的先后順序。在接收層為每個(gè)向系統(tǒng)傳輸數(shù)據(jù)的數(shù)據(jù)源開辟一個(gè)臨時(shí)緩沖區(qū)。緩沖區(qū)格式如圖3所示。ID標(biāo)識(shí)不同數(shù)據(jù)源，數(shù)字編號(hào)表示包的序號(hào)。

圖3 臨時(shí)緩沖區(qū)結(jié)構(gòu)

Fig. 3 Temporary buffer structure

傳輸機(jī)制為數(shù)據(jù)源周期向接入系統(tǒng)發(fā)送數(shù)據(jù)包，每個(gè)周期內(nèi)包的序號(hào)唯一。當(dāng)數(shù)據(jù)包到達(dá)接入系統(tǒng)后，系統(tǒng)刪除對(duì)應(yīng)緩沖區(qū)內(nèi)數(shù)字編號(hào)。當(dāng)一個(gè)傳輸周期過后，數(shù)據(jù)源向接入系統(tǒng)發(fā)送一個(gè)傳輸周期結(jié)束標(biāo)識(shí)。然后接入系統(tǒng)檢查對(duì)應(yīng)ID的臨時(shí)緩沖區(qū)，如果緩沖區(qū)為空，則不需重傳；如果緩沖區(qū)不空，則將存在的序號(hào)發(fā)送給數(shù)據(jù)源，數(shù)據(jù)源重新發(fā)送對(duì)應(yīng)序號(hào)的數(shù)據(jù)包。反復(fù)執(zhí)行以上步驟直到數(shù)據(jù)包全部到達(dá)。

2.2 數(shù)據(jù)傳輸分析

假設(shè)向系統(tǒng)傳輸數(shù)據(jù)的數(shù)據(jù)源的網(wǎng)絡(luò)丟包率為1-p，數(shù)據(jù)源需要傳送n個(gè)數(shù)據(jù)包，那么對(duì)于成功傳送第i個(gè)數(shù)據(jù)包的概率pi為：

pi=(1-p)k×p

(1)

假設(shè)數(shù)據(jù)源一次傳送一個(gè)數(shù)據(jù)包耗時(shí)為t，那么成功傳送第i個(gè)數(shù)據(jù)包耗時(shí)的期望值E(ti)為：

E(ti)=t×p+t×p×(1-p)+…+t×p×(1-p)k-1

(2)

即：

E(ti)=t×(1-(1-p)k)

(3)

其中，k為第i個(gè)數(shù)據(jù)包發(fā)送次數(shù)。由此可得數(shù)據(jù)源傳送n個(gè)數(shù)據(jù)包的總耗時(shí)期望值E(T)為：

(4)

從式(4)中，容易看出，系統(tǒng)的接收效率與網(wǎng)絡(luò)環(huán)境有關(guān)：網(wǎng)絡(luò)環(huán)境越好，系統(tǒng)的接收能力越強(qiáng)；反之，系統(tǒng)的接收能力下降。

3 負(fù)載平衡策略

結(jié)合已有的經(jīng)典負(fù)載平衡模型，本文提出了混合式負(fù)載平衡策略。如圖4所示，算法建立的模型分為三層，分別是任務(wù)分配層、負(fù)載控制層和資源層。

圖4 負(fù)載平衡模型的結(jié)構(gòu)

3.1 任務(wù)分配層

為了確保任務(wù)分配層的可靠性，該層中每個(gè)任務(wù)分配節(jié)點(diǎn)對(duì)等，同時(shí)進(jìn)行任務(wù)接收、分配和控制節(jié)點(diǎn)的負(fù)載信息的收集，每個(gè)節(jié)點(diǎn)互為備份。這樣設(shè)計(jì)的好處是既可以增強(qiáng)該層的魯棒性，又可以防止任務(wù)層成為系統(tǒng)的瓶頸，便于任務(wù)層的橫向擴(kuò)展。

任務(wù)分配節(jié)點(diǎn)接收到任務(wù)請(qǐng)求時(shí)，如果節(jié)點(diǎn)過于繁忙則拒絕服務(wù)。請(qǐng)求將以退避算法向剩余節(jié)點(diǎn)發(fā)出請(qǐng)求。當(dāng)任務(wù)分配節(jié)點(diǎn)接收任務(wù)后，根據(jù)控制節(jié)點(diǎn)的負(fù)載情況，隨機(jī)地轉(zhuǎn)發(fā)給負(fù)載較低的控制節(jié)點(diǎn)?？刂乒?jié)點(diǎn)接收到任務(wù)的概率與其負(fù)載程度成反比，即節(jié)點(diǎn)負(fù)載越重接收到任務(wù)的概率越低。

任務(wù)分配節(jié)點(diǎn)負(fù)責(zé)分配任務(wù)的同時(shí)，還需要負(fù)載控制節(jié)點(diǎn)的負(fù)載平衡。如果發(fā)生過載，則通知任務(wù)負(fù)載過重的節(jié)點(diǎn)進(jìn)行負(fù)載遷移，一個(gè)負(fù)載周期內(nèi)節(jié)點(diǎn)只執(zhí)行一次負(fù)載遷移指令。任務(wù)遷出的策略是以資源節(jié)點(diǎn)為單位進(jìn)行遷移，遷出任務(wù)最重的節(jié)點(diǎn)，這樣可以快速降低負(fù)載率。遷入的對(duì)象為負(fù)載較輕的控制節(jié)點(diǎn)。這類控制節(jié)點(diǎn)接收到資源節(jié)點(diǎn)的概率與其負(fù)載成反比，即負(fù)載越輕接收到資源節(jié)點(diǎn)的概率越大。

3.2 控制層

負(fù)載控制層由m個(gè)控制節(jié)點(diǎn)組成。節(jié)點(diǎn)之間工作相互獨(dú)立，互不干擾。每個(gè)節(jié)點(diǎn)連接n個(gè)資源節(jié)點(diǎn)，形成一個(gè)小的局域網(wǎng)，在局域網(wǎng)內(nèi)使用集中式負(fù)載平衡進(jìn)行管理?？刂乒?jié)點(diǎn)的可靠性由資源節(jié)點(diǎn)提供。如果控制節(jié)點(diǎn)宕機(jī)，那么將從這n個(gè)資源節(jié)點(diǎn)中，選擇一個(gè)新的節(jié)點(diǎn)作為控制節(jié)點(diǎn)，同時(shí)該節(jié)點(diǎn)的所有任務(wù)全部遷出到剩下的n-1個(gè)節(jié)點(diǎn)。通過這種方式，負(fù)載控制層可以不需要對(duì)控制節(jié)點(diǎn)進(jìn)行備份，實(shí)現(xiàn)節(jié)點(diǎn)角色的動(dòng)態(tài)變更，節(jié)約系統(tǒng)資源。

控制節(jié)點(diǎn)接收到任務(wù)后，根據(jù)資源節(jié)點(diǎn)的負(fù)載信息隨機(jī)分配任務(wù)到負(fù)載較輕的資源節(jié)點(diǎn)。資源節(jié)點(diǎn)接收到任務(wù)的概率也是與其負(fù)載程度成反比，即節(jié)點(diǎn)負(fù)載越重接收到的任務(wù)概率越低。

控制節(jié)點(diǎn)在其局域網(wǎng)內(nèi)作為中心控制節(jié)點(diǎn)。如果發(fā)生過載，則其通知任務(wù)負(fù)載過重的資源節(jié)點(diǎn)進(jìn)行負(fù)載遷移。遷移策略是以數(shù)據(jù)源為單位，遷出執(zhí)行通信最少的數(shù)據(jù)源。采用隨機(jī)方式，將任務(wù)遷移到負(fù)載相對(duì)較輕的一些節(jié)點(diǎn)。資源節(jié)點(diǎn)接收到任務(wù)的概率與其負(fù)載成反比，即負(fù)載越輕接收到任務(wù)的概率越大。遷出通信最少的數(shù)據(jù)源是防止系統(tǒng)做過多重復(fù)性工作，同時(shí)減少任務(wù)遷移帶來的網(wǎng)絡(luò)通信。

3.3 資源層

資源層是系統(tǒng)的資源真正提供者。這里的資源不包含存儲(chǔ)之類的持久化資源。持久化資源被使用頻率低，且必須通過冗余備份來保證其可靠性。文獻(xiàn)[13-14]中對(duì)這方面的介紹相當(dāng)全面，目前對(duì)于這方面的研究已經(jīng)相當(dāng)成熟，本文將不再作進(jìn)一步討論，因此本文討論的資源泛指中央處理器(Central Processing Unit， CPU)計(jì)算資源、內(nèi)存資源和通信資源等。資源的可靠性只通過設(shè)備的可靠性保證。因?yàn)槭褂眠@類資源的任務(wù)比較多且工作量巨大，通過備份實(shí)現(xiàn)可靠性不現(xiàn)實(shí)，因此，目前文獻(xiàn)[4，6，9]中都是通過設(shè)備的可靠性來保證資源的可靠性。如果資源節(jié)點(diǎn)失效，那么資源使用方則需要重新發(fā)送任務(wù)給任務(wù)分配節(jié)點(diǎn)請(qǐng)求資源。

3.4 負(fù)載遷移執(zhí)行過程

整個(gè)系統(tǒng)執(zhí)行負(fù)載平衡步驟如下。

步驟1 任務(wù)分配節(jié)點(diǎn)接收到來自數(shù)據(jù)源發(fā)送的接入請(qǐng)求。如果任務(wù)分配節(jié)點(diǎn)負(fù)載過重，則放棄服務(wù)，數(shù)據(jù)源使用退避算法再次申請(qǐng)；反之，任務(wù)節(jié)點(diǎn)根據(jù)控制節(jié)點(diǎn)負(fù)載信息，隨機(jī)將接入請(qǐng)求轉(zhuǎn)發(fā)給控制節(jié)點(diǎn)。控制節(jié)點(diǎn)接收到接入請(qǐng)求的概率與其負(fù)載程度成反比。接著執(zhí)行步驟2。

步驟2 控制節(jié)點(diǎn)接收到接入請(qǐng)求。根據(jù)資源節(jié)點(diǎn)的負(fù)載信息，隨機(jī)選中一個(gè)資源節(jié)點(diǎn)負(fù)責(zé)接收數(shù)據(jù)源數(shù)據(jù)，資源節(jié)點(diǎn)被選中概率與其負(fù)載程度成反比。接著執(zhí)行步驟3。

步驟3 資源節(jié)點(diǎn)與數(shù)據(jù)源通信。資源節(jié)點(diǎn)定期計(jì)算自身負(fù)載值；如果超過警戒值，則立刻給控制節(jié)點(diǎn)發(fā)送過載警告，執(zhí)行步驟4。

步驟4 控制節(jié)點(diǎn)接收到資源節(jié)點(diǎn)的負(fù)載過載信息后，計(jì)算自身負(fù)載值：如果超過警戒值，則通知任務(wù)分配層進(jìn)行控制層負(fù)載平衡；反之則通知局域網(wǎng)內(nèi)資源節(jié)點(diǎn)進(jìn)行負(fù)載遷移。

3.5 負(fù)載分析

負(fù)載平衡的本質(zhì)是提高整體系統(tǒng)資源利用率，平衡系統(tǒng)資源使用，使系統(tǒng)整體響應(yīng)時(shí)間最短、數(shù)據(jù)吞吐量最大。系統(tǒng)整體響應(yīng)時(shí)間和吞吐量一般與節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬、CPU計(jì)算資源內(nèi)存大小等相關(guān)；此外數(shù)據(jù)包丟失率能直接體現(xiàn)當(dāng)前系統(tǒng)接收負(fù)載狀況，因此本文給出衡量資源節(jié)點(diǎn)的負(fù)載公式如式(5)所示：

(5)

由式(5)，可計(jì)算出每個(gè)控制節(jié)點(diǎn)的局域網(wǎng)內(nèi)的負(fù)載總和：

(6)

在式(6)中，n表示控制節(jié)點(diǎn)所連接的資源節(jié)點(diǎn)個(gè)數(shù)。Li表示第i個(gè)控制節(jié)點(diǎn)所在局域網(wǎng)內(nèi)負(fù)載總和。因?yàn)槊總€(gè)控制節(jié)點(diǎn)連接的資源節(jié)點(diǎn)個(gè)數(shù)不同，所以本文使用總體負(fù)載的平均值來衡量控制節(jié)點(diǎn)所連接的局域網(wǎng)內(nèi)負(fù)載情況，則有：

(7)

本文使用標(biāo)準(zhǔn)差來衡量每個(gè)局域網(wǎng)內(nèi)負(fù)載平衡性，則有：

(8)

當(dāng)SDi值超過負(fù)載平衡閾值φ時(shí)，則觸發(fā)資源節(jié)點(diǎn)的負(fù)載平衡。

(9)

那么，在這k個(gè)節(jié)點(diǎn)中第j個(gè)節(jié)點(diǎn)應(yīng)該被分配任務(wù)的概率為：

(10)

控制節(jié)點(diǎn)的負(fù)載計(jì)算分為兩部分：第一部分為節(jié)點(diǎn)本身的網(wǎng)絡(luò)帶寬、CPU計(jì)算資源和內(nèi)存資源的消耗；第二部分為節(jié)點(diǎn)負(fù)責(zé)的局域網(wǎng)內(nèi)資源節(jié)點(diǎn)負(fù)載的平均水平。

每個(gè)控制節(jié)點(diǎn)的局域網(wǎng)內(nèi)的負(fù)載水平并不能體現(xiàn)整個(gè)系統(tǒng)的負(fù)載狀況，為了實(shí)現(xiàn)全局負(fù)載平衡，必須把局域網(wǎng)內(nèi)的負(fù)載水平體現(xiàn)在控制節(jié)點(diǎn)的負(fù)載信息上。這樣可以通過控制節(jié)點(diǎn)的負(fù)載平衡，來實(shí)現(xiàn)全局負(fù)載平衡。控制節(jié)點(diǎn)的負(fù)載為：

CLi=α′×Nru/Nr+β′×Cru/Cr+γ′×Mru/Mr+

θ×averag(Li)

(11)

其中：CLi表示第i個(gè)控制節(jié)點(diǎn)的負(fù)載值；α′+β′+γ′+θ=1且1>α′>0，1>β′>0，1>γ′>0，1>θ>0，α′、β′、γ′分別表示網(wǎng)絡(luò)帶寬、CPU計(jì)算資源和內(nèi)存資源在系統(tǒng)資源中的權(quán)重；θ表示局域網(wǎng)內(nèi)平均負(fù)載相對(duì)于控制節(jié)點(diǎn)負(fù)載的比重。

因此，系統(tǒng)中m個(gè)控制節(jié)點(diǎn)的整體負(fù)載為：

(12)

進(jìn)而，易得控制節(jié)點(diǎn)的平均負(fù)載值為：

(13)

最終，控制節(jié)點(diǎn)負(fù)載方差為：

(14)

當(dāng)SDCL的值負(fù)載平衡閾值大于φ′時(shí)，控制節(jié)點(diǎn)通知任務(wù)分配節(jié)點(diǎn)其負(fù)載過載，然后任務(wù)分配節(jié)點(diǎn)通知控制節(jié)點(diǎn)進(jìn)行任務(wù)遷移。

同CPU計(jì)算資源節(jié)點(diǎn)在局域網(wǎng)絡(luò)獲得任務(wù)的概率計(jì)算方式一樣，假設(shè)系統(tǒng)中有m個(gè)節(jié)點(diǎn)，選定k′個(gè)節(jié)點(diǎn)作為任務(wù)分配節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的負(fù)載為CLi，0

(15)

(16)

4 實(shí)驗(yàn)結(jié)果及分析

本文在3個(gè)計(jì)算機(jī)集群上進(jìn)行模擬實(shí)驗(yàn)，分別是：1)發(fā)送集群。由8臺(tái)計(jì)算機(jī)組成，用來模擬數(shù)據(jù)源向服務(wù)平臺(tái)發(fā)送數(shù)據(jù)。2)接收集群。由4臺(tái)計(jì)算機(jī)組成，用來模擬服務(wù)平臺(tái)，負(fù)責(zé)接收、處理和轉(zhuǎn)發(fā)存儲(chǔ)數(shù)據(jù)。3)存儲(chǔ)集群。由10臺(tái)計(jì)算組成，用來作數(shù)據(jù)的存儲(chǔ)。為了簡化實(shí)驗(yàn)，本文按照如表1參數(shù)進(jìn)行實(shí)驗(yàn)。

表1 系統(tǒng)參數(shù)

實(shí)驗(yàn)分析如下所示。

實(shí)驗(yàn)數(shù)據(jù)包大小分為3種：125 B、175 B與200 B。本文接收系統(tǒng)在不同接收速度下，采用多次仿真取平均值的方法，通過丟包率，重傳包數(shù)量、接收與處理延時(shí)、處理與存儲(chǔ)延遲和負(fù)載耗時(shí)來衡量接入系統(tǒng)和負(fù)載平衡算法的性能。

圖5～6為丟包率和重傳包數(shù)量隨接收速度變化趨勢(shì)。

圖5 不同接收速度下的丟包率

從圖5～6中可以看出，系統(tǒng)在接收速度小于50萬packet/s時(shí)，系統(tǒng)丟包率和重傳數(shù)量為0。隨著接收速度的增加，系統(tǒng)的丟包率開始增加。為了保證通信可靠，重傳包數(shù)迅速增加。這是因?yàn)榻邮账俣仁軘?shù)據(jù)源發(fā)送速度影響，當(dāng)數(shù)據(jù)源發(fā)送數(shù)據(jù)包速度過快時(shí)，網(wǎng)絡(luò)出現(xiàn)擁塞。從圖5～6中可看出，網(wǎng)絡(luò)狀況很好的情況下，系統(tǒng)有很好的接收能力。從圖中還可以看出，不同大小的數(shù)據(jù)包對(duì)接收系統(tǒng)也有一定影響，這是因?yàn)榻邮账俣纫欢〞r(shí)，數(shù)據(jù)包越大，網(wǎng)絡(luò)帶寬被占用越多。從這一方面，也可以證明系統(tǒng)接收能力受網(wǎng)絡(luò)狀況影響。

圖6 不同接收速度下的重傳數(shù)據(jù)包數(shù)

圖7與圖8描述的是系統(tǒng)各個(gè)處理層之間的處理延時(shí)情況。從圖7中，可以看出隨著接收速度的增加，接收到的數(shù)據(jù)包和處理之間的延時(shí)增加。這是由于處理速度最大值小于接收速度最大值，當(dāng)接收速度高于處理速度時(shí)，數(shù)據(jù)包會(huì)累積在緩沖區(qū)內(nèi)，導(dǎo)致處理延時(shí)的增加。從圖8中，可以看出隨著接收速度增加，處理延時(shí)和存儲(chǔ)延時(shí)反而減小。這是因?yàn)楸疚臑榱颂岣叽鎯?chǔ)效率，對(duì)存儲(chǔ)進(jìn)行了優(yōu)化。為了減少存取層訪問數(shù)據(jù)庫的次數(shù)，只有數(shù)據(jù)在緩沖區(qū)內(nèi)過期或者待存儲(chǔ)的數(shù)據(jù)過多時(shí)，存取層才訪問數(shù)據(jù)庫，因此，當(dāng)接收速度增加時(shí)，處理速度也被迫增加，數(shù)據(jù)緩沖區(qū)內(nèi)待存儲(chǔ)的數(shù)據(jù)快速累積，導(dǎo)致觸發(fā)存儲(chǔ)次數(shù)增加，因此處理與存儲(chǔ)延時(shí)變小。從兩幅圖中可以看出，數(shù)據(jù)包越大，處理和存儲(chǔ)延時(shí)相對(duì)越大。這是因?yàn)閿?shù)據(jù)包大導(dǎo)致處理速度變慢，所以觸發(fā)存儲(chǔ)次數(shù)相對(duì)較少。

圖7 接收與處理延時(shí)

圖8 處理與存儲(chǔ)延時(shí)

為了觸發(fā)負(fù)載平衡，實(shí)驗(yàn)開始時(shí)，先向分布式并發(fā)系統(tǒng)中單臺(tái)機(jī)器發(fā)送數(shù)據(jù)，這樣可以快速觸發(fā)系統(tǒng)的負(fù)載平衡，以此來觀測(cè)系統(tǒng)負(fù)載平衡速度。實(shí)驗(yàn)分別模擬26萬、34萬、42萬、50萬、58萬、66萬、74萬和82萬個(gè)數(shù)據(jù)源分別向系統(tǒng)發(fā)送數(shù)據(jù)包時(shí)系統(tǒng)的負(fù)載平衡耗時(shí)情況。

從圖9中可以看出，系統(tǒng)的負(fù)載耗時(shí)隨負(fù)載壓力的增大而增大；負(fù)載壓力越大，負(fù)載平衡耗時(shí)增加越快。這是因?yàn)樨?fù)載壓力越大，網(wǎng)絡(luò)資源消耗越大，那么負(fù)載的耗時(shí)也就會(huì)越長。從圖9中還可以看出，不同大小的通信數(shù)據(jù)包導(dǎo)致的負(fù)載耗時(shí)也不相同。這是因?yàn)榘l(fā)送數(shù)據(jù)包的速度一定，那么數(shù)據(jù)包越大，占用的網(wǎng)絡(luò)帶寬越大，導(dǎo)致系統(tǒng)通信延遲增加，進(jìn)而導(dǎo)致系統(tǒng)負(fù)載耗時(shí)的增加。

圖9 負(fù)載平衡耗時(shí)

5 結(jié)語

隨著網(wǎng)絡(luò)數(shù)據(jù)的快速增長，分布式系統(tǒng)應(yīng)用越來越廣。為了提高分布式系統(tǒng)的數(shù)據(jù)接入能力，有必要對(duì)負(fù)載平衡遺留問題作進(jìn)一步研究。本文在已有的負(fù)載平衡模型的基礎(chǔ)上，提出了混合式負(fù)載遷移平衡算法。實(shí)驗(yàn)表明，基于該負(fù)載平衡策略的系統(tǒng)能在很短時(shí)間內(nèi)完成負(fù)載平衡任務(wù)，任務(wù)響應(yīng)迅速，且節(jié)點(diǎn)具有自適應(yīng)性。

本文算法也存在局限性和不足，還需在真實(shí)環(huán)境進(jìn)行檢驗(yàn)。本文算法考慮的資源問題只關(guān)注節(jié)點(diǎn)自身，沒有考慮多個(gè)節(jié)點(diǎn)協(xié)同工作情況下負(fù)載平衡的實(shí)現(xiàn)方式。這是目前負(fù)載平衡研究的一個(gè)難題，日后也將該問題作為主要的研究方向。

References)

[1] 廖鋒,成靜靜.大數(shù)據(jù)環(huán)境下Hadoop分布式系統(tǒng)的研究與設(shè)計(jì)[J].廣東通信技術(shù),2013(10):22-27.(LIAO F, CHENG J J. Research and design of Hadoop distributed system under big data environment [J]. Guangdong Communication Technology, 2013(10): 22-27.)

[2] HASHEM I A T, YAQOOB I, ANUAR N B, et al. The rise of “big data” on cloud computing: review and open research issues [J]. Information Systems, 2015, 47: 98-115.

[3] 房俊華,王曉桐,張蓉,等.分布式數(shù)據(jù)流上的高性能分發(fā)策略[J].軟件學(xué)報(bào),2017,28(3):563-578.(FANG J H, WANG X T, ZHANG R, et al. A high performance distribution policy on distributed data streams [J]. Journal of Software, 2017, 28(3): 563-578.)

[4] JIANG Y, ZHOU Y, WANG W. Task allocation for undependable multiagent systems in social networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(8): 1671-1681.

[5] PENMATSA S, CHRONOPOULOS A T. Game-theoretic static load balancing for distributed systems [J]. Journal of Parallel and Distributed Computing, 2011, 71(4): 537-555.

[6] TONG Z, XIAO Z, LI K, et al. Proactive scheduling in distributed computing—A reinforcement learning approach [J]. Journal of Parallel and Distributed Computing, 2014, 74(7): 2662-2672.

[7] JIANG Y. A survey of task allocation and load balancing in distributed systems [J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(2): 585-599.

[8] VAN DER HORST J, NOBLE J. Distributed and centralized task allocation: when and where to use them [C]// SASOW 2010: Proceedings of the 2010 Fourth IEEE International Conference on Self-Adaptive and Self-Organizing Systems Workshop. Piscataway, NJ: IEEE, 2010: 1-8.

[9] IZAKIAN H, ABRAHAM A, LADANI B T. An auction method for resource allocation in computational grids [J]. Future Generation Computer Systems, 2010, 26(2): 228-235.

[10] WANG W, JIANG Y. Community-aware task allocation for social networked multiagent systems [J]. IEEE Transactions on Cybernetics, 2014, 44(9): 1529-1543.

[11] DI S, WANG C L. Decentralized proactive resource allocation for maximizing throughput of P2P grid [J]. Journal of Parallel and Distributed Computing, 2012, 72(2): 308-321.

[12] GARG S K, VENUGOPAL S, BROBERG J, et al. Double auction-inspired meta-scheduling of parallel applications on global grids [J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 450-464.

[13] DUONG-BA T, NGUYEN T, BOSE B, et al. Distributed client-server assignment for online social network applications [J]. IEEE Transactions on Emerging Topics in Computing, 2014, 2(4): 422-435.

[14] FARAGARDI H R, SHOJAEE R, KESHTKAR M A, et al. Optimal task allocation for maximizing reliability in distributed real-time systems [C]// ICIS 2013: Proceedings of the 2013 IEEE/ACIS 12th International Conference on Computer and Information Science. Piscataway, NJ: IEEE, 2013: 513-519.

[15] DUSSO P M, SAUER C, HRDER T. Optimizing sort in Hadoop using replacement selection [C]// Proceedings of the 2015 East European Conference on Advances in Databases and Information Systems. Berlin: Springer, 2015: 365-379.

[16] KOTA R, GIBBINS N, JENNINGS N R. Decentralized approaches for self-adaptation in Agent organizations [J]. ACM Transactions on Autonomous and Adaptive Systems, 2012, 7(1): 1-28.

[17] AN B, LESSER V, SIM K M. Strategic Agents for multi-resource negotiation [J]. Autonomous Agents and Multi-Agent Systems, 2011, 23(1): 114-153.

[18] CARPIO F, ENGELMANN A, JUKAN A. DiffFlow: differentiating short and long flows for load balancing in data center networks [C]// GLOBECOM 2016: Proceedings of the 2016 IEEE Global Communications Conference. Piscataway, NJ: IEEE, 2016: 1-6.

[19] JIANG Y, HUANG Z. The rich get richer: Preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 2012, 42(5): 1040-1052.

[20] EUGSTER P, KOGAN K, NIKOLENKO S I, et al. Heterogeneous packet processing in shared memory buffers [J]. Journal of Parallel & Distributed Computing, 2016, 99(8): 1-13.

[21] WANG T, SU Z, XIA Y, et al. Rethinking the data center networking: architecture, network protocols, and resource sharing [J]. IEEE Access, 2014, 2(7): 1481-1496.

This work is partially supported by the National Natural Science Foundation of China (60970012, 61572325), Shanghai Key Science and Technology Project (14511107902, 16DZ1203603), Shanghai Engineering Research Center Construction Project (GCZX14014), Shanghai Leading Academic Discipline Project (XTKX2012).

ZHOUYue, born in 1991, M. S. candidate. His research interests include distributed computing, Internet of things.

CHENQingkui, born in 1966, Ph. D., professor. His research interests include network computing, parallel computing, Internet of things.