一致性哈希算法
背景
在具体介绍一致性哈希算法之前，先问一个问题：为什么需要一致性哈希算法？下面我们通过一个案例来回答这个问题。
假设有这么一种场景：我们有三台缓存服务器分别为：node0、node1、node2，有3000万个缓存数据需要存储在这三台服务器组成的集群中，希望可以将这些数据均匀的缓存到三台机器上，你会想到什么方案呢？
我们可能首先想到的方案是：取模算法hash（key）%N，即：对缓存数据的key进行hash运算后取模，N是机器的数量；运算后的结果映射对应集群中的节点。具体如下图所示：
如上图所示，首先对key进行hash计算后的结果对3取模，得到的结果一定是0、1或者2；然后映射对应的服务器node0、node1、node2，最后直接找对应的服务器存取数据即可。
通过取模算法将每个数据请求都均匀的分散到了三个不同的服务器节点上，看起来很完美！但是，在分布式集群系统的负载均衡实现上，这种模型在集群扩容和收缩时却有一定的局限性：因为在生产环境中根据业务量的大小，调整服务器数量是常有的事，而服务器数量N发生变化后hash（key）%N计算的结果也会随之变化！导致整个集群的缓存数据必须重新计算调整，进而导致大量缓存在同一时间失效，造成缓存的雪崩，最终导致整个缓存系统的不可用，这是不能接受的。为了解决优化上述情况，一致性哈希算法应运而生。
一致性哈希简介
什么是一致性哈希？
一致性哈希(Consistent Hash)算法是1997年提出，是一种特殊的哈希算法，目的是解决分布式系统的数据分区问题：当分布式集群移除或者添加一个服务器时，必须尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
一致性哈希主要解决问题
我们知道，传统的按服务器节点数量取模在集群扩容和收缩时存在一定的局限性。而一致性哈希算法正好解决了简单哈希算法在分布式集群中存在的动态伸缩的问题。降低节点上下线的过程中带来的数据迁移成本，同时节点数量的变化与分片原则对于应用系统来说是无感的，使上层应用更专注于领域内逻辑的编写，使得整个系统架构能够动态伸缩。
一致性哈希的使用场景
一致性哈希算法是分布式系统中的重要算法，使用场景也非常广泛。主要是是负载均衡、缓存数据分区等场景。
一致性哈希应该是实现负载均衡的首选算法，它既可以在客户端实现，也可以在中间件上实现，比如日常使用较多的缓存中间件memcached 使用的路由算法用的就是一致性哈希算法。
此外，其它的应用场景还有很多：
- RPC框架Dubbo用来选择服务提供者
- 分布式关系数据库分库分表：数据与节点的映射关系
- LVS负载均衡调度器
一致性哈希的原理
算法原理
前面介绍的取模算法虽然使用简单，但缺陷也很明显，如果服务器中保存有服务请求对应的数据，那么如果重新计算请求的哈希值，会造成缓存的雪崩的问题。这种情况在分布式系统中是非常糟糕的。一个设计良好的分布式系统应该具有良好的单调性，即服务器的添加与移除不会造成大量的哈希重定位，而一致性哈希恰好可以解决这个问题 。
其实，一致性哈希算法本质上也是一种取模算法。只不过前面介绍的取模算法是按服务器数量取模，而一致性哈希算法是对固定值2^32取模，这就使得一致性算法具备良好的单调性：不管集群中有多少个节点，只要key值固定，那所请求的服务器节点也同样是固定的。其算法的工作原理如下：
- 一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0~2^32-1；
- 计算各服务器节点的哈希值，并映射到哈希环上；
- 将服务发来的数据请求使用哈希算法算出对应的哈希值；
- 将计算的哈希值映射到哈希环上，同时沿圆环顺时针方向查找，遇到的第一台服务器就是所对应的处理请求服务器。
- 当增加或者删除一台服务器时，受影响的数据仅仅是新添加或删除的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。
一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性 。
哈希环
首先，一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环。整个哈希空间的取值范围为0~2^32-1，按顺时针方向开始从0~2^32-1排列，最后的节点2^32-1在0开始位置重合，形成一个虚拟的圆环。如下图所示：
服务器映射到哈希环
接下来，将服务器节点映射到哈希环上对应的位置。我们可以对服务器IP地址进行哈希计算，哈希计算后的结果对2^32取模，结果一定是一个0到2^32-1之间的整数。最后将这个整数映射在哈希环上，整数的值就代表了一个服务器节点的在哈希环上的位置。即：hash（服务器ip）% 2^32。下面我们依次将node0、node1、node2三个缓存服务器映射到哈希环上，如下图所示：
对象 key 映射到服务器
当服务器接收到数据请求时，首先需要计算请求Key的哈希值；然后将计算的哈希值映射到哈希环上的具体位置；接下来，从这个位置沿着哈希环顺时针查找，遇到的第一个节点就是key对应的节点；最后，将请求发送到具体的服务器节点执行数据操作。
假设我们有“key-01：张三”、“key-02：李四”、“key-03：王五”三条缓存数据。经过哈希算法计算后，映射到哈希环上的位置如下图所示：
如上图所示，通过哈希计算后，key-01顺时针寻找将找到node0，key-02顺时针寻找将找到node1，key-03顺时针寻找将找到node2。最后，请求找到的服务器节点执行具体的业务操作。
以上便是一致性哈希算法的工作原理。
服务器扩容&缩容
前面介绍了一致性哈希算法的工作原理，那么，一致性哈希算法如何避免服务器动态伸缩的问题的呢？
服务器缩容
服务器缩容就是减少集群中服务器节点的数量或是集群中某个节点故障。假设，集群中的某个节点故障，原本映射到该节点的请求，会找到哈希环中的下一个节点，数据也同样被重新分配至下一个节点，其它节点的数据和请求不受任何影响。这样就确保节点发生故障时，集群能保持正常稳定。如下图所示：
如上图所示：节点node2发生故障时，数据key-01和key-02不会受到影响，只有key-03的请求被重定位到node0。在一致性哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是会寻址到此节点和前一节点之间的数据。其他哈希环上的数据不会受到影响。
服务器扩容
服务器扩容就是集群中需要增加一个新的数据节点，假设，由于需要缓存的数据量太大，必须对集群进行扩容增加一个新的数据节点。此时，只需要计算新节点的哈希值并将新的节点加入到哈希环中，然后将哈希环中从上一个节点到新节点的数据映射到新的数据节点即可。其他节点数据不受影响，具体如下图所示：
如上图所示，加入新的node3节点后，key-01、key-02不受影响，只有key-03的寻址被重定位到新节点node3，受影响的数据仅仅是会寻址到新节点和前一节点之间的数据。
通过一致性哈希算法，集群扩容或缩容时，只需要重新定位哈希环空间内的一小部分数据。其他数据保持不变。当节点数越多的时候，使用哈希算法时，需要迁移的数据就越多，使用一致哈希时，需要迁移的数据就越少。所以，一致哈希算法具有较好的容错性和可扩展性。
数据倾斜与虚拟节点
什么是数据倾斜？
前面说了一致性哈希算法的原理以及扩容缩容的问题。但是，由于哈希计算的随机性，导致一致性哈希算法存在一个致命问题：数据倾斜，，也就是说大多数访问请求都会集中少量几个节点的情况。特别是节点太少情况下，容易因为节点分布不均匀造成数据访问的冷热不均。这就失去了集群和负载均衡的意义。如下图所示：
如上图所示，key-1、key-2、key-3可能被映射到同一个节点node0上。导致node0负载过大，而node1和node2却很空闲的情况。这有可能导致个别服务器数据和请求压力过大和崩溃，进而引起集群的崩溃。
如何解决数据倾斜？
为了解决数据倾斜的问题，一致性哈希算法引入了虚拟节点机制，即对每一个物理服务节点映射多个虚拟节点，将这些虚拟节点计算哈希值并映射到哈希环上，当请求找到某个虚拟节点后，将被重新映射到具体的物理节点。虚拟节点越多，哈希环上的节点就越多，数据分布就越均匀，从而避免了数据倾斜的问题。
说起来可能比较复杂，一句话概括起来就是：原有的节点、数据定位的哈希算法不变，只是多了一步虚拟节点到实际节点的映射。具体如下图所示：
如上图所示，我们可以在服务器ip或主机名的后面增加编号来实现，将全部的虚拟节点加入到哈希环中，增加了节点后，数据在哈希环上的分布就相对均匀了。当有访问请求寻址到node0-1这个虚拟节点时，将被重新映射到物理节点node0。
一致性哈希算法实现
前面介绍了一致性哈希算法的原理、动态伸缩以及数据倾斜的问题后，下面我们根据上面的讲述，使用Java实现一个简单的一致性哈希算法。
数据节点
首先定义一个节点类，实现数据节点的功能，具体代码如下：
public class Node {
private static final int VIRTUAL_NODE_NO_PER_NODE = 200;
private final String ip;
private final List<Integer> virtualNodeHashes = new ArrayList<>(VIRTUAL_NODE_NO_PER_NODE);
private final Map<Object, Object> cacheMap = new HashMap<>();
public Node(String ip) {
Objects.requireNonNull(ip);
this.ip = ip;
initVirtualNodes();
}
private void initVirtualNodes() {
String virtualNodeKey;
for (int i = 1; i <= VIRTUAL_NODE_NO_PER_NODE; i++) {
virtualNodeKey = ip + "#" + i;
virtualNodeHashes.add(HashUtils.hashcode(virtualNodeKey));
}
}
public void addCacheItem(Object key, Object value) {
cacheMap.put(key, value);
}
public Object getCacheItem(Object key) {
return cacheMap.get(key);
}
public void removeCacheItem(Object key) {
cacheMap.remove(key);
}
public List<Integer> getVirtualNodeHashes() {
return virtualNodeHashes;
}
public String getIp() {
return ip;
}
}实现一致性哈希算法
接下来实现核心功能：一致性哈希算法，主要使用java的TreeMap类，实现哈希环和哈希查找的功能。具体代码如下所示：
public class ConsistentHash {
private final TreeMap<Integer, Node> hashRing = new TreeMap<>();
public List<Node> nodeList = new ArrayList<>();
/** * 增加节点
* 每增加一个节点，就会在闭环上增加给定虚拟节点
* 例如虚拟节点数是2，则每调用此方法一次，增加两个虚拟节点，这两个节点指向同一Node * @param ip
**/
public void addNode(String ip) {
Objects.requireNonNull(ip);
Node node = new Node(ip);
nodeList.add(node);
for (Integer virtualNodeHash : node.getVirtualNodeHashes()) {
hashRing.put(virtualNodeHash, node);
System.out.println("虚拟节点[" + node + "] hash:" + virtualNodeHash + "，被添加");
}
}
/**
* 移除节点
* @param node
**/
public void removeNode(Node node){
nodeList.remove(node);
}
/**
* 获取缓存数据
* 先找到对应的虚拟节点，然后映射到物理节点
* @param key
* @return
**/
public Object get(Object key) {
Node node = findMatchNode(key);
System.out.println("获取到节点:" + node.getIp());
return node.getCacheItem(key);
}
/**
* 添加缓存
* 先找到hash环上的节点，然后在对应的节点上添加数据缓存
* @param key
* @param value
**/
public void put(Object key, Object value) {
Node node = findMatchNode(key);
node.addCacheItem(key, value);
}
/**
* 删除缓存数据
**/
public void evict(Object key) {
findMatchNode(key).removeCacheItem(key);
}
/**
* 获得一个最近的顺时针节点
* @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
* @return 节点对象
* @return
**/
private Node findMatchNode(Object key) {
Map.Entry<Integer, Node> entry = hashRing.ceilingEntry(HashUtils.hashcode(key));
if (entry == null) {
entry = hashRing.firstEntry();
}
return entry.getValue();
}
}如上所示，通过TreeMap的ceilingEntry() 方法，实现顺时针查找下一个的服务器节点的功能。
哈希计算方法
哈希计算方法比较常见，网上也有很多计算hash 值的函数。示例代码如下：
public class HashUtils {
/**
* FNV1_32_HASH
* @param obj
* object
* @return hashcode
**/
public static int hashcode(Object obj) {
final int p = 16777619;
int hash = (int) 2166136261L;
String str = obj.toString();
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0)
hash = Math.abs(hash);
//System.out.println("hash computer:" + hash);
return hash;
}
}哈希函数本身有两处边界处理需要留意：
Math.abs对Integer.MIN_VALUE无效：补码下该值没有对应的正数，Math.abs(Integer.MIN_VALUE)返回的仍是负数，if (hash < 0)这一层的意图在这个取值上落空。(int) 2166136261L的截断是有意的：FNV 的 offset basis 在 32 位补码下等于0x811C9DC5，作为有符号 int 是负数——环上的位置按这套有符号语义生成，前后自洽；把它当无符号下标解读就会错位。
环的语义是无符号的 int。生成、比较、查找三处保持同一语义，映射关系才稳定。
验证测试
一致性哈希算法实现后，接下来添加一个测试类，验证此算法时候正常。示例代码如下：
public class ConsistentHashTest {
public static final int NODE_SIZE = 10;
public static final int STRING_COUNT = 100 * 100;
private static ConsistentHash consistentHash = new ConsistentHash();
private static List<String> sList = new ArrayList<>();
public static void main(String[] args) {
// 增加节点
for (int i = 0; i < NODE_SIZE; i++) {
String ip = new StringBuilder("10.2.1.").append(i).toString(); consistentHash.addNode(ip);
}
// 生成需要缓存的数据;
for (int i = 0; i < STRING_COUNT; i++) {
sList.add(RandomStringUtils.randomAlphanumeric(10));
}
// 将数据放入到缓存中。
for (String s : sList) {
consistentHash.put(s, s);
}
for(int i = 0 ; i < 10 ; i ++) {
int index = RandomUtils.nextInt(0, STRING_COUNT);
String key = sList.get(index);
String cache = (String)consistentHash.get(key);
System.out.println("Random:"+index+",key:" + key + ",consistentHash get value:" + cache +",value is:" + key.equals(cache));
}
// 输出节点及数据分布情况
for (Node node : consistentHash.nodeList){
System.out.println(node);
}
// 新增一个数据节点
consistentHash.addNode("10.2.1.110");
for(int i = 0 ; i < 10 ; i ++) {
int index = RandomUtils.nextInt(0, STRING_COUNT);
String key = sList.get(index);
String cache = (String) consistentHash.get(key);
System.out.println("Random:"+index+",key:" + key + ",consistentHash get value:" + cache +",value is:" + key.equals(cache));
}
// 输出节点及数据分布情况
for (Node node : consistentHash.nodeList){
System.out.println(node);
}
}
}四个评判指标与一个重映射界
前面讲的原理与实现都不是凭空来的。一致性哈希出自 Karger 等人在 STOC 1997 上的工作（原题见「参考」）。
它最初要解决的是 Web 代理缓存的热点，而非「缓存怎么分片」这类通用问题：某些页面会在极短时间内被大量请求 —— 1994 年 Shoemaker-Levy 9 彗星撞击后的 JPL 站点、1997 年 IBM 的深蓝比赛页面，都属于把单台服务器或共享代理缓存压垮的情形。而当时通行的「对缓存机器数
四个评判指标
这里先定义一个方案该满足什么，再给算法。这四个指标可以直接用来判断任何一种分片方案：
| 指标 | 定义 | 违反它的后果 |
|---|---|---|
| 平衡性（Balance） | 不同 key 的哈希结果尽可能均匀落到各节点上 | 全部 key 挤在一台 |
| 单调性（Monotonicity） | 可用节点集合变化时，key 要么留在原节点、要么落到新加入的节点；不会从一个老节点挪到另一个老节点 | 加一台机器导致两台老机器之间的数据对调 |
| 分散性（Spread） | 同一个 key 在不同客户端视角下被分配到的节点集合尽量小 | 客户端看不到全部节点 → 同一 key 落在不同节点，同一份数据被缓存多份，存储效率下降 |
| 负载（Load） | 从服务器视角看，单台节点承担的 key 数量尽量少 | 一台节点要存远超均值的 key |
单调性是这里最关键的一条，它把「一致性」这个词说清楚了：扩容缩容时受影响的 key 应当局限在换手的那一段，而不是全局重排。这也解释了为什么对
重映射界
传统哈希在槽数变化时几乎所有 key 都要重映射。一致性哈希给出的界是
虚拟节点的最初形态
机制是：每个节点（桶）映射到的是一系列伪随机的点，而不是环上的单个点。这个设计承担两个作用：
- 削弱数据倾斜：一个节点的多个点把它的「份额」分散到环上各处，各节点分到的区间之和因此更接近均值 —— 这正是前面「数据倾斜与虚拟节点」一节在数学上的依据；
- 可调节比例：改变某个节点映射的点数，就能改变它承担的 key 比例。这让异构集群（机器容量不同）可以按容量分配负载，而不必假设每台机器一样大。
所以「虚拟节点」不是后来的工程补丁，它在原始方案里就有 —— 本笔记「一致性哈希算法实现」一节正是这个机制。
来源核对：以上四个指标、「每个桶映射到多个点」与重映射界三点，已对照 STOC 1997 的正文逐条核实；精确表述、定理编号与评估口径见下。
精确表述与定理
模型：哈希函数带一个 view 参数。view 是客户端可见的桶集合，各客户端的 view 可以不一致。STOC 1997 把一致性哈希形式化为 ranged hash function
| 指标 | 精确表述 |
|---|---|
| 平衡性 | 对固定 view |
| 单调性 | |
| 分散性 | 跨全部 view，一个条目被映射到的不同桶的数量 |
| 负载 | 跨全部 view，一个桶上出现的不同条目数量 |
构造：两张随机函数表——
定理 4.1 给出这个构造的四条性质：
重映射界（定理 4.4）：对单调且通用的 ranged hash 函数，view 从
代入扩容：
评估：STOC 版的结果是分析式的，没有实验。协议在
与工程实现的差别：Karger 1997 的哈希空间是单位区间
最后一个对照，把两种方案在扩容时的行为并列：
扩容前的环 ──[node0]──────────────[node1]──────────────[node2]──
│
node3 插到这一段中间
▼
扩容后的环 ──[node0]──────────────[node1]────[node3]────[node2]──
└─只有这一段换主─┘
期望换手量 = 1/N（N 为扩容后的节点数）相关
- 02-BASE 理论 —— 功能分区与分片是 BASE 的第一层动作，哈希环是分片的实现手段之一
- 03-一致性模型 —— 名字里的「一致性」指扩容缩容时映射的稳定性，与一致性模型说的不是同一件事，别混
参考
- David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. STOC 1997（第 29 届 ACM 计算理论研讨会）。
YJ