/**

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

    }

}