佘 鵬

（武漢郵電科學(xué)研究院 武漢 430000）

1 引言

1.1 LVS集群系統(tǒng)及其相關(guān)算法

隨著Internet的的飛速發(fā)展與普及，人們對(duì)網(wǎng)絡(luò)的依賴與需求量呈現(xiàn)爆炸式的增長(zhǎng)，隨之而來(lái)的就是人們對(duì)網(wǎng)絡(luò)服務(wù)需求的與質(zhì)量的提高，為了滿足大多數(shù)人能夠正常地訪問(wèn)以及保證自身網(wǎng)絡(luò)服務(wù)的穩(wěn)定與高效，大多數(shù)網(wǎng)絡(luò)服務(wù)商要采用集群技術(shù)。Web集群技術(shù)通常是指將分散的，獨(dú)立的計(jì)算機(jī)通過(guò)一定的局域網(wǎng)或者廣域網(wǎng)連接在一起完成單個(gè)計(jì)算機(jī)（服務(wù)器）節(jié)點(diǎn)不能完成的任務(wù)。負(fù)載均衡技術(shù)是Web服務(wù)器集群的關(guān)鍵技術(shù)之一，主要是用來(lái)將客戶的服務(wù)請(qǐng)求按照規(guī)定的方法分發(fā)到服務(wù)器集群中的每一個(gè)服務(wù)器節(jié)點(diǎn)，這種規(guī)定的方法就是本文研究的負(fù)載均衡算法，主要分為靜態(tài)調(diào)度算法、動(dòng)態(tài)調(diào)度算法、自適應(yīng)調(diào)度算法。

1.2 LVS集群系統(tǒng)

LVS是Linux Viual Server的縮寫，是一個(gè)虛擬服務(wù)器集群系統(tǒng)，LVS集群通常是通過(guò)局域網(wǎng)或者廣域網(wǎng)，將不同的服務(wù)器連接起來(lái)，外部用戶無(wú)法直接訪問(wèn)每一臺(tái)服務(wù)器節(jié)點(diǎn)，而是通過(guò)LVS集群提供的一個(gè)虛擬IP（VIP）來(lái)訪問(wèn)，這個(gè)虛擬IP是在LVS的前端負(fù)載均衡器上配置好的，負(fù)載均衡器也是一臺(tái)服務(wù)器，但是它與其他服務(wù)器不同的地方在于它需要設(shè)置好負(fù)載均衡算法（調(diào)度算法）并且負(fù)責(zé)接收外部服務(wù)請(qǐng)求，然后通設(shè)定好的算法將這些請(qǐng)求分發(fā)到服務(wù)器集群中的一臺(tái)服務(wù)器節(jié)點(diǎn)，自身并不處理請(qǐng)求。

1.3 LVS相關(guān)算法

LVS已經(jīng)實(shí)現(xiàn)的調(diào)度算法算法有八種：1）輪叫；2）加權(quán)輪叫；3）最少鏈接；4）加權(quán)最少鏈接；5）基于局部的最少鏈接；6）帶復(fù)制的基于局部性的最少鏈接；7）帶復(fù)制的基于局部性的最少鏈接；8）源地址散列；9）最短期望延遲；10）無(wú)須隊(duì)列等待。

LVS集群的已實(shí)現(xiàn)的這十種調(diào)度算法算法根據(jù)實(shí)現(xiàn)的特點(diǎn)可以分為兩種：動(dòng)態(tài)算法和靜態(tài)算法。靜態(tài)調(diào)度算法指的是事先設(shè)計(jì)好的調(diào)度策略，由負(fù)載均衡器來(lái)運(yùn)行該算法策略，完成對(duì)客戶請(qǐng)求的調(diào)度分配。動(dòng)態(tài)調(diào)度算法是需要分析和獲取服務(wù)器節(jié)點(diǎn)的相關(guān)信息，然后將這些信息帶入調(diào)度算法中合理的分配請(qǐng)求。靜態(tài)算法相對(duì)于動(dòng)態(tài)算法的優(yōu)勢(shì)主要是靜態(tài)算法的響應(yīng)時(shí)間是最少的，因?yàn)樗恍枰紤]服務(wù)器節(jié)點(diǎn)與負(fù)載均衡之間的通信與獲取服務(wù)器節(jié)點(diǎn)信息的額外開銷，但是相對(duì)的，資源利用能力就比較差了，因?yàn)樗峙淙蝿?wù)的方式是固定的，這就意味著一些服務(wù)器可能會(huì)分配的任務(wù)過(guò)少，處于閑置狀態(tài)，一些服務(wù)器分配的任務(wù)過(guò)多，處于過(guò)載狀態(tài)。對(duì)于動(dòng)態(tài)算法，服務(wù)器會(huì)根據(jù)服務(wù)器的負(fù)載信息來(lái)重新分配任務(wù)，所以有更好的資源利用能力。

