面向JCF中間件的親和性動態負載均衡算法

曹衛東，孫曉君，周 原，王 靜

(1.中國民航大學 計算機科學與技術學院, 天津 300300； 2.中國民航大學 天津市智能信號與圖像處理重點實驗室，天津 300300)

0 引 言

逐年增長的航空旅客運輸量產生大量的訂票需求，新一代旅客服務系統(passenger service system，PSS)等大規模分布式集群系統能夠共同分擔海量用戶請求，其上部署的負載均衡算法可以提供一種有效透明的方法，提高集群系統中服務器的帶寬、吞吐量、數據處理能力等[1]。

民航業一直在積極建設新一代PSS，JCF(java core framework)中間件平臺是Java環境后臺交易平臺，也是新一代PSS的核心模塊之一。在JCF中間件平臺上，由于系統結構和業務需求原因，部分服務的上下文環境被存儲在處理該服務請求的服務器上，不被其它服務器共享，而在處理同一個用戶后續請求過程中需要用到這些環境，此外在處理同一個用戶的后續請求時，需要用到前面請求的處理結果，所以該類用戶請求需分配到同一服務器上按時間順序進行處理，稱之為服務的親和性。

若服務的親和性無法滿足，會出現用戶請求分配不合理、請求無法響應等問題。因此，本文在研究JCF平臺負載均衡機制及多種負載均衡算法基礎上，提出一種親和性動態負載均衡算法，算法提取用戶標識信息作為哈希映射鍵值，并使不同用戶請求均勻分布，保證了服務的親和性、系統負載均衡性能和穩定性。

1 相關工作

負載均衡的主要功能是縮短請求響應時間以及能夠動態適應集群中單個服務器狀態的變化。早期的負載均衡算法較簡單考慮因素較少，隨著研究的深入，提出一些適用于不同場景的算法[2]。從民航業務服務的親和性角度，按照用戶請求分配方式，對已有算法進行了如下分析和總結。

一類是以輪詢機制分配請求。將用戶的請求依次分配給集群系統中的服務節點，循環往復，如輪詢算法[3]。在其基礎上，通過為服務器分配比例因子或權值的方式，調配服務器接受請求的比例，如固定比例因子算法[4]、加權輪詢算法[5]。另一類是按照特定規則分配請求。例如，文獻[6]提出最小未完成交易數算法，選擇當前未完成交易數最小的服務器分配用戶請求；文獻[7]提出改進的動態告警負載均衡算法，綜合考慮請求類型、節點工作能力和實時負載值，再確定轉發的目標服務器；文獻[8]提出基于空間填充曲線的動態負載均衡算法，使均衡器根據實時收集的各項負載指標快速定位到最優編碼的服務器；文獻[9]提出一種數據段交換算法，將內存帶寬負載不均衡服務器上的數據段進行相互交換，使集群的帶寬負載達到均衡。

以上多種負載均衡算法，對于來自同一用戶的連續請求，可能會被分配到不同的服務器上，不能有效滿足服務的親和性需求。結合民航業務服務的親和性以及負載均衡需求，本文設計了一種親和性動態負載均衡算法。

2 面向JCF的親和性動態負載均衡算法

為了使集群系統在進行用戶請求分配過程中，滿足服務的親和性需求。面向JCF中間件平臺，提出了一種親和性動態負載均衡算法，該算法在進行用戶請求分配過程中，優先滿足服務的親和性需求，其次通過引入虛擬節點，有效保證了集群系統負載均衡性能，并結合實際應用情景，設計集群規模動態調整策略。

2.1 JCF中間件

JCF中間件平臺位于服務管理平臺和新一代PSS核心組件之間，Java語言編寫的各種應用可以部署到JCF中間件平臺上運行。基于該平臺可以實現不同系統之間的信息交換，并最終達到資源實時調度。JCF架構中的分布式運行系統是由多個服務器組成的分布式環境，允許通過擴展服務器個數進行集群規模擴展，在進行調用分布部署的服務時提供負載均衡功能[10-12]。JCF負載均衡功能模型如圖1所示，用戶的各類服務請求通過TSI(travelsky service integration)總線接入到內部集群系統，再分發到相應的集群中。

