一致性哈希

发表于 | 分类于
字数统计: 1,694 | 阅读时长 ≈ 8

传统的Hash介绍

传统的Hash是对服务器进行取模（取余）操作。
假如服务器的台数是N，取模算法为：

1
hash (数据ID) % N

使用上述Hash算法时，会有一些缺陷。
当缓存服务器数量发生变化时，会引起缓存的雪崩或几乎所有的位置缓存改变。

一致性Hash介绍

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，一致性哈希修正了使用的简单哈希算法带来的问题，当缓存服务器数量发生变化时可以尽量减少受影响的缓存。
采用一致性哈希算法时，服务器的数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存失效，缓存仍然能分担整个系统的压力，不至于同一时间集中到后端服务器上。
一致性哈希算法也是使用取模的方法，只是不是对服务器的数量进行取模，而是对 2^32 取模，算法如下。

1
hash (服务器的IP地址) % 2^32

或

1
hash (服务器的主机名) % 2^32

一致性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
package hash;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.zip.CRC32;

public class ConsistentHashWithoutVirtualNode {
    //用来存储服务器节点对象
    List<ServerNode> serverNodes= new ArrayList<ServerNode>();

    //添加服务器节点
    public void addServerNode(String serverNodeName){
        if(serverNodeName==null){
            return;
        }
        //利用Hash算法，求出服务器节点的Hash值
        long serverNodeHash = getHash(serverNodeName);
        ServerNode serverNode = new ServerNode(serverNodeName,serverNodeHash);
        serverNodes.add(serverNode);

        //将serverNodes进行排序
        Collections.sort(serverNodes,new Comparator<ServerNode>() {

            @Override
            public int compare(ServerNode node1, ServerNode node2) {
                if(node1.getServerNodeHash()<node2.getServerNodeHash()){
                    return -1;
                }
                return 1;
            }

        });
    }

    public long getHash(String serverNodeName) {
        CRC32 crc32 = new CRC32();
        crc32.update(serverNodeName.getBytes());
        return crc32.getValue();
    }
    //删除服务器节点
    public void deleteServerNode(String serverName){
        //这里假设所有服务器名字不一样，则直接遍历名字是否相同即可
        int serverNum=serverNodes.size();
        for(int i=0;i<serverNum;i++){
            ServerNode node = serverNodes.get(i);
            if(node.getServerNodeName().equals(serverName)){
                serverNodes.remove(node);
                return;
            }
        }
    }
    //得到应当路由到的服务器结点
    public ServerNode getServerNode(String key){
        //得到key的hash值
        long hash = getHash(key);
        //在serverNodes中找到大于hash且离其最近的的那个ServerNode
        //由于serverNodes是升序排列的，因此，找到的第一个大于hash的就是目标节点
        for(ServerNode node:serverNodes){
            if(node.getServerNodeHash()>hash){
                return node;
            }
        }
        //如果没有找到，则说明此key的hash值比所有服务器节点的hash值都大，因此返回最小hash值的那个Server节点
        return serverNodes.get(0);

    }

    public void printServerNodes(){
        System.out.println("所有的服务器节点信息如下：");
        for(ServerNode node:serverNodes){
            System.out.println(node.getServerNodeName()+":"+node.getServerNodeHash());
        }
    }
}

带虚拟节点

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
133
134
135
136
137
138
139
package hash;

public class VirtualServerNode {
    private String serverNodeName;//这个名字指的是其对应的真实的物理服务器节点的名字
    private long virtualServerNodeHash;

    public VirtualServerNode(String serverNodeName, long virtualServerNodeHash) {
        super();
        this.serverNodeName = serverNodeName;
        this.virtualServerNodeHash = virtualServerNodeHash;
    }
    public String getServerNodeName() {
        return serverNodeName;
    }
    public void setServerNodeName(String serverNodeName) {
        this.serverNodeName = serverNodeName;
    }
    public long getVirtualServerNodeHash() {
        return virtualServerNodeHash;
    }
    public void setVirtualServerNodeHash(long virtualServerNodeHash) {
        this.virtualServerNodeHash = virtualServerNodeHash;
    }

}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.zip.CRC32;

