架构师训练营第五章作业

 关注
发布于: 2020 年 07 月 07 日
1、用你熟悉的语言实现一致性hash算法
2、编写测试用例这个算法，测试100万kv数据，10个服务器节点情况下，计算这些kv数据在服务器上面分布数量的标准差，以评估算法的存储负载不均衡；
﻿
基于虚拟节点的一致性Hash算法﻿
﻿
服务器字符串的hash值放到环上，节点变成虚拟节点；
一个服务分成多个虚拟节点均匀的分布在环上面；
根据算出来的hash值顺时针查找获取最近的虚拟节点；
影响范围是基本所有虚拟节点都会受到影响，但是影响的数据量相对较少；
﻿
Hash代码实现﻿
一致性Hash实现﻿
public class HashNodeHandler {
﻿
    private List<String> nodes;
﻿
    private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
﻿
    private TreeMap<String, Integer> serverVisit = new TreeMap<>();
﻿
    private int nodeNum;
﻿
    public HashNodeHandler(List<String> nodes,Integer nodeNum){
        this.nodes = nodes;
        this.nodeNum = nodeNum;
    }
﻿
    public void calculation(){
        nodes.forEach(s -> {
            serverVisit.put(s, 0);
            for (int i = 0; i < nodeNum; i++) {
                virtualNodes.put(hash(s + "NODE=" + i), s);
            }
        });
﻿
    }
﻿
    public void put(Object object){
        int hash = hash(object);
        SortedMap<Integer, String> integerStringSortedMap = virtualNodes.tailMap(hash);
        String server = "";
        if (integerStringSortedMap.isEmpty()) {
            // 如果没有比reqHash大的值，则返回第一个虚拟服务器节点
            server = virtualNodes.get(virtualNodes.firstKey());
        } else {
            // greaterMap第一个值就是顺时针下离reqHash最近的虚拟服务器节点
            server = integerStringSortedMap.get(integerStringSortedMap.firstKey());
        }
        serverVisit.put(server, serverVisit.get(server) + 1);
    }
﻿
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
﻿
    public double calculationStandard() {
        Integer[] visitData = new Integer[serverVisit.size()];
        serverVisit.values().toArray(visitData);
        double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d);
        double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
        double std = Math.sqrt(avgStd);
        return std;
    }
﻿
    public TreeMap<String, Integer> getServerVisit() {
        return serverVisit;
    }
﻿
}
﻿
﻿
测试类﻿
public class HashTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("192.168.0.1");
        list.add("192.168.0.2");
        list.add("192.168.0.3");
        list.add("192.168.0.4");
        list.add("192.168.0.5");
        list.add("192.168.0.6");
        list.add("192.168.0.7");
        list.add("192.168.0.8");
        list.add("192.168.0.9");
        list.add("192.168.0.10");
        int num = 2000;
        HashNodeHandler hashNodeHandler = new HashNodeHandler(list, num);
        hashNodeHandler.calculation();
        test1000000(hashNodeHandler);
    }
﻿
    private static void test1000000(HashNodeHandler hashNodeHandler) {
        int num = 1000000;
        loop(hashNodeHandler,num);
    }
﻿
    private static void loop(HashNodeHandler hashNodeHandler,int num) {
        for (int i = 0; i < num; i++) {
            hashNodeHandler.put(i+"nodeDa");
        }
        System.out.println(hashNodeHandler.getServerVisit());
        System.out.println(hashNodeHandler.calculationStandard());
﻿
    }
﻿
}
﻿
﻿
验证结果﻿
服务器数量:10
虚拟节点数量:2000
测试数据量:1000000
服务器分配情况：{192.168.0.1=185375, 192.168.0.10=88721, 192.168.0.2=136291, 192.168.0.3=67317, 192.168.0.4=141577, 192.168.0.5=84482, 192.168.0.6=75216, 192.168.0.7=83256, 192.168.0.8=69623, 192.168.0.9=68142}
标准差：38213.9756816796
﻿
服务器数量:11
虚拟节点数量:2200
测试数据量:1000000
服务器分配情况：{192.168.0.1=185375, 192.168.0.10=88721, 192.168.0.11=30946, 192.168.0.2=136291, 192.168.0.3=66028, 192.168.0.4=141577, 192.168.0.5=81289, 192.168.0.6=75216, 192.168.0.7=56792, 192.168.0.8=69623, 192.168.0.9=68142}
标准差：42899.69760532234
﻿
﻿
服务器数量:8
虚拟节点数量:1600
测试数据量:1000000
服务器分配情况：{192.168.0.1=185375, 192.168.0.2=197838, 192.168.0.3=123376, 192.168.0.4=141577, 192.168.0.5=84482, 192.168.0.6=108407, 192.168.0.7=83256, 192.168.0.8=75689}
标准差：43759.45812621541
﻿
发布于: 2020 年 07 月 07 日阅读数: 33
原文链接:【http://xie.infoq.cn/article/c36bf10631bfc9ca1cefd9f06】。文章转载请联系作者。
叮叮董董

 关注
还未添加个人签名 2020.04.08 加入
还未添加个人简介
发布
暂无评论