成为作者

架构师培训 -05 缓存、消息和负载均衡

用户头像
刘敏
发布于: 2020 年 07 月 08 日

1.用代码实现一致性hash

作业题如下：

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

答：

通过测试代码跑下来，虚拟节点数和实际物理机器节点数越多标准差就越小，意味着也就越均匀一些。因此在物理机器几点数一定的情况下，为了使数据分布的更加均匀可以增加虚拟节点的数量。

150个虚拟节点运行结果：

"C:\Program Files\Java\jdk1.8.0_171\bin\java.exe" "-javaagent:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\lib\idea_rt.jar=64814:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_171\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\rt.jar;F:\arctrainingwp\ArcTraningCode\ConsisitencyHash\target\classes" com.lm.TestConsisitencyHash
当前节点数：10
192.168.1.107  : 100859
192.168.1.108  : 73776
192.168.1.109  : 93854
192.168.1.103  : 79809
192.168.1.104  : 102059
192.168.1.105  : 107971
192.168.1.106  : 46852
192.168.1.100  : 161547
192.168.1.101  : 67054
192.168.1.102  : 166219
标准差 ： 14654.29507004687
cost time : 651ms
 
增加五机器：192.168.1.110~192.168.1.114
当前节点数：15
192.168.1.107  : 71577
192.168.1.108  : 44549
192.168.1.109  : 53460
192.168.1.103  : 59504
192.168.1.114  : 69621
192.168.1.104  : 62496
192.168.1.105  : 80322
192.168.1.106  : 39764
192.168.1.110  : 89252
192.168.1.100  : 100197
192.168.1.111  : 101838
192.168.1.101  : 39152
192.168.1.112  : 67212
192.168.1.102  : 84686
192.168.1.113  : 36370
标准差 ： 11965.1818205993
cost time : 538ms
 
宕机2台：192.168.1.102,192.168.1.112
当前节点数：13
192.168.1.107  : 71974
192.168.1.108  : 124480
192.168.1.109  : 56890
192.168.1.103  : 75155
192.168.1.114  : 74784
192.168.1.104  : 71145
192.168.1.105  : 82248
192.168.1.106  : 46416
192.168.1.110  : 103847
192.168.1.100  : 105683
192.168.1.111  : 107291
192.168.1.101  : 40073
192.168.1.113  : 40014
标准差 ： 12852.666999498586
cost time : 260ms
 
Process finished with exit code 0

300个虚拟节点运行结果：

"C:\Program Files\Java\jdk1.8.0_171\bin\java.exe" "-javaagent:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\lib\idea_rt.jar=64907:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_171\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\rt.jar;F:\arctrainingwp\ArcTraningCode\ConsisitencyHash\target\classes" com.lm.TestConsisitencyHash
当前节点数：10
192.168.1.107  : 96734
192.168.1.108  : 119056
192.168.1.109  : 103420
192.168.1.103  : 103040
192.168.1.104  : 111921
192.168.1.105  : 81119
192.168.1.106  : 101298
192.168.1.100  : 97297
192.168.1.101  : 87186
192.168.1.102  : 98929
标准差 ： 10332.835719201192
cost time : 665ms
 
增加五机器：192.168.1.110~192.168.1.114
当前节点数：15
192.168.1.107  : 63658
192.168.1.108  : 74068
192.168.1.109  : 71250
192.168.1.103  : 54710
192.168.1.114  : 77158
192.168.1.104  : 72785
192.168.1.105  : 47065
192.168.1.106  : 60783
192.168.1.110  : 70745
192.168.1.100  : 57167
192.168.1.111  : 85572
192.168.1.101  : 56571
192.168.1.112  : 73190
192.168.1.113  : 73591
192.168.1.102  : 61687
标准差 ： 9918.51304379845
cost time : 457ms
 
