PHP一致性hash的实现

本文是剽窃了Flexihash的实现，不是本人所为，简化了实现的细节
http://code.google.com/p/flexihash/

一致性hash大多用于缓存集群中，为了使在缓存中由于一台或多台服务器宕机，导致后端数据库压力过大而崩溃，他对添加和减少缓存服务器迁移的数据量最小化，相对于取模来说

对于一致性hash的原理和介绍，网上有很多，我这里就不转帖了

    <?php
    /**
    *        Consisten Hashing
    *
    */


    class ConsistenHash {

            private $_targetNum = 0;

            //值越大，分布在环上的数据就越均匀
            private $_replicas = 64;

            private $_targetToPositions = array();

            private $_positionsToTargets = array();

            public function __construct($replicas = null){
                    if(!empty($replicas)) $this->_replicas = $replicas;
            }

            //添加单个目标
            public function addTarget($target){
                    //如果target为空则返回false
                    if(empty($target)) return false;

                    //如果target存在则返回
                    if(array_key_exists($target,$this->_targetToPositions)) return $this;

                    for($i=0;$i<$this->_replicas;$i++){
                            $position = $this->hash($target.$i);
                            $this->_positionsToTargets[$position] = $target;
                            $this->_targetToPositions[$target][] = $position;
                    }

                    $this->_targetNum++;
                    //ksort($this->_positionsToTargets,SORT_REGULAR);

            }

            //批量添加目标对象，在分布式缓存中为缓存服务器，如果在分表中，则为表名列表
            public function addTargets($targets){
                    if(is_array($targets)){
                            foreach($targets as $target){
                                    $this->addTarget($target);
                            }
                    }else{
                            $this->addTarget($target);
                    }
                    return $this;
            }

            //获取目标对应的位置对象
            public function getTarget($id){

                    if(empty($id)) return array();

                    if($this->_targetNum == 1)
                            return array_unique(array_values($this->_positionToTarget));

                    $position = $this->hash($id);

                    ksort($this->_positionsToTargets,SORT_REGULAR);

                    foreach($this->_positionsToTargets as $k=>$v){
                            if($k > $position){
                                    return $v;
                            }
                    }
            }

            //获取所有位置与目标对象列表
            public function getAllList($flag = null){
                    if(empty($flag)) {
                            return $this->_targetToPositions;
                    }
                    ksort($this->_positionsToTargets,SORT_REGULAR);
                    return $this->_positionsToTargets;
            }

            //通过crc32计算target和key的值
            public function hash($target){
                    $hash = sprintf("%u",crc32($target));
                    return $hash;
            }
    }
    ?>



以下是测试用的code：

    <?php

    require_once "consisten_hash.class.php";

    $hash = new ConsistenHash(8);

    $hash->addTargets(array('cache-001','cache-002','cache-003','cache-004'));

    print_r($hash->getAllList(true));


    $position = $hash->hash('abc');
    $target = $hash->getTarget('abc');
    echo $position."\n";
    echo $target."\n";
    ?>