Week 004 作业

package cn.zs.mstpxu;
import static org.hamcrest.CoreMatchers.nullValue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;
import java.util.concurrent.atomic.AtomicInteger;
/**
 * Simple Version
 * 本例子仅考虑到单线程执行情况下的ConsistencyHash场景，时间有点仓促所以可能会存在考虑不周的情况，希望大家指正。
 * @author Master_PeiXU
 *
 */
public class ConsistencyHash {
	//保存Server节点映射,方便client查找最近节点。
	SortedMap<Integer,String> treeMap = new TreeMap<>();
   //保存结果
	private Map<String, Integer> consistencyHashResult = new HashMap<String, Integer>();
	
	private static List<String> DEFAULT_LIST = Arrays.asList("Server0","Server1","Server2","Server3","Server4","Server5"
															,"Server6","Server7","Server8","Server9");
	//Hash环大小
	private final int HASH_RANGE = Integer.MAX_VALUE - 1;
	private volatile List<String> serverLists = new ArrayList<String>();
	
	private int DEFAULT_VIPCOUNT = 1000;
	
	private int vipCount;
	
	
	public ConsistencyHash() {
		this.serverLists = DEFAULT_LIST;
		this.vipCount = DEFAULT_VIPCOUNT;
		doHash();
	}
	public ConsistencyHash(List<String> serverLists,int vipCount) {
		this.serverLists = serverLists;
		this.vipCount = vipCount;
		doHash();
	}
	
	/**
	 * 执行Hash的方法
	 */
	public void doHash() {
		for(String server : serverLists) {
			doVirtualIp(vipCount,server);
		}
	}
	
	/**
	 * 虚拟IP生成，并插入到Hash环中的方法函数
	 * @param vipNumber 虚拟Ip个数
	 * @param server 服务器名称
	 */
	private void doVirtualIp(int vipNumber, String server) {
		for(int i = 0 ; i < vipNumber ; i++) {
			String vipTemp = generateVirtualIp(server,i);
			Integer value = genHashSlot(vipTemp);
			treeMap.put(value,vipTemp);		
		}
	}
	
	/**
	 * 虚拟Ip生成逻辑，此处简单设为server+0~vipNumber-1
	 * @param server 真实服务器名称
	 * @param vipId 虚拟ip节点
	 * @return
	 */
	private String generateVirtualIp(String server,int vipId) {
		return server + ":" +vipId;
	}
	/**
	 * 生成32位Hash
	 * @param node 节点名称
	 * @return
	 */
	private int genHashSlot(String name) {
        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < name.length(); i++)
            hash = (hash ^ name.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;
	}
	
	/**
	 * 在Hash环上增加虚拟服务器
	 * 本考虑需要维护类中：consistencyHashResult,但该成员变量仅做展示使用,
	 * 且对其进行动态维护比较复杂,一致性Hash的应用场景可以接受一定程度上的缓存失效;故放弃对该成员变量进行维护。
	 * @param serverName
	 * @return
	 */
	public boolean addServer(String serverName) {
		boolean ifSuccess= serverLists.add(serverName);
		treeMap.replace(genHashSlot(serverName),serverName);
		return ifSuccess;
	}
	
	public boolean removeServer(String serverName) {
		boolean ifSuccess = serverLists.remove(serverName);
		removeServerInHashCycle(serverName);
		return ifSuccess;
	}
	/**
	 * 在Hash环上删除serverName的所有虚拟节点
	 * 本考虑需要维护类中：consistencyHashResult,但该成员变量仅做展示使用,
	 * 且对其进行动态维护比较复杂,一致性Hash的应用场景可以接受一定程度上的缓存失效;故放弃对该成员变量进行维护。
	 * @param serverName
	 */
	private void removeServerInHashCycle(String serverName) {
		for(int i = 0 ; i < vipCount ; i++ ) {
			String virtualServerNode = generateVirtualIp(serverName,i);
			Integer hashSlot = genHashSlot(virtualServerNode);
			if(virtualServerNode.equals(treeMap.get(hashSlot))) {
				treeMap.remove(hashSlot);
			}
		}		
	}
	
	/**
	 * 
	 * @param client 客户端Node
	 */
	public void recordConsistencyHash(String client){
		int clientNode = genHashSlot(client);
		//tailMap:Returns a view of the portion of this map whose keys are greater than or equal to clientNode key
		//返回大于或等于clientNode的key
	    SortedMap subMap = treeMap.tailMap(clientNode);
	    if(subMap.size() != 0) {
		    //找到第一个大于或等于clientNode的key,符合一致性Hash语义
	        int firstKey = (Integer)subMap.firstKey();
	        //获取到的是虚拟Ip节点,本例中写死了分隔方式为以  ":" 进行分隔，很丑。需要修改。
	        String virtualNode = (String)subMap.get(firstKey);
	        //获取到了实际节点
	        String actualNode = virtualNode.split(":")[0];
	        Integer result = consistencyHashResult.putIfAbsent(actualNode, new Integer(0));
	        if(null != result) {
	        	consistencyHashResult.put(actualNode, result + 1);
	        }
	    }else {//若为空集合，则为边界条件，找TreeMap中的最小节点
	    		firstKey = treeMap.firstKey();
	    	  String virtualNode = treeMap.get(firstKey);
	        //获取到了实际节点
	        String actualNode = virtualNode.split(":")[0];
	        Integer result = consistencyHashResult.putIfAbsent(actualNode, new Integer(0));
	        if(null != result) {
	        	consistencyHashResult.put(actualNode, result + 1);
	        }
	    }
	}
	
	public static void main(String[] args) {
		ConsistencyHash consistencyHash = new ConsistencyHash();
		SortedMap<Integer, String> testMap = consistencyHash.treeMap;
		for(int i =0 ; i < 1000000 ; i++) {
			consistencyHash.recordConsistencyHash(UUID.randomUUID().toString());
		}
		Set result = consistencyHash.consistencyHashResult.entrySet();
		result.stream().forEach(System.out::println);
	}
}