一致性Hash原理

简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，
如假设某哈希函数 H 的值空间为 0 ~ 2^32-1（即哈希值是一个32位无符号整形）

提高容错性和和扩展性

1，用户访问时，根据用户的 IP 使用上面相同的函数 Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针行走，遇到的第一台服务器就是其应该定位到的服务器。
2，注意这里提高容错性，用到了虚拟节点设置在圆环上，这个虚拟节点本质就是与物理节点进行绑定的一个节点，这里想到的是map形式进行绑定

一致性Hash实现

思路

1.hash值是一个非负整数，把非负整数的值范围做成一个圆环；
2.对集群的节点的某个属性求hash值（如节点名称），根据hash值把节点放到环上；
3.对数据的key求hash值，一样的把数据也放到环上，按顺时针方向，找离他最近的节点，就存储到这个节点上。（这个圆环相当于有序的集合，且为了方便查找，存储结构使用treeMap）

圆环中的存储的数据节点结构如下图所示：

代码

public class Node {

    private String id;

    private String name;

    private List<String> datas = new ArrayList<>();


    public Node() { }

    public Node(String id, String name) {
        this.id = id;
        this.name = name;
    }

    public void setId(String id) {
        this.id = id;
    }

    public void setName(String name) {
        this.name = name;
    }


    public String getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public void setDatas(List<String> datas) {
        this.datas = datas;
    }

    public List<String> getDatas() {
        return datas;
    }

    @Override
    public String toString() {
        return "Node【" +
                "id='" + id + ''' +
                ", name='" + name + ''' +
                ", datas=" + datas.toString() +
                '】';
    }
}

@Data
public class HashUtilServe {

    // 存放物理节点
    private List<Node> nodeList = new ArrayList<>();

    // 设置每个物理节点的虚拟节点50个
    private int virtalNodeNum = 50;

    // 物理节点和虚拟hash节点key进行关联
    private HashMap<Node,List<Integer>> virNode = new HashMap<>();

    // 定义一个hash集合存放节点
    private SortedMap<Integer,Node> sortedMap = new TreeMap<>();

    /**
     * 增加服务节点
     * @param node
     */
    public  void  createServe(Node node){
        // 加入物理节点
        nodeList.add(node);
        ArrayList<Integer> hashlist = new ArrayList<>();
        // 创建虚拟节点
        for(int i=0; i<virtalNodeNum; i++){
            int hashValue = FNVHash1(node.getId() + "-" + i);
            hashlist.add(hashValue);
            sortedMap.put(hashValue,node);
        }virNode.put(node,hashlist);
    }

    /**
     * 删除服务节点
     * @param node
     */
    public void deleteServe(Node node){
        // 删除物理节点
        nodeList.remove(node);
        // 删除对应的物理节点
        List<Integer> hashs = virNode.get(node);
        for (Integer hash : hashs) {
            sortedMap.remove(hash);
        }
        // 删除关联表
        virNode.remove(node);
    }

    /**
     * 查好数据对应服务节点
     * @param data
     * @return
     */
    public Node findServe(String data){

        // 对数据进行hash
        int hashValue = FNVHash1(data);

        // 获取【key>=hashvalue】的虚拟节点的map
        SortedMap<Integer, Node> findedMap = sortedMap.tailMap(hashValue);

        if(findedMap.isEmpty()){
            // 只有一台服务器节点并且当前数据缓存的服务器宕机了，找不到服务节点
            return null;
           //  return sortedMap.get(sortedMap.firstKey());
        }
        // 拿最近一台的服务器节点
        return  findedMap.get(findedMap.firstKey());
    }

    /**
     * 分布式缓存存储数据
     * @param data
     * @return
     */
    public Node saveData(String data){

        // 对数据进行hash
        int hashValue = FNVHash1(data);

        // 获取【key>=hashvalue】的虚拟节点的map
        SortedMap<Integer, Node> findedMap = sortedMap.tailMap(hashValue);

        Node node =new Node();
        if(findedMap.isEmpty()){
            // 只有一台服务器节点
            node = sortedMap.get(sortedMap.firstKey());
        }
        // 拿最近一台的服务器节点
        node = findedMap.get(findedMap.firstKey());

        // 将数据缓存到对应服务节点中
        List<String> datas = node.getDatas();
        datas.add(data);
        node.setDatas(datas);
        return node;
    }

    // 散列工具类
    public int FNVHash1(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.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 class DemoPract {
    public static void main(String[] args) {

        // 创建三台服节点对象
        Node serv1 = new Node("192.168.0.1", "serv1");
        Node serv2 = new Node("192.168.0.5", "serv2");
        Node serv3 = new Node("192.168.0.11", "serv3");

        HashUtilServe hashUtil = new HashUtilServe();
        // 将服务器添加到Hash环上
        hashUtil.createServe(serv1);
        hashUtil.createServe(serv2);
        hashUtil.createServe(serv3);

        // 缓存数据到服务节点上
        hashUtil.saveData("1今天是个好日子");
        hashUtil.saveData("2理想要有的");
        hashUtil.saveData("3很厉害的事情");
        hashUtil.saveData("啊哈java才是最牛的");

        Node serve33 = hashUtil.findServe("3很厉害的事情");
        System.out.println(serve33.toString());

        // 删除服务节点3
        hashUtil.deleteServe(serv3);
        System.out.println("---------删除服务3节点----------------");

        Node serve1 = hashUtil.findServe("1今天是个好日子");
        Node serve2 = hashUtil.findServe("2理想要有的");
        Node serve3 = hashUtil.findServe("3很厉害的事情");
        System.out.println(serve1.toString());
        System.out.println(serve2.toString());
        System.out.println(serve3.toString());

    }
}

测试结果如下：
如图所示：可以看到服务器3宕机之后，再查询原来缓存到到服务3的数据，发现三号服务器的缓存数据查询不到了