圖1 JCF負載均衡功能模型

2.2 算法設計

親和性動態負載均衡算法基于帶有虛擬節點的一致性哈希算法，其基本原理如下：首先根據鍵值的比特數N(一般取N=32)可以得到一個0～232-1的哈希環；接著定義虛擬節點個數，一個實際服務器節點對應若干個虛擬節點；再計算虛擬節點的哈希值，映射到哈希環上；然后計算用戶請求的哈希值再映射到環上，按順時針映射到距離其最近的虛擬節點，該虛擬節點所對應的實際服務器節點，即為該用戶請求的實際處理節點。

本文在處理用戶請求時，對用戶請求的頭部攜帶的具體標識，進行信息提取和轉化得到用戶標識信息，作為哈希函數的輸入。由于民航系統實際應用中，同一航空公司的用戶請求的標識是固定的，哈希環上的服務器節點也固定，因此，同一個用戶請求的鍵值映射到哈希環上以后，會映射到相同的服務器節點，以此保證服務的親和性。

本文算法引入虛擬節點機制，并使用運算性能高、碰撞率低和隨機分布特征更良好的MurmurHash3算法進行具體哈希值計算。可以使得哈希環上更加均勻的分布更多的虛擬節點，用戶請求將更加均勻的映射到每一個實際服務器節點上，這樣可以有效減少服務器過載和輕載問題出現。保證集群系統的負載均衡性能。

算法如圖2所示，實際服務器節點Server A對應圖中Server A1和Server A2兩個虛擬節點，實際服務器節點Server B對應圖中Server B1和Server B2兩個虛擬節點，req1通過哈希函數計算得到key1，并順時針映射到距離其最近的虛擬節點Server A2上，根據對應關系，最終分配到Server A處理，req2、req3、req4同理，根據算法映射到各個節點進行處理。

圖2 算法

2.3 算法流程

算法流程如圖3所示。

首先定義虛擬節點數量記為VNN，將實際服務器節點

圖3 算法流程

與虛擬節點進行映射，即一個實際服務器節點對應VNN個虛擬節點

(1)

其中，N為當前集群中實際服務器節點總數，k為常數，W為整個集群的權重之和，wi為第i個服務器的權重。

(1)根據式(1)計算出虛擬節點個數，對于每個虛擬節點其編號Virtual_Nodeit，(1≤i≤N)，(1≤t≤VNN)，表示第i個實際服務器節點對應的第t個虛擬節點；

(2)建立虛擬節點和實際服務器節點之間的對應關系，一個實際服務器節點對應VNN個虛擬節點；

(3)計算實際服務器節點的哈希值。在JCF中間件平臺的服務庫中，每個服務器注冊一個元數據表，根據表中服務器節點配置的server_name，通過MurmurHash3算法計算得到每個服務器節點的哈希值Node_hashi，(1≤i≤N)；

(4)計算虛擬節點的哈希值。對于某個虛擬節點，將Node_hashi加Virtual_Nodeit的值作為MurmurHash3算法輸入，計算得到每個虛擬節點的哈希值，記為Virtual_Node_hashit，(1≤i≤N),(1≤t≤VNN)，表示第i個實際服務器節點對應的第t個虛擬節點的哈希值；

(5)根據Virtual_Node_hashit的值將虛擬節點映射到環上；

(6)用戶請求的處理。用戶根據設定規則設置請求內容，算法解析用戶發送的http請求，從用戶請求的消息頭headers中獲取請求頭部的host值，若值的類型為字符串，首先要應用函數將字符串類型數據轉換成整形數據。使用Fowler-NOll-Vo函數完成這個目的

keyuser=Fowler-NOLL-Vo(host)

(2)

