一致性哈希算法
问题举例
均衡负载问题：搭建Redis集群（3机），key落到哪台机？
使用哈希算法
通过计算hash来求得hash值。 如公式 h=hash(key)%3，我们把Redis编号设置成0,1,2来保存对应hash计算出来的值，h的值等于Redis对应的编号。 但是hash算法也会面临容错性和扩展性的问题。
- 容错性：系统中的某个服务出现问题时，不能影响其他系统；
- 扩展性：加入新的服务器后，整个系统能正确高效运行。
现假设有一台Redis服务器宕机了，那么为了填补空缺，要将宕机的服务器从编号列表中移除，此时每个key就要按h = Hash(key) % 2重新计算。同样，如果新增一台服务器，规则也同样需要重新计算，h = Hash(key) % 4。
大量的key会重定向到其他服务器中，造成缓存命中率降低，而这种情况在分布式系统中是十分糟糕的。在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
一致性哈希算法
我们可以把一致哈希算法（Consistent hashing）看成是对 2^32 进行取模运算的结果值组织成一个圆环，这个圆环被称为哈希环。
一致性哈希要进行两步哈希：
- 对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
- 当对数据进行存储或访问时，对数据进行哈希映射；
对「数据」进行哈希映射得到一个结果，往顺时针的方向的找到第一个节点找到存储该数据的节点
假设节点数量从 3 增加到了 4，新的节点 D 经过哈希计算后映射到了下图中的位置。可以看到，key-01、key-03 都不受影响，只有 key-02 需要被迁移节点 D。
假设节点数量从 3 减少到了 2，比如将节点 A 移除。可以看到，key-02 和 key-03 不会受到影响，只有 key-01 需要被迁移节点 B
结论
在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响，减少了扩缩容时的数据迁移量。
一致性哈希算法 + 虚拟节点
一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，可能会有大量的请求集中在一个节点上。如图，有一半以上的数据的寻址都会找节点 A，导致负载不均衡。
要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。
但问题是实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。
而且，有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对配置更好的节点增加更多的虚拟机节点。
结论
带虚拟节点的一致性哈希方法不仅适合节点扩缩容的场景，而且还能实现节点均衡分布，甚至支持节点硬件配置不同的场景（加权负载均衡）。