public class ConsistentHashWithVirtualNode {
    //保存虚拟服务器节点节点
    List<VirtualServerNode> virtualServerNodes = new ArrayList<VirtualServerNode>();
    //每个物理节点对应的虚拟节点的个数
    private final static int VIRTUAL_NUM = 5;
    //添加服务器节点
    public void addServerNode(String serverName){
        if(serverName==null){
            return;
        }
        for(int i=0;i<VIRTUAL_NUM;i++){
            //这里假设，虚拟节点的名字为类似这样的形式：serverName+"&&VN"+i，这样方便从虚拟节点得到物理节点
            String virtualServerNodeName = serverName+"&&VN"+i;
            long hash = getHash(virtualServerNodeName);
            VirtualServerNode vsNode = new VirtualServerNode(serverName, hash);
            virtualServerNodes.add(vsNode);
        }
        //将virtualServerNodes进行排序
        Collections.sort(virtualServerNodes,new Comparator<VirtualServerNode>() {

            @Override
            public int compare(VirtualServerNode node1, VirtualServerNode node2) {
                if(node1.getVirtualServerNodeHash()<node2.getVirtualServerNodeHash()){
                    return -1;
                }
                return 1;
            }

        });     

    }
    public long getHash(String serverNodeName) {
        CRC32 crc32 = new CRC32();
        crc32.update(serverNodeName.getBytes());
        return crc32.getValue();
    }
    //删除服务器节点,即要删除其物理服务器节点对应的所有虚拟节点
    public void deleteServerNode(String serverName){

        for(int i=0;i<virtualServerNodes.size();i++){
            VirtualServerNode node = virtualServerNodes.get(i);

            if(node.getServerNodeName().contains(serverName)){//这里用了contain查找，这里就把该物理服务器节点对应的虚拟节点都删除了
                virtualServerNodes.remove(node);
                /*
                 * 删除元素后，需要把下标减一。这是因为在每次删除元素后，ArrayList会将后面部分的元素依次往上挪一个位置(就是copy)，
                 * 所以，下一个需要访问的下标还是当前下标，所以必须得减一才能把所有元素都遍历完。
                 * */
                i--;
            }
        }
    }
    //得到应当路由到的结点
    public VirtualServerNode getServerNode(String key){
        //得到key的hash值
        long hash = getHash(key);
        //在VirtualServerNode中找到大于hash且离其最近的的那个VirtualServerNode
        //由于serverNodes是升序排列的，因此，找到的第一个大于hash的就是目标节点
        for(VirtualServerNode node:virtualServerNodes){
            if(node.getVirtualServerNodeHash()>hash){
                return node;
            }
        }
        //如果没有找到，则说明此key的hash值比所有服务器节点的hash值都大，因此返回最小hash值的那个Server节点
        return virtualServerNodes.get(0);

    }

    public void printServerNodes(){
        System.out.println("所有的服务器节点信息如下：");
        for(VirtualServerNode node:virtualServerNodes){
            System.out.println(node.getServerNodeName()+":"+node.getVirtualServerNodeHash());
        }
    }

    public static void main(String[] args){
        ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode();
        //添加一系列的服务器节点
        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"};
        for(String server:servers){
            ch.addServerNode(server);
        }
        //打印输出一下服务器节点
        ch.printServerNodes();

        //看看下面的客户端节点会被路由到哪个服务器节点
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        System.out.println("此时，各个客户端的路由情况如下：");
        for(String node:nodes){
            VirtualServerNode virtualServerNode = ch.getServerNode(node);
            System.out.println(node+","+ ch.getHash(node)+"------->"+
                    virtualServerNode.getServerNodeName()+","+virtualServerNode.getVirtualServerNodeHash());
        }

        //如果由一个服务器节点宕机，即需要将这个节点从服务器集群中移除
        String deleteNodeName="192.168.0.2:111";
        ch.deleteServerNode(deleteNodeName);

        System.out.println("删除节点"+deleteNodeName+"后，再看看同样的客户端的路由情况，如下：");
        for(String node:nodes){
            VirtualServerNode virtualServerNode = ch.getServerNode(node);
            System.out.println(node+","+ ch.getHash(node)+"------->"+
                    virtualServerNode.getServerNodeName()+","+virtualServerNode.getVirtualServerNodeHash());
        }
    }
}
坚持原创技术分享，您的支持将鼓励我继续创作！