一致性哈希是分布式存储 负载均衡的重要算法，不废话，直接开整！！！
什么是分布式存储的负载均衡
例如，MySQL常见的分库分表，传统做法就是对ID哈希进行取模，然后根据余数路由到不同的数据库，表。如下图
这种做法缺点也明显
- 无法动态的扩容，缩容。数据量激增，也只能通过全库的数据迁移实现，成本太大。
面对缺点，一致性哈希为我们提供了思路。
一致性哈希
哈希环和节点映射
集群中存储节点 的相对位置都分布在一个 具有16384个位置（2^32）的环上。每个节点通过hash（IP） % 16384 ，得出自身在环的位置 这个过程便是节点映射。如下图，假设每个节点 Hash(IP) % 16384 得到的具体位置，可能的节点分布 如下图
数据映射
添加一条数据的工作原理如下：
Hash(Object.ID) % 16384 得出 取模结果
- 结果在 0 ~ 5461 ，数据 落在节点2
- 结果在 5461 ~ 10922 ，数据落在节点3
- 结果在 10922 ~ 16384，数据落在节点1
工作原理如下图
总结，如果数据取模结果落在哈希环上两个节点之间，则顺时针找到第一个节点就是 存储的位置。
动态扩容，缩容
扩容
如果新加一个节点4，机器映射后位于结点2和3之间， index 7700。如下图
数据迁移永远都是基于顺时针存储的规则，所以原先存储在节点3的取模范围在 5461~ 7777的数据会迁移到节点4。这样由于扩容导致的数据迁移只在两个节点之间进行，降本增效！！！
虚拟节点
一致性哈希，到此为止了？不，还有一种情况要考虑：
如上图，增加节点4之后导致3，4节点存储的数据太少了，大量的数据存储在节点1，节点2.。这是典型的数据倾斜问题呀！！！
解决方案也简单，每个节点引入多个虚拟节点。虚拟节点分布在环上，然后维护虚拟节点和真实节点的映射。这样看起来就像增加了节点数量，各节点之间紧凑，不会出现较大的节点空隙，不会造成数据倾斜。如下图
路由到虚拟节点的数据，最终映射真实节点。
总结
一致性哈希的出现解决了传统哈希路由动态扩容导致大量数据迁移的问题。
核心思想就是 将节点映射在哈希环上；添加数据时，将数据哈希取模映射到环上的一个位置，然后顺时针查找离位置最近的节点存储。
作为一种优秀的负载均衡、数据分片和容错方案，一致性哈希算法已经在分布式系统中得到广泛的应用。比如类似的Redis Cluster，分布式数据库。
