广场 › 数据库 › Memcached 之PHP实现服务器集群一致性hash算法

Green 发表于 2021-7-22 13:14:15

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);
    }
}

文档来源：51CTO技术博客https://blog.51cto.com/u_15309652/3156248

查看完整版本: Memcached 之PHP实现服务器集群一致性hash算法