hashtable - 一致性哈希 : Where is the data-structure of ring kept

Question

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

问题:

这个环的数据结构是否存储:

在每个节点上？

部分在每个节点及其范围？

在单独的机器上作为负载平衡器？

当其他节点加入时，环会发生什么？

非常感谢。

Answer 1

我找到了问题 1 的答案。

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

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

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

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

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