動態(tài)網(wǎng)絡負載平衡的設計與實現(xiàn)

1．引言
　 　本質(zhì)上講，網(wǎng)絡負載平衡是分布式作業(yè)調(diào)度系統(tǒng)的一種實現(xiàn)。平衡器作為網(wǎng)絡請求分配的控制者，要根據(jù)集群節(jié)點的當前處理能力，采用集中或分布策略對網(wǎng)絡服 務請求進行調(diào)配，并且在每個服務請求的生命周期里監(jiān)控各個節(jié)點的有效狀態(tài)。一般的說，平衡器對請求的調(diào)度具備以下的特征：
網(wǎng)絡服務請求必須是可管理的
請求的分配對用戶是透明的
最好能夠提供異構(gòu)系統(tǒng)的支持
能夠依據(jù)集群節(jié)點的資源情況進行動態(tài)分配和調(diào)整
負載平衡器在集群的各個服務節(jié)點中分配工作負載或網(wǎng)絡流量。可以靜態(tài)預先設置或根據(jù)當前的網(wǎng)絡狀態(tài)來決定負載分發(fā)到哪個特定的節(jié)點，節(jié)點在集群內(nèi)部可以互相連接，但它們必須與平衡器直接或間接相連。
　 　網(wǎng)絡平衡器可以認為是網(wǎng)絡層次上的作業(yè)調(diào)度系統(tǒng)，大多數(shù)網(wǎng)絡負載平衡器能夠在網(wǎng)絡的相應層次上實現(xiàn)單一系統(tǒng)映像，整個集群能夠體現(xiàn)為一個單一的IP地址 被用戶訪問，而具體服務的節(jié)點對用戶而言是透明的。這里，平衡器可靜態(tài)或動態(tài)配置，用一種或多種算法決定哪個節(jié)點獲得下一個網(wǎng)絡服務請求。
2．網(wǎng)絡平衡原理
　 　在TCP/IP協(xié)議中，數(shù)據(jù)包含有必要的網(wǎng)絡信息，因而在網(wǎng)絡緩存或網(wǎng)絡平衡的具體實現(xiàn)算法里，數(shù)據(jù)包的信息很重要。但由于數(shù)據(jù)包是面向分組的（IP） 和面向連接的（TCP），且經(jīng)常被分片，沒有與應用有關(guān)的完整信息，特別是和連接會話相關(guān)的狀態(tài)信息。因此必須從連接的角度看待數(shù)據(jù)包——從源地址的端口 建立到目的地址端口的連接。
　　平衡考慮的另一個要素就是節(jié)點的資源使用狀態(tài)。由于負載平衡是這類系統(tǒng)的最終目的，那么及時、準確的把握節(jié)點負載狀況，并根據(jù)各個節(jié)點當前的資源使用狀態(tài)動態(tài)調(diào)整負載平衡的任務分布，是網(wǎng)絡動態(tài)負載平衡集群系統(tǒng)考慮的另一關(guān)鍵問題。
　 　一般情況下，集群的服務節(jié)點可以提供諸如處理器負載，應用系統(tǒng)負載、活躍用戶數(shù)、可用的網(wǎng)絡協(xié)議緩存以及其他的資源信息。信息通過高效的消息機制傳給平 衡器，平衡器監(jiān)視所有處理節(jié)點的狀態(tài)，主動決定下個任務傳給誰。平衡器可以是單個設備，也可以使一組平行或樹狀分布的設備。
3．基本的網(wǎng)絡負載平衡算法
　 　平衡算法設計的好壞直接決定了集群在負載均衡上的表現(xiàn)，設計不好的算法，會導致集群的負載失衡。一般的平衡算法主要任務是決定如何選擇下一個集群節(jié)點， 然后將新的服務請求轉(zhuǎn)發(fā)給它。有些簡單平衡方法可以獨立使用，有些必須和其它簡單或高級方法組合使用。而一個好的負載均衡算法也并不是萬能的，它一般只在 某些特殊的應用環(huán)境下才能發(fā)揮最大效用。因此在考察負載均衡算法的同時，也要注意算法本身的適用面，并在采取集群部署的時候根據(jù)集群自身的特點進行綜合考 慮，把不同的算法和技術(shù)結(jié)合起來使用。
3．1 輪轉(zhuǎn)法：
　　輪轉(zhuǎn) 算法是所有調(diào)度算法中最簡單也最容易實現(xiàn)的一種方法。在一個任務隊列里，隊列的每個成員（節(jié)點）都具有相同的地位，輪轉(zhuǎn)法簡單的在這組成員中順序輪轉(zhuǎn)選 擇。在負載平衡環(huán)境中，均衡器將新的請求輪流發(fā)給節(jié)點隊列中的下一節(jié)點，如此連續(xù)、周而復始，每個集群的節(jié)點都在相等的地位下被輪流選擇。這個算法在 DNS域名輪詢中被廣泛使用。
　　輪轉(zhuǎn)法的活動是可預知的，每個節(jié)點被選擇的機會是1/N，因此很容易計算出節(jié)點的負載分布。輪轉(zhuǎn)法典型的適用于集群中所有節(jié)點的處理能力和性能均相同的情況，在實際應用中，一般將它與其他簡單方法聯(lián)合使用時比較有效。
3．2 散列法
　 　散列法也叫哈希法（HASH），通過單射不可逆的HASH函數(shù)，按照某種規(guī)則將網(wǎng)絡請求發(fā)往集群節(jié)點。哈希法在其他幾類平衡算法不是很有效時會顯示出特 別的威力。例如，在前面提到的UDP會話的情況下，由于輪轉(zhuǎn)法和其他幾類基于連接信息的算法，無法識別出會話的起止標記，會引起應用混亂。
　　而采取基于數(shù)據(jù)包源地址的哈希映射可以在一定程度上解決這個問題：將具有相同源地址的數(shù)據(jù)包發(fā)給同一服務器節(jié)點，這使得基于高層會話的事務可以以適當?shù)姆绞竭\行。相對稱的是，基于目的地址的哈希調(diào)度算法可以用在Web Cache集群中，指向同一個目標站點的訪問請求都被負載平衡器發(fā)送到同一個Cache服務節(jié)點上，以避免頁面缺失而帶來的更新Cache問題。
3．3 最少連接法
　 　在最少連接法中，平衡器紀錄目前所有活躍連接，把下一個新的請求發(fā)給當前含有最少連接數(shù)的節(jié)點。這種算法針對TCP連接進行，但由于不同應用對系統(tǒng)資源 的消耗可能差異很大，而連接數(shù)無法反映出真實的應用負載，因此在使用重型Web服務器作為集群節(jié)點服務時（例如Apache服務器），該算法在平衡負載的 效果上要打個折扣。為了減少這個不利的影響，可以對每個節(jié)點設置最大的連接數(shù)上限（通過閾值設定體現(xiàn)）。
3．4 最低缺失法
　　在最低缺失法中，平衡器長期紀錄到各節(jié)點的請求情況，把下個請求發(fā)給歷史上處理請求最少的節(jié)點。與最少連接法不同的是，最低缺失記錄過去的連接數(shù)而不是當前的連接數(shù)。
3．5 最快響應法
　　平衡器記錄自身到每一個集群節(jié)點的網(wǎng)絡響應時間，并將下一個到達的連接請求分配給響應時間最短的節(jié)點，這種方法要求使用ICMP包或基于UDP包的專用技術(shù)來主動探測各節(jié)點。
　 　在大多數(shù)基于LAN的集群中，最快響應算法工作的并不是很好，因為LAN中的ICMP包基本上都在10ms內(nèi)完成回應，體現(xiàn)不出節(jié)點之間的差異；如果在 WAN上進行平衡的話，響應時間對于用戶就近選擇服務器而言還是具有現(xiàn)實意義的；而且集群的拓撲越分散這種方法越能體現(xiàn)出效果來。這種方法是高級平衡基于 拓撲結(jié)構(gòu)重定向用到的主要方法。
3．6 加權(quán)法
　　加權(quán)方法只能 與其他方法合用，是它們的一個很好的補充。加權(quán)算法根據(jù)節(jié)點的優(yōu)先級或當前的負載狀況（即權(quán)值）來構(gòu)成負載平衡的多優(yōu)先級隊列，隊列中的每個等待處理的連 接都具有相同處理等級，這樣在同一個隊列里可以按照前面的輪轉(zhuǎn)法或者最少連接法進行均衡，而隊列之間按照優(yōu)先級的先后順序進行均衡處理。在這里權(quán)值是基于 各節(jié)點能力的一個估計值。
4、動態(tài)反饋負載均衡
　 　當客戶訪問集群資源時，提交的任務所需的時間和所要消耗的計算資源是千差萬別的，它依賴于很多因素。例如：任務請求的服務類型、當前網(wǎng)絡帶寬的情況、以 及當前服務器資源利用的情況等等。一些負載比較重的任務需要進行計算密集的查詢、數(shù)據(jù)庫訪問、很長響應數(shù)據(jù)流；而負載比較輕的任務請求往往只需要讀一個小 文件或者進行很簡單的計算。
　　對任務請求處理時間的不同可能會導致處理結(jié)點利用率的傾斜（Skew），即處 理結(jié)點的負載不平衡。有可能存在這樣情況，有些結(jié)點已經(jīng)超負荷運行，而其他結(jié)點基本是閑置著。同時，有些結(jié)點已經(jīng)忙不過來，有很長的請求隊列，還不斷地收 到新的請求。反過來說，這會導致客戶長時間的等待，而集群整體的服務質(zhì)量下降。因此，有必要采用一種機制，使得平衡器能夠?qū)崟r地了解各個結(jié)點的負載狀況， 并能根據(jù)負載的變化做出調(diào)整。
　　具體的做法上采用了基于負反饋機制的動態(tài)負載均衡算法，該算法考慮每一個結(jié)點的實時負載和響應能力，不斷調(diào)整任務分布的比例，來避免有些結(jié)點超載時依然收到大量請求，從而提高單一集群的整體吞吐率。
　 　在集群內(nèi)，負載均衡器上運行服務端監(jiān)控進程，監(jiān)控進程負責監(jiān)視和收集集群內(nèi)各個結(jié)點的負載信息；而每個結(jié)點上運行客戶端進程，負責定時向均衡器報告自身 的負載狀況。監(jiān)控進程根據(jù)收到的全部結(jié)點的負載信息來進行同步操作，既對將要分配的任務按照權(quán)值得比例重新進行分布。權(quán)值得計算主要根據(jù)各個結(jié)點的CPU 利用率、可用內(nèi)存以及磁盤I/O狀況計算出新的權(quán)值，若新權(quán)值和當前權(quán)值的差值大于設定的閥值，監(jiān)控器采用新的權(quán)值對集群范圍內(nèi)的任務重新進行分布，直到 下一次的負載信息同步到來之前。均衡器可以配合動態(tài)權(quán)值，采用加權(quán)輪詢算法來對接受的網(wǎng)絡服務請求進行調(diào)度。
4．1 加權(quán)輪詢調(diào)度
 加權(quán)輪詢調(diào)度（Weighted Round-Robin Scheduling）算法用相應的權(quán)值表示結(jié)點的處理性能。該算法根據(jù)權(quán)值的高低順序并按照輪詢的方式將任務請求分配到各結(jié)點。權(quán)值高的結(jié)點比權(quán)值低的結(jié)點處理更多的任務請求，相同權(quán)值的結(jié)點處理相同份額的請求。加權(quán)輪詢的基本原理可描述為：
 假設某集群內(nèi)有一組結(jié)點N = {N0, N1, …, Nn-1}，W(Ni)表示結(jié)點Ni的權(quán)值，
 一個指示變量i表示上一次選擇的服務器，T（Ni）表示結(jié)點Ni當前所分配的任務量。
 ∑T(Ni)  表示當前同步周期需要處理的任務總量。
 ∑W(Ni)  表示結(jié)點的權(quán)值總和。
 則： W(Ni)/ ∑W(Ni)= T(Ni)/ ∑T(Ni)
 表示任務的分配是按照各個結(jié)點權(quán)值占權(quán)值總數(shù)的比例來進行分配。
