架构师训练营作业 -20200705

caibird1984
关注
发布于: 2020 年 07 月 05 日
1、用你熟悉的编程语言实现一致性hash算法
﻿
以下代码通过JAVA语言实现：
﻿
/**
 * 分布式缓存实现
 * @author xiaofy
 */
public class MyCache {
﻿
	/**
	 * 保存每个虚拟节点与服务器名称的对应关系
	 */
	private TreeMap<Integer, String> nodes = new TreeMap<Integer, String>();
	
	/**
	 * 保存每个服务器中保存的数据量
	 */
	private Map<String, Long> serverDataMap = new HashMap<String, Long>();
	
	/**
	 * 模拟添加数据
	 * @param key 数据的键
	 */
	public void addData(String key) {
		if(key == null || "".equals(key.trim())) {
			return;
		}
		
		Integer nodeHash = selectNode(key);
		String serverName = nodes.get(nodeHash);
		if(serverName != null && !"".equals(serverName.trim())) {
			addServerDataCount(serverName);
		}
	}
	
	/**
	 * 服务器内的数据量加1
	 * @param serverName 服务器名称
	 */
	private void addServerDataCount(String serverName) {
		long dataCount = 0;
		if(serverDataMap.containsKey(serverName)) {
			dataCount = serverDataMap.get(serverName);
		}
		
		dataCount++;
		serverDataMap.put(serverName, dataCount);
	}
	
	/**
	 * 选择数据存储节点
	 * @param key 数据的键
	 * @return 选择的节点哈希值
	 */
	private Integer selectNode(String key) {
		int keyHash = key.hashCode();
		SortedMap<Integer, String> node = nodes.tailMap(keyHash, true);
		if(!node.isEmpty()) {
			return node.firstKey();
		}
		return nodes.firstKey();
	}
﻿
	/**
	 * 构造虚拟节点名称
	 * @param serverName 服务器名称
	 * @param nodeIndex 节点编号
	 * @return 虚拟节点名称
	 */
	private String buildNodeName(String serverName, int nodeIndex) {
		return serverName + "_" + nodeIndex;
	}
	
	/**
	 * 计算数据存储数量的标准差
	 * @return 数据存储数量的标准差
	 */
	public double getStandDeviation() {
		double sum = 0;
		for(String key : serverDataMap.keySet()) {
			sum += serverDataMap.get(key);
		}
		
		long total = 0;
		double average = sum / serverDataMap.size();
		for(String key : serverDataMap.keySet()) {
			long count = serverDataMap.get(key);
			total += (count-average)*(count-average);
		}
		
		double result = Math.sqrt(total/serverDataMap.size());
		return result;
	}
	
	/**
	 * 构造函数
	 * @param serverList 服务器列表
	 * @param nodesPerServer 每台服务器的虚拟节点数
	 */
	public MyCache(List<String> serverList, int nodesPerServer) {
		initNodes(serverList, nodesPerServer);
	}
	
	/**
	 * 初始化每个服务器的虚拟节点信息
	 * @param serverList 服务器列表
	 * @param nodesPerServer 每台服务器的虚拟节点数
	 */
	private void initNodes(List<String> serverList, int nodesPerServer) {
		for(int i = 0; i < serverList.size(); i++) {
			String serverName = serverList.get(i);
			for(int j = 0; j < nodesPerServer; j++) {
				String nodeName = buildNodeName(serverName, j);
				nodes.put(nodeName.hashCode(), serverName);
			}
		}
	}
}
﻿
﻿
2、编写测试用例测试这个算法，测试100万KV数据，10个服务器节点的情况下，计算这些KV数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性
﻿
以每台服务器划分100个虚拟节点，编写简单的测试程序，如下：
﻿
/**
 * 测试程序
 * @author xiaofy
 */
public class CacheSampleMain {
	
	/**
	 * 每台服务器的虚拟节点数
	 */
	private static final int NODECOUNTPER_SERVER = 100;
	
	/**
	 * 模拟添加到缓存的记录数
	 */
	private static final int DATA_COUNT = 1000000;
﻿
	public static void main(String[] args) {
		List<String> serverList = createServerList();
		MyCache myCache = new MyCache(serverList, NODECOUNTPER_SERVER);
		
		for(int i = 0; i < DATA_COUNT; i++) {
			//模拟数据的KEY
			String key = UUID.randomUUID().toString().replace("-", "");
			myCache.addData(key);
		}
		
		double standardDeviation = myCache.getStandDeviation();
		System.out.println("标准差为：" + standardDeviation);
	}
﻿
	/**
	 * 构造服务器列表
	 * @return 服务器IP列表
	 */
	private static List<String> createServerList() {
		List<String> list = new ArrayList<String>();
		for(int i = 1; i <= 10; i++) {
			String serverName = "192.168.0." + i;
			list.add(serverName);
		}
		return list;
	}
}
﻿
测试结果，标准差为：
﻿