java - 一致性哈希如何工作？

Question

我正在尝试了解一致性哈希的工作原理。这是我正在尝试的文章 follow但无法理解，首先我的问题是:

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

2. 示例 java 代码不工作，任何基于简单 java 的一致性哈希的建议。

更新

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

Answer 1

对于 python 实现，请引用我的 github repo

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

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

假设我们有一个散列函数 f(id) ，它接受上述 ids 并从中创建散列。假设我们有 3 台服务器 - (s1, s2 and s3)

我们可以通过服务器数量(即 3)对哈希取模，将每个键映射到一个服务器，我们得到以下结果。

我们可以使用 f() 通过简单的查找来检索键的值。对于关键 Jackson 来说，f("Jackson")%(no of servers) => 1211*3 = 2 (node-2).

这看起来很完美，是的，但不是雪茄!

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

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

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

什么是一致性哈希？

在 Consistent hashing 中，我们可视化圆环中所有节点的列表。(基本上是一个排序数组)

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

例如，如果我们要散列 key smith，我们计算散列值 1123，找到散列值 > 1123 的直接节点，即散列值 1500 的节点 3

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