架构师训练营第 5 周作业

public interface Node {
    String getKey();
}

public class VirtualNode<T extends Node> implements Node {
    final T physicalNode;
    final int vIndex;
    public VirtualNode(T physicalNode, int vIndex) {
        this.physicalNode = physicalNode;
        this.vIndex = vIndex;
    }
    public boolean isVirtualNodeOf(T physicalNode) {
        if (physicalNode == null) return false;
        return physicalNode.getKey().equals(this.physicalNode.getKey());
    }
    @Override
    public String getKey() {
        return this.physicalNode.getKey() + "_" + vIndex;
    }
    public T getPhysicalNode() {
        return physicalNode;
    }
}

public class ServerNode implements Node {
    private final String zoneId;
    private final String ip;
    private final int port;
    public ServerNode(String zoneId, String ip, int port) {
        this.zoneId = zoneId;
        this.ip = ip;
        this.port = port;
    }
    @Override
    public String getKey() {
        return zoneId + "_" + ip + ":" + port;
    }
}

public interface HashAlgorithm {
    long hash(String key);
}

public class Sha256HashAlgorithm implements HashAlgorithm {
    private final MessageDigest messageDigest;
    public Sha256HashAlgorithm() {
        try {
            messageDigest = MessageDigest.getInstance("SHA-256");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("初始化 SHA-256 哈希算法失败");
        }
    }
    @Override
    public long hash(String key) {
        byte[] digest = messageDigest.digest(key.getBytes());
        long h = 0;
        for (int i = 0; i < 4; i++) {
            h <<= 8;
            h |= ((int) digest[i]) & 0xFF;
        }
        return h;
    }
}

public class ConsistentHash<T extends Node> {
    private final SortedMap<Long, VirtualNode<T>> hashRing = new TreeMap<>();
    private final HashAlgorithm hashAlgorithm;
    public ConsistentHash(Collection<T> pNodes, int vNodeCount) {
        this(pNodes, vNodeCount, new Sha256HashAlgorithm());
    }
    public ConsistentHash(Collection<T> pNodes, int vNodeCount, HashAlgorithm hashAlgorithm) {
        this.hashAlgorithm = hashAlgorithm;
        if (pNodes != null) {
            for (T pNode : pNodes) {
                appendVirtualNode(pNode, vNodeCount);
            }
        }
    }
    public void appendVirtualNode(T pNode, int vNodeCount) {
        if (vNodeCount < 0) throw new IllegalArgumentException("虚拟节点数量不能小于 0");
        int existingVNodeCount = this.getPhysicalNodeExistingVirtualNodeCount(pNode);
        for (int i = 0; i < vNodeCount; i++) {
            VirtualNode<T> virtualNode = new VirtualNode<>(pNode, i + existingVNodeCount);
            hashRing.put(hashAlgorithm.hash(virtualNode.getKey()), virtualNode);
        }
    }
    public void removePhysicalNode(T pNode) {
        if (pNode == null) return;
        Iterator<Long> iterator = hashRing.keySet().iterator();
        while (iterator.hasNext()) {
            Long key = iterator.next();
            VirtualNode<T> virtualNode = hashRing.get(key);
            if (virtualNode.isVirtualNodeOf(pNode)) {
                iterator.remove();
            }
        }
    }
    public T routeNode(String key) {
        if (hashRing.isEmpty()) {
            return null;
        }
        long hash = hashAlgorithm.hash(key);
        SortedMap<Long, VirtualNode<T>> tailMap = hashRing.tailMap(hash);
        long nodeHash = !tailMap.isEmpty() ? tailMap.firstKey() : hashRing.firstKey();
        return hashRing.get(nodeHash).getPhysicalNode();
    }
    private int getPhysicalNodeExistingVirtualNodeCount(T physicalNode) {
        int count = 0;
        for (VirtualNode<T> node : hashRing.values()) {
            if (node.isVirtualNodeOf(physicalNode)) {
                count++;
            }
        }
        return count;
    }
}

public class Test {
  public static void main(String[] args) {
		// 虚拟节点数量
    for (int i = 1; i < 1000; i++) {
      int times = 1000000;
      List<ServerNode> servers = Arrays.asList(
        new ServerNode("zone1", "192.168.0.1", 6789),
        new ServerNode("zone1", "192.168.0.2", 6789),
        new ServerNode("zone1", "192.168.0.3", 6789),
        new ServerNode("zone1", "192.168.0.4", 6789),
        new ServerNode("zone1", "192.168.0.5", 6789),
        new ServerNode("zone1", "192.168.0.6", 6789),
        new ServerNode("zone1", "192.168.0.7", 6789),
        new ServerNode("zone1", "192.168.0.8", 6789),
        new ServerNode("zone1", "192.168.0.9", 6789),
        new ServerNode("zone1", "192.168.0.10", 6789));
      ConsistentHash<ServerNode> consistentHash = new ConsistentHash<>(servers, i);
      Map<String, Integer> routedCount = Maps.newLinkedHashMap();
      routedCount.put("zone1_192.168.0.1:6789", 0);
      routedCount.put("zone1_192.168.0.2:6789", 0);
      routedCount.put("zone1_192.168.0.3:6789", 0);
      routedCount.put("zone1_192.168.0.4:6789", 0);
      routedCount.put("zone1_192.168.0.5:6789", 0);
      routedCount.put("zone1_192.168.0.6:6789", 0);
      routedCount.put("zone1_192.168.0.7:6789", 0);
      routedCount.put("zone1_192.168.0.8:6789", 0);
      routedCount.put("zone1_192.168.0.9:6789", 0);
      routedCount.put("zone1_192.168.0.10:6789", 0);
      for (int j = 0; j < times; j++) {
        ServerNode routeNode = consistentHash.routeNode(UUID.randomUUID().toString());
        routedCount.put(routeNode.getKey(), routedCount.get(routeNode.getKey()) + 1);
      }
      System.out.println(i + "\t" + getStandardDeviation(routedCount.values().toArray(new Integer[0])));
    }
  }
  
  private static double getStandardDeviation(Integer[] array) {
    int m = array.length;
    double sum = 0;
    for (Integer i : array) {
      sum += i;
    }
    double dAve = sum / m;
    double dVar = 0;
    for (Integer i : array) {
      dVar += (i - dAve) * (i - dAve);
    }
    return Math.sqrt(dVar / m);
  }
}