极客大学架构师训练营第五周作业

关注
发布于: 2020 年 11 月 22 日
一、用你熟悉的编程语言实现一致性 hash 算法。大致思路：
定义节点抽象接口，将实际物理节点和会用到的虚拟节点抽象为节点
定义hash函数接口，便于自定义扩展更好的hash计算
虚拟节点是为优化一致性hash可能的不均衡引入，实际上第一个虚拟节点即为物理节点
利用Java集合中的TreeMap特性实现一致性hash算法
/**
 * 抽象节点
 * @author wellman
 **/
public interface Node {
    /**
     * 节点关键字，用于唯一确定一个节点
     * @return 节点关键字
     * @author wellman
     **/
    String getKey();
}
﻿
/**
 * 虚拟节点
 * @author wellman
 **/
public class VirtualNode<T extends Node> implements Node {
    /**
     * 所属实际物理节点
     **/
    private final T physicalNode;
    /**
     * 物理节点下的子索引
     **/
    private final int subIndex;
    public VirtualNode(T physicalNode, int subIndex) {
        this.physicalNode = physicalNode;
        this.subIndex = subIndex;
    }
    @Override
    public String getKey() {
        return physicalNode.getKey() + ":" + subIndex;
    }
    /**
     * 判断当前虚拟节点是否属于指定的物理节点
     * @param pNode 物理节点
     * @return true or false
     * @author wellman
     **/
    public boolean isVirtualNodeOf(T pNode) {
        return physicalNode.getKey().equalsIgnoreCase(pNode.getKey());
    }
    /**
     * 返回当前虚拟节点对应的物理节点
     * @return 物理节点
     * @author wellman
     **/
    public T getPhysicalNode() {
        return physicalNode;
    }
}
﻿
/**
 * Hash计算的函数接口
 * @author wellman
 **/
public interface HashFunction {
    /**
     * 计算hash值
     * @param key 关键字
     * @return hash值
     * @author wellman
     **/
    long hash(String key);
}
﻿
/**
 * 使用MD5计算hash值
 * @author wellman
 **/
