基于硬件資源的加權輪詢算法研究

2020-08-21 17:21:37陳震廖濤

電腦知識與技術 2020年21期

陳震廖濤

摘要：隨著互聯網應用技術的快速發展，各大型網站的用戶規模也在急劇增長。由此帶來的集中式訪問，高并發等問題是Web服務器所面臨的一項巨大挑戰。使用負載均衡技術可以有效解決這一問題，但傳統負載均衡算法中的加權輪詢算法（Round-Robin，RR）是一種靜態算法，無法在服務運行中動態調整集群的負載情況。為解決這一問題，文章將RR算法加以改進，提出了一種新的算法：基于硬件資源的加權輪詢算法（Round-Robin Based on Hardware Resources.RRBHR）。該算法調用云監控EMS接口采集參數，在服務器間硬件異構性的基礎上，設立動態調整機制分配權重，最終達到可動態調整服務器集群負載的效果。對該算法進行了相關實驗，實驗結果得出，改造后的RRBHR算法在響應時間和吞吐量上都要優于之前的靜態算法。

關鍵詞：負載均衡;服務器集群;加權輪詢算法;高并發;動態分配權重

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2020）21-0072-04

開放科學（資源服務）標識碼（ OSID）：

1 背景

伴隨著互聯網應用技術的發展與完善，人們大多日常的辦公、通訊、出行、購物等都可以通過訪問網站來完成。這方便人們活動的同時也給網站服務器帶來了一個問題：隨著大批量用戶的請求量增多，網站服務器處理請求時的壓力也在不斷增大。在某些特殊的活動期間，如：節假日期間、商品的秒殺活動、雙十一購物節等，用戶短時間內對網站訪問量會驟然激增。在這種高并發、高集中式的訪問情況下，網站服務器需要在短時間內集中處理大批量請求，這會導致服務器的負載不斷增大。其中，硬件性能較差的服務器處理請求效率低，可能會造成大量的請求積壓，服務器負載會逐漸增大。在達到一定的閾值后，該服務器的性能可能會受到嚴重影響甚至崩潰，造成用戶請求超時失效。而其他性能好的服務器由于處理請求效率高，接收的請求會很快地處理掉，處于相對空閑狀態。為解決這一問題，增加服務器機器的數量，構建更多的集群來平均服務器的請求數是一種可行的辦法。但這種方法花費金額巨大并且會增加網站后期運維成本，并不經濟實用。此時，軟件層面上的負載均衡（LoadBalance）技術成為人們的突破點[1]。這種搭建在服務網絡架構上的負載均衡技術，可以有效地平攤高并發等問題帶來的壓力，均衡每臺服務器的負載。從而能夠維持各自服務器的性能，保障整個集群的運行穩定，是一種透明且廉價的方式，相比增加服務器集群數目更加靈活和經濟實用[2]。

傳統負載均衡算法可分為靜態算法（static algorithm）和動態算法（dynamic algorithm）兩大類。靜態負載均衡算法常見的有加權隨機算法，一致性哈希算法，輪詢算法和加權輪詢算法等。動態負載均衡算法常見的有最快響應算法，最小活躍數算法等。不同的負載均衡算法方案選擇，對服務器集群的影響也不相同。對此，一些相關研究和各種負載均衡優化方案被提了出來。文婷婷等人提出了一種彈性算法，根據概率分布和資源需求，設計了一種彈性虛擬機遷移的負載均衡算法[3]。汪佳文等人提出了動態自適應權重算法，結合改進后的Pick-k算法，能夠始終保證性能最優的節點提供服務[4]。王宇耕等人提出了基于負載預測的自適應算法，根據AR算法得出預測值的結果，調整服務器的權值[5]。張慧芳分析了加權最小連接數算法和IP隧道負載均衡技術，提出了一種可以根據動態反饋調整的算法[6]。王東提出了DWA算法，將Http請求分為事務性和發布性請求，對兩種狀態進行了分析后，根據DWA算法合理調整節點的任務調度進行負載[7]。

