一致性哈希

传统的Hash介绍

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

hash (数据ID) % N

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

一致性Hash介绍

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

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

或

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

一致性Hash实现

不带虚拟节点

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

带虚拟节点

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