_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;$iaddTargets($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;$iset($key, time(), 0, 10); } echo "单台机器:"; var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6)); ?>
$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;$iset($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;$iset($key, time(), 0, 10); } echo "单台机器:"; var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));