public class MD5HashFunction implements HashFunction {
    private MessageDigest instance;
    public MD5HashFunction() {
        try {
            instance = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
    }
    @Override
    public long hash(String key) {
        instance.reset();
        instance.update(key.getBytes());
        byte[] digest = instance.digest();
        long h = 0;
        for (int i = 0; i < 4; i++) {
            h <<= 8;
            h |= ((int) digest[i]) & 0xFF;
        }
        return h;
    }
}
﻿
/**
 * 一致性Hash路由器
 * @author wellman
 **/
public class ConsistentHashRouter<T extends Node> {
    /**
     * 节点存储对象
     * Key为节点键计算的Hash值
     * Value为对应的节点，这里的节点是虚拟节点，考虑一致性Hash分配均衡性问题引入虚拟节点，物理节点对应第一个虚拟节点
     * 一致性Hash算法是一个 2^32 大小的数组，TreeMap的容量是 int 修饰的，大小相等
     **/
    private final SortedMap<Long, VirtualNode<T>> HASH_RING = new TreeMap<>();
    /**
     * 默认用MD5进行Hash，支持自定义Hash函数
     **/
    private final HashFunction hashFunction;
    /**
     * 实例化一致性Hash路由器
     * @param physicalNodeList 物理节点列表
     * @param virtualNodeNum 指定的虚拟节点数量
     * @author wellman
     **/
    public ConsistentHashRouter(Collection<T> physicalNodeList, int virtualNodeNum) {
        this(physicalNodeList, virtualNodeNum, new MD5HashFunction());
    }
    /**
     * 实例化一致性Hash路由器
     * @param physicalNodeList 物理节点列表
     * @param virtualNodeNum 指定的虚拟节点数量
     * @param hashFunction Hash函数
     * @author wellman
     **/
    public ConsistentHashRouter(Collection<T> physicalNodeList, int virtualNodeNum, HashFunction hashFunction) {
        if (physicalNodeList == null || physicalNodeList.isEmpty()) {
            throw new IllegalArgumentException("请指定物理节点");
        }
        if (hashFunction == null) {
            throw new IllegalArgumentException("请指定Hash实现");
        }
        this.hashFunction = hashFunction;
        physicalNodeList.forEach(node -> {
            addNode(node, virtualNodeNum);
        });
    }
    /**
     * 根据指定的key，路由到具体的物理节点
     * @param routeKey 路由键
     * @return 根据一致性Hash算法匹配到的实际节点
     * @author wellman
     **/
    public Node route(String routeKey) {
        if (routeKey == null || "".equals(routeKey)) {
            throw new IllegalArgumentException("路由键不能为空");
        }
        if (HASH_RING.isEmpty()) {
            return null;
        }
        // 计算hash值
        Long hashCode = hashFunction.hash(routeKey);
        // 利用TreeMap特性，顺时针找到比当前key大的第一个节点剩余的部分
        SortedMap<Long,VirtualNode<T>> tailMap = HASH_RING.tailMap(hashCode);
        // 如果节点不是空，则返回第一个节点，否则返回整个Hash环的第一个节点
        Long nodeHashCode = !tailMap.isEmpty() ? tailMap.firstKey() : HASH_RING.firstKey();
        // 返回节点对应的实际物理节点
        return HASH_RING.get(nodeHashCode).getPhysicalNode();
    }
    /**
     * 添加节点，支持在运行过程中动态添加节点，根据一致性Hash特性，添加节点后，只会影响新增节点与邻近老节点之间的数据
     * @param physicalNode 物理节点
     * @param virtualNodeNum 虚拟节点数量
     * @author wellman
     **/
    public void addNode(T physicalNode, int virtualNodeNum) {
        if (virtualNodeNum < 0) {
            throw new IllegalArgumentException("错误的虚拟节点数:" + virtualNodeNum);
        }
        int maxIdx = getMaxIndexFromExistNode(physicalNode);
        for (int i = 0; i < virtualNodeNum; i++) {
            VirtualNode<T> vNode = new VirtualNode<>(physicalNode, i + maxIdx);
            HASH_RING.put(hashFunction.hash(vNode.getKey()), vNode);
        }
    }
    /**
     * 删除节点，比如节点下线
     * 删除是根据物理节点进行删除，所以需要遍历，找到物理节点对应的所有虚拟节点全部删除
     * @param physicalNode 物理节点
     * @author wellman
     **/
    public void removeNode(T physicalNode) {
        Iterator<Long> it = HASH_RING.keySet().iterator();
        while (it.hasNext()) {
            Long key = it.next();
            VirtualNode<T> virtualNode = HASH_RING.get(key);
            if (virtualNode.isVirtualNodeOf(physicalNode)) {
                it.remove();
            }
        }
    }
    /**
     * 获取物理节点已经存在的最大索引，第一次添加是索引为0
     * @param physicalNode 物理节点
     * @return 最大索引
     * @author wellman
     **/
    private int getMaxIndexFromExistNode(T physicalNode) {
        int idx = 0;
        for (VirtualNode<T> vNode : HASH_RING.values()) {
            if (vNode.isVirtualNodeOf(physicalNode)) {
                idx++;
            }
        }
        return idx;
    }
}
﻿
/**
 * 实际节点，此处为数据库节点
 * @author wellman
 **/
public class DbNode implements Node {
    /**
     * 数据库IP地址
     **/
    private final String ip;
    /**
     * 数据库使用端口
     **/
    private final int port;
    public DbNode(String ip, int port) {
        this.ip = ip;
        this.port = port;
    }
    @Override
    public String getKey() {
        return ip + ":" + port;
    }
    @Override
    public String toString() {
        return "DbNode{" +
                "ip='" + ip + '\'' +
                ", port=" + port +
                '}';
    }
}
﻿
/**
 * @author wellman
 **/
public class Client {
    public static void main(String[] args) {
        List<DbNode> nodeList = Arrays.asList(new DbNode("127.0.0.1", 3306), new DbNode("192.168.1.1", 3306));
        ConsistentHashRouter<DbNode> router = new ConsistentHashRouter<>(nodeList, 10);
        int testRoundCount = 50;
        List<String> sameIpList = new ArrayList<>(testRoundCount);
        System.out.println("第一次====================");
        for (int i = 0; i < testRoundCount; i++) {
            String requestIp = "10." + getRandom(255) + ".144." + getRandom(200);
            sameIpList.add(requestIp);
            Node node = router.route(requestIp);
            System.out.printf("requestIp=%s 路由到数据库: %s%n", requestIp, node);
        }
        System.out.println("第二次用与第一次相同的IP====================");
        for (String ip : sameIpList) {
            Node node = router.route(ip);
            System.out.printf("requestIp=%s 路由到数据库: %s%n", ip, node);
        }
        router.addNode(new DbNode("172.111.1.1", 3306), 15);
        System.out.println("第三次为新增节点后====================");
        for (String ip : sameIpList) {
            Node node = router.route(ip);
            System.out.printf("requestIp=%s 路由到数据库: %s%n", ip, node);
        }
    }
    private static int getRandom(int max) {
        Random random = new Random(System.nanoTime());
        return random.nextInt(max);
    }
}
﻿
二、编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性测试代码：
/**
 * @author wellman
 **/
public class Client {
    public static void main(String[] args) {
        List<DbNode> nodeList = generateNodeList();
        ConsistentHashRouter<DbNode> router = new ConsistentHashRouter<>(nodeList, 10);
        Map<String, Integer> routeCountMap = new HashMap<>(16);
        long begin = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            Node node = router.route("Request-" + i);
            String key = node.getKey();
            if (routeCountMap.containsKey(key)) {
                routeCountMap.put(key, routeCountMap.get(key) + 1);
            } else {
                routeCountMap.put(key, 1);
            }
        }
        long end = System.currentTimeMillis();
        System.out.printf("cost=%s \n", end - begin);
        System.out.println(routeCountMap);
    }
    private static List<DbNode> generateNodeList() {
        List<DbNode> nodeList = new ArrayList<>(11);
        for (int i = 0; i < 10; i++) {
            nodeList.add(new DbNode("Node-" + i, 3306));
        }
        return nodeList;
    }
}
﻿
1000000 个请求，10个服务器节点，每个节点平均值为：100000
方差公式：
S=n∑i=1n​(Xi−X​)2​
标准差公式：
σ=S​
﻿
测试一：虚拟节点数 10输出结果：
{Node-7:3306=57270, Node-4:3306=66478, Node-2:3306=110523, Node-3:3306=157893, Node-0:3306=113326, Node-8:3306=69517, Node-6:3306=113266, Node-9:3306=90051, Node-1:3306=107692, Node-5:3306=113984}
标准差σ= 34792.95
﻿
测试二：虚拟节点数 50输出结果：
{Node-7:3306=124956, Node-4:3306=124726, Node-2:3306=128851, Node-3:3306=79794, Node-0:3306=95666, Node-8:3306=103824, Node-6:3306=96568, Node-9:3306=89442, Node-1:3306=90353, Node-5:3306=65820}
标准差σ= 19730.26
﻿
测试三：虚拟节点数 100输出结果：
{Node-7:3306=104010, Node-4:3306=105443, Node-2:3306=113656, Node-3:3306=81710, Node-0:3306=108849, Node-6:3306=90082, Node-8:3306=99095, Node-9:3306=107060, Node-1:3306=101356, Node-5:3306=88739}
标准差σ= 9,605.72
﻿
测试四：虚拟节点数 200输出结果：
{Node-7:3306=104737, Node-4:3306=105494, Node-2:3306=112146, Node-3:3306=92164, Node-0:3306=111415, Node-6:3306=94360, Node-8:3306=99012, Node-9:3306=89089, Node-1:3306=93241, Node-5:3306=98342}
标准差σ= 7,694.94
﻿
测试五：虚拟节点数 300输出结果：
{Node-7:3306=106858, Node-4:3306=102767, Node-2:3306=112641, Node-3:3306=103470, Node-0:3306=107338, Node-8:3306=98993, Node-6:3306=83964, Node-9:3306=97082, Node-1:3306=90039, Node-5:3306=96848}
标准差σ= 8,100.67
﻿
虚拟节点数 | 标准差 |
:-: | :-: |
10 | 34792.95 |
50 | 19730.26|
100 | 9,605.72|
200 | 7,694.94|
300 | 8,100.67|
﻿
从测试的情况来看，虚拟节点数在200-300之间负载会比较均衡
发布于: 2020 年 11 月 22 日阅读数: 19
原文链接:【http://xie.infoq.cn/article/d470e17b61510b5da61236c9f】。未经作者许可，禁止转载。
井中人

关注
还未添加个人签名 2018.08.24 加入
还未添加个人简介
发布
暂无评论
创作场景

极客大学架构师训练营第五周作业

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

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

测试一：虚拟节点数 10

测试二：虚拟节点数 50

测试三：虚拟节点数 100

测试四：虚拟节点数 200

测试五：虚拟节点数 300

井中人

评论
