作业

发布于: 2020 年 07 月 07 日
  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

<?php
class ConsistencyHash
{
public $real_nodes = [
'node1' => '127.0.0.1:6379',
'node2' => '127.0.0.1:6380',
'node3' => '127.0.0.1:6381',
'node4' => '127.0.0.1:6382',
'node5' => '127.0.0.1:6383',
'node6' => '127.0.0.1:6384',
'node7' => '127.0.0.1:6385',
'node8' => '127.0.0.1:6386',
'node9' => '127.0.0.1:6387',
'node10' => '127.0.0.1:6388',
];
public $nodes_key_num = [
'node1' => 0,
'node2' => 0,
'node3' => 0,
'node4' => 0,
'node5' => 0,
'node6' => 0,
'node7' => 0,
'node8' => 0,
'node9' => 0,
'node10' => 0
];
public $virtual_nodes = [];
public $virtual_num = 100;
public function hash($node)
{
return sprintf('%u', crc32($node));
}
public function createNodes()
{
foreach ($this->real_nodes as $key => $node) {
for ($i = 1; $i <= $this->virtual_num; $i++) {
$v_k = 'virtual_' . $key . '_' . $i;
$pos = $this->hash($v_k);
$this->virtual_nodes[$pos] = $key;
}
}
ksort($this->virtual_nodes);
return $this;
}
public function getNode($key)
{
$pos = $this->hash($key);
$node = '';
foreach ($this->virtual_nodes as $key => $val) {
if ($pos <= $key) {
$node = $val;
break;
}
}
return $node;
}
public function setCache()
{
for ($i = 1; $i <= 1000000; $i++) {
$key = 'test_' . $i;
$node = $this->getNode($key);
$node and $this->nodes_key_num[$node]++;
}
return $this;
}
public function getStd()
{
$len = count($this->nodes_key_num);
$sum = array_sum($this->nodes_key_num);
$avg = $sum / $len;
$arr = array_values($this->nodes_key_num);
$std = 0;
for ($i = 0; $i < $len; $i++) {
$std += ($arr[$i] - $avg) * ($arr[$i] - $avg);
}
return sqrt($std / $len);
}
}
$std = (new ConsistencyHash())->createNodes()->setCache()->getStd();
echo '标准差为:'.$std;

执行结果:

虚拟节点为100时,标准差为:20487.105448062

虚拟节点为150时,标准差为:17217.024847807

虚拟节点为180时,标准差为:18964.40962461

虚拟节点为200时,标准差为:23095.739911075

虚拟节点为230时,标准差为:22782.274918015

虚拟节点为300时,标准差为:23168.954922698

用户头像

chenzt

关注

还未添加个人签名 2018.05.15 加入

还未添加个人简介

评论

发布
暂无评论
作业