改進加權輪詢負載均衡算法研究

韓朋花，葉青，姜曉明，陳占芳

（長春理工大學 計算機科學技術學院，長春 130022）

在云計算環境下，出現了云存儲安全［1］、數據挖掘［2，3］、負載均衡［4］等技術。因為負載均衡技術能夠滿足人們對計算機處理速度的要求，負載均衡算法是影響負載均衡技術的重要因素之一，所以對負載均衡算法的相關研究非常重要。負載均衡算法有很多，常見的負載均衡算法可以分為兩種，一種是靜態的負載均衡算法，主要包括：輪詢算法、加權輪詢算法、目標地址散列算法、源地址散列算法等［5］。另一種是動態的負載均衡算法，主要包括：最小鏈接算法、加權最小鏈接算法、基于位置的最小連接算法、帶復制的基于位置的最小連接算法等［6，7］。本文主要介紹輪詢算法和加權輪詢算法，通過實時監測負載因子的狀態，動態的計算服務器的權值，進而對加權輪詢算法進行改進，運用負載測試工具Load-Runner進行性能測試。

1 經典算法

1.1 輪詢算法（Round Robin）

輪詢算法是以輪詢的方式，將請求分配到不同的服務器上。輪詢算法的優點是實現簡單，不需要記錄當前的連接狀態，是一種無狀態的算法。

輪詢算法是在假設服務器不存在差異的情況下，相對簡單，不適用于服務器的配置性能不一樣的情況，當請求服務器時間變化較大時，容易導致發生服務器間負載不均衡的現象。

1.2 加權輪詢算法（Weighted Round Robin）

加權輪詢算法是對輪詢算法的改進，用權值來表示服務器之間存在的差異，權值高的服務器分配的任務多，權值低的服務器分配的任務少。

加權輪詢算法解決了服務器之間存在差異的問題，實現相對簡單，不需要記錄當前的連接狀態，是一種無狀態連接。但是，權值是人為設置的，不能夠動態的反應服務器之間的差異。

2 基于動態反饋的加權輪詢算法

2.1 改進算法設計思想

服務器實時的負載就是一個動態的二維數據［8］，它是由服務器中負載因子的利用率和對應的權值相乘得到的。鑒于此，改進的算法思路如下：一定的時間周期內（如T=10s）收集一次服務器的負載因子的值（這些負載因子的值是動態變化的），根據收集到的負載因子的值，首先將這些負載因子的值和對應設定的閾值進行比較，在收集到的負載因子值小于對應設定閾值的情況下，計算各個服務器的處理能力極值和每個服務器的實時負載值，這兩個值相比得到一個值，這個值叫做負載率。如果負載率小于負載率閾值，計算當前服務器的權值，根據權值進行輪詢處理請求任務。

根據計算出的服務器的權值求出權值比，代表了服務器能夠處理任務的權值比，這個比值能夠很好地代表當前服務器的性能。這個比值不包含負載率大于等于閾值（Y）的服務器，根據這個比值確定服務器的權值，可以確保服務器的正常運行。

設置閾值（Y）還有一個作用，可以給負載過重的服務器一個緩沖時間，這樣就能夠避免這臺服務器既要處理任務隊列中的任務，又要接受新的任務從而導致這臺服務器宕機。

改進算法工作模型如圖1所示?？蛻舳讼蚍掌靼l送請求的時候，請求先被發送到負載均衡服務器，負載均衡服務器對服務器進行實時反饋負載狀態（負載因子的信息），然后負載均衡服務器把請求根據權值輪詢的分配到服務器，服務器處理完成請求之后，把結果直接發送到客戶端。

圖1 改進算法工作模型

2.2 改進算法流程

改進算法需要解決以下幾個問題：①時間周期（T）是多少；②采集那些參數（負載因子）能實時反映服務器的性能；③如何采集這些負載因子；

考慮到負載因子的收集對系統來說是一種開銷［9］，因此過多的負載因子反而達不到資源的有效利用，本文涉及到的負載因子為CPU的處理能力、內存容量的大小、網絡帶寬大小。對于時間周期來說，較長的時間周期不利于服務器的負載均衡，較短的時間周期要頻繁的收集負載因子的值，影響算法的效率，所以本文的時間周期是10s（T=10s）。

在Linux系統的內核中，有一個全局變量記錄時間：Jiffies（單位：10-2）。CPU的利用率根據執行用戶和系統的Jiffies除以Jiffies的總數表示。

在Linux系統中，采集文件/proc/stat的第一行信息，能得到CPU的用戶態、系統態、空閑態等不用狀態下的Jiffies。通過命令：cat/proc/stat獲取CUP的使用情況。

為了計算CPU的利用率，以時間周期的開始位置和結束位置為樣點，計算它們的差值。

CPU的利用率：

其中，i表示第i臺服務器（以下同理），L(ci)表示服務器CPU的利用率，Δu表示兩樣點之間用戶態的差值，Δs表示兩樣點之間內存系統的差值，Δj表示兩樣點之間CUP利用率的差值。

在Linux系統中，采集文件/proc/meminfo的前四行信息，能得到內存的使用情況。通過命令：cat/proc/meminfo獲取內存的使用情況。

