一種面向多類型服務(wù)的動(dòng)態(tài)負(fù)載均衡算法

李國(guó)+申亞坤+李永華++曲文麗

摘 要： 針對(duì)航空物流ILink數(shù)據(jù)平臺(tái)交易復(fù)雜性高、服務(wù)種類多、業(yè)務(wù)規(guī)模大等特點(diǎn)，提出一種面向多類型服務(wù)的動(dòng)態(tài)負(fù)載均衡算法。通過(guò)分析四種基本服務(wù)類型以及實(shí)時(shí)采集四種服務(wù)類型的資源消耗，根據(jù)用戶服務(wù)請(qǐng)求類型的不同動(dòng)態(tài)調(diào)整各服務(wù)器的負(fù)載，引入了過(guò)載服務(wù)器節(jié)點(diǎn)緩沖機(jī)制緩沖負(fù)載過(guò)重節(jié)點(diǎn)，有效解決了航空物流ILink數(shù)據(jù)平臺(tái)可能出現(xiàn)的用戶等待時(shí)間過(guò)長(zhǎng)、局部負(fù)載過(guò)重、甚至個(gè)別服務(wù)器節(jié)點(diǎn)崩潰的問(wèn)題，達(dá)到了集群的負(fù)載均衡。仿真實(shí)驗(yàn)結(jié)果表明，提出的算法在系統(tǒng)吞吐量、系統(tǒng)響應(yīng)時(shí)間、負(fù)載率等關(guān)鍵指標(biāo)上優(yōu)于經(jīng)典的比率算法和遺傳算法。

關(guān)鍵詞： ILink平臺(tái)； 動(dòng)態(tài)負(fù)載均衡算法； 多類型服務(wù)； 緩沖機(jī)制

中圖分類號(hào)： TN911?34； TP302 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）12?0128?04

Abstract： A dynamic load balancing algorithm for multi?type services is proposed to suit aviation logistics ILink data platform to complex transaction， multi?type service and large?scale business. The four fundamental service types were analyzed and resource consumption of the four service types was acquired in real time. The algorithm can update the load balance weight of every service according to the types of users′ service requests. A node buffer mechanism for overload servers was imported to solve the problems of long time waiting of users， over?heavy local load and even the breakdown of individual server node possibly appearing on the aviation logistics ILink data platform， so as to achieve the load balancing. The simulation results show that the algorithm is superior to the classic ratio algorithm and genetic algorithm in system throughout， responding time and load efficiency.

Keywords： ILink platform； dynamic load balancing algorithm； multi?type service； buffering mechanism

航空物流是一種高效的現(xiàn)代化運(yùn)輸方式，我國(guó)航空物流運(yùn)輸周轉(zhuǎn)量逐年增加，已經(jīng)成為現(xiàn)代最重要的運(yùn)輸方式之一。如何高效地處理海量航空物流數(shù)據(jù)訪問(wèn)請(qǐng)求是當(dāng)前亟待解決的問(wèn)題。目前采用軟件負(fù)載均衡是解決該問(wèn)題的方案之一，但是由于服務(wù)器性能不同，必須依賴有效的負(fù)載均衡算法，將大量的并發(fā)訪問(wèn)合理轉(zhuǎn)發(fā)到多個(gè)節(jié)點(diǎn)分別進(jìn)行處理，各服務(wù)器比較均衡地承擔(dān)任務(wù)，進(jìn)而提高集群系統(tǒng)的處理能力和服務(wù)質(zhì)量，縮短用戶響應(yīng)時(shí)間，實(shí)現(xiàn)高效的負(fù)載均衡[1?3]。

1 問(wèn)題描述

航空物流數(shù)據(jù)交換平臺(tái)負(fù)載均衡問(wèn)題是航空物流信息平臺(tái)的關(guān)鍵問(wèn)題。為了讓服務(wù)器集群中多臺(tái)服務(wù)器最大化地分?jǐn)傆脩舻牟l(fā)請(qǐng)求，避免甚至消除集群中的負(fù)載過(guò)重、負(fù)載震蕩等問(wèn)題，國(guó)內(nèi)外學(xué)者相繼提出了多種負(fù)載均衡算法，主要分為兩類：靜態(tài)負(fù)載均衡算法和動(dòng)態(tài)負(fù)載均衡算法。常見(jiàn)的負(fù)載均衡算法如表1所示。

