理解一致性哈希算法

野性酷女 2021-11-04 22:42 336阅读 0赞

### 场景分析 ###

在分布式缓存的伸缩性设计中，最主要的目标就是在新加入缓存服务器后，应该使整个服务器集群中已经缓存的数据尽可能还被访问到。对于服务器集群管理，路由算法至关重要，它决定着客户端究竟该访问集群中的哪台服务器。

--------------------

### 余数Hash ###

简单的路由算法可以使用**余数Hash**：

> 用服务器数目除缓存数据key的Hash值，余数为服务器列表下标编号。

该思路的简单代码实现如下：

class RemainderHash { private List<String> serverNodes; private int serverNodeSize; public RemainderHash(List<String> serverNodes) { this.serverNodes = serverNodes; this.serverNodeSize = serverNodes.size(); } public String getServerNode(String key) { return serverNodes.get(hash(key)); } public int hash(String key) { return Math.abs(key.hashCode() % serverNodeSize); } }

该算法可以保证缓存数据在整个服务器集群的均衡分布。  
但是假如服务器由3台扩容至4台，扩容前后的缓存重复命中率（扩容前后，同一缓存数据仍在同一服务器上）只有24.99%，而假如服务器由100台扩容至101台，扩容前后的缓存重复命中率只有0.71%。*[均衡性和重复命中率的测试代码在这][Link 1]*

所以这种余数Hash算法不能满足实际生产需要。

--------------------

### 一致性Hash算法的思想 ###

要解决上述问题，目前比较流行的算法是一致性Hash算法，该算法通过一致性`Hash`环的数据结构实现`key`到缓存服务器的映射。

该算法的具体过程为：  
①先构造一个长度为232的整数环（称作一致性Hash环），  
②根据节点名称的Hash值（其分布范围为\[0, 232\-1\]）将缓存服务器节点放置在这个Hash环上；（要保证n个服务器节点均衡地放置在环上）  
③根据缓存数据的key的Hash值（其分布范围也为\[0, 232\-1\]）在Hash环上顺时针查找距离这个key的Hash值最近的缓存服务器节点，即为该数据应该放置的的服务器。

![Image 1][]

一致性Hash示意图.png

图中，以Node开头的圆形表示服务器，以key开头的方形表示缓存数据，带箭头的虚线表示缓存数据应该放置在哪台服务器。可以看出，在新增一台服务器后，受影响的缓存数据只是分布在Node2和Node4之间的一小段（顺时针）数据。

但是，上面描述的算法存在一个问题：新加入的结点Node4只影响了Node3，原来的Node1和Node2不受影响，即扩容后，每台服务器的负载不同，没有达到缓存数据均衡分布在各台服务器上的效果。

上述**负载不均衡问题的解决方案是使用虚拟层**：将每台物理服务器虚拟为一组虚拟缓存服务器，将虚拟缓存服务器的Hash值放置在Hash环上，缓存数据通过key的Hash值首先找到虚拟服务器节点，再找到这个虚拟服务器节点对应的物理服务器。  
使用虚拟节点后，缓存数据在服务器节点的分布示意图如下：（图片来源：[The Simple Magic of Consistent Hashing][]）

![Image 1][]

使用虚拟节点的一致性Hash算法示意图.png

这样，在新加入一个物理服务器节点时，是将一组虚拟节点（假设数量为n）加入环中，这些虚拟节点会影响n个虚拟节点，受影响的n个虚拟节点又对应不同的物理服务器，最终，新加入一台服务器将会分摊原集群中所有服务器的一部分负载，从而达到负载均衡的目的。（每个物理节点对应的虚拟节点越多，各物理节点之间的负载越均衡，但太多会影响性能。在实践中，经验值为150）。

--------------------

### 一致性Hash算法的实现 ###

