一種動(dòng)態(tài)網(wǎng)絡(luò)負(fù)載平衡集群的實(shí)踐方法

1．引言


本質(zhì)上講，網(wǎng)絡(luò)負(fù)載平衡是分布式作業(yè)調(diào)度系統(tǒng)的一種實(shí)現(xiàn)。平衡器作為網(wǎng)絡(luò)請求分配的控制者，要根據(jù)集群節(jié)點(diǎn)的當(dāng)前處理能力，采用集中或分布策略對網(wǎng)絡(luò)服務(wù)請求進(jìn)行調(diào)配，并且在每個(gè)服務(wù)請求的生命周期里監(jiān)控各個(gè)節(jié)點(diǎn)的有效狀態(tài)。一般的說，平衡器對請求的調(diào)度具備以下的特征：


網(wǎng)絡(luò)服務(wù)請求必須是可管理的


請求的分配對用戶是透明的


最好能夠提供異構(gòu)系統(tǒng)的支持


能夠依據(jù)集群節(jié)點(diǎn)的資源情況進(jìn)行動(dòng)態(tài)分配和調(diào)整


負(fù)載平衡器在集群的各個(gè)服務(wù)節(jié)點(diǎn)中分配工作負(fù)載或網(wǎng)絡(luò)流量。可以靜態(tài)預(yù)先設(shè)置或根據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)來決定負(fù)載分發(fā)到哪個(gè)特定的節(jié)點(diǎn)，節(jié)點(diǎn)在集群內(nèi)部可以互相連接，但它們必須與平衡器直接或間接相連。


網(wǎng)絡(luò)平衡器可以認(rèn)為是網(wǎng)絡(luò)層次上的作業(yè)調(diào)度系統(tǒng)，大多數(shù)網(wǎng)絡(luò)負(fù)載平衡器能夠在網(wǎng)絡(luò)的相應(yīng)層次上實(shí)現(xiàn)單一系統(tǒng)映像，整個(gè)集群能夠體現(xiàn)為一個(gè)單一的IP地址被用戶訪問，而具體服務(wù)的節(jié)點(diǎn)對用戶而言是透明的。這里，平衡器可靜態(tài)或動(dòng)態(tài)配置，用一種或多種算法決定哪個(gè)節(jié)點(diǎn)獲得下一個(gè)網(wǎng)絡(luò)服務(wù)請求。


2．網(wǎng)絡(luò)平衡原理


在TCP/IP協(xié)議中，數(shù)據(jù)包含有必要的網(wǎng)絡(luò)信息，因而在網(wǎng)絡(luò)緩存或網(wǎng)絡(luò)平衡的具體實(shí)現(xiàn)算法里，數(shù)據(jù)包的信息很重要。但由于數(shù)據(jù)包是面向分組的（IP）和面向連接的（TCP），且經(jīng)常被分片，沒有與應(yīng)用有關(guān)的完整信息，特別是和連接會(huì)話相關(guān)的狀態(tài)信息。因此必須從連接的角度看待數(shù)據(jù)包——從源地址的端口建立到目的地址端口的連接。


平衡考慮的另一個(gè)要素就是節(jié)點(diǎn)的資源使用狀態(tài)。由于負(fù)載平衡是這類系統(tǒng)的最終目的，那么及時(shí)、準(zhǔn)確的把握節(jié)點(diǎn)負(fù)載狀況，并根據(jù)各個(gè)節(jié)點(diǎn)當(dāng)前的資源使用狀態(tài)動(dòng)態(tài)調(diào)整負(fù)載平衡的任務(wù)分布，是網(wǎng)絡(luò)動(dòng)態(tài)負(fù)載平衡集群系統(tǒng)考慮的另一關(guān)鍵問題。


一般情況下，集群的服務(wù)節(jié)點(diǎn)可以提供諸如處理器負(fù)載，應(yīng)用系統(tǒng)負(fù)載、活躍用戶數(shù)、可用的網(wǎng)絡(luò)協(xié)議緩存以及其他的資源信息。信息通過高效的消息機(jī)制傳給平衡器，平衡器監(jiān)視所有處理節(jié)點(diǎn)的狀態(tài)，主動(dòng)決定下個(gè)任務(wù)傳給誰。平衡器可以是單個(gè)設(shè)備，也可以使一組平行或樹狀分布的設(shè)備。


