基于局部性的最小连接调度

在基于局部性的最小连接负载调度（Locality-Based Least-Connection Scheduling）中，我们假设任何后端服务器都可以处理任一请求。算法的目标是在后端服务器的负载平衡情况下，提高后端服务器的访问局部性，从而提高后端服务器的主存Cache命中率。

在WEB应用中，来自不同用户的请求很有可能重叠，WEB访问流中存在空间的局部性，容易获得WEB请求的URL，所以，LBLC算法主要针对WEB应用。静态WEB页面的请求格式如下：

<scheme>://<host>:<port>/<path>

其中，区分页面不同的变量是文件的路径<path>，我们将之记为请求的目标。CGI动态页面的格式如下：

<scheme>://<host>:<port>/<path>?<query>

我们将其中的CGI文件路径<path>记为请求的目标。因为CGI程序一般要读一个或者多个文件来生成一个动态页面，若在服务器负载基本平衡情况下将相同的CGI请求发送到同一服务器，可以提高服务器文件系统的Cache命中率。
LBLC算法的基本流程如下：

while (true) {
  get next request r;
  r.target = { extract path from static/dynamic request r };
  if (server[r.target] == NULL) then {
    n = { least connection node };
    server[r.target] = n;
  } else {
    n = server[r.target];
    if (n.conns > n.high && a node with node.conns < node.low) || 
      n.conns >= 2*n.high then {
      n = { least connection node };
      server[r.target] = n;
    }
  }
  if (r is dynamic request) then
    n.conns = n.conns + 2;
  else
    n.conns = n.conns + 1;
  send r to n and return results to the client;
  if (r is dynamic request) then
    n.conns = n.conns - 2;
  else
    n.conns = n.conns - 1;
}

在算法中，我们用后端服务器的活跃连接数（n.conns）来表示它的负载，server是个关联变量，它将访问的目标和服务器对应起来。在这里，假设动态页面的处理是静态页面的2倍。开销算法的意图是将请求序列进行分割，相同的请求去同一服务器，可以提高访问的局部性；除非出现严重的负载不平衡了，我们进行调整，重新分配该请求的服务器。我们不想因为微小或者临时的负载不平衡，进行重新分配服务器，会导致Cache不命中和磁盘访问。所以，“严重的负载不平衡”是为了避免有些服务器空闲着而有服务器超载了。

我们定义每个结点有连接数目的高低阀值，当结点的连接数（node.conns）小于其连接数低阀值（node.low）时，表明该结点有空闲资源；当结点的连接数（node.conns）大于其连接数高阀值（node.high）时，表明该结点在处理请求时可能会有一定的延时。在调度中，当一个结点的连接数大于其高阀值并且有结点的连接数小于其低阀值时，重新分配，将请求发到负载较轻的结点上。还有，为了限制结点过长的响应延时，当结点的连接数大于2倍的高阀值时，将请求重新分配到负载较轻的结点，不管是否有结点的连接数小于它的低阀值。

我们在调度器上进行限制后端服务器的正在处理连接数必须小于∑node.high，这样可以避免所有结点的连接数大于它们的2倍的高阀值。这样，可以保证当有结点的连接数大于2倍的高阀值时，必有结点的连接数小于其高阀值。

正确选择结点的高低阀值是根结点的处理性能相关的。在实践中，结点的低阀值应尽可能高来避免空闲资源，否则会造成结点的低吞吐率；结点的高阀值应该一个较高的值并且结点的响应延时不大。选择结点的高低阀值是一个折衷平衡的过程，结点的高低阀值之差有一定空间，这样可以限制负载不平衡和短期负载不平衡，而不破坏访问的局部性。对于一般结点，我们选择高低阀值分别为30和60；对于性能很高的结点，可以将其阀值相应调高。

在基本的LBLC算法中，在任何时刻，任一请求目标只能由一个结点来服务。然而，有可能一个请求目标会导致一个后端服务器进入超载状态，这样比较理想的方法就是由多个服务器来服务这个文档，将请求负载均衡地分发到这些服务器上。这样，我们设计了带复制的LBLC算法，其流程如下：

while (true) {
  get next request r;
  r.target = { extract path from static/dynamic request r };
  if (serverSet[r.target] == ∮) then {
    n = { least connection node };
    add n to serverSet[r.target];
  } else {
    n = {least connection node in serverSet[r.target]};
    if (n.conns > n.high && a node with node.conns < node.low) || 
      n.conns >= 2*n.high then {
      n = { least connection node };
      add n to serverSet[r.target];
    }
    if |serverSet[r.target]| > 1 
      && time()-serverSet[r.target].lastMod > K then {
      m = {most connection node in serverSet[r.target]};
      remove m from serverSet[r.target];
    }
  }
  if (r is dynamic request) then
    n.conns = n.conns + 2;
  else
    n.conns = n.conns + 1;
  send r to n and return results to the client;
  if (r is dynamic request) then
    n.conns = n.conns - 2;
  else
    n.conns = n.conns - 1;
  if (serverSet[r.target] changed) then
    serverSet[r.target].lastMod = time();
}

这个算法与原来算法的差别是调度器维护请求目标到一个能服务该目标的结点集合。请求会被分发到其目标的结点集中负载最轻的一个，调度器会检查是否发生结点集中存在负载不平衡，若是，则挑选所有结点中负载最轻的一个，将它加入该目标的结点集中，让它来服务该请求。另一方面，当请求目标的结点集有多个服务器，并且上次结点集的修改时间之差大于K秒时，将最忙的一个结点从该目标的结点集中删除。在实验中，K的缺省值为60秒。