架构师训练营第五周作业一致性 hash 算法
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
interface Cache
{
public function get(string $key);
public function set(string $key, string $value);
public function getName();
public function getCount();
}
class CacheTest implements Cache
{
private $name;
private $data = [];
public function __construct($name)
{
$this->name = $name;
}
public function get(string $key)
{
return $this->data[$key] ?? null;
}
public function set(string $key, string $value)
{
$this->data[$key] = $value;
}
public function getName()
{
return $this->name;
}
/**
* 获取key数量
* @return int
*/
public function getCount()
{
return count($this->data);
}
}
/**
* 一致性哈希算法
* User: lbbniu <lbbniu@gmail.com>
* Date: 2020/7/8
* Time: 15:41
*/
class ConsistentHashing
{
/**
* 是否排序
* @var bool
*/
private $is_sorted = false;
/**
* 节点对应的虚拟节点
* @var array
*/
private $nodes = [];
/**
* 哈希环
* @var array
*/
private $position = [];
private $keys = [];
/**
* 节点
* @var array
*/
private $map_nodes = [];
/**
* 虚拟节点数
* @var int
*/
private $mul;
public function __construct($mul)
{
$this->mul = $mul;
}
/**
* 增加节点
* @param Cache $cache
* @return $this
*/
public function addNode(Cache $cache)
{
$name = $cache->getName();
$this->map_nodes[$name] = $cache;
for ($i = 0; $i < $this->mul; $i++) {
$key = self::hash("{$name}#{$i}");
$this->nodes[$name][] = $key;
$this->position[$key] = $name;
}
$this->is_sorted = false;
return $this;
}
/**
* 移除节点
* @param Cache $cache
*/
public function removeNode(Cache $cache)
{
$name = $cache->getName();
if (!$this->map_nodes[$name]) {
return;
}
unset($this->map_nodes[$name]);
foreach ($this->nodes[$name] as $key) {
unset($this->position[$key]);
}
unset($this->nodes[$name]);
$this->is_sorted = false;
}
/**
* 获取key对象的节点名称
* @param $key
* @return string
*/
public function getNodeName(string $key): string
{
//排序
if (!$this->is_sorted) {
$this->keys = array_keys($this->position);
sort($this->keys, SORT_NUMERIC);
$this->is_sorted = true;
}
$hash = self::hash($key);
$find_key = null;
//二分查找第一个大于等于key的节点
$low = 0;
$high = count($this->keys) - 1;
while ($low <= $high) {
$mid = $low + (($high - $low) >> 1);
if ($this->keys[$mid] >= $hash) {
if ($mid == 0 || $this->keys[$mid - 1] < $hash) {
$key = $this->keys[$mid];
return $this->position[$key];
} else {
$high = $mid - 1;
}
} else {
$low = $mid + 1;
}
}
return $this->position[$this->keys[0]];
}
public function getNode(string $key)
{
$name = $this->getNodeName($key);
return $this->map_nodes[$name];
}
/**
* 设置缓存
* @param string $key
* @param string $value
* @return bool
*/
public function set(string $key, string $value)
{
$cache = $this->getNode($key);
return $cache->set($key, $value);
}
/**
* 获取缓存内容
* @param string $key
* @return string
*/
public function get(string $key): string
{
$cache = $this->getNode($key);
return $cache->get($key);
}
/**
* 计算哈希值
* @param $key
* @return int
*/
private static function hash1($key): int
{
return (int)sprintf('%u', crc32($key));
}
protected static function hash2($str)
{
// hash(i) = hash(i-1) * 33 + str[i]
$hash = 0;
$s = md5($str);
$seed = 5;
$len = 32;
for ($i = 0; $i < $len; $i++) {
// (hash << 5) + hash 相当于 hash * 33
//$hash = sprintf("%u", $hash * 33) + ord($s{$i});
// $hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF;
$hash = ($hash << $seed) + $hash + ord($s{$i});
}
return $hash & 0x7FFFFFFF;
}
public static function hash(string $value)
{
// var_dump(hexdec(hash('adler32', 'lbbniu', false)));
// var_dump(hexdec(hash('fnv132', 'lbbniu', false)));
// var_dump(hexdec(hash('fnv1a32', 'lbbniu', false)));
// var_dump(hexdec(hash('crc32', 'lbbniu', false)));
return hexdec(hash('fnv132', $value, false));
// return hexdec(hash('fnv1a32', $value, false));
}
/**
* 获取一组数据的标准差
* @param string $list // 所要计算标准差的数据
* @return float [object] [返回标准差]
*/
public function getVariance($list)
{
$avg = array_sum($list) / count($list);
$total_var = 0;
foreach ($list as $lv) {
$total_var += pow(($lv - $avg), 2);
}
return intval(sqrt($total_var / (count($list) - 1)));
}
}
测试代码
<?php
/**
* Created by PhpStorm.
* User: lbbniu <lbbniu@gmail.com>
* Date: 2020/7/8
* Time: 16:36
*/
ini_set('memory_limit', -1);
require_once "./Cache.php";
require_once "./CacheTest.php";
require_once "./ConsistentHashing.php";
function echo_log($msg)
{
echo $msg . PHP_EOL;
}
$virtualNodeNumbers = [1, 5, 100, 120, 140, 150, 180, 200, 250, 300, 400, 500, 1000, 1500, 2000, 2500];
$data = [];
for ($i = 0; $i < 1000000; $i++) {
$data[] = "key:{$i}";
}
//标准差
$variances = [];
foreach ($virtualNodeNumbers as $virtualNodeNumber) {
$con_hash = new ConsistentHashing($virtualNodeNumber);
$caches = [];
foreach (range(1, 10) as $num) {
$cache = new CacheTest("serverNode{$num}");
$con_hash->addNode($cache);
$caches[] = $cache;
}
foreach ($data as $index => $key) {
$con_hash->set($key, $index);
}
$list = [];
foreach ($caches as $cache) {
$list[] = $cache->getCount();
echo_log("虚拟节点数量为 {$virtualNodeNumber},服务器 " . $cache->getName() . " 的命中次数为" . $cache->getCount());
}
echo_log("应该数据量：1000000, 实际数据量：" . array_sum($list));
$variances[] = $con_hash->getVariance($list);
echo_log('-----------------------------------');
}
foreach ($variances as $index => $variance) {
echo_log("虚拟节点数量为 {$virtualNodeNumbers[$index]},标准差为：{$variance}");
}
测试结果：
虚拟节点数量为 1,服务器 serverNode1 的命中次数为94240
虚拟节点数量为 1,服务器 serverNode2 的命中次数为341630
虚拟节点数量为 1,服务器 serverNode3 的命中次数为55120
虚拟节点数量为 1,服务器 serverNode4 的命中次数为29320
虚拟节点数量为 1,服务器 serverNode5 的命中次数为31360
虚拟节点数量为 1,服务器 serverNode6 的命中次数为110
虚拟节点数量为 1,服务器 serverNode7 的命中次数为317720
虚拟节点数量为 1,服务器 serverNode8 的命中次数为62910
虚拟节点数量为 1,服务器 serverNode9 的命中次数为29770
虚拟节点数量为 1,服务器 serverNode10 的命中次数为37820
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 5,服务器 serverNode1 的命中次数为94240
虚拟节点数量为 5,服务器 serverNode2 的命中次数为341630
虚拟节点数量为 5,服务器 serverNode3 的命中次数为55120
虚拟节点数量为 5,服务器 serverNode4 的命中次数为29320
虚拟节点数量为 5,服务器 serverNode5 的命中次数为31360
虚拟节点数量为 5,服务器 serverNode6 的命中次数为110
虚拟节点数量为 5,服务器 serverNode7 的命中次数为317720
虚拟节点数量为 5,服务器 serverNode8 的命中次数为62910
虚拟节点数量为 5,服务器 serverNode9 的命中次数为29770
虚拟节点数量为 5,服务器 serverNode10 的命中次数为37820
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 100,服务器 serverNode1 的命中次数为110950
虚拟节点数量为 100,服务器 serverNode2 的命中次数为15300
虚拟节点数量为 100,服务器 serverNode3 的命中次数为84940
虚拟节点数量为 100,服务器 serverNode4 的命中次数为201990
虚拟节点数量为 100,服务器 serverNode5 的命中次数为51080
虚拟节点数量为 100,服务器 serverNode6 的命中次数为47580
虚拟节点数量为 100,服务器 serverNode7 的命中次数为87180
虚拟节点数量为 100,服务器 serverNode8 的命中次数为103900
虚拟节点数量为 100,服务器 serverNode9 的命中次数为234540
虚拟节点数量为 100,服务器 serverNode10 的命中次数为62540
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 120,服务器 serverNode1 的命中次数为24800
虚拟节点数量为 120,服务器 serverNode2 的命中次数为45930
虚拟节点数量为 120,服务器 serverNode3 的命中次数为150180
虚拟节点数量为 120,服务器 serverNode4 的命中次数为131900
虚拟节点数量为 120,服务器 serverNode5 的命中次数为89460
虚拟节点数量为 120,服务器 serverNode6 的命中次数为71350
虚拟节点数量为 120,服务器 serverNode7 的命中次数为137750
虚拟节点数量为 120,服务器 serverNode8 的命中次数为79770
虚拟节点数量为 120,服务器 serverNode9 的命中次数为100530
虚拟节点数量为 120,服务器 serverNode10 的命中次数为168330
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 140,服务器 serverNode1 的命中次数为31620
虚拟节点数量为 140,服务器 serverNode2 的命中次数为45930
虚拟节点数量为 140,服务器 serverNode3 的命中次数为147120
虚拟节点数量为 140,服务器 serverNode4 的命中次数为132680
虚拟节点数量为 140,服务器 serverNode5 的命中次数为67340
虚拟节点数量为 140,服务器 serverNode6 的命中次数为56540
虚拟节点数量为 140,服务器 serverNode7 的命中次数为145620
虚拟节点数量为 140,服务器 serverNode8 的命中次数为79230
虚拟节点数量为 140,服务器 serverNode9 的命中次数为117600
虚拟节点数量为 140,服务器 serverNode10 的命中次数为176320
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 150,服务器 serverNode1 的命中次数为41760
虚拟节点数量为 150,服务器 serverNode2 的命中次数为47550
虚拟节点数量为 150,服务器 serverNode3 的命中次数为145500
虚拟节点数量为 150,服务器 serverNode4 的命中次数为129010
虚拟节点数量为 150,服务器 serverNode5 的命中次数为67340
虚拟节点数量为 150,服务器 serverNode6 的命中次数为46400
虚拟节点数量为 150,服务器 serverNode7 的命中次数为146140
虚拟节点数量为 150,服务器 serverNode8 的命中次数为82380
虚拟节点数量为 150,服务器 serverNode9 的命中次数为133890
虚拟节点数量为 150,服务器 serverNode10 的命中次数为160030
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 180,服务器 serverNode1 的命中次数为44440
虚拟节点数量为 180,服务器 serverNode2 的命中次数为59390
虚拟节点数量为 180,服务器 serverNode3 的命中次数为141640
虚拟节点数量为 180,服务器 serverNode4 的命中次数为117580
虚拟节点数量为 180,服务器 serverNode5 的命中次数为67340
虚拟节点数量为 180,服务器 serverNode6 的命中次数为44950
虚拟节点数量为 180,服务器 serverNode7 的命中次数为139610
虚拟节点数量为 180,服务器 serverNode8 的命中次数为92360
虚拟节点数量为 180,服务器 serverNode9 的命中次数为133890
虚拟节点数量为 180,服务器 serverNode10 的命中次数为158800
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 200,服务器 serverNode1 的命中次数为48780
虚拟节点数量为 200,服务器 serverNode2 的命中次数为65110
虚拟节点数量为 200,服务器 serverNode3 的命中次数为129530
虚拟节点数量为 200,服务器 serverNode4 的命中次数为116600
虚拟节点数量为 200,服务器 serverNode5 的命中次数为64160
虚拟节点数量为 200,服务器 serverNode6 的命中次数为77820
虚拟节点数量为 200,服务器 serverNode7 的命中次数为139610
虚拟节点数量为 200,服务器 serverNode8 的命中次数为100330
虚拟节点数量为 200,服务器 serverNode9 的命中次数为101450
虚拟节点数量为 200,服务器 serverNode10 的命中次数为156610
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 250,服务器 serverNode1 的命中次数为54330
虚拟节点数量为 250,服务器 serverNode2 的命中次数为63890
虚拟节点数量为 250,服务器 serverNode3 的命中次数为144970
虚拟节点数量为 250,服务器 serverNode4 的命中次数为135750
虚拟节点数量为 250,服务器 serverNode5 的命中次数为75630
虚拟节点数量为 250,服务器 serverNode6 的命中次数为76320
虚拟节点数量为 250,服务器 serverNode7 的命中次数为111910
虚拟节点数量为 250,服务器 serverNode8 的命中次数为74810
虚拟节点数量为 250,服务器 serverNode9 的命中次数为112470
虚拟节点数量为 250,服务器 serverNode10 的命中次数为149920
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 300,服务器 serverNode1 的命中次数为56360
虚拟节点数量为 300,服务器 serverNode2 的命中次数为64580
虚拟节点数量为 300,服务器 serverNode3 的命中次数为138040
虚拟节点数量为 300,服务器 serverNode4 的命中次数为122690
虚拟节点数量为 300,服务器 serverNode5 的命中次数为84380
虚拟节点数量为 300,服务器 serverNode6 的命中次数为75550
虚拟节点数量为 300,服务器 serverNode7 的命中次数为100360
虚拟节点数量为 300,服务器 serverNode8 的命中次数为94100
虚拟节点数量为 300,服务器 serverNode9 的命中次数为112590
虚拟节点数量为 300,服务器 serverNode10 的命中次数为151350
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 400,服务器 serverNode1 的命中次数为67970
虚拟节点数量为 400,服务器 serverNode2 的命中次数为65520
虚拟节点数量为 400,服务器 serverNode3 的命中次数为119520
虚拟节点数量为 400,服务器 serverNode4 的命中次数为100770
虚拟节点数量为 400,服务器 serverNode5 的命中次数为107280
虚拟节点数量为 400,服务器 serverNode6 的命中次数为98700
虚拟节点数量为 400,服务器 serverNode7 的命中次数为80060
虚拟节点数量为 400,服务器 serverNode8 的命中次数为77730
虚拟节点数量为 400,服务器 serverNode9 的命中次数为150780
虚拟节点数量为 400,服务器 serverNode10 的命中次数为131670
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 500,服务器 serverNode1 的命中次数为80870
虚拟节点数量为 500,服务器 serverNode2 的命中次数为66250
虚拟节点数量为 500,服务器 serverNode3 的命中次数为140030
虚拟节点数量为 500,服务器 serverNode4 的命中次数为155000
虚拟节点数量为 500,服务器 serverNode5 的命中次数为92360
虚拟节点数量为 500,服务器 serverNode6 的命中次数为57580
虚拟节点数量为 500,服务器 serverNode7 的命中次数为93120
虚拟节点数量为 500,服务器 serverNode8 的命中次数为86830
虚拟节点数量为 500,服务器 serverNode9 的命中次数为97790
虚拟节点数量为 500,服务器 serverNode10 的命中次数为130170
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 1000,服务器 serverNode1 的命中次数为112380
虚拟节点数量为 1000,服务器 serverNode2 的命中次数为57530
虚拟节点数量为 1000,服务器 serverNode3 的命中次数为102960
虚拟节点数量为 1000,服务器 serverNode4 的命中次数为157600
虚拟节点数量为 1000,服务器 serverNode5 的命中次数为114500
虚拟节点数量为 1000,服务器 serverNode6 的命中次数为60080
虚拟节点数量为 1000,服务器 serverNode7 的命中次数为106860
虚拟节点数量为 1000,服务器 serverNode8 的命中次数为63430
虚拟节点数量为 1000,服务器 serverNode9 的命中次数为88200
虚拟节点数量为 1000,服务器 serverNode10 的命中次数为136460
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 1500,服务器 serverNode1 的命中次数为85410
虚拟节点数量为 1500,服务器 serverNode2 的命中次数为78980
虚拟节点数量为 1500,服务器 serverNode3 的命中次数为123320
虚拟节点数量为 1500,服务器 serverNode4 的命中次数为134800
虚拟节点数量为 1500,服务器 serverNode5 的命中次数为93380
虚拟节点数量为 1500,服务器 serverNode6 的命中次数为124620
虚拟节点数量为 1500,服务器 serverNode7 的命中次数为92350
虚拟节点数量为 1500,服务器 serverNode8 的命中次数为78650
虚拟节点数量为 1500,服务器 serverNode9 的命中次数为87670
虚拟节点数量为 1500,服务器 serverNode10 的命中次数为100820
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 2000,服务器 serverNode1 的命中次数为79340
虚拟节点数量为 2000,服务器 serverNode2 的命中次数为64860
虚拟节点数量为 2000,服务器 serverNode3 的命中次数为130520
虚拟节点数量为 2000,服务器 serverNode4 的命中次数为88470
虚拟节点数量为 2000,服务器 serverNode5 的命中次数为83230
虚拟节点数量为 2000,服务器 serverNode6 的命中次数为149790
虚拟节点数量为 2000,服务器 serverNode7 的命中次数为87770
虚拟节点数量为 2000,服务器 serverNode8 的命中次数为98790
虚拟节点数量为 2000,服务器 serverNode9 的命中次数为110730
虚拟节点数量为 2000,服务器 serverNode10 的命中次数为106500
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 2500,服务器 serverNode1 的命中次数为119300
虚拟节点数量为 2500,服务器 serverNode2 的命中次数为84440
虚拟节点数量为 2500,服务器 serverNode3 的命中次数为112960
虚拟节点数量为 2500,服务器 serverNode4 的命中次数为84170
虚拟节点数量为 2500,服务器 serverNode5 的命中次数为75510
虚拟节点数量为 2500,服务器 serverNode6 的命中次数为117520
虚拟节点数量为 2500,服务器 serverNode7 的命中次数为101970
虚拟节点数量为 2500,服务器 serverNode8 的命中次数为105720
虚拟节点数量为 2500,服务器 serverNode9 的命中次数为111590
虚拟节点数量为 2500,服务器 serverNode10 的命中次数为86820
应该数据量：1000000, 实际数据量：1000000
-----------------------------------
虚拟节点数量为 1,标准差为：123690
虚拟节点数量为 5,标准差为：123690
虚拟节点数量为 100,标准差为：68918
虚拟节点数量为 120,标准差为：46606
虚拟节点数量为 140,标准差为：49989
虚拟节点数量为 150,标准差为：47358
虚拟节点数量为 180,标准差为：43601
虚拟节点数量为 200,标准差为：35809
虚拟节点数量为 250,标准差为：35384
虚拟节点数量为 300,标准差为：31256
虚拟节点数量为 400,标准差为：28139
虚拟节点数量为 500,标准差为：31843
虚拟节点数量为 1000,标准差为：33233
虚拟节点数量为 1500,标准差为：20348
虚拟节点数量为 2000,标准差为：25374
虚拟节点数量为 2500,标准差为：15932
通过上面测试虚拟节点数量的变化可以看出标准差也在变化，不同哈希函数怕出的测试结果也有差别。
标准差和java同学算出来的相差比较大，希望知道原因的大佬给予指出原因。