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

发表评论     3,062 人阅读

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

回顾一致哈希算法步骤：
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的一种实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
 * 一致哈希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

发表评论

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