這些算法的研究，多數都是傾向于動態算法，在多數情況下，動態算法相對于靜態算法，在性能和靈活性等方面都要優于后者[8]。靜態負載均衡算法不考慮服務器的運行狀態[9]，其參數值是一開始就設定好的，以固定的權重分配任務。在程序運行過程中不會發生更改，即使運行過程中有服務器出現負載失衡，程序也會按照預先設定好的參數運行。動態負載均衡算法的參數值會根據程序運行時的環境不同，動態的調整更改參數信息，從而保障各個服務器的負載情況相似。

2 幾種靜態算法介紹與比較

普通輪詢算法[10]的算法思想是將收到的請求以輪流分配的方式分給各個服務器，其算法簡單，適用于服務器性能相近的情況。在實際的生產環境中，Weh集群的各個服務器的配置并不都是相同的，加權輪詢算法是對普通輪詢算法加以改進后的算法。在服務部署在服務器之前，開發人員會預先根據各個服務器配置性能不同，評估賦予不同的權值，使性能較好的服務器分配的權重大，性能弱的服務器分配的權重較小。通過權重調整各服務器處理的請求數，最終使得每個服務器總體處理的請求數大致等于預先分配的權重比，從而達到負載均衡的效果。加權隨機算法思想基于古典概率分布，加權隨機算法在服務啟動前，事先為每個服務器提供了相應的權值，使各臺服務運行中處理的請求數近似于它們權重的比例。加權隨機算法簡單高效，但在請求數較少時，其中多數請求會分配給權重較大的服務，可能出現請求傾斜的情況。一致性哈希算法是將服務器的IP地址或者其他信息作為依據，生成一個hash值投射到一定長度的hash環上。每當有新的請求時，根據算法，為其生成一個hash值，然后在hash環上查找出第一個大于或者等于該hash值的服務器節點，該請求會被投射在這個節點的服務器處理。以此分散服務器的請求，達到負載均衡的效果。

常見的衡量負載均衡算法的指標有響應時間和吞吐量。響應時間是指接受和處理一定數目請求所耗費的時間，本文中默認為單位為秒。吞吐量是單位時間內處理的請求數量。比較上述幾種靜態算法的性能，使用Postjson分別對加權隨機，加權輪詢，一致性哈希算法模擬進行500、1000、1500、2000、2500并發數的用戶請求，去除最大值和最小值后取平均值進行數據統計，如表1所示。

從表1中可以看出，隨著并發數的增加，三種算法的響應時間也逐漸增加，吞吐量趨于穩定。一致性哈希算法的響應時間高于另外兩種算法，可能是因為請求處理過程中，大量的時間消耗在哈希計算中之中，也導致吞吐量低于其他兩種算法。加權隨機算法和加權輪詢算法在響應時間和吞吐量上十分相似。由于加權輪詢算法的特性，不會出現少請求量的數據傾斜問題，且服務器硬件的異構性更契合于加權輪詢算法。將原本的靜態算法改進為動態算法會有更大的提升空間，文章提出了基于硬件資源的加權輪詢算法改進。

3 基于硬件資源的加權輪詢算法

3.1 算法思想

服務器處理請求的能力與它們當前硬件使用率息息相關，以這些硬件使用率作為負載因子，如：CPU利用率，內存使用率，磁盤使用率，網絡帶寬使用率等[11]，計算得出服務器的負載值Load（Si），作為評價服務器負載情況指標。并以每個服務器本身硬件參數為基礎，通過公式W（si）計算得出各個服務器權值。在程序運行過程中，周期性的用負載判斷公式O（Si）檢測整個集群的負載狀況。當某個服務器短時間處理請求數較大，負載較重出現負載不均時，動態的降低該服務器的權重以減少處理的請求數。當服務器處理請求數較少，處于相對空閑時，加大權重，增加處理請求數以提高整體效率。

3.2 算法模型建立

算法模型的建立需要考慮以下幾個問題：1）采集服務器各負載因子時，如何盡量減少對服務器的侵人性;2）各項硬件的權重該如何合理分配;3）怎樣把各服務器整體硬件配置的差異，抽象出來用數值化表現;4）如何判斷調整權重的時機及如何調整權重。

