我们在第二期中讲过，HASH算法是一种非常快速的查找算法，可以用于对数据进行分区和分片。但是有一个问题。根据常规哈希算法算出来的哈希值，通常是无法扩展的，也就是说，假如说，我们一开始想将数据分成四个数据片，随着我们数据量的增长，四个数据片都接近了系统的极限，现在我们想加入一个新的数据片。这时使用传统的哈希算法，通常是无法做到的。只能讲数据重新在汇总起来再重新分成五分，这样就导致了巨大的运维成本。
那么有没有能够扩展的哈希算法呢，有的，这就是一致性哈希算法
一致性哈希算法
一致性哈希算法是1997年在论文Consistent hashing and random trees中被提出 ，在分布式系统中应用非常广泛。一致性哈希是一种哈希算法，简单地说在移除或者添加一个服务器时，此算法能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，尽可能满足单调性的要求。
一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0~232-1。整个空间按顺时针方向组织。0~232-1在零点中方向重合。接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性
算法实例
假如说我们只有三台服务器，那么经过哈希函数，所有落在server1和server3 之间的 key值都会区访问server3上的数据分片，所有落在server3 和server2的key值都会去访问server2的分片，所有落在server2 和server1之间的key值都会去访问server1的分片
那么现在我们增加一个server4，这时候原有的映射是不变的，只有落在server3和server4之间的key值原来事需要访问Server2，现在需要调整到Server4，那就是需要仅仅迁移这一部分数据
，这样的工作量远远少于我们一开始提到，把所有的数据重新汇总在分开。
以上就是一致性HASH算法的原理。
