PHPhash一致性

1. [文件] 一致性hash.php ~ 6KB     下载(0)    

<?php
/**
 * 一致性hahs实现类
 * 
 */
class FlexiHash{
	/**
	 * var int
	 * 虚拟节点
	 */
	private $_replicas = 200;
	
	/**
	 * 使用hash方法
	 */
	private $_hasher = null;
	
	/**
	 * 真实节点计数器
	 * 
	 */
	private $_tagertCount = 0;
	
	/**
	 * 位置对应节点，用户lookup中根据位置确定要访问的节点
	 */
	private $_positionToTarget = array();
	
	/**
	 * 节点对应位置，用于删除节点
	 */
	private $_targetToPositions = array();
	
	/**
	 * 是否已排序
	 */
	private $_positionToTargetSorted = false;
	
	/**
	 * @ $hasher hash方法
	 * @ $replicas 虚拟节点的个数
	 * 
	 * 确定要使用的hash方法和虚拟的节点数，虚拟节点越多，分布越均匀，但程序的分布式运算越慢
	 */
	public function __construct(FlexiHash_Hasher $hasher=null, $replicas = null){
		// hash方法
		$this->_hasher = $hasher?$hasher: new FlexiHash_Crc32Hasher();
		// 虚拟节点的个数
		if (!empty($replicas)){
			$this->_replicas = $replicas;
		}
	}
	
	/**
	 * 增加节点，根据虚拟节点数，把节点分布到更多的虚拟位置上
	 */
	public function addTarget($target){
		
		if (isset($this->_targetToPositions[$target])) {
			throw new FlexiHash_Exception("Target $target already exists.");
		}
		
		$this->_targetToPositions[$target] = array();
		
		for ($i = 0; $i < $this->_replicas; $i++) {
			
			// 根据规定的方法hash
			$position = $this->_hasher->hash($target.$i);
			
			// 虚拟节点对应的真实的节点
			$this->_positionToTarget[$position] = $target;
			
			// 真实节点包含的虚拟节点
			$this->_targetToPositions[$target][] = $position;
		}
		
		
		$this->_positionToTargetSorted = false;
		
		// 真实节点个数
		$this->_targetCount++;
		
		return $this;
	}
	
	/**
	 * 添加多个节点
	 * 
	 */
	public function addTargets($targets){
		foreach ($targets as $target){
			$this->addTarget($target);
		}
		return $this;
	}
	
	/**
	 * 移除某个节点
	 * 
	 */
	public function removeTarget($target){
		if (!isset($this->_targetToPositions[$target])){
			throw new FlexiHash_Exception("target $target does not exist\n");
		}
		
		foreach($this->_targetToPositions[$target] as $position){
			unset($this->_positionToTarget[$position]);
		}
		
		unset($this->_targetToPositions[$target]);
		
		$this->_targetCount--;
		
		return $this;
	}
	
	/**
	 * 获取所有节点
	 * 
	 */
	public function getAllTargets(){
		return array_keys($this->_targetToPositions);
	}
	
	
	/**
	 * 根据key查找hash到的真实节点
	 * 
	 */
	public function lookup($resource){
		$targets = $this->lookupList($resource, 1);
		
		if (empty($targets)){
			throw new FlexiHash_Exception("no targets exist");
		}
		
		return $targets[0];
	}
	
