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