3．基本的網(wǎng)絡(luò)負(fù)載平衡算法


平衡算法設(shè)計(jì)的好壞直接決定了集群在負(fù)載均衡上的表現(xiàn)，設(shè)計(jì)不好的算法，會(huì)導(dǎo)致集群的負(fù)載失衡。一般的平衡算法主要任務(wù)是決定如何選擇下一個(gè)集群節(jié)點(diǎn)，然后將新的服務(wù)請求轉(zhuǎn)發(fā)給它。有些簡單平衡方法可以獨(dú)立使用，有些必須和其它簡單或高級方法組合使用。而一個(gè)好的負(fù)載均衡算法也并不是萬能的，它一般只在某些特殊的應(yīng)用環(huán)境下才能發(fā)揮最大效用。因此在考察負(fù)載均衡算法的同時(shí)，也要注意算法本身的適用面，并在采取集群部署的時(shí)候根據(jù)集群自身的特點(diǎn)進(jìn)行綜合考慮，把不同的算法和技術(shù)結(jié)合起來使用。


3．1 輪轉(zhuǎn)法：


輪轉(zhuǎn)算法是所有調(diào)度算法中最簡單也最容易實(shí)現(xiàn)的一種方法。在一個(gè)任務(wù)隊(duì)列里，隊(duì)列的每個(gè)成員（節(jié)點(diǎn)）都具有相同的地位，輪轉(zhuǎn)法簡單的在這組成員中順序輪轉(zhuǎn)選擇。在負(fù)載平衡環(huán)境中，均衡器將新的請求輪流發(fā)給節(jié)點(diǎn)隊(duì)列中的下一節(jié)點(diǎn)，如此連續(xù)、周而復(fù)始，每個(gè)集群的節(jié)點(diǎn)都在相等的地位下被輪流選擇。這個(gè)算法在DNS域名輪詢中被廣泛使用。


輪轉(zhuǎn)法的活動(dòng)是可預(yù)知的，每個(gè)節(jié)點(diǎn)被選擇的機(jī)會(huì)是1/N，因此很容易計(jì)算出節(jié)點(diǎn)的負(fù)載分布。輪轉(zhuǎn)法典型的適用于集群中所有節(jié)點(diǎn)的處理能力和性能均相同的情況，在實(shí)際應(yīng)用中，一般將它與其他簡單方法聯(lián)合使用時(shí)比較有效。


3．2 散列法


散列法也叫哈希法（HASH），通過單射不可逆的HASH函數(shù)，按照某種規(guī)則將網(wǎng)絡(luò)請求發(fā)往集群節(jié)點(diǎn)。哈希法在其他幾類平衡算法不是很有效時(shí)會(huì)顯示出特別的威力。例如，在前面提到的UDP會(huì)話的情況下，由于輪轉(zhuǎn)法和其他幾類基于連接信息的算法，無法識(shí)別出會(huì)話的起止標(biāo)記，會(huì)引起應(yīng)用混亂。


而采取基于數(shù)據(jù)包源地址的哈希映射可以在一定程度上解決這個(gè)問題：將具有相同源地址的數(shù)據(jù)包發(fā)給同一服務(wù)器節(jié)點(diǎn)，這使得基于高層會(huì)話的事務(wù)可以以適當(dāng)?shù)姆绞竭\(yùn)行。相對稱的是，基于目的地址的哈希調(diào)度算法可以用在Web Cache集群中，指向同一個(gè)目標(biāo)站點(diǎn)的訪問請求都被負(fù)載平衡器發(fā)送到同一個(gè)Cache服務(wù)節(jié)點(diǎn)上，以避免頁面缺失而帶來的更新Cache問題。


3．3 最少連接法