(7)計算用戶請求的哈希值，根據keyuser通過MurmurHash3算法計算用戶請求的哈希值User_hash；

(8)處理用戶請求，將User_hash映射到環上，按順時針方向映射到距離最近的虛擬節點上，根據實際服務器節點和虛擬節點的對應關系，該請求實際是映射到對應的實際服務器節點上去處理；

(9)當有新的請求發送到集群時，重復(6)～(8)步。

2.4 集群規模動態調整

在實際的使用中，集群中能夠正常提供服務的服務器的個數可能會發生變化。分為以下兩類情況：當業務量增加，需要增加新的服務器以滿足新的業務需求，或者已宕機服務器經過維護重新投入使用，會造成集群規模擴展。另外，由于服務器性能下降，負載量長時間過大，運行的程序出現死循環，線路或者服務器發生物理故障時，會造成集群規模縮減。

當集群規模發生動態變化時，需要對服務請求做平滑處理，保證集群負載均衡的同時，最大程度減少受影響的用戶個數，保證絕大部分用戶服務的親和性能夠得到滿足，保證系統的穩定性。本文算法針對集群規模變化，設計了如下動態調整策略：

(1)集群規模擴展。當需要增加服務器時，首先將服務器信息添加到服務庫中。再根據規則生成新的服務器節點的虛擬節點，并映射到環上。服務請求根據規則映射到新服務器上進行處理。

如圖4所示，原先集群系統中有服務器Server A、Server B、Server C，req1映射到Server A處理，req4映射到Server B處理，req2和req3映射到Server C處理，當集群中增加一個服務器Server D后，此時req2順時針尋找到距離其最近的服務器節點為Server D，則req2映射到Ser-ver D處理。其余用戶請求不受影響。

圖4 增加Server D節點

(2)集群規模縮減。當需要刪除服務器時，將服務器從服務庫中刪除，并從環中刪除該服務器的所有虛擬節點映射，原來發送到該服務器上的用戶請求，沿順時針再繼續尋找離自己最近的服務器作為新的服務器節點，由新的服務器節點處理請求。

圖5中顯示集群中原先有4個服務器，請求映射情況為req1映射到Server A，req2映射到Server D，req3 映 射 到Server C，req4映射到Server B，此時Server B發生故障，req4按順時針方向映射到與其距離最近的Server D，其它請求映射關系不變。

圖5 刪除Server B節點

如圖4、圖5所示，當增加服務器ServerD和刪除服務器ServerB后，重分布的用戶分別為req2和req4，環上其余用戶不受影響。由此表明，當集群規模發生動態變化時，受影響的用戶僅包括，從變化服務器逆時針到距離其最近的服務器節點之間這一段哈希環上的用戶，其余用戶不受影響，這保證了絕大部分用戶服務的親和性，避免了大部分用戶重分布帶來的損失。當服務器減少時，集群系統的負載均衡性能相對減弱，使得部分服務器負載增大。但從總體上來看，由于動態調整策略的存在，服務的親和性受影響的用戶較少，且受影響的用戶能夠得到及時有效的調整，集群系統的負載均衡性能受到的沖擊較小，系統相對穩定。

3 系統仿真和算法性能分析

3.1 實驗環境與過程

實驗模擬JCF中間件平臺，搭建了一套仿真實驗環境，由7臺Dell服務器組成一個小型集群系統。其中一臺作為服務庫，一臺作為適配器，其它作為處理用戶請求的目標服務器，服務器的配置為：CPU型號：Intel(R) Core 2 Duo E7500;CPU內核：2 core；RAM：6 GB，硬盤：300 G；操作系統：Ubuntu 14.04；運行環境Myeclipse，jdk1.8，相關軟件：Apache JMeter。

服務庫上安裝服務注冊表，包含各臺服務器節點的信息，適配器上安裝Nginx反向代理服務器，為了進行算法對比，在Nginx反向代理服務器上部署了4種算法，分別為固定比例因子算法、最小未完成交易數算法、輪詢算法和本文算法，其中固定比例因子算法和最小未完成交易數算法為JCF平臺上原有算法。