2 WLC算法的分析與改進(jìn)

2.1 WLC算法

在現(xiàn)有的LVS集群系統(tǒng)的八種負(fù)載均衡算法中，加權(quán)最少鏈接算法（WLC）是所有算法中相對(duì)來(lái)說(shuō)效率與實(shí)用性比較高的，該算法是最小鏈接算法的改進(jìn)，算法的核心是：為每個(gè)服務(wù)器設(shè)置一個(gè)權(quán)值Wi，這個(gè)值代表服務(wù)器的性能，權(quán)值越大的性能越好。當(dāng)負(fù)載均衡器分配請(qǐng)求時(shí)，會(huì)在所有服務(wù)器鏈表中在尋找Wi不為零的情況下連接數(shù)與權(quán)值比值最小的服務(wù)器節(jié)點(diǎn)，如果找不到服務(wù)器節(jié)點(diǎn)，則會(huì)返回NULL。

算法的基本實(shí)現(xiàn)：假如一組服務(wù)器用｛S0，S1，S2…，Sn-1｝表示，W（Si）表示服務(wù)器節(jié)點(diǎn) Si的權(quán)值，C（Si）表示服務(wù)器節(jié)點(diǎn)Si的當(dāng)前連接數(shù)，那么服務(wù)器當(dāng)前的鏈接總數(shù)為Csum= ∑C（Si），（i=0，1，2…，n-1），負(fù)載均衡器從集群中選擇的節(jié)點(diǎn)為Sm，那么服務(wù)器節(jié)點(diǎn)應(yīng)當(dāng)滿足下面條件：

公式中Csum是一個(gè)常量，所以公式可以簡(jiǎn)化為

由于服務(wù)器池中的每個(gè)服務(wù)器節(jié)點(diǎn)的權(quán)值都大于零，并且除法運(yùn)算對(duì)性能的消耗要大于乘法運(yùn)算，所以公式可以寫成

負(fù)載均衡器接收到請(qǐng)求任務(wù)后，加權(quán)最小鏈接算法的節(jié)點(diǎn)選擇過(guò)程如下：

圖1 加權(quán)最小連接調(diào)度算法

2.2 WLC算法存在的問(wèn)題

WLC算法雖然好處很多，但是也具有自身的局限性：1）權(quán)值的配置完全是由管理員配置的，不是由服務(wù)器節(jié)點(diǎn)的自身負(fù)載狀況決定的，當(dāng)系統(tǒng)管理員發(fā)現(xiàn)權(quán)值不合理時(shí)，必須要不斷地調(diào)整權(quán)值。并且完全依賴管理員的經(jīng)驗(yàn)配置權(quán)值有可能導(dǎo)致服務(wù)器的效率，進(jìn)而影響整個(gè)服務(wù)器集群的效率。2）一旦一個(gè)服務(wù)器設(shè)定了一個(gè)權(quán)值，盡管權(quán)值是根據(jù)每個(gè)服務(wù)器節(jié)點(diǎn)的性能來(lái)分配的，但是隨著隨之權(quán)值大的服務(wù)器分配的任務(wù)增多，服務(wù)器的性能會(huì)有所下降，如果繼續(xù)給權(quán)值大的服務(wù)器分配任務(wù)則有可能導(dǎo)致負(fù)載，所以權(quán)值應(yīng)該隨著服務(wù)器的性能改變而改變，本文提出了一種動(dòng)態(tài)改變權(quán)值的的思想。

