周 岳，陳慶奎

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig. 3 Temporary buffer structure

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

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

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

pi=(1-p)k×p

(1)

假設(shè)數(shù)據(jù)源一次傳送一個數(shù)據(jù)包耗時為t，那么成功傳送第i個數(shù)據(jù)包耗時的期望值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個數(shù)據(jù)包發(fā)送次數(shù)。由此可得數(shù)據(jù)源傳送n個數(shù)據(jù)包的總耗時期望值E(T)為：

(4)

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

3 負載平衡策略

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

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

3.1 任務(wù)分配層

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

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

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

3.2 控制層

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

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

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

3.3 資源層

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

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

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

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

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

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

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

3.5 負載分析

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

(5)

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

(6)

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

(7)

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

(8)

當SDi值超過負載平衡閾值φ時，則觸發(fā)資源節(jié)點的負載平衡。

(9)

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

(10)

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

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

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

θ×averag(Li)

(11)

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

因此，系統(tǒng)中m個控制節(jié)點的整體負載為：

(12)

進而，易得控制節(jié)點的平均負載值為：

(13)

最終，控制節(jié)點負載方差為：

(14)

當SDCL的值負載平衡閾值大于φ′時，控制節(jié)點通知任務(wù)分配節(jié)點其負載過載，然后任務(wù)分配節(jié)點通知控制節(jié)點進行任務(wù)遷移。

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

(15)

(16)

4 實驗結(jié)果及分析

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

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

實驗分析如下所示。

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

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

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

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

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

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

圖7 接收與處理延時

圖8 處理與存儲延時

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

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

圖9 負載平衡耗時

5 結(jié)語

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

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

References)

[1] 廖鋒,成靜靜.大數(shù)據(jù)環(huán)境下Hadoop分布式系統(tǒng)的研究與設(shè)計[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].軟件學報,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.