一致性 Hash 算法

典型的集群服务里有 N 台机器，正常情况下一个请求会随机地分配到某一台服务器上。对于分布式缓存服务，我们会要求同一个 key 的请求都落在同一台机器上，那么我们可以根据 key 对机器数目进行取模得到目标服务器。但这会造成一个问题，如果我们需要增加一台服务器，那就需要对当前已经存在的缓存全部换入换出，无法平稳过渡。这就引出了一致性 Hash 算法。

原理

我们假设有一个 Hash 算法能够将 key 映射到 $[0,2^{32}]$ ，我们将这个区间想象成一个圆。首先我们将 $N$ 台服务器作为 key，通过 Hash 算法映射到 Hash 空间，假设是 $S_1,S_2,...S_N$ 。然后我们将请求的 key 也通过 Hash 算法映射到这个圆上，为 $K$ 。现在我们从 $K$ 位置开始顺时针前进，直到遇到第一个 $S_k$ 。这个 $S_k$ 所对应的服务器，便是该 key 的映射位置。

通过一致性 Hash，就可以很容易地进行服务节点的增加或者减少（增加一个节点，仅需要迁移后一个节点的数据），而不会影响到其他原有的映射关系。

虚拟节点

如果我们的服务器很少，就很容易遇到数据倾斜的问题。有个简单的解决方案就是增加虚拟节点。对于某一台服务器，我们可以用 $k$ 一致性 Hash 函数得到 $k$ 个虚拟节点，再映射到圆上。这样，我们在整个 Hash 空间中就有 $kN$ 个节点，就能大大缓解数据倾斜的问题。