Memcached集群--一致性哈希算法
、一致性哈希算法
Consistent Hashing原理：
首先求出memcached服务器（节点）的哈希值，并将其配置到0~2^32的圆上
然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上，如果超过2^32仍然找不到服务器，就会保存到第一台memcached服务器上。
<?php
//一致性HASH的实现
interface hash{
public function _hash($str);
}
interface distribution{
public function lookup($key);
}
class Moder implements hash,distribution{
protected $_nodes=array();
protected $_cnt=0;
public function _hash($str){
return sprintf('%u',crc32($str));//将字符串转换成32位无符号整数
}
public function addNode($node){
if(in_array($node,$this->_nodes)){
return true;
}
$this->_nodes[]=$node;
$this->_cnt+=1;
return true;
}
public function delNode($node){
if(in_array($node,$this->_nodes)){
return true;
}
$key=array_search($node,$this->_nodes);
unset($this->_nodes[$key]);
$this->_cnt -= 1;//节点减1
return true;
}
public function lookup($key){
$key=$this->_hash($key)%$this->_cnt;
return $this->_nodes[$key];
}
}
class Consistent implements hash,distribution{
protected $_nodes=array();
protected $_position=array();
protected $_mul=64;
public function _hash($str){
return sprintf('%u',crc32($str));//将字符串转换成32位无符号整数
}
//核心功能
public function lookup($key){
$point=$this->_hash($key);
$node=current($this->_position);//先取圆环上最小的节点做结果
foreach($this->_position as $k=>$v){
if($point <= $k){
$node = $v;
break;
}
}
return $node;
}
public function addNode($node){
for($i=0;$i<$this->_mul;$i++){
$this->_position[$this->_hash($node.'-'.$i)]=$node;
}
//$this->_nodes[$this->_hash($node)]=$node;//如array(13亿=>'a');
$this->_sortPos();
}
//循环所有虚节点的位置，谁的值==指定的真实节点，就把他删掉
public function delNode($node){
foreach($this->_position as $k=>$v){
if($v==$node){
unset($this->_position[$key]);
}
}
}
public function _sortPos(){
ksort($this->_position,SORT_REGULAR);
}
//调试用的函数
/* public function printNodes(){
print_r($this->_nodes);
} */
public function printPos(){
echo '<pre>';
print_r($this->_position);
echo '</pre>';
}
}
$con=new Moder();
$con->addNode('a');
$con->addNode('b');
$con->addNode('c');
/*
echo '所有服务器如下:<br/>';
$con->printPos();
*/
echo '当前的键计算的hash落点是'.$con->_hash('title').'<br/>';
echo $con->lookup('title');
?>
版权声明：本文为博主原创文章，未经博主允许不得转载。
页:
[1]