架构师训练营第五周作业

关注
发布于: 2020 年 07 月 08 日
作业：用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
解题思路：可使用 Java 中 TreeMap 来实现一致性 hash 环，采用常见的 MD5  算法作为 hash 算法；
﻿
首先定义节点接口类：
public interface INode {
    /**
    * 节点唯一标识，用于 hash 映射
    */
    String getKey();
}
物理服务器节点类：
public class ServiceNode implements INode {
    private String ip;
    private String port;
    public ServiceNode(String ip, String port) {
        this.ip = ip;
        this.port = port;
    }
    @Override
    public String getKey() {
        return ip + ":" + port;
    }
}
虚拟节点类：
public class VirtualNode<T extends INode> implements INode {
    private T PhysicalNode;
    private int count;
    public VirtualNode(T PhysicalNode, int count) {
        this.PhysicalNode = PhysicalNode;
        this.count = count;
    }
    public T getPhysicalNode() {
        return PhysicalNode;
    }
    @Override
    public String getKey() {
        return PhysicalNode.getKey() + "_" + count;
    }
}
hash 路由算法实现类：
public class ConsistentHashRouter<T extends INode> {
    private MessageDigest instance;
    private final SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>();
    public ConsistentHashRouter() {
        try {
            this.instance = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
        }
    }
    /**
     * 添加物理节点
     *
     * @param physicalNode    物理节点
     * @param virtualNodeSize 虚拟节点个数
     */
    public void addNode(T physicalNode, int virtualNodeSize) {
        if (physicalNode == null || virtualNodeSize <= 0) {
            throw new IllegalArgumentException();
        }
        IntStream.range(0, virtualNodeSize).forEach(i -> {
            VirtualNode virtualNode = new VirtualNode(physicalNode, exitVirtualNodeSize.intValue() + i);
            String key = virtualNode.getKey();
            ring.put(hash(key), virtualNode);
        });
    }
    /**
     * 删除物理节点
     *
     * @param physicalNode
     */
    public void removeNode(T physicalNode) {
        if (physicalNode == null) {
            throw new IllegalArgumentException();
        }
        Iterator<Long> iterator = ring.keySet().iterator();
        while (iterator.hasNext()) {
            Long hashValue = iterator.next();
            VirtualNode virtualNode = ring.get(hashValue);
            if (virtualNode.getPhysicalNode().getKey().equals(physicalNode.getKey())) {
                iterator.remove();
            }
        }
    }
    public T getRouteNode(String key) {
        long hashValue = hash(key);
        SortedMap<Long, VirtualNode<T>> tailVirtualNodeSortedMap = ring.tailMap(hashValue);
        Long firstVirtualNodeKey = tailVirtualNodeSortedMap.isEmpty() ? ring.firstKey() : tailVirtualNodeSortedMap.firstKey();
        return ring.get(firstVirtualNodeKey).getPhysicalNode();
    }
    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;
    }
    public static void main(String[] args) throws NoSuchAlgorithmException {
        ConsistentHashRouter consistentHashRouter = new ConsistentHashRouter();
        int virtualNodeSize = 200;
        consistentHashRouter.addNode(new ServiceNode("192.168.2.1", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.2", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.3", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.4", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.5", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.6", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.7", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.8", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.9", "8080"), virtualNodeSize);
        consistentHashRouter.addNode(new ServiceNode("192.168.2.10", "8080"), virtualNodeSize);
        Map<String, Integer> countMap = new HashMap<>();
        IntStream.range(0, 1000_000).forEach(i -> {
            INode routeNode = consistentHashRouter.getRouteNode(String.valueOf(i));
            Integer count = countMap.getOrDefault(routeNode.getKey(), new Integer(0));
            countMap.put(routeNode.getKey(), ++count);
        });
        countMap.forEach((key, value) -> System.out.print("\n" + key + " " + value));
    }
}
100 万 kv 数据，10 个服务器节点，每个服务器节点设 100 个虚拟节点，测试结果如下：
192.168.2.10:8080 99713
192.168.2.7:8080 106130
192.168.2.5:8080 97859
192.168.2.1:8080 110436
192.168.2.2:8080 84954
192.168.2.6:8080 102653
192.168.2.9:8080 117970
192.168.2.3:8080 106100
192.168.2.8:8080 89319
192.168.2.4:8080 84866
﻿
100 万  kv 数据，10个服务器节点，每个服务器节点设 150 个虚拟节点，测试结果如下：
192.168.2.10:8080 101217
192.168.2.7:8080 106113
192.168.2.5:8080 90174
192.168.2.1:8080 123683
192.168.2.2:8080 97148
192.168.2.6:8080 88330
192.168.2.9:8080 103188
192.168.2.3:8080 101783
192.168.2.8:8080 99816
192.168.2.4:8080 88548
100 万 kv 数据，10 个服务器节点，每个服务器节点设 200 个虚拟节点，测试结果如下：
192.168.2.10:8080 99804
192.168.2.7:8080 98113
192.168.2.5:8080 101482
192.168.2.1:8080 107150
192.168.2.6:8080 91332
192.168.2.2:8080 106021
192.168.2.9:8080 95693
192.168.2.3:8080 105099
192.168.2.8:8080 103286
192.168.2.4:8080 92020
总结
虚拟节点数在 150-250 之间，可以达到较好的负载均衡性。
发布于: 2020 年 07 月 08 日阅读数: 51
斌

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

架构师训练营第五周作业

作业：

斌

评论