采集負載因子對運行中的系統來說，是一種額外的開銷，降低采集過程中對系統的侵人性有利于提高系統的性能。傳統采集方式有Perfmon檢測、Linux命令或向服務器植入程序等方式，這些方式會周期性的發送采集數據到數據庫或日志中，研究人員再取出數據進行分析，使用這些方法需要對數據進行二次處理分析且較為復雜。本實驗加入了阿里云開發工具包（Alibaba Cloud SDK for Java），使用RPC風格直接通過Http請求的方式，調用云監控的API采集數據。此種方法對服務器侵人性小且采集的數據不需要二次處理，可直接使用在算法中。

服務器運行過程中各項硬件使用率是實時變化的，硬件使用率越高，說明當前狀態下的服務器負載越高。將各個硬件參數的權重系數與負載因子乘積之和作為服務器Si的負載指標函數Load（Si），如公式（1）所示。服務器負載Load（Si）：

其中，k1+k2+k3+k4+k5=1。

k1代表相應硬件或指標的權重，表示該硬件在整個服務中的重要程度。L（Ci），L（Mi），L（Di），L（Ni）分別代表CPU使用率，內存使用率，磁盤使用率和帶寬使用率，L（LJ是Load average數值，是Linux系統特有的屬性。表示在一定時間間隔內，在CPU中運行列隊的平均進程數。服務器運行過程中，各硬件的使用率越高，負載值Load（Si）越大，說明當前服務器的負載狀況越高。

使用層次分析法（ Analytic Hierarchy Process）確定公式（1）中的k值。建立層次分析模型，如圖1所示：

在服務器硬件構成中，CPU負責大量的運算，是整個系統的核心。內存和網絡帶寬也是相對重要的部分，通過對比分析這些硬件的相對重要程度得出目標層對比表2。

服務器集群中各機器的配置并不是相同的，服務器的硬件配置越高，性能越好，處理請求的效率也就越高。本實驗選取4臺硬件配置各不相同的服務器，做了差異化處理，如表4所示。所有服務器的cpu型號皆為Intel⑩Xeon⑧系列。其中一臺服務器使用Nacos和Dubbo架構提供分布式系統的遠程過程調用（Remote Procedure Call.RPC）服務，以Nacos作為服務的注冊中心，結合Dubbo自身的容錯機制[12]呵保證服務的高可用性和可靠性[13]。其余服務器作為服務提供者，構成一個小型的服務器集群。

把服務器不同的硬件配置抽象出來，用具體的數值表示，得出服務器性能指數P（Si）。P（Si）用于衡量某個服務器在整個集群中的性能狀況。

服務器性能綜合指數P（S.）：

P（Si）= P（Ci）+ P（Mi）+ P（Ni）

（2）

其中，P（Ci）代表服務器i的CPU性能在整個集群中的性能比值，通過查閱資料可知：型號為Platinum 8269CY的CPU單核計算能力是型號為E5-2682 V4的CPU單核計算能力的1.7倍，可近似認為兩者CPU性能比值為1.7：1。同理，認為內存為IGiB的內存與2GiB內存的性能比值為1：2。以各項硬件性能比值之和作為評價服務器性能綜合指數P（Si），P（Si）越大代表該服務器的硬件配置越高，處理請求的速度越快，可承受的負載能力也越強。

在初始情況下，為每個服務器分配權重。初始權重的大小由服務器硬件性能指數和當前硬件剩余性能組成，通過公式（3）計算得出權重W（Si）。權重的大小代表著處理請求能力的大小，服務器性能越好，處理請求效率越高，所分配的權重應該越大。

服務器權重W（Si）：

P（ratio）代表某個服務器在集群中的性能比值，D（Si）是當前服務器的剩余性能。剩余性能的組成由各硬件剩余使用率和CPU空閑狀況構成。

