来源

一致性哈希算法

简称DHT，主要应用于分布式缓存中，可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。

首先，我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区，在Redis中则是把缓存key分配到16384个slot。
每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。
我们的每一个缓存节点（Shard）也遵循同样的Hash算法，比如利用IP做Hash，映射到环形空间当中。
如何让key和节点对应起来呢？很简单，每一个key的顺时针方向最近节点，就是key所归属的存储节点。所以图中key1存储于node1，key2，key3存储于node2，key4存储于node3。

当增加或删除节点时

增加节点
当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。

有哪些key会受到影响呢？图中加入了新节点node4，处于node1和node2之间，按照顺时针规则，从node1到node4之间的缓存不再归属于node2，而是归属于新节点node4。因此受影响的key只有key2。
最终把key2的缓存数据从node2迁移到node4，就形成了新的符合一致性哈希规则的缓存结构。
删除节点
当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。

有哪些key会受到影响呢？图中删除了原节点node3，按照顺时针规则，原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

最终把key4的缓存数据从node3迁移到node1，就形成了新的符合一致性哈希规则的缓存结构。

缓存节点都是按IP来Hash到环形空间，可能会出现分布不均匀的情况，比如所有的key都归属于同一个节点。

基于原来的物理节点映射出N个子节点，最后把所有的子节点映射到环形空间上。
【数据结构与算法】一致性哈希算法
如上图所示，假如node1的ip是192.168.1.109，那么原node1节点在环形空间的位置就是hash（“192.168.1.109”）。

我们基于node1构建两个虚拟节点，node1-1 和 node1-2，虚拟节点在环形空间的位置可以利用（IP+后缀）计算，例如：

hash（“192.168.1.109#1”），hash（“192.168.1.109#2”）

此时，环形空间中不再有物理节点node1，node2，只有虚拟节点node1-1，node1-2，node2-1，node2-2。由于虚拟节点数量较多，缓存key与虚拟节点的映射关系也变得相对均衡了。

由于分布式缓存系统的节点部署变化更频繁，而传统关系型数据库的分布分表相对稳定，不过mysql，仍然可以用一致性哈希表的思想，虽然处理逻辑会复杂一些，却可以避免动态水平扩展时候的尴尬。

一致性哈希算法，举个栗子：
我们钟表有 60 分钟，从 0 开始到 59，共 60 个点。
现在我们将机器往这 60 个点分配，规则如下：
hash(ip) % 60。

假设有 3 台机器 A，B 和 C，分别被分配到了 14，37 和 46 这三个点上。

图片的分配规则类似：
hash(image_id) % 60。
现有 3 张图片 x， y， z，分别被分配到 5，30，50 这三个点。
【数据结构与算法】一致性哈希算法
很明示，图片都没被分配到机器的节点上，怎么办呢?在钟表上顺时钟往前寻找，第一台遇到的机器，就是它的归属。

— 我是分割线 —

现在很不凑巧，A B C 三台机器分别分配到 5，10，15 这三个点。这样对 A 是很不公平的吖，要负责存储绝大多数的图片，那这怎么办呢?我们*核心价值观基本内容：和谐、平等、公正。为建设和谐社会努力奋斗！！

为了避免不必要的争端，我们引入“虚拟节点”，每台机器都可以拔一根汗毛，变成若干台，把虚拟节点分散到 60 个点上，归属“虚拟节点”的图片，均保存到它的真身。这样就能解决分配不均匀的问题。

应用时，将 60 替换下即可，如替换为 2的 32 次方