基于預測閾值的動態權值負載均衡算法

李慧斌 何利力

摘要：為優化整個服務器集群負載，提出一種基于預測閾值的動態權值負載均衡算法。動態評估服務器性能，根據評估結果計算服務器權值，并引入反映集群負載平衡程度和狀態的閾值，以避免因頻繁修改權值造成服務器抖動;使用Holt-Winters對訪問量進行預測，并通過結果預測閾值，實現復雜負載環境下的負載均衡，達到最優負載均衡。實驗結果表明，預測閾值的動態權值負載均衡算法在低并發以及高并發時都有很好的性能表現，能夠提升系統的最大吞吐量，減少響應時間，提高整個集群利用率。

關鍵詞：Holt-Winters預測;負載均衡;服務器集群;動態負載算法

DOI：10.11907/rjdk.192093 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0085-05

0 引言

互聯網用戶和Web應用的爆發式增長，對服務端提出了更高要求，這需要服務器保持可靠運行且能迅速響應，可同時為大量并發客戶端提供優質服務。這種高可用性和高可擴展性，對集群網絡和處理能力都提出了挑戰。于是，高效而廉價的服務器集群成為首選方案，在現有設備下提高整個集群性能變得更加迫切。負載調度算法決定著整個集群性能是否可以完全釋放，作用重大。

現有負載均衡算法主要分成動態負載均衡技術和靜態負載均衡技術兩大類。靜態負載均衡技術指在負載過程中根據預先設置好的策略進行任務分配，不會根據服務器實時情況進行調整，運用起來常常不如動態負載均衡效果好，但靜態負載均衡算法比動態負載均衡算法更加節約服務器資源。

由于效果較好，因此動態負載均衡算法也較多。原地址哈希算法是一種很好的負載均衡算法，只要請求源地址不變，提供服務的總是同一臺服務器。但由于用戶活躍程度不同，可能會出現某服務器處理大量請求，而其它服務器空閑的情況，造成服務器集群負載不平衡。針對這種情況，文獻提出了一種基于預測模型和獨立訓練節點的負載均衡算法。該算法雖然解決了上述問題，但每次都要預測響應時間，根據預測響應時間進行分配，當并發量小時，預測算法反而增加了響應時間，不利于短而快的請求。針對以上問題，文獻提出了一種自適應負載指標權值的負載均衡算法。該算法很好地解決了快速轉發問題，但是只根據評估集群中服務器節點狀態及負載情況修改權值，容易因頻繁的權值修改引起集群抖動。針對頻繁修改權值的問題，文獻提出了動態調節權重的負載均衡策略。在負載算法調節權值前計算一次閾值，根據閾值情況進行權值調節。但其信息都由Nginx負載節點采集，增加了負載節點壓力，影響負載性能。同時，只對服務器節點進行信息收集與預測，且在集群負載出現傾斜時才作出調整。

鑒于此，本文提出基于預測閾值的負載均衡算法。算法具有以下特點：對服務器集群評估不僅僅是根據服務器的CPU、內存、磁盤I/0等參數進行服務器節點權值計算，而是將服務器集群中的每一個節點當前運行的Web項目加入評估中，通過計算每次請求對服務器節點資源的消耗情況實現綜合評估。為了防止權值頻繁更新造成服務器集群抖動，設定反映集群負載平衡程度和狀態閾值，閾值設定保證了權值更新頻率和集群穩定性。同時，增加閾值預測，在集群負載傾斜前調整集群中服務器節點權值，進一步保證服務器集群穩定。預測算法部署方式靈活，可以與負載服務器同時運行，也可以獨立運行，避免了預測算法對負載服務器性能的影響。

1 集群狀態動態評估

采用動態評估方法，對整個集群狀態和集群中的服務器進行評估，主要分為3個部分：節點性能動態評估、節點權值計算、集群負載狀態評估。①節點性能動態評估指從服務器運行項目的角度，評估集群中單服務器節點性能;②權值計算指結合節點性能評估結果，計算此節點權值;③集群負載狀態指評估整個集群當前負載情況，并結合預測閾值及當前閾值對集群負載進行調整，實現動態負載。

1.1 節點性能動態評估

處理整個集群負載問題，首先要量化集群中的每一臺服務器，這是Web集群負載的首要問題。使用不同的性能評估標準，對整個集群的負載能力影響很大。對此，結合服務器運行項目對資源占用情況，從CPU（Central Processing Unit）、內存（RAM）、磁盤I/0，服務器帶寬（Bandwidth）這4個維度評估節點服務器性能。

設集群中有n臺服務器Cluster=（serverl，Server2，……，Server_n），對其中一臺服務器的性能定義為P（serverl），其衡量該服務器的服務能力。

1.2 節點權值計算

權值決定負載服務器將任務分配給哪一個節點，負載服務器也是整個集群的人口。要實現集群最優負載均衡，調整權值非常必要。在實際生產環境中，服務器整體性能及服務器運行項目不會經常變動，只要預測的閾值入在正常范圍內，就不調整權值。因此，權值不會頻繁調整，保證了整個集群的穩定。

