架构师训练营 Week5 - 课后作业

 关注
发布于: 2020 年 10 月 25 日
  做业务实现多了，很久没有怎么接触算法代码了。参考了网上的实现花了接近一天才完成这个作业。
﻿
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;
    }
}
﻿