libmemcached的一致性hash算法

memcached的客户端用了一致性hash来定位每个服务器所在位置。

以libmemcached库为例，在memcached_server_by_key函数中，首先根据hashkit中指定的哈希算法从key中计算出一个哈希值来，然后根据如下算法，从所有的节点中找到一个离自己最近的节点：

如果哈希值在最后一个节点上，或在最后一个节点和倒数第二个节点之间的话，则返回第一个节点

否则返回哈希值后面里自己最近的一个节点。

代码：

      while (left < right)
      {
        middle= left + (right - left) / 2;
        if (middle->value < hash)
          left= middle + 1;
        else
          right= middle;
      }
      if (right == end)
        right= begin;
      return right->index;

 这个算法很奇怪，没有看懂，明天继续分析