第五周作业

关注

发布于: 2020 年 11 月 23 日

用你熟悉的编程语言实现一致性 hash 算法。

算法接口：

public interface ConsistencyHash {
    /**     * 设置虚拟节点数量     * @param num     */    void setVirtualNodeNum(int num);
    /**     * 添加服务器节点     * @param service     */    void addService(String service);
    /**     * 批量添加     * @param services     */    void addServices(String[] services);

    /**     * 获取顺时针最近的服务器节点     * @param key     * @return     */    String getService(Object key);
}

复制代码

算法的具体实现：

public class ConsistencyHashImpl implements ConsistencyHash {
    private TreeMap<Integer, String> hashServices = new TreeMap<>();
    private int virtualNodeNum = 0;
    public static final String VIRTUAL_NODE_SEG = "V";
    @Override    public void setVirtualNodeNum(int num) {        this.virtualNodeNum = num;    }
    @Override    public void addService(String service) {        int hashcode = getHash(service);        hashServices.put(hashcode, service);
        addVirtualNode(service);    }
    private void addVirtualNode(String service) {        for (int i = 0; i < virtualNodeNum; i++) {            int hashcode = getHash(service + VIRTUAL_NODE_SEG + i);
            hashServices.put(hashcode, service);        }    }
    @Override    public void addServices(String[] services) {        Stream.of(services).forEach(this::addService);    }
    @Override    @Nullable    public String getService(Object key) {        if(hashServices.isEmpty()) {            return null;        }        int hashcode = getHash(key);
        String service = "";
        // 大于hashcode的数据，顺时针取第一个        SortedMap sortedMap = hashServices.tailMap(hashcode);        if (sortedMap != null && !sortedMap.isEmpty()) {            service = hashServices.get(sortedMap.firstKey());        } else {            service = hashServices.get(hashServices.firstKey());        }        if(service.contains(VIRTUAL_NODE_SEG)) {            service = service.split(VIRTUAL_NODE_SEG)[0];        }        return service;    }
    private int getHash(Object obj){        String str = obj.toString();        final int p = 16777619;        int hash = (int)2166136261L;        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 Test {
    public static void main(String[] args) {
        // 服务器节点        String[] services = {"127.0.0.1:8080", "127.0.0.2:8080", "127.0.0.3:8080", "127.0.0.4:8080",                "127.0.0.5:8080", "127.0.0.6:8080", "127.0.0.7:8080", "127.0.0.8:8080",                "127.0.0.9:8080", "127.0.0.10:8080"};
        // 记录每个服务器存储的数量        Map<String, Integer> count = new HashMap<>();
        // 一致性hash算法        ConsistencyHash consistencyHash = new ConsistencyHashImpl();        consistencyHash.setVirtualNodeNum(150);        consistencyHash.addServices(services);
        // 随机数key，        Random random = new Random();        for (int i = 0; i < 1000000; i++) {            int data = random.nextInt();            String service = consistencyHash.getService(data);
            if (count.containsKey(service)) {                count.put(service, (count.get(service) + 1));            } else {                count.put(service, 1);            }        }
        System.out.println(count);            }
}

复制代码

执行结果：

编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

标准差计算：

//标准差σ=sqrt(s^2)    public static double standardDiviation(int[] x) {        int m=x.length;        double sum=0;        for(int i=0;i<m;i++){//求和            sum+=x[i];        }        double dAve=sum/m;//求平均值        double dVar=0;        for(int i=0;i<m;i++){//求方差            dVar+=(x[i]-dAve)*(x[i]-dAve);        }        // 平均方差开平方        return Math.sqrt(dVar/m);    }