PHP 一致性哈希算法的一种简单实现

在分布式系统中，如果某业务可以由多个相同的节点处理，很容易想到用HASH的方式将业务请求分散到这些节点处理，比如memecache缓存等分 布式集群应用，如果只是简单的使用，不涉及用户用户状态等信息，则可以直接采用取模算法。正常情况下，取模算法好像也不错，但是一旦增加节点或者其中一个 节点上宕机的话，命中率将会急剧降低，所以取模算法在这种情况下弊端很明显，为此，在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法。 具体的算法介绍我这里不多少了，需要了解的可以参见本文：http://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html

 

下面贴一个用PHP对其进行的简单实现

class Hash
{
    //落点集合,可以缓存起来
    private $_locations = array();
    //虚拟节点数量
    private $virtualNodeNum = 24;
    //维护的另一种节点和虚拟节点对应关系，方便删除
    private $_nodes;
    //将字符串转成数字
    private function _hash($str)
    {
        return sprintf('%u', crc32($str));
    }

    /**
     * 寻找字符串所在的机器位置
     * @param $str
     * @return bool|mixed
     */
    public function getLocation($str)
    {
        if(empty($this->_locations)){
            return false;
        }else{
            $position = $this->_hash($str);
            //默认取第一个节点
            $node = current($this->_locations);
            foreach($this->_locations as $k=>$v){
                //如果当前的位置，小于或等于节点组中的一个节点，那么当前位置对应该节点
                if($position <= $k){
                    $node = $v;
                    break;
                }
            }
            return $node;
        }
    }

    /**
     * 添加一个节点
     * @param $node
     */
    public function addNode($node)
    {
        //生成虚拟节点
        for($i=0;$i<$this->virtualNodeNum;$i++){
            $tmp = $this->_hash($node.$i);
            $this->_locations[$tmp] = $node;
            $this->_nodes[$node][] = $tmp;
        }
        //对节点排序
        ksort($this->_locations,SORT_NUMERIC);
    }

    /**
     * 删除一个节点
     * @param $node
     */
    public function deleteNode($node)
    {
        foreach($this->_nodes[$node] as $v){
            unset($this->_locations[$v]);
        }
    }

}