	/**
	 * 查找资源存在的节点
	 * 
	 * 描述:根据要求的数量，返回与$resource哈希后数值相等或比其大并且是最小的数值对应的节点，若不存在或数量不够，则从虚拟节点排序后的前一个或多个
	 */
	public function lookupList($resource, $requestedCount){
		
		if (!$requestedCount) {
			throw new FlexiHash_Exception('Invalid count requested');
		}
		
		if (empty($this->_positionToTarget)) {
			return array();
		}
		
		// 直接节点只有一个的时候
		if ($this->_targetCount == 1 ){
			return array_unique(array_values($this->_positionToTarget));
		}
		
		// 获取当前key进行hash后的值
		$resourcePosition = $this->_hasher->hash($resource);
	
		$results = array();
		
		$collect = false;
		
		$this->_sortPositionTargets();
		
		// 查找与$resourcePosition 相等或比其大并且是最小的数
		foreach($this->_positionToTarget as $key => $value){
			
			if (!$collect && $key > $resourcePosition){
				
				$collect = true;
			}
			
			if ($collect && !in_array($value, $results)){
				$results[] = $value;
			}
			
			// 找到$requestedCount 或个数与真实节点数量相同
			if (count($results) == $requestedCount || count($results) == $this->_targetCount){
				return $results;
			}
		}
		// 如数量不够或者未查到，则从第一个开始，将$results中不存在前$requestedCount-count($results)，设置为需要的节点
		foreach ($this->_positionToTarget as $key => $value){
			if (!in_array($value, $results)){
				$results[] = $value;
			}
			
			if (count($results) == $requestedCount || count($results) == $this->_targetCount){
			
				return $results;
			}
		}
		
		return $results;
		
	}
	
	/**
	 * 根据虚拟节点进行排序
	 */
	private function _sortPositionTargets(){
		if (!$this->_positionToTargetSorted){
			ksort($this->_positionToTarget, SORT_REGULAR);
			
			$this->_positionToTargetSorted = true;
		}
	}
	
}// end class

/**
 * hash方式
 */
interface FlexiHash_Hasher{
	public function hash($string);
}

class FlexiHash_Crc32Hasher implements FlexiHash_Hasher{
	public function hash($string){
		return sprintf("%u",crc32($string));
	}
}


class FlexiHash_Md5Hasher implements FlexiHash_Hasher{
	public function hash($string){
		return substr(md5($string), 0, 8);
	}
}

class FlexiHash_Exception extends Exception{
}

$runData['BEGIN_TIME'] = microtime(true);

for($i=0;$i<10000;$i++) {


	 $targetsArray = array(
	 	"127.0.0.1:11211",
		"127.0.0.1:11212",
		"127.0.0.1:11213",
		"127.0.0.1:11214",
		"127.0.0.1:11215"
	 );
	 $flexiHashObj = new FlexiHash(new FlexiHash_Crc32Hasher(),1);
	 
	 $result = $flexiHashObj->addTargets($targetsArray);
	  $key = md5(mt_rand());
	 $targets = $flexiHashObj->lookup($key);
//	var_dump($targets);
	 
	 

}
	echo "一致性hash:";
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));




$runData['BEGIN_TIME'] = microtime(true); 
$m= new Memcache;
$m->connect('127.0.0.1', 11211); 
for($i=0;$i<10000;$i++) {
        $key = md5(mt_rand());
        $b = $m->set($key, time(), 0, 10);
}
echo "单台机器:";
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));
?>

2. [代码]虚拟节点的hash一致性    

<?php   
class memcacheHashMap{  
    private $_node = array();  
      
    private $_nodeData = array();  
      
    private $_keyNode = 0;  
      
    private $_memcache = null;  
      
      
    // 每个物理服务器生成虚拟节点的个数  
    private $_virtualNodeNum = 200;  
      
    private function __construct(){  
        // 配置文件  
        $config = array(  
            "127.0.0.1:11211",  
            "127.0.0.1:11212",  
            "127.0.0.1:11213",  
            "127.0.0.1:11214",  
            "127.0.0.1:11215"  
        );  
          
        if (!$config){  
            throw new Exception("cache config null");  
        }  
          
        // 设置虚拟节点  
        foreach($config as $key=>$value){  
              
            for ($i = 0; $i < $this->_virtualNodeNum; $i++){  
                $this->_node[sprintf("%u", crc32($value."#".$i))] = $value."#".$i;  
            }  
        }  
          
        // 排序  
        ksort($this->_node);  
          
//      print_r($this->_node);  
    }  
      
    // 单例模式  
    static public function getInstance(){  
        static $memcacheObj = null;  
        if (!is_object($memcacheObj)) {  
            $memcacheObj = new self();  
        }  
        return $memcacheObj;  
    }  
      
