面向高并發民航業務的動態負載均衡設計

田　豐　倪兆陽　丁建立　王　靜

1(中國民航信息網絡股份有限公司研發中心　北京 100000)2(中國民航大學計算機科學與技術學院　天津 300000)

?

面向高并發民航業務的動態負載均衡設計

田豐1倪兆陽2丁建立2王靜2

1(中國民航信息網絡股份有限公司研發中心北京 100000)2(中國民航大學計算機科學與技術學院天津 300000)

針對民航業務實時并發請求多、業務功能復雜、數據量大的特點，簡要介紹當前業務系統的總體結構和負載均衡機制，分析現有負載均衡算法的優點和不足。為了提高民航業務系統的魯棒性和可靠性，根據其軟硬件結構特點在原負載均衡機制的基礎上提出改進的動態負載均衡策略。同時設計維護負載度量指標所需的數據結構以及在這種數據結構下維護該指標的方法，并進行實驗對比驗證。實驗結果表明，動態負載均衡策略能夠更好地應對高并發復雜網絡環境，使系統的魯棒性和可靠性得到提升。

動態負載均衡高并發民航分布式

0　引　言

隨著經濟社會的發展，航空運輸變得越來越普及。2014年中國民航旅客運輸量已經達到3.9億人次，排名世界第二。互聯網的迅猛發展也使越來越多的人從網絡渠道獲得關于航班的各種信息。以民航旅客服務信息系統中目前為止最大規模的服務器集群DIP(Data Integration Platform)來說，其吞吐量持續峰值已經達到10 000 TPS，日處理消息量在2億條左右。這意味著越來越多的民航業務要由信息系統處理，系統負載量大幅增加。

民航旅客服務信息系統的運行狀況不僅僅關系到提供給地面用戶的服務質量，還涉及到空中的交通安全和全國各航空公司的飛行計劃安排，一旦出現差錯將造成大量的旅客滯留和航班延誤，其損失是不可估量的。這就要求民航旅客服務信息系統能夠良好地應對高并發高負載環境。提高現有信息系統對高并發、動態變化、連續高可靠性的適應能力以及對其他需求的應對能力成為當前的重要任務。

民航旅客服務信息系統屬于大規模分布式系統。在分布式環境下，系統中往往有多個處理能力各不相同的節點，而且請求的到達以及請求的復雜性都是隨機的。如果一味地將請求全部分配給系統內某一臺服務器，則不但會造成該服務器負擔過重容易崩潰而且也沒有充分利用系統資源[1]。單臺服務器處理能力的提高是有限度的，所以如何對請求進行分流，實現靈活的負載均衡，從而達到對整個分布式系統高效利用的目的成了企業亟需解決的問題。

1　負載均衡分類與現狀

負載均衡大體上可以分為靜態負載均衡和動態負載均衡兩大類[2]。

靜態負載均衡通常以網絡流和啟發式算法為理論基礎，依據分布式網絡中的靜態指標來進行請求分流。網絡流法是一種重要的計算機圖論方法，使用最大流最小割算法求解[3]。Stone研究了將計算開銷和服務器之間的通信開銷考慮在內情況下的請求分流問題，使用最大流最小割算法給出了具有兩個處理器的系統中的最優分配方案，但是沒有給出具有多個處理器情況下的解決方案[4]。Bokhari研究了雙處理器系統中的動態分配模型，并對Stone的研究進行了擴展，使其能夠解決任務通信圖為樹形結構的請求分流問題。Towsley又進一步研究，將Bokhari的成果推廣到了串并聯通信圖結構[5]。靜態負載均衡算法固然有其自身的優勢，但是系統靜態指標或歷史經驗數據不能動態反映分布式系統負載情況的變化，所以靜態負載均衡不能根據實際情況動態調整負載策略[6]。

動態負載均衡算法以服務器的實時負載狀態信息來決定任務的分配，其負載策略由當前系統狀態決定[7]。研究者在近些年提出了許多動態負載均衡算法，按照算法的控制位置特征這些算法大致可以分為分布式、集中式和混合/層次三類。分布式負載均衡算法的基本策略就是鄰近法，每一臺服務器與鄰近的服務器交換負載，并通過多次迭代達到全局負載均衡。比如Kolb等針對MapReduce可能產生的節點瓶頸問題提出了基于塊的負載均衡算法BlockSplit。集中式負載均衡算法中，處于邏輯上中心位置的節點收集所有其他節點的負載情況，根據全局的負載信息做出決策。比如GreedyLB算法在全局范圍選取一個當前負載量最小的服務器，將負載分配給它。為了減小負載均衡算法的系統開銷，一些算法重點研究了如何根據服務器網絡的拓撲結構來構建一個層次樹的問題。在此基礎上將服務器劃分為多個域，每一層在相鄰域之間進行負載均衡，并且在層間執行負載均衡，最后達到全局負載均衡的目的，這樣的負載均衡算法稱為混合/層次負載均衡算法。比如Wang等根據ZEUS網絡框架和云計算結構特征，提出了一種具有三級層次拓撲結構的兩階段負載均衡算法[8]。通常情況下，動態負載均衡相對于靜態負載均衡能夠有30%～40%的性能提升[9]。

2　JCF總體結構

2.1整體結構

JCF(Java Core Framework)中間件平臺是民航旅客服務信息系統的重要組成部分，它運行于分布式環境下，面對著不同的硬件平臺、操作系統和異構的網絡環境。它通過適配服務的方式來解決JCF平臺內部業務服務與現有企業服務總線對接的問題，以及通過企業服務總線訪問JCF平臺內部業務服務時所需要的負載均衡、資源隔離、故障隔離等需求。

JCF平臺由開發工具、運行系統、管理工具三大部分組成，為業務服務的開發、部署、運行和維護提供完整的支持。

其中運行系統的功能可以分為兩個層次，如圖1所示。

圖1　JCF運行系統層次

服務層為應用支撐框架，允許用戶使用Java語言創建核心業務邏輯，然后使用JCF提供的流程配置工具將核心業務邏輯編排成可以獨立部署和運行的業務服務。平臺采用SEDA架構，其中每個服務為一個階段，每個階段含有一個資源控制器，根據本階段的負載情況動態調整資源配置。階段之間的調用由JCF系統的服務調用平臺負責。

調用層為分布式服務調用平臺，為服務之間的相互調用提供基本支撐，包括SEDA 異步調用、負載均衡、故障隔離、自動尋址等功能。對業務應用的開發者來說它是“透明”的。

2.2負載均衡機制

JCF的負載均衡機制位于服務調用方的攔截器中，作為攔截鏈的一個Handler存在，叫做LoadBalanceHandler。LoadBalanceHandler從屬于服務調用者，調用負載均衡器LoadBalancer選擇服務實例。LoadBalancer是獨立于攔截器Handler而單獨存在的，是對負載均衡算法的抽象，如圖2所示。

圖2　負載均衡器

每一個LoadBalancer實例都是當前服務器中的某一個被調用服務的負載均衡算法的抽象。其中主要的方法是chooseServer，用來選擇一個服務器處理當前請求。ServiceInstance是對服務實例的抽象，其中封裝了服務實例所在服務器的主機地址和端口。ServerMetaInfo是用來描述服務器的對象。AbstractRule是所有負載均衡算法的抽象基類。ConsistentHashingRule是一致性哈希算法。WeightedRoundRobinRule、LeastPendingRequestRule是不同策略的隨機負載均衡算法。當負載均衡邏輯選擇服務實例時拋出異常時，根據指定的環境變量，決定中止調用并返回錯誤信息，或者使用父類的隨機負載均衡算法RandomRule隨機選擇一個服務實例。

負載均衡器是在客戶端的服務器，由于在一臺服務器上有可能存在多個服務作為某個服務的客戶端，因此需要建立一個被調用服務的唯一的負載均衡器。JCF平臺采用工廠模式創建負載均衡器，LoadBalancerFactory是負載均衡器的工廠類，便于擴展新的負載均衡策略；LoadBalanceManager作為負載均衡器的管理者，負責保存服務器內共享的唯一的負載均衡器，如圖3所示。

圖3　負載均衡器的管理機制

在當前JCF平臺的固定比例因子負載均衡算法中，負載均衡的Handler通過LoadBalanceManager調用LoadBalanceFactory創建LoadBalancer的實例，并調用chooseServer()方法選擇接收請求的服務器。而在chooseServer()方法中依賴服務注冊庫維護的LoadFactorMap和LoadbalancerInfo按照固定比例因子算法選擇服務器。其中LoadBalanceInfo用來保存一個服務的固定比例因子的負載均衡信息，包括服務實例列表和根據比例因子計算出的最大值、最大公約數、輪轉周期、輪轉列表，以及表示輪轉列表當前位置的的下標。LoadFactorMap是維護服務注冊庫信息和LoadBalanceInfo的類，當服務實例增加或減少時，重新計算固定比例因子的輪轉列表，并設置到LoadBalanceInfo中。

