Memcached 一致性哈希算法

通俗理解一致性哈希
把各服务器节点映射放在钟表的各个时刻上, 把 key 也映射到钟表的某个时刻上. 该 key 沿钟表顺时针走,碰到的第 1 个节点即为该 key 的存储节点

疑问 1: 时钟上的指针最大才 11 点,如果我有上百个 memcached 节点怎么办?
答: 时钟只是为了便于理解做的比喻,在实际应用中,我们可以在圆环上分布[0,2^32-1]的数字, 这样,全世界的服务器都可以装下了.

疑问 2: 我该如何把”节点名”,”键名”转化成整数?
答: 你可以用现在的函数,如 crc32(),也可以自己去设计转化规则,但注意转化后的碰撞率要低. 即不同的节点名,转换为相同的整数的概率要低. 一致性哈希对其他节点的影响通过图可以看出,当某个节点 down 后,只影响该节点顺时针之后的 1 个节点,而其他节点 不受影响.因此，Consistent Hashing 最大限度地抑制了键的重新分布

一致性哈希+虚拟节点对缓存命中率的影响
由图中可以看到,理想状态下, 1) 节点在圆环上分配分配均匀,因此承担的任务也平均,但事实上, 一般的 Hash 函数对于节 点在圆环上的映射,并不均匀. 2) 当某个节点 down 后,直接冲击下 1 个节点,对下 1 个节点冲击过大,能否把 down 节点上的 压力平均的分担到所有节点上? 完全可以—引入虚拟节点来达到目标 虚拟节点即----N 个真实节点,把每个真实节点映射成 M 个虚拟节点, 再把 M*N 个虚拟节点, 散列在圆环上. 各真实节点对应的虚拟节点相互交错分布 这样,某真实节点 down 后,则把其影响平均分担到其他所有节点上

<?php
/**
 * 一致性哈希
 *
 * @author jinpeng
 * @date 2022/10/26
 */

class Content{

    protected $_node = [];
    protected $_position = [];
    protected $_mul = 64; //散列成64个虚拟节点

    // 查找key所处的位置
    public function find($key)
    {
        $point = $this->_hash($key);

        echo "<br/>";
        echo 'key节点位置：'. $point;
        echo "<br/>";

        $node = current($this->_position);
        foreach ($this->_position as $key => $item)
        {
            if ($point <= $key)
            {
                $node = $item;
                break;
            }
        }

        return $node;
    }

    // 排序节点
    protected function _sortNode()
    {
        ksort($this->_position, SORT_REGULAR);
    }

    // 新增节点
    public function addNode($node)
    {
        // 分布散列点
        for ($i =1; $i < $this->_mul; $i ++)
        {
            $posName = $node . '_' . $i;
            $this->_position[$this->_hash($posName)] = $node;
        }

        $this->_sortNode();
    }

    // 删除节点
    public function delNode($node)
    {
        foreach ($this->_position as $key => $item)
        {
            if ($node == $item)
            {
                unset($this->_position[$key]);
            }
        }
    }

    protected function _hash($str)
    {
        return sprintf("%u", crc32($str)); // 无符号的 0-2^32
    }


    // 测试方法
    public function getPosition()
    {
        echo "<pre>";
        print_r($this->_position);
    }
}


$con = new Content();
$con->addNode('a');
$con->addNode('b');
$con->addNode('c');

$con->getPosition();

echo '获取到环上节点：'. $con->find('name');