架构师训练营第五周 - 作业

用户头像
桔子
关注
发布于: 2020 年 07 月 09 日

作业:

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

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

// 一致性哈希算法
class ConsistentHashing
{
protected $nodes = array();
protected $position = array();
protected $mul = 64; // 每个节点对应64个虚拟节点

/**
* 把字符串转为32位符号整数
*/
public function hash($str)
{
return sprintf('%u', crc32($str));
}

/**
* 核心功能
*/
public function lookup($key)
{
$point = $this->hash($key);

//先取圆环上最小的一个节点,当成结果
$node = current($this->position);

// 循环获取相近的节点
foreach ($this->position as $key => $val) {
if ($point <= $key) {
$node = $val;
break;
}
}

reset($this->position);

return $node;
}

/**
* 添加节点
*/
public function addNode($node)
{
if(isset($this->nodes[$node])) return;

// 添加节点和虚拟节点
for ($i = 0; $i < $this->mul; $i++) {
$pos = $this->hash($node . '-' . $i);
$this->position[$pos] = $node;
$this->nodes[$node][] = $pos;
}

// 重新排序
$this->sortPos();
}

/**
* 删除节点
*/
public function delNode($node)
{
if (!isset($this->nodes[$node])) return;

// 循环删除虚拟节点
foreach ($this->nodes[$node] as $val) {
unset($this->position[$val]);
}

// 删除节点
unset($this->nodes[$node]);
}

/**
* 排序
*/
public function sortPos()
{
ksort($this->position, SORT_REGULAR);
}
}




用户头像

桔子

关注

还未添加个人签名 2018.11.15 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周 - 作业