面向大規模數據接入系統的負載平衡機制

周 岳，陳慶奎

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

0 引言

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

文獻[3]指出，由于分布式系統內存在任務的多樣性和各節點性能的差異性，導致集群內存在負載不平衡現象。負載的不平衡性導致分布式系統無法充分發揮其并行處理的性能。如果負載差異過大，還會進一步導致系統的處理速度下降、網絡延遲增加、任務的響應速度下降等。

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

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

1 相關工作

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

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

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

圖1 3種控制模式結構

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

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

2 接入系統模型

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

圖2 接入系統結構

2.1 數據接收層

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

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

圖3 臨時緩沖區結構

Fig. 3 Temporary buffer structure

傳輸機制為數據源周期向接入系統發送數據包，每個周期內包的序號唯一。當數據包到達接入系統后，系統刪除對應緩沖區內數字編號。當一個傳輸周期過后，數據源向接入系統發送一個傳輸周期結束標識。然后接入系統檢查對應ID的臨時緩沖區，如果緩沖區為空，則不需重傳；如果緩沖區不空，則將存在的序號發送給數據源，數據源重新發送對應序號的數據包。反復執行以上步驟直到數據包全部到達。

2.2 數據傳輸分析

假設向系統傳輸數據的數據源的網絡丟包率為1-p，數據源需要傳送n個數據包，那么對于成功傳送第i個數據包的概率pi為：

pi=(1-p)k×p

(1)

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

(4)

從式(4)中，容易看出，系統的接收效率與網絡環境有關：網絡環境越好，系統的接收能力越強；反之，系統的接收能力下降。

3 負載平衡策略

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

圖4 負載平衡模型的結構

3.1 任務分配層

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

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

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

3.2 控制層

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

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

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

3.3 資源層

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

3.4 負載遷移執行過程

整個系統執行負載平衡步驟如下。

步驟1 任務分配節點接收到來自數據源發送的接入請求。如果任務分配節點負載過重，則放棄服務，數據源使用退避算法再次申請；反之，任務節點根據控制節點負載信息，隨機將接入請求轉發給控制節點。控制節點接收到接入請求的概率與其負載程度成反比。接著執行步驟2。

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

步驟3 資源節點與數據源通信。資源節點定期計算自身負載值；如果超過警戒值，則立刻給控制節點發送過載警告，執行步驟4。

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

3.5 負載分析

負載平衡的本質是提高整體系統資源利用率，平衡系統資源使用，使系統整體響應時間最短、數據吞吐量最大。系統整體響應時間和吞吐量一般與節點的網絡帶寬、CPU計算資源內存大小等相關；此外數據包丟失率能直接體現當前系統接收負載狀況，因此本文給出衡量資源節點的負載公式如式(5)所示：

(5)

由式(5)，可計算出每個控制節點的局域網內的負載總和：

(6)

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

(7)

本文使用標準差來衡量每個局域網內負載平衡性，則有：

(8)

當SDi值超過負載平衡閾值φ時，則觸發資源節點的負載平衡。

(9)

那么，在這k個節點中第j個節點應該被分配任務的概率為：

(10)

控制節點的負載計算分為兩部分：第一部分為節點本身的網絡帶寬、CPU計算資源和內存資源的消耗；第二部分為節點負責的局域網內資源節點負載的平均水平。

每個控制節點的局域網內的負載水平并不能體現整個系統的負載狀況，為了實現全局負載平衡，必須把局域網內的負載水平體現在控制節點的負載信息上。這樣可以通過控制節點的負載平衡，來實現全局負載平衡。控制節點的負載為：

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

θ×averag(Li)

(11)

其中：CLi表示第i個控制節點的負載值；α′+β′+γ′+θ=1且1>α′>0，1>β′>0，1>γ′>0，1>θ>0，α′、β′、γ′分別表示網絡帶寬、CPU計算資源和內存資源在系統資源中的權重；θ表示局域網內平均負載相對于控制節點負載的比重。

因此，系統中m個控制節點的整體負載為：

(12)

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

(13)

最終，控制節點負載方差為：

(14)

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

同CPU計算資源節點在局域網絡獲得任務的概率計算方式一樣，假設系統中有m個節點，選定k′個節點作為任務分配節點，每個節點的負載為CLi，0

(15)

(16)

4 實驗結果及分析

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

表1 系統參數

實驗分析如下所示。

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

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

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

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

圖6 不同接收速度下的重傳數據包數

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

圖7 接收與處理延時

圖8 處理與存儲延時

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

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

圖9 負載平衡耗時

5 結語

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

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

References)

[1] 廖鋒,成靜靜.大數據環境下Hadoop分布式系統的研究與設計[J].廣東通信技術,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] 房俊華,王曉桐,張蓉,等.分布式數據流上的高性能分發策略[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.