一致性哈希(Consistent Hashing)

发表于 | 分类于
本文字数: 1.7k | 阅读时长 ≈ 7 分钟

一致性Hash算法

需求

在使用n台缓存服务器时，一种常见的负载均衡的做法是：对资源o的请求做hash(o) mod n，来决定映射的到的服务器。当需要增加或减少缓存服务器时，最糟糕的情况是，因为所有hash(o) mod n值被改变，导致所有缓存失效。

一致性哈希要求在服务器数量变化时，也尽量使同一个资源的请求，落在同一台服务器上。

原理

一致性哈希采用环状结构，先给每个节点(集群)计算Hash，并且将节点根据Hash值放在环中指定位置，然后对资源请求做Hash，沿着顺时针的方向找到环上满足条件的第一个节点，就是该请求对应的节点。

例如有如下哈希环，每个数字代表一个哈希值：

有3台缓存服务器(E1~E3)，哈希值为hash(E1)=75，hash(E2)=10，hash(E3)=35，将3个节点放入环中：

资源请求(o1~o3)，哈希值为hash(o1)=10，hash(o2)=36，hash(o3)=90，将3个请求放入环中：

然后顺时针找到第一个节点，可以得出o1请求到E2，o2请求到E1，o3请求到E2。

1.此时如果删除E1，受影响的只有请求o2，从请求节点E1转移到E2：

2.此时如果添加E4(hash(E4)=55)，受影响的只有请求o2，从请求节点E1转移到E4：

一致性哈希可以将受影响的范围缩小为单个节点上的资源请求。

问题与优化

问题1：资源倾斜

如果哈希环很大(一般是0~2^32)，并且节点hash范围很小，就会导致大部分请求落在同一个节点上，从而负载不均衡。

例如哈希环大小为10000，而节点hash范围在1000-2000之间，那么会导致90%以上的请求落在第一个节点上(hash值大于2000或者hash值小于1000)。

问题2：节点雪崩

如果环上某个节点1不可用时，那么到节点1的请求就会落入下一个节点2，导致节点2的压力增大，如果此时节点2因为压力过大而崩溃，那么所有请求会到节点3，最终的结果就会导致所有节点都不可用。

优化：引入虚拟节点

如果将一个节点拆分成多个虚拟节点，那么整个哈希环上的节点分布就会变得相对均匀，并且每个节点的资源请求也会变得相对均匀：

一致性Hash算法实现(Java)

无虚拟节点实现

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
public class ConsistentHashingTest {

    /**
     * 节点集合
     */
    private static final SortedMap<Integer, String> NODE_MAP = new TreeMap<>();

    /**
     * 此处使用FNV1_32_HASH算法
     *
     * @param string 字符串
     * @return hash值
     */
    private int getHash(String string) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < string.length(); i++) {
            hash = (hash ^ string.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        return Math.abs(hash);
    }

    /**
     * 添加节点
     *
     * @param node 节点
     */
    private void addNode(String node) {
        NODE_MAP.put(getHash(node), node);
    }

    /**
     * 获取节点
     *
     * @param request 请求对象
     * @return 节点
     */
    private String getNode(String request) {
        SortedMap<Integer, String> map = NODE_MAP.tailMap(getHash(request));
        int hash = map.isEmpty() ? NODE_MAP.firstKey() : map.firstKey();
        return NODE_MAP.get(hash);
    }

    public static void main(String[] args) {

        ConsistentHashingTest cht = new ConsistentHashingTest();

        // 模拟3个节点，计算hash
        String[] nodes = {"192.168.1.1:11211", "192.168.1.2:11211", "192.168.1.3:11211"};
        for (String node : nodes) {
            cht.addNode(node);
        }
        for (Map.Entry<Integer, String> entry : NODE_MAP.entrySet()) {
            System.out.println("node:" + entry.getKey() + ". hash:" + entry.getValue());
        }

        // 模拟5个请求，打印请求节点结果
        for (int keyIndex = 0; keyIndex < 5; keyIndex++) {
            String key = String.valueOf("key-" + keyIndex);
            String node = cht.getNode(key);
            System.out.println("key:" + key + ". hash:" + cht.getHash(key) + ". node:" + node);
        }
    }
}

输出结果：