航空物流數(shù)據(jù)交換平臺(tái)調(diào)度模型如圖1所示。在ILink client向數(shù)據(jù)交換平臺(tái)發(fā)送請(qǐng)求以后，請(qǐng)求經(jīng)過(guò)互聯(lián)網(wǎng)首先到達(dá)服務(wù)器集群的虛擬服務(wù)器。虛擬服務(wù)器對(duì)外提供透明的服務(wù)訪問(wèn)，它屏蔽了內(nèi)層物理服務(wù)器的具體細(xì)節(jié)。在虛擬服務(wù)器中，由于用戶服務(wù)請(qǐng)求類型的不同，資源消耗情況差異較大，所以虛擬服務(wù)器會(huì)把用戶請(qǐng)求依據(jù)服務(wù)類型分別加入到相應(yīng)的服務(wù)請(qǐng)求隊(duì)列，隨后用戶請(qǐng)求被緩存到31個(gè)等待就緒隊(duì)列中。負(fù)載控制模塊是負(fù)載均衡機(jī)制的核心，該模塊包括負(fù)載采集、負(fù)載計(jì)算和請(qǐng)求分發(fā)。負(fù)載采集模塊負(fù)責(zé)采集，包括節(jié)點(diǎn)各種類型的服務(wù)CPU占用率、內(nèi)存占用率、磁盤空閑比等；負(fù)載計(jì)算模塊是根據(jù)算法模型，對(duì)采集到的服務(wù)器狀態(tài)信息確定各服務(wù)類型的負(fù)載系數(shù)，進(jìn)而確定服務(wù)器接收用戶請(qǐng)求的概率。負(fù)載分發(fā)模塊功能則是根據(jù)節(jié)點(diǎn)接收用戶請(qǐng)求的概率對(duì)用戶請(qǐng)求進(jìn)行分發(fā)。

在ILink數(shù)據(jù)平臺(tái)上，提供的主要有四種網(wǎng)絡(luò)服務(wù)，即CoreService，ConfigService，SitaService，SendMsgService，如表2所示。

這四種服務(wù)的功能各不相同資源消耗差異較大，ConfigService主要是根據(jù)數(shù)據(jù)庫(kù)中的信息配置用戶的請(qǐng)求報(bào)文，該操作涉及大量的用戶數(shù)據(jù)保存，需要占用大量的磁盤空間；CoreService是把用戶報(bào)文信息寫入到xml文件或者從xml文件把信息封裝到用戶的報(bào)文中，顯然該服務(wù)類型需要進(jìn)行頻繁的I/O操作；SitaService是為了實(shí)現(xiàn)平臺(tái)的國(guó)際化，將用戶的報(bào)文轉(zhuǎn)化成國(guó)際通用Sita報(bào)文格式，轉(zhuǎn)換過(guò)程涉及大量的格式轉(zhuǎn)換，CPU內(nèi)存消耗較大；SendMsgService則是系統(tǒng)中使用最多的一種網(wǎng)絡(luò)服務(wù)，完成用戶數(shù)據(jù)報(bào)文發(fā)送和轉(zhuǎn)發(fā)的功能，主要消耗計(jì)算機(jī)的帶寬資源。

該問(wèn)題的調(diào)度模型如下：

2 算法設(shè)計(jì)

2.1 ILink平臺(tái)

ILink航空貨運(yùn)數(shù)據(jù)交換平臺(tái)是航空電子貨單信息平臺(tái)的基礎(chǔ)平臺(tái)，通過(guò)建立安全、高效、穩(wěn)定的數(shù)據(jù)傳輸通道，實(shí)現(xiàn)航空物流參與者之間的數(shù)據(jù)交換。ILink平臺(tái)是由多臺(tái)服務(wù)器構(gòu)成的分布式系統(tǒng)，具有高度的系統(tǒng)安全性、可靠的傳輸穩(wěn)定性、支持業(yè)務(wù)報(bào)文轉(zhuǎn)換，支持用戶單點(diǎn)接入和多點(diǎn)接入，支持高并發(fā)的業(yè)務(wù)模型，允許進(jìn)行負(fù)載均衡擴(kuò)展。

2.2 算法設(shè)計(jì)

服務(wù)器集群接收到用戶請(qǐng)求以后，綜合考慮各臺(tái)服務(wù)器性能的差異性以及各種類型的服務(wù)差異性，根據(jù)服務(wù)器的不同服務(wù)類型消耗資源的不同計(jì)算各臺(tái)服務(wù)器分配請(qǐng)求的概率。根據(jù)概率對(duì)收到的用戶請(qǐng)求進(jìn)行分配，由于用戶請(qǐng)求的隨機(jī)性，在服務(wù)器接收服務(wù)的過(guò)程中，可能導(dǎo)致某些服務(wù)器節(jié)點(diǎn)始終處于高負(fù)荷狀態(tài)，此時(shí)，引入過(guò)載緩沖機(jī)制，把負(fù)載過(guò)重節(jié)點(diǎn)加入到過(guò)載隊(duì)列中，避免了部分節(jié)點(diǎn)負(fù)載過(guò)重，有利于服務(wù)器集群的負(fù)載均衡。算法流程如圖2所示。

