「分布式专题」一致性Hash算法的实现Java_python

上文主要介绍了一致性hash算法的由来以及概念知识。本文主要对其进行实现及演示。

「分布式专题」分布式系统中一致性hash算法_国涛i的博客-CSDN博客_分布式一致性hash算法近年来B2C、O2O等商业概念的提出和移动端的发展，使得分布式系统流行了起来。分布式系统相对于单系统，解决了流量大、系统高可用和高容错等问题。功能强大也意味着实现起来需要更多技术的支持。例如系统访问层的负载均衡，缓存层的多实例主从复制备份，数据层的分库分表等我们以负载均衡为例，常见的负载均衡方法有很多，但是它们的优缺点也都很明显：随机访问策略。系统随机访问，缺点：可能造成服务器负载压力不均衡，俗话讲就是撑的撑死，饿的饿死。轮询策略。请求均匀分配，如果服务器有性能差异，则无法...https://blog.csdn.net/weixin_44912855/article/details/122250832

代码如下

/**
 * 不带虚拟节点的一致性Hash算法
 * 重点：1.如何造一个hash环，2.如何在哈希环上映射服务器节点，3.如何找到对应的节点
 */
public class ConsistencyHash {

    // 当前服务器地址（唯一标识）
    private static final 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", "192.168.0.5:111"};

    //key表示服务器的hash值，value表示服务器  
    private static final SortedMap sortedMap = new TreeMap();

    //程序初始化，将所有的服务器放入sortedMap中  
    static {
        for (String server : servers) {
            int hash = getHash(server);
            sortedMap.put(hash, server);
        }
    }

    // 得到应当路由到的结点  
    private static String getServer(String key) {
        // 得到该key的hash值  
        int hash = getHash(key);
        // 得到大于该Hash值的所有Map  
        SortedMap subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            // 如果没有比该key的hash值大的，则从第一个node开始  
            Integer i = sortedMap.firstKey();
            // 返回对应的服务器  
            return sortedMap.get(i);
        }
        // 第一个Key就是顺时针过去离node最近的那个结点
        Integer i = subMap.firstKey();
        //返回对应的服务器
        return subMap.get(i);
    }

    // 使用FNV1_32_HASH算法计算服务器的Hash值
    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;
    }

    public static void main(String[] args) {
        String server = getServer("小王");
        System.out.println(server);
    }
}

如上段代码，当前mysql一共有6台机器。小王访问服务器

如果此时3这台机器挂了，传统的hash取模的形式，小王的请求还是会转发到3这台机器上。导致不可用

而一致性hash算法实现

还记不记得上篇文章提到的数据倾斜问题。为了解决这一问题，一致性hash算法引入了虚拟节点概念。

带虚拟节点的实现

/**
 * 带虚拟节点的一致性Hash算法
 */
public class ConsistentHashingWithoutVirtualNode {

    static 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",
            "192.168.0.6:111",
            "192.168.0.7:111",
            "192.168.0.8:111",
            "192.168.0.9:111",
            "192.168.0.10:111",
            "192.168.0.11:111",
            "192.168.0.12:111",
            "192.168.0.13:111",
            "192.168.0.15:111",
            "192.168.0.16:111",
            "192.168.0.17:111",
            "192.168.0.18:111",
            "192.168.0.19:111",
            "192.168.0.20:111",
            "192.168.0.21:111",
            "192.168.0.22:111",
            "192.168.0.23:111",
            "192.168.0.5:111"};
    //真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
    private static final List realNodes = new LinkedList();

    //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    private static final SortedMap virtualNodes = new TreeMap();

    //虚拟节点的数目，这里写死
    private static final int VIRTUAL_NODES = 32;

    static {
        //先把原始的服务器添加到真实结点列表中
        realNodes.addAll(Arrays.asList(servers));

        //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                String virtualNodeName = str + "&&VN" + String.valueOf(i);
                int hash = getHash(virtualNodeName);
                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                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 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;
    }

    public static void main(String[] args) {
        String server = getServer("小王");
        System.out.println(server);
    }
}