2.3 WLC算法的優(yōu)化

本文針對(duì)WLC算法存在的一些問(wèn)題，提出了一種新的動(dòng)態(tài)權(quán)值分配算法：即每個(gè)服務(wù)器子節(jié)點(diǎn)周期性獲取自身的負(fù)載狀況，并與負(fù)載機(jī)端建立udp連接發(fā)送這些負(fù)載信息，負(fù)載均衡器根據(jù)每個(gè)服務(wù)器節(jié)點(diǎn)的負(fù)載信息來(lái)動(dòng)態(tài)調(diào)整權(quán)值。為了確保算法的準(zhǔn)確性，需要根據(jù)服務(wù)器節(jié)點(diǎn)的一些性能參數(shù)來(lái)動(dòng)態(tài)調(diào)整權(quán)值，在信息的采集和參數(shù)的處理中，必然的要產(chǎn)生額外的開銷，如果對(duì)系統(tǒng)性能的改進(jìn)不能優(yōu)于帶來(lái)的額外開銷，會(huì)更容易導(dǎo)致服務(wù)器的過(guò)載。所以在優(yōu)化算法中，盡量不要選擇過(guò)多的參數(shù)，因此只采用CPU利用率，內(nèi)存利用率，以及帶寬利用率三個(gè)參數(shù)來(lái)確定服務(wù)器節(jié)點(diǎn)的真實(shí)負(fù)載情況。

優(yōu)化算法中后端真實(shí)服務(wù)器獲取到自身的性能參數(shù)后，計(jì)算出新的權(quán)值，并周期性地發(fā)送給負(fù)載均衡器，負(fù)載均衡器接收到新的權(quán)值后，根據(jù)服務(wù)器節(jié)點(diǎn)的IP用新的權(quán)值代替舊的權(quán)值。這種頻繁的寫入會(huì)影響負(fù)載均衡器的性能，進(jìn)而影響任務(wù)的分配。通常而言，服務(wù)器節(jié)點(diǎn)的處理能力在短周期內(nèi)不會(huì)變化很大，所以沒(méi)有必要頻繁寫入權(quán)值，所以我們?cè)趦?yōu)化算法中引入了一個(gè)權(quán)值變化最小值（邊界值）B，當(dāng)權(quán)值的變化大于最小值（邊界值）B的時(shí)候，原始的權(quán)值才會(huì)被替換。

我們還是用S0，S1，S2，…，Sn-1來(lái)表示集群中的服務(wù)器節(jié)點(diǎn)，W（Si）表示權(quán)值，用 CPU_USE，MEM_USE，BAND_USE三個(gè)參數(shù)分別表示服務(wù)器節(jié)點(diǎn)的CPU利用率，內(nèi)存利用率和網(wǎng)絡(luò)帶寬利用率。僅僅有了三個(gè)負(fù)載參數(shù)還不夠，每個(gè)參數(shù)還應(yīng)有不同的重要程度，所以根據(jù)它們對(duì)服務(wù)器的影響程度還要設(shè)置三個(gè)影響因子：Kcpu，Kmem，Kband，這三個(gè)因子應(yīng)該是常量，實(shí)現(xiàn)就應(yīng)該規(guī)定好，本文將他們的值設(shè)為 Kcpu=0.5，Kmem=0.3，Kband=0.2進(jìn)行后面的測(cè)試。因此，新的權(quán)值表示式表達(dá)函數(shù)為：

公式中A是一個(gè)權(quán)值改變的調(diào)節(jié)參考系數(shù)，由于IPVS中權(quán)值不能分配成小數(shù)，否則系統(tǒng)會(huì)報(bào)ille?gal weight specific的錯(cuò)誤，所以本文將它設(shè)置為10。這個(gè)數(shù)值可以根據(jù)系統(tǒng)的需要設(shè)置得更大，但是這樣做會(huì)有一個(gè)不好的影響就是CPU利用率，或者內(nèi)存利用率，網(wǎng)絡(luò)帶寬利用率只要有一點(diǎn)改變，整個(gè)權(quán)值的改變就會(huì)非常大，所以為了更加準(zhǔn)確與合理，把A的值取10。