在最少連接法中，平衡器紀(jì)錄目前所有活躍連接，把下一個(gè)新的請求發(fā)給當(dāng)前含有最少連接數(shù)的節(jié)點(diǎn)。這種算法針對TCP連接進(jìn)行，但由于不同應(yīng)用對系統(tǒng)資源的消耗可能差異很大，而連接數(shù)無法反映出真實(shí)的應(yīng)用負(fù)載，因此在使用重型Web服務(wù)器作為集群節(jié)點(diǎn)服務(wù)時(shí)（例如Apache服務(wù)器），該算法在平衡負(fù)載的效果上要打個(gè)折扣。為了減少這個(gè)不利的影響，可以對每個(gè)節(jié)點(diǎn)設(shè)置最大的連接數(shù)上限（通過閾值設(shè)定體現(xiàn)）。


3．4 最低缺失法


在最低缺失法中，平衡器長期紀(jì)錄到各節(jié)點(diǎn)的請求情況，把下個(gè)請求發(fā)給歷史上處理請求最少的節(jié)點(diǎn)。與最少連接法不同的是，最低缺失記錄過去的連接數(shù)而不是當(dāng)前的連接數(shù)。


3．5 最快響應(yīng)法


平衡器記錄自身到每一個(gè)集群節(jié)點(diǎn)的網(wǎng)絡(luò)響應(yīng)時(shí)間，并將下一個(gè)到達(dá)的連接請求分配給響應(yīng)時(shí)間最短的節(jié)點(diǎn)，這種方法要求使用ICMP包或基于UDP包的專用技術(shù)來主動(dòng)探測各節(jié)點(diǎn)。


在大多數(shù)基于LAN的集群中，最快響應(yīng)算法工作的并不是很好，因?yàn)長AN中的ICMP包基本上都在10ms內(nèi)完成回應(yīng)，體現(xiàn)不出節(jié)點(diǎn)之間的差異；如果在 WAN上進(jìn)行平衡的話，響應(yīng)時(shí)間對于用戶就近選擇服務(wù)器而言還是具有現(xiàn)實(shí)意義的；而且集群的拓?fù)湓椒稚⑦@種方法越能體現(xiàn)出效果來。這種方法是高級平衡基于拓?fù)浣Y(jié)構(gòu)重定向用到的主要方法。


3．6 加權(quán)法


加權(quán)方法只能與其他方法合用，是它們的一個(gè)很好的補(bǔ)充。加權(quán)算法根據(jù)節(jié)點(diǎn)的優(yōu)先級或當(dāng)前的負(fù)載狀況（即權(quán)值）來構(gòu)成負(fù)載平衡的多優(yōu)先級隊(duì)列，隊(duì)列中的每個(gè)等待處理的連接都具有相同處理等級，這樣在同一個(gè)隊(duì)列里可以按照前面的輪轉(zhuǎn)法或者最少連接法進(jìn)行均衡，而隊(duì)列之間按照優(yōu)先級的先后順序進(jìn)行均衡處理。在這里權(quán)值是基于各節(jié)點(diǎn)能力的一個(gè)估計(jì)值。


4、動(dòng)態(tài)反饋負(fù)載均衡


當(dāng)客戶訪問集群資源時(shí)，提交的任務(wù)所需的時(shí)間和所要消耗的計(jì)算資源是千差萬別的，它依賴于很多因素。例如：任務(wù)請求的服務(wù)類型、當(dāng)前網(wǎng)絡(luò)帶寬的情況、以及當(dāng)前服務(wù)器資源利用的情況等等。一些負(fù)載比較重的任務(wù)需要進(jìn)行計(jì)算密集的查詢、數(shù)據(jù)庫訪問、很長響應(yīng)數(shù)據(jù)流；而負(fù)載比較輕的任務(wù)請求往往只需要讀一個(gè)小文件或者進(jìn)行很簡單的計(jì)算。


