一致性 hash 算法

关注
发布于: 2020 年 11 月 22 日
hash的意思是散列，目的将一组输入的数据均匀的分开、打散。可以实现快速的查找，插入，删除等操作。在很多工具和程序都能看到，比如：map的key，负载均衡，数据分片，数据统计等等。
一致性hash：对节点和数据，都做一次hash运算，然后比较节点和数据的hash值，数据值和节点最相近的节点作为处理节点。为了分布得更均匀，通过使用虚拟节点的方式，每个节点计算出n个hash值，均匀地放在hash环上这样数据就能比较均匀地分布到每个节点。
原理：
对于一个圆形的环分割成2^32份，也就是0到2^32-1的空间，然后在这个圆形的空间均匀的分布所有的服务器。比如有三个服务器就分成三份。按照顺时针的方向，每个服务器只管理自己顺时针上的区域，那么就可以管理这个园上所有区域的数据就分别存储到三个服务器上。理论上很完美的实现了hash值和服务器的关系。下图说明：
上面的CacheA，CacheB,CacheC这是三个服务器。如果计算的对象对应的hash值刚好这三个服务器，直接就可以取到服务器。如果就像图中Object1对应的hash值key1不在服务器，按照顺时针的方向，找到cacheA，说明Object1对象在CacheA存储着，同理Object4在CacheB上。
实际物理节点：
图中有三个服务器，对应三个物理节点，每个节点按理想情况下负载压力差不多。一切看起来那么完美，但是，如果CacheB服务器挂掉，按照顺时针的方法，Object4就会找到CacheC上，这样CacheC就会承担2\3的压力，也就是CacheC的压力是cacheA的两倍。也会出现数据迁移的，导致原先圆环的数据重新分配到CacheA和CacheB上。这样很容易出现问题。这些下面的出现解决方案！
虚拟物理节点：
如果上图的服务器的每个虚拟出5个节点，这样就有原先的3个服务器变成15个服务器，然后把这15个服务器在通过hash运算放到这个环上，这样就会出现均匀的计算，比如：CacheA&&VN1，CacheC&&VN1，CacheB&&VN4，CacheA&&VN5，CacheB&&VN2，CacheC&&VN4...，这样的数据，这样如果CacheB挂掉，那么CacheB的下一个可能是A，也可能是C，这样就会分担一部分压力，不出现一个服务瞬时压力变大。
添加虚拟节点的java代码：
import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import org.junit.platform.commons.util.StringUtils;
public class HashingVirtualNode {
    //对应服务器1，2，3
    private static String[] servers = {"192.168.0.1:8080", "192.168.0.2:8080", "192.168.0.3:8080"};
    //存放node数据，一般没有多少服务器，查找比较多，ArrayList比较快
    private static List<String> realNodes = new ArrayList<>();
    //虚拟节点，TreeMap利用红黑树，查找比较快
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
    //设置的5个节点
    private static final int VIRTUAL_NODES = 5;
    static{
        //先把原始的服务器添加到真实结点列表中
        for(int i=0; i<servers.length; i++)
            realNodes.add(servers[i]);
        //添加虚拟节点
        for (String str : realNodes){
            for(int i=0; i<VIRTUAL_NODES; i++){
                String virtualNodeName = str + "&&VN" + String.valueOf(i);
                //注意这是hash的方式在把虚拟机节点放到圆环上
                int hash = getHash(virtualNodeName);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        System.out.println();
    }
    //使用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;
    }
    //得到应当路由到的结点
    private static String getServer(String key){
        //得到该key的hash值
        int hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }
        //virtualNode虚拟节点名称要截取一下，获取真实节点
        if(StringUtils.isNotBlank(virtualNode)){
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        return null;
    }
}
﻿