基于改進TOPSIS的動態權重負載均衡算法

張 卓，張 上+，項天旭，李夢思

(1.三峽大學 湖北省建筑質量檢測裝備工程技術研究中心，湖北 宜昌 443002；2.三峽大學 計算機與信息學院，湖北 宜昌 443002)

0 引 言

近年來微服務憑借靈活的服務支持和優秀的組織架構得到了國內外企業的廣泛青睞[1]。所謂的微服務，是指將大型分布式系統按照不同的業務與功能解耦成若干微服務，分別提供對應業務處理功能，每個微服務相當于一個獨立的小型服務系統。系統服務功能的單一性可以更加靈活地應用流量限制技術和負載均衡算法使系統更好應對高并發場景，保證系統的可靠性和高效性[2-4]。微服務作為當前新興的分布式架構，帶來便捷高效的同時也對分布式系統中負載均衡的問題提出了更高的要求[5]。

為了在分布式系統中實現更優秀的負載均衡效果，本文基于當前主流的加權最小連接數算法[6]，提出一種基于改進逼近理想及排序(technique for order preference by similarity to an ideal solution，TOPSIS)模型動態確定權重進行負載分發的算法，對用戶請求進行動態調度，充分利用服務器資源。所提算法的創新點總結如下：

(1)考慮集群系統負載狀況的實時性，引入動態權重，將后端服務器作為評價對象，實時負載信息作為評價指標，建立計算模型將評價結果作為依據匹配出最優對象處理請求，得到最佳分配方案。

(2)針對所提負載均衡方案的權重分配時效問題，提出一種最少上報策略，后端服務器發送權重信息時對比判斷權重變化率，判斷是否發送自身權重，優化負載均衡器與節點交互所占用資源。

(3)所提算法將網絡服務請求的均衡問題建模為一個分配優化問題，利用改進TOPSIS模型求解該問題，充分利用集群系統資源，降低系統響應時間，提升吞吐量。

1 相關研究

目前負載均衡技術的研究主要分為：軟件負載均衡[7]和硬件負載均衡[8]。硬件負載均衡器處理網絡請求能力與負載性強，負載均衡策略多樣化。但成本過高，配置冗余且無法有效監控服務器使用狀態。軟件負載均衡器的成本低且可擴展性強，配置簡單，使用靈活，可以改進負載均衡算法來提高系統的負載分發能力。目前國內許多學者外對負載均衡算法進行了研究與改進，比如文獻[9]采用粒子群優化算法分配任務，解決有效任務調度問題；利用動態分組方式提交任務并結合資源使用狀態，收集到分組的結果后，將集群的所有結果合并到一個分配圖，最后引入粒子群優化算法調整負載方案。該方案具有優秀的負載平衡性。文獻[10]提出了一種基于Nginx負載均衡的動態分配算法，該算法根據后端服務器的負載性能指標和處理請求的平均響應時間，通過改進熵值法等算法動態地設置輪詢權重，并且對Nginx內部模塊進行改進，通過測試平均響應時間和最高并發量，得到了比Nginx內置算法更優的結論。文獻[11]提出一種基于云中心虛擬機布局的多資源負載優化算法，該算法減少資源碎片且限制虛擬機空余服務率，平衡各資源的使用，防止節點性能浪費。但該算法存在節點資源利用率低的問題。文獻[12]提出一種動靜融合的負載均衡算法，針對服務器硬件配置和運行時負載狀態變化設計靜態權重與動態權重。該算法能夠實時調整服務器權重，但沒有考慮后端服務器的權重上報策略，節點資源利用率還有進一步提升的空間。文獻[13]提出一種動態加權輪詢算法，引入多負載指標層次分析法確定各性能指標對服務器負載的影響程度，實現動態負載均衡的算法。該算法判斷服務器負載指標較全面，但是采用層次分析法主觀意識過大，通用性不強。