實驗中使用Apache JMeter軟件，構造大量的http請求，在一定的時間周期內發送到適配器上，適配器根據當前配置的負載均衡算法，將請求轉發給后端服務器。

3.2 實驗場景與性能分析

根據本文算法的特點，并且結合實際的應用需求，本文實驗場景分為4個部分：

(1)場景一：系統處于穩定狀態，集群中有4個服務器處理用戶請求，使用Apache JMeter構造大量用戶請求，在一定的時間周期內，發送到集群系統，通過適配器上部署的4種不同的負載均衡算法，分配到服務器上去處理。觀察實驗結果，統計實驗數據，計算4種算法的親和率。

親和率計算方法如下，在一個實驗時間周期內，一共有num個用戶訪問了集群系統，第i個用戶共發送NRi(1≤i≤N)個連續請求，記該用戶首次映射的服務器為目標服務器，則第i個用戶的所有連續請求命中目標服務器的總次數記為NOi(1≤i≤N)，則第i個用戶命中目標服務器的命中率記為Hi

(3)

則整個集群系統的親和率記為A

(4)

式(4)表示，在一個實驗時間周期內，所有訪問該集群系統的用戶，命中目標服務器的命中率之和，取其平均數，即為該集群系統的親和率。

在配置了負載均衡算法的集群系統中，親和率為所有用戶的連續請求發送到其目標服務器次數占其發送請求總次數的比率。親和率越高，即表示越多的用戶連續請求被分配到相同服務器處理，則更加滿足服務的親和性需求。通過親和率的大小，可以觀察當前集群系統在滿足服務的親和性方面的表現。

如圖6所示為在不同用戶請求總數情況下，4種算法的親和率。系統的親和率隨著請求數量的增加基本處于穩定狀態，對于固定比例因子算法、輪詢算法和最小未完成交易數算法，當請求總數為200時，親和率分別為23.5%、26.5%和25.5%；當請求總數為800時，親和率分別為26.6%、23.4%和22.6%；當請求總數為2000時，親和率分別為25.3%、26.2%和26.6%；實驗結果表明，以上3種算法的親和率基本穩定在24%、25%和25%左右。本文算法的親和率在不同請求總數情況下均為99%。對比實驗結果表明，本文算法的親和率比其它3種算法的親和率高很多，這表示本文算法能夠將絕大部分的用戶連續請求發送到目標服務器上去處理，有效滿足服務的親和性需求。

圖6 4種算法的親和率

(2)場景二：系統處于穩定狀態，集群中有4個服務器處理用戶請求，使用Apache JMeter構造大量用戶請求，在一定時間周期內，發送到集群系統，模擬不同的請求并發數，并發數由少至多。統計請求總響應時間和系統吞吐量，請求總響應時間為系統處理請求并響應的總時間，系統吞吐量表示每秒完成的請求數。

如圖7所示，當請求并發數遞增時，固定比例因子算法的請求響應時間從0.09 s增加到0.26 s；輪詢算法的請求響應時間從0.076 s增加到0.275 s；最小未完成交易數算法的請求響應時間從0.02 s增加到0.2 s；本文算法的請求相應時間從0.02 s增加到0.18 s，4種算法的請求總響應時間，隨著請求并發數的增加不斷增加，其中本文算法請求響應時間相對較短。

圖7 4種算法的請求總響應時間

這是由于固定比例因子算法、輪詢算法和最小未完成交易數算法，這3種算法的請求分配機制均不能保證連續請求被分配到同一服務器。由于此時未滿足服務的親和性，會導致該請求無法及時響應或者無法響應，增加系統的請求總響應時間。

本文算法在處理同一用戶的連續請求時，由于標識固定，會將這些連續請求發送到同一服務器的服務隊列中，按照時間順序處理，避免由于服務所需資源與服務器綁定，而導致的請求無法響應問題，同時減少由于后續請求需要前面請求處理結果的等待時間，因此使得服務的親和性得以保證，負載均衡情況下請求響應時間相對較短。

