假设业务场景：有10万条数据（😂这个数据量有点少，不然改成10亿条？🤔），需要进行分布式缓存，要求可动态扩容与动态增删节点。
require_once 'HashRing.php';
$lib = new HashRingLib();
// 添加8台主机
for ($i = 1; $i<= 8; $i++) {
$lib->addHost('host'.$i);
}
// 计数
$hostNum = [];
// 模拟10万条数据
for ($i=1; $i<=100000; $i++) {
// key
$key = 'key'.$i.rand(10000,99999);
// 获得虚拟节点
$node = $lib->selectNode($lib->stringToHash($key));
// 虚拟节点对应的主机
$host = $lib->nodeList[$node];
// 计数
if (!isset($hostNum[$host])) {
$hostNum[$host] = 1;
} else {
$hostNum[$host] += 1;
}
}
// 打印结果
ksort($hostNum);
print_r($hostNum);运行结果
打印统计结果：每个主机分布了多少个key值
Array ( [host1] => 13108 [host2] => 10970 [host3] => 12408 [host4] => 14020 [host5] => 14379 [host6] => 12087 [host7] => 12767 [host8] => 10261 )
> 一致性哈希类 `HashRing.php`
class HashRing
{
// 主机列表
public $hostList = [];
// 虚拟节点列表
public $nodeList = [];
// 虚拟节点key列表
public $nodeKeyList = [];
// 默认主机节点数
public $defaultHostDodeNum = 200;
/**
* 将字符串转成hash数值
* @param string $str
* @return int
*/
public function stringToHash(string $str): int
{
return (int)sprintf('%u',crc32(md5($str)));
}
/**
* 增加主机
* @param string $host 主机标识
* @param int|null $nodeNum 主机虚拟节点数量
* @return HashRingLib
*/
public function addHost(string $host, int $nodeNum = null): HashRingLib
{
if (empty($nodeNum)) {
$nodeNum = $this->defaultHostDodeNum;
}
// 判断服务器是否存在
if (!isset($this->hostList[$host])) {
// 记录本次增加的节点【】
$addNodeList = [];
// 增加虚拟节点
for ($i = 1; $i<= $nodeNum; $i++ ) {
$node = $this->stringToHash($host.'#'.$i);
// 虚拟节点对应的服务器
$this->nodeList[$node] = $host;
// 服务器对应所有节点
$this->hostList[$host][] = $node;
// 记录当前新增的节点
$addNodeList[] = $node;
}
// 对虚拟节点排序
ksort($this->nodeList, SORT_NUMERIC);
/**
* TODO 这里省略了一个hash重新分布的步骤
* TODO 如果有业务逻辑层有缓存失效刷新逻辑，此步骤可以忽略
* 当我们新增节点时，要将大于当前节点位置的最近的一个节点上的数据，进行重新hash分布
* 1、计算出本次新增节点的最近的一个节点（大于当前节点hash）
* 2、将查找出来的节点中的key值重新进行hash分布
*/
}
return $this;
}
/**
* 删除主机
* @param string $host
* @return $this
*/
public function removeHost(string $host): HashRingLib
{
// 判断服务器是否存在
if (isset($this->hostList[$host])) {
// 要删除的节点
$deleteNodeList = $this->hostList[$host];
// 删除对应虚节点
foreach ($deleteNodeList as $node) {
unset($this->nodeList[$node]);
}
//删除对应服务器
unset($this->hostList[$host]);
/**
* TODO 移除服务器，需要把该服务服节点的数据key进行重新hash分布，此步骤省略，实现思路如下：
* 1、遍历 要删除的节点 $deleteNodeList，获得当前每个节点下挂载的key
* 2、对所有的key 进行 重新hash分布
*/
}
return $this;
}
/**
* 查找最近的节点【大于当前节点】二分查找
* 如果 大于最大节点 或者 小于最小节点 或者 等于最小节点 则 返回最小节点
* 如果 等于最大节点 返回最大节点
* @param $node
* @return mixed
*/
public function selectNode($node)
{
$arr = array_keys($this->nodeList);
// 节点长度
$length = count($arr);
// 开始位置
$start = 0;
// 结束位置
$end = $length - 1;
// 查找的值
$value = $node;
if ($end < 0) {
return $value;
}
// 如果小于最小节点 或者 大于最大节点 或则 等于最小节点
if ($node < $arr[0] or $node > $arr[$end] or $node == $arr[0]) {
return $arr[0];
}
// 当前查找节点等于最大节点
if ($node == $arr[$end]) {
return $arr[$end];
}
while ($start <= $end) {
// 中位数
$middle = floor(($start + $end) / 2);
// 当前值
$value = $arr[$middle];
// 判断当前位置的值，是否大于当前节点
if ($node < $value) {
$end = $middle - 1;
} else {
$start = $middle + 1;
}
}
return $value;
}
}