例如某個JCF域內含有3臺JCF服務器，負載均衡因子分別設置為1、2、3。假設請求處理速度遠遠小于請求到達速度，當有60個請求同時到達時這些請求將會以3∶2∶1 的比例被分配給域內3臺服務器。

該算法屬于靜態負載均衡算法，實現簡單且復雜度低，符合算法設計原則。但是其比例因子只能根據機器性能和以往經驗由人工設定，在運行過程中不能根據負載情況的變化實時調整策略。如果運行過程中某臺服務器負載過大，該狀況并不能為負載均衡算法所察覺，仍然會按照固定比例向其發送請求，而不能讓其他運行狀況尚良好的服務器多分擔請求。所以該算法的靈活性欠佳，需要對其進行改進。

3　動態負載均衡設計

為了改善負載均衡算法的靈活性，新的算法采用動態負載均衡策略，以未完成請求數為負載度量指標，循環服務列表中的每一個服務實例，選擇未完成請求數最低的服務實例處理請求。

3.1未完成請求數的維護

國際民航系統間報文交互基于IATA所定義的國際規范,該規范分TYPE-A和TYPE-B兩種類型，其中TYPE-A屬于Request-Reply模式，TYPE-B屬于One-way模式。JCF平臺提供了基于這兩種模式的負載均衡機制。未完成請求數的維護方式取決于消息傳輸模式：

1) 在One-way模式下，使用服務端的隊列深度。當收到服務端的Signal信號時，將相應服務實例的指標值更新為信號中攜帶的請求隊列深度。

2) 在Request-Reply模式下，使用客戶端維護的指標。當負載均衡Handler選出服務器后，對該服務實例的未完成請求數加1；當收到服務端的應答消息時，對相應服務實例的未完成請求數減1；當收到超時信號時，由于同一個請求消息收到超時信號后就不會再收到應答消息，所以對相應服務實例的未完成請求數減1。

在Request-Reply模式下客戶端需要按照一定的時間窗口進行計數。只計算指定長度時間窗口內的請求數，在時間窗口內分為不同的刻度分別統計，每過一個刻度，就拋棄窗口外的計數，這樣就完成了對超時請求數的拋棄。

3.2未完成請求數的統計

統計過去s個時間單位的未完成請求數的算法，可以表述為獲取當前時間t以前s個時間單位(μ)的未完成請求數reqno之和：

未完成請求數的統計需要使用一個適當的數據結構，然后處理好三個問題：

1) 當請求發出時，使未完成請求數加1；

2) 當應答收到時，使未完成請求數減1；

3) 當需要統計時，統計出指定時間范圍內的未完成請求數之和。

3.3數據結構

在計算機中模擬這一統計過程只需關心s個時間單位內的未完成請求數，所以給每個服務實例定義一個包含s個結點的線性表。每個結點代表一個時間窗口，即一個時間單位，其中保存建立該結點時的時刻time以及一個時間單位內的未完成請求數reqno(使用原子數據類型)。新的結點加在后面，當加入新的結點時，各結點依次前移，把時間最久遠的結點拋棄，如圖4為一個s=5的數據結構。

圖4　數據結構

3.4增加未完成請求數

假設采用結構數組方式實現該數據結構，命名為cell。同時假設當前時刻為t，如果t-cell[s-1].time<μ，則cell[s-1].reqno=cell[s-1].reqno+1。

設μ=1,t=25.74時，格子的內容如下所示：

判斷條件25.74-25<1成立，則cell[4].reqno=1+1=2。

如果t-cell[s-1].time≥μ，則首先需要滑動時間窗口，再進行未完成請求數的累計。

3.5滑動時間窗口

再按照t-cell[s-1].time<μ的情況進行增加請求數操作，如下所示：

3.6減少未完成請求數

對于非血運重建患者，基于多項臨床試驗及薈萃分析[3-5]顯示：SCAD患者若無禁忌證，建議阿司匹林100mg/d長期治療，若不能耐受阿司匹林，建議服用氯吡格雷75mg/d或替格瑞洛 60mg 2次/d～90mg 2次/d；血栓高危患者如心肌梗死病史且伴有1項危險因素：年齡65歲以上、糖尿病、2次心肌梗死、多支病變、腎功能異常(肌酐清除率<60ml/min)，且出血風險較低的患者可考慮采用阿司匹林聯合替格瑞洛(60mg 2次/d)長期治療，治療期間嚴密監測出血。

假設μ=1,t=27時窗口的內容如下所示：

3.7統計未完成請求數

設當前時間為t，如果t-cell[s-1].time<μ，那么只需要對當前的數據結構進行累積：