面向多服務(wù)類型的動(dòng)態(tài)負(fù)載均衡算法流程如下：

（1） 初始化隊(duì)列。算法開(kāi)始，需要對(duì)用戶請(qǐng)求就緒隊(duì)列和服務(wù)器過(guò)載隊(duì)列進(jìn)行初始化。在用戶請(qǐng)求就緒隊(duì)列中存放用戶各種服務(wù)類型的用戶請(qǐng)求，服務(wù)器過(guò)載隊(duì)列則存放后臺(tái)過(guò)載的服務(wù)器節(jié)點(diǎn)。

（2） 更新各服務(wù)類型負(fù)載系數(shù)。四種不同的服務(wù)類型對(duì)服務(wù)器的負(fù)載是不同的，算法根據(jù)收集到的動(dòng)態(tài)確定各個(gè)服務(wù)類型的負(fù)載系數(shù)，越大，說(shuō)明當(dāng)前j類型的服務(wù)對(duì)服務(wù)器的負(fù)擔(dān)越重。

（3） 計(jì)算服務(wù)器節(jié)點(diǎn)的負(fù)載。通過(guò)收集到的后臺(tái)各服務(wù)器的狀態(tài)信息，綜合考慮服務(wù)器操作系統(tǒng)和其他軟件開(kāi)銷，依據(jù)式（4）計(jì)算服務(wù)器當(dāng)前的負(fù)載狀況。

（4） 檢查節(jié)點(diǎn)是否過(guò)載。對(duì)于服務(wù)器集群中的節(jié)點(diǎn)，在運(yùn)行過(guò)程中，可能有的節(jié)點(diǎn)處于高負(fù)荷狀態(tài)，在算法中，設(shè)定服務(wù)器負(fù)載閾值為0.9，當(dāng)某個(gè)節(jié)點(diǎn)的負(fù)載超過(guò)該閾值以后，就認(rèn)定該節(jié)點(diǎn)處于高負(fù)載狀態(tài)，將該節(jié)點(diǎn)加入過(guò)載隊(duì)列。

（5） 更新過(guò)載隊(duì)列。過(guò)載隊(duì)列保存了處于高負(fù)載狀態(tài)的服務(wù)器節(jié)點(diǎn)，過(guò)載隊(duì)列不接收用戶請(qǐng)求，一段時(shí)間以后，如果過(guò)載隊(duì)列中的節(jié)點(diǎn)負(fù)載低于設(shè)定的最低閾值0.75，則把該節(jié)點(diǎn)移出過(guò)載隊(duì)列，重新接收用戶的請(qǐng)求，繼續(xù)分擔(dān)集群的任務(wù)。

（6） 更新分配概率。后臺(tái)服務(wù)器依據(jù)節(jié)點(diǎn)的負(fù)載狀況進(jìn)行用戶請(qǐng)求的分配，具體來(lái)說(shuō)就是根據(jù)各個(gè)服務(wù)器節(jié)點(diǎn)的給每個(gè)節(jié)點(diǎn)分配一個(gè)相對(duì)應(yīng)的比率，負(fù)載均衡模塊把該比率作為一段時(shí)間內(nèi)收到的用戶請(qǐng)求調(diào)度的依據(jù)。

3 實(shí)驗(yàn)設(shè)計(jì)

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證該動(dòng)態(tài)負(fù)載均衡算法的性能，搭建了一套模擬的ILink環(huán)境。該環(huán)境模擬真實(shí)的生產(chǎn)環(huán)境，由兩臺(tái)Dell服務(wù)器組成，每臺(tái)服務(wù)器上虛擬出四臺(tái)虛擬機(jī)，各個(gè)虛擬機(jī)的配置如下：操作系統(tǒng)為Windows Server 2008 R2 Enterprise，處理器為IntelXeon CPU E5?2665@2.40 GHz，安裝內(nèi)存為4 GB，2 GB，1 GB，512 MB，系統(tǒng)類型為64位操作系統(tǒng)，運(yùn)行環(huán)境為MyEclipse，jdk1.7.0_07。

3.2 實(shí)驗(yàn)過(guò)程

