PHP通过一致性哈希算法实现哈希环

假设业务场景：有10万条数据，需要进行分布式缓存，要求可动态扩容与动态增删节点。

一致性哈希类 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)
    {
        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;
    }
}

演示代码

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
)