int acc = 0;

for(int i = 0; i < s; i++) {

acc += cell[i].reqno

}

如果t-cell[s-1].time≥μ，也就是說沒有最近一個時間單位的未完成請求數，那么首先需要滑動時間窗口，然后再按上述方式進行統計。

3.8負載均衡算法

對上述未完成請求數維護方法進行分析，發現不論是發出請求還是收到應答均需要判斷是否需要滑動時間窗口。如果滑動了時間窗口，還需要對每個服務實例的總體未完成請求數進行更新以提供負載均衡操作所需要的最新參考指標。對各種操作歸納總結，提煉出公共操作后繪制出算法流程如圖5所示。

圖5　算法流程圖

針對上述數據結構特點，分析負載均衡流程，設計出Request-Reply模式下的動態負載均衡算法：

a) 計算當前時刻t與最近的時間窗口所記錄的時刻的差值Δt=t-cell[s-1].time；

b) 判斷Δt是否大于一個時間單位μ，若是則轉到步驟c)，否則轉到步驟e)；

e) 判斷事件類型，若為發出服務請求則轉步驟f)，否則轉步驟h)；

f) 遍歷所有服務實例的未完成請求數，選擇其中的最小值summin；

g) 對第min個服務實例的最近一個時間窗口的未完成請求數加1，即cell[s-1].reqno=cell[s-1].reqno+1，然后對summin加1，算法結束；

i) 判斷pos是否大于0，若是則轉步驟j)，否則算法結束；

j) 從應答消息中得到服務實例編號back，對第back個服務實例的第pos個時間窗口的未完成請求數減1，即cell[pos].reqno=cell[pos].reqno-1，然后對sumback進行減1操作，算法結束。

4　實　驗

本節給出了采用動態負載均衡算法的服務器集群和采用固定比例因子負載均衡算法的服務器集群的性能對比實驗結果。兩個服務器集群cluster1和cluster2均部署JCF平臺，通過適配服務接收服務總線上的請求消息。兩個集群內均含有3臺業務服務器和1臺適配服務器，其中業務服務器上均部署有serviceA和serviceB兩種業務服務，適配服務器上部署適配服務adapterService。serviceA用來模擬簡單業務服務，不設置延遲；serviceB用來模擬復雜業務服務，其延遲時間設置為3秒。如圖6所示。

圖6　實驗場景

兩個集群的服務器配置相同，具體配置信息如下：

? Intel(R) Xeon(R) CPU X7550 @ 2.00 GHz；

? 8 GB RAM；

? Red Hat Enterprise Linux Server release 6.3 (Santiago)；

? SUN JDK Version 1.6.0_10。

其中cluster1采用動態負載均衡算法，cluster2采用固定比例因子負載均衡算法，比例因子設置為1∶1∶1。按照JCF平臺的處理機制，當請求消息在服務總線上出現后，將由適配服務負責獲取該消息，然后執行負載均衡算法選擇集群內的一臺服務器，將請求交由該服務器進行處理。

實驗環境搭建完成后用客戶端程序向服務總線持續發送serviceA的請求消息，發送間隔為3毫秒，該操作模擬民航請求中并發量大，同時處理速度較快的航班可售庫存查詢。第30秒鐘時發送一條serviceB的請求消息，模擬民航請求中隨時可能出現的業務功能復雜的運價搜索或航班計劃創建請求。運價搜索請求的處理需要在多條航路中綜合判斷以返回符合搜索條件的結果，該過程會涉及到多航段排列組合進行運價計算；而航班計劃創建會對原有航班計劃產生連鎖影響，需要進行大量計算以安排出新的計劃表。這兩種請求都會耗費大量服務器資源，降低服務器吞吐率。實驗過程持續90秒鐘，結束后統計出兩個服務器集群的TPS數和集群內各臺服務器的TPS數，截取其中15秒鐘的數據繪制成如圖7-圖9所示。

圖7　cluster1內各服務器TPS

圖8　cluster2內各服務器TPS

圖9　集群TPS

從圖中可以看出，在第30秒時兩個集群中均有一臺服務器的TPS數突然下降，這是由于請求消息中出現了對serviceB的請求，該請求會占用大量服務器資源，導致其TPS數下降。不同的是cluster1內另外兩臺服務器的TPS數在此種情況下出現了上升，集群TPS保持穩定；而cluster2內另外兩臺服務器的TPS數沒有明顯變化，集群TPS出現下降的情況。這說明動態負載均衡起到了應有的作用，在集群內某臺服務器執行了運價搜索或航班計劃創建之類的復雜請求。隊列中出現積壓請求消息的情況后，動態負載均衡算法根據各臺服務器未完成請求數的情況自動將新接收到的請求多分發給另外兩臺負載較小的服務器，從而使集群TPS不受影響或受影響較小。而固定比例因子負載均衡算法則不論服務器負載情況變化，只能按照設定好的比例因子將請求按比例發送給各臺服務器，集群TPS會因此受到業務復雜程度的影響。