采集服務器負載信息的常見方式有周期式和貪婪式[14j。周期式是每隔一定的時間段或次數采集服務器的信息，貪婪式是每次請求都收集信息，再進行任務分配。過于頻繁的收集、更新權值不但不會提高負載均衡能力，而且會對系統運行造成額外的負擔。本實驗使用周期式，引入了計數器i，每當服務器處理一次請求時，i加1，當i值達到某個閾值時，根據（6）的負載判斷公式判斷各服務器負載狀況，并把i重置為0。

負載判斷公式O（si）：

a是失衡指數，作為閾值來衡量負載失衡程度，代表著基于本身性能基礎上，該服務器負載失衡程度。O（si）的值越接近于0，說明當前服務器的負載狀況越好。設定a值為0.3，若O（si）值小于0，說明服務器的負載較為均衡，不用調整權重，若O（s.）值大于0，說明系統負載不均，需要調用公式（3）重新計算并分配權值。使用此種權重更新策略既不會對系統本身的運行造成太大的負擔，又能很好地均衡負載情況。

3.3 算法步驟與流程

算法執行的關鍵步驟如下：

第一步：使用Dubbo的RPC遠程服務調用方案，將服務注冊到Nacos上。構成可訪問的服務提供集群。

第二步：服務初始化，調用云監控EMS接口采集服務器參數，通過公式（3）為每個服務器分配初始權重w（s，）。

第三步：開始處理請求，并設置計數器i，i的值隨著處理的請求數增加而增大，i到達閾值時，通過公式（6）開始判斷當前服務器負載情況。

第四步：若O（si）值大于0，說明當前服務器負載不均，調用公式重新分配權重w（si）。若O（Si）小于0，說明服務器狀況良好，進行下一步。

第五步：計數器重新置為0，跳轉到第三步，直至所有請求處理完畢。

算法流程圖如圖2所示。

4 實驗結果與分析

把相同的服務分別部署到三臺硬件配置各不相同的服務器上，使用Nacos和Dubbo架構實現服務的發現與治理。用本地主機作為請求端模擬用戶高并發請求，訪問部署在服務器上的服務。

在上述相同的實驗環境下，對RR算法和改進后的RRBHR算法進行實驗，得出表6。從表6中可以看出，在不同并發數的情況下，RRBHR的響應時間都要小于RR算法，并且整體的吞吐量也有了約6%-10%左右的提升。根據實驗結果可以驗證改進后的RRBHR算法可以在一定程度上提升整體服務器集群的性能。

5 結束語

通過檢測服務器的硬件運行狀況來動態更改加權輪詢算法的權值，并設立了調整機制，減少了部分服務器由于負載不均造成壓力過大甚至癱瘓的風險，達到了優化服務器集群負載的效果。改進后的RRBHR算法在性能上優于原先的靜態加權輪詢算法，有了約6% -10%的提升。該算法尚有一點小的缺陷：人為設置的計數器i值過小時，會更頻繁調用云監控CMS的接口，可能會造成調用方法出錯，得不到準確的負載因子。計數器值過大時，可能會造成調整權重滯后。如何合理地設置計數器i以達到性能的最優，是值得進一步研究的地方。

參考文獻：

[1]羅擁軍，李曉樂，孫如祥.負載均衡算法綜述[J].科技情報開發與經濟，2008（23）： 134-136.

[2]胡利軍.Web集群服務器的負載均衡和性能優化[D].北京：北京郵電大學，2010.

[3]文婷婷，李洪赭，面向云服務平臺的彈性負載均衡算法[J].計算機與現代化，2019（10）： 28-33.

[4]汪佳文，王書培，徐立波，等.基于權重輪詢負載均衡算法的優化[J].計算機系統應用，2018，27（4）： 138-144.

[5]王宇耕，肖鵬，張力，等.基于負載預測的自適應權值負載均衡算法[J].計算機工程與設計，2019，40（4）： 1033-1037.

[6]張慧芳，基于動態反饋的加權最小連接數服務器負載均衡算法研究[Dl.上海：華東理工大學，2013.

[7]王東.動態反饋負載均衡策略的研究[D].哈爾濱：哈爾濱工程大學，2018.

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

[9]覃川.基于Nginx的Web服務器負載均衡策略改進與實現[D].成都：西南交通大學，2017.

[10]彭云亞.網格服務的動態分布式策略負載均衡的研究與實現[D].北京：北京交通大學，2008.

[11]高振斌，潘亞辰，華中，等.改進的基于加權最小連接數的負載均衡算法[J].科學技術與工程，2016，16（6）： 81-85.