4.2 權(quán)值計算
　　當集群的結(jié)點初次投入系統(tǒng)中使用時，系統(tǒng)管理員根據(jù)結(jié)點的硬件配置情況對每個結(jié)點都設定一個初始權(quán)值DW（Ni）（通常根據(jù)結(jié)點的硬件配置來定義，硬件配置越高的結(jié)點默認值越高），在負載均衡器上也先使用這個權(quán)值。然后，隨著結(jié)點負載的變化，均衡器對權(quán)值進行調(diào)整。
　 　動態(tài)權(quán)值是由結(jié)點運行時各方面的參數(shù)計算出來的。我們在實驗中選取了最重要幾項，包括：CPU資源，內(nèi)存資源，當前進程數(shù)，響應時間等信息作為計算公式 的因子。結(jié)合每個結(jié)點當前的權(quán)值，可以計算出新的權(quán)值的大小。動態(tài)權(quán)值目的是要正確反映結(jié)點負載的狀況，以預測結(jié)點將來可能的負載變化。對于不同類型的系 統(tǒng)應用，各個參數(shù)的重要程度也有所不同。典型的Web應用環(huán)境下，可用內(nèi)存資源和響應時間就非常重要；如果用戶以長的數(shù)據(jù)庫事務為主，則CPU使用率和可 用內(nèi)存就相對重要一些。為了方便在系統(tǒng)運行過程中針對不同的應用對各個參數(shù)的比例進行適當調(diào)整，我們?yōu)槊恳粋�參數(shù)設定一個常量系數(shù) Ri ，用來來表示各個負載參數(shù)的重要程度，其中Σ Ri = 1。因此，任何一個結(jié)點Ni的權(quán)值公式就可以描述為：
LOAD(Ni)=R1*Lcpu(Ni)+R2*Lmemory(Ni)+R3*Lio(Ni)+R4*Lprocess(Ni)+R5*Lresponse(Ni)
其中Lf(Ni) 表示結(jié)點Ni 當前某一項參數(shù)的負載值，
上述公式中依次表示為：CPU使用率、內(nèi)存使用率、
 磁盤I/O訪問率、進程總數(shù)以及響應時間。
