2020-07-04- 第五周作业

关注
发布于: 2020 年 07 月 08 日
作业﻿
﻿
答：
1 一致性hash算法实现﻿
一致性hash算法步骤
﻿
（1）使用hash算法计算出10个物理服务器结点对应的虚拟节点hashcode，并将这些虚拟节点尽量均匀分布在hash环上。
（2）同样使用hash算法，计算KV数据中键的hashcode，并其映射到hash环上。
（3）从数据映射hash环的位置开始顺时针查找，找到一个虚拟节点，要求该节点的hashcode大于等于KV数据中键的hashcode。
（4）找到该虚拟节点对应的物理服务器节点，并将该KV数据存储到该物理节点上。
﻿
一致性hash算法实现（JAVA）
代码清单1：ConsistencyHash.java
一致性算法实现类，构造方法有三个输入：hashcode算法，物理节点列表，每个物理节点的虚拟节点个数。包括了添加和删除物理节点方法，以及getNode通过KV中键的值获需要存储的物理节点对象。
package demo.algorithm;
import demo.hash.HashMethod;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * 一致性hash算法
 * @param <T>
 */
public class ConsistencyHash<T> {
    private Collection nodes;
    private HashMethod hashMethod;
    private int virtualNodesCount;
    /**
     * hash环上的虚拟节点
     */
    private SortedMap<Integer, T> hashRing = new TreeMap<>();
    /**
     * 构造方法
     * @param hashMethod  hash算法
     * @param nodes       物理节点集合
     * @param virtualNodesCount   单个物理节点在hash环上的虚拟节点个数
     */
    public ConsistencyHash(HashMethod hashMethod, Collection<T> nodes, int virtualNodesCount){
        this.hashMethod = hashMethod;
        this.virtualNodesCount = virtualNodesCount;
        for(T n : nodes) {
            addNode(n);
        }
    }
    /**
     * 添加节点
     * @param node 节点对象
     */
    public void addNode(T node) {
        for(int i = 0; i < virtualNodesCount; i++) {
            hashRing.put(hashMethod.hash(i + "#" +node.toString() + "#" + i), node);
        }
    }
    /**
     * 删除节点
     * @param node 待删除结点
     */
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodesCount; i++) {
            hashRing.remove(hashMethod.hash(node.toString() + i));
        }
    }
    /**
     * 获取物理节点
     * @param key 键
     * @return
     */
    public T getNode(Object key) {
        int hash = hashMethod.hash(key);
        for(int c : hashRing.keySet()) {
            if(hash <= c) {
                return hashRing.get(c);
            }
        }
        return hashRing.get(hashRing.firstKey());
    }
}
代码清单2：Md5HashMethod.java
使用MD5算法计算出对象的hashcode，因hashcode可能为负数，使用了Integer.MAX_VALUE进行与操作去除符号。
package demo.hash;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class Md5HashMethod implements HashMethod {
    @Override
    public int hash(Object obj) {
        byte[] secretBytes = null;
        try {
            secretBytes = MessageDigest.getInstance("md5").digest(
                    obj.toString().getBytes());
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("没有这个md5算法！");
        }
        String md5code = new BigInteger(1, secretBytes).toString(16);
        return md5code.hashCode() & Integer.MAX_VALUE;
    }
}
代码清单3：Node.java
package demo.node;
public class Node {
    String nodeName;
    public Node(String nodeName) {
        this.nodeName = nodeName;
    }
    public String toString() {
        return this.nodeName;
    }
}
﻿
2 测试算法的负载均衡性代码清单4：Main.java
Main.main方法使用Md5Hash算法计算hashcode，resMap记录每个节点上存储的KV个数。使用10个物理节点，每个物理节点有80个虚拟节点。最终打印出每个物理节点上存储的KV个数，并计算样本的标准差。
package demo;
import demo.algorithm.ConsistencyHash;
import demo.hash.HashMethod;
import demo.hash.Md5HashMethod;
import demo.hash.NormalHashMethod;
import demo.node.Node;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;
public class Main {
    public static void main(String[] args) {
        HashMethod hashMethod = new Md5HashMethod();
        Map<Node, Integer> resMap = new LinkedHashMap<>();
        List<Node> nodes = new ArrayList<>();
        for(int i = 0; i < 10; i++) {
            String nodeName = i + "NODE" + i;
            Node n = new Node(nodeName);
            nodes.add(n);
            resMap.put(n, 0);
        }
        ConsistencyHash<Node> consistencyHash = new ConsistencyHash(hashMethod, nodes, 80);
        IntStream.range(0, 1000000).forEach(idx -> {
            Node n = consistencyHash.getNode(idx);
            resMap.put(n, resMap.get(n) + 1);
        });
        // 计算标准差
        int avg = 100000;
        int temp = 0;
        for(Node n: resMap.keySet()) {
            System.out.println(n.toString() + " : " + resMap.get(n));
            temp += (resMap.get(n) - avg) * (resMap.get(n) - avg);
        }
        int s = temp / 10;
        System.out.println("方差：" + s);
        System.out.println("标准差：" + Math.sqrt(s));
    }
}
实验结果
0NODE0 : 101213
1NODE1 : 92116
2NODE2 : 104745
3NODE3 : 102025
4NODE4 : 103392
5NODE5 : 90734
6NODE6 : 99023
7NODE7 : 97158
8NODE8 : 104955
9NODE9 : 104639
方差：24271273
标准差：4926.588373306623
一致性hash算法最重要的核心就是要保证虚拟节点hashCode的均衡性。只要虚拟机结点在hash环上是均匀分布的，那就可以保证这些KV数据就能均匀分布在这10个服务器节点上，其标准差就会很小。
﻿
而影响算法均衡性的一个最主要因素就是hash函数。hash函数的主要作用就是将虚拟节点和KV数据的key值尽量均匀分布在hash环上，注意是尽量均匀分布。实际上由于hash函数的不均衡性，以及KV数据的随机性，想要将hashCode均匀分布是较难的。
﻿
根据不同的场景hash函数也有所不同，主要的有：直接定址法、数字分析法、折叠法、平方取中法、减去法、基数转换法、除留余数法、随机数法、字符串数值hash法、旋转法等。
﻿
除了需要构造hash函数外，hash冲突也是需要解决的一个问题，尽可能的将hash冲突减少到最低。
﻿