架构 2 期 - 第五周作业（1）

关注

发布于: 2020 年 11 月 22 日

﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
一致性hash算法实现思路
定义真实节点
定义虚拟节点数量和名称规则
连接虚拟节点
实现节点定位
﻿
import java.util.LinkedList;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashingVirtualNode {
    /**
     * 虚拟节点树
     */
    private SortedMap<Integer,String> vNodes = new TreeMap();
    /**
     * 真实节点
     */
    private LinkedList<String> realNodes;
    /**
     * 一个真实节点对应的虚拟节点数量
     */
    private int virtualNums;
    /**
     * 虚拟节点连接符
     */
    private static final String VIRTUAL_NODE_SUFFIX = "-";
    /**
     * 构造器初始化hash环
     * @param nodes
     * @param vn
     */
    public ConsistentHashingVirtualNode(LinkedList<String> nodes,int vn){
        this.realNodes = nodes;
        this.virtualNums = vn;
        initP2Vmapping();
    }
    /**
     * 构建hash环主方法，初始化虚拟节点与物理节点的映射关系；
     * 映射的虚拟节点采用TreeMap排序，利用二叉树特性方便查找节点；
     * map中key存储虚拟节点hash值，value存储对应的实体节点；虚拟节点的hash值来自于实体节点字符拼接；
     */
    private void initP2Vmapping(){
        for(String node:realNodes){
            for( int i=0;i< virtualNums;i++ ){
                String vName = getVirtualNodeNameByIndex(node,i);
                vNodes.put(hash(vName),node);
            }
        }
    }
    /**
     * 拼接虚机节点
     * @param nodeName
     * @param index
     * @return
     */
    private String getVirtualNodeNameByIndex(String nodeName, int index){
        return new StringBuffer(nodeName)
                .append(VIRTUAL_NODE_SUFFIX)
                .append(index)
                .toString();
    }
    /**
     * hash算法，使用MD5散列。
     * @param k
     * @return
     */
    private int hash(String k) {
        return MD5Util.md5HashCode(k);
    }
    /**
     * 定位被路由到的实际节点
     * @param p
     * @return
     */
    public String locate(String p){
        SortedMap<Integer,String> toTailed =  vNodes.tailMap(hash(p));
        Integer key = toTailed.isEmpty()?vNodes.firstKey():toTailed.firstKey();
        return vNodes.get(key);
    }
    public static void main(String[] args) {
        LinkedList<String> realNodes = new LinkedList<>();
        realNodes.add("192.168.1.1");
        realNodes.add("192.168.1.3");
        realNodes.add("192.168.1.5");
        realNodes.add("192.168.1.7");
        realNodes.add("192.168.1.9");
        ConsistentHashingVirtualNode consis = new ConsistentHashingVirtualNode(realNodes,12);
    }
}
﻿