考慮新權(quán)值L的取值情況，當(dāng)服務(wù)器的負(fù)載所占比重值都為1時(shí)，表示系統(tǒng)處于滿載狀態(tài)，根據(jù)公司計(jì)算出來(lái)的權(quán)值L為0，此時(shí)負(fù)載均衡器將不會(huì)分配任務(wù)給這臺(tái)服務(wù)器。當(dāng)服務(wù)器處于空閑狀態(tài)，則每個(gè)參數(shù)值均為0，新的權(quán)值計(jì)算出來(lái)為10。所以以上公式中L的取值范圍為［0，10］。

處于服務(wù)器的真是狀況考慮，當(dāng)影響服務(wù)器性能的三個(gè)參數(shù) CPU_USE，MEM_USE，BAND_USE中任何一個(gè)參數(shù)達(dá)到了一定的繁忙程度，其他兩項(xiàng)無(wú)論處于什么狀態(tài)，都不應(yīng)該繼續(xù)給該服務(wù)器分配任務(wù)，否則將導(dǎo)致服務(wù)器無(wú)法有效的處理客戶請(qǐng)求從而影響集群系統(tǒng)的整體性能。所以當(dāng)這三個(gè)參數(shù)種任何一個(gè)大于0.9時(shí)，都需要將權(quán)值設(shè)置為0，以避免服務(wù)器節(jié)點(diǎn)過(guò)載甚至宕機(jī)。

本文將負(fù)載均衡器獲與服務(wù)器端交互的周期T設(shè)置為10s，即服務(wù)器每10s都會(huì)根據(jù)自身的負(fù)載情況計(jì)算出新的權(quán)值發(fā)送到負(fù)載均衡器端，負(fù)載均衡器除了轉(zhuǎn)發(fā)客戶端的請(qǐng)求之外，還要每隔10s更新一次所有服務(wù)器的權(quán)值，這樣無(wú)疑會(huì)使得負(fù)載均衡器的負(fù)擔(dān)過(guò)重，不利于提高集群系統(tǒng)的性能。因此應(yīng)當(dāng)有一個(gè)邊界值B來(lái)控制是否更新權(quán)值，此時(shí)將邊界值B代入可以得到權(quán)值的式子為

顯然，這個(gè)最小值B的取值代表著對(duì)改進(jìn)算法的有效評(píng)估值，B的取值越小，新權(quán)值寫入IPVS的頻率越高，如果B的取值為零，那么每一次的服務(wù)器節(jié)點(diǎn)返回的權(quán)值都滿足條件，那么每次服務(wù)器節(jié)點(diǎn)返回的權(quán)值都會(huì)寫入到IPVS調(diào)度，如果B的取值為1，那么新的權(quán)值永遠(yuǎn)不滿足條件，IPVS不會(huì)做出任何改變，保持原來(lái)的調(diào)度方式。本文中將B取值設(shè)為5。

所以，動(dòng)態(tài)權(quán)值反應(yīng)了當(dāng)前服務(wù)器節(jié)點(diǎn)的負(fù)載情況與處理請(qǐng)求能力。本文命名這種改進(jìn)的WLC算法為動(dòng)態(tài)權(quán)值分配算法。

3 算法實(shí)現(xiàn)

3.1 LVS實(shí)驗(yàn)環(huán)境搭配

本文選取了兩臺(tái)Ubuntu虛擬機(jī)作為真實(shí)服務(wù)器提供網(wǎng)絡(luò)服務(wù)，為了模擬不同的服務(wù)器子節(jié)點(diǎn)，給他們的核心數(shù)依次分配為3，4，核心內(nèi)存也依次分配為2G，4G來(lái)顯示性能的區(qū)別。負(fù)載均衡器也用的Ubantu虛擬機(jī)作為它的Linux系統(tǒng)。負(fù)載均衡器安裝的操作系統(tǒng)是Ubantu8.04，內(nèi)核版本是2.6，采用該版本的系統(tǒng)的一大好處是它已經(jīng)集成了IPVS軟件，剩下的就是安裝配置管理軟件ipvsadm，打開Linux的命令行輸入指令：sudo apt-get install ipvsadm，然后等待軟件安裝成功。等安裝完成后輸入：sudo ipvsadm，看到版本號(hào)則說(shuō)明安裝成功。

