一致性hash算法
为什么会出现一致性hash传统hash算法的弊端顺序分区哈希分区节点取余分区
一致性hash算法算法演示如何让key和缓存节点对应起来呢？增加节点有哪些key会受到影响呢？删除节点有哪些key会受到影响呢？
一致性hash升级版一致性hash算法+虚拟节点的实现Java实现示例
为什么会出现一致性hash
一致性哈希是分布式系统组件负载均衡的首选算法，比如分库分表时要考虑数据怎么均匀分布，它既可以在客户端实现，也可以在中间件上实现。其应用有：
分布式散列表(DHT)的设计；分布式关系数据库(MySQL)：分库分表时，计算数据与节点的映射关系；分布式缓存：Memcached 的客户端实现了一致性哈希，还可以使用中间件 twemproxy 管理 redis/memcache 集群；RPC 框架 Dubbo：用来选择服务提供者；亚马逊的云存储系统 Dynamo；分布式 Web 缓存；Bittorrent DHT；LVS。
传统hash算法的弊端
资源数据分布通常有哈希分区和顺序分区两种方式
顺序分布：数据分散度易倾斜、键值业务相关、可顺序访问、不支持批量操作。哈希分布：数据分散度高、键值分布业务无关、无法顺序访问、支持批量操作。
顺序分区
顺序分区通常指顺序访问某个资源，如在RocketMQ中，Topic(消息主题)可能对应多个实际的消息队列，消息投递时，如果有5个消息，只有三个队列，消息按照1-2-3-1-2这样的投递顺序。
哈希分区
节点取余分区
对特定数据采用hash算法得到一个整数，再通过整数对分区数取余就可以得到资源的存储路由。如redis的键或用户ID，再根据节点数量N使用公式：hash(key)%N计算出哈希值，用来决定数据映射到哪个分区节点。
优点 这种方式的突出优点就是简单，且常用于数据库的分库分表。如京东某系统中采用shardingjdbc，用这种方式进行分库分表路由处理。缺点 当节点数量发生变化时，如扩容或收缩节点（没有遇到过），数据节点关系需要重新计算，会导致数据的重新迁移。所以扩容通常采用翻倍扩容，避免数据映射全部打乱而全部迁移，翻倍迁移只发生50%的数据迁移。如果不翻倍缩扩容，如某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将宕掉的服务器使用算法去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。
传统求余做负载均衡算法，缓存节点数由3个变成4个，缓存不命中率为75%。计算方法：穷举hash值为1-12的12个数字分别对3和4取模，然后比较发现只有前3个缓存节点对应结果和之前相同，所以有75%的节点缓存会失效，可能会引起缓存雪崩。
一致性hash算法
一致性hash算法是因为节点数目发生改变时，尽可能少的数据迁移而出现的。比如扩容时，需要50%的数据迁移；但如果引入一种算法，可以减少数据的迁移量，所以就出现了一致性hash算法。将所有的存储节点排列在收尾相接的hash环上，每个key在计算Hash后会顺时针找到临接的存储节点存放。而当有节点加入或退出时，仅影响该节点在Hash环上顺时针相邻的后续节点。
优点 加入和删除节点只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响。缺点 数据的分布和节点的位置有关，因为这些节点不是均匀的分布在哈希环上的，所以数据在进行存储时达不到均匀分布的效果。所以，出现了增加虚拟节点的方式来减少不均衡的现象。
算法演示
1、首先，我们将hash算法的值域映射成一个具有2的32次方个桶的空间中，即0~（2的32次方）-1的数字空间。现在我们可以将这些数字头尾相连，组合成一个闭合的环形。 2、每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。 3、我们的每一个缓存节点也遵循同样的Hash算法，比如利用IP或者主机名做Hash，映射到环形空间当中，如下图
如何让key和缓存节点对应起来呢？
很简单，每一个key的顺时针方向最近节点，就是key所归属的缓存节点。所以图中key1存储于node1，key2，key3存储于node3，key4存储于node4。 当缓存的节点有增加或删除的时候，一致性哈希的优势就显现出来了。让我们来看看实现的细节：
增加节点
当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。
有哪些key会受到影响呢？
图中加入了新节点node4，处于node1和node2之间，按照顺时针规则，从node1到node4之间的缓存不再归属于node2，而是归属于新节点node4。因此受影响的key只有key2。 最终把key2的缓存数据从node2迁移到node4，就形成了新的符合一致性哈希规则的缓存结构。
删除节点
当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。
有哪些key会受到影响呢？
图中删除了原节点node3，按照顺时针规则，原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。 最终把key4的缓存数据从node3迁移到node1，就形成了新的符合一致性哈希规则的缓存结构。
说明：这里所说的迁移并不是直接的数据迁移，而是在查找时去找顺时针的后继节点，因缓存未命中而刷新缓存。 计算方法：假设节点hash散列均匀（由于hash是散列表，所以并不是很理想），采用一致性hash算法，缓存节点从3个增加到4个时，会有0-33%的缓存失效，此外新增节点不会环节所有原有节点的压力。
如果出现分布不均匀的情况怎么办？ 一致性hash算法的结果相比传统hash求余算法已经进步很多，但是出现分布不均匀的情况会有问题。比如下图这样，按顺时针规则，所有的key都归属于统一个节点。
一致性hash升级版
为了解决节点太少而产生的数据分配不均衡的问题。一致性hash通过引入虚拟节点的方式做了优化。
所谓虚拟节点，就是基于原来的物理节点映射出N个子节点，最后把所有的子节点映射到环形空间上。
虚拟节点越多，分布越均匀。使用一致性hash算法+虚拟节点这种情况下，缓存节点从3个变成4个，缓存失效率为25%，而且每个节点都平均的承担了压力。
一致性hash算法+虚拟节点的实现
原理理解了，实现并不难，主要是一些细节：
hash算法的选择。 Java代码不要使用hashcode函数，这个函数结果不够散列，而且会有负值需要处理。 这种计算Hash值的算法有很多，比如CRC32HASH、FNV132HASH、KETAMAHASH等，其中KETAMAHASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以，比如FNV132_HASH算法的计算效率就会高一些。数据结构的选择。根据算法原理，我们的算法有几个要求： 要能根据hash值排序存储 排序存储要被快速查找 （List不行） 排序查找还要能方便变更 （Array不行） 另外，由于二叉树可能极度不平衡。所以采用红黑树是最稳妥的实现方法。Java中直接使用TreeMap即可。
Java实现示例
package com
.xxl
.util
.core
.skill
.consistencyhash
;
import java
.io
.UnsupportedEncodingException
;
import java
.nio
.ByteBuffer
;
import java
.nio
.ByteOrder
;
import java
.security
.MessageDigest
;
import java
.security
.NoSuchAlgorithmException
;
import java
.util
.ArrayList
;
import java
.util
.List
;
import java
.util
.SortedMap
;
import java
.util
.TreeMap
;
public class ConsistencyHashUtil {
private List
<String> shardNodes
;
private final int NODE_NUM
= 1000;
private TreeMap
<Long, String> virtualHash2RealNode
= new TreeMap<Long, String>();
public void initVirtual2RealRing(List
<String> shards
) {
this.shardNodes
= shards
;
for (String node
: shardNodes
) {
for (int i
= 0; i
< NODE_NUM
; i
++){
long hashCode
= hash("SHARD-" + node
+ "-NODE-" + i
);
virtualHash2RealNode
.put(hashCode
, node
);
}
}
}
public String
getShardInfo(String key
) {
long hashCode
= hash(key
);
SortedMap
<Long, String> tailMap
= virtualHash2RealNode
.tailMap(hashCode
);
if (tailMap
.isEmpty()) {
return virtualHash2RealNode
.get(virtualHash2RealNode
.firstKey());
}
return virtualHash2RealNode
.get(tailMap
.firstKey());
}
public void printMap() {
System
.out
.println(virtualHash2RealNode
);
}
public static Long
hash(String key
) {
ByteBuffer buf
= ByteBuffer
.wrap(key
.getBytes());
int seed
= 0x1234ABCD;
ByteOrder byteOrder
= buf
.order();
buf
.order(ByteOrder
.LITTLE_ENDIAN
);
long m
= 0xc6a4a7935bd1e995L
;
int r
= 47;
long h
= seed
^ (buf
.remaining() * m
);
long k
;
while (buf
.remaining() >= 8) {
k
= buf
.getLong();
k
*= m
;
k
^= k
>>> r
;
k
*= m
;
h
^= k
;
h
*= m
;
}
if (buf
.remaining() > 0) {
ByteBuffer finish
= ByteBuffer
.allocate(8).order(
ByteOrder
.LITTLE_ENDIAN
);
finish
.put(buf
).rewind();
h
^= finish
.getLong();
h
*= m
;
}
h
^= h
>>> r
;
h
*= m
;
h
^= h
>>> r
;
buf
.order(byteOrder
);
return h
;
}
public static long hash2(String key
) {
MessageDigest md5
;
try {
md5
= MessageDigest
.getInstance("MD5");
} catch (NoSuchAlgorithmException e
) {
throw new RuntimeException("MD5 not supported", e
);
}
md5
.reset();
byte[] keyBytes
= null
;
try {
keyBytes
= key
.getBytes("UTF-8");
} catch (UnsupportedEncodingException e
) {
throw new RuntimeException("Unknown string :" + key
, e
);
}
md5
.update(keyBytes
);
byte[] digest
= md5
.digest();
long hashCode
= ((long) (digest
[3] & 0xFF) << 24)
| ((long) (digest
[2] & 0xFF) << 16)
| ((long) (digest
[1] & 0xFF) << 8)
| (digest
[0] & 0xFF);
long truncateHashCode
= hashCode
& 0xffffffffL
;
return truncateHashCode
;
}
public static void main(String
[] args
) {
List
<String> shards
= new ArrayList<String>();
shards
.add("consumer-uuid-2");
shards
.add("consumer-uuid-1");
ConsistencyHashUtil sh
= new ConsistencyHashUtil();
sh
.initVirtual2RealRing(shards
);
sh
.printMap();
int consumer1
= 0;
int consumer2
= 0;
for (int i
= 0; i
< 10000; i
++) {
String key
= "consumer" + i
;
System
.out
.println(hash(key
) + ":" + sh
.getShardInfo(key
));
if ("consumer-uuid-1".equals(sh
.getShardInfo(key
))) {
consumer1
++;
}
if ("consumer-uuid-2".equals(sh
.getShardInfo(key
))) {
consumer2
++;
}
}
System
.out
.println("consumer1:" + consumer1
);
System
.out
.println("consumer2:" + consumer2
);
}
}
参考： https://www.xuxueli.com/blog/?blog=./notebook/6-%E7%AE%97%E6%B3%95/%E4%B8%80%E8%87%B4%E6%80%A7Hash%E7%AE%97%E6%B3%95.md https://blog.csdn.net/kefengwang/article/details/81628977 https://crossoverjie.top/JCSprout/#/algorithm/consistent-hash-implement 一致性hash理论基础论文：https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/chash.pdf
