一致性Hash算法
前言
Github:https://github.com/HealerJean
来源:https://mp.weixin.qq.com/s/WTz1KA9kOGrqFVTtALJzjQ
1、一致性 Hash 算法背景
我们有三台缓存服务器编号node0
、node1
、node2
,现在有 3000
万个key
,希望可以将这些个 key 均匀的缓存到三台机器上,你会想到什么方案呢?
我们可能首先想到的方案是:取模算法hash(key)% N
,即:对 key 进行 hash 运算后取模,N 是机器的数量;
这样,对 key
进行 hash
后的结果对 3
取模,得到的结果一定是 0
、1
或者 2
,正好对应服务器node0
、node1
、node2
,存取数据直接找对应的服务器即可,简单粗暴,完全可以解决上述的问题;
1.1、缺点
取模算法虽然使用简单,但对机器数量取模,在集群扩容和收缩时却有一定的局限性:因为在生产环境中根据业务量的大小,调整服务器数量是常有的事;
而服务器数量 N 发生变化后hash(key)% N
计算的结果也会随之变化!
比如:一个服务器节点挂了,计算公式从hash(key)% 3
变成了hash(key)% 2
,结果会发生变化,此时想要访问一个 key,这个 key 的缓存位置大概率会发生改变,那么之前缓存 key 的数据也会失去作用与意义;
大量缓存在同一时间失效,造成缓存的雪崩,进而导致整个缓存系统的不可用,这基本上是不能接受的;
为了解决优化上述情况,一致性 hash 算法应运而生~
2、一致性 Hash 算法详述
2.1、算法原理
一致性哈希算法在 1997 年由麻省理工学院提出,是一种特殊的哈希算法,在移除或者添加一个服务器时,能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系;
解决:一致性哈希解决了简单哈希算法在分布式哈希表(Distributed Hash Table,DHT)中存在的动态伸缩等问题;
一致性 hash 算法本质上也是一种取模算法; 不过,不同于上边按服务器数量取模,一致性 hash
是对固定值 2^32 取模;**IPv4 的地址是 4 组 8 位 2 进制数组成,所以用 2^32 可以保证每个 IP
地址会有唯一的映射; **
举例:192.168.1.1是用十进制表示的,而IP4的概念里32位 指的是二进制,192.168.1.1转换成二进制后为1100 0000.1010 1000.0000 0001.0000 0001,八位二进制数字最大可以表示的范围即2的八次方=256,这也就是为什么我们日常所见的IP地址的有效范围是0~-255
2.1.1、hash
环
我们可以将这
2^32
个值抽象成一个圆环 ⭕️,圆环的正上方的点代表 0,顺时针排列,以此类推:1、2、3…直到2^32-1
,而这个由 2 的 32 次方个点组成的圆环统称为hash环
;
2.1.2、服务器映射到 hash 环
在对服务器进行映射时,使用
hash(服务器ip)% 2^32
,即:使用服务器IP
地址进行hash
计算,用哈希后的结果对2^32
取模,结果一定是一个 0 到2^32-1
之间的整数;而这个整数映射在 hash 环上的位置代表了一个服务器,依次 将
node0
、node1
、node2
三个缓存服务器映射到 hash 环上;
2.1.3、对象 key 映射到服务器
在对对应的 Key 映射到具体的服务器时,需要首先计算 Key 的 Hash 值:
hash(key)% 2^32
;
将 Key 映射至服务器遵循下面的逻辑:
从缓存对象 key 的位置开始,沿顺时针方向遇到的第一个服务器,便是当前对象将要缓存到的服务器;
假设我们有 “semlinker”、”kakuqo”、”lolo”、”fer” 四个对象,分别简写为 o1、o2、o3 和 o4;
首先,使用哈希函数计算这个对象的 hash 值,值的范围是 [0, 2^32-1]:
hash(o1) = k1;
hash(o2) = k2;
hash(o3) = k3;
hash(o4) = k4;
同时 3 台缓存服务器,分别为 CS1、CS2 和 CS3:
’
K1 => CS1
K4 => CS3
K2 => CS2
K3 => CS1
2.1.4、服务器缩容扩容
2.1.4.1、缩容
假设
CS3
服务器出现故障导致服务下线,这时原本存储于CS3
服务器的对象o4
,需要被重新分配至CS2
服务器,其它对象仍存储在原有的机器上:此时受影响的数据只有 CS2 和 CS3 服务器之间的部分数据!
2.1.3.2、扩容
假如业务量激增,我们需要增加一台服务器 CS4,经过同样的 hash 运算,该服务器最终落于 t1 和 t2 服务器之间,具体如下图所示:
此时,只有 t1
和 t2
服务器之间的部分对象需要重新分配;
在以上示例中只有 o3
对象需要重新分配,即它被重新到 CS4
服务器;
在前面我们已经说过:如果使用简单的取模方法,当新添加服务器时可能会导致大部分缓存失效,而使用一致性哈希算法后,这种情况得到了较大的改善,因为只有少部分对象需要重新分配!
2.2、数据偏斜&服务器性能平衡问题
在上面给出的例子中,各个服务器几乎是平均被均摊到 Hash 环上;但是在实际场景中很难选取到一个 Hash 函数这么完美的将各个服务器散列到 Hash 环上;此时,在服务器节点数量太少的情况下,很容易因为节点分布不均匀而造成数据倾斜问题;
问题1:如下图被缓存的对象大部分缓存在
node-4
服务器上,导致其他节点资源浪费,系统压力大部分集中在node-4
节点上,这样的集群是非常不健康的:问题2:在上面新增服务器 CS4 时,CS4 只分担了 CS1 服务器的负载,服务器 CS2 和 CS3 并没有因为 CS4 服务器的加入而减少负载压力;如果 CS4 服务器的性能与原有服务器的性能一致甚至可能更高,那么这种结果并不是我们所期望的;
2.2.1、虚拟节点
针对上面的问题,我们可以通过:引入虚拟节点来解决负载不均衡的问题:
即将每台物理服务器虚拟为一组虚拟服务器,将虚拟服务器放置到哈希环上,如果要确定对象的服务器,需先确定对象的虚拟服务器,再由虚拟服务器确定物理服务器;
在图中:o1 和 o2 表示对象,v1 ~ v6 表示虚拟服务器,s1 ~ s3 表示实际的物理服务器;
2.2.2、虚拟节点的计算
虚拟节点的 hash
计算通常可以采用:对应节点的 IP
地址加数字编号后缀 hash
(10.24.23.227#1) 的方式;
举个例子,node-1 节点 IP 为 10.24.23.227,正常计算node-1
的 hash 值:
⬤ hash(10.24.23.227#1)% 2^32
假设我们给 node-1 设置三个虚拟节点,node-1#1
、node-1#2
、node-1#3
,对它们进行 hash 后取模:
⬤ hash(10.24.23.227#1)% 2^32
⬤ hash(10.24.23.227#2)% 2^32
⬤ hash(10.24.23.227#3)% 2^32
⬤ 分配的虚拟节点个数越多,映射在
hash
环上才会越趋于均匀,节点太少的话很难看出效果;⬤ 引入虚拟节点的同时也增加了新的问题,要做虚拟节点和真实节点间的映射,
对象key->虚拟节点->实际节点
之间的转换;
2.2.3、使用场景
一致性
hash
在分布式系统中应该是实现负载均衡的首选算法,它的实现比较灵活,既可以在客户端实现,也可以在中间件上实现,比如日常使用较多的缓存中间件memcached
和redis
集群都有用到它;
其它的应用场景还有很多:
方法 RPC
框架Dubbo
用来选择服务提供者
- 分布式关系数据库分库分表:数据与节点的映射关系
LVS
负载均衡调度器- ……
3、一致性 Hash
算法实现
3.1、不带虚拟节点的一致性哈希算法
import org.junit.Test;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* 不带虚拟节点的一致性Hash算法
*/
public class ConsistentHashingWithoutVirtualNode {
/**
* 待添加入Hash环的服务器列表
*/
private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};
/**
* key表示服务器的hash值,value表示服务器
*/
private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
/**
* 程序初始化,将所有的服务器放入sortedMap中
*/
static {
for (String server : servers) {
int hash = getHash(server);
System.out.println("[" + server + "]加入集合中, 其Hash值为" + hash);
sortedMap.put(hash, server);
}
System.out.println();
}
/**
* 得到应当路由到的结点
*/
private static String getServer(String key) {
//得到该key的hash值
int hash = getHash(key);
//得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(subMap.isEmpty()){
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
return sortedMap.get(i);
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
return subMap.get(i);
}
}
/**
* 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
*/
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
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);
}
return hash;
}
@Test
public void test(){
String[] keys = {"太阳", "月亮", "星星"};
for (String key : keys) {
System.out.println("[" + key + "]的hash值为" + getHash(key) + ", 被路由到结点[" + getServer(key) + "]");
}
}
}
3.1.2、日志打印
[192.168.0.0:111]加入集合中, 其Hash值为575774686
[192.168.0.1:111]加入集合中, 其Hash值为8518713
[192.168.0.2:111]加入集合中, 其Hash值为1361847097
[192.168.0.3:111]加入集合中, 其Hash值为1171828661
[192.168.0.4:111]加入集合中, 其Hash值为1764547046
[太阳]的hash值为1977106057, 被路由到结点[192.168.0.1:111]
[月亮]的hash值为1132637661, 被路由到结点[192.168.0.3:111]
[星星]的hash值为880019273, 被路由到结点[192.168.0.3:111]
3.2、带虚拟节点的一致性哈希算法
import org.apache.commons.lang3.StringUtils;
import java.util.*;
/**
* 带虚拟节点的一致性Hash算法
*/
public class ConsistentHashingWithVirtualNode {
/**
* 待添加入Hash环的服务器列表
*/
private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};
/**
* 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
*/
private static List<String> realNodes = new LinkedList<>();
/**
* 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
*/
private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
/**
* 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
*/
private static final int VIRTUAL_NODES = 5;
static {
//先把原始的服务器添加到真实结点列表中
Collections.addAll(realNodes, servers);
//再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
for (String str : realNodes) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
String virtualNodeName = str + "&&VN" + i;
int hash = getHash(virtualNodeName);
System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
/**
* 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
*/
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
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);
}
return hash;
}
/**
* 得到应当路由到的结点
*/
private static String getServer(String key) {
//得到该key的hash值
int hash = getHash(key);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if (subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = virtualNodes.firstKey();
//返回对应的服务器
virtualNode = virtualNodes.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
virtualNode = subMap.get(i);
}
//virtualNode虚拟节点名称要截取一下
if (StringUtils.isNotBlank(virtualNode)) {
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
return null;
}
public static void main(String[] args) {
String[] keys = {"太阳", "月亮", "星星"};
for (String key : keys) {
System.out.println("[" + key + "]的hash值为" + getHash(key) + ", 被路由到结点[" + getServer(key) + "]");
}
}
}
3.2.1、日志打印
虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075
虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081
虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370
虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914
虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629
虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288
虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309
虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528
虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861
虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551
虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222
虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840
虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480
虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074
虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136
虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251
虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739
虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370
虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500
虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780
虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010
虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390
虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117
虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803
虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678
[太阳]的hash值为1977106057, 被路由到结点[192.168.0.2:111]
[月亮]的hash值为1132637661, 被路由到结点[192.168.0.4:111]
[星星]的hash值为880019273, 被路由到结点[192.168.0.3:111]