對任務(wù)請求處理時(shí)間的不同可能會(huì)導(dǎo)致處理結(jié)點(diǎn)利用率的傾斜（Skew），即處理結(jié)點(diǎn)的負(fù)載不平衡。有可能存在這樣情況，有些結(jié)點(diǎn)已經(jīng)超負(fù)荷運(yùn)行，而其他結(jié)點(diǎn)基本是閑置著。同時(shí)，有些結(jié)點(diǎn)已經(jīng)忙不過來，有很長的請求隊(duì)列，還不斷地收到新的請求。反過來說，這會(huì)導(dǎo)致客戶長時(shí)間的等待，而集群整體的服務(wù)質(zhì)量下降。因此，有必要采用一種機(jī)制，使得平衡器能夠?qū)崟r(shí)地了解各個(gè)結(jié)點(diǎn)的負(fù)載狀況，并能根據(jù)負(fù)載的變化做出調(diào)整。


具體的做法上采用了基于負(fù)反饋機(jī)制的動(dòng)態(tài)負(fù)載均衡算法，該算法考慮每一個(gè)結(jié)點(diǎn)的實(shí)時(shí)負(fù)載和響應(yīng)能力，不斷調(diào)整任務(wù)分布的比例，來避免有些結(jié)點(diǎn)超載時(shí)依然收到大量請求，從而提高單一集群的整體吞吐率。


在集群內(nèi)，負(fù)載均衡器上運(yùn)行服務(wù)端監(jiān)控進(jìn)程，監(jiān)控進(jìn)程負(fù)責(zé)監(jiān)視和收集集群內(nèi)各個(gè)結(jié)點(diǎn)的負(fù)載信息；而每個(gè)結(jié)點(diǎn)上運(yùn)行客戶端進(jìn)程，負(fù)責(zé)定時(shí)向均衡器報(bào)告自身的負(fù)載狀況。監(jiān)控進(jìn)程根據(jù)收到的全部結(jié)點(diǎn)的負(fù)載信息來進(jìn)行同步操作，既對將要分配的任務(wù)按照權(quán)值得比例重新進(jìn)行分布。權(quán)值得計(jì)算主要根據(jù)各個(gè)結(jié)點(diǎn)的CPU 利用率、可用內(nèi)存以及磁盤I/O狀況計(jì)算出新的權(quán)值，若新權(quán)值和當(dāng)前權(quán)值的差值大于設(shè)定的閥值，監(jiān)控器采用新的權(quán)值對集群范圍內(nèi)的任務(wù)重新進(jìn)行分布，直到下一次的負(fù)載信息同步到來之前。均衡器可以配合動(dòng)態(tài)權(quán)值，采用加權(quán)輪詢算法來對接受的網(wǎng)絡(luò)服務(wù)請求進(jìn)行調(diào)度。


4．1 加權(quán)輪詢調(diào)度


加權(quán)輪詢調(diào)度（Weighted Round-Robin Scheduling）算法用相應(yīng)的權(quán)值表示結(jié)點(diǎn)的處理性能。該算法根據(jù)權(quán)值的高低順序并按照輪詢的方式將任務(wù)請求分配到各結(jié)點(diǎn)。權(quán)值高的結(jié)點(diǎn)比權(quán)值低的結(jié)點(diǎn)處理更多的任務(wù)請求，相同權(quán)值的結(jié)點(diǎn)處理相同份額的請求。加權(quán)輪詢的基本原理可描述為：


假設(shè)某集群內(nèi)有一組結(jié)點(diǎn)N = {N0, N1, …, Nn-1}，W(Ni)表示結(jié)點(diǎn)Ni的權(quán)值，


一個(gè)指示變量i表示上一次選擇的服務(wù)器，T（Ni）表示結(jié)點(diǎn)Ni當(dāng)前所分配的任務(wù)量。


∑T(Ni) 表示當(dāng)前同步周期需要處理的任務(wù)總量。


∑W(Ni) 表示結(jié)點(diǎn)的權(quán)值總和。


則： W(Ni)/ ∑W(Ni)= T(Ni)/ ∑T(Ni)


表示任務(wù)的分配是按照各個(gè)結(jié)點(diǎn)權(quán)值占權(quán)值總數(shù)的比例來進(jìn)行分配。


4.2 權(quán)值計(jì)算


