一致性哈希

type

status

date

slug

summary

负载均衡

假设我们有一个快递管理站，有 4 个货柜，对于一个新的货物，我们该分配给谁呢？

一种方案是顺序分配，即根据货物的 id 对 4 取余（简单哈希），分配给对应编号的货柜。

此时我们需要新添加一个货柜呢？我们可以用新的算法 id 对 5 取余来分配。这时候遇到了一个问题，原来的货物必须也重新分配，否则用户就不能根据新的算法来找到之前的货物了。这是一个很大的麻烦，因为在重新分配的过程中，我们的服务会有很长一段时间不可使用，并且每次扩缩容都会出现这个问题。

简单哈希的问题在于扩缩容的时候需要修改哈希算法，一致性哈希不需要修改哈希算法。假设我们最多能安装 100 个货柜，那哈希结果是货物的 id 对 100 取余。

得到货物的哈希结果以后，怎么找到货柜呢？

我们可以将货柜的编号也进行哈希计算，得到货柜的哈希结果。这样在地址空间上就会有 4 个货柜的哈希值。对于每个货物，我们都找到大于等于货物的哈希结果值的第一个货柜哈希值，得到实际存储这个货物的货柜。

当然，对于货物的哈希值等于 97 这样的结果，我们可以用环的思想，再去找到编号为 1 的货柜。也就是说，哈希空间实际上是这样的：

这种方法是如何解决前面的问题的呢？

假设我们增加一个货柜，那么我们就一定会在这个哈希环上增加一个货柜节点，如下：

那么，有哪些货物受到影响呢？

按照前面的方法，对于每个货物，我们都找到大于等于货物的哈希结果值的第一个货柜哈希值，得到实际存储这个货物的货柜。这里，0～65 和 81～100 的货物都不需要调整位置，只有哈希值是 65～81 的货物需要从 4 号货柜搬运到 5 号货柜。因此，需要停止服务的货柜大大减少，并且处理时间也缩短了。

同样的，如果我们移除了一个货柜，需要做的也只是把这个货柜上的货物，搬运到哈希环上的下一个货柜节点。

代码实现

总结

这里对一致性哈希做了简单的原理介绍和代码展示。

更复杂的情况是，如果货柜哈希值差异很大导致某些货柜需要容纳更多货物，怎么样让货物的分配更均匀呢？我们可以给每个货柜增加很多个虚假的”分身“，这样哈希环上的货柜间隔就会尽可能地接近，在存取的时候再根据“分身”找到实际的货柜，这样就可以避免数据不均匀的情况了。