架构作业：一致性 hash

<?php

class ConsisterHash
{
    protected $serverList = []; //服务器列表
    protected $vistualNode = []; //虚拟节点
    public $vistualNodeCount = 150; //虚拟节点数 默认150


    //增加实际服务器节点
    public function addNodes(array $nodes)
    {
        foreach ($nodes as $node) {
            $this->addNode($node);
        }
    }
    
    //增加实际服务器节点
    private function addNode($server)
    {
        if (!isset($this->serverList[$server])) {

            $this->addVistualNode($server);  //增加虚拟节点

            ksort($this->vistualNode, SORT_NUMERIC);

        }

        return true;
    }

    public function getVistualNode()
    {
        return $this->vistualNode;
    }

    public function lookup($key)
    {
        $point = $this->hash(($key));

        $finalServer = current($this->vistualNode);

        foreach ($this->vistualNode as $k => $server) {

            if ($k >= $point) {
                $finalServer = $server;
                break;
            }
        }

        reset($this->vistualNode);

        return $finalServer;

    }

    //删除实际服务节点
    public function delNode($node)
    {
        if (isset($this->serverList[$node])) {

            //删除虚拟节点
            foreach ($this->serverList as $k => $v) {
                unset($this->vistualNode[$v]);
            }

            //删除实际节点
            unset($this->serverList[$node]);

        }

        return true;
    }


    /**
     * @param $string
     * @return string
     * 字符串转化成整形数字2^32;
     */
    public function hash($string)
    {
        return sprintf("%u", crc32(md5($string)));
    }

    /**
     * time33 函数
     * @param string $str
     * @return 32位正整数
     * hash(i)=33*hash(i-1)+str[i]
     */
    public function time33($str)
    {
        $hash = 0;
        $s = md5($str); //相比其它版本，进行了md5加密
        $seed = 5;
        $len = 32;//加密后长度32
        for ($i = 0; $i < $len; $i++) {

            $hash = ($hash << $seed) + $hash + ord($s{$i});
        }
        return $hash & 0x7FFFFFFF;
    }

    /**
     * @param $server
     */
    private function addVistualNode($server)
    {
        for ($i = 0; $i < $this->vistualNodeCount; $i++) {

            $vistualHashKey = $this->hash($server . "-" . $i);
            $this->vistualNode[$vistualHashKey] = $server;
            $this->serverList[$server][] = $vistualHashKey;//用作删除

        }
    }

    /**
     * @param $length
     * @return string
     * 随机数
     */
    function randomKeys($length)
    {
        $pattern = '1234567890abcdefghijklmnopqrstuvwxyz   
               ABCDEFGHIJKLOMNOPQRSTUVWXYZ';

        $key = "";
        for ($i = 0; $i < $length; $i++) {
            $key .= $pattern{mt_rand(0, 35)};    //生成php随机数
        }
        return $key;
    }

    /**
     * @param $arr
     * @return float
     * 计算标准差
     */
    public function standDeviation($arr)
    {
        $num_of_elements = count($arr);

        $variance = 0.0;

        $average = array_sum($arr) / $num_of_elements;

        foreach ($arr as $i) {
            $variance += pow(($i - $average), 2);
        }

        return (float)sqrt($variance / $num_of_elements);
    }

}

$con = new ConsisterHash();

$nodeServerList = [
    "127.0.0.0:8080",
    "127.1.1.1:8080",
    "127.2.2.2:8080",
    "127.3.3.3:8080",
    "127.4.4.4:8080",
    "127.5.5.5:8080",
    "127.6.6.6:8080",
    "127.7.7.7:8080",
    "127.8.8.8:8080",
    "127.9.9.9:8080",
];

$con->addNodes($nodeServerList);

$nodeServerList_hit = [
    "127.0.0.0:8080" => 0,
    "127.1.1.1:8080" => 0,
    "127.2.2.2:8080" => 0,
    "127.3.3.3:8080" => 0,
    "127.4.4.4:8080" => 0,
    "127.5.5.5:8080" => 0,
    "127.6.6.6:8080" => 0,
    "127.7.7.7:8080" => 0,
    "127.8.8.8:8080" => 0,
    "127.9.9.9:8080" => 0,
];

for ($i = 0; $i < 1000000; $i++) {

    $node = $con->lookup($con->randomKeys(6));

    $nodeServerList_hit[$node]++;

}

print "总计数:" . $i . "\n";

print "虚拟节点设置为:" . $con->vistualNodeCount . "\n";

foreach ($nodeServerList_hit as $k => $v) {
    print $k . ' 存储key数: ' . $v . "\n";
}

print "标准差: " . $con->standDeviation($nodeServerList_hit) . "\n";