改進(jìn)加權(quán)輪詢負(fù)載均衡算法研究

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

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

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

1 經(jīng)典算法

1.1 輪詢算法（Round Robin）

輪詢算法是以輪詢的方式，將請求分配到不同的服務(wù)器上。輪詢算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，不需要記錄當(dāng)前的連接狀態(tài)，是一種無狀態(tài)的算法。

輪詢算法是在假設(shè)服務(wù)器不存在差異的情況下，相對簡單，不適用于服務(wù)器的配置性能不一樣的情況，當(dāng)請求服務(wù)器時間變化較大時，容易導(dǎo)致發(fā)生服務(wù)器間負(fù)載不均衡的現(xiàn)象。

1.2 加權(quán)輪詢算法（Weighted Round Robin）

加權(quán)輪詢算法是對輪詢算法的改進(jìn)，用權(quán)值來表示服務(wù)器之間存在的差異，權(quán)值高的服務(wù)器分配的任務(wù)多，權(quán)值低的服務(wù)器分配的任務(wù)少。

加權(quán)輪詢算法解決了服務(wù)器之間存在差異的問題，實(shí)現(xiàn)相對簡單，不需要記錄當(dāng)前的連接狀態(tài)，是一種無狀態(tài)連接。但是，權(quán)值是人為設(shè)置的，不能夠動態(tài)的反應(yīng)服務(wù)器之間的差異。

2 基于動態(tài)反饋的加權(quán)輪詢算法

2.1 改進(jìn)算法設(shè)計(jì)思想

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

根據(jù)計(jì)算出的服務(wù)器的權(quán)值求出權(quán)值比，代表了服務(wù)器能夠處理任務(wù)的權(quán)值比，這個比值能夠很好地代表當(dāng)前服務(wù)器的性能。這個比值不包含負(fù)載率大于等于閾值（Y）的服務(wù)器，根據(jù)這個比值確定服務(wù)器的權(quán)值，可以確保服務(wù)器的正常運(yùn)行。

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

改進(jìn)算法工作模型如圖1所示?？蛻舳讼蚍?wù)器發(fā)送請求的時候，請求先被發(fā)送到負(fù)載均衡服務(wù)器，負(fù)載均衡服務(wù)器對服務(wù)器進(jìn)行實(shí)時反饋負(fù)載狀態(tài)（負(fù)載因子的信息），然后負(fù)載均衡服務(wù)器把請求根據(jù)權(quán)值輪詢的分配到服務(wù)器，服務(wù)器處理完成請求之后，把結(jié)果直接發(fā)送到客戶端。

圖1 改進(jìn)算法工作模型

2.2 改進(jìn)算法流程

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

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

在Linux系統(tǒng)的內(nèi)核中，有一個全局變量記錄時間：Jiffies（單位：10-2）。CPU的利用率根據(jù)執(zhí)行用戶和系統(tǒng)的Jiffies除以Jiffies的總數(shù)表示。

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

為了計(jì)算CPU的利用率，以時間周期的開始位置和結(jié)束位置為樣點(diǎn)，計(jì)算它們的差值。

CPU的利用率：

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

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

內(nèi)存的利用率：

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

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

帶寬的利用率：

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

2.3 改進(jìn)算法步驟

改進(jìn)算法執(zhí)行步驟如下：

第一步：收集負(fù)載因子的值；

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

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

第四步：將各個服務(wù)器R(i)的值和服務(wù)器對應(yīng)的閾值Y(i)進(jìn)行比較，若R(i)＞Y(i)，將這臺服務(wù)器的權(quán)值設(shè)置為0，否則進(jìn)行下一步；

第五步：計(jì)算服務(wù)器計(jì)算權(quán)值C(i)，并根據(jù)服務(wù)器的權(quán)值W(i)計(jì)算服務(wù)器真實(shí)分配權(quán)值CW(i)的值；

第六步：計(jì)算服務(wù)器之間真實(shí)分配權(quán)值CW(i)的比，得到服務(wù)器的權(quán)值，根據(jù)這個權(quán)值輪詢分配任務(wù)。

其中，Y(ci)，Y(mi)，Y(ni)分別表示服務(wù)器CPU、內(nèi)存和網(wǎng)絡(luò)的閾值，Y(i)表示服務(wù)器的閾值，N(i)表示服務(wù)器處理能力極值，M(i)表示服務(wù)器實(shí)時負(fù)載，R(i)表示服務(wù)器實(shí)時負(fù)載率，T(i)表示各個負(fù)載因子的權(quán)重向量，W(i)表示服務(wù)器的權(quán)重。

2.4 改進(jìn)算法涉及公式

服務(wù)器處理能力極值：

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

服務(wù)器實(shí)時負(fù)載的值：

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

服務(wù)器實(shí)時負(fù)載率：

服務(wù)器計(jì)算權(quán)值：

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

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

服務(wù)器真實(shí)分配權(quán)值：

3 實(shí)驗(yàn)結(jié)果及分析

通過對大量用戶同時并發(fā)請求訪問進(jìn)行模擬，使用負(fù)載測試工具LoadRunner實(shí)時進(jìn)行監(jiān)測［10］，分別進(jìn)行六次測試，得到改進(jìn)前后的算法關(guān)于系統(tǒng)平均響應(yīng)時間的對比，如圖2。

圖2 系統(tǒng)平均響應(yīng)時間

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

4 結(jié)語

改進(jìn)前加權(quán)輪詢算法的權(quán)值是人為設(shè)定的，不能夠?qū)崟r反應(yīng)服務(wù)器的差異。改進(jìn)后加權(quán)輪詢算法的權(quán)值是根據(jù)服務(wù)器運(yùn)行期間負(fù)載因子計(jì)算的，是動態(tài)的改變的，所以能夠更真實(shí)地反應(yīng)服務(wù)器的負(fù)載差異，符合負(fù)載均衡的要求，優(yōu)化了加權(quán)輪詢算法，使算法得到了較大的改進(jìn)。但是一定周期采集負(fù)載因子的值，會帶來一定的額外開銷，在今后的研究中，還需要對改進(jìn)后加權(quán)輪詢算法不斷的改進(jìn)和完善。

［1］從立鋼，郭利菊.云存儲系統(tǒng)安全技術(shù)研究［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，37（03）：132-134.

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

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

［4］羅擁軍，李曉樂，孫如祥.負(fù)載均衡算法綜述［J］.科技情報(bào)開發(fā)與經(jīng)濟(jì)，2008，（23）：134-136.

［5］王以山.數(shù)字皮影表演中負(fù)載均衡問題的研究與應(yīng)用［D］.北京：北京工業(yè)大學(xué)，2010.

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

［7］莊旻軒.服務(wù)器集群中基于動態(tài)反饋的負(fù)載均衡算法［D］.大連：大連理工大學(xué)，2014.

［8］張慧芳.基于動態(tài)反饋的加權(quán)最小連接數(shù)服務(wù)器負(fù)載均衡算法研究［D］.上海：華東理工大學(xué)，2013.

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

［10］蔡程宇，婁淵勝.改進(jìn)加權(quán)最小連接數(shù)負(fù)載均衡調(diào)度算法研究［J］.哈爾濱商業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，31（01）：102-104.