內存的利用率：

其中，L(mi)表示服務器內存的利用率，memtotal表示內存，memfree表示空閑內存。

在Linux系統中，采集文件/proc/net/dev的第四行記錄，能得到帶寬的使用情況，通過命令：cat/proc/net/dev獲取帶寬的使用情況。

帶寬的利用率：

其中，L(ni)表示服務器帶寬的利用率，ΔR表示兩樣點之間接受帶寬的差，ΔT表示兩樣點之間傳送帶寬的差，Δt表示一個時間周期，totalBW表示網口帶寬，服務器采用eth0網口，帶寬為100Mbps。

2.3 改進算法步驟

改進算法執行步驟如下：

第一步：收集負載因子的值；

第二步：將各個負載因子的值和對應的閾值進行比較，若存在L(ci)＞Y(ci)、L(mi)＞Y(mi)或者L(ni)＞Y(ni)，將這臺服務器的權值設置為0，這個周期內不再對這臺服務器分配任務，否則根據負載因子的權重向量T(i)計算服務器實時負載M(i)的值；

第三步：計算服務器處理能力極值N(i)和服務器實時負載率R(i)的值；

第四步：將各個服務器R(i)的值和服務器對應的閾值Y(i)進行比較，若R(i)＞Y(i)，將這臺服務器的權值設置為0，否則進行下一步；

第五步：計算服務器計算權值C(i)，并根據服務器的權值W(i)計算服務器真實分配權值CW(i)的值；

第六步：計算服務器之間真實分配權值CW(i)的比，得到服務器的權值，根據這個權值輪詢分配任務。

其中，Y(ci)，Y(mi)，Y(ni)分別表示服務器CPU、內存和網絡的閾值，Y(i)表示服務器的閾值，N(i)表示服務器處理能力極值，M(i)表示服務器實時負載，R(i)表示服務器實時負載率，T(i)表示各個負載因子的權重向量，W(i)表示服務器的權重。

2.4 改進算法涉及公式

服務器處理能力極值：

其中，P(i)=[P(ci),P(mi),P(ni)]，P(ci),P(mi),P(ni)分別表示服務器CPU處理速度，內存大小，網絡吞吐量。T(i)=[T(c),T(m),T(n)]，T(c),T(m),T(n)分別表示CPU、內存和網絡的權值，且它們的和為1。

服務器實時負載的值：

其中，L(i)=[L(ci),L(mi),L(ni)]，L(ci),L(mi),L(ni)分別表示服務器CPU、內存和網絡的利用率。

服務器實時負載率：

服務器計算權值：

其中，，n表示服務器數量，由于R都一樣并且除法計算速度比較慢，所以上式優化為C(i)=R-R(i)。

當兩個服務器的C(i)值一樣時，只能代表這臺服務器的處理能力，并不能代表這臺服務器在所有服務器中的處理能力，為了解決這種問題，為服務器設置權值W(i)。

服務器真實分配權值：

3 實驗結果及分析

通過對大量用戶同時并發請求訪問進行模擬，使用負載測試工具LoadRunner實時進行監測［10］，分別進行六次測試，得到改進前后的算法關于系統平均響應時間的對比，如圖2。

圖2 系統平均響應時間

由圖2可知，改進后算法的系統平均響應時間明顯提高，平均提高了140ms左右。由于改進后算法的權值是根據服務器的負載情況求出的，更能夠反應出服務器的負載情況，有效的利用服務器等資源，因此改進后的算法在系統平均響應時間上得到了明顯的提高。

4 結語

改進前加權輪詢算法的權值是人為設定的，不能夠實時反應服務器的差異。改進后加權輪詢算法的權值是根據服務器運行期間負載因子計算的，是動態的改變的，所以能夠更真實地反應服務器的負載差異，符合負載均衡的要求，優化了加權輪詢算法，使算法得到了較大的改進。但是一定周期采集負載因子的值，會帶來一定的額外開銷，在今后的研究中，還需要對改進后加權輪詢算法不斷的改進和完善。

［1］從立鋼，郭利菊.云存儲系統安全技術研究［J］.長春理工大學學報：自然科學版，2014，37（03）：132-134.

［2］王鵬，王健安，郭暢，等.基于云計算及數據挖掘技術的海量數據處理研究［J］.長春理工大學學報：自然科學版，2013，36（06）：157-160.

［3］巴濟慈.基于云計算的海量數據挖掘處理與研究［D］.長春：長春理工大學，2013.

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

［5］王以山.數字皮影表演中負載均衡問題的研究與應用［D］.北京：北京工業大學，2010.

［6］RadojevicB，ZagarM.AnalysisofIssueswith Load Balancing Algorithms in Hosted（Cloud）Environments［C］.Opatija MIPRO.2011：416-420.

［7］莊旻軒.服務器集群中基于動態反饋的負載均衡算法［D］.大連：大連理工大學，2014.

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

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

［10］蔡程宇，婁淵勝.改進加權最小連接數負載均衡調度算法研究［J］.哈爾濱商業大學學報：自然科學版，2015，31（01）：102-104.