架构师训练营作业 (第五周)

package com.hash;

/**
 * hash 算法
 * @create 2020-07-08 20:43
 */
public class CustomHashUtil {
    public static int hashCode(String key) {

        final int p = 16776619;
        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;
        hash = Math.abs(hash);
        return hash;
    }
}


package com.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @create 2020-07-08 21:00
 */
public class Node {

    private String domain;
    private int count = 0;
    private Map<String, Object> data = new HashMap();

    public Node(String domain) {
        this.domain= domain;
    }
    public <T> void put(String key,String value) {
        data.put(key,value);
        count++;
    }
    public void remove(String key){
        data.remove(key);
        count--;
    }
    public <T> T get(String key) {
        return (T) data.get(key);
    }

    public int getCount() {
        return count;
    }
    public String getName() {
        return domain;
    }
}

package com.hash;

import java.util.LinkedList;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * @create 2020-07-08 21:03
 */
public class CustomServer {

    //待添加入Hash环的真实服务器节点列表
    private  LinkedList<Node> realNodes = new LinkedList<>();

    //虚拟节点列表
    private  SortedMap<Integer, Node> sortedMap = new TreeMap<Integer, Node>();

    public CustomServer() {
        init();
    }

    private void init() {
        //初始化服务器数量
        for (int i = 0; i < 10; i++) {
            String nodeName = "server"+i;
            Node node = new Node(nodeName);
            realNodes.add(node);
        }

        //引入虚拟节点： 添加1000倍虚拟节点，将10台server对应的虚拟节点放入TreeMap中
        for (Node node : realNodes) {
            for (int i = 1; i <=1000; i++) {
                String nodeName = node.getName() + "-VM" + String.valueOf(i);
                int hash = CustomHashUtil.hashCode(nodeName);
                sortedMap.put(hash, node);
            }
        }
    }

    //得到应当路由到的结点
    protected   Node getNode(String key) {
        //得到该key的hash值
        int hash = CustomHashUtil.hashCode(key);
        //得到大于该Hash值的所有Map
        Node node;
        SortedMap<Integer, Node> subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            node = sortedMap.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            node= subMap.get(i);
        }

        if(node!=null) {
            node.put(key,hash+"");
            System.out.println(node.getName());
        }
        return node;
    }

    //获取实际服务器上负载平均值
    private   double getAverage(LinkedList<Node> arr) {
        double sum = 0;
        int number = arr.size();
        for (int i = 0; i < number; i++) {
            Node node =arr.get(i);
            sum += node.getCount();
        }
        return sum / number;
    }
    //获取实际服务器上负载的标准差
    protected   double getStandardDevition(LinkedList<Node> arr) {
        double sum = 0;
        int number = arr.size();
        double avgValue = getAverage(arr);//获取平均值
        for (int i = 0; i < number; i++) {
            Node node =arr.get(i);
            sum += Math.pow((node.getCount() - avgValue), 2);
        }
        return Math.sqrt((sum / (number - 1)));
    }

    public LinkedList<Node> getRealNodes() {
        return realNodes;
    }

    public SortedMap<Integer, Node> getSortedMap() {
        return sortedMap;
    }
}

package com.hash;

import lombok.extern.slf4j.Slf4j;

/**
 * @create 2020-07-08 21:09
 */
@Slf4j
public class Test {
    public static void main(String[] args) {
        CustomServer customServer=new CustomServer();
        //模拟节点
        for (int i = 0; i < 1000000; i++) {
            String key = "用户:"+i;

            System.out.println(key + "的hash值为" + CustomHashUtil.hashCode(key) + ", 对应结点：" + customServer.getNode(key).getName() + "");
        }

        //打印 Node的实际负载
        for (int i = 0; i < customServer.getRealNodes().size(); i++) {
            Node node = customServer.getRealNodes().get(i);
            System.out.println("服务器：" + node.getName()+"，对应用户数量："+node.getCount());
        }

        System.out.println("标准差："+customServer.getStandardDevition(customServer.getRealNodes())+"");
    }
}