一致性Hash算法(consistent hash)

在分布式集群中,有三台服务器(0, 1, 2)用于缓存图片(图片不重名),我们可以$hash(图片名)\%3$ 的方式将图片存放到对应的服务器中,用户请求时,根据上式从对应的服务器上取到图片。但是,当我们增加或减少服务器个数的时候,由于映射函数变化,需要将所有的图片重新散列,才能找到正确的位置,涉及到大量文件的转移,无疑是成本巨大的。解决方法是采用一致性hash算法

对$2^{32}$取模

将ip地址映射为一个唯一的非负数字

$2^{32}$是ipv4地址的最大数量,保证任何ip地址取模后不会重复对应同一个数字;取模后取值范围为:$\{0, 1, 2, … , 2^{32}-1\}$, 将这些数字按顺序围成一个圆,称为 hash 环,将服务器放到 hash 环上,计算方法为:$hash(服务器IP地址)\%2^{32}$ ,这个结果就代表服务器

iphash

如图,将三台服务器A,B,C映射到 hash 环上;这时,我们有一些图片想存入这三台服务器中,将图片映射到 hash 环上,公式为$hash(图片名称)\%2^{32}$

picture hash

当服务器和图片都映射到 hash 环上后,将图片存放在顺时针方向最近的服务器上,即图片 1 存放在服务器 A 上,图片 2 存放在服务器 B 上;读取图片时同理

优点

当服务器 A 出现问题,移除服务器 A,只有映射到粉色部分的图片需要移动到服务器 C,hash 环上其他部分的图片不需要移动,避免了大量图片移动

bad move

与 hash 算法对比

  • 使用 hash 算法:当服务器数量发生变化时,所有服务器同时失效,所有资源需要重新分配
  • 使用一致性 hash 算法:当服务器数量发生变化时,其他服务器不受影响,只有一部分资源需要重新分配

hash 环倾斜问题

可以发现,服务器要存储的数据是与它逆时针最近的服务器之间的数据;如果服务器映射的太集中,有的服务器存放的数据太少,有的服务器存放的数据太多,导致有的服务器不能被充分利用,有的却饱和,当请求时,也会造成大量请求发送到同一个服务器上;我们希望服务器映射到 hash 环上均匀一些

hash oblique

如上图,服务器 B 存储了红色区域的数据;当服务器 B 坏掉时,服务器B,C之间的数据都要移动到服务器 A 中,增大了 A 的负载,超出 A 的承受能力还可能使 A 坏掉,并继续向后产生连锁反应,解决方法是使用虚拟节点

虚拟节点

在 hash 环上生成实际节点的虚拟节点,如果数据对应的是虚拟节点,则存放到虚拟节点对应的实际节点,虚拟节点使得服务分布的更均匀,数据分布的也就更均匀

virtual node

nginx 配置

1
2
3
4
5
upstream backend {
hash $consistent_key consistent;
server ip:port weight=1;
server ip:port weight=2;
}

如果 location 指定了一致性哈希 key,使用请求参数 cat 做 key,如果没有,使用请求 uri 做 key

1
2
3
4
5
6
7
location / {
set $consistent_key $arg_cat;
if ($consistent_key = "") {
set $consistent_key $request_uri;
}
}
}
您的支持鼓励我继续创作!