例如，在WEB服務器集群中，我們采用以系數(shù){0.1, 0.4, 0.1, 0.1, 0.3}，這里認為服務器的內(nèi)存和請求響應時間較其他參數(shù)重要一些。若當前的系數(shù)Ri不能很好地反映應用的負載，系統(tǒng)管理員可以對系數(shù)不斷地修正，直到找到貼近當前應用的一組系數(shù)。
　 　另外，關(guān)于采集權(quán)值的周期置，雖然很短的周期可以更確切地反映各個結(jié)點的負載，但是很頻繁地采集（如1秒1次或者多次）會給均衡器和結(jié)點帶來負擔，也可 能增加不必要的網(wǎng)絡負荷。另外，由于采集器是在采集時刻進行負載計算的，經(jīng)實驗證明，均衡器反映出來各個結(jié)點的負載信息會出現(xiàn)劇烈的抖動，均衡器無法準確 捕捉結(jié)點真實的負載變化趨勢。因此解決這些問題，一方面要適當?shù)卣{(diào)整采集負載信息的周期，一般在5～10秒；另一方面，可以使用移動平均線或者是滑動窗口 來避免抖動，使得均衡器收集到的負載信息表現(xiàn)為平滑曲線，這樣在負反饋機制的調(diào)整效果上就會比較好。
 均衡器的動態(tài)權(quán)值采集程序周期性地運行，若缺省權(quán)值不為零，則查詢該結(jié)點的各負載參數(shù)，并計算出動態(tài)權(quán)值LOAD(Ni) 。我們引入以下權(quán)值計算公式，結(jié)合結(jié)點的初始權(quán)值和采集的動態(tài)權(quán)值來計算最終的權(quán)值結(jié)果。
 Wi = A*DW(Ni)+B*(LOAD(Ni)-DW(Ni))1/3
 在公式中，如果動態(tài)權(quán)值恰好等 于初始權(quán)值，最終權(quán)值不變，則說明系統(tǒng)的負載狀況剛好達到理想狀況，等于初始權(quán)值DW(Ni)。如果動態(tài)權(quán)值計算結(jié)果高于初始權(quán)值，最終權(quán)值變高，則說明 系統(tǒng)負載很輕，均衡器將會增加分配給該結(jié)點的任務比率。如果動態(tài)權(quán)值低于初始權(quán)值，最終權(quán)值變低，說明系統(tǒng)開始處于重載狀況，均衡器將會減少對該結(jié)點分配 的任務。在實際使用中，若發(fā)現(xiàn)所有結(jié)點的權(quán)值都小于他們的DW(Ni)，則說明當前個集群處于超載狀態(tài)，這時需要加入新的結(jié)點到集群中來處理部分負載；反 之，若所有結(jié)點的權(quán)值大大高于DW(Ni)，則說明當前系統(tǒng)的負載都比較輕。