跳至
_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));
?>登录后复制
2. [代码]虚拟节点的hash一致性
$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));登录后复制
