<?php/***一致性hahs实现类**/classFlexiHash{/***varint*虚拟节点*/private$_replicas=200;/***使用hash方法*/private$_hasher=null;/***真实节点计数器**/private$_targetCount=0;/***位置对应节点，用户lookup中根据位置确定要访问的节点*/private$_positionToTarget=array();/***节点对应位置，用于删除节点*/private$_targetToPositions=array();/***是否已排序*/private$_positionToTargetSorted=false;/***@$hasherhash方法*@$replicas虚拟节点的个数**确定要使用的hash方法和虚拟的节点数，虚拟节点越多，分布越均匀，但程序的分布式运算越慢*/publicfunction__construct(FlexiHash_Hasher$hasher=null,$replicas=null){//hash方法$this->_hasher=$hasher?$hasher:newFlexiHash_Crc32Hasher();//虚拟节点的个数if(!empty($replicas)){$this->_replicas=$replicas;}}/***增加节点，根据虚拟节点数，把节点分布到更多的虚拟位置上*/publicfunctionaddTarget($target){if(isset($this->_targetToPositions[$target])){thrownewFlexiHash_Exception("Target$targetalreadyexists.");}$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;}/***添加多个节点**/publicfunctionaddTargets($targets){foreach($targetsas$target){$this->addTarget($target);}return$this;}/***移除某个节点**/publicfunctionremoveTarget($target){if(!isset($this->_targetToPositions[$target])){thrownewFlexiHash_Exception("target$targetdoesnotexist\n");}foreach($this->_targetToPositions[$target]as$position){unset($this->_positionToTarget[$position]);}unset($this->_targetToPositions[$target]);$this->_targetCount--;return$this;}/***获取所有节点**/publicfunctiongetAllTargets(){returnarray_keys($this->_targetToPositions);}/***根据key查找hash到的真实节点**/publicfunctionlookup($resource){$targets=$this->lookupList($resource,1);if(empty($targets)){thrownewFlexiHash_Exception("notargetsexist");}return$targets[0];}/***查找资源存在的节点**描述:根据要求的数量，返回与$resource哈希后数值相等或比其大并且是最小的数值对应的节点，若不存在或数量不够，则从虚拟节点排序后的前一个或多个*/publicfunctionlookupList($resource,$requestedCount){if(!$requestedCount){thrownewFlexiHash_Exception('Invalidcountrequested');}if(empty($this->_positionToTarget)){returnarray();}//直接节点只有一个的时候if($this->_targetCount==1){returnarray_unique(array_values($this->_positionToTarget));}//获取当前key进行hash后的值$resourcePosition=$this->_hasher->hash($resource);$results=array();$collect=false;$this->_sortPositionTargets();//查找与$resourcePosition相等或比其大并且是最小的数foreach($this->_positionToTargetas$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->_positionToTargetas$key=>$value){if(!in_array($value,$results)){$results[]=$value;}if(count($results)==$requestedCount||count($results)==$this->_targetCount){return$results;}}return$results;}/***根据虚拟节点进行排序*/privatefunction_sortPositionTargets(){if(!$this->_positionToTargetSorted){ksort($this->_positionToTarget,SORT_REGULAR);$this->_positionToTargetSorted=true;}}}//endclass/***hash方式*/interfaceFlexiHash_Hasher{publicfunctionhash($string);}classFlexiHash_Crc32HasherimplementsFlexiHash_Hasher{publicfunctionhash($string){returnsprintf("%u",crc32($string));}}classFlexiHash_Md5HasherimplementsFlexiHash_Hasher{publicfunctionhash($string){returnsubstr(md5($string),0,8);}}classFlexiHash_ExceptionextendsException{}$runData['BEGIN_TIME']=microtime(true);$key="lihuibin";for($i=0;$i<10;$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:11218");$flexiHashObj=newFlexiHash(newFlexiHash_Crc32Hasher(),1);$result=$flexiHashObj->addTargets($targetsArray);$key=$key."$i";$targets=$flexiHashObj->lookup($key);var_dump($targets);#$key=md5(mt_rand());#$targets=$flexiHashObj->lookup($key);#var_dump($targets);}echo"一致性hash:";var_dump(number_format(microtime(true)-$runData['BEGIN_TIME'],6));exit;$runData['BEGIN_TIME']=microtime(true);$m=newMemcache;$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));?>