PHP 实现一致性哈希算法

class Hash
{
    private $serverList;
    private $virtualNodeNum;
    private $nodeList = [];
    private $nodeServerMap = [];
    public function __construct($serverList, $virtualNodeNum)
    {
        $this->serverList = $serverList;
        $this->virtualNodeNum = $virtualNodeNum;
        $this->_initNodeList();
    }
    //通过key值获取服务器信息（遍历算法）
    public function getServerName($key)
    {
        $keyPosition = $this->_getHashName($key);
        $resNode = $this->nodeList[0];
        foreach ($this->nodeList as $key => $node) {
            if ($keyPosition < $node) {
                $resNode = $node;
                break;
            };
        }
        return $this->nodeServerMap[$resNode];
    }
    //通过key值获取服务器信息（二分算法）
    public function getServerName2($key)
    {
        $keyPosition = $this->_getHashName($key);
        $resNode = $this->nodeList[0];
        $start = 0;
        $end = count($this->nodeList) - 1;
        if ($keyPosition > $this->nodeList[$start] && $keyPosition < $this->nodeList[$end]) {
            while ($start <= $end) {
                $middle = intval(($start + $end) / 2);
                if ($middle < 1) {
                    break;
                }
                if ($keyPosition <= $this->nodeList[$middle] && $keyPosition > $this->nodeList[$middle - 1]) {
                    $resNode = $this->nodeList[$middle];
                    break;
                }
                if ($keyPosition < $this->nodeList[$middle]) {
                    $end = $middle - 1;
                } else {
                    $start = $middle + 1;
                }
            }
        }
        if ($keyPosition == $this->nodeList[$end]) {
            $resNode = $this->nodeList[$end];
        }
        return $this->nodeServerMap[$resNode];
    }
    //初始化虚拟节点
    private function _initNodeList()
    {
        foreach ($this->serverList as $serverName) {
            $this->_addNode($serverName);
        }
        asort($this->nodeList, SORT_NUMERIC);
        $this->nodeList = array_merge($this->nodeList, []);
    }
    //生成哈希值
    private function _getHashName($key)
    {
        return sprintf('%u', crc32($key));
    }
    //为单服务器加虚拟节点
    private function _addNode($serverName)
    {
        for ($i = 0; $i < $this->virtualNodeNum; $i++) {
            $key = $serverName . '_' . $i;
            $node = $this->_getHashName($key);
            $this->nodeList[] = $node;
            $this->nodeServerMap[$node] = $serverName;
        }
    }
}

function getVariance($avg, $list, $isSwatch = false)
{
    $arrayCount = count($list);
    if ($arrayCount == 1 && $isSwatch == TRUE) {
        return FALSE;
    } elseif ($arrayCount > 0) {
        $total_var = 0;
        foreach ($list as $lv)
            $total_var += pow(($lv - $avg), 2);
        return $isSwatch ? sqrt($total_var / (count($list) - 1)) : sqrt($total_var / count($list));
    } else
        return false;
}

function test($serverNum)
{
    echo $serverNum . '个服务节点测试' . PHP_EOL;
    $minNum = 0;
    $minVariance = null;
    $key = 'RenXiaoLong';
    for ($n = 0; $n < $serverNum; $n++) {
        $serverList[] = 'server_' . ($n+1);
    }
    $keyNum = 1000000;//100万KV值
    for ($virtualNodeNum = 50; $virtualNodeNum <= 250; $virtualNodeNum = $virtualNodeNum + 10) {
        $bucketList = [];
        $serverHash = new Hash($serverList, $virtualNodeNum);
        for ($i = 0; $i < $keyNum; $i++) {
            $serverName = $serverHash->getServerName2($key . '_' . $i);
            if (!isset($bucketList[$serverName])) {
                $bucketList[$serverName] = 1;
            } else {
                $bucketList[$serverName]++;
            }
        }
        $variance = getVariance($keyNum / count($serverList), $bucketList);
        if (is_null($minVariance) || $minVariance > $variance) {
            $minVariance = $variance;
            $minNum = $virtualNodeNum;
        }
        echo '虚拟节点数：' . $virtualNodeNum . ' 标准差：' . $variance . PHP_EOL;
    }
    echo PHP_EOL . ' 最小标准差：' . $minVariance . ' 此时虚拟节点数：' . $minNum;
}

10个服务节点测试
虚拟节点数：50 标准差：23823.18714614
虚拟节点数：60 标准差：13750.255706713
虚拟节点数：70 标准差：10457.388259025
虚拟节点数：80 标准差：12140.558043187
虚拟节点数：90 标准差：10525.395707526
虚拟节点数：100 标准差：9295.6409999526
虚拟节点数：110 标准差：10793.353955097
虚拟节点数：120 标准差：12310.234067637
虚拟节点数：130 标准差：12050.280851499
虚拟节点数：140 标准差：12502.381789083
虚拟节点数：150 标准差：11116.714442676
虚拟节点数：160 标准差：11321.901059451
虚拟节点数：170 标准差：11846.528622343
虚拟节点数：180 标准差：11664.198489395
虚拟节点数：190 标准差：12261.751139213
虚拟节点数：200 标准差：13443.812428028
虚拟节点数：210 标准差：13487.275551423
虚拟节点数：220 标准差：13023.136265892
虚拟节点数：230 标准差：13377.86814855
虚拟节点数：240 标准差：13833.141826787
虚拟节点数：250 标准差：13468.785216195

最小标准差：9295.6409999526 此时虚拟节点数：100

虚拟节点数：50 标准差：19297.022367828
虚拟节点数：60 标准差：13789.030155457
虚拟节点数：70 标准差：12054.611169436
虚拟节点数：80 标准差：12896.92409033
虚拟节点数：90 标准差：12870.180499226
虚拟节点数：100 标准差：12419.704611145
虚拟节点数：110 标准差：12476.328542517
虚拟节点数：120 标准差：12978.090505677
虚拟节点数：130 标准差：13230.367235022
虚拟节点数：140 标准差：13510.130888637
虚拟节点数：150 标准差：11336.710886276
虚拟节点数：160 标准差：10958.520043199
虚拟节点数：170 标准差：12371.022162917
虚拟节点数：180 标准差：12781.696298397
虚拟节点数：190 标准差：13978.722151604
虚拟节点数：200 标准差：15354.59327459
虚拟节点数：210 标准差：15417.344232181
虚拟节点数：220 标准差：14829.183563958
虚拟节点数：230 标准差：14817.24592527
虚拟节点数：240 标准差：14795.569431756
虚拟节点数：250 标准差：15065.574263891

最小标准差：10958.520043199 此时虚拟节点数：160