MC的分布式算法的实现和一些总结

首先我们知道Memcached是一个分布式的缓存系统，但memcached并不像是mongodb那样，允许配置多个节点，且节点之间是自动分配数据的

也就是说memcached节点之间，是互不相通信的，因此，memcached的分布式，要靠用户去设计算法，把数据分布在多个memcached节点中。

我们来看一下常用的分布式的算法：

1.取模算法：

最容易想到的就是取模算法，即N个节点要从0-》n-1进行编号，key对N取模，余i，则key落在第i台服务器上。

就是将server的hash值与server的总台数进行求余,即hash%N,这种方法的弊端是当增减服务器时,将会有较多的缓存需要被重新分配且会造成缓存分配不均匀的情况(有可能某一台服务器分配的很多,其它的却很少).

但我们来看一下这种算法对缓存命中率的影响：

我们假设有8台服务器，运行中突然down一台，则求余的底数变成7

我们来推算一下产生的后果：

一般地,我们从数学上归纳之:

有N台服务器，变成了N-1台服务器，

每N*(N-1)个数中，只有（n-1）个单元，%n，%（n-1）得到相同的结果

所以 命中率在服务器down的短期内，急遽下降至1/(N-1)

所以 服务器越多，则down机的后果越严重！

我们来讨论下一致性hash的算法：

通俗理解一致性哈希：

把各个服务器节点放在钟表的各个时刻上，我们将Key也映射到钟表的某个时刻上，该key沿钟表顺时针走，碰到第一个比它小的节点后，则这个key就落到这台服务器上。

1 疑问1:时钟上的指针最大才11点,如果我有上百个memcached节点怎么办?2 答: 时钟只是为了便于理解做的比喻,在实际应用中,我们可以在圆环上分布[0,2^32-1]的数字,3 这样,全世界的服务器都可以装下了.4 5 疑问2:我该如何把”节点名”,”键名”转化成整数?6 答: 你可以用现在的函数,如crc32().7 也可以自己去设计转化规则,但注意转化后的碰撞率要低.8 即不同的节点名,转换为相同的整数的概率要低.

好了，那我们再考虑一下当某个节点Down了之后，后产生什么样的影响？

当某个节点down后,只影响该节点顺时针之后的1个节点,而其他节点不受影响.因此，Consistent Hashing最大限度地抑制了键的重新分布

我们通过上图看到，6号节点down后，所有的压力都转移到7号节点上，造成了7号节点服务器的压力特别的大，那我们考虑是否能够将6号节点的压力注意到其余的节点上呢？

所以我们引入了虚拟节点的概念：

虚拟节点即----N个真实节点,把每个真实节点映射成M个虚拟节点, 再把M*N个虚拟节点,

散列在圆环上. 各真实节点对应的虚拟节点相互交错分布

这样,某真实节点down后,则把其影响平均分担到其他所有节点上

好了，上面就是一致性hash的理论知识点，接下来我们来考虑一下怎样实现？

下面是用php来实现的代码：

 1 <?php 2  3  4 html' target='_blank'>class Consistent { 5         protected $_nodes = array(); 6  7         //生成一个数值   8         public function _hash($str){ 9                 return sprintf('%u',crc32($str));10         }11 12         public function find($key){13                 $point = $this->_hash($key);14                 $pos  = current($this->_nodes);15 16                 foreach($this->_nodes as $k=>$v){17                         if($point <= $k){18                                 $pos = $v;19                                 break;20                         }21                 }22                 return $pos;23         }24 25         public function addServer($server){26                 for($i=1;$i<=32;$i++){27                         $pos = $this->_hash($server.'-'.$i);28                         $this->_nodes[$pos] = $server;29                 }30 31                 ksort($this->_nodes,SORT_REGULAR);32         }33 34         public function printNodes(){35                 print_r($this->_nodes);36         }37 38 }39 40 $cons = new Consistent();41 42 $cons->addServer('a');43 $cons->addServer('b');44 $cons->addServer('c');45 46 echo $cons->_hash('name').'<br/>';47 echo '应该落在'.$cons->find('name').'<br/>';48 49 $cons->printNodes();50 ?>

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。