一致性哈希，为什么需要 Vnode？

Question

我对一致性哈希的理解是，您采用一个密钥空间，对密钥进行哈希处理，然后按 360 进行取模，然后将值放入一个环中。然后，在该环上均匀分布节点。您可以通过从散列密钥所在的位置顺时针查看来选择处理该密钥的节点。

然后在许多解释中他们继续描述Vnode。在引用 dynamo 论文的riak 文档中，他们说：

The basic consistent hashing algorithm presents some challenges. First, the random position assignment of each node on the ring leads to non-uniform data and load distribution.

然后他们继续提出 Vnodes 作为确保输入密钥空间在环周围均匀分布的一种方法。据我了解，要点是 Vnode 划分范围的次数比机器多得多。假设您有 10 台机器，则可能有 100 个 Vnode，并且单个机器的 Vnode 将随机分散在环周围。

现在我的问题是为什么需要这个额外的 Vnode 步骤。哈希函数应该提供其输出的均匀分布，因此这似乎是不必要的。根据这个答案，即使哈希函数的模仍然是均匀分布的。

Answer 1

在我看来，大多数关于一致性哈希的解释所缺少的关键信息是，它们没有详细说明有关“多个哈希函数”的部分。

\n

无论出于何种原因，大多数“傻瓜一致性哈希”文章都掩盖了使虚拟节点以随机分布方式工作的实现细节。

\n

在讨论它如何工作之前，让我通过一个它不工作的例子来澄清上面的内容。

\n

怎么不起作用​

\n

vnode 的简单实现如下所示：

\n

\n来源

\n

这是很幼稚的，因为您会注意到，例如，绿色 vnode 始终位于蓝色 vnode 之前。这意味着，如果绿色 vnode 离线，那么它将仅被蓝色 vnode 取代，这违背了从单令牌节点迁移到分布式虚拟节点的整个目的。

\n

文章很快提到practically, Vnodes are randomly distributed across the cluster。然后它显示了一张单独的图片来表明这一点，但没有解释如何实现这一点的机制。

\n

它是如何运作的

\n

vnode 的随机分布是通过使用多个唯一的哈希函数来实现的。这些多重函数就是随机分布的来源。

\n

这使得实现看起来大致如下：

\n

A) 环的形成

\n

\n
1. 您有一个n由物理节点组成的环physical_nodes = [\'192.168.1.1\', \'192.168.1.2\', \'192.168.1.3\', \'192.168.1.4\']；（将此视为B/R/P/G上一张图片的左侧）
\n
2. 您决定将每个物理节点分布为k“虚拟切片”，即单个物理节点被切片k\n
   \n
   1. 在此示例中，我们使用k = 4，但实际上我们使用应该使用k \xe2\x89\x88 log ₂来获得合理平衡的负载，以便在整个数据存储中(num_items)存储总计num_items
   \n
   \n
\n
3. 这意味着num_virtual_nodes == n * k; （对应上图右侧的16块）
\n
4. k为每个via分配一个唯一的哈希算法hash_funcs = [md5, sha, crc, etc]\n
   \n
   1. （也可以使用递归调用k次的单个函数）
   \n
   \n
\n
5. 按以下方式划分环：
\n

\n

virtual_physical_map = {}\nvirtual_node_ids = []\nfor hash_func in hash_funcs:\n  for physical_node in physical_nodes:\n    virtual_hash = hash_func(physical_node)\n    virtual_node_ids.append(virtual_hash)\n    virtual_physical_map[virtual_hash] = physical_node\nvirtual_node_ids.sort()\n

\n

您现在拥有一个由n * k虚拟节点组成的环，这些虚拟节点随机分布在n物理节点上。

\n

B) 分区请求流程

\n

\n
1. 分区请求是通过提供的key_tuple密钥来发出的
\n
2. 被key_tuple散列得到key_hash
\n
3. 通过以下方式找到下一个顺时针节点virtual_node = binary_search(key_hash, virtual_node_ids)
\n
4. 通过查找真实节点physical_id = virtual_physical_map[virtual_node]
\n

\n

斯坦福讲座的第 6 页对我理解这一点非常有帮助。

\n

最终效果是 vnode 在环上的分布如下所示：

\n

\n来源

\n

Answer 2

First, the random position assignment of each node on the ring leads to non-uniform data and load distribution.

好的哈希函数提供均匀分布，但输入的数量也必须足够大，才能使它们看起来分散。钥匙是，但服务器不是。因此，经过 360 度哈希和取模的一百万个密钥将均匀分布在环上，但如果您仅使用 3 个服务器 S1 到 S3 来保存键值对，则无法保证它们可能被哈希（使用与密钥相同的哈希函数）统一在环上的位置 0、120 和 240 处。S1 可能在 10 处进行哈希处理，S2 在 12 处进行哈希处理，S3 在 50 处进行哈希处理。因此，与其他两个相比，S2 持有的 KV 对要少得多。通过拥有虚拟服务器，您可以增加它们在环上均匀散列的机会。

另一个好处是当添加或删除服务器时均匀地重新分配密钥，如文档中所述。