架构师课作业 - 第五周

/**
 * 服务节点
 */
public class ServiceNode {
    // 节点ID
    private String nodeId;
    // 节点名称
    private String nodeName;
    // 节点IP
    private String ipAddress;
    public ServiceNode(String nodeId, String nodeName, String ipAddress) {
        this.nodeId = nodeId;
        this.nodeName = nodeName;
        this.ipAddress = ipAddress;
    }
    public String getNodeId() {
        return nodeId;
    }
    public String getNodeName() {
        return nodeName;
    }
    public String getIpAddress() {
        return ipAddress;
    }
}

/**
 * 虚拟服务节点
 */
public class VirtualServiceNode extends ServiceNode {
    private boolean virtualTag;
    private ServiceNode realServiceNode;
    public VirtualServiceNode(String nodeId, String nodeName, String ipAddress, ServiceNode serviceNode) {
        super(nodeId, nodeName, ipAddress);
        virtualTag = true;
        realServiceNode = serviceNode;
    }
    public boolean isVirtualTag() {
        return virtualTag;
    }
    public ServiceNode getRealServiceNode() {
        return realServiceNode;
    }
}

/**
 * 一致性Hash算法
 */
public class ConsistentHash {
    private final SortedMap<Integer, ServiceNode> sortedMap;
    public ConsistentHash() {
        this.sortedMap = new TreeMap<Integer, ServiceNode>();
    }
    /**
     * 根据服务节点, 构建一致性Hash环
     * @param serviceNodes
     */
    public void buildHashRing(List<ServiceNode> serviceNodes){
        for (ServiceNode serviceNode : serviceNodes) {
            increaseServiceNode(serviceNode);
        }
        System.out.println("一致性Hash环构建完毕");
    }
    /**
     * Hash环增加节点
     * @param serviceNode
     */
    public void increaseServiceNode(ServiceNode serviceNode){
        final int hash = getHash(serviceNode.getNodeId());
        System.out.println("[" + serviceNode.getNodeName() + "]加入集合中, 其Hash值为" + hash);
        sortedMap.put(hash, serviceNode);
    }
    /**
     * Hash环减少节点
     * @param serviceNode
     */
    public void reduceServiceNode(ServiceNode serviceNode){
        final int hash = getHash(serviceNode.getNodeId());
        System.out.println("[" + serviceNode.getNodeName() + "]从集合中移除, 其Hash值为" + hash);
        sortedMap.remove(hash);
    }
    /**
     * 查找节点
     * @param key
     * @return
     */
    public ServiceNode getServiceNode(String key){
        final int hash = getHash(key);
        final SortedMap<Integer, ServiceNode> serviceNodeSortedMap = sortedMap.tailMap(hash);
        if(serviceNodeSortedMap.isEmpty()){
            final ServiceNode serviceNode = sortedMap.get(sortedMap.firstKey());
            System.out.println("未找到节点, 取首个节点[" + serviceNode.getNodeName() + "]");
            return sortedMap.get(sortedMap.firstKey());
        }
        final ServiceNode serviceNode = serviceNodeSortedMap.get(serviceNodeSortedMap.firstKey());
        System.out.println("找到节点[" + serviceNode.getNodeName() + "]");
        return serviceNode;
    }
    private static 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;
    }
}

/**
 * 一致性Hash算法 (包含虚拟节点)
 */
