Created
July 22, 2020 07:50
-
-
Save storyflow/174f5cc7b6aee6e7b6e1bf64e9bbd0c0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
// 一致性哈希算法 | |
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); | |
} | |
} | |
// 测试 | |
$con = new ConsistentHashing(); | |
$con->addNode('a'); | |
$con->addNode('b'); | |
$con->addNode('c'); | |
$con->addNode('d'); | |
$key1 = 'www.zhihu.com'; | |
$key2 = 'www.baidu.com'; | |
$key3 = 'www.google.com'; | |
$key4 = 'www.testabc.com'; | |
echo 'key' . $key1 . '落在' . $con->lookup($key1) . '号节点上!<br>'; | |
echo 'key' . $key2 . '落在' . $con->lookup($key2) . '号节点上!<br>'; | |
echo 'key' . $key3 . '落在' . $con->lookup($key3) . '号节点上!<br>'; | |
echo 'key' . $key4 . '落在' . $con->lookup($key4) . '号节点上!<br>'; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment