相信學(xué)過(guò)C語(yǔ)言的朋友，或者是IT工作者們都會(huì)對(duì)算法一次不陌生。那么，針對(duì)不同的領(lǐng)域，對(duì)算法的簡(jiǎn)易度也是不一樣的。在語(yǔ)言類，編程類，網(wǎng)絡(luò)類等，算法的使用基本上就是整個(gè)結(jié)構(gòu)的基礎(chǔ)。那么我們現(xiàn)在就來(lái)介紹一下負(fù)載均衡算法的種類。看一看它都有些什么類型。

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

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

負(fù)載均衡算法1 輪轉(zhuǎn)法

輪轉(zhuǎn)算法是所有調(diào)度算法中最簡(jiǎn)單也最容易實(shí)現(xiàn)的一種方法｡在一個(gè)任務(wù)隊(duì)列里,隊(duì)列的每個(gè)成員(節(jié)點(diǎn))都具有相同的地位,輪轉(zhuǎn)法簡(jiǎn)單的在這組成員中順序輪轉(zhuǎn)選擇｡在負(fù)載均衡環(huán)境中,均衡器將新的請(qǐng)求輪流發(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)用中,一般將他與其他簡(jiǎn)單方法聯(lián)合使用時(shí)比較有效｡

負(fù)載均衡算法2 散列法

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

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

負(fù)載均衡算法3 最少連接法

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

負(fù)載均衡算法4 最低缺失法

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

負(fù)載均衡算法5 最快響應(yīng)法

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

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

負(fù)載均衡算法6 加權(quán)法

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