public class ConsistentHash<T> { /** * 哈希函数 */ private final HashFunction hashFunction; /** * 每台物理服务器节点虚拟出虚拟节点个数 */ private final int numberOfReplicas; /** * Hash环 * <p> * 该Map中仅存放虚拟服务器节点，并不存放实际的缓存数据！！！ * 该Map中key为虚拟服务器节点对应在环中的位置 * <p> * 使用TreeMap的原因： * TreeMap的内部使用红黑树（平衡查找树）， * 因而在确定了一个缓存数据key的hash值在该环中的位置后， * 可以很快查找到该缓存数据应该放置的物理服务器 */ private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>(); /** * 构造器 * * @param hashFunction 哈希函数 * @param numberOfReplicas 每台物理服务器节点虚拟出虚拟节点个数 * @param nodes 物理服务器节点 */ public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) { this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; //将物理服务器放在环上 for (T node : nodes) { add(node); } } /** * 添加物理服务器节点 * <p> * 实现：将该物理服务器节点放在环中的numberOfReplicas个位置处， * （添加一个物理服务器节点，就要添加numberOfReplicas个虚拟节点） * * @param node 要添加的物理服务器节点 */ public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.put(hashFunction.hash(node.toString() + i), node); } } /** * 移除物理服务器节点 * <p> * 实现：因为该物理服务器节点放在了环中的多个位置，所以在删除时都要删除 * （移除一个物理服务器节点，就要将该服务器节点对应的numberOfReplicas个虚拟节点移除） * * @param node 要移除的物理服务器节点 */ public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.remove(hashFunction.hash(node.toString() + i)); } } /** * 根据缓存数据的key获取物理服务器节点 * * @param key 缓存数据的key * @return 该缓存数据所在的物理服务器节点 */ public T get(Object key) { if (circle.isEmpty()) { return null; } int hash = hashFunction.hash(key); //如果缓存数据的key的哈希值没有落在虚拟服务器节点上， //则 if (!circle.containsKey(hash)) { //获取map中key值大于该缓存数据的key的哈希值的子map SortedMap<Integer, T> tailMap = circle.tailMap(hash); //如果该子map不为空，则返回该子map的第一个元素（因为该map是排序好的，第一个即是最小的元素） //如果该子map为空，说明该缓存数据的key的哈希值超出了哈希环中最后的那个虚拟服务器节点对应的位置（顺时针）， // 则将该缓存数据放在哈希环中第一个虚拟服务器节点中（顺时针） hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); } } class HashFunction { int hash(Object key) { return key.hashCode(); } }

上述代码中，Hash算法有待改进，因为Hash算法至关重要，大部分Object的hashCode()方法不能很好地得到分布均衡的哈希值，比如，通常这些哈希值都是一定范围内的比较小的整数。

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2，但由于MD5碰撞案例较多，因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是[安全散列算法][Link 2]。

//TODO 哈希算法归类

那么如何使用一致性Hash呢？通常，只会在别人的依赖库里遇到一致性Hash算法，而不是自己编写。比如，大部分的支持分布式的缓存组件的客户端都支持一致性哈希。值得注意的是，仅仅客户端需要实现一致性哈希算法，缓存服务器除了缓存数据，什么都不用做。

--------------------

### 参考 ###

①《大型网站技术架构--核心原理与案例分析》 ：（文字描述部分）  
② [Consistent Hashing][] ：（一致性算法的代码）  
③ [Hash算法总结][Hash]  
④ [The Simple Magic of Consistent Hashing][]

作者：maxwellyue  
链接：https://www.jianshu.com/p/05ad6637e66b  
来源：简书  
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

转载于:https://www.cnblogs.com/xiaoshen666/p/11258597.html

[Link 1]: https://link.jianshu.com?t=https://github.com/maxwellyue/JavaLanguage/blob/master/src/consistanthash/RemainderHash.java
[Image 1]: 
[The Simple Magic of Consistent Hashing]: https://link.jianshu.com?t=https://dzone.com/articles/simple-magic-consistent
[Link 2]: https://link.jianshu.com?t=https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F
[Consistent Hashing]: https://link.jianshu.com?t=http://www.tom-e-white.com/2007/11/consistent-hashing.html
[Hash]: https://www.jianshu.com/p/bf1d7eee28d0