一致性哈希算法

Posted on

一致性hash环

一致性hash算法通过一致性hash环的数据结构来试下，环的起点是0，终点是2^32-1,起点于终点链接。

把服务器，对象放到环上

比如有四台服务器，把四台服务器ip经过hash算法后，放到环上。再把缓存的对象hash后也放到环上

为对象选择机器

对象在环上的点，顺时针找到第一台机器，就把该对象缓存到这台服务器上。见下图

tomcat-load

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
package com.yahuifan.springbootwebjspsample;

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashingWithVirtualNode {

    //待添加到hash环上的服务器ip
    private static String [] server = new String[]{"127.168.0.111","127.168.0.122",
            "127.168.0.133","127.168.0.144","127.168.0.155"};

    //用SortedMap 来表示hash环，key为服务器hash值，value为ip
    private static SortedMap<Integer,String> map = new TreeMap<Integer,String>();

    //将所有服务器放入map中
    static {
        for (int i = 0; i < server.length; i++) {
            System.out.println("[" + server[i] + "]加入集合中, 其Hash值为" + getHash(server[i]));
            map.put(getHash(server[i]),server[i]);
        }
    }

    private static String  getServer(String key){
        //获取key的hash
        Integer keyHas = getHash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = map.tailMap(keyHas);
        if(subMap.isEmpty()){
            //如果没有，取第一位
            Integer firstKey = map.firstKey();
            return map.get(firstKey);
        }else {
            //如果有，顺时针取第一个节点
            Integer firstKey = subMap.firstKey();
            return map.get(firstKey);
        }

    }

    //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
    private static int getHash(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;
    }

    public static void main(String[] args) {
        String[] keys = {"保时捷", "法拉利", "布加迪"};
        for(int i=0; i<keys.length; i++)
            System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])
                    + ", 被路由到结点[" + getServer(keys[i]) + "]");

    }

}

执行结果：
tomcat-load

缺陷

如果hash环上的服务器分配不均，会导致各个缓存服务器的负载相差较大

解决方案

利用虚拟节点的方式，给每个服务器映射多个虚拟节点，然后进行hash，放到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
71
72
73
74
75
76
package com.yahuifan.springbootwebjspsample;

import org.springframework.util.StringUtils;

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashingWithVirtualNode {

    //服务器
    private static String [] servers = {"127.168.0.999","127.168.0.888",
            "127.168.0.777","127.168.0.666","127.168.0.555"};

    //存放虚拟节点
    private static SortedMap<Integer,String> virtualNode = new TreeMap<>();

    //默认给每个服务器分配5个虚拟节点
    private static Integer VIRTUAL_NODE = 5;

    static {
        for (int i = 0; i < servers.length; i++) {
            for (int j = 0; j < VIRTUAL_NODE; j++) {
                String virNode = servers[i] + "&" + j;
                int hash = getHash(virNode);
                System.out.println("虚拟节点[" + virNode + "]被添加, hash值为" + hash);
                virtualNode.put(hash,virNode);
            }
        }
    }

    private static String getServer(String key){
        int hash = getHash(key);
        SortedMap<Integer, String> integerStringSortedMap = virtualNode.tailMap(hash);
        String virtualNo;
        if(integerStringSortedMap.isEmpty()){
            Integer firstKey = virtualNode.firstKey();
            //返回对应的虚拟节点
            virtualNo = virtualNode.get(firstKey);
        }else {
            Integer firstKey = integerStringSortedMap.firstKey();
            virtualNo = virtualNode.get(firstKey);
        }
        if(!StringUtils.isEmpty(virtualNo)){
            return virtualNo.substring(0,virtualNo.indexOf("&"));
        }
        return null;
    }


    //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
    private static int getHash(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;
    }

    public static void main(String[] args){
        String[] keys = {"拉法", "P-ONE", "918"};
        System.out.println("-------------------");
        for(int i=0; i<keys.length; i++)
            System.out.println("[" + keys[i] + "]的hash值为" +
                    getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");
    }

}

结果：
tomcat-load

总结

一致性哈希算法解决了分布式环境下，服务器增加或者减少，简单的取模运算无法获取较高的命中率的问题，通过虚拟节点的使用，让各个服务器的负载相对于均衡。