[NoSQL] Memcached 之PHP实现服务器集群一致性hash算法

/**
 * memcached 一致性hash，分布式算法
 * Class MemcacheCluster
 */
class MemcacheCluster
{
  protected $nodes = array(); //服务器节点
  protected $position = array(); //虚拟节点
  protected $virtualNum = 32;  //每个节点有32个虚拟节点；具体数量也可以 16 ，8等
  public function hash($str)
  {
    //将字符串转成32位符号整数
    return sprintf("%u", crc32($str));
  }
  //查找key 落到哪个节点上
  public function findNode($key)
  {
    $point = $this->hash($key);
    //先取圆环上最小的一个节点
    //$key 哈希后比最大的节点都大就放到第一个节点
    $node = current($this->position);
    //下面这个查找可以后期优化为二分查找法。
    foreach ($this->position as $k => $v) {
      if ($point <= $k) {
        $node = $v;
        break;
      }
    }
    //复位数组指针
    reset($this->position);
    return $node;
  }
  public function addNode($node)
  {
    if (isset($this->nodes[$node])) {
      return;
    }
    for ($i = 0; $i < $this->virtualNum; $i++) {
      $pos = $this->hash($node . '-' . $i);
      $this->position[$pos] = $node;
      //方便删除对应的虚拟节点
      $this->nodes[$node][] = $pos;
    }
    $this->sortPos();
  }
  public function delNode($node)
  {
    if (!isset($this->nodes[$node])) {
      return;
    }
    //循环所有的虚节点,谁的值==指定的真实节点 ,就把他删掉
    foreach ($this->nodes[$node] as $k) {
      unset($this->position[$k]);
    }
    unset($this->nodes[$node]);
  }
  protected function sortPos()
  {
    //将虚拟节点排序
    //把每一项按常规顺序排列（Standard ASCII，不改变类型）
    ksort($this->position, SORT_REGULAR);
  }
}