3.2 客戶端模擬壓力測(cè)試配置

完成了LVS實(shí)驗(yàn)環(huán)境的搭配后，我們還需要在客戶端機(jī)器上安裝模擬壓力測(cè)試的相關(guān)軟件。本文選擇的是微軟公司提供的免費(fèi)測(cè)試軟件WAS（Web Application Stress）來(lái)對(duì)集群系統(tǒng)做高負(fù)載，多用戶請(qǐng)求并發(fā)的壓力測(cè)試。在WAS客戶端配置好向集群提交請(qǐng)求服務(wù)，會(huì)生成一份集群系統(tǒng)的數(shù)據(jù)吞吐量（Bytes Recv Rate）和平均響應(yīng)時(shí)間（TTFB Avg）報(bào)告。本文主要采用TTFB Avg的值來(lái)對(duì)比分析原來(lái)算法與優(yōu)化算法的性能好壞。

3.3 服務(wù)器負(fù)載參數(shù)的獲取

本文的實(shí)驗(yàn)環(huán)境是基于node.js語(yǔ)言來(lái)測(cè)試的，在node.js提供好的API中，有可以直接獲取這些參數(shù)的方法，具體如下：

1）CPU和MEM的參數(shù)獲取

根據(jù)node.js提供的api，cpu利用率可以用os.cpus（）來(lái)獲取，該方法返回一個(gè)對(duì)象數(shù)組，包含安裝的每個(gè)CPU/CPU核的信息：具體的屬性分別有user（CPU花費(fèi)在用戶模式下的毫秒時(shí)間數(shù)），nice（CPU花費(fèi)在良好模式下的毫秒數(shù)），sys（CPU花費(fèi)在系統(tǒng)模式下的毫秒時(shí)間數(shù)），idle（CPU花費(fèi)在空閑模式下的毫秒時(shí)間數(shù)），irq（CPU花費(fèi)在中斷請(qǐng)求模式下的毫秒時(shí)間數(shù)），通過(guò)這四個(gè)屬性可以得出cpu的利用率公式：CPU_USE=（user+nice+sys）/（user+nice+sys+idle）。

內(nèi)存利用率的獲取則要使用os.totalmem（），os.freemem（）這兩個(gè)函數(shù)，os.totalmem（）方法會(huì)以整數(shù)的形式返回所有系統(tǒng)內(nèi)存的字節(jié)數(shù)，freemem（）方法則是以整數(shù)的形式返回空閑系統(tǒng)內(nèi)存的字節(jié)數(shù)，因此服務(wù)器的內(nèi)存利用率MEM_USE=1-os.freemem（）/os.totalmem（）。

2）網(wǎng)絡(luò)帶寬利用率的獲取

Linux系統(tǒng)中提供了命令“netstat-e”查看系統(tǒng)以太網(wǎng)的統(tǒng)計(jì)數(shù)據(jù)。通過(guò)網(wǎng)卡接收和發(fā)送的數(shù)據(jù)數(shù)值相加，我們可以得到當(dāng)前時(shí)刻的數(shù)據(jù)總流量，然后通過(guò)相同的方法繼續(xù)獲取了下一個(gè)時(shí)刻的數(shù)據(jù)總流量，用下一時(shí)刻的總流量減去當(dāng)前時(shí)刻的總流量再除以時(shí)間間隔，得到的就是實(shí)際的網(wǎng)速，接下來(lái)在用實(shí)際的網(wǎng)速除以網(wǎng)卡的速度，得到的就是網(wǎng)絡(luò)帶寬利用率。具體的實(shí)現(xiàn)公式如下：

