服務器集群負載均衡算法分析

游燦虹

（四川大學網絡空間安全學院，成都610065）

0 引言

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

本文將對服務器集群的負載均衡算法進行研究和總結，對常用的負載均衡算法進行介紹和分析，并對負載均衡算法的發展情況進行總結。

1 負載均衡分類

我們一般用負載來描述一個系統的忙閑程度。而所謂的負載均衡，就是指將負載合理地分攤到多個節點服務器上去并行執行，從而協同地完成系統的工作任務。它是構筑在原有網絡架構之上的，提供了一種廉價有效的方法去擴展服務器和網絡設備的帶寬、加強處理網絡數據的能力、提高了吞吐量、增強了網絡的可靠性和靈活性[1]。根據負載均衡的不同特點可以將其分為多個類別，下面我們將從實現方式和地理結構上對其進行介紹。

1.1 根據實現方式進行分類

（1）軟件負載均衡

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

（2）硬件負載均衡

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

1.2 根據地理結構進行分類

（1）本地負載均衡

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

（2）全局負載均衡

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

2 常用經典負載均衡算法[3-5]

常用的經典負載均衡算法主要分為靜態和動態兩種。其中靜態負載均衡算法不考慮服務器的實際狀態，如輪詢算法、加權輪詢算法等，它以特定的概率去進行任務調度；動態負載均衡算法將服務器的實時負載狀態信息考慮在算法之中，如最小連接法、加權最小連接法等，以此來動態決定任務調度。

2.1 靜態負載均衡

（1）輪詢法

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

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

（2）加權輪詢法

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

圖2 加權輪詢法

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

2.2 動態負載均衡

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

（1）最小連接法

最小連接法是將任務分配給集群中當前時刻具有最小連接數的節點服務器。當一個節點服務器收到一個任務請求后就將當前連接數加一，當節點服務器出現故障時就將該節點的權值設為0，不再分配任務給該節點服務器。如圖3 所示（圓圈內數字為任務序號），節點服務器上數字為當前節點的連接數，此時三個節點服務器的連接數分別為300,235 和260。此時任務26 來時發現最小連接數為235，對應節點服務器2，就將該任務分配給給該服務器。

圖3 最小連接法

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

（2）加權最小連接法

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

圖4 加權最小連接法

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

3 改進的負載均衡算法

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

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

3.1 基于動態反饋的負載均衡算法

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

3.2 基于遺傳算法的動態負載均衡算法

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

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

3.3 基于神經網絡反饋機制的負載均衡算法

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

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

4 結語

負載均衡算法作為集群系統中的一個重要部分，影響著一個集群系統的正常運行。通過對傳統和改進的負載均衡算法的分析可知，如何用實時且適當的方式反映節點服務器的CPU 利用情況、當前網絡狀況、I/O 情況、內存利用情況以及請求負載情況等是研究的主要方向，除此之外如何在處理過程中不增加較多額外的開銷，也是我們需要去考慮的問題。