分布式一致性 hash 算法
发布于: 2020 年 07 月 08 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
代码
<?php/** * Created by PhpStorm. * User: 消逝文字 * Date: 2020/7/8 * Time: 23:07 */class HomeWork{ private $server; private $node; public function hash($str) { return sprintf('%u', crc32($str)); } public function addServer($server) { if (!isset($this->server[$server])) { $this->addNode($server); } } public function addNode($server) { for ($i = 0; $i < 200; $i++) { $key_node = $this->hash($server.$i); $this->server[$server][] = $key_node; $this->node[$key_node] = $server; } ksort($this->node, SORT_NUMERIC); } public function dropServer($server) { foreach ($this->server[$server] as $value) { unset($this->node[$value]); } unset($this->server[$server]); } public function getServer($str) { $key_str = $this->hash($str); $server = current($this->node); foreach ($this->node as $k => $v) { if ($k >= $key_str) { $server = $v; break; } } reset($this->node); return $server; }}$server = new HomeWork();$server->addNode('192.168.1.1:8080');$server->addNode('192.168.1.2:8080');$server->addNode('192.168.1.3:8080');$server->addNode('192.168.1.4:8080');$server->addNode('192.168.1.5:8080');$server->addNode('192.168.1.6:8080');$server->addNode('192.168.1.7:8080');$server->addNode('192.168.1.8:8080');$server->addNode('192.168.1.9:8080');$server->addNode('192.168.1.10:8080');// 补充/** * Created by phpStorm * User: Kevin Xiang * Date: 2020/7/9 * Time: 11:09 AM *//** * 用你熟悉的编程语言实现一致性 hash 算法。 * 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下, * 计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。 * Class ConsistentHashing */class ConsistentHashing{ private $ring = []; // Hash 环 private $node = []; // 服务器节点数组 private $virtualNodeNums; // 虚拟节点数量 public function __construct($node, $virtualNodeNums) { $this->node = $node; $this->virtualNodeNums = $virtualNodeNums; $this->addServer($this->node); } public function hash(string $str) { $hash = 0; $s = md5($str); $seed = 5; $len = 32; for ($i = 0; $i < $len; $i++) { $hash = ($hash << $seed) + $hash + ord($s{$i}); } return $hash & 0x7FFFFFFF; } protected function addServer(array $server) { foreach ($server as $v) { $this->addNode($v); } } protected function addNode(string $node) { for ($i = 0; $i < $this->virtualNodeNums; $i++) { $hash_node = $this->hash($node."#".$i); $this->ring[$node][] = $hash_node; $this->node[$hash_node] = $node; } ksort($this->ring, SORT_NUMERIC); } public function removeServer(string $node) { if (isset($this->ring[$node])) { foreach ($this->ring[$node] as $v) unset($this->node[$v]); unset($this->ring[$node]); } } public function findServer(string $key) { $hash_key = $this->hash($key); $server = current($this->node); foreach ($this->node as $k => $v) { if ($k >= $hash_key) { $server = $v; break; } } reset($this->node); return $server; }}$node = [ '192.168.1.10', '192.168.2.10', '192.168.3.10', '192.168.4.10', '192.168.5.10', '192.168.6.10', '192.168.7.10', '192.168.8.10', '192.168.9.10', '192.168.10.10',];$cHash = new ConsistentHashing($node, 150);$cHash->removeServer('192.168.1.10');for ($i = 0; $i <= 1000000; $i++) { $key = "missyourlove#".$i; echo "key:".$key."落在了".$cHash->findServer($key)."服务器上".PHP_EOL;}
这道题自己还有点没弄明白,先提交。然后自己琢磨下,到时候在重新实现一遍
代码参考:https://blog.csdn.net/weixin_43932088/article/details/85983537
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 62
版权声明: 本文为 InfoQ 作者【_MISSYOURLOVE】的原创文章。
原文链接:【http://xie.infoq.cn/article/ea7c38313426d48576bcb45d2】。未经作者许可,禁止转载。
这个人很懒,还没有介绍过自己~ 2019.04.28 加入
这个懒人,还没有添加过简介~
评论