在對(duì)算法進(jìn)行仿真實(shí)驗(yàn)的過(guò)程中，需要分別編寫客戶端程序和服務(wù)端的響應(yīng)程序。首先在服務(wù)器端，配置ILink數(shù)據(jù)交換平臺(tái)中的四種常見(jiàn)服務(wù)即SendMsgService服務(wù)、CoreService服務(wù)、ConfigService服務(wù)和SitaService服務(wù)，具體配置過(guò)程為編寫相應(yīng)服務(wù)的后臺(tái)程序，并對(duì)服務(wù)的配置文件進(jìn)行修改。例如，對(duì)于CoreService服務(wù)，該服務(wù)的主要資源消耗為I/O消耗，所以實(shí)驗(yàn)中對(duì)CoreService的編寫主要是訪問(wèn)后臺(tái)數(shù)據(jù)庫(kù)，對(duì)其進(jìn)行讀寫操作以消耗計(jì)算機(jī)的I/O資源。

對(duì)四種服務(wù)配置完成后，需要模擬生產(chǎn)環(huán)境中真實(shí)的客戶請(qǐng)求，編寫Java的Servlet程序，通過(guò)Tomcat服務(wù)器接收用戶的請(qǐng)求，并在收到請(qǐng)求以后解析請(qǐng)求，然后調(diào)用服務(wù)端的后臺(tái)服務(wù)進(jìn)行相應(yīng)操作。在客戶端，同樣需要借助程序在短時(shí)間內(nèi)分場(chǎng)景產(chǎn)生各種服務(wù)類型的用戶請(qǐng)求，同時(shí)記錄各個(gè)請(qǐng)求的響應(yīng)時(shí)間以及一段時(shí)間內(nèi)該算法的吞吐量。

3.3 實(shí)驗(yàn)場(chǎng)景

在航空物流數(shù)據(jù)交換平臺(tái)上，服務(wù)類型的不同，對(duì)集群的負(fù)載也是不同的。本實(shí)驗(yàn)設(shè)計(jì)了四個(gè)實(shí)驗(yàn)場(chǎng)景，第一個(gè)場(chǎng)景的目的是測(cè)試仿真程序的可靠性，保證用戶能夠獲取到各種類型的服務(wù)。第二個(gè)場(chǎng)景是為了通過(guò)多次實(shí)驗(yàn)獲取一組較優(yōu)的，因?yàn)榈娜≈抵苯佑绊懰惴ǖ男阅芎脡?。第三個(gè)場(chǎng)景是測(cè)試算法在吞吐量這一指標(biāo)上的優(yōu)劣。第四個(gè)場(chǎng)景是測(cè)試算法在負(fù)載率指標(biāo)上的好壞。圖3描述了在100組不同的負(fù)載系數(shù)情況下算法響應(yīng)時(shí)間這一指標(biāo)的優(yōu)劣。用戶請(qǐng)求的分配過(guò)程依賴于的設(shè)置，設(shè)置的好壞直接影響算法的性能。最終本文選定的一組較優(yōu)的為[0.15，0.45，0.27，0.13]。從圖3可以看到在并發(fā)量30以前三種算法的響應(yīng)時(shí)間差別不大，在30以后，響應(yīng)時(shí)間急劇上升，而且本文算法是始終優(yōu)于其他兩種算法的。這是因?yàn)樵谙到y(tǒng)并發(fā)訪問(wèn)量較小的情況下，各類服務(wù)請(qǐng)求相對(duì)來(lái)說(shuō)都很少，這時(shí)比率算法和本文算法區(qū)別不大，遺傳算法搜索能力較強(qiáng)，容易最快找到一組最優(yōu)解。當(dāng)訪問(wèn)量逐漸增大以后，各類服務(wù)請(qǐng)求區(qū)別較大，而比率算法和遺傳算法是忽視這種服務(wù)類型差別的，導(dǎo)致服務(wù)器對(duì)于所有的請(qǐng)求全部接收，一定程度上影響了算法的響應(yīng)時(shí)間，且遺傳算法在并發(fā)量較大的時(shí)候容易陷入“早熟”，這也是遺傳算法在并發(fā)量較大時(shí)比本文算法性能差的一個(gè)原因。

