架构师训练营 - 第五周作业

关注
发布于: 2020 年 10 月 25 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
代码实现
@FunctionalInterface
public interface HashFunction {
    Integer hash(String key);
}
﻿
public class Fnv1Function implements HashFunction {
    @Override
    public Integer hash(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;
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
}
﻿
@AllArgsConstructor
@Getter
@Setter
public class Node {
﻿
    private String ip;
    private String name;
}
﻿
public class ConsistentHash {
    private HashFunction hashFunction;
    private int numberOfReplicas;
    private SortedMap<Integer, Node> circle = new TreeMap<>();
    public ConsistentHash(HashFunction hashFunction,
                          int numberOfReplicas,
                          Collection<Node> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        for (Node node : nodes) {
            add(node);
        }
    }
    public void add(Node node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(this.hashFunction.hash(getKey(node, i)), node);
        }
    }
    public void remove(Node node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(getKey(node, i));
        }
    }
    private String getKey(Node node, int virtualNode) {
        StringBuilder builder = new StringBuilder(node.getIp())
                .append("&&")
                .append("VIRTUAL_NODE=")
                .append(virtualNode);
        return builder.toString();
    }
    public Node get(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        Integer hashCode = hashFunction.hash(key);
        if (!circle.containsKey(hashCode)) {
            SortedMap<Integer, Node> tailMap = circle.tailMap(hashCode);
            hashCode = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hashCode);
    }
}
﻿
public class ConsistentHashTest {
    private static final String IP_PREFIX = "127.0.0.";
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();// 每台真实机器节点上保存的记录条数
        List<Node> realNodes = new ArrayList<>();
        for (int i = 1; i < 11; i++) {
            String ip = IP_PREFIX + i;
            String nodeName = "NODE_" + i;
            map.put(ip, 0);
            realNodes.add(new Node(ip, nodeName));
        }
        ConsistentHash consistentHash = new ConsistentHash(new Fnv1Function(), 100, realNodes);
        // 将1000000条记录存储到10台机器节点
        for (int i = 0; i < 1000000; i++) {
            String data = UUID.randomUUID().toString() + i;
            Node node = consistentHash.get(data);
            //do something
            map.put(node.getIp(), map.get(node.getIp()) + 1);
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("IP为：" + entry.getKey() + "; 总条数为：" + entry.getValue());
        }
        Collection<Integer> values = map.values();
        Integer[] array = values.toArray(new Integer[values.size()]);
        System.out.println("标准差为：" + calculateStandardDeviation(array));
    }
    public static double calculateStandardDeviation(Integer[] arr) {
        int m = arr.length;
        double sum = 0;
        for (int i = 0; i < m; i++) {//求和
            sum += arr[i];
        }
        double dAve = sum / m;//求平均值
        double dVar = 0;
        for (int i = 0; i < m; i++) {//求方差
            dVar += (arr[i] - dAve) * (arr[i] - dAve);
        }
        //reture Math.sqrt(dVar/(m-1));
        return Math.sqrt(dVar / m);
    }
}
计算结果
IP为：192.168.0.2; 总条数为：96433
IP为：192.168.0.1; 总条数为：120307
IP为：192.168.0.4; 总条数为：85154
IP为：192.168.0.3; 总条数为：105413
IP为：192.168.0.10; 总条数为：94731
IP为：192.168.0.9; 总条数为：106091
IP为：192.168.0.6; 总条数为：96966
IP为：192.168.0.5; 总条数为：83885
IP为：192.168.0.8; 总条数为：105772
IP为：192.168.0.7; 总条数为：105248
标准差为：10341.27909883492
﻿