游燦虹

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

0 引言

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

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

1 負(fù)載均衡分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）輪詢法

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

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

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

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

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

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

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

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

（1）最小連接法

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

圖3 最小連接法

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

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

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

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

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

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

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

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

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

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

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

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

針對(duì)GA 無法處理問題空間參數(shù)的情況，將問題解的參數(shù)進(jìn)行二維編碼，分別表示系統(tǒng)中的應(yīng)用服務(wù)器信息和每個(gè)處理器上待分配的若干個(gè)任務(wù)。仿真實(shí)驗(yàn)表明，該算法總能最快地返回用戶請(qǐng)求的數(shù)據(jù)，因?yàn)樗瑫r(shí)考慮了緩存利用率和服務(wù)器狀態(tài)。不過該算法在未滿窗口時(shí)依舊使用的輪詢方式，所以當(dāng)這種情況持續(xù)較長(zhǎng)時(shí)間時(shí)，也會(huì)出現(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)行反饋控制。在集群中，由于各個(gè)節(jié)點(diǎn)服務(wù)器具有不同的處理能力，因此其所能承受的負(fù)載也是不一樣的，在處理過程中，每臺(tái)節(jié)點(diǎn)服務(wù)器的處理能力和任務(wù)分配情況會(huì)出現(xiàn)一定的偏差，這時(shí)就可以利用BP 神經(jīng)網(wǎng)絡(luò)反饋機(jī)制來修正權(quán)值和閾值。

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

4 結(jié)語

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