架构师训练营第 1 期 -- 第五周作业

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class ConsistentHashMain {
	
	public static void main(String[] args) throws Exception {
		String[] servers = new String[]{"server1", "server2", "server3", "server4", "server5", "server6", "server7", "server8", "server9", "server10"};
		
		ExecutorService threadPool = Executors.newFixedThreadPool(10);
		
		final int maxVirtualNodes = 300;
		final int visitTime = 1000000;
		final int avgLoad = visitTime/servers.length;
		for (int virtualNodes = 1; virtualNodes <= maxVirtualNodes; virtualNodes++) {
			final int vNodes = virtualNodes;
			threadPool.execute(() -> {
				HashCircle circle = new HashCircle(vNodes, servers);
				for (int i = 0; i < visitTime; i++) {
					UUID uuid = UUID.randomUUID();
					circle.visitCluster(uuid.toString());
				}
				int x = 0;
				for (int i = 0; i < servers.length; i++) {
					int a = circle.getVisitorLogMap().get(servers[i]).size() - avgLoad;
					x += a * a;
				}
				int y = x / servers.length;
				System.out.println(String.format("%d:%d", vNodes, y));
			});
		}
		threadPool.awaitTermination(1, TimeUnit.HOURS);
	}
	
}


class HashCircle {
	
	/**
	 * 主环
	 */
	private String[] circle;
	
	private int[] addressMapper;
	
	/**
	 * 虚节点数量
	 */
	private int virtualNodeFactor;
	
	
	/**
	 * 地址记录字典
	 */
	private Map<String, List<Integer>> nodeAddressMap = new HashMap<>();
	
	private Map<String, List<String>> visitorLogMap = new HashMap<>(); 
	
	
	HashCircle(int virtualNodeFactor, String[] nodes) {
		this.virtualNodeFactor = virtualNodeFactor;
		circle = new String[virtualNodeFactor * nodes.length];
		addressMapper = new int[circle.length];
		this.assignNodes(nodes);
	}
	
	private void assignNodes(String[] nodes) {
		int interval = Integer.MAX_VALUE / nodes.length / this.virtualNodeFactor;
		int currentAddress = 0;
		int mapperIndex = 0;
		for (int i = 0; i < this.virtualNodeFactor; i++) {
			for (int j = 0; j < nodes.length; j++) {
				currentAddress += interval;
				currentAddress = convertNeg(currentAddress);
				addressMapper[mapperIndex] = currentAddress;
				circle[mapperIndex++] = nodes[j];
				recordAddress(nodes[j], currentAddress);
			}
		}
	}

	private void recordAddress(String content, int currentAddress) {
		List<Integer> addrList = nodeAddressMap.get(content);
		if (addrList == null) {
			addrList = new ArrayList<Integer>(this.virtualNodeFactor);
			nodeAddressMap.put(content, addrList);
		}
		addrList.add(currentAddress);
	}
	
	/**
	 * 不同的用户过来，返回访问的服务器id
	 * @param visitorId
	 * @return
	 */
	public String visitCluster(String visitorId) {
		int address = visitorId.hashCode();
		String server = getNode(address);
		List<String> userIdList = visitorLogMap.get(server);
		if (userIdList == null) {
			userIdList = new ArrayList<String>();
			visitorLogMap.put(server, userIdList);
		}
		userIdList.add(visitorId);
		return server;
	}

	public Map<String, List<Integer>> getNodeAddressMap() {
		return nodeAddressMap;
	}

	public Map<String, List<String>> getVisitorLogMap() {
		return visitorLogMap;
	}
	
	public String getNode(int hashCode) {
		hashCode = convertNeg(hashCode);
		for (int i = 0; i < addressMapper.length; i++) {
			if (hashCode < addressMapper[i]) {
				return circle[i];
			}
		}
		return circle[0];
	}

	private int convertNeg(int hashCode) {
		if (hashCode < 0) {
			hashCode = hashCode & 0x7fffffff;
		}
		return hashCode;
	}
	
}