宕机2台：192.168.1.102,192.168.1.112
当前节点数：13
192.168.1.107  : 74394
192.168.1.108  : 89825
192.168.1.109  : 73495
192.168.1.103  : 62275
192.168.1.114  : 89199
192.168.1.104  : 76838
192.168.1.105  : 63574
192.168.1.106  : 75256
192.168.1.110  : 82873
192.168.1.100  : 73179
192.168.1.111  : 87903
192.168.1.101  : 64670
192.168.1.113  : 86519
标准差 ： 9376.953236526244
cost time : 322ms
 
Process finished with exit code 0

一致性hash

package com.lm;
import java.util.*;
/**
 * @author lm
 * @description 一致性hash
 * @date 2020/7/8 14:54
 */
public class ConsisitencyHash {
    private final static Integer VIRTUAL_NUM = 150;
    static SortedMap<Integer, String> virtualNodeMap = new TreeMap<Integer, String>();
    static List<String> relServers;
    public static void init(List<String> relServers) {
        ConsisitencyHash.relServers = relServers;
        List<Integer> virtualNodeList = new ArrayList<Integer>();
        //初始化150个虚拟节点
        for (int i = 0; i < VIRTUAL_NUM; i++) {
            String key = UUID.randomUUID().toString();
            Integer hash = hash(key);
            virtualNodeList.add(hash);
        }
        //将虚拟节点分配给实体节点
        assignVirtualNode(virtualNodeList, relServers);
    }
    /**
     * 路由到具体的节点
     *
     * @param key
     * @return
     */
    public static String router(String key) {
        int hash = hash(key);
        SortedMap<Integer, String> subMap = virtualNodeMap.tailMap(hash);
        Integer firstKey = null;
        if (subMap.isEmpty()) {
            firstKey = virtualNodeMap.firstKey();
        }  else {
            firstKey = subMap.firstKey();
        }
        return virtualNodeMap.get(firstKey);
    }
    /**
     *移出服务器
     * @param servers
     */
    public static void removeServers(List<String> servers) {
        List<Integer> removeHashs = new ArrayList<Integer>();
        for (SortedMap.Entry<Integer, String> virtualNode : virtualNodeMap.entrySet()) {
            if (servers.contains(virtualNode.getValue())) {
                removeHashs.add(virtualNode.getKey());
            }
        }
        if (removeHashs.size() == 0) {
            return;
        }
        //删除拿出来的key
        for(Integer key : removeHashs) {
            virtualNodeMap.remove(key);
        }
        for (String server : servers) {
            relServers.remove(server);
        }
        assignVirtualNode(removeHashs, relServers);
    }
    /**
     * 添加服务器
     * @param servers
     */
    public static synchronized void addServers(List<String> servers) {
        int relNodeNum = relServers.size() + servers.size();
        int virtualNum = virtualNodeMap.size();
        int preAssignableNodeNum = virtualNum / relNodeNum;
        int newServerWaitAssignNum = preAssignableNodeNum * servers.size();
        int waitGetVirtualNodeNum = newServerWaitAssignNum / relServers.size();
        Set<Map.Entry<Integer, String>> set = virtualNodeMap.entrySet();
        List<Integer> waitAssignVirtualNode = new ArrayList<Integer>();
        for (String relServer : relServers) {
            for (SortedMap.Entry<Integer, String> entry : set) {
                if(relServer.equals(entry.getValue())) {
                    waitAssignVirtualNode.add(entry.getKey());
                    if (waitAssignVirtualNode.size() % waitGetVirtualNodeNum == 0) {
                        break;
                    }
                }
            }
        }
        //将新增节点加入到节点列表中
        relServers.addAll(servers);
        //将拿出来的节点分配给新加入的节点
        assignVirtualNode(waitAssignVirtualNode, servers);
    }
    private static void assignVirtualNode(List<Integer> waitAssignVirtualNodes, List<String> assignableRelNode) {
        int virtualNum = waitAssignVirtualNodes.size();
        int relNodeNum = assignableRelNode.size();
        int assignableNodeNum = virtualNum / relNodeNum;
        for (int i = 0; i < virtualNum; i++) {
            int relNodeIndx = i / assignableNodeNum;
            if (relNodeIndx >= relNodeNum) {
                relNodeIndx = virtualNum % relNodeNum;
            }
            virtualNodeMap.put(waitAssignVirtualNodes.get(i), assignableRelNode.get(relNodeIndx));
        }
    }
    private static int hash(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;
    }
}

