写点什么

架构师训练营第五周作业——一致性哈希算法

用户头像
文智
关注
发布于: 2020 年 10 月 24 日

设计

本文将描述基于虚拟节点的一致性哈希算法的实现,实现语言为 Java。

  1. 一致性 hash 环需要一个以 hash 值为 Key 的容器,且该容器能方便地实现插入、删除、查找最近节点等操作,Java 中 SortedMap 接口满足该条件,实现类可以使用 TreeMap

  1. 各节点命中次数的标准差,可以用来作为衡量节点负载均衡程度,假设节点 i 的命中次数为 Hi,平均命中次数为 Havg,标准差的计算公式为:

实现

  1. 节点

public class Node {
private String ip; private int hitCount; public Node(String ip) { this.ip = ip; this.hitCount = 0; } public String getIp() { return ip; }
public int getHitCount() { return hitCount; } public void hit() { this.hitCount++; } public void setHitCount(int clientCount) { this.hitCount = clientCount; } @Override public boolean equals(Object obj) { return obj != null && obj instanceof Node && ((Node)obj).getIp().equals(ip); }}
复制代码
  1. 一致性哈希算法

import java.util.Collection;import java.util.HashMap;import java.util.Map;import java.util.SortedMap;import java.util.TreeMap;import java.util.UUID;
public class ConsistentHash {
// 实际节点 protected Map<String, Node> nodes; // 虚拟节点,形成一致性hash环 protected SortedMap<Integer, Node> virtualNodes; // 每个节点的虚拟节点数 protected int virtualNodeSize; public ConsistentHash(int virtualNodeSize) { this.nodes = new HashMap<>(); this.virtualNodes = new TreeMap<>(); this.virtualNodeSize = virtualNodeSize; } /** * 增加节点 * @param ip */ public void addNode(String ip) { Node node = new Node(ip); this.nodes.put(ip, node); for (int i = 0; i < virtualNodeSize; ++i) { virtualNodes.put(UUID.randomUUID().hashCode(), node); } } /** * 删除节点 * @param ip */ public void removeNode(String ip) { Node node = nodes.get(ip); virtualNodes.keySet().forEach(key -> { if (virtualNodes.get(key).equals(node)) { virtualNodes.remove(key); } }); } /** * 根据hash值寻找下一个据里最近的节点 * @param hash 由请求计算得到的hash值 * @return */ public Node findNode(int hash) { Node node; // tailMap为hash之后的节点集合 SortedMap<Integer, Node> tailMap = virtualNodes.tailMap(hash); if (tailMap.isEmpty()) { // 如果hash之后没有节点,则下一个节点应为所有节点的第一个节点 node = virtualNodes.get(virtualNodes.firstKey()); } else { node = tailMap.get(tailMap.firstKey()); } // 命中节点 node.hit(); return node; } public Collection<Node> getNodes() { return nodes.values(); } /** * 获取虚拟节点数 */ public int getVirtualNodesSize() { return virtualNodes.size(); }}
复制代码
  1. 测试类

import java.util.Collection;import java.util.Iterator;import java.util.UUID;
public class ConsistentHashTest { private final static String[] nodeIPs = { "192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5", "192.168.0.6", "192.168.0.7", "192.168.0.8", "192.168.0.9", "192.168.0.10" }; private final static int TEST_CASES = 1000000; /** * 计算节点命中的标准差 * @param nodes * @return */ public double calcStandardDeviation(Collection<Node> nodes) { double sum = 0; Iterator<Node> it = nodes.iterator(); while (it.hasNext()) { sum += it.next().getHitCount(); } double avg = sum / nodes.size(); int sqsum = 0; it = nodes.iterator(); while (it.hasNext()) { sqsum += Math.pow((it.next().getHitCount() - avg), 2); } return Math.sqrt(sqsum / nodes.size()); } /** * 创建ConsistentHash实例并进行测试 * @param virtualNodeSize 虚拟节点数 */ public void doTest(int virtualNodeSize) { ConsistentHash consistentHash = new ConsistentHash(virtualNodeSize); for (int i = 0; i < nodeIPs.length; ++i) { consistentHash.addNode(nodeIPs[i]); } for (int i = 0; i < TEST_CASES; ++i) { consistentHash.findNode(UUID.randomUUID().hashCode()); } double sd = calcStandardDeviation(consistentHash.getNodes()); System.out.println(String.format("%d虚拟节点数的标准差:%d", virtualNodeSize, Math.round(sd))); }
public static void main(String[] args) { ConsistentHashTest test = new ConsistentHashTest(); test.doTest(10); test.doTest(50); test.doTest(100); test.doTest(150); test.doTest(200); test.doTest(250); } }
复制代码

结论

运行以上测试类 5 次,每次生成 100 万 hash 测试,统计结果如下,表格中为不同虚拟节点数对应的标准差:

由以上图标基本可以看出,150 虚拟节点之内,标准差随虚拟节点数增加显著下降,而 150 至 250 之间有波动。当然测试次数比较少,不能因此说多少虚拟节点数是最好的,但大致趋势还是能看出来的。


思考

以上算法中,虚拟节点位置随机,因此不可能完全均匀分布,要想使环上虚拟节点均匀分布,那么有可能还是需要干预。

