游燦虹

（四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，成都610065）

0 引言

在計算機(jī)技術(shù)的飛速發(fā)展的今天，互聯(lián)網(wǎng)使用人群日益增長，網(wǎng)絡(luò)業(yè)務(wù)請求數(shù)呈現(xiàn)爆炸式增長，這給傳統(tǒng)的單一服務(wù)器帶來巨大壓力。雖然通過給服務(wù)器的硬件進(jìn)行升級能夠解決一定的問題，但是當(dāng)硬件設(shè)備提升到一定程度后，繼續(xù)提升所帶來的的花費將呈幾何式增加。這并不是所有企業(yè)都能負(fù)擔(dān)得起的。而服務(wù)器集群化方案因為其高性價比和良好的拓展性，被廣泛的使用。由此引出了一個新的問題，即如何合理地分配業(yè)務(wù)請求到各個服務(wù)器上，又能使得集群內(nèi)部不出現(xiàn)因業(yè)務(wù)請求過多而導(dǎo)致的服務(wù)器節(jié)點過忙或者因業(yè)務(wù)請求過少而出現(xiàn)服務(wù)器節(jié)點閑置的情況，這個問題也就是常說的負(fù)載均衡問題。

本文將對服務(wù)器集群的負(fù)載均衡算法進(jìn)行研究和總結(jié)，對常用的負(fù)載均衡算法進(jìn)行介紹和分析，并對負(fù)載均衡算法的發(fā)展情況進(jìn)行總結(jié)。

1 負(fù)載均衡分類

我們一般用負(fù)載來描述一個系統(tǒng)的忙閑程度。而所謂的負(fù)載均衡，就是指將負(fù)載合理地分?jǐn)偟蕉鄠€節(jié)點服務(wù)器上去并行執(zhí)行，從而協(xié)同地完成系統(tǒng)的工作任務(wù)。它是構(gòu)筑在原有網(wǎng)絡(luò)架構(gòu)之上的，提供了一種廉價有效的方法去擴(kuò)展服務(wù)器和網(wǎng)絡(luò)設(shè)備的帶寬、加強(qiáng)處理網(wǎng)絡(luò)數(shù)據(jù)的能力、提高了吞吐量、增強(qiáng)了網(wǎng)絡(luò)的可靠性和靈活性[1]。根據(jù)負(fù)載均衡的不同特點可以將其分為多個類別，下面我們將從實現(xiàn)方式和地理結(jié)構(gòu)上對其進(jìn)行介紹。

1.1 根據(jù)實現(xiàn)方式進(jìn)行分類

（1）軟件負(fù)載均衡

軟件負(fù)載均衡的解決方案是指在服務(wù)器相上安裝附加軟件來實現(xiàn)負(fù)載均衡，例如Nginx、DNS Load Balance 等，它擁有配置相對簡單，使用起來靈活便捷，花費相對低廉等優(yōu)點，可以滿足一般情況下的負(fù)載均衡需求。但是該方案缺點也比較多，一方面服務(wù)器安裝的三方軟件在運行的時候也會消耗系統(tǒng)一定量的資源，而且越是功能復(fù)雜的模塊，消耗的量越多，另一方面當(dāng)并發(fā)連接請求數(shù)非常高時，這個軟件反而可能會成為服務(wù)器工作的一個負(fù)擔(dān)[1-2]。

（2）硬件負(fù)載均衡

硬件負(fù)載均衡的解決方案是直接把負(fù)載均衡設(shè)備（通常稱之為負(fù)載均衡器）安裝在服務(wù)器和外部網(wǎng)絡(luò)之間，用特定的設(shè)備完成特定的任務(wù)，使得系統(tǒng)整體性能得到極大提升，可達(dá)到最佳的負(fù)載均衡需求。雖然該方案相對于軟件方式，功能和性能都更強(qiáng)大，但是花費也相對較大，而且因為使用的單個負(fù)載均衡器，一旦出現(xiàn)問題將導(dǎo)致整個系統(tǒng)癱瘓。

1.2 根據(jù)地理結(jié)構(gòu)進(jìn)行分類

（1）本地負(fù)載均衡

本地負(fù)載均衡指的是對本地的服務(wù)器集群做負(fù)載均衡，它不需花費昂貴開支去購置高性能的服務(wù)器，只需充分利用現(xiàn)有的設(shè)備資源，就可有效地避免因服務(wù)器單點故障所造成的數(shù)據(jù)流量損失，它通常用來解決數(shù)據(jù)流量過大、網(wǎng)絡(luò)負(fù)載過重的問題。即使是再給現(xiàn)有服務(wù)器進(jìn)行擴(kuò)充，也只需要在集群中簡單地增加一個新的服務(wù)器即可，現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)不需要去做改變，服務(wù)也不需要停止。

