您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记
memcached-一致性哈希分布式算法原理与实现
发布时间：2017-11-22 17:42:39编辑：雪饮阅读（）
相对于之前讨论的取模分布式算法来说，一致性哈希分布式算法的原理其对memcached的命中率则损失的更小，而且是服务器越多，损失越小。而取模分布式算法则是服务器越多，损失越大。
算法原理：
如图：
图中红、绿、蓝分别表示多个不同的服务器，每个服务器被分为不同的区域，每个区域的弦与圆的交点做为节点，该节点称为虚拟节点。这里意即将每个服务器上分布这各个虚拟节点。在初始化这3个服务器的时候同时初始化了各个节点。当一个key来存储的时候则计算出该key的int值，并默认分配在3个服务器中最小的那个节点所属服务器。然后通过循环依次判断该key真正应该是属于哪个服务器来负责存储的。
即便该key的int值再所有节点中都没有，则默认在最小节点所属服务器中存储该key。
取出key与存储key则是同理。
算法实现：
<?php
interface hash{
public function _hash($str);
}
interface distribution{
public function lookup($key);
}
class Consistent implements hash,distribution{
protected $_nodes=array();
protected $_postion=array();
protected $_mul=64;
public function _hash($str){
//把字符串转成32位无符号整数
return sprintf('%u',crc32($str));
}
//核心功能
public function lookup($key){
$point=$this->_hash($key);
//先取圆环上最小的一个节点，当成结果
$node=current($this->_postion);
foreach($this->_postion as $k=>$v){
if($point <= $k){
$node=$v;
break;
}
}
return $node;
}
public function addNode($node){
for($i=0;$i<$this->_mul;$i++){
$this->_postion[$this->_hash($node.'_'.$i)]=$node;
}
$this->_sortPos();
}
//循环所有的虚拟节点，谁的值==指定的真实节点，就把他删掉
public function delNode($node){
foreach($this->_postion as $k=>$v){
if($v==$node){
unset($this->_postion[$k]);
}
}
}
protected function _sortPos(){
ksort($this->_postion,SORT_REGULAR);
}
//调试用的函数
public function printPos(){
print_r($this->_postion);
}
}
$con=new Consistent();
$con->addNode('a');
$con->addNode('b');
$con->addNode('c');
echo '所有的服务器如下:<br/>';
$con->printPos();
$str='title';
echo "当前的键计算的hash落点是,".$con->_hash($str)."<br/>";
echo "应该落在".$con->lookup($str)."号服务器";
?>
这里需要注意的是crc32的算法结果问题。
crc32返回的结果在32位机上会产生溢出，所以结果可能为负数。而在64位机上不会溢出，所以总是正值。
CRC算法是按字长位数bit进行计算的。
crc32函数会按照php中的两个常量参考计算 PHP_INT_SIZE，PHP_INT_MAX
关键字词：memcached,一致性,哈希,分布式,算法
下一篇：memcached-附件