public class ConsistentHashWithVirtualNode extends ConsistentHash {
    /**
     * 虚拟节点数
     */
    private final int virtualNum;
    public ConsistentHashWithVirtualNode(int virtualNum) {
        this.virtualNum = virtualNum;
    }
    /**
     * 增加节点 (包括虚拟节点)
     * @param serviceNode
     */
    @Override
    public void increaseServiceNode(ServiceNode serviceNode) {
        super.increaseServiceNode(serviceNode);
        // 虚拟节点新增
        final List<ServiceNode> virtualServiceNode = getVirtualServiceNode(serviceNode);
        for (ServiceNode virServiceNode : virtualServiceNode) {
            super.increaseServiceNode(virServiceNode);
        }
    }
    /**
     * 减少节点 (包括虚拟节点)
     * @param serviceNode
     */
    @Override
    public void reduceServiceNode(ServiceNode serviceNode) {
        super.reduceServiceNode(serviceNode);
        // 虚拟节点删除
        final List<ServiceNode> virtualServiceNode = getVirtualServiceNode(serviceNode);
        for (ServiceNode virServiceNode : virtualServiceNode) {
            super.reduceServiceNode(virServiceNode);
        }
    }
    /**
     * 根据服务节点, 构建虚拟节点集合
     * @param serviceNode
     * @return
     */
    private List<ServiceNode> getVirtualServiceNode(ServiceNode serviceNode){
        List<ServiceNode> serviceNodes = new ArrayList<>(virtualNum);
        for (int i = 0; i < virtualNum; i++) {
            VirtualServiceNode virtualServiceNode = new VirtualServiceNode(
                    serviceNode.getNodeId() + "." + i,
                   serviceNode.getNodeName() + "." + i,
                    serviceNode.getIpAddress(),
                    serviceNode);
            serviceNodes.add(virtualServiceNode);
        }
        return serviceNodes;
    }
}

public class ZTest {
    static final ServiceNode serviceNodeTest = new ServiceNode("TEST", "节点TEST", "192.168.0.255");
    public static void main(String[] args) {
        ConsistentHash consistentHash = new ConsistentHashWithVirtualNode(2);
        consistentHash.buildHashRing(buildServiceNodes());
        // 新增节点
        consistentHash.increaseServiceNode(serviceNodeTest);
        // 删除节点
        consistentHash.reduceServiceNode(serviceNodeTest);
        // 查找节点
        consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
        consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
        consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
    }
    private static List<ServiceNode> buildServiceNodes() {
        List<ServiceNode> serviceNodes = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            serviceNodes.add(new ServiceNode(
                    UUID.randomUUID().toString().replaceAll("-", ""),
                    "节点" + (char) (65 + i),
                    "192.168.0." + i));
        }
        return serviceNodes;
    }
}

public class ZTest {
    public static void main(String[] args) {
        ConsistentHash consistentHash = new ConsistentHashWithVirtualNode(150);
        consistentHash.buildHashRing(buildServiceNodes());
        // 循环100万次
        Map<ServiceNode, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000000; i++) {
            ServiceNode serviceNode = consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
            if (serviceNode instanceof VirtualServiceNode) {
                // 通过虚拟节点找到真实服务节点
                serviceNode = ((VirtualServiceNode) serviceNode).getRealServiceNode();
            }
            // 统计KV分布到服务节点的次数
            final Integer num = map.getOrDefault(serviceNode, 0);
            map.put(serviceNode, num + 1);
        }
        // 打印各个节点被分配次数
        int[] nums = new int[10];
        int i = 0;
        for (Map.Entry<ServiceNode, Integer> entry : map.entrySet()) {
            nums[i++] = entry.getValue();
            System.out.println("节点[" + entry.getKey().getNodeName() + "] 分配到次数: " + entry.getValue());
        }
        // 标准差
        final double deviation = standardDeviation(nums);
        System.out.println("标准差为: " + deviation);
    }
    private static List<ServiceNode> buildServiceNodes() {
        List<ServiceNode> serviceNodes = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            serviceNodes.add(new ServiceNode(
                    UUID.randomUUID().toString().replaceAll("-", ""),
                    "节点" + (char) (65 + i),
                    "192.168.0." + i));
        }
        return serviceNodes;
    }
    /**
     * 标准差
     * @param array
     * @return
     */
    public static double standardDeviation(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        double average = sum / array.length;
        int total = 0;
        for (int i = 0; i < array.length; i++) {
            total += (array[i] - average) * (array[i] - average);
        }
        return Math.sqrt(total / array.length);
    }
}