第 5 周 技术选型:技术选型能力反映了架构师的综合水平(一)

发布于: 2020 年 07 月 08 日

作业一:

  • 用你熟悉的编程语言实现一致性 hash 算法。

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

<?php
class ConsistentHashing
{
protected $nodes = [];
protected $positions = [];
protected $indexes = [];
protected $len = 0;
protected $virtualNum = 1024;
public function hashCode($str)
{
$hash = 5381;
$md5 = md5($str);
$seed = 5;
$len = 32;
for ($i = 0; $i < $len; $i++) {
$hash = ($hash << $seed) + $hash + ord($md5{$i});
}
return $hash & 0x7FFFFFFF;
}
public function lookup($key)
{
$code = $this->hashCode($key);
$low = 0;
$height = $this->len -1;
$index = null;
$min = 0;
while ($low <= $height) {
$mid = floor(($low + $height) / 2);
if ($this->indexes[$mid] === $code) {
$index = $mid;
break;
} elseif ($this->indexes[$mid] < $code ) {
$low = $mid + 1;
} elseif ($this->indexes[$mid] > $code ) {
$min = $mid;
$height = $mid -1;
}
}
if ($index === null) {
$index = $min;
}
$position = $this->indexes[$index];
return $this->positions[$position];
}
public function addNode($node)
{
if (isset($this->nodes[$node])) {
return;
}
for ($i = 0; $i < $this->virtualNum; $i++) {
$position = $this->hashCode($node . '-' . $i);
$this->positions[$position] = $node;
$this->nodes[$node][] = $position;
}
$this->sortPositions();
}
public function delNode($node)
{
if (!isset($this->nodes[$node])) {
return;
}
foreach ($this->nodes[$node] as $position) {
unset($this->positions[$position]);
}
unset($this->nodes[$node]);
}
public function sortPositions()
{
ksort($this->positions, SORT_REGULAR);
$this->indexes = array_keys($this->positions);
$this->len = count($this->indexes);
}
}
$ch = new ConsistentHashing();
for ($i = 1; $i <= 10; $i++) {
$ch->addNode($i);
}
$data = [];
for ($i = 1; $i <= 1000000; $i++) {
$node = $ch->lookup($i);
if (!isset($data[$node])) {
$data[$node] = 0;
}
$data[$node]++;
}
print_r($data);
$avg = 100000;
$total = 0;
foreach ($data as $v) {
$total += ($v - $avg) ** 2;
}
echo sqrt($total / 10);

结果:

Array
(
[9] => 98147
[10] => 99861
[2] => 99196
[7] => 100465
[6] => 98903
[4] => 103516
[3] => 102046
[5] => 95635
[8] => 103289
[1] => 98942
)
2303.4205434527%

用户头像

陆不得

关注

还未添加个人签名 2017.12.14 加入

还未添加个人简介

评论

发布
暂无评论
第5周 技术选型:技术选型能力反映了架构师的综合水平(一)