第五周课后作业

public interface NodeRoute {

    /**
     * 根据key获取对应的服务节点
     * @param key
     * @return
     */
    ServiceNode get(String key);

    void addNode(ServiceNode node);

    void removeNode(ServiceNode node);

    Collection<ServiceNode> getAllNodes();
}


public class VirtualNodeConsistentHashRoute implements NodeRoute {

    private final ConcurrentNavigableMap<Integer, ServiceNode> skipListMap = new ConcurrentSkipListMap<>();
    private final CopyOnWriteArrayList<ServiceNode> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    private final int virtualNodeNumber;
    private final int virtualNodeLength;

    /**
     * 构造函数
     * @param nodeNumber 每个节点的虚拟节点数
     */
    public VirtualNodeConsistentHashRoute(int nodeNumber) {
        virtualNodeNumber = Math.max(nodeNumber, 1);
        virtualNodeLength = Integer.MAX_VALUE / virtualNodeNumber;
    }

    /**
     * 添加一个虚拟节点
     * 虚拟节点的计算比较简单，以node的hash值加上（Integer.MAX_VALUE / virtualNodeNumber）的值，确保能均匀分布在环上
     * @param node
     */
    @Override
    public void addNode(ServiceNode node) {
        if (Objects.isNull(node)) {
            return;
        }

        if (copyOnWriteArrayList.contains(node)) {
            return;
        }

        copyOnWriteArrayList.add(node);
        int hashCode = node.hashCode();
        long virtualNodeHashCode;
        for (int i = 0; i < virtualNodeNumber; i++) {
            virtualNodeHashCode = hashCode + (long)i * virtualNodeLength;
            virtualNodeHashCode = virtualNodeHashCode % Integer.MAX_VALUE;
            skipListMap.put((int) virtualNodeHashCode, node);
        }
    }

    /**
     * 删除服务节点
     * 需要移除对应的虚拟节点
     * @param node
     */
    @Override
    public void removeNode(ServiceNode node) {
        if (Objects.isNull(node)) {
            return;
        }

        if (!copyOnWriteArrayList.contains(node)) {
            return;
        }

        copyOnWriteArrayList.remove(node);
        int hashCode = node.hashCode();
        long virtualNodeHashCode;
        for (int i = 0; i < virtualNodeNumber; i++) {
            virtualNodeHashCode = hashCode + (long)i * virtualNodeLength;
            virtualNodeHashCode = virtualNodeHashCode % Integer.MAX_VALUE;
            skipListMap.remove((int)virtualNodeHashCode);
        }
    }

    /**
     * 获取所有服务节点
     * @return
     */
    @Override
    public Collection<ServiceNode> getAllNodes() {
        return Collections.unmodifiableCollection(copyOnWriteArrayList);
    }

    /**
     * 根据key获取对应的服务节点
     * @param key
     * @return
     */
    @Override
    public ServiceNode get(String key) {
        if (Objects.isNull(key) || CollectionUtils.isEmpty(skipListMap)) {
            return null;
        }

        int keyHashValue = key.hashCode();
        Map.Entry entry = skipListMap.ceilingEntry(keyHashValue);
        return Objects.nonNull(entry) && Objects.nonNull(entry.getValue())
                ? (ServiceNode) entry.getValue()
                : skipListMap.firstEntry().getValue();

    }
}

public class ServiceNode {

    private final AtomicInteger atomicInteger = new AtomicInteger();

    public ServiceNode() {
    }

    public void add(String key, Object value) {
        atomicInteger.incrementAndGet();
    }

    public int count() {
        return atomicInteger.get();
    }
}

public class LoadBalancingTest {

    public static void main(String[] args) {
        //10个服务器节点，每个服务器有150个虚拟节点
        NodeRoute nodeRoute = getNodeRouteHaveServices(10, 150);
        //100w个随机kv存取
        testServiceNodeHit(nodeRoute, 1_000_000);
        //计算标准差
        printStandardDeviation(1_000_000, nodeRoute.getAllNodes());
    }

    private static NodeRoute getNodeRouteHaveServices(int serviceNumber, int virtualNodeNumber) {
        NodeRoute nodeRoute = new VirtualNodeConsistentHashRoute(virtualNodeNumber);
        for (int i = 0; i < serviceNumber; i++) {
            nodeRoute.addNode(new ServiceNode());
        }
        return nodeRoute;
    }

    private static void testServiceNodeHit(NodeRoute nodeRoute, int number) {
        Random random = new SecureRandom();
        String keyString;
        Object value = new Object();
        for (int i = 0; i < number; i++) {
            keyString = "" + random.nextInt(Integer.MAX_VALUE);
            ServiceNode serviceNode = nodeRoute.get(keyString);
            serviceNode.add(keyString, value);
        }
    }

    private static void printStandardDeviation(int testNumber,
                                               Collection<ServiceNode> serviceNodes) {
        int nodeNumber = serviceNodes.size();
        int average = testNumber / nodeNumber;
        double variance = serviceNodes.stream()
                .mapToDouble(serviceNode -> {
                    int hitCount = serviceNode.count();
                    double oneVariance = Math.pow((hitCount - average), 2) / nodeNumber;
                    System.out.println("节点数据量: " + hitCount);
                    return oneVariance;
                }).sum();
        double standardDeviation = Math.sqrt(variance);
        System.out.println("标准差:" + standardDeviation);
    }
}