ローカルベースの最小リンク(Locality-Based Least Connections Scheduling)

ローカルベースの最小リンクスケジューリング(Locality-Based Least Connections Scheduling、以下LBLCと略す)アルゴリズムは、Cacheクラスタにおいてクライアントがメッセージを要求するターゲットIPアドレスが変化するため、メッセージを要求するターゲットIPアドレスに対する負荷等化スケジューリングであり、現在は主にCacheクラスタシステムに用いられている.ここでは、任意のバックエンドサーバが任意の要求を処理できると仮定し、アルゴリズムの設計目標は、サーバの負荷が基本的にバランスしている場合に、同じターゲットIPアドレスの要求を同じサーバにスケジューリングし、各サーバのアクセス局所性とプライマリ・ストレージ・Cache命中率を向上させ、クラスタ・システム全体の処理能力を向上させることである.
LBLCスケジューリングアルゴリズムは、まず、要求されたターゲットIPアドレスに基づいて、そのターゲットIPアドレスが最近使用されたサーバを探し出し、そのサーバが利用可能で過負荷がなければ、要求をそのサーバに送信する.サーバが存在しない場合、またはサーバがオーバーロードされ、サーバの半分のワークロードがある場合は、「最小リンク」の原則で使用可能なサーバを選択し、要求をサーバに送信します.アルゴリズムの詳細は次のとおりです.
LBLCスケジューリングアルゴリズムフロー

        S = {S0, S1, ..., Sn-1}，W(Si)     Si   ，
C(Si)     Si      。ServerNode[dest_ip]       ，  
  IP           ，        Hash    。WLC(S)  
   S           ，            。Now     
  。

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;

また、関連変数ServerNode[dest_ip]に対して周期的なゴミ回収(Garbage Collection)を行い、期限切れの宛先IPアドレスをサーバ関連項目に回収する.期限切れの関連項目とは、現在の時間(実装時にシステムクロックビート数jiffiesを使用)から最近の使用時間が設定期限切れ時間を超えた関連項目を減算し、システムのデフォルトの設定期限切れ時間は24時間です.