當(dāng)集群的結(jié)點(diǎn)初次投入系統(tǒng)中使用時(shí)，系統(tǒng)管理員根據(jù)結(jié)點(diǎn)的硬件配置情況對每個(gè)結(jié)點(diǎn)都設(shè)定一個(gè)初始權(quán)值DW（Ni）（通常根據(jù)結(jié)點(diǎn)的硬件配置來定義，硬件配置越高的結(jié)點(diǎn)默認(rèn)值越高），在負(fù)載均衡器上也先使用這個(gè)權(quán)值。然后，隨著結(jié)點(diǎn)負(fù)載的變化，均衡器對權(quán)值進(jìn)行調(diào)整。


動(dòng)態(tài)權(quán)值是由結(jié)點(diǎn)運(yùn)行時(shí)各方面的參數(shù)計(jì)算出來的。我們在實(shí)驗(yàn)中選取了最重要幾項(xiàng)，包括：CPU資源，內(nèi)存資源，當(dāng)前進(jìn)程數(shù)，響應(yīng)時(shí)間等信息作為計(jì)算公式的因子。結(jié)合每個(gè)結(jié)點(diǎn)當(dāng)前的權(quán)值，可以計(jì)算出新的權(quán)值的大小。動(dòng)態(tài)權(quán)值目的是要正確反映結(jié)點(diǎn)負(fù)載的狀況，以預(yù)測結(jié)點(diǎn)將來可能的負(fù)載變化。對于不同類型的系統(tǒng)應(yīng)用，各個(gè)參數(shù)的重要程度也有所不同。典型的Web應(yīng)用環(huán)境下，可用內(nèi)存資源和響應(yīng)時(shí)間就非常重要；如果用戶以長的數(shù)據(jù)庫事務(wù)為主，則CPU使用率和可用內(nèi)存就相對重要一些。為了方便在系統(tǒng)運(yùn)行過程中針對不同的應(yīng)用對各個(gè)參數(shù)的比例進(jìn)行適當(dāng)調(diào)整，我們?yōu)槊恳粋€(gè)參數(shù)設(shè)定一個(gè)常量系數(shù) Ri ，用來來表示各個(gè)負(fù)載參數(shù)的重要程度，其中Σ Ri = 1。因此，任何一個(gè)結(jié)點(diǎn)Ni的權(quán)值公式就可以描述為：


LOAD(Ni)=R1*Lcpu(Ni)+R2*Lmemory(Ni)+R3*Lio(Ni)+R4*Lprocess(Ni)+R5*Lresponse(Ni)


其中Lf(Ni) 表示結(jié)點(diǎn)Ni 當(dāng)前某一項(xiàng)參數(shù)的負(fù)載值，


上述公式中依次表示為：CPU使用率、內(nèi)存使用率、


磁盤I/O訪問率、進(jìn)程總數(shù)以及響應(yīng)時(shí)間。


例如，在WEB服務(wù)器集群中，我們采用以系數(shù){0.1, 0.4, 0.1, 0.1, 0.3}，這里認(rèn)為服務(wù)器的內(nèi)存和請求響應(yīng)時(shí)間較其他參數(shù)重要一些。若當(dāng)前的系數(shù)Ri不能很好地反映應(yīng)用的負(fù)載，系統(tǒng)管理員可以對系數(shù)不斷地修正，直到找到貼近當(dāng)前應(yīng)用的一組系數(shù)。


