hashtable - 一致性哈希：环的数据结构保存在哪里

Question

我们在一个环中有 N 个具有基本一致性哈希的缓存节点。

问题：

1. 是否存储了此环的数据结构：
   • 在每个节点上？
   • 部分在每个节点及其范围？
   • 在单独的机器上作为负载平衡器？
     
     
2. 当其他节点加入时，环会发生什么？

非常感谢。

Answer 1

我找到了问题 1 的答案。

答案1： 所有方法都写在我的博客中：http: //ivoroshilin.com/2013/07/15/distributed-caching-under-consistent-hashing/

在哪里保存环的数据结构有几个选项：

• 中央协调点：专用机器保持环并作为中央负载平衡器将请求路由到适当的节点。优点：非常简单的实现。这将非常适合具有少量节点和/或数据的动态系统。缺点：这种方法的一大缺点是可扩展性和可靠性。稳定的分布式系统没有单一的故障点。

• 没有中心协调点——完全复制：每个节点都保存环的完整副本。适用于稳定的网络。例如，此选项在 Amazon Dynamo 中使用。优点：查询在一跳中直接路由到适当的缓存服务器。缺点：从环中加入/离开服务器需要通知/修改环中的所有缓存服务器。

• 没有协调中心点——部分重复：每个节点都保留环的部分副本。此选项是 CHORD 算法的直接实现。就 DHT 而言，每台缓存机器都有其前任和继任者，当接收到查询时，会检查它是否具有密钥。如果那台机器上没有这样的键，则使用映射函数来确定它的哪个邻居（继任者和前任者）与该键的距离最小。然后它将查询转发给距离最短的邻居。该过程继续进行，直到当前的缓存机器找到密钥并将其发回。优点：对于高度动态的更改，由于节点之间闲聊的大量开销，以前的选项不适合。因此，此选项是这种情况下的选择。缺点：没有直接的消息路由。