测试代码

package com.lm;
import java.util.*;
/**
 * @author lm
 * @description 测试一致性hash
 * @date 2020/7/8 16:35
 */
public class TestConsisitencyHash {
    private final static Integer DATA_SIZE = 1000000;
    public static void main(String[] args) {
        List<String> relServers = getServers();
        List<String> dataList = generateData();
        ConsisitencyHash.init(relServers);
        test(dataList);
        System.out.println("增加五机器：192.168.1.110~192.168.1.114" );
        List<String> addServers = new ArrayList<String>();
        addServers.add("192.168.1.110");
        addServers.add("192.168.1.111");
        addServers.add("192.168.1.112");
        addServers.add("192.168.1.113");
        addServers.add("192.168.1.114");
        ConsisitencyHash.addServers(addServers);
        test(dataList);
        System.out.println("宕机2台：192.168.1.102,192.168.1.112" );
        List<String> removeServers = new ArrayList<String>();
        removeServers.add("192.168.1.102");
        removeServers.add("192.168.1.112");
        ConsisitencyHash.removeServers(removeServers);
        test(dataList);
    }
    private static void test(List<String> dataList) {
        long startTime = System.currentTimeMillis();
        System.out.println("当前节点数："+ ConsisitencyHash.relServers.size() );
        Map<String, Integer> vistNumMap = new HashMap<String, Integer>(ConsisitencyHash.relServers.size());
        for (String key : dataList) {
            String server = ConsisitencyHash.router(key);
            Integer vistNum = vistNumMap.get(server);
            if (vistNum == null) {
                vistNum = 0;
            }
            vistNumMap.put(server, vistNum + 1);
        }
        for (Map.Entry<String, Integer> entry : vistNumMap.entrySet()) {
            System.out.println(entry.getKey() + "  : " + entry.getValue());
        }
        double standardDeviation = standardDiviation( vistNumMap);
        System.out.println("标准差 ： " +standardDeviation);
        long endTime = System.currentTimeMillis();
        System.out.println("cost time : " + (endTime - startTime));
        System.out.println(" " );
    }
    public static List<String> getServers() {
        List<String> relServers = new LinkedList<String>();
        relServers.add("192.168.1.100");
        relServers.add("192.168.1.101");
        relServers.add("192.168.1.102");
        relServers.add("192.168.1.103");
        relServers.add("192.168.1.104");
        relServers.add("192.168.1.105");
        relServers.add("192.168.1.106");
        relServers.add("192.168.1.107");
        relServers.add("192.168.1.108");
        relServers.add("192.168.1.109");
        return relServers;
    }
    public static List<String> generateData() {
        List<String> dataList = new ArrayList<String>(DATA_SIZE);
        for (int i = 0; i < DATA_SIZE; i++) {
            dataList.add(UUID.randomUUID().toString());
        }
        return dataList;
    }
    public static double standardDiviation(Map<String,Integer> vistNumMap) {
        int size = vistNumMap.size();
        long  sum = 0;
        for(Map.Entry<String,Integer> entry :vistNumMap.entrySet()) {
            sum += entry.getValue();
        }
        double average = sum / size;
        int total = 0;
        for(Map.Entry<String,Integer> entry :vistNumMap.entrySet()) {
            total += (entry.getValue() - average) * (entry.getValue()- average);
        }
        double standardDeviation = Math.sqrt(total /size);
        return standardDeviation;
    }
}

发布于: 2020 年 07 月 08 日 阅读数: 7
用户头像

刘敏

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2020, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 |  京 ICP 备 16027448 号 - 5 京公网安备 京公网安备 11010502039052号
架构师培训 -05 缓存、消息和负载均衡