<?php//原理概念请看我的上一篇随笔（http://www.cnblogs.com/tujia/p/5416614.html）或直接百度
/**
 * 接口：hash（哈希插口）、distribution（分布式算法接口）
 * 方法:
 * hash
 *     _hash，处理并返回一个字符串的哈希值
 * distribution
 *  _lookup：给它一个key，它要反正此key需要存取的目标服务器信息
 *
 *
 * 一致性哈希分布式算法类：ConsistentHash
 * 方法：
 *     addServ：    添加服务器
 *     addPos：    添加”虚拟节点“
 *     sortPos：    对所有”虚拟节点“进行排序，形成集群圈
 *  _hash:        实现插口的_hash方法
 *  _lookup:    实现插口的_lookup方法
 *
 * 测试用方法
 *     printServ:    打印集群中的服务器列表信息
 *     printPos:    打印集群中的虚拟节点列表信息
 *     decServ:    删除一台服务器及他的所有虚拟节点
 */

interface hash{
    public function _hash($str);
}

interface distribution{
    public function _lookup($key);
}

/**
* 一致性哈希算法类
*/
class ConsistentHash implements hash,distribution
{
    protected $mem_serv = array();//服务器列表
    protected $node_pos = array();//所有虚拟节点
    protected $mul         = 64;//第一台服务器弄64个虚拟节点
    /**
     * 添加服务器
     * @param array $serv_info 服务器配置信息，格式为：array('host':'127.0.0.1', 'port':11211);
     */
    public function addServ($serv_info){
        if(!is_array($serv_info) || !isset($serv_info['host']) || !isset($serv_info['port'])) return false;

        $str                        = $serv_info['host'] .':'. $serv_info['port'];
        $serv_key                     = $this->_hash($str);
        //记录服务器信息
        $this->mem_serv[$serv_key]     = $serv_info;

        //添加虚拟节点
        $this->addPos($serv_key);
        return true;
    }

    /**
     * 添加虚拟节点
     * @param string $serv_key 服务器的key
     */
    protected function addPos($serv_key){
        for($i=0; $i<$this->mul; $i++){
            $pos         = 'node_' . $serv_key . '_' . $i;
            $pos_hash     = $this->_hash($pos);
            $this->node_pos[$pos_hash] = $serv_key;
        }
        $this->sortPos();
        return true;
    }

    /**
     * 对所有虚拟节点进行排序
     */
    protected function sortPos(){
        return ksort($this->node_pos);
    }

    /**
     * 对字符串进行hash处理，返回其整数无符号整数值
     * @param  string $str 要进行处理的字符串
     */
    public function _hash($str){
        return sprintf("%u", crc32($str));
    }

    /**
     * 通过key计算它的落点服务器信息
     * @param  string $key 键
     */
    public function _lookup($key){
        $key_hash = $this->_hash($key);

        $serv_key = key($this->mem_serv);
        foreach ($this->node_pos as $pos=>$serv) {
            if($key_hash<=$pos){
                $serv_key = $serv;
                break;
            }
        }

        return $this->mem_serv[$serv_key];
    }

    /**
     * 以下的方法做为测试用
     */

    /**
     * 打印服务器列表
     * @return [type] [description]
     */
    public function printServ(){
        echo '<pre>';
        print_r($this->mem_serv);
        echo '</pre>';
    }

    public function printPos(){
        echo '<pre>';
        print_r($this->node_pos);
        echo '</pre>';
    }

    /**
     * 删除一个服务器及它的所有虚拟节点
     * @param  int $serv_key 服务器的hash值
     */
    public function decServ($serv_key=''){
        if(empty($serv_key)) $serv_key = key($this->mem_serv);
        unset($this->mem_serv[$serv_key]);
        return true;
    }
}

//测试
/*$dis = new ConsistentHash();
$dis->addServ(array('host'=>'127.0.0.1', 'port'=>11211));
$dis->addServ(array('host'=>'127.0.0.1', 'port'=>11212));
$dis->addServ(array('host'=>'127.0.0.1', 'port'=>11213));
$dis->addServ(array('host'=>'127.0.0.1', 'port'=>11214));
$dis->addServ(array('host'=>'127.0.0.1', 'port'=>11215));

$dis->printServ();
$dis->printPos();

print_r($dis->_lookup('name'));
print_r($dis->_lookup('age'));
print_r($dis->_lookup('sex'));
print_r($dis->_lookup('height'));
print_r($dis->_lookup('weight'));*/
?>