圖4是在實(shí)驗(yàn)場(chǎng)景二確定的基礎(chǔ)上四種服務(wù)類型混雜訪問(wèn)的情況下系統(tǒng)吞吐量指標(biāo)的實(shí)驗(yàn)結(jié)果圖。該實(shí)驗(yàn)接近真實(shí)的用戶訪問(wèn)場(chǎng)景，從吞吐量的角度驗(yàn)證了算法的優(yōu)劣。在圖4中，三種算法在請(qǐng)求訪問(wèn)量不飽和的情況下，系統(tǒng)吞吐量差別不大，所有用戶的所有服務(wù)類型的請(qǐng)求都能得到及時(shí)響應(yīng)。但是隨著系統(tǒng)并發(fā)量的增加，三種算法差距逐漸加大，這是因?yàn)殡S著并發(fā)量的增多，用戶對(duì)各種服務(wù)類型的請(qǐng)求也趨于隨機(jī)化且數(shù)量較大，本文算法能夠依據(jù)服務(wù)類型的不同計(jì)算節(jié)點(diǎn)的負(fù)載，并把負(fù)載超過(guò)閾值的節(jié)點(diǎn)加入過(guò)載隊(duì)列，暫停其提供服務(wù)，避免了服務(wù)器節(jié)點(diǎn)負(fù)載過(guò)大從而用戶請(qǐng)求失敗的概率，增加了系統(tǒng)吞吐量。

圖5通過(guò)負(fù)載均衡率L這一綜合指標(biāo)，衡量了三種算法在服務(wù)器集群上運(yùn)行的效率。在訪問(wèn)量不飽和的情況下，三種算法差別細(xì)微，請(qǐng)求量為30～50時(shí)三種算法在負(fù)載率指標(biāo)上差距加大。在系統(tǒng)請(qǐng)求量超過(guò)50以后，三種算法系統(tǒng)負(fù)載率趨于最大值，對(duì)于比率算法和遺傳算法，負(fù)載率在0.9以上，而本文算法在0.8左右，總體性能較好，后臺(tái)各個(gè)服務(wù)器能夠比較均衡地承擔(dān)用戶請(qǐng)求，這是因?yàn)樗惴ㄔO(shè)定的閾值為0.8，超過(guò)閾值負(fù)載的節(jié)點(diǎn)將加入到過(guò)載隊(duì)列中，等待一段時(shí)間以后繼續(xù)為用戶提供服務(wù)，當(dāng)然，閾值是能夠根據(jù)需要進(jìn)行設(shè)定的。

4 結(jié) 語(yǔ)

本文提出了一種面向多類型服務(wù)的動(dòng)態(tài)負(fù)載均衡算法，該算法能夠根據(jù)服務(wù)器中各個(gè)服務(wù)類型資源消耗的不同，計(jì)算服務(wù)器節(jié)點(diǎn)的負(fù)載，依據(jù)負(fù)載狀況確定的概率來(lái)分配用戶請(qǐng)求，算法能夠在訪問(wèn)量較大的情況下緩沖過(guò)載的節(jié)點(diǎn)，一定程度上提高了系統(tǒng)的吞吐量和降低了集群負(fù)載率。但是本文中各服務(wù)類型對(duì)服務(wù)器的負(fù)載系數(shù)是固定的，是根據(jù)大量隨機(jī)實(shí)驗(yàn)選取的，研究負(fù)載系數(shù)根據(jù)不同的業(yè)務(wù)環(huán)境進(jìn)行自適應(yīng)變化將是下一步的工作重點(diǎn)。

參考文獻(xiàn)

[1] 王榮生，楊際祥，王凡.負(fù)載均衡策略研究綜述[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（8）：1681?1686.

[2] 李新，黎文偉.一種改進(jìn)的動(dòng)態(tài)告警負(fù)載均衡算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（7）：1585?1589.

[3] 鄭貴德，陳明.以云計(jì)算為后臺(tái)的負(fù)載均衡技術(shù)[J].現(xiàn)代電子技術(shù)，2012，35（9）：77?80.

[4] SEMCHEDINE Fouzi， BOUALLOUCHE?MEDJKOUNE Louiza， AISSANI Djamil. Task assignment policies in distributed server systems： A suivey [J]. Journal of network and computer applications， 2011， 34（4）： 1123?1130.

[5] CHOI S Y， LEE S， LEE T， et al. Double?phase polling algorithm based on partitioned ONU subgroups for high utilization in EPONs [J]. Journal of optical communications and networking， 2009， 1（5）： 484?497.

[6] MIRZA Hamid Turab， CHEN Ling， CHEN Gencai. Practicability of dataspace system [J]. JDCTA， 2010， 3（4）： 233?243.

[7] 王鵬，黃焱，李坤，等.云計(jì)算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J].計(jì)算機(jī)研究與發(fā)展，2014，51（5）：1095?1107.

[8] 王強(qiáng)，李雄飛，王婧.云計(jì)算中的數(shù)據(jù)放置與任務(wù)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（11）：2416?2426.

[9] 周瑩蓮，劉甫.服務(wù)器負(fù)載均衡技術(shù)研究[J].計(jì)算機(jī)與數(shù)字工程，2010，38（4）：11?14.