架构师训练营 -week5 命题作业

package jiketime_homework.week05;
import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * @Author jeffSmile
 * @Date 下午 5:22 2020/7/4 0004
 * @Description //TODO
 * 用你熟悉的编程语言实现一致性 hash 算法。
 **/
public class ConsistentHashingWithVirtualNode {
    /**
     * 待添加入Hash环的服务器列表
     */
    private static String[] servers = {"192.168.0.0:11211", "192.168.0.1:11211", "192.168.0.2:11211","192.168.0.3:11211", "192.168.0.4:11211",
            "192.168.0.5:11211", "192.168.0.6:11211", "192.168.0.7:11211","192.168.0.8:11211", "192.168.0.9:11211"};
    /**
     * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
     */
    private static List<String> realNodes = new LinkedList<String>();
    /**
     * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
     */
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
    /**
     * 虚拟节点的数目，一个真实结点对应5个虚拟节点
     */
    private static  int VIRTUAL_NODES = 5;
    public ConsistentHashingWithVirtualNode(){
        this(VIRTUAL_NODES,  servers);
    }
    public ConsistentHashingWithVirtualNode(int virNodes, String[] servers){
        this.servers=servers;
        this.VIRTUAL_NODES = virNodes;
        initHashCircle();
    }
    public void initHashCircle() {
        System.out.println("构造hash环==========开始=============");
        // 先把原始的服务器添加到真实结点列表中
        for (int i = 0; i < servers.length; i++)
            realNodes.add(servers[i]);
        // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes)
        {
            for (int i = 0; i < VIRTUAL_NODES; i++)
            {
                String virtualNodeName = str + "&&MEMCACHED_" + String.valueOf(i);
                int hash = getHash(virtualNodeName);
//                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        System.out.println("构造hash环==========完毕=============");
    }
    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值
     */
    public 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 String getServer(String node) {
        // 得到带路由的结点的Hash值
        int hash = getHash(node);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        Integer i = 0;
        String virtualNode = null;
        if(!subMap.isEmpty()){
            // 第一个Key就是顺时针过去离node最近的那个结点
            i = subMap.firstKey();
            // 返回对应的虚拟节点名称
            virtualNode = subMap.get(i);
        }else{
            i = virtualNodes.firstKey();
            virtualNode = virtualNodes.get(i);
        }
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }
    public static void main(String[] args)
    {
        ConsistentHashingWithVirtualNode consistentHash = new ConsistentHashingWithVirtualNode();
//        String[] nodes = {"127.0.0.1", "47.107.125.20", "172.18.75.44"};
//        for (int i = 0; i < nodes.length; i++)
//            System.out.println("[" + nodes[i] + "]的hash值为" + consistentHash.getHash(nodes[i]) + ", 被路由到结点[" + consistentHash.getServer(nodes[i]) + "]");
        System.out.println(consistentHash.getServer("77"));
    }
}

package jiketime_homework.week05;
import java.util.List;
public class StandardDeviaction {
    //计算和
    public static double calcSum(List<Integer> list){
        double sum = 0;
        for(int i = 0;i<list.size();i++){
            sum += list.get(i);
        }
        return sum;
    }
    
    //求平均值
    public static double mean(List<Integer> list){
        return calcSum(list) / list.size();
    }
    
    //求标准差
    public static double standardDeviaction(List<Integer> list){
        double sum = 0;
        double meanValue = mean(list);                //平均数
        for(int i = 0;i < list.size();i++){
            sum += Math.pow(list.get(i)-meanValue, 2);
        }
        return Math.sqrt(sum/list.size());
    }
}

package jiketime_homework.week05;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
 * @author jeffSmile
 * @date 2020-07-04 下午 5:37
 * @desc 编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
 */
public class TestConsistentHash {
    /**
     * @Author jeffSmile
     * @Date 下午 5:38 2020/7/4 0004
     * @Description 将100万数据计算hash，并计算hash环上服务器10个节点各自被命中的总数
     **/
    public static Map<String,Integer> loadCache(ConsistentHashingWithVirtualNode consistentHash){
        Map<String,Integer> blanceMap = new HashMap<>();
        for (int i = 0; i < 1000000; i++) {
            String server = consistentHash.getServer(String.valueOf(i));
            if(blanceMap.get(server)==null){
                blanceMap.put(server,1);
            }else{
                blanceMap.put(server, blanceMap.get(server)+1);
            }
        }
        return blanceMap;
    }
    public static void main(String[] args) {
        ConsistentHashingWithVirtualNode consistentHash = new ConsistentHashingWithVirtualNode();
        Map<String,Integer> blanceMap = loadCache(consistentHash);
        List<Integer> blanceList = new ArrayList<>();
        for (String key : blanceMap.keySet()) {
            System.out.println(key+"节点上存储数据量："+blanceMap.get(key));
            blanceList.add(blanceMap.get(key));
        }
        double standardDeviaction =  StandardDeviaction.standardDeviaction(blanceList);
        System.out.println("标准差为："+standardDeviaction);
    }
}