（2）全局負(fù)載均衡

全局負(fù)載均衡指的是對地理位置不同、網(wǎng)絡(luò)結(jié)構(gòu)不同的服務(wù)器集群間做負(fù)載均衡。該方案通過在多個區(qū)域部署自己的服務(wù)器站點，使得用戶只需通過一個IP 或者域名就能迅速地訪問到距離自己最近的區(qū)域服務(wù)器站點，從而獲得最快的訪問速度。同時這種方式也能夠用于那些擁有多站點廣區(qū)域子公司的大型公司通過企業(yè)內(nèi)部網(wǎng)達(dá)到資源統(tǒng)一合理分配的需求。

2 常用經(jīng)典負(fù)載均衡算法[3-5]

常用的經(jīng)典負(fù)載均衡算法主要分為靜態(tài)和動態(tài)兩種。其中靜態(tài)負(fù)載均衡算法不考慮服務(wù)器的實際狀態(tài)，如輪詢算法、加權(quán)輪詢算法等，它以特定的概率去進(jìn)行任務(wù)調(diào)度；動態(tài)負(fù)載均衡算法將服務(wù)器的實時負(fù)載狀態(tài)信息考慮在算法之中，如最小連接法、加權(quán)最小連接法等，以此來動態(tài)決定任務(wù)調(diào)度。

2.1 靜態(tài)負(fù)載均衡

（1）輪詢法

輪詢法就是將任務(wù)請求按照固定的順序從頭到尾的循環(huán)分配給節(jié)點服務(wù)器，如圖1 所示（圓圈內(nèi)為任務(wù)序號），這種算法是嚴(yán)格按照節(jié)點服務(wù)器的序號進(jìn)行分配的，大致流程是第一個請求發(fā)送到服務(wù)器1，下一個請求發(fā)送到服務(wù)器2，第三個請求發(fā)送到服務(wù)器3，后續(xù)請求重新從服務(wù)器1 開始繼續(xù)按照這種方式分發(fā)。

這種算法比較簡單，但并不一定合適的，因為一方面實際情況中可能出現(xiàn)節(jié)點服務(wù)器配置并不是完全一致的，所以可能出現(xiàn)某個處理能力較弱節(jié)點服務(wù)器過載的情況；另一方面每個用戶請求給節(jié)點服務(wù)器帶來的狀態(tài)變化可能是不同的，即使集群服務(wù)器處理能力相同，也可能因為某個節(jié)點因為分配過多重任務(wù)而出現(xiàn)過載的情況。所以該算法比較適合于集群服務(wù)器處理能力相當(dāng)且各個業(yè)務(wù)請求帶來的負(fù)載差距不大的情況。

（2）加權(quán)輪詢法

加權(quán)輪詢法是針對輪詢法的缺點進(jìn)行優(yōu)化后的一種算法，顧名思義它是先給每個節(jié)點服務(wù)器增加一個權(quán)值，服務(wù)器的處理能力越強(qiáng)該服務(wù)器的權(quán)值越大反之則越小。進(jìn)行任務(wù)分配的時候就根據(jù)權(quán)值去輪詢分配不同數(shù)量的任務(wù)給節(jié)點服務(wù)器。如圖2 所示（圓圈內(nèi)為任務(wù)序號），該網(wǎng)絡(luò)中節(jié)點服務(wù)器的權(quán)重比為1:2:1，在分配任務(wù)時首先將請求發(fā)送到服務(wù)器1 上，第二個請求發(fā)送到服務(wù)器2 上，第三個請求因為服務(wù)器2 權(quán)重較高所以發(fā)送到服務(wù)器2 上，第四個請求發(fā)送到服務(wù)器3 上，后續(xù)請求依照這種方式繼續(xù)從服務(wù)器1 上開始分配。

圖2 加權(quán)輪詢法

根據(jù)加權(quán)輪詢法的分配流程可知，該算法考慮到了節(jié)點服務(wù)器處理能力可能不同的問題，并且給處理能力較高的節(jié)點服務(wù)器分配了更多的業(yè)務(wù)請求，一定程度上避免了業(yè)務(wù)堆積造成的過載問題。但是這種算法并未考慮到業(yè)務(wù)請求本身給服務(wù)器帶來的負(fù)載差距較大時帶來的問題，而且如何更加合理地選擇權(quán)值的配比也是一個問題。

2.2 動態(tài)負(fù)載均衡

分析靜態(tài)負(fù)載均衡算法可知，因其自身的考慮上的缺陷，依舊可能出現(xiàn)集群負(fù)載不均衡的問題。動態(tài)負(fù)載均衡正是為解決這些問題而出現(xiàn)的。

