一致哈希PHP实现及应用(一致哈希学习笔记二)

一致哈希算法介绍参考文章《一致哈希算法理解(一致哈希学习笔记一)》

回顾一致哈希算法步骤:
0、将每一个服务器节点按照ip或者server_name, 通过hash函数(eg: crc32)得到对应的一组hash整数值,这里称做hash_servers,并对得到的整数值按由小到大进行排序。
1、将key也通过上面同一个hash函数计算得到对应hash整数值, 这里称为hash_key。

2、遍历hash_servers,用hash_key与hash_servers中的数逐个比较,当hash_key最后小于hash_servers中的那个数存在时,这个数对应的节点就是这个key所存储的节点,否则存在第一个节点。

一致哈希算法PHP的一种实现

/**
 * 一致哈希PHP的一种实现
 * 
 * @link 
 * @author salmonl
 * @date   2018-08-24
 */
class ConsistentHashing
{
    // 每个节点对应虚拟节点数
    const VIRTUAL_NODES = 32; 

    protected $nodes    = [];
    protected $position = [];

    /**
     * 添加节点
     */
    public function add_node($node) {
        if (isset($this->nodes[$node])) {
            return;
        }

        // 添加节点和虚拟节点
        for ($i = 0; $i < self::VIRTUAL_NODES; $i++) {
            $pos = $this->my_hash($node . '-' . $i);
            $this->position[$pos] = $node;
            $this->nodes[$node][] = $pos;
        }

        // 重新排序
        $this->sort_position();
    }

    /**
     * 删除节点
     */
    public function del_node($node) {
        if (!isset($this->nodes[$node])) return;

        // 循环删除虚拟节点
        foreach ($this->nodes[$node] as $val) {
            unset($this->position[$val]);
        }

        // 删除节点
        unset($this->nodes[$node]);
    }

    /**
     * 定位key所属节点
     */
    public function lookup($key) {
        $point = $this->my_hash($key);

        // 先取圆环上最小的一个节点,当成结果
        $node = current($this->position);

        // 循环获取相近的节点
        foreach ($this->position as $key => $val) {
            if ($point <= $key) {
                $node = $val;
                break;
            }
        }

        // 指向第一个单元
        reset($this->position);

        return $node;
    }

    /**
     * 按键名排序
     */
    private function sort_position() {
        ksort($this->position);
    }

    /**
     * 自定义哈希函数,把key转为32位符号整数
     */
    private function my_hash($key) {
        return sprintf('%u', crc32($key));
    }
}


// 测试
$ch = new ConsistentHashing();

$ch->add_node('N1');
$ch->add_node('N2');
$ch->add_node('N3');

$k1 = 'niliu_k1';
$k2 = 'niliu_k2';

echo 'key ' . $k1 . '落在' . $ch->lookup($k1) . '节点上' . PHP_EOL;
echo 'key ' . $k2 . '落在' . $ch->lookup($k2) . '节点上' . PHP_EOL;

$ch->del_node('N1');
$k1 = 'niliu_k1';
$k2 = 'niliu_k2';
echo 'after delete node' . PHP_EOL;
echo 'key ' . $k1 . '落在' . $ch->lookup($k1) . '节点上' . PHP_EOL;
echo 'key ' . $k2 . '落在' . $ch->lookup($k2) . '节点上' . PHP_EOL;

// output
key niliu_k1落在N1节点上
key niliu_k2落在N3节点上
after delete node
key niliu_k1落在N3节点上
key niliu_k2落在N3节点上

更多语言实现可参考:Implementations in various languages

参考:
https://www.jianshu.com/p/bf3eb8c8e519

发表评论

电子邮件地址不会被公开。 必填项已用*标注