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

package love.luke.architect.demo;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.UUID;
import java.util.Map.Entry;
import lombok.extern.slf4j.Slf4j;
@Slf4j
public class ConsistentHashRouter {
		
	/**
	 * 虚拟节点的放大比例，真实节点数:虚拟节点数 = 1:virtualTime
	 */
	private int virtualTimes;
	/**
	 * 真实节点的IP清单列表，真实节点的位置餐宿格式为ip:prot
	 */
	private String[] serversIp;
	/**
	 * 由serversIps 真实节点的IP清单列表转换而来的List, 后续便于增删
	 */
	private List<String> realNodes;
	/**
	 * 虚拟节点构成的哈希环，使用TreeMap，后续查找节点方便
	 */
	private TreeMap<Integer, String> virtualNodes;
	
	
	public ConsistentHashRouter(int virtualTimes, String[] serversIp) {
		
		if (null == serversIp || serversIp.length == 0)
			throw new IllegalArgumentException("输入服务器清单不能为空");
		
		this.serversIp= serversIp;
		this.virtualTimes = virtualTimes;
		
		realNodes = new LinkedList<String>();
		for(String ip :  serversIp ) {
			realNodes.add(ip);
		}
		
		//为每个固定节点，生成哈希环上的虚拟节点
		virtualNodes = new TreeMap<Integer, String>();
		for(String realNode : realNodes) {
			for (int i=0; i<virtualTimes; i++) {
				// 采用随机UUID的hash为虚拟节点位置
				int key = getHash(UUID.randomUUID().toString());
				virtualNodes.put(key, realNode);
			}
		}
	}
	
	/**
	 * 计算输入字符串对应的hash值
	 * @param str 
	 * @return 哈希值
	 */
	private int getHash(String str) {
		// 先暂时使用内置的Hash算法，后续可以更换算法以达到更好的效果
		return str.hashCode();
	}
	
	/**
	 * 根据传入的Key，得到对应的实际服务节点
	 * @param key
	 * @return 
	 */
	public synchronized String getServer(String key) {
		// 计算查询Key的hash
		int hashOfKey = getHash(key);
		// 在哈希环上向后找到大于查询Key的hash 的最近的一个虚拟节点
		Entry<Integer, String> entry = virtualNodes.ceilingEntry(hashOfKey);
    // 因为是哈希环，所以当向后上找不到比当前查询Key hash大的节点，则循环返回第一个虚拟节点
		if (null == entry) {
			entry = virtualNodes.firstEntry();
		}
		
		return entry.getValue();
	}
	
	/**
	 * 增加实际真实节点
	 * @param newServerIp
	 */
	public synchronized void addServer(String newServerIp) {
		realNodes.add(newServerIp);
		for (int i=0; i<virtualTimes; i++) {
			int key = getHash(UUID.randomUUID().toString());
			virtualNodes.put(key, newServerIp);
		}
	}
}

import static org.junit.Assert.*;
import java.util.HashMap;
import java.util.UUID;
import java.util.Map.Entry;
import love.luke.architect.demo.ConsistentHashRouter;
import org.junit.Test;
public class ConsistentHashRouterTest {
	@Test
	public void test() {
		final int TEST_CASE_AMOUNT = 1000000;
		
		String seversIp[] = { "10.0.0.0", "10.0.0.1", "10.0.0.2", "10.0.0.3",
				"10.0.0.4", "10.0.0.5", "10.0.0.6", "10.0.0.7",
				"10.0.0.8", "10.0.0.9" };
		
		// 10个实体服务器，每个服务器对应100个虚拟节点
		ConsistentHashRouter router = new ConsistentHashRouter(10, seversIp);
		// 计数器，统计每个真实Server被命中的次数
		HashMap<String, Long> counterMap = new HashMap<>();
		// 随机生成100万个UUID作为key进行测试，记录分实际存储节点被命中选取出来的数量
		for (int i = 0; i < TEST_CASE_AMOUNT; i++) {
			String key = UUID.randomUUID().toString();
			String ip = router.getServer(key);
			Long counter = counterMap.get(ip);
			if (counter == null)
				counterMap.put(ip, 1L);
			else
				counterMap.put(ip, counter + 1);
		}
		// 计算10个实际节点被命中次数的方差
		long sum = 0;
		double average = 0;
		for (Entry<String, Long> counterEntry : counterMap.entrySet()) {
			System.out.println(counterEntry.getKey() + " :"
					+ counterEntry.getValue());
			sum = sum + counterEntry.getValue();
		}
		average = sum / counterMap.keySet().size() ;
		System.out.println("average:" + average);
		
		double deviation = 0;
		for (Entry<String, Long> counterEntry : counterMap.entrySet()) {
			deviation = deviation + Math.pow(counterEntry.getValue() - average, 2);
		}
		System.out.println("Standard Deviation:" + Math.sqrt(deviation/counterMap.keySet().size()));
	}
}

10.0.0.8 :106954
10.0.0.7 :53143
10.0.0.9 :106018
10.0.0.4 :85179
10.0.0.3 :109442
10.0.0.6 :100047
10.0.0.5 :87724
10.0.0.0 :151591
10.0.0.2 :128801
10.0.0.1 :71101
Standard Deviation:26581.8542656452


10.0.0.8 :106176
10.0.0.7 :104553
10.0.0.9 :81190
10.0.0.4 :99238
10.0.0.3 :93703
10.0.0.6 :112491
10.0.0.5 :103025
10.0.0.0 :91412
10.0.0.2 :101293
10.0.0.1 :106919
average:100000.0
Standard Deviation:8610.433194677256