lblc算法使用問(wèn)題

wing731

剛學(xué)集群，遇到一個(gè)LBLC算法使用的問(wèn)題:
我想使用LBCL算法來(lái)提供cache命中率，將相同目標(biāo)地址的請(qǐng)求調(diào)度到同一臺(tái)服務(wù)器，來(lái)提高各臺(tái)服務(wù)器的訪問(wèn)局部性和主存Cache命中率，從而整個(gè)集群系統(tǒng)的處理能力。
                    
                                          _____squid 1
                                       /
                       director------squid 2
                                       \
                                         -----squid 3

這樣dr上是否要有3個(gè)vip，與這3個(gè)squid對(duì)應(yīng)，或是怎么根據(jù)目標(biāo)地址去判定然后調(diào)動(dòng)？

kns1024wh

2.5. 基于局部性的最少鏈接調(diào)度

基于局部性的最少鏈接調(diào)度（Locality-Based Least Connections Scheduling，以下簡(jiǎn)稱為L(zhǎng)BLC）算法是針對(duì)請(qǐng)求報(bào)文的目標(biāo)IP地址的負(fù)載均衡調(diào)度，目前主要用于Cache集群系統(tǒng)，因?yàn)樵贑ache集群中客戶請(qǐng)求報(bào)文的目標(biāo)IP地址是變化的。這里假設(shè)任何后端服務(wù)器都可以處理任一請(qǐng)求，算法的設(shè)計(jì)目標(biāo)是在服務(wù)器的負(fù)載基本平衡情況下，將相同目標(biāo)IP地址的請(qǐng)求調(diào)度到同一臺(tái)服務(wù)器，來(lái)提高各臺(tái)服務(wù)器的訪問(wèn)局部性和主存Cache命中率，從而整個(gè)集群系統(tǒng)的處理能力。

LBLC調(diào)度算法先根據(jù)請(qǐng)求的目標(biāo)IP地址找出該目標(biāo)IP地址最近使用的服務(wù)器，若該服務(wù)器是可用的且沒(méi)有超載，將請(qǐng)求發(fā)送到該服務(wù)器；若服務(wù)器不存在，或者該服務(wù)器超載且有服務(wù)器處于其一半的工作負(fù)載，則用“最少鏈接”的原則選出一個(gè)可用的服務(wù)器，將請(qǐng)求發(fā)送到該服務(wù)器。該算法的詳細(xì)流程如下：

LBLC調(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)，一般來(lái)說(shuō)它是通過(guò)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;



此外，對(duì)關(guān)聯(lián)變量ServerNode[dest_ip]要進(jìn)行周期性的垃圾回收（Garbage Collection），將過(guò)期的目標(biāo)IP地址到服務(wù)器關(guān)聯(lián)項(xiàng)進(jìn)行回收。過(guò)期的關(guān)聯(lián)項(xiàng)是指哪些當(dāng)前時(shí)間（實(shí)現(xiàn)時(shí)采用系統(tǒng)時(shí)鐘節(jié)拍數(shù)jiffies）減去最近使用時(shí)間超過(guò)設(shè)定過(guò)期時(shí)間的關(guān)聯(lián)項(xiàng)，系統(tǒng)缺省的設(shè)定過(guò)期時(shí)間為24小時(shí)。

2.6. 帶復(fù)制的基于局部性最少鏈接調(diào)度

