Hash、分布式Hash与一致性哈希（Consistent Hashing）介绍

关于作者

作者简介：张帅，公众号：Flowlet，WeChat：yorkszhang

近年来，随着云计算和大数据等概念的出现，分布式系统得到了普及。有这样一种系统为许多高流量动态网站和 Web 应用程序提供分布式缓存，这其中就利用了一种称为一致性Hash的算法。

在云网络场景中为了支撑起千万级路由、百万级VPC在很多高性能分布式网关的设计中也借鉴了一致性hash的思想。

本文就带大家剥丝抽茧，详解：一致性hash的思想与原理：

1、一致性Hash（Consistent Hashing）的背景。

2、什么是Hash？

3、分布式Hash（Distributed Hashing）介绍。

4、一致性Hash（Consistent Hashing）原理。

5、一致性Hash（Consistent Hashing）实现算法介绍。

1、一致性hash背景

美国麻省理工学院在1997年发表的论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Releifying Hot Spots on the World Wide Web（一致性哈希和随机树：缓解万维网上的热点的分布式缓存协议）》中首次提出了一致性hash（Consistent hashing）的思想。

一致性hash算法可以有效地解决分布式结构下动态增加和删除节点所带来的问题。在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了一致性hash算法，可以说一致性hash算法是分布式系统负载均衡的首选算法。

2、什么是Hash？

Hash是将一个数据（通常是任意大小的对象）映射到另一固定大小的数据（通常是整数，称为哈希码）的过程。把将某数据映射到哈希码的这个函数，称为哈希函数。

例如：一些设计用于散列字符串的散列函数，输出范围为0 .. 100。可以将字符串映射Hello映射到数字57，World映射到数字40。

由于可能的输入比输出多得多，因此任何给定的数字都会有许多不同的字符串映射到它，这种现象称为碰撞。好的散列函数应该使得不同输入值的输出尽可能均匀地分布在输出范围内。

3、分布式Hash介绍

在云场景中当流量太大而无法在单台设备上处理时，就需要将网络请求分发到多台设备上进行处理。如何将不同的网络请求分发到不同的服务器上呢？

我们可能首先想到的方案是：取模算法hash（key）% N，即：对key进行hash运算后取模，N是机器的数量；

假设我们有三台服务器 ，A、B、C（标号0、1、2）并且我们有一些带有哈希值的字符串key：

这样，对key进行hash后的结果对3取模，得到的结果一定是0、1或者2，正好对应服务器A（0）、B（1）、C（2），存取数据直接找对应的服务器即可，简单粗暴，完全可以解决上述的问题。

取模算法虽然使用简单，但对机器数量取模，在集群扩容和收缩时却有一定的局限性：因为在生产环境中根据业务量的大小，调整服务器数量是常有的事；而服务器数量N发生变化后hash（key）% N计算的结果也会随之变化！

在我们之前的示例中，如果我们删除服务器 C，我们必须使用hash（key）% 2替代之前的hash（key）% 3，key的新位置将变为如下所示：

请注意此时想要访问一个key，这个key的所处的服务器全都发生改变，那么之前服务器缓存的key的数据也会失去作用与意义；

大量缓存在同一时间失效，造成缓存的雪崩，进而导致整个系统的不可用，这基本上是不能接受的；

那么，如何解决这个问题呢？我们需要一个不直接依赖于服务器数量的分配方案，以便在添加或删除服务器时，将需要重新定位的key的数量降至最低。于是一致性hash算法应运而生。

4、一致性Hash原理

一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求的服务器之间的映射关系；

一致性哈希解决了简单哈希算法在分布式哈希表（Distributed Hash Table，DHT）中存在的动态伸缩等问题；

一致性hash算法本质上也是一种取模算法；不过，不同于上边按服务器数量取模，一致性hash是对固定值2^32取模。（IPv4地址是由32位2进制数组成，所以用2^32可以保证每个IP地址会有唯一的映射；）

我们可以将这2^32个值抽象成一个圆环，圆环的正上方的点代表0，顺时针排列，以此类推：1、2、3…直到2^32-1，而这个由2的32次方个点组成的圆环统称为hash环；

• 我们将对象Key映射到Hash环上，前例中的对象将如下所示：

• 我们将服务器的IP地址（或某个 ID）映射到Hash环上：

• 对象key映射到服务器

从对象key的位置开始，沿逆时针方向遇到的第一个服务器，便是当前对象将要映射到的服务器；

为了确保对象Key在服务器之间均匀分布，我们需要引入虚拟节点来解决数据倾斜的问题。

我们为每台服务器分配多个虚拟节点，每台服务器对应的虚拟节点的数量（权重）取决于服务器的处理性能。例如，如果某台服务器的处理性能是其他服务器的两倍时，它可以分配其他服务器两倍的虚拟节点。

如下图所示A、B、C每台服务器的权重是10，则对象key映射到服务器的结果如下所示：

服务器扩缩容场景：

• 服务器减少

假设服务器C出现故障导致服务下线，将会导致虚拟节点C0-C9从图中消失，原本属于服务器C的任务将会被重新分配到服务器A跟B。而原本属于服务器A跟B的任务将会保持不变。

• 服务器增加 如果我们增加一台服务器D（权重10），则原本属于A、B、C服务器的任务的1/4将会分配给服务器D，其他保持不变。

5、一致性Hash实现

本文简要的介绍了一致性哈希算法，目前一致性哈希算法基本成为了分布式系统组件的标准配置。

具体一致性Hash算法的实现主要有：

• ketama算法
• Rendezvous hashing/HRW算法：1996年的论文 《A Name-Base Mapping Scheme for Rendezvous》中提出。

• Jump consistent hash算法：Google于2014年发表的论文《A Fast, Minimal Memory, Consistent Hash Algorithm》中提出。

• Consistent Hashing with Bounded Loads算法：Google在2017年发布论文《Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the www》中提出。

• Maglev Hash算法：Google在2016年发布的论文《Maglev: A Fast and Reliable Software Network Load Balancer》中提出。

6、总结

美国作为近现代科学的起源地，中国技术人员目前还主要局限于应用科学，我们与美国在基础理论科学方面的研究差距是巨大的。

希望做技术的人们不要被外界的声音弄的浮躁了，其实我们差距真的很大，共勉！

（正文完）

end

转载与投稿

文章转载需注明：Flowlet

欢迎云计算、SDN、NFV、互联网IT等方向的大牛投稿。

| 温馨提示 |

欢迎分享、收藏、点赞、转发。