如圖8所示，當請求并發數為60 個/s時，固定比例因子算法、輪詢算法、最小未完成交易數算法和本文算法的吞吐量分別為：36.2個/s、37.5個/s、38.3個/s、38.4個/s；當請求并發數為500個/s時，4種算法的吞吐量分別為：119.0個/s、101.6個/s、117.6個/s、118.1個/s。4種算法的系統吞吐量隨著請求并發數量的增多呈上升趨勢，本文算法的系統吞吐量和其它算法的系統吞吐量接近，并發量高時略低于其它算法。

圖8 4種算法的吞吐量

這是由于當多個用戶在一定時間周期內，發送來多個連續請求，并且這些用戶請求映射到相同的服務器上去處理，該服務器的處理壓力會增大，極端情況時服務器會由于過載而宕機。此時，服務器處理能力會明顯降低，集群系統吞吐量相應的會降低。

(3)場景三：集群系統規模擴展，新增加一個服務器，先到服務注冊庫中注冊，此時服務器總數增加至5臺，適配器上部署本文算法，用戶請求的映射根據2.4節介紹的動態調整策略變化。觀察同一類請求的分布情況，分析請求在系統規模擴展情況下，多少用戶請求受到了影響，若在一個實驗周期內，由于服務器增加，導致某一用戶請求需重映射到新的目標服務器，則記變化一次，統計總的變化次數CT，記該周期內所有用戶發送請求的總數為num_req，記系統的變化率為CR，則

(5)

(4)場景四：集群系統規模縮減，模擬集群系統中有一臺服務器出現故障，從服務器注冊庫中刪除了一個服務器，服務器總數減少至3臺，適配器上部署本文算法，用戶請求的映射根據2.4節介紹的動態調整策略變化。觀察同一類請求分布情況，統計系統變化率。

場景三和場景四，分別模擬了給集群增加一個服務器和減少一個服務器的情況，并統計集群的變化率，實驗結果見表1。

表1 變化率統計

兩種狀態下本文算法的變化率分別為21%和34%，即表明變化節點沿逆時針到距離其最近的服務器節點之間這一段哈希環上的用戶請求數占總請求數的21%和34%。這說明分別有21%和34%的用戶的連續請求受到影響，并根據動態調整策略重分布到新的服務器處理。實驗結果表明，本文算法保證了絕大多數用戶的請求處理不受到集群系統規模變化的影響，避免了所有用戶重分布的情況發生，保證了絕大多數用戶服務的親和性。同時受影響的一部分用戶請求，能根據動態調整策略重映射到新的服務器上處理，由于算法設置的虛擬節點在哈希環上分布較均勻，部分請求重映射不會造成某一服務器嚴重過載現象，對集群系統的負載均衡沖擊較小，保證了系統的穩定性。

不同場景下的實驗結果表明，本文提出的親和性動態負載均衡算法，優先保證服務的親和性，雖犧牲了一部分負載均衡性能，使得負載均衡效果沒有優于其它算法，但是集群系統的負載均衡仍得以保證。根據實際生產需求，而設計的集群規模變化實驗結果表明，系統的親和性和穩定性均能夠得到保證。

4 結束語

為了解決民航業大規模分布式集群系統在進行用戶請求負載分配過程中，出現服務的親和性和負載均衡問題，分析了JCF中間件平臺上原有的負載均衡算法以及其它常見負載均衡算法的特點，基于帶有虛擬節點的一致性哈希算法，提出一種親和性動態負載均衡算法，通過設計對比實驗，驗證了該算法能夠使得用戶請求得到合理的分配，滿足服務的親和性需求，同時具有負載均衡功能，并保證集群系統的穩定性和可伸縮性。

但是，該算法還有許多不足，如何在此基礎上，進一步提升算法的負載均衡效果，將是下一步重點研究內容。