memcached分布式-一致性哈希

2019-11-11 05:40:28

字体：大中小

来源：转载

供稿：网友

一致性哈希分布式算法

概述

一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：均衡性：尽可能分布到所有的缓冲中，使得所有的空间得到利用；单调性：新增缓冲时候，能分配到新的缓冲区。分散性：尽量避免不一致情况发生，降低分散性。负载：能最好均匀分布到各个缓冲区。同时清晰路由到某个节点。

分析

当n个memcached服务器中1台down掉了，也就是变成了n-1台。1/（n-1）:将down掉了那一台服务器负载平均分配到其余的服务器上。

场景分析

引入虚拟节点，如3台服务器a，b，ca1,a2.....a64个节点。b1,b2....b64个节点。c1,c2...c64个节点，混合均匀排序；（条件：假设前一个节点挂掉会找相邻的节点进行存储。）keyx在服务器b1，keyy在服务器b2,keyz在服务器节点b64；假设b服务器down掉，则keyx在a服务器，keyy在b服务器，keyz在a服务器（相邻节点）虚拟出虚拟越多的虚拟节点这样就能使得所有的缓存key均匀分布并且当一台挂掉会找相邻的节点；这样概率角度能达到均匀的负载到其他服务器上去。

php实现

需要一个函数把字符串转成整数的函数crc32

简单示例

<?phpclass Consistent { PRotected $nodes = array(); protected $virtual = 64;//表示每台服务器有64个虚拟节点 protected $position = array();//虚拟节点 /** *@function 实现hash，将字符串转成响应整数 */ public function _hash($str) { //把字符串转成32位无符号整数 return sprintf('%u', crc32($str)); } /** *@function 根据key 值来查找到相关的存储节点 * */ public function lookup($key) { //算出key值 $point = $this->_hash($key); //沿着节点进行判断该key值应该存储哪个节点 $node = current($this->nodes); foreach($this->position as $key => $val) { if($point <= $key) { $node = $val; break; } } return $node;//返回node节点所处的服务器； } /** *@function 添加一个服务器需要新增64个虚拟节点 */ public function addNode($node) { //虚拟出64个节点。 for($i = 0; $i < $this->virtual; $i++) { $num = $node .'-'.$i; $this->position[$this->_hash($num)] = $node;//新增64个位置 } $this->nodes[] = $node; //对新增节点进行排序，整个节点进行排序 $this->nodeSort(); } /** *@function 删除一个服务器节点 * */ public function delNode($node) { //循环所有的虚拟节点位置 foreach($this->position as $key => $val) { if($val == $node) { unset($this->position[$key]); } } } /** *@function 排序大小 * */ public function nodeSort() { ksort($this->position, SORT_REGULAR); } /** *@function 获取所有的节点 * */ public function getNodes() { return $this->nodes; } /** *@function 返回所有的虚拟节点 * */ public function getVirtual() { return $this->position; }}$con = new Consistent();$con->addNode('a');//a服务器$con->addNode('b');//b服务器$con->addNode('c');//c服务器print_r($con->getVirtual());$name = 'linjunbin';$tital = 'title4';echo $name.'数字为'.$con->_hash($name).'落在'.$con->lookup($name);echo '<br>';echo $tital.'数字为'.$con->_hash($tital).'落在'.$con->lookup($tital);

未完待续….

上一篇：代码规范重要性

下一篇：字符串问题（四）