（1）最小連接法

最小連接法是將任務(wù)分配給集群中當(dāng)前時刻具有最小連接數(shù)的節(jié)點服務(wù)器。當(dāng)一個節(jié)點服務(wù)器收到一個任務(wù)請求后就將當(dāng)前連接數(shù)加一，當(dāng)節(jié)點服務(wù)器出現(xiàn)故障時就將該節(jié)點的權(quán)值設(shè)為0，不再分配任務(wù)給該節(jié)點服務(wù)器。如圖3 所示（圓圈內(nèi)數(shù)字為任務(wù)序號），節(jié)點服務(wù)器上數(shù)字為當(dāng)前節(jié)點的連接數(shù)，此時三個節(jié)點服務(wù)器的連接數(shù)分別為300,235 和260。此時任務(wù)26 來時發(fā)現(xiàn)最小連接數(shù)為235，對應(yīng)節(jié)點服務(wù)器2，就將該任務(wù)分配給給該服務(wù)器。

圖3 最小連接法

分析可知，此方法會出現(xiàn)類似輪詢法中的一個問題，即當(dāng)服務(wù)器處理能力差距非常大的時候，負(fù)載分配的效果就比較差。主要是因為此時單純的連接數(shù)已經(jīng)無法準(zhǔn)確表明服務(wù)器的處理能力了，例如可能出現(xiàn)自身處理能力很差的服務(wù)器雖然連接數(shù)小，但是本身已經(jīng)無法再處理任務(wù)了，而自身處理能力極好的服務(wù)器雖然連接數(shù)大，但是依舊能夠繼續(xù)處理任務(wù)。在這個時候任務(wù)就會被被分配到前者，從而導(dǎo)致該服務(wù)器出現(xiàn)過載的情況。所以說該方法更適用于各個服務(wù)器處理能力相近時。

（2）加權(quán)最小連接法

加權(quán)最小連接法是針對最小連接法無法較好的解決處理能力差距較大的節(jié)點服務(wù)器之間的負(fù)載均衡問題而提出的。該算法將節(jié)點服務(wù)器的處理能力用權(quán)值表示，在進(jìn)行任務(wù)調(diào)度時讓節(jié)點的連接數(shù)和其權(quán)值盡可能成比例。如圖4 所示（圓圈內(nèi)數(shù)字為任務(wù)序號），該架構(gòu)下節(jié)點服務(wù)器處理能的權(quán)重比為1:2:1，當(dāng)前連接數(shù)分別為100,150,110。根據(jù)該算法最近兩個任務(wù)都發(fā)送到了處理能力較高的服務(wù)器2 上。

圖4 加權(quán)最小連接法

分析可知該算法考慮到了各臺服務(wù)器的狀態(tài)和處理能力，能比較好地進(jìn)行任務(wù)的調(diào)度。不過它和靜態(tài)負(fù)載均衡中的加權(quán)輪詢法類似，都使用權(quán)值代表了服務(wù)器的處理能力，所以也會帶來另一個問題，即如何合理的設(shè)置這個權(quán)值，如果只憑經(jīng)驗去選取往往會帶來較大的誤差。

3 改進(jìn)的負(fù)載均衡算法

通過對常用的動靜態(tài)負(fù)載均衡算法的介紹和分析可知，動態(tài)負(fù)載均衡算法因為將服務(wù)器的處理能力和當(dāng)前負(fù)載狀況納入計算中，所以實際效果更好。然而連接數(shù)并不能完全表征當(dāng)前服務(wù)器的剩余處理能力，另外因為業(yè)務(wù)請求有多種類型，不同類型給節(jié)點服務(wù)器帶來的負(fù)載也可能出現(xiàn)較大差距。最后隨著并發(fā)請求數(shù)的增加，負(fù)載均衡調(diào)度器自身也可能成為任務(wù)調(diào)度的瓶頸。

為了解決前面所提到的一些問題，研究出新的或者改進(jìn)的負(fù)載均衡算法已經(jīng)成為了一個熱點。本文接下來將對一些新提出的改進(jìn)的負(fù)載均衡算法進(jìn)行簡單介紹和分析。

3.1 基于動態(tài)反饋的負(fù)載均衡算法