另外，關(guān)于采集權(quán)值的周期置，雖然很短的周期可以更確切地反映各個(gè)結(jié)點(diǎn)的負(fù)載，但是很頻繁地采集（如1秒1次或者多次）會(huì)給均衡器和結(jié)點(diǎn)帶來負(fù)擔(dān)，也可能增加不必要的網(wǎng)絡(luò)負(fù)荷。另外，由于采集器是在采集時(shí)刻進(jìn)行負(fù)載計(jì)算的，經(jīng)實(shí)驗(yàn)證明，均衡器反映出來各個(gè)結(jié)點(diǎn)的負(fù)載信息會(huì)出現(xiàn)劇烈的抖動(dòng)，均衡器無法準(zhǔn)確捕捉結(jié)點(diǎn)真實(shí)的負(fù)載變化趨勢。因此解決這些問題，一方面要適當(dāng)?shù)卣{(diào)整采集負(fù)載信息的周期，一般在5～10秒；另一方面，可以使用移動(dòng)平均線或者是滑動(dòng)窗口來避免抖動(dòng)，使得均衡器收集到的負(fù)載信息表現(xiàn)為平滑曲線，這樣在負(fù)反饋機(jī)制的調(diào)整效果上就會(huì)比較好。


均衡器的動(dòng)態(tài)權(quán)值采集程序周期性地運(yùn)行，若缺省權(quán)值不為零，則查詢該結(jié)點(diǎn)的各負(fù)載參數(shù)，并計(jì)算出動(dòng)態(tài)權(quán)值LOAD(Ni) 。我們引入以下權(quán)值計(jì)算公式，結(jié)合結(jié)點(diǎn)的初始權(quán)值和采集的動(dòng)態(tài)權(quán)值來計(jì)算最終的權(quán)值結(jié)果。


Wi = A*DW(Ni)+B*(LOAD(Ni)-DW(Ni))1/3


在公式中，如果動(dòng)態(tài)權(quán)值恰好等于初始權(quán)值，最終權(quán)值不變，則說明系統(tǒng)的負(fù)載狀況剛好達(dá)到理想狀況，等于初始權(quán)值DW(Ni)。如果動(dòng)態(tài)權(quán)值計(jì)算結(jié)果高于初始權(quán)值，最終權(quán)值變高，則說明系統(tǒng)負(fù)載很輕，均衡器將會(huì)增加分配給該結(jié)點(diǎn)的任務(wù)比率。如果動(dòng)態(tài)權(quán)值低于初始權(quán)值，最終權(quán)值變低，說明系統(tǒng)開始處于重載狀況，均衡器將會(huì)減少對該結(jié)點(diǎn)分配的任務(wù)。在實(shí)際使用中，若發(fā)現(xiàn)所有結(jié)點(diǎn)的權(quán)值都小于他們的DW(Ni)，則說明當(dāng)前個(gè)集群處于超載狀態(tài)，這時(shí)需要加入新的結(jié)點(diǎn)到集群中來處理部分負(fù)載；反之，若所有結(jié)點(diǎn)的權(quán)值大大高于DW(Ni)，則說明當(dāng)前系統(tǒng)的負(fù)載都比較輕。


5、總結(jié)


網(wǎng)絡(luò)負(fù)載平衡是集群作業(yè)調(diào)度系統(tǒng)的具體實(shí)現(xiàn)。由于其處理的作業(yè)單元是TCP/IP協(xié)議下的網(wǎng)絡(luò)連接，因此可以采用面向網(wǎng)絡(luò)連接的集中基本調(diào)度算法?？紤]集群負(fù)載不平衡的可能，采取了動(dòng)態(tài)獲取服務(wù)節(jié)點(diǎn)的權(quán)值并使用負(fù)反饋機(jī)制調(diào)整平衡器對網(wǎng)絡(luò)服務(wù)請求的分布，以適應(yīng)服務(wù)節(jié)點(diǎn)在運(yùn)行過程中資源的變化。筆者也在 LVS集群系統(tǒng)的基礎(chǔ)上，配合原有的輪詢算法對其進(jìn)行改進(jìn)，增加了采集動(dòng)態(tài)權(quán)值的程序并實(shí)時(shí)反饋到負(fù)載平衡器的調(diào)度系統(tǒng)上。實(shí)踐證明，采用動(dòng)態(tài)平衡在集群系統(tǒng)的整體吞吐量方面有所提高，特別是在集群各個(gè)節(jié)點(diǎn)性能不一，集群提供的網(wǎng)絡(luò)服務(wù)程序所訪問的資源多樣化的情況下，負(fù)反饋機(jī)制的效果尤其明顯。在其他類型的集群中，負(fù)反饋機(jī)制的動(dòng)態(tài)負(fù)載平衡也能夠得到很好的應(yīng)用，只是平衡器所處理的作業(yè)單元不同于網(wǎng)絡(luò)連接，而具體的負(fù)載算法上也將有所不同。