2 常用負載均衡算法分析

目前主流的軟件負載均衡器有Nginx、HAProxy[14]、Ribbon[15]和LVS[16]等。Nginx是一款輕量級高性能的Web服務器，其熱部署、代碼開源且可擴展性強，目前國內外眾多企業系統架構用其作為代理服務器。本文采用Nginx作為集群系統軟件負載均衡器，研究基于Nginx的動態權重負載均衡算法。

常用負載均衡算法分析見表1，目前Nginx負載均衡算法研究中分為靜態和動態兩大類型。前者是在集群系統初始化之前配置負載均衡策略，以固定方式分配請求，配置簡單，在并發量較小時能發揮出優秀的效果，也可以解決Session等問題。但是當并發量過大且各類請求資源消耗相差較大時，會導致整個集群系統節點負載差異較大，平均請求響應時間延長，甚至導致節點宕機。后者能夠實時的與后端服務器進行信息交互，根據服務器反饋的負載信息調整合適的負載策略，對比靜態算法能夠更加合理的將請求分發到各個后端服務器，但是由于負載均衡器頻繁的收集后臺節點負載信息，會增大集群系統的資源開銷，導致平均請求響應時間增加，整個集群性能下降。

表1 常用負載均衡算法分析

針對于上述問題，本文提出一種能夠根據后端服務器實時負載信息調整權重，彌補了靜態負載均衡算法不能根據集群系統實時負載情況進行策略調整問題的負載均衡策略，并且優化后端服務器與負載均衡器之間的交互資源消耗和平均響應時間，同時提高了集群系統吞吐量。

3 基于改進TOPSIS的負載均衡算法

3.1 負載均衡器模型設計

本節設計的負載均衡器系統模型如圖1所示。負載信息收集模塊與負載信息計算模塊部署在集群的每臺后端服務器上，負載均衡算法實現模塊部署在Nginx主機。

圖1 系統結構

負載信息收集模塊周期T收集并計算后端服務器proc文件夾中CPU利用率(R_cpu)、內存利用率(R_mem)、網絡利用率(R_net)、IO利用率(R_io)性能指標，使用Redis[17]數據庫作為全局數據區域共享給負載信息計算模塊，負載信息收集模塊流程如圖2所示。

圖2 負載信息收集模塊流程

負載信息計算模塊主要是解決權重計算的相關問題，主要實現如下兩個功能，負載信息計算模塊流程如圖3所示。

圖3 負載信息計算模塊流程

(1)該模塊周期T在全局數據區域Redis中獲取所有后端服務器負載信息，建立本文設計的改進TOPSIS模型計算后端服務器綜合權重。權重信息反映了該服務器當前負載狀態。

(2)該模塊以HTTP請求中Post方法周期T發送權重JSON信息到負載均衡算法實現模塊，確保在下一個周期T內，權重最大的后端服務器能夠獲得更多的服務請求。該模塊每隔周期T檢測所得的權重大小，若新權重與上一次計算所得權重超過權重變化率Δt，則將新權重發送至負載均衡器。反之則不發送，只是將權重信息存儲到Redis中，繼續沿用上一次接收的權重信息。主動方式發送權重信息可以減少由于集群系統頻繁發送數據而占用網絡資源。由于周期T和權重變化率Δt在實際的應用場合都有所不同，本文通過Apache JMeter[18]壓測后得出周期T與權重變化率Δt。

負載均衡算法實現模塊包括Nginx和注冊中心Consul[19]。Nginx的Upsync[20]模塊周期T從Consul中的K/V服務中取出后端服務器列表和權重信息，并根據改寫的Nginx的Upstream[21]模塊使加權最小連接數算法的靜態權重變更為動態權重，為后端服務器動態調整權重，負載均衡算法實現模塊流程如圖4所示。

圖4 負載均衡算法實現模塊流程

3.2 動態權重計算

