架构师训练营 No.5 周作业

关注
发布于: 2020 年 07 月 08 日
用熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
一致性Hash算法是对2^32取模。简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下：
﻿
整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。
一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，其环分布如下： 
﻿
 
此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。
代码_Hash算法：
public class HashUtils {
  private static final long PSART = 16777619L;
	private static final long PMULT = 2166136261L;
	public static long getHash(String str) {
		long p = PSART;
		long hash = PMULT;
		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 class MathUtils {
	public static double standardDiviation(int[] x) {
		int m = x.length;
		int sum = 0;
		// 求和
		for (int i = 0; i < m; i++) {
			sum += x[i];
		}
		// 求平均值
		int dAve = sum / m;
		int dVar = 0;
		for (int i = 0; i < m; i++) {// 求方差
			dVar += Math.pow(x[i] - dAve, 2);
		}
		return Math.sqrt(dVar / m);
	}
}
一致性HASH算法：
public class ConsistentHashing {
	private List<String> realNodes = new LinkedList<String>();
	private SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
	private int virtualNum = 0;
	
	public ConsistentHashing() {
	}
	public ConsistentHashing(List<String> nodes, int virtualNum) {
		realNodes.addAll(nodes);
		this.virtualNum = virtualNum;
		init();
	}
	public ConsistentHashing(Map<String, Integer> nodes) {
		realNodes.addAll(nodes.keySet());
	}
	
	public void init() {
		sortedMap.clear();
		for (String node : realNodes) {
			String realNode = node + "_0";
			sortedMap.put((int) HashUtils.getHash(realNode), realNode);
			for (int i = 1; i <= virtualNum; i++) {
				String virtualNode = node + "_" + String.valueOf(i);
				sortedMap.put( (int) HashUtils.getHash(virtualNode), virtualNode);
			}
		}
	}
	
	public String getServer(String node) {
		int hash = (int) HashUtils.getHash(node);
		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
		if(!subMap.isEmpty()) {
			Integer i = subMap.firstKey();
			String virtualNode = subMap.get(i);
			return virtualNode.substring(0, virtualNode.indexOf("_"));
		}
		return realNodes.get(0);
	}
	
	public int getVirtualNum() {
		return virtualNum;
	}
	public void setVirtualNum(int virtualNum) {
		this.virtualNum = virtualNum;
	}
	public List<String> getRealNodes() {
		return realNodes;
	}
	public void addNode(String node) {
		realNodes.add(node);
	}
	public void removeNode(String node) {
		realNodes.remove(node);
	}	
}
﻿
测试代码：
public class AppTest extends TestCase {
	private ConsistentHashing consistentHashing;
	private static Map<String, Integer> nodes = new HashMap<String, Integer>();
	
	public AppTest(String testName) {
		super(testName);
		for(int i=0;i<10;i++) {
			nodes.put( "192.168.0."+(i+1), i);
		}
		consistentHashing = new ConsistentHashing(nodes);
	}
	public static Test suite() {
		return new TestSuite(AppTest.class);
	}
	
	public void testHash() {
		goHash(0);//无虚拟节点
		goHash(10);//10虚拟节点
		goHash(100);
		goHash(1000);
	}
	
	public void goHash(int virNUm) {
		consistentHashing.setVirtualNum(virNUm);
		consistentHashing.init();
		
		int[] counters =  new int[nodes.size()];
		for (int i = 0; i < 1000000; i++) {
			String node = UUID.randomUUID().toString();
			String serverIp = consistentHashing.getServer(node);			
			counters[nodes.get(serverIp)]++;
		}
		
		for (int i = 0; i < counters.length; i++) {
			System.out.println("路由到结点[192.168.0."+(i+1)+"] "+ counters[i]+"次");
		}
		double dsv = MathUtils.standardDiviation(counters);
		System.out.println(virNUm + "虚拟节点标准差："+ dsv);
		
		assertTrue(true);
	}
}
﻿
测试结果：
路由到结点[192.168.0.1] 73711次
路由到结点[192.168.0.2] 88132次
路由到结点[192.168.0.3] 38560次
路由到结点[192.168.0.4] 81524次
路由到结点[192.168.0.5] 102842次
路由到结点[192.168.0.6] 213723次
路由到结点[192.168.0.7] 36849次
路由到结点[192.168.0.8] 53248次
路由到结点[192.168.0.9] 273023次
路由到结点[192.168.0.10] 38388次
0虚拟节点 标准差：14654.29507004687
﻿
路由到结点[192.168.0.1] 148980次
路由到结点[192.168.0.2] 95794次
路由到结点[192.168.0.3] 86326次
路由到结点[192.168.0.4] 36654次
路由到结点[192.168.0.5] 89828次
路由到结点[192.168.0.6] 110975次
路由到结点[192.168.0.7] 93610次
路由到结点[192.168.0.8] 84907次
路由到结点[192.168.0.9] 105570次
路由到结点[192.168.0.10] 147356次
10虚拟节点 标准差：14654.29507004687
﻿
路由到结点[192.168.0.1] 104468次
路由到结点[192.168.0.2] 105734次
路由到结点[192.168.0.3] 86492次
路由到结点[192.168.0.4] 95853次
路由到结点[192.168.0.5] 103345次
路由到结点[192.168.0.6] 97413次
路由到结点[192.168.0.7] 112574次
路由到结点[192.168.0.8] 87883次
路由到结点[192.168.0.9] 102369次
路由到结点[192.168.0.10] 103869次
100虚拟节点 标准差：7719.426986506188
﻿
路由到结点[192.168.0.1] 95187次
路由到结点[192.168.0.2] 97355次
路由到结点[192.168.0.3] 103488次
路由到结点[192.168.0.4] 97147次
路由到结点[192.168.0.5] 104259次
路由到结点[192.168.0.6] 97661次
路由到结点[192.168.0.7] 100685次
路由到结点[192.168.0.8] 106974次
路由到结点[192.168.0.9] 98206次
路由到结点[192.168.0.10] 99038次
1000虚拟节点 标准差：3568.2843216313354
﻿
﻿
发布于: 2020 年 07 月 08 日阅读数: 61
连增申

关注
还未添加个人签名 2020.04.02 加入
还未添加个人简介
发布
暂无评论
创作场景

架构师训练营 No.5 周作业

连增申

评论
