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

文智

关注

发布于: 2020 年 10 月 24 日

设计

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

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

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

实现

节点

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);	}}

复制代码

一致性哈希算法

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();  }}

复制代码

测试类

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

原文链接:【http://xie.infoq.cn/article/2a76cf0630f00171d027a83b1】。未经作者许可，禁止转载。

文智

关注

还未添加个人签名 2018.11.29 加入

还未添加个人简介

发布

暂无评论

创作场景

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

设计

实现

结论

思考

实现

验证

文智

评论