集群中節點權值根據集群中節點S_i的負載情況3l（S_i）及節點S_i的性能評估值計算得出，如式（4）所示。

權值評估針對每一個服務器節點，增加了項目對當前節點的資源消耗參數，這樣評估出的權值更加準確。準確的權值會使集群負載更加均衡，減少權值調整次數，進一步降低抖動發生概率，增強集群穩定性。

1.3 集群整體負載狀態計算

均衡的負載能夠使集群釋放出更好的性能，對提高集群并發量及業務處理能力有重要影響。節點服務器資源利用狀態是影響整個集群的基礎，其定義如下：

其中，U_i是服務器節點S_i=（i=1，2，……，n）的資源使用情況，SL（S_i）是當前節點服務器的負載情況，P（S_i）是當前節點服務器的綜合性能評估。

服務器資源使用情況標準差（Standard Deviation）用σ表示，可以很好地反映出當前集群負載的離散程度。σ值越小，整個集群負載平衡程度越好;反之，σ值越大，整個集群負載越不平衡，需重新計算負載權值。

2 預測閾值的動態權值負載均衡算法設計

算法主要部分是閾值預測，通過預測閾值可以在集群負載傾斜和負載超載之前對集群進行相應調整，同時閾值可以避免權值頻繁調整造成的服務器集群抖動。預測閾值通過預測CN并進一步計算得出。

2.1 預測CN（鏈接數）

用戶請求服務會產生一個或多個鏈接，在鏈接產生前預測鏈接信息，對掌握服務器性能及集群性能變化具有重要意義。通過預測值（preCN）可以計算出預測閾值入，并根據預測閾值讓集群提前作出相應調整。同時，也可將預測值（preCN）代人負載算法進行運算，通過負載算法輸出值對當前權值進行修正，使集群性能發揮到最大。

Web服務的服務器集群中，連接數變化呈周期性規律。為使預測算法對服務器資源的消耗盡可能小、通過預測模型對結果進行預測時盡可能迅速，選擇時間序列預測模型。

在Holt方法基礎上增加帶周期因子Holt-Winters方法。將鏈接到達的時間序列進行分割，整個序列有N個周期，每周期S個時隙，設其中某時隙為最小粒度。原始轉移方程如下：

其中，ψ_i（i=1，2，…，T）是第i時間間隙時連接數的統計值;A_i、B_i、C_i表示Holt-Winters中基線、線性趨勢和季節趨勢的因子;a、b、c是平滑因子，范圍是[0，1]。

2.2 閾值入計算

由于負載調度、節點信息收集等會消耗一定資源，這類資源的消耗在大量并發時微不足道，但在并發量很小時會增加負載。此時，引入一個閾值入用來反映集群負載狀態和集群當前負載的平衡程度，能夠使負載服務器在更加合適的時機調整集群中每個節點的負載。入定義如下：

其中，SL（S_i）是節點S_i的綜合負載情況，P（Server_i）表示節點S_i的整體性能評估，相關系數k₁+k₂=1，C_d是集群負載離散程度。閾值入范圍是（0，1]，該值能夠反映出當前服務器集群狀態。入越接近1，證明服務器集群當前負載越大;反之，則證明服務器集群當前負載較輕，如表l所示。

2.3 算法設計

集群由負載均衡服務器（LBS，Load Balance Server）負責調度。根據負載均衡服務器性能情況，具體可以分成兩種形式：一種是整套算法由負載均衡服務器負責，同時整個集群中的服務器向負載均衡服務器匯報;另一種是額外增加一臺負載控制服務器（Load Balance Control Server）負責負載算法，而負載均衡服務器只需負責任務分配即可。兩種方式根據實際情況設置，第一種方法實現簡單，同時節約成本，但是負載均衡服務器會承受更大壓力，比較適合LBS性能較好的情況;第二種方法可能會增加成本，但會減輕負載均衡服務器壓力，釋放LBS性能，比較適合LBS性能一般的情況。

負載算法實現如下：負載控制服務器向所有節點發送查詢請求，查詢各服務器的CPU、內存、磁盤I/0、帶寬等相關指標;同時，各節點也會向負載控制器匯報自身資源使用情況。這兩項工作并不是同時進行，具體由閾值以及服務器節點的負載情況SL聯合控制。當閾值較低時，說明整個集群負載較低，同時LBS負載較輕，或是有獨立節點（增加單獨負載控制服務器）時，由負載控制服務器向集群中的服務器節點收集信息。當集群閩值較高，且LBS負載較高時，集群中服務器定時向LBS服務器匯報，同時LBS計算閾值、負載平衡度、預測CN等，并根據結果選擇是否重新計算和更新權值。

