分布式一致性 hash 算法

<?php
/**
 * Created by PhpStorm.
 * User: 消逝文字
 * Date: 2020/7/8
 * Time: 23:07
 */
class HomeWork
{
    private $server;
    private $node;
    public function hash($str)
    {
        return sprintf('%u', crc32($str));
    }
    public function addServer($server)
    {
        if (!isset($this->server[$server])) {
            $this->addNode($server);
        }
    }
    public function addNode($server)
    {
        for ($i = 0; $i < 200; $i++) {
            $key_node = $this->hash($server.$i);
            $this->server[$server][] = $key_node;
            $this->node[$key_node] = $server;
        }
        ksort($this->node, SORT_NUMERIC);
    }
    public function dropServer($server)
    {
        foreach ($this->server[$server] as $value) {
            unset($this->node[$value]);
        }
        unset($this->server[$server]);
    }
    public function getServer($str)
    {
        $key_str = $this->hash($str);
        $server = current($this->node);
        foreach ($this->node as $k => $v) {
            if ($k >= $key_str) {
                $server = $v;
                break;
            }
        }
        reset($this->node);
        return $server;
    }
}
$server = new HomeWork();
$server->addNode('192.168.1.1:8080');
$server->addNode('192.168.1.2:8080');
$server->addNode('192.168.1.3:8080');
$server->addNode('192.168.1.4:8080');
$server->addNode('192.168.1.5:8080');
$server->addNode('192.168.1.6:8080');
$server->addNode('192.168.1.7:8080');
$server->addNode('192.168.1.8:8080');
$server->addNode('192.168.1.9:8080');
$server->addNode('192.168.1.10:8080');
// 补充
/**
 * Created by phpStorm
 * User: Kevin Xiang
 * Date: 2020/7/9
 * Time: 11:09 AM
 */
/**
 *  用你熟悉的编程语言实现一致性 hash 算法。
 *  编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，
 *  计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
 * Class ConsistentHashing
 */
class ConsistentHashing
{
    private $ring = [];  // Hash 环
    private $node = [];  // 服务器节点数组
    private $virtualNodeNums; // 虚拟节点数量
    public function __construct($node, $virtualNodeNums)
    {
        $this->node = $node;
        $this->virtualNodeNums = $virtualNodeNums;
        $this->addServer($this->node);
    }
    public function hash(string $str)
    {
        $hash = 0;
        $s = md5($str);
        $seed = 5;
        $len = 32;
        for ($i = 0; $i < $len; $i++) {
            $hash = ($hash << $seed) + $hash + ord($s{$i});
        }
        return $hash & 0x7FFFFFFF;
    }
    protected function addServer(array $server)
    {
       foreach ($server as $v) {
            $this->addNode($v);
       }
    }
    protected function addNode(string $node)
    {
        for ($i = 0; $i < $this->virtualNodeNums; $i++) {
            $hash_node = $this->hash($node."#".$i);
            $this->ring[$node][] = $hash_node;
            $this->node[$hash_node] = $node;
        }
        ksort($this->ring, SORT_NUMERIC);
    }
    public function removeServer(string $node)
    {
        if (isset($this->ring[$node]))
        {
            foreach ($this->ring[$node] as $v)
                unset($this->node[$v]);
            unset($this->ring[$node]);
        }
    }
    public function findServer(string $key)
    {
        $hash_key = $this->hash($key);
        $server = current($this->node);
        foreach ($this->node as $k => $v)
        {
            if ($k >= $hash_key)
            {
                $server = $v;
                break;
            }
        }
        reset($this->node);
        return $server;
    }
}
$node = [
    '192.168.1.10',
    '192.168.2.10',
    '192.168.3.10',
    '192.168.4.10',
    '192.168.5.10',
    '192.168.6.10',
    '192.168.7.10',
    '192.168.8.10',
    '192.168.9.10',
    '192.168.10.10',
];
$cHash = new ConsistentHashing($node, 150);
$cHash->removeServer('192.168.1.10');
for ($i = 0; $i <= 1000000; $i++) {
    $key = "missyourlove#".$i;
    echo "key:".$key."落在了".$cHash->findServer($key)."服务器上".PHP_EOL;
}