关于一致性 Hash 算法的测试

关注

发布于: 2020 年 11 月 22 日

关于一致性 Hash 算法的测试,主要验证算法负载不均的代码测试.

先看结果:模拟测试 100wPV 落地分布情况

[192.168.0.0:111]加入集合中, 其Hash值为575774686
[192.168.0.1:111]加入集合中, 其Hash值为8518713
[192.168.0.2:111]加入集合中, 其Hash值为1361847097
[192.168.0.3:111]加入集合中, 其Hash值为1171828661
[192.168.0.4:111]加入集合中, 其Hash值为1764547046
[192.168.0.5:111]加入集合中, 其Hash值为1943673564
[192.168.0.6:111]加入集合中, 其Hash值为626760931
[192.168.0.7:111]加入集合中, 其Hash值为597804546
[192.168.0.8:111]加入集合中, 其Hash值为1738780525
[192.168.0.9:111]加入集合中, 其Hash值为1460877425
路由结点:[192.168.0.2:111], 根据hash算法分配到数量88094
路由结点:[192.168.0.8:111], 根据hash算法分配到数量129998
路由结点:[192.168.0.7:111], 根据hash算法分配到数量10281
路由结点:[192.168.0.6:111], 根据hash算法分配到数量13428
路由结点:[192.168.0.1:111], 根据hash算法分配到数量98397
路由结点:[192.168.0.4:111], 根据hash算法分配到数量11841
路由结点:[192.168.0.3:111], 根据hash算法分配到数量255224
路由结点:[192.168.0.5:111], 根据hash算法分配到数量83417
路由结点:[192.168.0.0:111], 根据hash算法分配到数量263709
路由结点:[192.168.0.9:111], 根据hash算法分配到数量45611

复制代码

从结果来看分布不同的节点上最大相差 10 倍左右;

使用一致性 Hash 算法，增强了系统的伸缩性，但是有可能导致负载分布不均匀，解决办法就是使用虚拟节点代替真实节点.

一致性 Hash 算法测试负载分布代码:

package com.jr.service.planokr;
import java.util.HashMap;import java.util.Map;import java.util.SortedMap;import java.util.TreeMap;
/** * 不带虚拟节点的一致性Hash算法 * @author zb 2020/11/20 * */public class Architect {
        /**         * 待添加入Hash环的服务器列表  共10个         */        private 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.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111"};
        /**         * key表示服务器的hash值，value表示服务器的名称         */        private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
        private static HashMap<String,Integer> haspMap = new HashMap<String,Integer>();
        /**         * 程序初始化，将所有的服务器放入hashmap中         */        static        {            for (int i = 0; i < servers.length; i++)            {                int hash = getHash(servers[i]);                System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);                sortedMap.put(hash, servers[i]);                haspMap.put(servers[i],0);            }            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 node)        {            // 获取带路由的结点的Hash值            int hash = getHash(node);            // 获取大于该Hash值的所有Map            SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);            if(subMap.isEmpty()){                //如果没有比该key的hash值大的，则从第一个node开始                Integer i = sortedMap.firstKey();                //返回对应的服务器                return sortedMap.get(i);            }else{                // 第一个Key就是顺时针过去离node最近的那个结点                Integer i = subMap.firstKey();                // 返回对应的服务器名称                return subMap.get(i);            }        }
        public static void main(String[] args) {            String ser = "192.168.129.120:";            String node = "";            int count = 0;            for (int i = 0; i < 1000000; i++) {
                node = getServer(ser + String.valueOf(i) );
//                System.out.println("[" + ser + i + "]的hash值为" +getHash(ser+i ) + ", 被路由到结点[" + node + "]");
                if (haspMap.containsKey(node)) {
                    count = haspMap.get(node);
                    haspMap.put(node, count+1);
                } else {                    System.out.println("[" + ser + i + "]的hash值为, 没有找到路由结点");                }

                /*if(i > 0 && i%100000 == 0){                    printHaspMapLog(i);                }*/            }            printHaspMapLog();

        }

    private static void printHaspMapLog() {//        System.out.println("请求总数量："+i);        for (Map.Entry<String, Integer> entry : haspMap.entrySet()) {            System.out.println("路由结点:["+ entry.getKey() +"], 根据hash算法分配到数量"+entry.getValue());
        }    }
}