algorithm - 是否有支持密钥零重映射的一致哈希算法？

Question

我理解经典的一致缓存算法，在添加/删除节点时，必须将一些键重新映射到不同的节点。如果我放宽一些要求，是否有一种算法完全不支持重新映射？

在我的应用程序中，我想逐步将键分配给节点：

1. 一旦一个键被分配给一个节点，它就会永远留在那里。

2. 节点被添加但不被移除。一个节点在添加后永远不会关闭 - 假设一个复制/备份机制在工作。

3. 密钥不需要在节点之间均匀分布。尽力而为：当添加一个新节点时，分配给它的新键比旧节点多。

   这种情况有算法吗？

Answer 1

我可以想象两种类似的解决方法，它们可以为您提供您所要求的，但两者都带有可能不可接受的条件：

1. 如果缓存客户端知道第一次请求键的顺序，即如果缓存键包括某种单调递增的 id 或版本号，那么您可以跟踪集群大小增加的序列号，并根据当时存在的节点数。
2. 如果您不介意两阶段查找，则可以保留一个 key → numnodes 查找表，该表记录了缓存一个键时有多少个节点，然后使用它来计算哈希码。或者只保留一个键 → 缓存节点查找表。

（如果两阶段查找可以，则 #2 的变体，但查找表的大小是一个问题：保留一个哈希（键）→缓存节点查找表，并使该哈希尽可能小，以保持查找表很小。如果两个键碰巧有相同的散列，它们最终会在同一个节点上——但如果平衡不严格，这不是问题。）

这些技术甚至都不依赖于一致的散列——只是简单的散列码——但两者都有很大的局限性。

在一般情况下，如果没有将密钥与第一次缓存该密钥时有关缓存状态的信息联系起来，那么不，我认为您要求的内容是不可能的。