基于局部性的最少鏈接算法及其實(shí)現(xiàn)原理
來源：中國(guó)政府采購(gòu)招標(biāo)網(wǎng) 時(shí)間：2008/9/22
在負(fù)載均衡產(chǎn)品的調(diào)度器(Load Balancer)的實(shí)現(xiàn)技術(shù)中，IP負(fù)載均衡技術(shù)是效率最高的。這里我們將要介紹的LBLC和LBLCR就是實(shí)現(xiàn)IP負(fù)載均衡技術(shù)的兩種方式。
基于局部性的最少鏈接調(diào)度算法
這里講的LBLC，即基于局部性的最少鏈接調(diào)度(Locality-Based Least Connections Scheduling)算法就是針對(duì)請(qǐng)求報(bào)文的目標(biāo)IP地址的負(fù)載均衡調(diào)度。
這種算法的前提假設(shè)是：任意一臺(tái)服務(wù)器都可以處理任一請(qǐng)求。算法的設(shè)計(jì)目標(biāo)是在服務(wù)器的負(fù)載基本平衡情況下，將相同目標(biāo)IP地址的請(qǐng)求調(diào)度到同一臺(tái)服務(wù)器，來提高各臺(tái)服務(wù)器的訪問局部性和主存Cache命中率，從而整個(gè)集群系統(tǒng)的處理能力。
LBLC調(diào)度算法先根據(jù)請(qǐng)求的目標(biāo)IP地址找出該目標(biāo)IP地址最近使用的服務(wù)器，若該服務(wù)器是可用的且沒有超載，將請(qǐng)求發(fā)送到該服務(wù)器;若服務(wù)器不存在，或者該服務(wù)器超載且有其它服務(wù)器處于其一半的工作負(fù)載，則用”最少鏈接”的原則選出一個(gè)可用的服務(wù)器，將請(qǐng)求發(fā)送到該服務(wù)器。
由于在Cache集群中客戶請(qǐng)求報(bào)文的目標(biāo)IP地址是變化的，所以此種均衡算法主要應(yīng)用在Cache集群系統(tǒng)中。
最少連接數(shù)調(diào)度算法流程
假設(shè)有一組服務(wù)器S = {S0, S1, ..., Sn-1}，W(Si)表示服務(wù)器Si的權(quán)值，
C(Si)表示服務(wù)器Si的當(dāng)前連接數(shù)。ServerNode[dest_ip]是一個(gè)關(guān)聯(lián)變量，表示目標(biāo)IP地址所對(duì)應(yīng)的服務(wù)器結(jié)點(diǎn)，一般來說它是通過Hash表實(shí)現(xiàn)的。WLC(S)表示在集合S中的加權(quán)最小連接服務(wù)器，即前面的加權(quán)最小連接調(diào)度。Now為當(dāng)前系統(tǒng)時(shí)間。
if (ServerNode[dest_ip] is NULL) then {
n = WLC(S);
if (n is NULL) then return NULL;
ServerNode[dest_ip].server = n;
} else {
n = ServerNode[dest_ip].server;
if ((n is dead) OR
(C(n) > W(n) AND
there is a node m with C(m) < W(m)/2))) then {
n = WLC(S);
if (n is NULL) then return NULL;
ServerNode[dest_ip].server = n;
}
}
ServerNode[dest_ip].lastuse = Now;
return n;
帶復(fù)制的基于局部性最少鏈接調(diào)度(LBLCR)
LBLCR，即Locality-Based Least Connections Scheduling with Replication，也就是帶復(fù)制的基于局部性最少鏈接調(diào)度。LBLCR算法也是針對(duì)目標(biāo)IP地址的負(fù)載均衡，也是主要用于Cache集群系統(tǒng)。
它與LBLC算法基本相同，唯一的不同之處是它要維護(hù)從一個(gè)目標(biāo)IP地址到一個(gè)服務(wù)器組的映射，而LBLC算法維護(hù)從一個(gè)目標(biāo)IP地址到一臺(tái)服務(wù)器的映射。
LBLC算法的主要缺點(diǎn)是：對(duì)于一個(gè)“熱門”站點(diǎn)的服務(wù)請(qǐng)求，一臺(tái)Cache服務(wù)器可能會(huì)忙不過來處理這些請(qǐng)求。這時(shí)，LBLC調(diào)度算法會(huì)從所有的Cache服務(wù)器中按“最小連接”原則選出一臺(tái)Cache服務(wù)器，映射該“熱門”站點(diǎn)到這臺(tái)Cache服務(wù)器，很快這臺(tái)Cache服務(wù)器也會(huì)超載，就會(huì)重復(fù)上述過程選出新的Cache服務(wù)器。這樣，可能會(huì)導(dǎo)致該“熱門”站點(diǎn)的映像會(huì)出現(xiàn)在所有的Cache服務(wù)器上，降低了Cache服務(wù)器的使用效率。