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

Question

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

问题：

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

非常感谢。

Answer 1

我找到了问题 1 的答案。

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

关于在何处保留 ring 的数据结构有几个选项：

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

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

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