5　結　語

在分布式系統中，負載均衡的目的是根據各臺服務器的性能指標和負載情況來分配請求[10]，服務器的處理能力和當前未完成請求數是負載均衡算法所要參考的重要指標[11]。未完成請求數是一個動態變化的指標，維護該參數首先需要設計一種動態度量策略，該策略要良好地適配系統結構和工作機制，以準確地反映系統中負載的變化情況。負載均衡算法是負載均衡策略的核心，在設計時要減小復雜度，避免負載均衡算法成為系統性能瓶頸[12]。

本文針對JCF平臺的結構特點設計了動態負載均衡算法。該算法用一種窗口式的數據結構維護每個業務實例的未完成請求數，并且用滑動窗口的方式完成超時請求的自動丟棄。在此基礎上以業務實例的未完成請求數為度量指標，將請求分發到負載量最小的服務器上，最大程度減少民航業務復雜度的變化對集群吞吐率的影響。這增強了JCF平臺的魯棒性，使JCF平臺在高并發、復雜程度動態變化的民航業務環境下保持穩定的性能。

[1] 尤天舒. 基于Agent的集群負載均衡模型及其實驗研究[D].吉林大學,2014.

[2] 王紅斌. Web服務器集群系統的自適應負載均衡調度策略研究[D].吉林大學,2013.

[3] 晉英豪. 異構網絡中負載均衡和資源分配策略研究[D].中國科學技術大學,2015.

[4] 胡楊. 虛實結合框架下負載均衡服務集群的研究與實現[D].浙江大學,2015.

[5] 陳濤,肖儂,劉芳. 對象存儲系統中自適應的元數據負載均衡機制[J]. 軟件學報,2013,24(2):331-342.

[6] 弭偉. 基于DHT的分布式網絡中負載均衡機制及其安全性的研究[D].北京郵電大學,2012.

[7] 吳和生. 云計算環境中多核多進程負載均衡技術的研究與應用[D].南京大學,2013.

[8] 楊際祥. 并行與分布式計算負載均衡問題研究[D].大連理工大學,2012.

[9] 周瑩蓮,劉甫.服務器負載均衡技術研究[J]. 計算機與數字工程,2010,38(4):11-14,35.

[10] 尚志浩.OpenFlow網絡中服務器負載均衡的研究[D].蘭州大學,2014.

[11] 吳宇文.基于OpenFlow的網絡負載均衡算法的研究與設計[D].華東師范大學,2014.

[12] 周松泉.一種新的服務器集群負載均衡算法[D].南昌航空大學,2012.

DYNAMIC LOAD BALANCE DESIGN FOR HIGH CONCURRENCY CIVIL AVIATION BUSINESS

Tian Feng1Ni Zhaoyang2Ding Jianli2Wang Jing2

1(ResearchandDevelopmentCenter，TravelSkyTechnologyLimited,Beijing100000,China)2(SchoolofComputerScienceandTechnology，CivilAviationUniversityofChina,Tianjin300000,China)

For the features of civil aviation business such as a lot of real-time concurrent requests, complicated business functions and large data amount, we briefly introduced the overall architecture and load balance mechanism of current business system, and analysed the merits and drawbacks of existing load balance algorithm. To promote the robustness and reliability of civil aviation business system, we put forward an improved dynamic load balance strategy based on the original mechanism in accordance with the software and hardware feature. Meanwhile we designed a new data structure required for maintaining the load measurement indicators and the relative method to maintain such indicator in this structure, and carried out experiment for contrast verification. Experimental result indicated that the dynamic load balance strategy could cope well with high concurrency and complicated network environment, which promoted the robustness and reliability of the system.

DynamicLoad balanceHigh concurrencyCivil aviationDistributed

2015-07-06。民航局科技創新引導資金專項(MHRD 20130106，MHRD20140106，MHRD20150107)；中國民航大學中央高校基金項目(3122014P004，3122014C016)。田豐，工程師，主研領域：中間件及云計算架構。倪兆陽，碩士生。丁建立，教授。王靜，講師。

TP319

A

10.3969/j.issn.1000-386x.2016.10.001