當請求抵達時，負載節點依據權值進行調度。同時，負載控制器記錄該請求相關信息，如：處理時間、處理請求的服務器節點、服務器節點當前請求數CN_i等。如果某節點長時間不響應，控制服務器則將其設置為請求不可達。如果某節點已經過載，控制服務器則將其設置成過載態，負載調度時會越過此服務器，直到所有服務器都到達過載態。如果長時間處于這種狀態，則說明整個集群的服務器節點性能需要提高。

負載算法步驟如下：

（1）整個集群節點初始化，評估集群中的服務器，計算出初始P（Server_i），并初始化權值。

（2）控制服務器計算權值，并修改負載服務器的權值列表。

（3）收集服務器信息，統計CN_i并上報給控制服務器，每收集一定數量的數據控制服務器便更新R系數，重載P（serverl）。

（4）控制服務器每隔一段時間進行CN預測，得出preCN，進行模擬負載，得出預測集群離散度，并預測閾值入。如果入值在合理范圍內轉步驟（5），入值異常則轉步驟（2）。

（5）有新的請求到達時，負載服務器根據權值分配任務，任務下發前判斷當前節點負載狀態，如果超載，則跳過當前節點。下發成功后將結果上報給控制服務器。

（6）控制服務器接收或查詢整個集群中節點負載狀態，計算SL（serverl）并將結果傳給負載服務器。同時，計算集群當前離散度及閾值入，如果需要更新權值，則轉步驟（2），否則轉步驟（3）。當整個集群一直處于中低負載運行時，控制服務器將著重判斷集群離散度C_d。如果所有集群都處于超載狀態，控制服務器將通知負載服務器請求等待，直到有服務器退出超載狀態。

3 實驗驗證

3.1 仿真實驗平臺搭建

為了驗證算法，用8臺云主機搭建仿真實驗環境，分別是5臺業務邏輯節點，2臺數據庫節點，1臺負載服務器節點，并在該環境中對預測閾值的動態權值負載算法進行驗證分析。本文采用PTS（Performance Testing Service）性能壓測工具，它面向云化和分布式設計，更加適合現行主流技術架構。PTS可以模擬出大量用戶訪問業務的真實情景。

為了有效測出算法性能，采取并發模式進行施壓，同時使用設置上限每次增加10%的自動遞增模式，所有壓力采用國內公網IP進行壓測，最大程度地模擬真實環境。

由于控制服務器和負載服務器在同一臺機器上，因此采用由服務器節點向上匯報的方式，服務器節點根據當前節點負載變化頻率分為3個等級，最短5。匯報一次，最長15s向上匯報，如一個服務器超過20s沒有匯報，控制服務器將其設置成不可達。服務器集群中各節點配置如表2所示。

3.2 實驗結果分析

基于預測模型和獨立訓練節點的負載均衡算法（實驗組1）在處理負載均衡問題上具有較好效果，因此將本文算法（實驗組2）與其作對照實驗。同時，為了更加清晰地顯示實驗結果，還增加了普通的加權輪詢算法作為對照組

實驗過程中，在搭建好的仿真實驗平臺上分別運行本文預測閾值動態權值負載均衡算法與兩種對照算法。通過PTS壓測工具以每秒增加50的并發量進行壓測，每一次壓測5分鐘，每隔4s統計一次平均響應時間和當前集群狀態。結果如圖1所示。

從圖1可以看出，并發量提高，平均響應時間隨之上升。當并發量不是很高時，普通加權輪詢算法（對照組）與本文算法相差無幾，但是本文算法稍低于對照組，原因在于普通加權算法是憑借經驗設置權值，而本文是根據服務器狀態計算R值，并通過R值評估服務節點性能后計算權值。但是基于預測模型和獨立訓練節點的負載均衡算法（實驗組1）平均響應時間略高于本文算法和對照組，這是由于實驗組1的算法全程都有負載調度器參與，在低并發時，復雜算法增加了額外開銷。而本文算法由于增加了預測閾值入，在低并發時控制服務器并不參與，避免了額外的系統開銷，提升了響應速度。

在高并發時，對照組權值固定，每種請求對資源的需求不同，造成負載不均，使得響應時間增大。而實驗組1由于負載調度器的參與讓整個集群負載更加均衡從而使響應時間低于對照組。而本文算法由于權值是請求到達之前就已經確定好，因此在請求到來時避免了控制服務器運算，提升了平均響應時間。

4 結語

本文對復雜環境下的負載問題進行了深人研究，考慮到不同項目對資源占用情況不同和集群節點性能差異，提出了一種基于預測閾值的動態權值負載均衡算法。算法中的權值結合了項目對節點資源的消耗情況，通過負載離散度控制，保證了整個集群負載最優，又通過閾值對算法進行調節，綜合考慮了高并發和低并發兩種不同情況。最后的模擬實驗顯示，本文算法能減少響應時間，使整個集群負載更加平衡，負載效果較好。后續可分析不同任務對資源的消耗程度，將其進行量化，并結合任務訪問頻率作進一步研究。