帶復(fù)制的基于局部性最少鏈接調(diào)度（Locality-Based Least Connections with Replication Scheduling，以下簡(jiǎn)稱為L(zhǎng)BLCR）算法也是針對(duì)目標(biāo)IP地址的負(fù)載均衡，目前主要用于Cache集群系統(tǒng)。它與LBLC算法的不同之處是它要維護(hù)從一個(gè)目標(biāo)IP地址到一組服務(wù)器的映射，而LBLC算法維護(hù)從一個(gè)目標(biāo)IP地址到一臺(tái)服務(wù)器的映射。對(duì)于一個(gè)“熱門”站點(diǎn)的服務(wù)請(qǐng)求，一臺(tái)Cache 服務(wù)器可能會(huì)忙不過(guò)來(lái)處理這些請(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ù)上述過(guò)程選出新的Cache服務(wù)器。這樣，可能會(huì)導(dǎo)致該“熱門”站點(diǎn)的映像會(huì)出現(xiàn)在所有的Cache服務(wù)器上，降低了Cache服務(wù)器的使用效率。LBLCR調(diào)度算法將“熱門”站點(diǎn)映射到一組Cache服務(wù)器（服務(wù)器集合），當(dāng)該“熱門”站點(diǎn)的請(qǐng)求負(fù)載增加時(shí)，會(huì)增加集合里的Cache服務(wù)器，來(lái)處理不斷增長(zhǎng)的負(fù)載；當(dāng)該“熱門”站點(diǎn)的請(qǐng)求負(fù)載降低時(shí)，會(huì)減少集合里的Cache服務(wù)器數(shù)目。這樣，該“熱門”站點(diǎn)的映像不太可能出現(xiàn)在所有的Cache服務(wù)器上，從而提供Cache集群系統(tǒng)的使用效率。

LBLCR算法先根據(jù)請(qǐng)求的目標(biāo)IP地址找出該目標(biāo)IP地址對(duì)應(yīng)的服務(wù)器組；按“最小連接”原則從該服務(wù)器組中選出一臺(tái)服務(wù)器，若服務(wù)器沒(méi)有超載，將請(qǐng)求發(fā)送到該服務(wù)器；若服務(wù)器超載；則按“最小連接”原則從整個(gè)集群中選出一臺(tái)服務(wù)器，將該服務(wù)器加入到服務(wù)器組中，將請(qǐng)求發(fā)送到該服務(wù)器。同時(shí)，當(dāng)該服務(wù)器組有一段時(shí)間沒(méi)有被修改，將最忙的服務(wù)器從服務(wù)器組中刪除，以降低復(fù)制的程度。LBLCR調(diào)度算法的流程如下：

LBLCR調(diào)度算法流程
假設(shè)有一組服務(wù)器S = {S0, S1, ..., Sn-1}，W(Si)表示服務(wù)器Si的權(quán)值，
C(Si)表示服務(wù)器Si的當(dāng)前連接數(shù)。ServerSet[dest_ip]是一個(gè)關(guān)聯(lián)變量，表示
目標(biāo)IP地址所對(duì)應(yīng)的服務(wù)器集合，一般來(lái)說(shuō)它是通過(guò)Hash表實(shí)現(xiàn)的。WLC(S)表示
在集合S中的加權(quán)最小連接服務(wù)器，即前面的加權(quán)最小連接調(diào)度；WGC(S)表示在
集合S中的加權(quán)最大連接服務(wù)器。Now為當(dāng)前系統(tǒng)時(shí)間，lastmod表示集合的最近
修改時(shí)間，T為對(duì)集合進(jìn)行調(diào)整的設(shè)定時(shí)間。

if (ServerSet[dest_ip] is NULL) then {
        n = WLC(S);
        if (n is NULL) then return NULL;
        add n into ServerSet[dest_ip];
} else {
        n = WLC(ServerSet[dest_ip]);
        if ((n is NULL) OR
            (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;
                add n into ServerSet[dest_ip];
        } else
        if (|ServerSet[dest_ip]| > 1 AND
            Now - ServerSet[dest_ip].lastmod > T) then {
                m = WGC(ServerSet[dest_ip]);
                remove m from ServerSet[dest_ip];
        }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
        ServerSet[dest_ip].lastmod = Now;
return n;



此外，對(duì)關(guān)聯(lián)變量ServerSet[dest_ip]也要進(jìn)行周期性的垃圾回收（Garbage Collection），將過(guò)期的目標(biāo)IP地址到服務(wù)器關(guān)聯(lián)項(xiàng)進(jìn)行回收。過(guò)期的關(guān)聯(lián)項(xiàng)是指哪些當(dāng)前時(shí)間（實(shí)現(xiàn)時(shí)采用系統(tǒng)時(shí)鐘節(jié)拍數(shù)jiffies）減去最近使用時(shí)間（lastuse）超過(guò)設(shè)定過(guò)期時(shí)間的關(guān)聯(lián)項(xiàng)，系統(tǒng)缺省的設(shè)定過(guò)期時(shí)間為24小時(shí)。