一致性HASH，主要应用于分布式缓存中的负载均衡场景中，用来解决简单HASH中存在的动态伸缩问题，该算法最早在1997年由麻省理工学院提出，是一种特殊的哈希算法。

简单哈希在分布式应用中存在的问题

哈希算法，就是?将?任意长度的二进制值映射为较短的固定长度的二进制值，是一个KV键值对的映射关系。如果我们设计一个分布式缓存系统，用来缓存一些资源，为了避免热点问题，需要把这些资源存储在不同的机器上，如何分散的存储呢？根据普通的HASH算法路由，如取模，key%N，key是数据的key，N是机器节点数，将数据映射到具体的节点上。随着?数据?的?增加?，需要?添加?资源时候?，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，需要?重新?哈?希?，也就是?Rehash或者?数据迁移，资源?越来越大?的?时候?，REHASH时间越长?，带来?服务?不可用?的?风险?越大?，而?这种?设计?是?分布式?设计?中?最糟糕的?设计?。

一个良好设计的分布式系统应该具有最基本的单调性，即服务器的添加与移除不会造成大量的哈希重定位，而一致性哈希恰好可以解决这个问题。

解决简单哈希动态伸缩问题

一致性哈希如何在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0-2的32次方-1。整个空间按顺时针方向组织。

当客户端查询的时候，首先使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。

当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。

当删除一台机器的时候，也只需要把当前节点的缓存数据数据迁移到顺时针的下一个节点上即可。

如图所示

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。

然后将数据key使用相同的函数Hash计算出哈希值，定位到环上的位置，从此位置沿环顺时针“行走”，例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下

根据一致性Hash算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

添加节点的时候

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的节点X 上。其它数据也不会受到影响。

综上所述，一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

人生到处知何似，应似飞鸿踏雪泥，留下您的印记再走呗，感谢