架构师训练营 Week5 - 课后作业
做业务实现多了,很久没有怎么接触算法代码了。参考了网上的实现花了接近一天才完成这个作业。
1. 一致性哈希环
这里不多说,老师在课上讲了。 上个图来表示下:
2. TreeMap 与 一致性Hash环
网上搜到的一致性hash实现大多都是通过TreeMap来实现的。感觉TreeMap展开是一条线,Root节点是最中间。有空研究下firstKey 和tailMap的逻辑再来扩充这部分的分析
3. 一致性Hash实现
https://github.com/SmileRR/Architect-001/tree/main/DistributeCache/src/main/java/org/eg
Consistent Hash Cluster实现
package org.eg;import org.eg.cache.Cluster;import org.eg.cache.Node;import org.eg.hash.HashAlgorithm;import java.util.ArrayList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;public class ConsistentHashCluster extends Cluster { private SortedMap<Long, Node> circle = new TreeMap<Long, Node>(); private final HashAlgorithm algorithm; private final int numberOfReplicies; public ConsistentHashCluster(HashAlgorithm algorithm, int numberOfReplicas) { this.algorithm = algorithm; this.numberOfReplicies = numberOfReplicas; } @Override public void addNode(Node node) { for (int i = 0; i < numberOfReplicies; i++) { circle.put(algorithm.hash(node.toString() + i), node); } } @Override public void removeNode(Node node) { for (int i = 0; i < numberOfReplicies; i++) { circle.remove(algorithm.hash(node.toString() + i)); } } @Override public List<Node> getNodes() { List<Node> nodes = new ArrayList<Node>(); for (Node node: circle.values()) { if (!nodes.contains(node)) nodes.add(node); } return nodes; } @Override public Node get(String key) { if (circle.isEmpty()) return null; long hash = algorithm.hash(key); //顺时针(正序)查找 if (! circle.containsKey(hash)) { SortedMap<Long, Node> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty()?circle.firstKey():tailMap.firstKey(); } return circle.get(hash); }}
4. 求100万KV, 10节点时的标准差
测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
这里引用了很多不同的Hash算法,对比在不同数量虚拟节点是标准差和性能影响。可以看出虚拟节点数量的增加在达到某个值后就不在明显。150并非是所有Hash算法的最有解,但也是达到了某一个数量级。
同时对比性能影响,算法和虚拟节点导致标准差变小,性能也随之下降。所以需要选一个折衷点。
准备的测试代码准本来打算对每一种Hash算法做遍历测试找出本算法的最优虚拟节点数,轻视了每一次计算所花的时间,在等待了5分钟后暂时放弃了寻找最优的想法。通过图表了解了他们的区别,在需要时再集中测试吧。
额外提出一点,很有意思。试了好几遍,用NATIVE HASH 在只有原始节点时T1显然很突兀的在性能指标中花了更多的时间,CRC32 HASH也是同样问题。
测试代码:
package org.eg;import org.eg.cache.Cluster;import org.eg.cache.Node;import org.eg.hash.HashAlgorithm;import java.util.UUID;public class TestCluster { static final int DATA_SIZE = 1000000; static final int NODE_SIZE = 10; static final int REPLICIES_RANGE = 500; public static void main(String[] args) { long start = System.currentTimeMillis(); int virtalNodes = 1; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 50; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 100; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 150; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 300; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 500; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes); virtalNodes = 1000; System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes); new TestCluster().testHashAlgorithm(virtalNodes);// new TestCluster().identifyNoOfReplicies(); System.out.println("Time spent: " + (System.currentTimeMillis() - start)); } // 测试各种Hash算法在100万K-V下 private void testHashAlgorithm(int replicies) { for (HashAlgorithm alg : HashAlgorithm.values()) { long start = System.currentTimeMillis(); Cluster cluster = new ConsistentHashCluster(alg, replicies); setup(cluster); long sdt = calcStandardDeviation(cluster); System.out.println( alg + ", " + sdt + ", " + (System.currentTimeMillis()- start)); } } //识别最优虚拟节点数量,待优化 private void identifyNoOfReplicies() { StringBuilder sb = new StringBuilder(); for (HashAlgorithm alg: HashAlgorithm.values() ) { long bestSDT = Long.MAX_VALUE; long bestNum = 1; for (int i = 1; i < REPLICIES_RANGE; i++) { long sdt = testHashAlgorithm(alg, i); if(bestSDT > sdt) { bestSDT = sdt; bestNum = i; } } System.out.println("Algorithm : " + alg + ", Best VirtualNodes: " + bestNum + ", StandardDeviation:" + bestSDT); } } private long testHashAlgorithm(HashAlgorithm alg, int noOfReplicies) { Cluster cluster = new ConsistentHashCluster(alg, noOfReplicies); setup(cluster); long sdt = calcStandardDeviation(cluster); return sdt; } private void setup(Cluster cluster) { for (int i = 0; i < NODE_SIZE; i++) { cluster.addNode(new Node("c" + i, "192.168.0." + i)); } for (int i = 0; i < DATA_SIZE; i++) { String key = UUID.randomUUID().toString() + i; String value = "value" + key; cluster.get(key).put(key, value); } } private long calcStandardDeviation(Cluster cluster) { long sum = 0; long avg = DATA_SIZE / NODE_SIZE; for (Node node : cluster.getNodes()) { sum += Math.pow((node.getData().size() - avg), 2); } long sdt = Math.round(Math.sqrt(sum / NODE_SIZE)); return sdt; }}
版权声明: 本文为 InfoQ 作者【冉】的原创文章。
原文链接:【http://xie.infoq.cn/article/bfbb277abc8994c1fc40b7d3b】。文章转载请联系作者。
冉
还未添加个人签名 2018.09.18 加入
还未添加个人简介
评论 (2 条评论)