五张图理解一致性Hash原理

　　啥是Hash值?

　　hash(散列，杂糅)函数，是将任意长度的数据映射到有限长度的域上。直观解释起来，就是对一串数据m进行杂糅，输出另一段固定长度的数据h，作为这段数据的特征(指纹)。

　　如何保证无论数据块m多大，其输出值h为固定长度?

　　将m分成固定长度(如128位)，依次进行hash运算，然后用不同的方法迭代即可(如前一块的hash值与后一块的hash值进行异或)。如果不够128位用0补全或者用1补全随意，算法中约定就可以了。

　　为了解决什么问题?

　　分布式系统中实现负载均衡，常常需要将同一个客户端发送的请求指定到同一个服务器端来做处理，包括缓存，Session持久等场景。

　　Hash取模方式

　　最开始的方式是通过对客户端某特征的Hash值取模，例如：对客户端IP地址Hash后取模，根据模寻找服务器。

　　Hash取模方式的弊端

　　这种方式在服务器个数固定不变时没有问题。如果需要弹性扩容或故障停机的情况下，原来的取模公式就会发生变化：Hash(IP) % 4会变成Hash(IP) % ?。此时IP地址经过取模运算的结果将发生很大变化，根据模值获取的服务器也会变得不可控。

　　一致性Hash的原理

　　为避免上述Hash取模方式的问题，提出一致性Hash解决方案。目的是当服务器个数发生变动时，尽可能少的影响客户端到服务器的映射关系。

　　环形Hash空间

　　通常的Hash算法都是将value映射为一个32位的key值，也即是0 ~ 2^32-1的数值空间。我们可以将这个空间想象成一个首尾相连的环。

　　把服务器映射到环形空间上

　　利用服务器的某特征的Hash值，将服务器映射到环形空间上。服务器与服务器的间隔即是各服务器的管理区域。

　　把客户端映射到环形空间

　　将客户端映射到环形空间，形成服务器和客户端Hash值的交替出现情况。

　　客户端逆时针(顺时针也行，只要保证规则一致即可)找到离自己最近的服务器Hash值，算作客户端与此服务器建立映射关系。

　　添加服务器节点

　　Server#4为新增服务器节点，将原来Server#3到Server#0管辖的区域分割成两部分，受影响的客户端只有Client#2。它由原来与Server#0建立的映射关系变成与Server#4建立映射关系。

　　同理，删除服务器节点也只会影响部分节点。

　　一致性Hash就是将原来点到点的映射关系变成点到线的映射关系，从而减少因服务器个数变化引起的映射关系变化。

　　一致性Hash的优化

　　为了尽量实现各服务器的负载均衡，在上述基础上，将同一台服务器影分身成多个虚拟节点来达到负载均衡的目的。

​