一致性哈希算法

为了解决这些问题，引入一致性哈希算法。假设数据的id通过哈希函数转换成的哈希值范围是$2^{32}$，也就是$O~2^{32}-1$的数字空间中。我们将这些数字头尾相连，想象成一个闭合的环形，那么一个数字id在计算出哈希值之后认为对应到环中的一个位置上

接下来，想象有三台机器也处于这样一个环中，这三台机器在环中的位置根据机器id计算出的哈希值来决定。那么一条数据如何确定归属哪台机器呢？首先把该数据的id用哈希值算出哈希值，并映射到环中的相应位置，然后顺时针找寻离这个位置最近的机器，那台机器就是该数据的归属。例如，下图有一个数据m，计算其hash值后映射到环上，那么他的归属就是2号机器

普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效，这样就大大的不满足单调性了。下面来分析一下一致性哈希算法是如何处理的

以上面的分布为例，如果Node2（机器2）出现故障被删除了，那么按照顺时针迁移的方法，Hash值属于图中红色片段的所有数据将会被迁移到Node3（机器）中，这样仅仅是红色的一段映射位置发生了变化，其它的对象没有任何的改动。如下图：

如果往集群中添加一个新的节点NODE4，通过对应的哈希算法得到KEY4，并映射到环中，如下图：

按照顺时针迁移的规则，数据Hash值处于红色段的数据被迁移到了Node4中，其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析，一致性哈希算法在保持了单调性的同时，数据的迁移时间达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力

其实上面的一致性哈希函数还存在一个很大的问题，我们说Hash函数是输入的样本量很大的时候，其输出结果在输出域上是均匀分布的，但是这里假如只有三个输入，就很难保证分布是均匀的，有可能产生下图所示的分布，就导致负载极其不均衡

更加优化的一致性哈希算法引入了虚拟节点机制，即对每一台机器产生多个结点，称为虚拟节点。具体做法可以在机器ip或主机名的后面增加编号或端口号来实现。假设一台机器有1000个虚拟节点，3台机器就有3000个结点，3000个结点映射到哈希域上就相对比较均匀了