浅谈一致性hash算法_genhash

1.背景

售后系统中的执行情况是通过crane使某一台机器从数据库里获取所有待处理数据，然后进行处理。这样其实在修改代码后无法实现真正意义上的灰度部署。因此我们希望对这些待处理的数据做负载均衡，让每台机器都能处理一部分数据，从而起到灰度部署的效果。
实现负载均衡有一个很常见的算法，就是所谓的一致性hash算法。简单学习了下并且给出了算法的简单实现。

2.算法介绍

2.1 普通hash算法的局限性

我们先看一般的hash算法如何处理这一问题的。假设我们的hash算法很简单，就是对机器数取余。假设我们有12个请求，4台机器，那么每台机器的执行情况如下(Mi表示第i台机器，括号中的数字表示第几个请求)：
M1(1,5,9),M2(2,6,10),M3(3,7,11),M4(4,8,12)

很不幸，有一天M4宕机了，此时根据我们的hash运算规则，重新分配后的结果如下：
M1(1,4,7,10), M2(2,5,8,11), M3(3,6,9,12)
我们可以看到由于机器宕机导致hash值的计算规则发生变化，因此原来的大量请求都发生了处理机器的变更。很多时候我们是不希望看到这种情况的。下面我们来看一致性hash算法是如何解决这个问题的。

2.2 如何解决大量hash重定位的问题

假设我们的hash函数的值域为[0, 2^32-1]，如下图：

假设我们有三台机器，我们计算这三台机器的hash值（例如取机器的IP或者hostname进行计算），将其标记到环上：

这时假设有四个数据A,B,C,D。它们的hash值在环上的位置如下：

我们选取每个数据在环上的位置，顺时针方向寻找其遇到的第一台机器。上图中A对应的机器就是server1，D对应的就是server3，B和C对应的就是server2。

如果某台机器（例如server1）发生了宕机，此时环中server1这个节点消失，因此原来映射到server1上的数据A现在就移动到了server3上。所以当发生宕机时仅有映射到宕机机器的数据需要发生迁移，因此解决了机器变更导致大量hash映射失效的问题。

对应的，当添加新机器时也仅有部分新服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

2.3 保证平衡性

上面的思路看起来解决了hash失效的问题，但是也带来了新的问题，那就是每台机器负载均衡的问题。假设发送宕机前有n台机器，每台机器承载1/n的数据量。发生宕机后，宕机机器的下一个节点承载了两倍于之前的数据量，这是不可接受的。

之所以会出现机器变更带来的负载不均衡的问题，是因为我们将一台机器的请求全部分给了另外一台机器。如果能够将其分发给多台机器就可以解决这一问题了。因此我们引入虚拟节点的概念。

我们之前过于耿直的给一台机器只在环上建立了一个节点（映射了一个hash值），虚拟节点的意思就是每一台机器在环上建立多个节点（映射多个hash值），如下图：

假设Node1失效（环上移除绿色节点），那么原来属于Node1处理的数据一部分移动到了蓝色的Node3上，一部分移动到了青色的Node2上，这样就极大的减小了出现负载不均衡的概率（只能说降低了概率而不能说完全避免这一情况，假设每一个绿色的节点后面的节点均为蓝色，实际上还是会负载不均衡，但是这种情况会随着每台机器对应虚拟节点个数的增多而减小）。

2.4 保证环上节点的均衡性

前面的讨论事实上都基于环上节点是平均分布的，但是我们需要考虑到下面这种情况的出现：

如果虚拟节点在环上的分布本来就不均匀，那么我们的负载就极有可能出现不均衡的情况（前提是hash函数值落在每个地方的概率是均等的）。

如何避免呢，方法其实和上面一样，引入虚拟节点来增大环上的节点个数来减少出现的概率。

3.代码实现

public class ConsistentHash {

    private int nodesPerMachine = 5;

    /**
     * 所有的机器集合
     */
    private HashSet<String> machineSet;

    /**
     * 存储hash值和虚拟节点的对应关系
     */
    private SortedMap<Integer, String> hash_node_map;

    public ConsistentHash() {
        machineSet = new HashSet<>();
        hash_node_map = new TreeMap<>();
    }

    public ConsistentHash(int nodesPerMachine) {
        machineSet = new HashSet<>();
        hash_node_map = new TreeMap<>();
        this.nodesPerMachine = nodesPerMachine;
    }

    public static void main(String[] args) {
        ConsistentHash consistentHash = new ConsistentHash();
        consistentHash.addMachine("machine1");
        consistentHash.addMachine("machine2");
        consistentHash.addMachine("machine3");
        System.out.println(consistentHash.calculateMachine("input"));
        consistentHash.removeMachine("machine3");
        System.out.println(consistentHash.calculateMachine("input"));
    }

    /**
     * 添加新机器
     */
    public void addMachine(String machine) {
        machineSet.add(machine);
        System.out.println("添加新机器：" + machine);
        // 生成虚拟节点
        List<String> nodeList = generateNodeByMachine(machine);
        for (String node : nodeList) {
            hash_node_map.put(genHash(node), node);
            System.out.println("添加新节点" + node + "对应hash值为" + genHash(node));
        }
    }

    /**
     * 移除机器
     */
    public void removeMachine(String machine) {
        machineSet.remove(machine);
        System.out.println("移除机器：" + machine);
        List<String> nodeList = generateNodeByMachine(machine);
        for (String node : nodeList) {
            hash_node_map.remove(genHash(node));
        }
    }

    /**
     * 计算请求所属的机器
     *
     * @param input 请求
     * @return 机器
     */
    public String calculateMachine(String input) {
        int hash = genHash(input);
        String node;
        SortedMap<Integer, String> tailMap = hash_node_map.tailMap(hash);
        // 比虚拟节点hash值的最大值大，映射到最小hash值的虚拟节点上
        if (tailMap.isEmpty()) {
            node = hash_node_map.get(hash_node_map.firstKey());
        } else {
            node = hash_node_map.get(tailMap.firstKey());
        }
        System.out.println("请求所属虚拟节点为" + node);
        return calculateMachineByNode(node);
    }

    /**
     * 根据虚拟节点查找机器
     *
     * @param node 虚拟节点
     * @return 机器
     */
    private String calculateMachineByNode(String node) {
        return node.substring(0, node.indexOf('#'));
    }

    /**
     * 根据机器生成虚拟节点
     *
     * @param machine 机器
     * @return 虚拟节点集
     */
    private List<String> generateNodeByMachine(String machine) {
        List<String> nodeList = new ArrayList<>(nodesPerMachine);
        for (int i = 0; i < nodesPerMachine; i++) {
            String node = machine + "#" + i;
            nodeList.add(node);
        }
        return nodeList;
    }

    /**
     * 生成hash值 这段代码从网上copy而来
     *
     * @param str
     * @return
     */
    private int genHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        // 如果算出来的值为负数则取其绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

}
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

参考：
http://blog.codinglabs.org/articles/consistent-hashing.html