架构师训练营 - 命题作业 第 5 周

package consistanthash;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashWithVirtualNode {
	// 真实节点列表
	private List<String> realNodes = new LinkedList<String>();

	// 虚拟节点列表, key表示虚拟节点的hash值，value表示虚拟节点的名称
	private TreeMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

	public ConsistentHashWithVirtualNode(String[] servers, int virtualNumPerNode) {
		// 先把原始的服务器添加到真实结点列表中
		if (servers != null) {
			for (int i = 0; i < servers.length; i++) {
				realNodes.add(servers[i]);

				// 再添加虚拟节点
				for (int j = 0; j < virtualNumPerNode; j++) {
					String virtualNodeName = servers[i] + "#" + String.valueOf(j);
					int hash = getHash(virtualNodeName);
					System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
					virtualNodes.put(hash, virtualNodeName);
				}
			}
		}
	}

	// 使用FNV1_32_HASH算法计算服务器的Hash值
	private 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;
	}

	// 得到应当路由到的结点
	public String getServer(String key) {
		// 得到该key的hash值
		int hash = getHash(key);
		String virtualNode = null;
		Map.Entry<Integer, String> servers = virtualNodes.ceilingEntry(hash); // 得到大于该Hash值的所有Map
		if (servers == null) {
			virtualNode = virtualNodes.firstEntry().getValue(); // 如果没有比该key的hash值大的，则从第一个node开始
		} else {	
			virtualNode = servers.getValue();
		}
		
		//截取真实节点
		if (virtualNode != null) {
			return virtualNode.substring(0, virtualNode.indexOf("#"));
		}
		return null;

	}

}


package consistanthash;

import java.util.HashMap;
import java.util.Map;

import org.junit.Before;
import org.junit.Test;

public class TestCache {
	private Map<String, Integer> serverCount = new HashMap<String, Integer>();
	private String[] servers = { "192.168.0.1:6379", "192.168.0.2:6379", "192.168.0.3:6379", "192.168.0.4:6379",
			"192.168.0.5:6379", "192.168.0.6:6379", "192.168.0.7:6379", "192.168.0.8:6379", "192.168.0.9:6379",
			"192.168.0.10:6379" };
	private int maxCacheNum = 1000000;
	private int virtualNum = 10;
	
	@Before
	public void setUp() {
	}

	@Test
	public void testCache1() { // 10个虚拟节点, 标准差为： 38914.03697896172
		virtualNum = 10;
		ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode(servers, virtualNum);
		setCache(ch, maxCacheNum);
		String result = calculateResult(ch, virtualNum);
		System.out.println(result);
	}

	@Test
	public void testCache2() { // 100个虚拟节点, 标准差为：  4769
		virtualNum = 100;
		ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode(servers, virtualNum);
		setCache(ch, maxCacheNum);
		String result = calculateResult(ch, virtualNum);
		System.out.println(result);
	}
	
	@Test
	public void testCache3() { // 1000个虚拟节点, 标准差为：  3850
		virtualNum = 1000;
		ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode(servers, virtualNum);
		setCache(ch, maxCacheNum);
		String result = calculateResult(ch, virtualNum);
		System.out.println(result);
	}
	
	@Test
	public void testCache4() { // 10000个虚拟节点, 标准差为：  1104
		virtualNum = 10000;
		ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode(servers, virtualNum);
		setCache(ch, maxCacheNum);
		String result = calculateResult(ch, virtualNum);
		System.out.println(result);
	}
	
	public void setCache(ConsistentHashWithVirtualNode ch, int cacheNum) {
		for (int i = 0; i < cacheNum; i++) {
			String key = "key" + i;
			String server = ch.getServer(key);
			serverCount.putIfAbsent(server, 1);
			int count = serverCount.get(server);
			serverCount.put(server, ++count);
		}
	}

	private String calculateResult(ConsistentHashWithVirtualNode ch, int virtualNum) {
		int totalNum = 0;
		for (Map.Entry<String, Integer> serverInfo : serverCount.entrySet()) {
			totalNum += serverInfo.getValue();
		}
		
		int avg = totalNum / serverCount.size();
		StringBuilder sb = new StringBuilder();
		sb.append("总缓存个数：").append(totalNum).append(" 服务器台数：").append(serverCount.size()).append(" 每服务器虚拟节点数：")
				.append(virtualNum).append(" 平均值：").append(avg).append("\r\n");
		// 标准差公式： (每个样本 - 平均值)的平方 / (服务器数 - 1)，结果再取平方根
		long diff = 0;
		for (Map.Entry<String, Integer> serverInfo : serverCount.entrySet()) {
			sb.append("Server-Name:").append(serverInfo.getKey()).append(" Cache-num: ").append(serverInfo.getValue()).append("\r\n");
			long tmp = serverInfo.getValue() - avg;
			diff += (tmp * tmp);
		}
		diff /= (serverCount.size() - 1);
		sb.append("标准差为： ").append(Math.sqrt(diff)).append("\r\n");
		return sb.toString();
	}
}