TOPSIS是一種逼近理想解及排序算法，主要應用在多目標決策分析[22]。基本原理是通過歸一化后的數據建立規范化矩陣，找出其多個目標集合中最劣目標對象(反理想解)和最優目標對象(正理想解)，計算評價目標集合各數據與最劣目標對象和最優目標對象的歐式距離，獲得各評價目標對象與最優目標對象的貼近度作為理想貼近度，按理想解貼近度的值進行排序作為評價目標對象優劣的依據。理想貼近度設計取值在0和1之間，該值越接近1，則相應的目標對象越接近最優水平，反之，越接近0，則相應的目標對象越接近最劣水平。

在本文設計的算法中，將后端服務器的負載信息采集模塊收集的CPU利用率(R_cpu)、內存利用率(R_mem)、網絡利用率(R_net)、IO利用率(R_io)作為評價目標，根據TOPSIS建模計算出理想貼近度作為權重發送給負載均衡器，故算法的權重取值范圍在0和1之間。負載均衡器根據各后端服務器的權重，選擇出最優的后端服務器響應處理用戶請求。本文定義用Li來表示各個后端服務器的權重，下標i(i=1，2，3，…，n) 表示第i臺后端服務器，Ri_cpu，Ri_mem，Ri_net，Ri_io分別代表第i臺后端服務器的CPU利用率、內存利用率、網絡利用率和IO利用率。

根據上文構建的后端服務器指標體系，建立本文算法TOPSIS模型的具體步驟與公式如下：

(1)為了消除負載信息指標之間量綱的影響，需要對負載信息指標進行標準化處理。建立負載信息指標的正向化矩陣R，rij為第i臺后端服務器的第j個評價指標

(1)

(2)對其標準化的矩陣記為Z，Z中的每一個元素為

(2)

(3)由式(2)可得標準化負載信息指標矩陣Z

(3)

(4)定義各項負載信息評價指標最大值集合Z+

(4)

(5)定義負載信息各項評價指標最小值集合Z-

(5)

(6)定義第i(i=1，2，3，…，n) 臺后端服務器各項負載信息評價指標與其對應評價指標最大值的歐式距離

(6)

(7)定義第i(i=1，2，3，…，n) 臺后端服務器各項負載信息評價指標與其對應評價指標最小值的歐式距離

(7)

(8)由式(6)和式(7)綜合計算得出第i(i=1，2，3，…，n) 臺后端服務器的理想貼近度作為權重

(8)

上述設計TOPSIS模型雖然可以計算出各個后端服務器的權重，但是該模型略顯片面性，因為缺少不同性能指標之間的比較。雖然層次分析等方法可以確定不同性能指標權重，但是其需要對指標間的關系進行刨析且其主觀意識過大。本文采取相對客觀的熵值賦權法[23]計算性能指標權重并結合TOPSIS模型計算出后端服務器的最終權重。

由于各項性能指標在計量單位上的不統一，故對這4項指標進行綜合計算前需要各項指標進行數據處理，以此來解決數據差異性問題，此步驟已在式(1)～式(3)中完成，可以直接用以計算。負載性能指標綜合計算步驟如下：

(1)計算第j項負載信息指標下的第i臺后端服務器占該指標總和比例

(9)

(2)計算第j項負載信息評價指標的熵值

(10)

其中，ln為自然對數，ej>0，k>0。

(3)計算第j項負載信息評價指標的信息效用值

dj=1-ej

(11)

(4)計算第j項負載信息評價指標的權重

(12)

基于式(12)可以改進式(6)與式(7)，為不同的負載信息指標設置不同的權重，可以得到如下公式

(13)

(14)

3.3 最少上報策略

負載信息計算模塊周期T的長短會直接影響本文算法負載均衡效果。如果周期T選取過短，則負載信息計算模塊頻繁的發送權重信息會給負載均衡器帶來過多的資源開銷。如果周期T選取過長，負載均衡器不能實時的更新各后端服務器的權重，負載均衡的效果會受到影響。