1
2
3
4
5
6
7
8
node:304106378. hash:192.168.1.3:11211
node:1448754510. hash:192.168.1.2:11211
node:1730768071. hash:192.168.1.1:11211
key:key-0. hash:1630648129. node:192.168.1.1:11211
key:key-1. hash:69512740. node:192.168.1.3:11211
key:key-2. hash:2003832772. node:192.168.1.3:11211
key:key-3. hash:1771936323. node:192.168.1.3:11211
key:key-4. hash:877918179. node:192.168.1.2:11211

模拟1000个请求，看下请求分布情况：

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
public static void main(String[] args) {

    ConsistentHashingTest cht = new ConsistentHashingTest();

    // 模拟3个节点，计算hash
    String[] nodes = {"192.168.1.1:11211", "192.168.1.2:11211", "192.168.1.3:11211"};
    for (String node : nodes) {
        cht.addNode(node);
    }
    for (Map.Entry<Integer, String> entry : NODE_MAP.entrySet()) {
        System.out.println("node:" + entry.getKey() + ". hash:" + entry.getValue());
    }

    Map<String, Integer> countMap = new HashMap<>();
    // 模拟1000个请求，打印请求节点结果
    for (int keyIndex = 0; keyIndex < 1000; keyIndex++) {
        String key = String.valueOf("key-" + keyIndex);
        String node = cht.getNode(key);
        int count = countMap.getOrDefault(node, 0);
        countMap.put(node, ++count);
    }

    for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
        System.out.println("node:" + entry.getKey() + ". count:" + entry.getValue());
    }
}

输出结果相当不平均：

1
2
3
node:192.168.1.1:11211. count:109
node:192.168.1.3:11211. count:345
node:192.168.1.2:11211. count:546

虚拟节点实现

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
public class ConsistentHashingTest {

    /**
     * 节点集合
     */
    private static final SortedMap<Integer, String> NODE_MAP = new TreeMap<>();

    /**
     * 虚拟节点数量
     */
    private static final int VIRTUAL_NODE_COUNT = 1000;

    /**
     * 虚拟节点分隔符
     */
    private static final String VIRTUAL_NODE_SPILT = "#";

    /**
     * 此处使用FNV1_32_HASH算法
     *
     * @param string 字符串
     * @return hash值
     */
    private int getHash(String string) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < string.length(); i++) {
            hash = (hash ^ string.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        return Math.abs(hash);
    }

    /**
     * 添加节点
     *
     * @param node 节点
     */
    private void addNode(String node) {
        NODE_MAP.put(getHash(node), node);
    }

    /**
     * 获取节点
     *
     * @param request 请求对象
     * @return 节点
     */
    private String getNode(String request) {
        SortedMap<Integer, String> map = NODE_MAP.tailMap(getHash(request));
        int hash = map.isEmpty() ? NODE_MAP.firstKey() : map.firstKey();
        String node = NODE_MAP.get(hash);
        return node.substring(0, node.indexOf(VIRTUAL_NODE_SPILT));
    }

    public static void main(String[] args) {

        ConsistentHashingTest cht = new ConsistentHashingTest();

        // 模拟3个节点，计算hash
        String[] nodes = {"192.168.1.1:11211", "192.168.1.2:11211", "192.168.1.3:11211"};
        for (String node : nodes) {
            // 使用虚拟节点
            for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
                cht.addNode(node + VIRTUAL_NODE_SPILT + i);
            }
        }
        for (Map.Entry<Integer, String> entry : NODE_MAP.entrySet()) {
            System.out.println("node:" + entry.getKey() + ". hash:" + entry.getValue());
        }

        Map<String, Integer> countMap = new HashMap<>();
        // 模拟1000个请求，打印请求节点结果
        for (int keyIndex = 0; keyIndex < 1000; keyIndex++) {
            String key = String.valueOf("key-" + keyIndex);
            String node = cht.getNode(key);
            int count = countMap.getOrDefault(node, 0);
            countMap.put(node, ++count);
        }

        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            System.out.println("node:" + entry.getKey() + ". count:" + entry.getValue());
        }
    }
}

输出结果比单节点均衡很多：

1
2
3
node:192.168.1.1:11211. count:341
node:192.168.1.3:11211. count:320
node:192.168.1.2:11211. count:339

参考

对一致性Hash算法，Java代码实现的深入研究
一致性Hash在负载均衡中的应用
Consistent Hashing