参考：https://blog.csdn.net/gonghaiyu/article/details/108375298
传统hash算法的弊端
资源数据分布通常有哈希分区和顺序分区两种方式，优缺点：
- 顺序分区：数据分散度易倾斜、键值业务相关、可顺序访问、不支持批量操作。
- 哈希分区：数据分散度高、键值分布业务无关、无法顺序访问、支持批量操作。
简单介绍
1、顺序分区
顺序分区通常指顺序访问某个资源，如在RocketMQ中，Topic(消息主题)可能对应多个实际的消息队列，消息投递时，如果有5个消息，只有三个队列，消息按照1-2-3-1-2这样的投递顺序。
2、哈希分区
2.1、节点取余分区
对特定数据采用hash算法得到一个整数，再通过整数对分区数取余就可以得到资源的存储路由。如redis的键或用户ID，再根据节点数量N使用公式：hash(key)%N计算出哈希值，用来决定数据映射到哪个分区节点。
优点
这种方式的突出优点就是简单，且常用于数据库的分库分表。如京东某系统中采用shardingjdbc，用这种方式进行分库分表路由处理。
缺点
当节点数量发生变化时，如扩容或收缩节点（没有遇到过），数据节点关系需要重新计算，会导致数据的重新迁移。所以扩容通常采用翻倍扩容，避免数据映射全部打乱而全部迁移，翻倍迁移只发生50%的数据迁移。如果不翻倍缩扩容，如某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将宕掉的服务器使用算法去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。
扩容.jpg
2.2、一致性hash算法
将所有的存储节点排列在首尾相接的hash环上，每个key在计算Hash后会顺时针找到临接的存储节点存放。而当有节点加入或退出时，仅影响该节点在Hash环上顺时针相邻的后续节点。
优点
加入和删除节点只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响。
缺点
数据的分布和节点的位置有关，因为这些节点不是均匀的分布在哈希环上的，所以数据在进行存储时达不到均匀分布的效果。所以，出现了增加虚拟节点的方式来减少不均衡的现象。
算法演示
1、首先，我们将hash算法的值域映射成一个具有2的32次方个桶的空间中，即0~（2的32次方）-1的数字空间。现在我们可以将这些数字头尾相连，组合成一个闭合的环形。
2、每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。
3、我们的每一个缓存节点也遵循同样的Hash算法，比如利用IP或者主机名做Hash，映射到环形空间当中，如下图
算法演示.png
如何让key和缓存节点对应起来？
很简单，每一个key的顺时针方向最近节点，就是key所归属的缓存节点。所以图中key1存储于node1，key2，key3存储于node3，key4存储于node4。
算法演示nk.png
增加节点：只影响顺时针最近节点数据，随后进行迁移即可
删除节点：只影响顺时针最近节点数据，随后进行迁移即可
雪崩效应：由于缓存的节点有可能很少，并且hash散列也不是均匀的，如果某个热点数据节点宕机，会使后续节点压力增加，继而宕机，形成连锁反应，造成雪崩效应。
细节内容参考：https://blog.csdn.net/gonghaiyu/article/details/108375298
说明：这里所说的迁移并不是直接的数据迁移，而是在查找时去找顺时针的后继节点，因缓存未命中而刷新缓存。
计算方法：假设节点hash散列均匀（由于hash是散列表，所以并不是很理想），采用一致性hash算法，缓存节点从3个增加到4个时，会有0-33%的缓存失效，此外新增节点不会环节所有原有节点的压力。
2.3、一致性hash升级版
为了解决节点太少而产生的数据分配不均衡的问题，也可能导致雪崩效应。一致性hash通过引入虚拟节点的方式做了优化。
所谓虚拟节点，就是基于原来的物理节点映射出N个子节点，最后把所有的子节点映射到环形空间上。
2.4、一致性hash算法+虚拟节点的实现
原理理解了，实现并不难，主要是一些细节：
- 1.hash算法的选择。
Java代码不要使用hashcode函数，这个函数结果不够散列，而且会有负值需要处理。
这种计算Hash值的算法有很多，比如CRC32HASH、FNV132HASH、KETAMAHASH等，其中KETAMAHASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以，比如FNV132_HASH算法的计算效率就会高一些。
数据结构的选择。根据算法原理，我们的算法有几个要求： - 2.要能根据hash值排序存储
排序存储要被快速查找 （List不行）
排序查找还要能方便变更 （Array不行）
另外，由于二叉树可能极度不平衡。所以采用红黑树是最稳妥的实现方法。Java中直接使用TreeMap即可。
package 算法.一致性hash;
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;
/**
* 一致性hash
* @author xuxueli 2015-10-26 22:50:29
*
* 《普通hash方法》
* NODE节点 : 有序数组或list列表, 如缓存redis服务器ip列表;
* 数据节点 : 支持获取hashCode, 如redis key;
* 映射方法 : key.hashCode % NODE.size
* 优点 : 简单,高效;
* 缺点 : NODE增减, 所有映射都会失效, 如redis服务某一个节点宕机, 所有持久化文件要做数据迁移, 其他缓存全部失效;
*
* 《一致性hash算法》
* hash环 : 抽象概念, 一张巨大的hash环装链表;
* NODE节点 : 对NODE进行hash计算, 散列对应到hash环上某一个位置;
* NODE节点-虚拟节点 : 对每个NODE节点生成一定量虚拟节点, 每个NODE虚拟节点都对关联到一个真实NODE节点, 对虚拟节点进行hash计算, 散列对应到hash换上某一个位置;
* 数据节点 : 对数据进行hash计算, 对应到hash环上某一个位置, 然后顺时针找到最近的NODE节点, 命中然后存储;
*
* 优点 : NODE增减, 改节点原NODE节点的命中会漂移到相邻的后一个NODE节点, 不会造成整体失效, 只会影响其中一个节点;
* 缺点 : 理解和维护起来, 需要一定学习成本;
* 缺点(已解决) : NODE其中一个节点失效, 该节点数据瞬间映射到下一个节点, 会造成例如 “缓存雪崩”现象, 在此引入NODE虚拟节点, 可以将该节点数据, 平衡的散列到其他存活的NODE节点中;
*
* --- 0 --------- node1_1 ----------- node2_2 --------- node1_2 ------ node2_1 ------ 2^64|0 ---
* -------- key1 --------- key02 ---------
*/
public class ConsistencyHashUtil {
private List<String> shardNodes;
private final int NODE_NUM = 1000;
private TreeMap<Long, String> virtualHash2RealNode = new TreeMap<Long, String>();
/**
* init consistency hash ring, put virtual node on the 2^64 ring
*/
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);
}
}
}
/**
* get real node by key's hash on the 2^64
*/
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());
}
/**
* prinf ring virtual node info
*/
public void printMap() {
System.out.println(virtualHash2RealNode);
}
/**
* MurMurHash算法，是非加密HASH算法，性能很高，
* 比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）
* 等HASH算法要快很多，而且据说这个算法的碰撞率很低.
* http://murmurhash.googlepages.com/
*/
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);
// for big-endian version, do this first:
// finish.position(8-buf.remaining());
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
/**
* get hash code on 2^32 ring (md5散列的方式计算hash值)
* @return
*/
public static long hash2(String key) {
// md5 byte
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();
// hash code, Truncate to 32-bits
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);
/*long start = System.currentTimeMillis();
for (int i = 0; i < 1000 * 1000 * 1000; i++) {
if (i % (100 * 1000 * 1000) == 0) {
System.out.println(i + ":" + hash("key1" + i));
}
}
long end = System.currentTimeMillis();
System.out.println(end - start);*/
}
}