极客时间架构师培训 1 期 - 第 5 周作业

/** * CacheNode.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
/** * <p> * ClassName: CacheNode * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class CacheNode {
    private String name; // 节点Name
    private String ip; // 节点IP
    private String port; // 端口
    private Long numCache; // Cache存储数量
    public CacheNode(String strName, String strIp, String StrPort) {        name = strName;        ip = strIp;        port = StrPort;        numCache = 0L;    }
    public void addNumCache(){        numCache++;        return;    }

    public Long getNumCache(){        return numCache;    }
    public String getNodeCacheKey() {        return this.name + "-" + this.ip + "-" + this.port;    }
    @Override    public String toString() {        return "CacheNode{" +                "name='" + name + '\'' +                ", ip='" + ip + '\'' +                ", port='" + port + '\'' +                ", numCache=" + numCache +                '}';    }}

/** * HashUtils.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.io.UnsupportedEncodingException;import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;
/** * <p> * ClassName: HashUtils * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class HashUtils {    public static Long hash(String nodeName, int number) {        byte[] digest = md5(nodeName);        return (((long) (digest[3 + number * 4] & 0xFF) << 24)                | ((long) (digest[2 + number * 4] & 0xFF) << 16)                | ((long) (digest[1 + number * 4] & 0xFF) << 8)                | (digest[number * 4] & 0xFF))                & 0xFFFFFFFFL;    }
    /**     * md5加密     *     * @param str     * @return     */    public static byte[] md5(String str) {        try {            MessageDigest md = MessageDigest.getInstance("MD5");            md.reset();            md.update(str.getBytes("UTF-8"));            return md.digest();        } catch (NoSuchAlgorithmException e) {            e.printStackTrace();            return null;        } catch (UnsupportedEncodingException e) {            e.printStackTrace();            return null;        }    }

    public static double standardDeviation(Long[] x) {        int m = x.length;        double sum = 0;        for (int i = 0; i < m; i++) {// 求和            sum += x[i];        }        double dAve = sum / m;// 求平均值        double dVar = 0;        for (int i = 0; i < m; i++) {// 求方差            dVar += (x[i] - dAve)* (x[i] - dAve);        }        return Math.sqrt(dVar / m);    }}

/** * ConsistentHashLoadBalance.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.io.UnsupportedEncodingException;import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;import java.util.LinkedList;import java.util.Map;import java.util.TreeMap;
/** * <p> * ClassName: ConsistentHashLoadBalance * </p> * <p> * Description: Hash算法 * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class ConsistentHashLoadBalance {
    //虚拟节点    private TreeMap<Long, CacheNode> virtualNodes = new TreeMap<>();
    //真实节点    private LinkedList<CacheNode> nodes;
    //每个真实节点对应的虚拟节点数    private final int replicCnt;
    public ConsistentHashLoadBalance(LinkedList<CacheNode> nodes, int replicCnt){        this.nodes = nodes;        this.replicCnt = replicCnt;        initalization();    }
    /**     * 初始化哈希环     * 循环计算每个node名称的哈希值，将其放入treeMap     */    private void initalization(){        for (CacheNode node: nodes) {            for (int i = 0; i < replicCnt/4; i++) {                String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i);                for (int j = 0; j < 4; j++) {                    virtualNodes.put(HashUtils.hash(virtualNodeName, j), node);                }            }        }    }
    private String getNodeNameByIndex(String nodeName, int index){        return new StringBuffer(nodeName)                .append("&&")                .append(index)                .toString();    }    /**     * 根据资源key选择返回相应的节点名称     * @param key     * @return 节点名称     */    public CacheNode selectNode(String key){        Long hashOfKey = HashUtils.hash(key, 0);        if (!virtualNodes.containsKey(hashOfKey)) {            Map.Entry<Long, CacheNode> entry = virtualNodes.ceilingEntry(hashOfKey);            if (entry != null) {                return entry.getValue();            } else {                return nodes.getFirst();            }        } else {            return virtualNodes.get(hashOfKey);        }    }
    public void addNode(CacheNode node){        nodes.add(node);        for (int i = 0; i < replicCnt/4; i++) {            String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i);            for (int j = 0; j < 4; j++) {                virtualNodes.put(HashUtils.hash(virtualNodeName, j), node);            }        }    }
    public void removeNode(CacheNode node){        nodes.remove(node);        for (int i = 0; i < replicCnt/4; i++) {            String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i);            for (int j = 0; j < 4; j++) {                virtualNodes.remove(HashUtils.hash(virtualNodeName, j), node);            }        }    }
    public void printTreeNode(){        if (virtualNodes != null && ! virtualNodes.isEmpty()){            virtualNodes.forEach((hashKey, node) ->                    System.out.println(                            new StringBuffer(node.toString())                                    .append(" ==> ")                                    .append(hashKey)                    )            );        } else {            System.out.println("Cycle is Empty");        }
    }

}

/** * ConsistentHashLoadBalanceMain.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.util.HashMap;import java.util.LinkedList;
/** * <p> * ClassName: ConsistentHashLoadBalanceMain * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class ConsistentHashLoadBalanceMain {    public static void main(String[] args){        LinkedList<CacheNode> nodes = new LinkedList<>();        nodes.add(new CacheNode("node1", "192.168.13.1", "8080"));        nodes.add(new CacheNode("node1", "192.168.13.2", "8080"));        nodes.add(new CacheNode("node1", "192.168.13.3", "8080"));        nodes.add(new CacheNode("node1", "192.168.13.4", "8080"));
        ConsistentHashLoadBalance consistentHash = new ConsistentHashLoadBalance(nodes, 150);        System.out.print("初始化后缓存信息：");        consistentHash.printTreeNode();        long startTime=System.currentTimeMillis();        //100W数据加入测试        for (int n = 0; n < 1000000; n++) {
            String key = String.format("%f", Math.random());//  key 选择            CacheNode keyHash = consistentHash.selectNode(key);            //找到加++            keyHash.addNumCache();        }        System.out.print("测试数据入缓存后信息：");        consistentHash.printTreeNode();        long endTime=System.currentTimeMillis();        double std = 0;        double avg =100000;        Long[] ccArray = new Long[nodes.size()];        for (int i = 0; i < nodes.size(); i++) {            CacheNode node = nodes.get(i);            ccArray[i] = node.getNumCache();            //System.out.println(" 节点：" + i +"  缓存个数： " + (node.GetNumCache()) );        }
        System.out.println(" 节点个数：" + nodes.size() +"  100万次查找算法程序运行时间： " + (endTime - startTime ) + "ms" +" 标准差：" + HashUtils.standardDeviation(ccArray));
    }
}