文獻(xiàn)[6]中提出了一種基于動態(tài)反饋的負(fù)載均衡算法，算法是針對一般負(fù)載均衡算法無法適用于I/O 密集型任務(wù)的存儲系統(tǒng)，不能動態(tài)實時地反應(yīng)系統(tǒng)、網(wǎng)絡(luò)的狀態(tài)的問題所提出的。該算法考慮了每個連接的實時負(fù)載和響應(yīng)能力，首先確定了四個影響系統(tǒng)負(fù)載均衡的因素：CPU 利用率、內(nèi)存利用率、命令響應(yīng)時間、命令隊列長度。并對各個連接中的這些參數(shù)進(jìn)行周期性地采集。并計算出實時的反饋值，結(jié)合歷史反饋值對系統(tǒng)中任務(wù)進(jìn)行分配以達(dá)到動態(tài)調(diào)整系統(tǒng)負(fù)載的功能。從測試結(jié)果上看，該算法的均衡效果要好于經(jīng)典算法。不過該算法也有其局限性，即其主要針對的是I/O密集型任務(wù)系統(tǒng)，當(dāng)I/O 任務(wù)較少時，計算反饋值的過程反倒會變成相對耗時的部分。

3.2 基于遺傳算法的動態(tài)負(fù)載均衡算法

文獻(xiàn)[7]中提出了一種基于遺傳算法（GA）的網(wǎng)絡(luò)GIS 集群服務(wù)器動態(tài)負(fù)載均衡算法，該算法同時考慮了基于服務(wù)器狀態(tài)和基于內(nèi)容的負(fù)載均衡算法，還能夠靈活調(diào)整針對這兩方面的權(quán)重。該系統(tǒng)集群由負(fù)載均衡器和應(yīng)用服務(wù)器組成，其中負(fù)載均衡器使用滑動窗口技術(shù)，一次處理落在窗口中的任務(wù)組，同時窗口大小又正好和遺傳算法中個體的基因數(shù)相等。另外針對滿串窗口和未滿窗口的情況采用不同的處理方案，其中滿窗口使用遺傳算法發(fā)送到應(yīng)用服務(wù)器，未滿窗口使用輪詢的方式發(fā)送到應(yīng)用服務(wù)器。

針對GA 無法處理問題空間參數(shù)的情況，將問題解的參數(shù)進(jìn)行二維編碼，分別表示系統(tǒng)中的應(yīng)用服務(wù)器信息和每個處理器上待分配的若干個任務(wù)。仿真實驗表明，該算法總能最快地返回用戶請求的數(shù)據(jù)，因為它同時考慮了緩存利用率和服務(wù)器狀態(tài)。不過該算法在未滿窗口時依舊使用的輪詢方式，所以當(dāng)這種情況持續(xù)較長時間時，也會出現(xiàn)輪詢方式所帶來的一些問題。

3.3 基于神經(jīng)網(wǎng)絡(luò)反饋機(jī)制的負(fù)載均衡算法

文獻(xiàn)[8]中提出了一種基于神經(jīng)網(wǎng)絡(luò)反饋機(jī)制的改進(jìn)型的加權(quán)最小連接數(shù)算法。該算法使用了BP 神經(jīng)網(wǎng)絡(luò)來進(jìn)行反饋控制。在集群中，由于各個節(jié)點服務(wù)器具有不同的處理能力，因此其所能承受的負(fù)載也是不一樣的，在處理過程中，每臺節(jié)點服務(wù)器的處理能力和任務(wù)分配情況會出現(xiàn)一定的偏差，這時就可以利用BP 神經(jīng)網(wǎng)絡(luò)反饋機(jī)制來修正權(quán)值和閾值。

該算法在一定的時間內(nèi)收集節(jié)點服務(wù)器的CPU利用率和網(wǎng)絡(luò)使用率，將其作為參數(shù)值，然后利用這些參數(shù)值去與初始化的閾值進(jìn)行比較，從而得到節(jié)點的負(fù)載比率R（Si）（服務(wù)器節(jié)點的處理能力極值與實時負(fù)載比值之比），而服務(wù)器節(jié)點負(fù)載的分配結(jié)果取決于負(fù)載比率。實驗結(jié)果表明，該算法能夠較好地反映服務(wù)器的負(fù)載情況，從而能夠更有效地應(yīng)對大量用戶請求，并降低響應(yīng)時間。但是該算法在計算負(fù)載比率時存在一定波動，而負(fù)載比率又是影響計算流程的一個重要參數(shù)，因此需要穩(wěn)定下來。

4 結(jié)語

負(fù)載均衡算法作為集群系統(tǒng)中的一個重要部分，影響著一個集群系統(tǒng)的正常運行。通過對傳統(tǒng)和改進(jìn)的負(fù)載均衡算法的分析可知，如何用實時且適當(dāng)?shù)姆绞椒从彻?jié)點服務(wù)器的CPU 利用情況、當(dāng)前網(wǎng)絡(luò)狀況、I/O 情況、內(nèi)存利用情況以及請求負(fù)載情況等是研究的主要方向，除此之外如何在處理過程中不增加較多額外的開銷，也是我們需要去考慮的問題。