架构师训练营第五周作业
发布于: 2020 年 10 月 25 日
1、用你熟悉的编程语言实现一致性 hash 算法。
public class ConsistentHash<T> {/*** Hash计算对象，用于自定义hash算法*/HashFunc hashFunc;/*** 复制的节点个数*/private final int numberOfReplicas;/*** 一致性Hash环*/private final SortedMap<Long, T> circle = new TreeMap<>();/*** 构造，使用Java默认的Hash算法* @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡* @param nodes 节点对象*/public ConsistentHash(int numberOfReplicas, Map<T, Integer> nodes) {this.numberOfReplicas = numberOfReplicas;this.hashFunc = key -> {// return fnv1HashingAlg(key.toString());return md5HashingAlg(key.toString());};//初始化节点for (T node : nodes.keySet()) {add(node);}}/*** 构造* @param hashFunc hash算法对象* @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡* @param nodes 节点对象*/public ConsistentHash(HashFunc hashFunc, int numberOfReplicas, Collection<T> nodes) {this.numberOfReplicas = numberOfReplicas;this.hashFunc = hashFunc;//初始化节点for (T node : nodes) {add(node);}}/*** 增加节点<br>* 每增加一个节点，就会在闭环上增加给定复制节点数<br>* 例如复制节点数是2，则每调用此方法一次，增加两个虚拟节点，这两个节点指向同一Node* 由于hash算法会调用node的toString方法，故按照toString去重** @param node 节点对象*/public void add(T node) {// circle.put(hashFunc.hash(node.toString()), node);for (int i = 0; i <= numberOfReplicas; i++) {circle.put(hashFunc.hash(node.toString() + i), node);}}/*** 移除节点的同时移除相应的虚拟节点** @param node 节点对象*/public void remove(T node) {for (int i = 0; i < numberOfReplicas; i++) {circle.remove(hashFunc.hash(node.toString() + i));}}/*** 获得一个最近的顺时针节点** @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点* @return 节点对象*/public T get(Object key) {if (circle.isEmpty()) {return null;}long hash = hashFunc.hash(key);if (!circle.containsKey(hash)) {//返回此映射的部分视图，其键大于等于 hashSortedMap<Long, T> tailMap = circle.tailMap(hash);hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}//正好命中return circle.get(hash);}/*** 使用MD5算法* @param key* @return*/private static long md5HashingAlg(String key) {MessageDigest md5 = null;try {md5 = MessageDigest.getInstance("MD5");md5.reset();md5.update(key.getBytes());byte[] bKey = md5.digest();long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF);return res;} catch (NoSuchAlgorithmException e) {e.printStackTrace();}return 0L;}/*** 使用FNV1hash算法* @param key* @return*/private static long fnv1HashingAlg(String key) {final int p = 16777619;int hash = (int) 2166136261L;for (int i = 0; i < key.length(); i++)hash = (hash ^ key.charAt(i)) * p;hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;return hash;}/*** Hash算法对象，用于自定义hash算法*/public interface HashFunc {public Long hash(Object key);}}
复制代码
2、编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
public class Test extends TestCase {
private ConsistentHash<String> consistentHashing; private static Map<String, Integer> nodes = new HashMap<>();
public Test(String testName) { super(testName); for (int i = 0; i < 10; i++) { nodes.put("192.168.0." + (i + 1), i ); } }
public static TestSuite suite() { return new TestSuite(Test.class); }
public void testHash() { //无虚拟节点 goHash(0); //10虚拟节点 goHash(10); goHash(100); goHash(1000); goHash(10000); goHash(100000); }
public void goHash(int virNUm) { consistentHashing = new ConsistentHash<>(virNUm, nodes);
int[] counters = new int[nodes.size()]; for (int i = 0; i < 1000000; i++) { String node = UUID.randomUUID().toString(); String serverIp = consistentHashing.get(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] 53290次路由到结点[192.168.0.2] 18649次路由到结点[192.168.0.3] 254214次路由到结点[192.168.0.4] 24436次路由到结点[192.168.0.5] 205070次路由到结点[192.168.0.6] 66066次路由到结点[192.168.0.7] 42079次路由到结点[192.168.0.8] 272557次路由到结点[192.168.0.9] 10908次路由到结点[192.168.0.10] 52731次0虚拟节点标准差：14654.29507004687
路由到结点[192.168.0.1] 82794次路由到结点[192.168.0.2] 78577次路由到结点[192.168.0.3] 105079次路由到结点[192.168.0.4] 119982次路由到结点[192.168.0.5] 111965次路由到结点[192.168.0.6] 131697次路由到结点[192.168.0.7] 130103次路由到结点[192.168.0.8] 60297次路由到结点[192.168.0.9] 126026次路由到结点[192.168.0.10] 53480次10虚拟节点标准差：14654.29507004687
路由到结点[192.168.0.1] 86344次路由到结点[192.168.0.2] 104864次路由到结点[192.168.0.3] 97530次路由到结点[192.168.0.4] 98138次路由到结点[192.168.0.5] 95254次路由到结点[192.168.0.6] 104830次路由到结点[192.168.0.7] 115565次路由到结点[192.168.0.8] 86401次路由到结点[192.168.0.9] 114282次路由到结点[192.168.0.10] 96792次100虚拟节点标准差：9523.838511860646
路由到结点[192.168.0.1] 97853次路由到结点[192.168.0.2] 100106次路由到结点[192.168.0.3] 98878次路由到结点[192.168.0.4] 96620次路由到结点[192.168.0.5] 102272次路由到结点[192.168.0.6] 98587次路由到结点[192.168.0.7] 101002次路由到结点[192.168.0.8] 98077次路由到结点[192.168.0.9] 103105次路由到结点[192.168.0.10] 103500次1000虚拟节点标准差：2259.5495126241426路由到结点[192.168.0.1] 100166次路由到结点[192.168.0.2] 99953次路由到结点[192.168.0.3] 99424次路由到结点[192.168.0.4] 98537次路由到结点[192.168.0.5] 101740次路由到结点[192.168.0.6] 100498次路由到结点[192.168.0.7] 100824次路由到结点[192.168.0.8] 100985次路由到结点[192.168.0.9] 99095次路由到结点[192.168.0.10] 98778次10000虚拟节点标准差：986.8647323721726路由到结点[192.168.0.1] 99652次路由到结点[192.168.0.2] 100449次路由到结点[192.168.0.3] 100534次路由到结点[192.168.0.4] 99458次路由到结点[192.168.0.5] 100133次路由到结点[192.168.0.6] 99463次路由到结点[192.168.0.7] 100392次路由到结点[192.168.0.8] 99981次路由到结点[192.168.0.9] 100235次路由到结点[192.168.0.10] 99703次100000虚拟节点标准差：387.9613382799889复制代码
虚拟节点达到 10 个时标准差只有 387，是虚拟节点越多越好？越多越稳定？
划线
评论
复制
发布于: 2020 年 10 月 25 日阅读数: 17
四夕晖
关注
还未添加个人签名 2018.01.16 加入
还未添加个人简介
评论