本文引入權重變化率Δt并設計最少上報策略解決權重上報周期問題。該策略使各后端服務器在周期T內的權重變化幅度與預先壓測出的權重變化率Δt相比較，當權重變化率大于Δt時，將新權重發送至負載均衡器，當小于Δt值時，只在Redis中修改保存當前的權重信息。如果負載均衡器在周期T內沒有收到后端服務器提交的權重信息，則按照上一周期T接收的該后端服務器的權重信息進行負載分發。權重變化率Δt計算公式如下所示

(15)

其中，Li(t1) 表示后端服務器i在t1時刻的權重，Li(t2) 表示該后端服務器i在t2時刻的權重，Δt表示該后端服務器在一個周期T內的權重變化率，且t2>t1。

4 仿真實驗

本節實驗拓撲架構包括一臺客戶端服務器和負載均衡器和3臺后端服務器組建模擬基于微服務架構的后端服務器集群系統。

實驗架構如圖5所示，其中客戶端中安裝了Apache JMeter測壓工具，可以模擬大量并發請求，實驗環境配置見表2。通過Apache JMeter模擬多個客戶端對集群系統進行并發訪問來測試負載均衡器的負載能力，根據吞吐量和平均響應時間兩個方面的指標與其它主流負載均衡算法的對比情況來檢驗本文算法的效果。

表2 實驗環境配置

在第3章對算法的分析中可知周期T是一個待定的參數。故先對周期T進行測試選值，測試從4 s開始，11 s結束，每隔1 s測試一次，共選取10個時間節點，使用Apache JMeter生成10組數據請求。每組用戶請求并發數為1100和1300，取10次實驗結果的平均值。評價標準為請求返回的響應時間，響應時間越短，說明服務器對用戶的請求處理越快，集群性能也越好。

平均響應時間與周期T如圖6所示，在4 s到6 s階段，由于在周期較短且處于高并發場景，負載均衡器過于頻繁的獲取后端服務器權重信息，大量占用了集群資源開銷，平均響應時間逐步下降。在6 s到11 s階段，由于負載均衡器獲取負載信息周期過長，對后端服務器權重調整不夠及時，平均響應時間逐步升高。當周期T等于6 s時集群的性能最好，故本文實驗選取周期T為6 s。

圖6 平均響應時間與周期T關系

選出合適的周期T后，在該周期下分別選取權重變化率Δt為0.07，0.08，0.09，0.10，0.11，0.12，測試條件和評價標準與測試周期T時相同，同樣取10組測試結果的平均值。平均響應時間與權重變化率如圖7所示，從測試結果可以得到，當Δt為0.09時平均響應時間最短，故本文實驗選取Δt值為0.09。

圖7 平均響應時間與權重變化率關系

為了測試本文動態權重負載均衡算法合理分配資源的效果，使用Apache JMeter對整個集群系統性能進行測試。主要測試內容為：在不同的并發數下，分別對加權最小連接數算法(weighted least-connection scheduling，least-con)、加權輪詢算法(weight round robin，WRR)和本文提出算法的平均響應時間、吞吐量進行對比測試。實驗進行10次，并對實驗記錄數據取平均值，得到各算法的平均響應時間與吞吐量的對比圖。

