week5. 课后作业

package com.demo.hash;
/**
 * 一致性哈希系统配置文件
 * @author niki-lauda
 * @create 2020-07-05 17:04
 */
public class SystemConstansts {
    /**
     * 实际机器简称-IP地址:端口
     */
    public static String NODE_LIST = "'M0;192.168.10.1:8306','M1;192.168.10.2:8306','M2;192.168.10.3:8306','M3;192.168.10.4:8306','M4;192.168.10.5:8306','M5;192.168.10.6:8306'," +
            "'M6;192.168.10.7:8306','M7;192.168.10.8:8306','M8;192.168.10.9:8306','M9;192.168.10.10:8306'";
    /**
     * 每台机器对应虚拟节点数量
     */
    public static final int VIRTUAL_NODE_NUM = 220;
}

package com.demo.hash;
import java.util.HashMap;
import java.util.Map;
/**
 * 机器
 * @author niki-lauda
 * @create 2020-07-05 17:12
 */
public class MachineNode {
    private String name;
    private String ipAddress;
    private Map<Object, Object> data;
    MachineNode(String name, String ipAddress) {
        this.name = name;
        this.ipAddress = ipAddress;
        data = new HashMap<>();
    }
    Object getValue(Object key) {
        Object value = data.get(key);
        System.out.println("获取数据从[" + name + "],地址=[" + ipAddress + "],key=[" + key + "],value=[" + value + "]");
        return value;
    }
    Object putValue(Object key, Object value) {
        data.put(key, value);
        System.out.println("新加数据从[" + name + "],地址=[" + ipAddress + "],key=[" + key + "],value=[" + value + "]");
        return value;
    }
    String getName() {
        return name;
    }
    int getDataSize() {
        return data.size();
    }
}

package com.demo.hash;
/**
 * 虚拟节点
 * @author niki-lauda
 * @create 2020-07-05 17:18
 */
public class VirtualNode {
    private int position;
    private MachineNode machineNode;
    VirtualNode(int position, MachineNode machineNode) {
        this.position = position;
        this.machineNode = machineNode;
    }
    Object getValue(Object key) {
        return machineNode.getValue(key);
    }
    Object putValue(Object key, Object value) {
        return machineNode.putValue(key,value);
    }
    String getName() {
        return machineNode.getName();
    }
    int getDataSize() {
        return machineNode.getDataSize();
    }
}

package com.demo.hash;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
/**
 * 一致性哈希环
 * @author niki-lauda
 * @create 2020-07-05 17:24
 */
public class ConsistentHashRing {
    private TreeMap<Integer, VirtualNode> nodeMap;
    private static final ConsistentHashRing INSTANCE = new ConsistentHashRing();
    private Map<String, Integer> machineDataSizeMap = new HashMap<>();
    private ConsistentHashRing() {
        this.nodeMap = new TreeMap<>();
        startUp();
    }
    public static ConsistentHashRing getInstance () {
        return INSTANCE;
    }
    private void startUp() {
        String nodeList = SystemConstansts.NODE_LIST;
        String[] nodeArray = nodeList.split(",");
        for (String nodeStr : nodeArray) {
            String[] data = nodeStr.split(";");
            machineDataSizeMap.put(data[0], 0);
            MachineNode machineNode = new MachineNode(data[0], data[1]);
            for (int i = 0; i < SystemConstansts.VIRTUAL_NODE_NUM; i++) {
                int nextInt = getHashCode(data[0] + i);
                nodeMap.put(nextInt, new VirtualNode(nextInt, machineNode));
            }
        }
    }
    public int getHashCode(String key) {
        // int ret = key.hashCode(); // 结果太聚集，不使用
        final int p = 16777619;
        int ret = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            ret = (ret ^ key.charAt(i)) * p;
        }
        ret += ret << 13;
        ret ^= ret >> 7;
        ret += ret << 3;
        ret ^= ret >> 17;
        ret += ret << 5;
        return ret;
    }
    public void addMachine(String machineConfig) {
        String[] configArray = machineConfig.split(";");
        machineDataSizeMap.put(configArray[0], 0);
        MachineNode machineNode = new MachineNode(configArray[0], configArray[1]);
        for (int i = 0; i < SystemConstansts.VIRTUAL_NODE_NUM; i++) {
            int nextInt = getHashCode(configArray[0] + i);
            nodeMap.put(nextInt, new VirtualNode(nextInt, machineNode));
        }
    }
    private VirtualNode getRightNode(int key) {
        Map.Entry<Integer, VirtualNode> integerVirtualNodeEntry = nodeMap.ceilingEntry(key);
        if(integerVirtualNodeEntry == null) {
            integerVirtualNodeEntry = nodeMap.firstEntry();
        }
        return integerVirtualNodeEntry.getValue();
    }
    public Object get(Object key) {
        VirtualNode rightMachine = getRightNode(getHashCode(key.toString()));
        return rightMachine.getValue(key);
    }
    public Object put(Object key, Object value) {
        VirtualNode rightMachine = getRightNode(getHashCode(key.toString()));
        return rightMachine.putValue(key, value);
    }
    private Map<String, Integer> getMachineDataSizeMap() {
        for (Map.Entry<String, Integer> entry : machineDataSizeMap.entrySet()) {
            for (Map.Entry<Integer, VirtualNode> nodeEntry : nodeMap.entrySet()) {
                if(entry.getKey().equals(nodeEntry.getValue().getName())) {
                    entry.setValue(nodeEntry.getValue().getDataSize());
                    break;
                }
            }
        }
        return machineDataSizeMap;
    }
    public double getStandardDeviation() {
        Map<String, Integer> machineDataSizeMap = getMachineDataSizeMap();
        int machineSize = machineDataSizeMap.size();
        long dataSize = 0L;
        for (Integer value : machineDataSizeMap.values()) {
            dataSize += value;
        }
        double averageSize = dataSize / machineSize;
        long total = 0;
        for (Integer value : machineDataSizeMap.values()) {
             total += (averageSize - value) * (averageSize - value);
        }
        return Math.sqrt(total / (machineSize - 1));
    }
}

package com.demo.hash;

import java.util.Random;

/**
 * @author niki-lauda
 * @create 2020-07-05 18:29
 */
public class TestHash {

    private static String getKey() {
        Random random = new Random();
        int nextInt = random.nextInt(15);
        nextInt = nextInt > 5 ? nextInt : 5;
        char start = 'A';
        String result = "";
        for (int i = 0; i < nextInt; i++) {
            int nextInt1 = random.nextInt(58);
            result += (char)(start + nextInt1);
        }
        return result;
    }
    
    public static void main(String[] args) {
        ConsistentHashRing instance = ConsistentHashRing.getInstance();
        for (int i = 0; i < 1000000; i++) {
            String key = getKey();
            instance.put(key, key);
        }
        System.out.println(instance.getStandardDeviation());
    }
}

public int getHashCode(String key) {
        // int ret = key.hashCode(); // 结果太聚集，不使用
        final int p = 16777619;
        int ret = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            ret = (ret ^ key.charAt(i)) * p;
        }
        ret += ret << 13;
        ret ^= ret >> 7;
        ret += ret << 3;
        ret ^= ret >> 17;
        ret += ret << 5;
        return ret;
    }