一致性哈希如何工作？

Question

我试图了解一致性哈希是如何工作的。这是我试图遵循但无法遵循的文章，首先我的问题是：

1. 我明白，服务器被映射到哈希码范围内，数据分布更加固定，看起来也很容易。但是这如何处理集群中添加新节点的问题呢？

2. 示例 java 代码不起作用，任何基于简单java的一致散列的建议。

更新

1. 一致性哈希的任何替代方案？

Answer 1

对于 python 实现请参阅我的github 存储库

最简单的解释什么是普通哈希？

假设我们必须将以下键值对存储在像 Redis 这样的分布式内存存储中。

假设我们有一个哈希函数 f(id)，它采用上面的 ids 并从中创建哈希值。假设我们有 3 台服务器 - （s1、s2 和 s3）

我们可以对服务器数量（即 3）进行哈希取模，以将每个密钥映射到服务器，我们剩下以下内容。

我们可以使用 f() 通过简单查找来检索键的值。对于密钥 Jackson 来说，f("Jackson")%(服务器数量) => 1211*3 = 2 (node-2)。

这看起来很完美，是的，很接近，但不是雪茄！

但是如果服务器说节点 1 宕机了怎么办？对用户 Jackson 应用相同的公式，即 f(id)%（服务器数量），1211%2 = 1 即，当实际密钥从上表散列到节点 2 时，我们得到节点 1。

我们可以在这里进行重新映射，如果我们有十亿个键怎么办，在这种情况下我们必须重新映射大量键，这很乏味:(

这是传统哈希技术的主要流程。

什么是一致性哈希？

在一致性哈希中，我们可视化圆环中所有节点的列表。（基本上是一个排序数组）

start func
For each node:
 Find f(node) where f is the hash function
 Append each f(node) to a sorted array
For any key
  Compute the hash f(key)
  Find the first f(node)>f(key)
  map it
end func

例如，如果我们必须对密钥 smith 进行哈希，我们计算哈希值 1123 ，找到哈希值 > 1123 的直接节点，即哈希值 1500 的节点 3

现在，如果我们失去了一个服务器，比如说我们失去了node-2，所有的键都可以映射到下一个服务器node-3:)是的，我们只需要重新映射node-2的键

Answer 2

我将回答你问题的第一部分。首先，该代码中有一些错误，因此我会寻找更好的示例。

这里以缓存服务器为例。

当您考虑一致性哈希时，您应该将其视为一个圆环，就像您链接到的文章所做的那样。当添加新服务器时，它一开始就没有数据。当客户端获取应该位于该服务器上的数据但找不到它时，就会发生缓存未命中。然后，程序应该在新节点上填充数据，因此将来的请求将被缓存命中。从缓存的角度来看，就是这样。