分布式一致性 hash 算法

发布于: 2020 年 07 月 08 日
分布式一致性hash算法

  • 用你熟悉的编程语言实现一致性 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 日 阅读数: 15
用户头像

_MISSYOURLOVE

关注

这个人很懒,还没有介绍过自己~ 2019.04.28 加入

这个懒人,还没有添加过简介~

评论

发布
暂无评论
分布式一致性hash算法