    private function _connectMemcache($key){  
        $this->_nodeData = array_keys($this->_node);  
//      echo "all node:\n";  
//      print_r($this->_nodeData);  
        $this->_keyNode = sprintf("%u", crc32($key));  
//      $this->_keyNode = 1803717635;  
//      var_dump($this->_keyNode);  
          
        // 获取key值对应的最近的节点  
        $nodeKey = $this->_findServerNode(0, count($this->_nodeData)-1);  
//      var_dump($nodeKey);  
//      echo "$this->_keyNode :search node:$nodeKey  IP:{$this->_node[$nodeKey]}\n";  
          
        //获取对应的真实ip  
        list($config, $num) = explode("#", $this->_node[$nodeKey]);  
          
        if (empty($config)){  
            throw new Exception("serach ip config error");  
        }  
          
        if (!isset($this->_memcache[$config])){  
            $this->_memcache[$config] = new Memcache;  
            list($host, $port) = explode(":", $config);  
            $this->_memcache[$config]->connect($host, $port);  
        }  
          
        return $this->_memcache[$config];  
          
          
          
    }  
    /** 
     * 采用二分法从虚拟memcache节点中查找最近的节点 
     * @param int $low 开始位置 
     * @param int $high 结束位置 
     *  
     */  
    private function _findServerNode($low, $high){  
          
        // 开始下标小于结束下标  
        if ($low < $high){  
              
            $avg = intval(($low+$high)/2);  
              
            if ($this->_nodeData[$avg] == $this->_keyNode){  
                return $this->_nodeData[$avg];  
            }elseif ($this->_keyNode < $this->_nodeData[$avg]){  
                return $this->_findServerNode($low, $avg-1);  
            }else{  
                return $this->_findServerNode($avg+1, $high);  
            }  
        }else if(($low == $high)){  
            // 大于平均值  
            if ($low ==0 || $low == count($this->_nodeData)-1){  
                return $this->_nodeData[$low];  
            }  
//          var_dump($low);  
            if ($this->_nodeData[$low] < $this->_keyNode){  
                  
                if (abs($this->_nodeData[$low] - $this->_keyNode) < abs($this->_nodeData[$low+1]-$this->_keyNode)){  
                    return $this->_nodeData[$low];  
                }else{  
                    return $this->_nodeData[$low+1];  
                }  
          
            }else {  
                if (abs($this->_nodeData[$low] - $this->_keyNode) < abs($this->_nodeData[$low-1]-$this->_keyNode)){  
                    return $this->_nodeData[$low];  
                }else{  
                    return $this->_nodeData[$low-1];  
                }  
            }  
        }else{  
            if ( ($low == 0)&&($high < 0) ){  
                return $this->_nodeData[$low];  
            }  
          
            if (abs($this->_nodeData[$low] - $this->_keyNode) < abs($this->_nodeData[$high]-$this->_keyNode)){  
                return $this->_nodeData[$low];  
            }else{  
                return $this->_nodeData[$high];  
            }  
        }  
    }  
      
    public function set($key, $value, $expire=0){  
//  var_dump($key);  
        return $this->_connectMemcache($key)->set($key, json_encode($value), 0, $expire);  
    }  
      
      
    public function add($key, $vakue, $expire=0){  
        return $this->_connectMemcache($key)->add($key, json_encode($value), 0, $expire);  
    }  
      
    public function get($key){  
        return $this->_connectMemcache($key)->get($key, true);  
    }  
      
    public function delete($key){  
        return $this->_connectMemcache($key)->delete($key);  
    }  
      
          
      
}  
  
  
$runData['BEGIN_TIME'] = microtime(true);  
//测试一万次set加get  
for($i=0;$i<10000;$i++) {  
        $key = md5(mt_rand());  
//        var_dump($key);  
        $b = memcacheHashMap::getInstance()->set($key, time(), 10);  
}  
echo "一致性hash:";  
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));  
$runData['BEGIN_TIME'] = microtime(true);   
$m= new Memcache;  
$m->connect('127.0.0.1', 11211);   
for($i=0;$i<10000;$i++) {  
        $key = md5(mt_rand());  
        $b = $m->set($key, time(), 0, 10);  
}  
echo "单台机器:";  
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));