问题引入
传统数据库集群设计时的主要策略是，将数据的id通过哈希函数转换成一个哈希值key，然后对机器数量N取模，得到数据的存放位置。由此带来的问题是，当增加、删除机器或机器宕机时需要对所有数据id重新进行一遍哈希，然后进行大量的数据迁移。
为了解决分布式集群容量变化时带来的大量数据迁移问题，引入一致性哈希算法。
算法思想
把全量的缓存空间当作一个环形存储结构，环形空间总共分成2^32个区域。每个数据的id都可以通过hash函数转换成一个0~(2^32)-1的数字，并对应到环形空间的一个区域。每台机器也遵循相同hash算法，根据机器IP或域名映射到环形空间。
离每一个数据的哈希值key的顺时针方向最近的节点，负责存储该key的数据。实现将数据和节点对应起来。
(本文章多次引用了程序员小灰中的图片，侵删)节点变化
当集群节点变化时，只会引起一小部分的数据迁移。
新增节点时的变化情况：
移除节点时的变化情况：
虚拟节点
当机器较少时，机器的哈希值很大可能不能均匀分布在哈希环上，就会出现负载不均衡的情况。
一致性哈希算法引入虚拟节点机制来解决这种数据倾斜的问题。即对每一台机器通过多个哈希函数映射到多个位置，这些位置上的节点称为虚拟节点。（也可以通过在IP或域名后增加编号后缀再通过同一哈希函数映射到不同位置）
- 在增加节点时，会打破原来负载均衡的情况，新增节点会从原有节点分流数据的情况。把新增一个物理节点拆分成多个虚拟节点并均匀分布在哈希环上可以有效解决这个问题。
- 在移除节点时，也会造成负载不均衡的情况。但当移除的物理节点已经被拆分成多个虚拟节点时，数据倾斜的情况也会减小很多。
注意：这是指的“数据迁移”实际是指key的路由情况。在数据库集群场景下，可以是根据key值决定数据存储位置，集群变化时根据key指定决定是否将该数据进行迁移；在服务应用集群场景下，可以是根据请求url进行分流。
代码实现
实现一致性哈希算法主要是考虑哈希环的数据结构，哈希环上存储的是机器的哈希值。当有数据需要路由时，查找哈希环上大于待路由数据哈希值且最小的值，即为该数据路由的目标机器。
考虑机器集群是动态变化的，因此数据结构不适合选择数组。适合的数据结构有List和树，下面分析两种实现方案：
- List列表
将机器节点的hash值放入List，然后进行排序。待路由数据只需在List中找到第一个hash值大于它的机器节点即可。这样问题就变成了类似有序表查找。- 查找的算法可以用：顺序查找O(N)、二分查找O(logN)、跳表O(logN)
因此，排序+查找时间复杂度总共为O(N*logN)
- 树
节点的hash值有自然顺序，并且要求查找时间复杂度低。因此可以使用二叉查找树作为保存节点hash值的数据结构。JDK的TreeSet和TreeMap提供了红黑树的实现。