  • 假设我们希望每台缓存服务器的负载完全均衡,也就是说只有一台服务器的时候,其负载是总负载的 100%,两台的时候每台负载是总负载的 50%,三台的时候每台是 33.33%,以此类推,N 台服务器,每台的负载时总负载的 1/N,这时候如果再增加一台服务器,每台负载由 1/N 降至 1/(N+1)

  • 可能的算法,增加第 N 台服务器节点时,假设此时环上已经有 V 个虚拟节点,那么,这 V 个虚拟节点将环切割成 V 段,如果想要第 N 台服务器加入以后,每台服务器的负载为 1/N,我们可以再环上每一段的前 1/N 增加一个对应服务器 N 的虚拟节点,这个虚拟节点分担所在段的 1/N 压力,V 段新增的虚拟节点分担的压力之和也就是整个环的 1/N。以下是这个过程的模拟:

  • 最初只有一台服务器(标记为 1),整个环只有 1 段;

  • 加入第二台服务器时,在环的 1/2 处新增节点(标记为 2),将环分成两段;

  • 增加第三台服务器时,在原来的两段的前 1/3 各增加一个节点(标记为 3),将环分为四段,增加第四台机器时,又在原来的四段的前 1/4 增加一个虚拟节点,以此类推


实现
  • 继承 ConsistentHash,覆盖 addNode 方法

public class EvenConsistentHash extends ConsistentHash {        public EvenConsistentHash(int virtualNodeSize) {        super(virtualNodeSize);    }        @Override    public void addNode(String ip) {        Node node = new Node(ip);        int n = nodes.size();        nodes.put(ip, node);                // 第0个节点        if (n == 0) {            virtualNodes.put(Integer.MIN_VALUE, node);            return;        }                // 获取已经存在的虚拟节点,在每两个虚拟节点之间插入新的虚拟节点        int v = virtualNodes.size();        Integer[] keys = virtualNodes.keySet().toArray(new Integer[v]);        Integer start = keys[0];        Integer next = start;        for (int i = 1; i < v; ++i) {            next = keys[i];            Integer k = calcKey(start, next, n);            // 当start和next过于接近时,新key可能和start或next重合            if (!k.equals(start) && !k.equals(next))                virtualNodes.put(k, node);            start = next;        }        //在最后一个虚拟节点之后插入虚拟节点        virtualNodes.put(calcKey(start, Integer.MAX_VALUE, n), node);    }        /**     * 计算start和next之间的第n个节点的虚拟节点位置     */    private Integer calcKey(Integer start, Integer next, int n) {        Double gap = 0.0 + next - start;        return start + Double.valueOf(gap / (n + 1)).intValue();    }}
public class ConsistentHashTest { private final static int TEST_CASES = 1000000; /** * 计算节点命中的标准差 * * @param nodes * @return */ public double calcStandardDeviation(Collection<Node> nodes) { double sum = 0; Iterator<Node> it = nodes.iterator(); while (it.hasNext()) { Node node = it.next(); sum += node.getHitCount(); } double avg = sum / nodes.size(); double sqsum = 0; it = nodes.iterator(); while (it.hasNext()) { sqsum += Math.pow((it.next().getHitCount() - avg), 2); } return Math.sqrt(sqsum / nodes.size()); } /** * 测试不同实体服务器节点数时的标准差 * * @param virtualNodeSize 虚拟节点数 */ public void nodeSizeTest(IConsistentHash consistentHash, int nodeSize) { for (int i = 0; i < nodeSize; ++i) { consistentHash.addNode(String.valueOf(i)); } for (int i = 0; i < TEST_CASES; ++i) { consistentHash.findNode(UUID.randomUUID().hashCode()); } double sd = calcStandardDeviation(consistentHash.getNodes()); System.out.println(String.format("节点数: %d, 虚拟节点数: %d, 标准差: %d", nodeSize, consistentHash.getVirtualNodesSize(), Math.round(sd))); } public static void main(String[] args) { ConsistentHashTest test = new ConsistentHashTest(); for (int i = 10; i <= 40; ++i) { test.nodeSizeTest(new EvenConsistentHash(10), i); } }}
复制代码
验证
  • 测试 10-40 台服务器节点时的标准差,从下图可以看到,标准差基本在 300 以下,这相对于 1000000 的基数来说还是挺小的。


  • 这个算法也存在很明显的问题,那就是节点数量指数增长,放置第 N 台服务器节点时,需要增加 2^(N-2)个虚拟节点,当然随着虚拟节点数增多,部分虚拟节点会重合,但虚拟节点的总数也非常大,因此新增节点的效率会比较低


发布于: 2020 年 10 月 24 日阅读数: 47
用户头像

文智

关注

还未添加个人签名 2018.11.29 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业——一致性哈希算法