基于預(yù)測閾值的動態(tài)權(quán)值負載均衡算法

李慧斌 何利力

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

關(guān)鍵詞：Holt-Winters預(yù)測;負載均衡;服務(wù)器集群;動態(tài)負載算法

DOI：10.11907/rjdk.192093 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

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

0 引言

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

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

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

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

1 集群狀態(tài)動態(tài)評估

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

1.1 節(jié)點性能動態(tài)評估

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

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

1.2 節(jié)點權(quán)值計算

權(quán)值決定負載服務(wù)器將任務(wù)分配給哪一個節(jié)點，負載服務(wù)器也是整個集群的人口。要實現(xiàn)集群最優(yōu)負載均衡，調(diào)整權(quán)值非常必要。在實際生產(chǎn)環(huán)境中，服務(wù)器整體性能及服務(wù)器運行項目不會經(jīng)常變動，只要預(yù)測的閾值入在正常范圍內(nèi)，就不調(diào)整權(quán)值。因此，權(quán)值不會頻繁調(diào)整，保證了整個集群的穩(wěn)定。

集群中節(jié)點權(quán)值根據(jù)集群中節(jié)點S_i的負載情況3l（S_i）及節(jié)點S_i的性能評估值計算得出，如式（4）所示。

權(quán)值評估針對每一個服務(wù)器節(jié)點，增加了項目對當前節(jié)點的資源消耗參數(shù)，這樣評估出的權(quán)值更加準確。準確的權(quán)值會使集群負載更加均衡，減少權(quán)值調(diào)整次數(shù)，進一步降低抖動發(fā)生概率，增強集群穩(wěn)定性。

1.3 集群整體負載狀態(tài)計算

均衡的負載能夠使集群釋放出更好的性能，對提高集群并發(fā)量及業(yè)務(wù)處理能力有重要影響。節(jié)點服務(wù)器資源利用狀態(tài)是影響整個集群的基礎(chǔ)，其定義如下：

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

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

2 預(yù)測閾值的動態(tài)權(quán)值負載均衡算法設(shè)計

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

2.1 預(yù)測CN（鏈接數(shù)）

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

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

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

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

2.2 閾值入計算

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

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

2.3 算法設(shè)計

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

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

當請求抵達時，負載節(jié)點依據(jù)權(quán)值進行調(diào)度。同時，負載控制器記錄該請求相關(guān)信息，如：處理時間、處理請求的服務(wù)器節(jié)點、服務(wù)器節(jié)點當前請求數(shù)CN_i等。如果某節(jié)點長時間不響應(yīng)，控制服務(wù)器則將其設(shè)置為請求不可達。如果某節(jié)點已經(jīng)過載，控制服務(wù)器則將其設(shè)置成過載態(tài)，負載調(diào)度時會越過此服務(wù)器，直到所有服務(wù)器都到達過載態(tài)。如果長時間處于這種狀態(tài)，則說明整個集群的服務(wù)器節(jié)點性能需要提高。

負載算法步驟如下：

（1）整個集群節(jié)點初始化，評估集群中的服務(wù)器，計算出初始P（Server_i），并初始化權(quán)值。

（2）控制服務(wù)器計算權(quán)值，并修改負載服務(wù)器的權(quán)值列表。

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

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

（5）有新的請求到達時，負載服務(wù)器根據(jù)權(quán)值分配任務(wù)，任務(wù)下發(fā)前判斷當前節(jié)點負載狀態(tài)，如果超載，則跳過當前節(jié)點。下發(fā)成功后將結(jié)果上報給控制服務(wù)器。

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

3 實驗驗證

3.1 仿真實驗平臺搭建

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

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

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

3.2 實驗結(jié)果分析

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

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

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

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

4 結(jié)語

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