本文將ΔT取值為1，即每隔1s對(duì)網(wǎng)絡(luò)進(jìn)行一次統(tǒng)計(jì)數(shù)據(jù)流量，通過(guò)nodejs獲取網(wǎng)絡(luò)的相關(guān)信息要用到exec（）函數(shù)，exec（）函數(shù)一般可以接受一個(gè)回調(diào)函數(shù)作為參數(shù)，回調(diào)函數(shù)中有三個(gè)參數(shù)它們通常是err，stdout和stderr，獲取到的網(wǎng)絡(luò)信息就在stdout中。

3.4 服務(wù)器與負(fù)載均衡器端的通信

服務(wù)器端通過(guò)收集自身的系統(tǒng)參數(shù)，并計(jì)算出新的權(quán)值，改權(quán)值需要傳遞到負(fù)載均衡器端，然后通過(guò)負(fù)載均衡器把新的權(quán)值設(shè)定到負(fù)載均衡算法中實(shí)現(xiàn)。通常傳輸層的協(xié)議有TCP、UDP兩種，由于傳輸?shù)臄?shù)據(jù)很少，而基于UDP協(xié)議的正好是無(wú)連接模式通訊，占用資源少，響應(yīng)速度比較迅速，延時(shí)低，所以本文采用的基于UDP協(xié)議的傳輸數(shù)據(jù)方式。

同時(shí)，node.js采用UDP編程也非常容易實(shí)現(xiàn)，在服務(wù)器端編寫一段發(fā)送權(quán)值程序，每隔10s執(zhí)行一次，具體代碼如下：

圖2 服務(wù)器與負(fù)載均衡器端的通信

3.5 實(shí)驗(yàn)結(jié)果與分析

測(cè)試運(yùn)行結(jié)束后，將WLC算法與優(yōu)化后算法的平均響應(yīng)時(shí)間（TTFB Avg）轉(zhuǎn)化成折線圖形式，可以更加直觀地看出兩種算法的差異。表中橫坐標(biāo)為請(qǐng)求任務(wù)連接數(shù)，縱坐標(biāo)為TTFB（ms）。

圖3 客戶端用戶任務(wù)請(qǐng)求響應(yīng)時(shí)間

從圖3中我們可以看出，當(dāng)用戶的訪問(wèn)請(qǐng)求不太多時(shí)，WLC算法的等待響應(yīng)時(shí)間要比優(yōu)化算法要稍短，主要是因?yàn)闄?quán)值的寫入，讀取等一系列操作造成了額外開銷，影響了服務(wù)器與負(fù)載均衡器的性能。但是隨著用戶的訪問(wèn)請(qǐng)求不斷地增加，優(yōu)化算法的響應(yīng)時(shí)間會(huì)明顯優(yōu)于WLC算法，整個(gè)服務(wù)器集群的性能會(huì)得到一定程度的提升。需要注意的是，無(wú)論是優(yōu)化算法還是WLC算法，隨著請(qǐng)求任務(wù)不斷的增多，當(dāng)達(dá)到一定的數(shù)量后整個(gè)集群系統(tǒng)會(huì)臨近一個(gè)飽和的狀態(tài)，因?yàn)槊颗_(tái)服務(wù)器的性能有限，無(wú)論怎么分配都會(huì)使得各個(gè)服務(wù)器節(jié)點(diǎn)的資源利用率達(dá)到飽和。出現(xiàn)這種情況時(shí)，我們應(yīng)該考慮增加服務(wù)器來(lái)擴(kuò)展集群，而不是擔(dān)心算法自身的問(wèn)題。

4 結(jié)語(yǔ)

本文主要通過(guò)研究LVS集群的加權(quán)最小鏈接算法，發(fā)現(xiàn)算法中只考慮服務(wù)器節(jié)點(diǎn)的當(dāng)前鏈接數(shù)作為節(jié)點(diǎn)的負(fù)載情況的參考標(biāo)準(zhǔn)是不太合理的，并提出一種采用CPU利用率，內(nèi)存利用率，以及網(wǎng)絡(luò)帶寬利用率三個(gè)參數(shù)來(lái)描述服務(wù)器節(jié)點(diǎn)的負(fù)載情況的動(dòng)態(tài)權(quán)值分配算法。并通過(guò)實(shí)驗(yàn)證明了該算法相對(duì)于原來(lái)的WLCS算法在一定程度上提高了LVS集群的性能。