前言
“
孤单的人啊孤单的歌
孤单的时候别唱情歌
写歌的人写着他的寂寞
不一定和你适合
悲伤的人啊悲伤的歌
悲伤的剧情不同角色
编剧的人编着谁的快乐
何必演的那么深刻
都是平凡的人
不是仙也不是神
不悲不喜
该得不可得
爱过的疼过的好聚又好散的
幻想中苦笑不得
不悲不喜该得不可得
见过的路过的得到又失去的
虚幻中成疯成魔
”
在敲代码的时候，来一首寂寞的歌，无限循环中，多了些不一样的滋味。
之前，我们聊过分布式系统设计实践，详细的可以查看一下之前的原创发文。其中，提到了分布式系统设计实践中常用的算法，一致性Hash算法。并没有细致的对其做讲解，今天碰巧遇到小伙伴问，那么把这个说一下。
简单说明
一致性哈希算法，是一种分布式哈希(DHT)算法，主要解决了分布式哈希的单调性和分散性问题。
单调性，指的要对已经存在的内容能够正常映射，避免在节点增减过程中，无法命中，类似于上文说的哈希取模分配，如果几点不断增加，计算方式就会失去平衡。分散性，指的就是解决哈希取模分配的不平衡问题。
一致性哈希的论文发表于1997年，阅读无障碍的同学可以直接看看大佬的论文理解更深刻，附上论文下载链接：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879
哈希
既然我们要聊一致性Hash，首先要把Hash这个基础概念理解透彻、弄明白。
哈希（Hash）是最常见的数据分布形式。
常见的哈希算法有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等。
常见散列方法
哈希（Hash）实现方式是通过散列方法，通过计算，就可以映射数据和处理节点关系。
常见的散列方法如下：
- 直接定址法：取关键字或关键字的某个线性函数值为散列地址，这个线性函数的定义多种多样，没有标准。
- 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
- 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的，取的位数由表长决定。
- 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
- 取模法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(key) = key % p（p<= M），不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要，一般取素数或 m，若 p 选择不好，容易产生冲突。
普通哈希算法负载均衡
场景：
在分布式系统环境下，数据库采用了水平分库，不同机器上安装了相同的库。那么，该如何选择哪个机器节点进行增删改查？
很明显，我们如何选择节点，就是需要选择一个合适的方式进行负载均衡。假使我们采用普通的hash算法进行负载均衡，并选择简单的「取模法」来说明这个过程。
假设有 3 个服务器节点编号 [0 - 2]，6 次动作编号 [1 - 6]，则完成哈希映射之后，三个节点数据映射情况如下：
哈希计算公式：动作% 节点总数 = Hash节点下标
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
5 % 3 = 2
6 % 3 = 0
通过Hash取模法，每个动作都均匀的分散到了三个不同的服务器节点上，看起来很完美！
但是，在分布式集群系统的负载均衡实现上，这种模型有两个问题：
1. 扩展能力差
在弹性伸缩的性能要求下，服务节点经常需要扩容缩容。
节点变化使原来计算的哈希值不准确，为了达到负载均衡的效果，要重新计算并更新哈希值，对于更新后哈希值不一致的原动作归属，要迁移到更新后的节点上去。
假设新增了 1 个服务器节点，由原来的 3 个服务节点变成 4 个节点编号 [0 - 3]，哈希映射情况如下：
哈希计算公式：动作% 节点总数 = Hash节点下标
1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0
5 % 4 = 1
6 % 4 = 2
可以看到后面三个 ：4、5、6 对应的存储节点全部失效了，这就需要把这几个节点的缓存数据迁移到更新后的节点上 (费时费力) ，也就是由原来的节点 [1, 2, 0] 迁移到节点 [0, 1, 2]，迁移后存储示意图如下：
2. 容错能力不佳
线上环境服务节点虽然有各种高可用性保证，但还是是有宕机的可能，即使没有宕机也有缩容的需求。不管是宕机和缩容都可以归结为服务节点删除的情况，下面分析下服务节点删除对负载均衡哈希值的影响。
同理，面对服务器节点减少，仍要面对Hash重新计算，数据迁移的问题。
一致性哈希算法
普通哈希算法实现的负载均衡各种各样的实际问题，所以我们引入一致性哈希算法。
一致性哈希，哈希函数计算方法不变，通过构建环状的 Hash 空间替代了原来普通的线性 Hash 空间。
哈希环，是一个足够大的Hash空间（一般是 0 ~ 2^32）
哈希环构建完毕，我们可以根据上边的场景采用一致性Hash形式，进行优化。
可以用服务器的 IP 或 主机名计算得到哈希值，计算得到的哈希值就是服务节点放置在 Hash 环上。
最后，对每个操作同样也计算一次哈希值，计算之后的哈希也映射到环上，沿顺时针的方向找到的环上的第一个节点。下图举例展示了节点的选择情况。
扩展能力提升
相较普通的Hash方式，扩展能力得到了一定提升。那么，一致性哈希是如何解决这个问题的呢？
我们看一下，如下图所示，当服务器集群要新增一个节点时，会发生什么。受影响的只有动作3，本来3是在ip：0，现在移到ip：3上 即可，其余节点存储的数据保持不动。
容错能力提升
普通哈希算法当某一服务节点宕机下线，也会导致原来哈希映射的大面积失效，失效的映射触发数据迁移影响服务性能，容错能力不足。一起来看下一致性哈希是如何提升容错能力的。
如下图所示，假设一个节点宕机下线，则只需按顺时针方向选择新的节点存放即可，不会对其他节点数据产生影响。一致性哈希能把节点宕机造成的影响控制在顺时针相邻节点之间，避免对整个集群造成影响。
一致性哈希优化
存在的问题
上边我们介绍了一致性哈希如何解决普通哈希的扩展和容错问题，原理比较简单，在理想情况下可以良好运行，但在实际使用中还有一些实际问题需要考虑，下面具体分析。
数据倾斜
哈希环的空间很大，如果节点比较少，这会导致什么问题呢？
可能的一种情况是，较少的服务节点哈希值聚集在一起，比如下图所示这种情况，数据按顺时针寻找节点就导致全都存储到一个节点上去，给单个节点很大的压力！这种情况称为数据倾斜。
一致性哈希-数据倾斜
节点雪崩
数据倾斜和节点宕机都可能会导致缓存雪崩。
数据倾斜导致所有数据都打到 单个节点上面，有可能会导致被压垮，节点宕机，数据又都打到 另一个节点上面，之后又进行传递。这时候故障就像像雪崩时滚雪球一样越滚越大。
还有一种情况是节点由于各种原因宕机下线。在数据量特别大的情况下也可能导致节点雪崩。
总之，连锁反应导致的整个缓存集群不可用，就称为节点雪崩。
虚拟节点
一致性Hash，通过创建「虚拟节点」的方式解决。
之前我们说，一致性Hash解决了单调性、分散性。其中关键的一个技术就是虚拟节点。
所谓虚拟节点，就是对原来单一的物理节点在哈希环上虚拟出几个它的分身节点，这些分身节点称为「虚拟节点」。打到分身节点上的数据实际上也是映射到分身对应的物理节点上，这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分，解决了数据倾斜问题。
由于虚拟节点分散在哈希环各个部分，当某个节点宕机下线，他所存储的数据会被均匀分配给其他各个节点，避免对单一节点突发压力导致的节点雪崩问题。
下图展示了虚拟节点的哈希环分布，其中左边是没做虚拟节点情况下的节点分布，右侧是完成虚拟节点配置的节点分布
一致性哈希-虚拟节点
总结
嗖嗖嗖，高大上的算法，实现起来，真的也就那么一回事。特别是在面试中，很多时候，面试官的刁难从一致性Hash开始。那么，相信，今天我们聊完，已经对一致性hash有深入理解了，来来来，吊打面试官吧！！
继续听歌！
