架构师训练营 -Week 05 命题作业

public interface HashFunction {
    Integer hash(Object key);
}

public interface ConsistentHash<T> {
    public void addNode(T node);
    public Boolean removeNode(T node);
    public T getDistribution(Object key);
}

public class ConsistentHashImpl<T>  implements ConsistentHash<T> {
    private NavigableMap<Integer, T> circle = new TreeMap<>();
    private Integer numberOfReplicas;
    private HashFunction hashFunction;
    public ConsistentHashImpl(Integer numberOfReplicas) {
        this(null, numberOfReplicas, null);
    }
    public ConsistentHashImpl(Collection<T> nodes, Integer numberOfReplicas) {
        this(nodes, numberOfReplicas, null);
    }
    public ConsistentHashImpl(Collection<T> nodes, int numberOfReplicas, HashFunction hashFunction) {
        this.numberOfReplicas = numberOfReplicas > 1 ? numberOfReplicas :  1;
        if (nodes != null) {
            for (T node: nodes) {
                addNode(node);
            }
        }
        if (hashFunction == null) {
            this.hashFunction = new HashFunction() {
                @Override
                public Integer hash(Object key) {
                    return HashUtil.fnvHash(key.toString());
                }
            };
        }
    }
    @Override
    public void addNode(T node) {
        if (node == null) {
            return;
        }
        for (int i = 1; i <= numberOfReplicas; i++) {
            this.circle.put(hashFunction.hash(node.toString() + i), node);
        }
    }
    @Override
    public Boolean removeNode(T node) {
        if (node != null) {
            for (int i = 1; i <= numberOfReplicas; i++) {
                this.circle.remove(hashFunction.hash(node.toString() + i));
            }
        }
        return true;
    }
    @Override
    public T getDistribution(Object key) {
        if (key == null) {
            throw new NullPointerException("key can not be null.");
        }
        if (this.circle.isEmpty()) {
            return null;
        }
        Integer hash = hashFunction.hash(key);
        SortedMap<Integer, T> tailMap = this.circle.tailMap(hash);
        Integer matchNodeHash = tailMap.isEmpty() ? this.circle.firstKey() : tailMap.firstKey();
        return this.circle.get(matchNodeHash);
    }
    public NavigableMap<Integer, T> getCircle() {
        return this.circle;
    }
}

public class ServerNode {
	private String ip;
	private int port;
	private Map<String, Object> cacheData = new HashMap<>();
	public ServerNode(String ip, int port) {
		this.ip = ip;
		this.port = port;
	}
	@Override
	public String toString() {
		return new StringBuilder().append(ip).append(":").append(port).toString();
	}
	public void put(String key, Object value) {
		this.cacheData.put(key, value);
	}
	public Object remove(String key) {
		return cacheData.remove(key);
	}
	public Integer getDataCount() {
		return cacheData.size();
	}
}

public class ConsistentHashImplTest {
	public static final String[] ips = new String[]{
			"192.168.0.10", "192.168.0.11", "192.168.0.12", "192.168.0.13", "192.168.0.14",
			"192.168.0.15", "192.168.0.16", "192.168.0.17", "192.168.0.18", "192.168.0.19"
	};
	public static final int port = 8000;
	@Test
	public void testFnvHashBalance() {
		// 每个服务器节点对应10个虚拟节点
		ConsistentHash<ServerNode> consistentHash = new ConsistentHashImpl<>(10);
		test(consistentHash);
	}
	private void test(ConsistentHash<ServerNode> consistentHash) {
		List<ServerNode> nodeList = new ArrayList<>(ips.length);
		for (String ip : ips) {
			ServerNode serverNode = new ServerNode(ip, port);
			consistentHash.addNode(serverNode);
			nodeList.add(serverNode);
		}
		// 打印虚拟节点分布
		NavigableMap<Integer, ServerNode> circle = ((ConsistentHashImpl<ServerNode>) consistentHash).getCircle();
		Iterator<Integer> it = circle.keySet().iterator();
		int num = 1;
		while(it.hasNext()) {
			Integer i = it.next();
			System.out.printf("第%s个虚拟节点, 服务器【%s】\n", num++, circle.get(i).toString());
		}
		// 准备一百万条数据，用一致性分布算法分布在服务器上
		for (int i = 0; i < 1000000; i++) {
			String key = String.valueOf(i);
			String value = RandomUtil.randomString(6);
			consistentHash.getDistribution(key).put(key, value);
		}
		// 打印分布
		for (ServerNode serverNode : nodeList) {
			System.out.printf("服务器【%s】节点存储(%s)条数据\n", serverNode.toString(), serverNode.getDataCount());
		}
		// 标准差计算
		int total = nodeList.stream().mapToInt(ServerNode::getDataCount).sum();
		double avg = total * 1.0 / nodeList.size();
		double sum = nodeList.stream().mapToDouble(node -> Math.pow((node.getDataCount() * 1.0) - avg, 2)).sum();
		double standardDeviation = Math.sqrt(sum / nodeList.size());
		System.out.printf("标准差：%s", String.valueOf(standardDeviation));
	}
  
  /*
  结果：
  哈希算法：FnvHash
  虚拟节点数：100
  每个服务器节点对应10个虚拟节点
  服务器【192.168.0.10:8000】节点存储(79204)条数据
  服务器【192.168.0.11:8000】节点存储(77773)条数据
  服务器【192.168.0.12:8000】节点存储(151707)条数据
  服务器【192.168.0.13:8000】节点存储(128070)条数据
  服务器【192.168.0.14:8000】节点存储(73088)条数据
  服务器【192.168.0.15:8000】节点存储(99577)条数据
  服务器【192.168.0.16:8000】节点存储(120744)条数据
  服务器【192.168.0.17:8000】节点存储(94620)条数据
  服务器【192.168.0.18:8000】节点存储(86496)条数据
  服务器【192.168.0.19:8000】节点存储(88721)条数据
  标准差：24251.429566110117  
  */