算法实现

不带虚拟节点的实现

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
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 不带虚拟节点的一致性Hash算法
 */
public class ConsistentHashingWithoutVirtualNode {

    //待添加入Hash环的服务器列表
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111",
            "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};

    //key表示服务器的hash值，value表示服务器
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();

    //程序初始化，将所有的服务器放入sortedMap中
    static {
        for (int i = 0; i < servers.length; i++) {
            String server = servers[i];
            int hash = getHash(server);
            System.out.println("[" + server + "]加入集合中, 其Hash值为" + hash);
            sortedMap.put(hash, server);
        }
        System.out.println();
    }

    //得到应当路由到的结点
    private static String getServer(String key) {
        //得到该key的hash值
        int hash = getHash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            return sortedMap.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            return subMap.get(i);
        }
    }

    //使用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 (String key : keys)
            System.out.println("[" + key + "]的hash值为" + getHash(key)
                    + ", 被路由到结点[" + getServer(key) + "]");
    }
}

带虚拟节点的实现

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
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.locks.StampedLock;

/**
 * @author <a href="mailto:wf2311@163.com">wf2311</a>
 * @since 2021/4/25 19:08.
 */
public class ConsistentHashingWithVirtualNode {
    private static final String NODE_SPILT = "@@";
    private static final String NODE_PREFIX = "VN";

    /**
     * key表示服务器的hash,value表示服务器
     */
    private final SortedMap<Integer, String> map = new TreeMap<>();

    /**
     * 服务器节点
     */
    private final List<String> servers;

    /**
     * 虚拟节点数量
     */
    private final int virtualNodeNum;

    private final StampedLock lock = new StampedLock();

    public ConsistentHashingWithVirtualNode(List<String> servers, int virtualNodeNum) {
        this.servers = servers;
        this.virtualNodeNum = virtualNodeNum;
        init();
    }

    private void init() {
        for (String server : servers) {
            addServer(server);
        }
    }

    public void addServer(String server) {
        long stamp = lock.writeLock();
        try {
            for (int i = 0; i < virtualNodeNum; i++) {
                String virtual = server + NODE_SPILT + NODE_PREFIX + i;
                int hash = getHash(virtual);
                map.put(hash, virtual);
            }
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    public void removeServer(String server) {
        long stamp = lock.writeLock();
        try {
            for (int i = 0; i < virtualNodeNum; i++) {
                String virtual = server + NODE_SPILT + NODE_PREFIX + i;
                map.remove(getHash(virtual));
            }
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    private void removeServer(String server, int i) {
        long stamp = lock.writeLock();
        try {
            String virtual = server + NODE_SPILT + NODE_PREFIX + i;
            int hash = getHash(virtual);
            map.put(hash, virtual);
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    public String findServer(String request) {
        int hash = getHash(request);
        long stamp = lock.tryOptimisticRead();
        String server = getServerByHashKey(hash);
        if (!lock.validate(stamp)) {
            stamp = lock.readLock();
            try {
                server = getServerByHashKey(hash);
            } finally {
                lock.unlockRead(stamp);
            }
        }
        return server;
    }

    private String getServerByHashKey(int hash) {
        SortedMap<Integer, String> subMap = map.tailMap(hash);
        Integer targetServerKey = subMap.isEmpty() ? map.firstKey() : subMap.firstKey();
        String virtual = map.get(targetServerKey);
        if (virtual != null) {
            return virtual.split(NODE_SPILT)[0];
        }
        return null;
    }

    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;
    }

}