一致性hash算法

今天听了一下大树老师的公开课，关于一致性hash算法，记录一下

• 当我们数据多时，我们就要用到集群，分布式，为了缓解数据库的压力，这时候我们会用到缓存，比如redis就是一个很好的缓存中间件
• 为了能让数据均衡的分布，我们可以用hash值 取余 的方式达到分布均衡，简单而且高效。
• 但也有一个问题就是如果我们需要在加一个节点呢，就会数据缓存命不中，从而增加数据库压力，甚至导致崩溃。（缓存雪崩）
• 比如原本有三个节点，我们加一个节点进去，就会造成 3/4 的缓存失效，同样如果是4 个节点，增加一个就会造成 4/5 的缓存失效。
  • 这时候我们可以选择加班，扩容，预热数据
  • 所以要想不加班，我们可以用一致性Hash算法

一致性Hash算法的规则

1. hash 值要是一个非负整数，把非负整数值范围做成一个圆环
2. 对集群节点的某个属性求hash值（如节点名称），根据hash值把节点放到环上
3. 对key求hash值，一样把数据也放到环上，按顺时针方向，离他最近的节点，就把他存储到这个节点上

但是我们发现不能缓解原有压力的节点，而且集群节点不一定会均衡分布在环上，（hash是散列值）

这时候，我们就需要加入虚拟节点的概念（把虚拟节点上环，虚拟节点越多，分布越均衡），新增节点的虚拟节点越多，对原有节点影响越均衡 这时候新增节点，对数据的影响比列： 1/4

代码呈现

• 物理，虚拟节点
• hash算法
• 虚拟节点放到环上 -> 值空间(0，int.max)
• 数据找到对应节点上

package 一致性hash算法;

import java.util.*;

/**
 * @Author :Ersan
 * @Date 2020/11/19
 * @Description
 */
public class ConsistenceHash {
    //物理节点 {id , name , ip......}
    private List<String> realNodes = new ArrayList<>();

    //保存物理节点与虚拟节点的关系
    private Map<String,List<Integer>> real2VirtualMap = new HashMap<>();

    //排序存储结构 环 key 是虚拟节点的hash值 value 物理节点名
    private SortedMap<Integer,String> sortedMap = new TreeMap<>();

    //虚拟节点的数量
    private int virutalNums = 100;

    public ConsistenceHash(int virutalNums) {
        this.virutalNums = virutalNums;
    }

//    public void removeServer(String node){
//
//    }

    public void addServer(String node) {

        this.realNodes.add(node);
        //虚拟出指定数量的虚拟节点
        int count = 0 , i = 0;
        String vnode = null;
        List<Integer> virutalNodes = new ArrayList<>(this.virutalNums);
        this.real2VirtualMap.put(node,virutalNodes);

        while ( count < this.virutalNums ) {
            i++;
            vnode = node + "--" + i;

            //计算hash值
            int hashvalue = FNV1_32_HASH.getHash(vnode);
            //hash 值会冲突 (hash冲突概率很低，不会影响)
            if (!sortedMap.containsKey(hashvalue)) {
                //保存物理节点与虚拟节点的对应关系
                virutalNodes.add(hashvalue);
                //虚拟节点要放到环上去   环在哪儿？？？？？ 数据结构   红黑树 TreeMap
                sortedMap.put(hashvalue,node);
                count++;
            }
        }
    }

    public String getServer(String key) {
        int hash = FNV1_32_HASH.getHash(key);
        //顺时针方向找，离他最近的
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            return sortedMap.get(sortedMap.firstKey());
        } else {
            return subMap.get(subMap.firstKey());
        }
    }

    public static void main(String[] args) {
        ConsistenceHash ch = new ConsistenceHash(100);
        ch.addServer("192.168.10.10");
        ch.addServer("192.168.10.11");
        ch.addServer("192.168.10.12");

        for (int i = 0; i < 10; i++) {
            System.out.println("bigTree-" + i + "对应的服务器：" + ch.getServer("bigTree-" + i));
        }
    }
}

FNV1_32_HASH

package 一致性hash算法;

/**
 * @Author :Ersan
 * @Date 2020/11/19
 * @Description
 */
public class FNV1_32_HASH {
    public static int getHash(String key) {
        final  int  p  =  16777619;
        int  hash  =  (int)2166136261L;
        for(int  i  =  0;  i  <  key.length();  i++)  {
            hash  =  (hash  ^  key.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;
    }
}