平均響應時間與并發數關系如圖8所示，整體可見3種算法的平均響應時間都在隨著并發量的增加而提升。在并發量為500以下時，3種不同算法的平均響應時間旗鼓相當并沒有明顯的差距。因為此時并發量較小，集群系統處于低負荷狀態各后端服務器均有能力來處理請求，動態負載均衡算法根據后端服務器運行狀態進行負載分發的優勢并不能體現出來，所以在集群系統并發量小的場景下更加推薦使用靜態負載均衡算法，配置簡單且能節約網絡資源。當并發量超過500后，此時集群系統已經進入中負荷狀態，3種算法的平均響應時間都有大幅度增加的趨勢，但least-con算法對比其它兩種算法平均響應時間稍低，因為該算法可以根據事先配置好的后端服務器權重，并結合選擇擁有最小連接數的后端服務器進行請求轉發，而靜態算法由于不能根據各后端服務器實時負載信息進行調整，故平均響應時間略高，本文算法由于會周期T獲取所有后端服務器詳細負載信息，所以平均響應時間稍高于least-con算法。總體來說3種算法負載分發能力勢均力敵，能滿足基本負載分發要求。但是當并發量超過900后，集群系統進入高負載狀態，由于本文設計算法可以根據后端服務器負載情況動態更新自身權重，在集群高負荷狀態下能夠選出最佳的后端服務器進行請求轉發，充分利用集群資源，優勢逐漸顯現出來，平均響應時間與WRR算法和least-con算法拉開距離。在并發數處于較高的1500時，本文動態權重負載均衡算法平均響應時間比least-con降低了15%，比WRR算法降低了13.1%。

圖8 平均響應時間與并發數關系

吞吐量與并發數關系如圖9所示，在并發量達到500之前，集群系統處于低負荷狀態，3種算法的吞吐量都隨著并發量的增加而增加，且比較穩定，說明3種算法在并發量較小的場景下都可以合理的完成負載分發。在并發量達到500之后，集群系統處于中負荷狀態，本文算法與least-con算法吞吐量高于WRR算法，靜態負載均衡算法的缺陷開始顯露，由于不能動態調整各后端服務器權重進行負載分發，導致并發連接數出現丟失的情況，吞吐量低于動態負載均衡算法。并發數達到900之后，集群系統處于高負荷狀態，3種算法吞吐量均開始大幅度下降，由于本文算法與least-con算法為動態負載均衡算法能夠實時調整負載分發對象，所以并發量基本持平吞吐量，能夠做到請求并發量基本持平于實際并發量，WRR算法由于在配置中固定的負載轉發對象權重，所以在高并發下吞吐量大幅下降。并發量為1200時，集群系統處于中超高負荷狀態，3種算法的吞吐量都大幅下降，但本文算法在超高并發下能夠根據整個集群系統狀態實時更新權重信息選擇出最佳的后端服務器進行請求轉發，所以本文算法減少的幅度較為穩定且高于least-con算法與WRR算法。本文算法吞吐量比least-con算法高21 %，比WRR算法高24.9%；并發量為較高的1500時，本文算法吞吐量比least-con算法高9%，比WRR算法高18.9%。從實驗結果整體來看，在并發量超過950之后，3種算法的吞吐量都隨并發量的增加有大幅度的減少，但是，表明本文算法對比這兩種主流算法能夠更加合理利用服務器資源。

圖9 吞吐量與并發數關系

實驗結果表明，本文提出的基于改進TOPSIS的動態權重負載均衡算法在高并發場景下對比其它兩種主流算法能更加有效合理進行負載分發，減少集群系統平均響應時間，使整個集群系統性能得到了提升。

5 結束語

負載均衡算法是大型分布式系統的關鍵研究問題。本文針對當前流行的微服務架構下后端服務器集群負載失衡的問題，引入動態權重概念，將后端服務器當前剩余負載性能抽象為權重，設計了一種實時反饋調整權重的動態負載均衡算法。在并發數較高情況下，本算法相較于其它常見主流負載均衡算法能夠以動態權重為依據合理分配請求到后端服務器節點，大幅度提升了集群系統的性能。

所提算法設計的負載均衡器為單體架構，所有請求都由負載均衡器進行處理轉發，在超高并發下存在宕機隱患。接下來將研究負載均衡器的服務流控技術，并且全面結合關鍵請求調度，異常處理、流量限制算法等，從而實現資源利用率的最大化以及集群的高可用性。