首页 / 算法 / 一致性Hash算法(分布式算法)
一致性Hash算法(分布式算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了一致性Hash算法(分布式算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含10232字,纯文字阅读大概需要15分钟。
内容图文
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法?
一致性哈希算法的PHP实现
/* * * 一致性哈希实现接口 * Interface ConsistentHash */ interface ConsistentHash { // 将字符串转为hash值 public function cHash($str); //添加一台服务器到服务器列表中publicfunction addServer($server); //从服务器删除一台服务器publicfunction removeServer($server); //在当前的服务器列表中找到合适的服务器存放数据publicfunction lookup($key); }
/* * * 具体一致性哈希实现 * author chenqionghe * Class MyConsistentHash */ class MyConsistentHash implements ConsistentHash { public$serverList = array(); //服务器列列表public$virtualPos = array(); //虚拟节点的位置public$virtualPosNum = 5; //每个节点对应5个虚节点/** * 将字符串转换成32位无符号整数hash值 * @param $str * @return int */publicfunction cHash($str) { $str = md5($str); returnsprintf(‘%u‘, crc32($str)); } /** * 在当前的服务器列表中找到合适的服务器存放数据 * @param $key 键名 * @return mixed 返回服务器IP地址 */publicfunction lookup($key) { $point = $this->cHash($key);//落点的hash值$finalServer = current($this->virtualPos);//先取圆环上最小的一个节点当成结果foreach($this->virtualPos as$pos=>$server) { if($point <= $pos) { $finalServer = $server; break; } } reset($this->virtualPos);//重置圆环的指针为第一个return$finalServer; } /** * 添加一台服务器到服务器列表中 * @param $server 服务器IP地址 * @return bool */publicfunction addServer($server) { if(!isset($this->serverList[$server])) { for($i=0; $i<$this->virtualPosNum; $i++) { $pos = $this->cHash($server . ‘-‘ . $i); $this->virtualPos[$pos] = $server; $this->serverList[$server][] = $pos; } ksort($this->virtualPos,SORT_NUMERIC); } returnTRUE; } /** * 移除一台服务器(循环所有的虚节点,删除值为该服务器地址的虚节点) * @param $key * @return bool */publicfunction removeServer($key) { if(isset($this->serverList[$key])) { //删除对应虚节点foreach($this->serverList[$key] as$pos) { unset($this->virtualPos[$pos]); } //删除对应服务器unset($this->serverList[$key]); } returnTRUE; } }
然后, 我们来测试一下该算法
$hashServer = new MyConsistentHash(); $hashServer->addServer(‘192.168.1.1‘); $hashServer->addServer(‘192.168.1.2‘); $hashServer->addServer(‘192.168.1.3‘); $hashServer->addServer(‘192.168.1.4‘); $hashServer->addServer(‘192.168.1.5‘); $hashServer->addServer(‘192.168.1.6‘); $hashServer->addServer(‘192.168.1.7‘); $hashServer->addServer(‘192.168.1.8‘); $hashServer->addServer(‘192.168.1.9‘); $hashServer->addServer(‘192.168.1.10‘); echo "增加十台服务器192.168.1.1~192.168.1.10<br />"; echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘; echo "移除一台服务器192.168.1.2<br />"; $hashServer->removeServer(‘192.168.1.2‘); echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘; echo "移除一台服务器192.168.1.6<br />"; $hashServer->removeServer(‘192.168.1.6‘); echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘; echo "移除一台服务器192.168.1.8<br />"; $hashServer->removeServer(‘192.168.1.8‘); echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘; echo "移除一台服务器192.168.1.2<br />"; $hashServer->removeServer(‘192.168.1.2‘); echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘; echo "增加一台服务器192.168.1.11<br />"; $hashServer->addServer(‘192.168.1.11‘); echo "保存 key1 到 server :".$hashServer->lookup(‘key1‘) . ‘<br />‘; echo "保存 key2 到 server :".$hashServer->lookup(‘key2‘) . ‘<br />‘; echo "保存 key3 到 server :".$hashServer->lookup(‘key3‘) . ‘<br />‘; echo "保存 key4 到 server :".$hashServer->lookup(‘key4‘) . ‘<br />‘; echo "保存 key5 到 server :".$hashServer->lookup(‘key5‘) . ‘<br />‘; echo "保存 key6 到 server :".$hashServer->lookup(‘key6‘) . ‘<br />‘; echo "保存 key7 到 server :".$hashServer->lookup(‘key7‘) . ‘<br />‘; echo "保存 key8 到 server :".$hashServer->lookup(‘key8‘) . ‘<br />‘; echo "保存 key9 到 server :".$hashServer->lookup(‘key9‘) . ‘<br />‘; echo "保存 key10 到 server :".$hashServer->lookup(‘key10‘) . ‘<br />‘; echo ‘<hr />‘;
运行结果如下
增加十台服务器192.168.1.1~192.168.1.10 保存 key1 到 server :192.168.1.2 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.6 保存 key4 到 server :192.168.1.8 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4 移除一台服务器192.168.1.2 保存 key1 到 server :192.168.1.7 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.6 保存 key4 到 server :192.168.1.8 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4 移除一台服务器192.168.1.6 保存 key1 到 server :192.168.1.7 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.3 保存 key4 到 server :192.168.1.8 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4 移除一台服务器192.168.1.8 保存 key1 到 server :192.168.1.7 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.3 保存 key4 到 server :192.168.1.10 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4 移除一台服务器192.168.1.2 保存 key1 到 server :192.168.1.7 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.3 保存 key4 到 server :192.168.1.10 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4 增加一台服务器192.168.1.11 保存 key1 到 server :192.168.1.7 保存 key2 到 server :192.168.1.1 保存 key3 到 server :192.168.1.11 保存 key4 到 server :192.168.1.10 保存 key5 到 server :192.168.1.9 保存 key6 到 server :192.168.1.10 保存 key7 到 server :192.168.1.7 保存 key8 到 server :192.168.1.4 保存 key9 到 server :192.168.1.7 保存 key10 到 server :192.168.1.4
原文:http://www.cnblogs.com/mycing/p/4776423.html
内容总结
以上是互联网集市为您收集整理的一致性Hash算法(分布式算法)全部内容,希望文章能够帮你解决一致性Hash算法(分布式算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。