架构师训练营：第五周作业 - 一致性 hash 实现

关注
发布于: 2020 年 07 月 08 日
作业：手动实现一致性 hash 算法﻿
分布式一致性 hash 算法原理
有一个有序的环型hash表，hash表上记录着 服务器节点的hash值与节点的映射。
为了使服务器的节点均匀的分布在 hash环上， 在hash环上增加了一些服务器的虚拟节点，虚拟节点被访问时指向真实的节点。
当有数据存入时，存在数据的hash值对应最近的下一个节点上。如果是末尾且没有服务器节点则存在第一个服务器节点上。
当有数据访问时，按照存入的逻辑查询服务器节点访问。
当一个服务器从 hash 环删除时，仅该节点记录的数据丢失。后来的数据按照存入逻辑，存入最近节点的服务器上。
当一个新服务器节点插入到 hash 环上时。新节点与上一个服务器节点间的数据会丢失。
﻿
计算在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
编写测试用例测试这个算法，测试 100万KV 数据，10个服务器节点的情况下，计算这些KV数
﻿
实现过程刚开始拿到这个题目时，感觉应该比较难，虽然分布式的一致性哈希算法到处有有讲解，但是却从来没有想过自己手动去编码实现。许多事情听起来觉得听懂了就会了，但是真正动手做的时候却发现不是那么简单，脑子里面连怎么做的步骤都没有个大概。
这次也是训练营作业要求去做，做的时候才发现自己眼高手低。学东西一点也没有把知识落地过。也庆幸这次作业让我认识到自己的缺点。让我明白以后该怎么去学东西。
﻿
一开始自己是没有想法的。不知道怎么去实现。虽然知道大概原理。所以还是看看大佬博客，看到一篇代码很简单的。看完后总结了几个实现分布式一致性算法的要点:
算法设计要点：
﻿
需要一个排序的hash表
找到一个hash算法，计算数据的hash值
hash表访问一个key最近的下一个节点，末尾hash访问hash表的第一个节点，这样就构成hash环。
﻿
使用java语言
排序hash表使用TreeMap ，hash算法在网上搜了一下，找到一个java实现的hash算法大全类。直接拿过来用。
再往后就是编写代码了，直接上代码：
﻿
//一致性hash类。
public class ConsistentHash {
    //构造hash环
    public static ConsistentHashMap build(List serverNode, int virtualNodeCount,HashAlgorithm hashAlgorithm) {
        ConsistentHashMap consistentHash =new ConsistentHashMap(serverNode,virtualNodeCount,hashAlgorithm);
        consistentHash.initNode();
        return consistentHash;
    }
    static class ConsistentHashMap{
        /**
         * 有序hash表
         */
        private TreeMap<Long,String> nodeMap;
        /**
         * 虚拟节点数
         */
        private int virtualNodeCount;
        /**
         * 真实的服务器
         */
        private List<String> serverNode;
        /**
         * 使用的hash算法
         */
        private HashAlgorithm hashAlgorithm;
        private ConsistentHashMap(List serverNode, int virtualNodeCount, HashAlgorithm hashAlgorithm) {
            this.nodeMap = new TreeMap<>();
            this.serverNode=serverNode;
            this.virtualNodeCount=virtualNodeCount;
            this.hashAlgorithm=hashAlgorithm;
        }
        private void initNode() {
            for (String realServer : serverNode) {
                for(int i=0;i<virtualNodeCount; i++){
                    String virtualName = new StringBuilder(realServer).append("#vtal").append(i).toString();
                    nodeMap.put(hash(virtualName), virtualName);
//            System.out.println("虚拟节点 : "+virtualName + "在hash环的 "+ hash(virtualName) +" 上" );
                }
            }
        }
        public String getServerNode(String key) {
            long hash = hash(key);
            //获取hash值对应的节点
            if( nodeMap.get(hash) != null){
                return getRealName(nodeMap.get(hash));
            }
            //获取hash值最近的节点
            if ( nodeMap.higherKey(hash) != null) {
                return getRealName(nodeMap.get(nodeMap.higherKey(hash)));
            }
            //获取首节点
            if( nodeMap.firstEntry() != null){
                return getRealName(nodeMap.firstEntry().getValue());
            }
            return null;
        }
        private String getRealName(String virtualNodeName) {
            return virtualNodeName !=null ? virtualNodeName.substring(0,virtualNodeName.lastIndexOf("#")) : null;
        }
        public void addServerNode(String node) {
            if (serverNode.contains(node)) {
                return ;
            }
            serverNode.add(node);
            for(int i=0;i<virtualNodeCount; i++){
                String virtualName = new StringBuilder(node).append("#vtal").append(i).toString();
                nodeMap.put(hash(virtualName), virtualName);
//            System.out.println("虚拟节点 : "+virtualName + "在hash环的 "+ hash(virtualName) +" 上" );
            }
        }
        public void removeServerNode(String node) {
            if(!serverNode.contains(node)){
                return ;
            }
            serverNode.remove(node);
            for(int i=0;i<virtualNodeCount; i++){
                String virtualName = new StringBuilder(node).append("#vtal").append(i).toString();
                nodeMap.remove(hash(virtualName));
            }
        }
        private long hash(String key) {
            return hashAlgorithm.hash(key);
        }
    }
}
﻿
//算法接口
public interface HashAlgorithm {
    int hash(String key);
}
//算法类网上找的。
//博客地址：https://www.cnblogs.com/lzl2016/p/6648259.html
public class HashAlgorithms {...}
﻿
//测试类
public class TestMain {
    public static void main(String[] args) {
        //测试一百万个key
        int totalKeyCount=100_0000;
        //真实服务器节点数
        int serverCount=10;
        //虚拟节点从每个服务器100个开始
        int startVirtualNodeCount=100;
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::FNVHash1,"FNVHash1");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::APHash,"APHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::ELFHash,"ELFHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::DJBHash,"DJBHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::JSHash,"JSHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::RSHash,"RSHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::SDBMHash,"SDBMHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::bernstein,"bernstein");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::oneByOneHash,"oneByOneHash");
        System.out.println("==============分隔==============");
        testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::java,"java");
        testOneByOneHash();
    }
    //进一步测试了FNH1 和 oneByone算法
    public static void testOneByOneHash() {
        int totalKeyCount=100_0000;
        int serverCount=10;
        int startVirtualNodeCount=200;
        int count=40;
        while(count-->0) {
            test(totalKeyCount, serverCount, startVirtualNodeCount += 20, HashAlgorithms::oneByOneHash, "oneByOneHash");
        }
        System.out.println("==============分隔==============");
        int count1=40;
        startVirtualNodeCount=200;
        while(count1-->0) {
            test(totalKeyCount, serverCount, startVirtualNodeCount += 20, HashAlgorithms::FNVHash1, "FNVHash1");
        }
    }
    //每次加20个虚拟节点，到200个为止
    public static void testFive(int totalKeyCount, int serverCount, int virtualNodeCount,HashAlgorithm hashAlgorithm,String algorrithmName){
        do{
            test( totalKeyCount, serverCount, virtualNodeCount, hashAlgorithm,algorrithmName);
        }while((virtualNodeCount+=20)<=200);
    }
    public static void test(int totalKeyCount, int serverCount, int virtualNodeCount,HashAlgorithm hashAlgorithm,String algorrithmName) {
        List<String> ipList = new ArrayList<>();
        Map<String, Integer> serverHodeCountMap = new HashMap<>(serverCount);
        for (int i = 0; i < serverCount; i++) {
            ipList.add("192.168.10." + i);
            serverHodeCountMap.put("192.168.10." + i, 0);
        }
        ConsistentHash.ConsistentHashMap constMap = ConsistentHash.build(ipList, virtualNodeCount,hashAlgorithm);
        String temp = null;
        for (int j = 0; j < totalKeyCount; j++) {
            temp = "testkey" + j;
            String serverNode = constMap.getServerNode(temp);
//            System.out.println("key : " + temp + " 被放到服务器 " + serverNode + " 中");
            serverHodeCountMap.put(serverNode, serverHodeCountMap.get(serverNode) + 1);
        }
        double sd = calculate(serverHodeCountMap, totalKeyCount);
        System.out.println(serverCount + " 个服务器，每个服务器 " + virtualNodeCount +
                " 个虚拟节点,测试" + totalKeyCount + " 个key " + ",使用 "+algorrithmName+" 算法,标准差为：" + sd);
    }
    //计算标准差
    public static double calculate(Map<String, Integer> serverHoldCountMap ,Integer totalCount) {
        float average = totalCount/1.00f / serverHoldCountMap.size();
        float sumAbs=0f;
        for (String key : serverHoldCountMap.keySet()) {
            float abs = Math.abs(average - serverHoldCountMap.get(key));
            sumAbs=sumAbs+(abs*abs);
        }
        double sd = Math.sqrt(sumAbs/serverHoldCountMap.size());
        return sd;
    }
}
﻿
测试结果
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：7827.245236991109
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：7099.085574917378
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：8407.645568171865
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：10131.300015299123
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：8603.725704600303
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：8979.737635365524
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：67049.62222115796
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：64940.375360787686
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：64940.375360787686
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：64940.375360787686
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：64940.375360787686
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为：64940.375360787686
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267992.5395976537
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267989.17709489685
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267989.17709489685
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267989.17709489685
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267989.17709489685
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为：267989.17709489685
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：267989.48277870903
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：161183.69187979284
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：161183.69187979284
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：161183.69187979284
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：161183.69187979284
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为：161183.69187979284
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：132226.51691699363
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：94827.32298235568
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：94827.32298235568
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：94827.32298235568
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：94827.32298235568
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为：94827.32298235568
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：72489.25680402579
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：60751.637607557546
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：30929.108102239225
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：20667.90826377938
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：14537.00711976162
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为：19730.376174822417
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：61024.46774860064
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：39616.98221722599
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：39577.49016802354
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：39540.59706175414
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：39512.08017809237
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为：39480.806476058715
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.55811084248
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.54486071508
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.54486071508
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.54486071508
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.54486071508
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为：154564.54486071508
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：10297.258275871302
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：9278.562819747463
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：9603.46937309637
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：9576.96820502188
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：8341.963318068474
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：6953.414700706409
==============分隔==============
10 个服务器，每个服务器 100 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：154447.9991712421
10 个服务器，每个服务器 120 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：178426.9784085355
10 个服务器，每个服务器 140 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：178426.9784085355
10 个服务器，每个服务器 160 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：178426.9784085355
10 个服务器，每个服务器 180 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：178426.9784085355
10 个服务器，每个服务器 200 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为：178426.9784085355
==============进一步测试了FNH1 和 oneByone ==============
10 个服务器，每个服务器 220 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：6647.218365602262
10 个服务器，每个服务器 240 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：7060.639631081592
10 个服务器，每个服务器 260 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：5204.911910878031
10 个服务器，每个服务器 280 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4229.263765716203
10 个服务器，每个服务器 300 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3894.359639273189
10 个服务器，每个服务器 320 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3409.753803429215
10 个服务器，每个服务器 340 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4094.8197762538953
10 个服务器，每个服务器 360 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3763.944340714937
10 个服务器，每个服务器 380 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4245.543074802092
10 个服务器，每个服务器 400 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4066.4906246049554
10 个服务器，每个服务器 420 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4226.439163172706
10 个服务器，每个服务器 440 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3895.0177149789706
10 个服务器，每个服务器 460 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4233.9409537687225
10 个服务器，每个服务器 480 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4194.46015596763
10 个服务器，每个服务器 500 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4034.7909487357583
10 个服务器，每个服务器 520 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4361.705400413925
10 个服务器，每个服务器 540 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4174.968742397959
10 个服务器，每个服务器 560 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：4165.408023231337
10 个服务器，每个服务器 580 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3415.390753632738
10 个服务器，每个服务器 600 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3191.8088915221724
10 个服务器，每个服务器 620 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3004.5019553995967
10 个服务器，每个服务器 640 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：3099.8590290527727
10 个服务器，每个服务器 660 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2468.2902989721447
10 个服务器，每个服务器 680 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2067.7751328420604
10 个服务器，每个服务器 700 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2090.249985049635
10 个服务器，每个服务器 720 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2188.9753310624587
10 个服务器，每个服务器 740 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2185.621879465888
10 个服务器，每个服务器 760 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2255.019068655518
10 个服务器，每个服务器 780 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2505.3752213989824
10 个服务器，每个服务器 800 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2176.6651097493154
10 个服务器，每个服务器 820 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2488.7052858866195
10 个服务器，每个服务器 840 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2389.849053810721
10 个服务器，每个服务器 860 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：1843.2668689042289
10 个服务器，每个服务器 880 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2037.948171568649
10 个服务器，每个服务器 900 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2015.8584399704262
10 个服务器，每个服务器 920 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：1838.2526349770317
10 个服务器，每个服务器 940 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2099.445045720416
10 个服务器，每个服务器 960 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2201.576480615652
10 个服务器，每个服务器 980 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2115.3256250516138
10 个服务器，每个服务器 1000 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为：2331.829539224512
==============分隔==============
10 个服务器，每个服务器 220 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：7181.890001942385
10 个服务器，每个服务器 240 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：6296.052096353715
10 个服务器，每个服务器 260 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4785.64582893469
10 个服务器，每个服务器 280 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：5079.123152671138
10 个服务器，每个服务器 300 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4880.028893357087
10 个服务器，每个服务器 320 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4342.532671149406
10 个服务器，每个服务器 340 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4346.437391703693
10 个服务器，每个服务器 360 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4876.869487693924
10 个服务器，每个服务器 380 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4011.071427935434
10 个服务器，每个服务器 400 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3739.066594753295
10 个服务器，每个服务器 420 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3656.793130599542
10 个服务器，每个服务器 440 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3536.7230595566853
10 个服务器，每个服务器 460 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2912.687762188045
10 个服务器，每个服务器 480 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3105.5063999290037
10 个服务器，每个服务器 500 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3463.148278662062
10 个服务器，每个服务器 520 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2970.870747777493
10 个服务器，每个服务器 540 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3166.0535371342035
10 个服务器，每个服务器 560 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3915.715004951203
10 个服务器，每个服务器 580 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3311.018725407635
10 个服务器，每个服务器 600 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4274.6148364501805
10 个服务器，每个服务器 620 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4227.956007339717
10 个服务器，每个服务器 640 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4031.2467054250105
10 个服务器，每个服务器 660 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3488.077980779673
10 个服务器，每个服务器 680 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3719.4554708989326
10 个服务器，每个服务器 700 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：4043.8486618566726
10 个服务器，每个服务器 720 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3885.8138143765973
10 个服务器，每个服务器 740 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3534.083473830238
10 个服务器，每个服务器 760 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3637.8468906758567
10 个服务器，每个服务器 780 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3217.7350729977757
10 个服务器，每个服务器 800 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3137.4983665334394
10 个服务器，每个服务器 820 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3145.792427990124
10 个服务器，每个服务器 840 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3384.599533179664
10 个服务器，每个服务器 860 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3044.0
10 个服务器，每个服务器 880 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2831.604315578008
10 个服务器，每个服务器 900 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2585.5683127699413
10 个服务器，每个服务器 920 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2366.119925109461
10 个服务器，每个服务器 940 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2438.5143017829523
10 个服务器，每个服务器 960 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：2979.574466261919
10 个服务器，每个服务器 980 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3264.744094105999
10 个服务器，每个服务器 1000 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为：3468.0595438948276
﻿
﻿
从测试结果总结：
hash选择非常重要，有的hash算法标准差为几万，而且也不随虚拟节点增加变化。有可能这些算法设计的目的是解决hash冲突的，不是注重均匀散列分布的。或者是我使用的方式不对。
FNV1Hash 算法 和 oneByone 算法表现突出，进一步测试发现 oneByone 方差更小。在不考虑算法的执行效率前提下 oneByone算法是很好的选择。
﻿
发布于: 2020 年 07 月 08 日阅读数: 113
zcj

关注
还未添加个人签名 2019.10.12 加入
精神小伙
发布
暂无评论
创作场景

架构师训练营：第五周作业 - 一致性 hash 实现

作业：手动实现一致性 hash 算法

实现过程

zcj

评论
