一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题。
简介:
一致性哈希算法是1997年在论文Consistenthashingandrandomtrees中被提出，在分布式系统中应用非常广泛。一致性哈希是一种哈希算法，简单地说在移除或者添加一个服务器时，此算法能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，尽可能满足单调性的要求。在普通分布式集群中，服务请求与处理请求服务器之间可以一一对应，也就是说固定服务请求与处理服务器之间的映射关系，某个请求由固定的服务器去处理。这种方式无法对整个系统进行负载均衡，可能会造成某些服务器过于繁忙以至于无法处理新来的请求。而另一些服务器则过于空闲，整体系统的资源利用率低，并且当分布式集群中的某个服务器宕机，会直接导致某些服务请求无法处理 。
进一步的改进可以利用hash算法对服务请求与处理服务器之间的关系进行映射，以达到动态分配的目的。通过hash算法对服务请求进行转换，转换后的结果对服务器节点值进行取模运算，取模后的值就是服务请求对应的请求处理服务器。这种方法可以应对节点失效的情况，当某个分布式集群节点宕机，服务请求可以通过hash算法重新分配到其他可用的服务器上。避免了无法处理请求的状况出现 。
但这种方法的缺陷也很明显，如果服务器中保存有服务请求对应的数据，那么如果重新计算请求的hash值，会造成大量的请求被重定位到不同的服务器而造成请求所要使用的数据失效，这种情况在分布式系统中是非常糟糕的。一个设计良好的分布式系统应该具有良好的单调性，即服务器的添加与移除不会造成大量的哈希重定位，而一致性哈希恰好可以解决这个问题。
一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0~232-1。整个空间按顺时针方向组织。0~232-1在零点中方向重合。接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
特点：
可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。
更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。
