共计 4909 个字符，预计需要花费 13 分钟才能阅读完成。
很多同学应该都晓得什么是哈希函数，在后端面试和开发中会遇到「一致性哈希」，那么什么是一致性哈希呢？名字听起来很厉害的样子，其实原理并不简单，这篇文章带你彻底搞懂一致性哈希！
进入主题前，先来一场缓和刺激的模仿面试吧。
模仿面试
面试官：看你简历上写参加了一个大型项目，用到了分布式缓存集群，那你说说你们是怎么做缓存负载平衡？
萌新：这个我晓得，咱们用的是轮询形式，第一个 key 给第一个存储节点，第二个 key 给第二个，以此类推。
面试官：还有其余解决方案吗？
萌新：能够用哈希函数，把申请打散随机调配到缓存集群内机器。
面试官：思考过这种哈希形式负载平衡的扩展性和容错性吗？
萌新：…
面试官：回去等告诉吧。
以上如有雷同，算你抄我的。
什么是哈希
数据结构中咱们学习过哈希表也称为散列表，咱们来回顾下散列表的定义。
散列表，是依据键间接拜访在指定贮存地位数据的数据结构。通过计算一个对于键的函数也称为哈希函数，将所需查问的数据映射到表中一个地位来拜访记录，放慢查找速度。这个映射函数称做「散列函数」，寄存记录的数组称做散列表。
散列函数能使对一个数据序列的拜访过程更加迅速无效，是一种空间换工夫的算法，通过散列函数数据元素将被更快定位。
下图示意了字符串通过哈希函数映射到哈希表的过程。没错，输出字符串是用脸滚键盘打进去的：）
常见的哈希算法有 MD5、CRC、MurmurHash 等算法。
MD5 算法
MD5 音讯摘要算法（英语：MD5 Message-Digest Algorithm），一种被宽泛应用的明码散列函数，能够产生出一个 128 位（16 字节）的散列值（hash value），MD5 算法将数据（如一段文字）运算变为另一固定长度值，是散列算法的根底原理。由美国明码学家 Ronald Linn Rivest 设计，于 1992 年公开并在 RFC 1321 中被加以标准。
CRC 算法
循环冗余校验（Cyclic Redundancy Check）是一种依据网络数据包或电脑文件等数据，产生简短固定位数校验码的一种散列函数，由 W. Wesley Peterson 于 1961 年发表。生成的数字在传输或者存储之前计算出来并且附加到数据前面，而后接管方进行测验确定数据是否发生变化。因为本函数易于用二进制的电脑硬件应用、容易进行数学分析并且尤其长于检测传输通道烦扰引起的谬误，因而取得广泛应用。
MurmurHash
MurmurHash 是一种非加密型哈希函数，实用于个别的哈希检索操作。由 Austin Appleby 在 2008 年创造，并呈现了多个变种，与其它风行的哈希函数相比，对于规律性较强的键，MurmurHash 的随机散布特色体现更良好。
这个算法曾经被很多开源我的项目应用，比方 libstdc++ (4.6 版)、Perl、nginx (不早于 1.0.1 版)、Rubinius、libmemcached、maatkit、Hadoop 等。
常见散列办法
- 间接定址法：取关键字或关键字的某个线性函数值为散列地址，这个线性函数的定义多种多样，没有规范。
- 数字分析法：假如关键字是以 r 为基的数，并且哈希表中可能呈现的关键字都是当时晓得的，则可取关键字的若干数位组成哈希地址。
- 平方取中法：取关键字平方后的两头几位为哈希地址。通常在选定哈希函数时不肯定能晓得关键字的全副状况，取其中的哪几位也不肯定适合，而一个数平方后的两头几位数和数的每一位都相干，由此使随机散布的关键字失去的哈希地址也是随机的，取的位数由表长决定。
- 折叠法：将关键字宰割成位数雷同的几局部（最初一部分的位数能够不同），而后取这几局部的叠加和（舍去进位）作为哈希地址。
- 取模法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(key) = key % p（p<= M），不仅能够对关键字间接取模，也可在折叠法、平方取中法等运算之后取模。对 p 的抉择很重要，个别取素数或 m，若 p 抉择不好，容易产生抵触。
缓存零碎负载平衡
在分布式集群缓存的负载平衡实现中，比方 memcached 缓存集群，须要把缓存数据的 key 利用哈希函数散列，这样缓存数据可能均匀分布到各个分布式存储节点上，要实现这样的负载平衡个别能够用哈希算法来实现。下图演示了这一分布式存储过程：
一般哈希算法负载平衡
后面咱们介绍过各种散列办法，不论是抉择上述哪种散列办法，在这个利用场景下，都是要把缓存数据利用哈希函数平均的映射到服务器集群上，咱们就抉择简略的「取模法」来阐明这个过程。
假如有 3 个服务器节点编号 [0 – 2]，6 个缓存键值对编号 [1 – 6]，则实现哈希映射之后，三个缓存数据映射状况如下：
哈希计算公式：key % 节点总数 = Hash 节点下标
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
5 % 3 = 2
6 % 3 = 0
每个连贯都平均的扩散到了三个不同的服务器节点上，看起来很完满！
然而，在分布式集群零碎的负载平衡实现上，这种模型有两个问题：
1. 扩大能力差
为了动静调节服务能力，服务节点常常须要扩容缩容。打个比方，如果是电商服务，双十一期间的服务机器数量必定要比平时大很多，新加进来的机器会使原来计算的哈希值不精确，为了达到负载平衡的成果，要从新计算并更新哈希值，对于更新后哈希值不统一的缓存数据，要迁徙到更新后的节点下来。
假如新增了 1 个服务器节点，由原来的 3 个服务节点变成 4 个节点编号 [0 – 3]，哈希映射状况如下：
哈希计算公式：key % 节点总数 = Hash 节点下标
1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0
5 % 4 = 1
6 % 4 = 2能够看到前面三个缓存 key：4、5、6 对应的存储节点全副生效了，这就须要把这几个节点的缓存数据迁徙到更新后的节点上 (费时费力)，也就是由原来的节点 [1, 2, 0] 迁徙到节点 [0, 1, 2]，迁徙后存储示意图如下：
2. 容错能力不佳
线上环境服务节点尽管有各种高可用性保障，但还是是有宕机的可能，即便没有宕机也有缩容的需要。不论是宕机和缩容都能够归结为服务节点删除的状况，上面剖析下服务节点删除对负载平衡哈希值的影响。
假如删除 1 个服务器节点，由最后的 3 个服务节点变成 2 个，节点编号 [0 – 1]，哈希映射状况如下：
哈希计算公式：key % 节点总数 = Hash 节点下标
1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1
6 % 2 = 0下图展现一般哈希负载平衡算法在一个节点宕机时候，导致的的缓存数据迁徙散布状况：
如图所见，在这个例子中，仅仅删除了一个服务节点，也导致了哈希值的大面积更新，哈希值的更新也是意味着节点缓存数据的迁徙（缓存数据示意心好累）。
一致性哈希算法负载平衡
正是因为一般哈希算法实现的缓存负载平衡存在扩大能力和容错能力差问题，所以咱们引入一致性哈希算法，那么什么是一致性哈希呢？先来看下 wiki 上对一致性 Hash 的定义
统一哈希由 MIT 的 David Karger 及其合作者提出，当初这一思维曾经扩大到其它畛域。在这篇 1997 年发表的学术论文中介绍了统一哈希如何利用于用户易变的分布式 Web 服务中。统一哈希也可用于实现强壮缓存来缩小大型 Web 利用中零碎局部生效带来的负面影响。
这篇形容一致性哈希的论文发表于 1997 年，浏览无障碍的同学能够间接看看大佬的论文了解更粗浅，附上论文下载链接：http://citeseerx.ist.psu.edu/…
一句话概括一致性哈希：就是一般取模哈希算法的改良版，哈希函数计算方法不变，只不过是通过构建环状的 Hash 空间代替一般的线性 Hash 空间。具体做法如下：
首先，抉择一个足够大的 Hash 空间（个别是 0 ~ 2^32）形成一个哈希环。
而后，对于缓存集群内的每个存储服务器节点计算 Hash 值，能够用服务器的 IP 或 主机名计算失去哈希值，计算失去的哈希值就是服务节点在 Hash 环上的地位。
最初，对每个须要存储的数据 key 同样也计算一次哈希值，计算之后的哈希也映射到环上，数据存储的地位是沿顺时针的方向找到的环上的第一个节点。下图举例展现了节点存储的数据状况，咱们上面的阐明也是基于目前的存储状况来开展。
原理讲完了，来看看为什么这样的设计能解决下面一般哈希的两个问题。
扩大能力晋升
后面咱们剖析过，一般哈希算法当须要扩容减少服务节点的时候，会导致原油哈希映射大面积生效。当初，咱们来看下一致性哈希是如何解决这个问题的。
如下图所示，当缓存服务集群要新增一个节点 node3 时，受影响的只有 key3 对应的数据 value3，此时只需把 value3 由原来的节点 node0 迁徙到新增节点 node3 即可，其余节点存储的数据放弃不动。
容错能力晋升
一般哈希算法当某一服务节点宕机下线，也会导致原来哈希映射的大面积生效，生效的映射触发数据迁徙影响缓存服务性能，容错能力有余。一起来看下一致性哈希是如何晋升容错能力的。
如下图所示，假如 node2 节点宕机下线，则原来存储于 node2 的数据 value2 和 value5，只需按顺时针方向抉择新的存储节点 node0 寄存即可，不会对其余节点数据产生影响。一致性哈希能把节点宕机造成的影响管制在顺时针相邻节点之间，防止对整个集群造成影响。
一致性哈希优化
存在的问题
下面展现了一致性哈希如何解决一般哈希的扩大和容错问题，原理比较简单，在现实状况下能够良好运行，但在理论应用中还有一些理论问题须要思考，上面具体分析。
数据歪斜
试想一下若缓存集群内的服务节点比拟少，就像咱们例子中的三个节点，而哈希环的空间又有很大（个别是 0 ~ 2^32），这会导致什么问题呢？
可能的一种状况是，较少的服务节点哈希值汇集在一起，比方下图所示这种状况 node0、node1、node2 汇集在一起，缓存数据的 key 哈希都映射到 node2 的顺时针方向，数据按顺时针寻找存储节点就导致全都存储到 node0 下来，给单个节点很大的压力！这种状况称为数据歪斜。
节点雪崩
数据歪斜和节点宕机都可能会导致缓存雪崩。
拿后面数据歪斜的示例来说，数据歪斜导致所有缓存数据都打到 node0 下面，有可能会导致 node0 不堪重负被压垮了，node0 宕机，数据又都打到 node1 下面把 node1 也打垮了，node1 也被打趴传递给 node2，这时候故障就像像雪崩时滚雪球一样越滚越大。
还有一种状况是节点因为各种起因宕机下线。比方下图所示的节点 node2 下线导致本来在 node2 的数据压到 node0 , 在数据量特地大的状况下也可能导致节点雪崩，具体过程就像方才的剖析一样。
总之，连锁反应导致的整个缓存集群不可用，就称为节点雪崩。
虚构节点
那该如何解决上述两个辣手的问题呢？能够通过「虚构节点」的形式解决。
所谓虚构节点，就是对原来繁多的物理节点在哈希环上虚构出几个它的分身节点，这些分身节点称为「虚构节点」。打到分身节点上的数据实际上也是映射到分身对应的物理节点上，这样一个物理节点能够通过虚构节点的形式平均扩散在哈希环的各个局部，解决了数据歪斜问题。
因为虚构节点扩散在哈希环各个局部，当某个节点宕机下线，他所存储的数据会被平均调配给其余各个节点，防止对繁多节点突发压力导致的节点雪崩问题。
下图展现了虚构节点的哈希环散布，其中右边是没做虚构节点状况下的节点散布，左边背景色绿色两个的 node0 节点是 node0 节点的虚构节点；背景色红色的 node1 节点是 node1 的虚构节点。
总结一下
本文首先介绍了什么是哈希算法和常见的哈希算法，以及常见散列形式，接着阐明基于一般哈希算法的缓存负载平衡实现，并举例说明一般算法的扩展性和容错性不便存在的问题。
为了解决一般算法的扩展性和容错性问题引入一致性哈希算法，图解和举例剖析了一致性哈希是如何进步扩展性和容错性。最初毛糙的一致性哈希算法也存在数据歪斜和节点雪崩的问题，解说了如何利用虚构节点优化一致性哈希算法，解决数据歪斜和雪崩问题。至此，一致性哈希你学会了吗？
再聊两句（求三连）
感激各位的浏览，文章的目标是分享对常识的了解，技术类文章我都会重复求证以求最大水平保障准确性，若文中呈现显著纰漏也欢送指出，咱们一起在探讨中学习。
如果感觉文章写的还行，对你有所帮忙，不要白票 lemon，动动手指导个「在看」或「分享」是对我继续创作的最大反对。
明天的技术分享就到这里，咱们下期再见。
