是否有支持密钥零重映射的一致性哈希算法？
Is there a consistent hashing algorithm that support zero remapping of keys?
我理解经典的一致性缓存算法，当adding/removing一个节点时，一些键必须重新映射到不同的节点。如果我放宽一些要求，是否有完全不支持重新映射的算法？
在我的应用程序中，我想将键增量分配给节点：
一旦一个键被分配给一个节点，它就会永远留在那里。
节点已添加但未删除。一个节点在添加后永远不会关闭 - 假设一个 replication/backup 机制在工作。
密钥不需要在节点之间均匀分布。尽力而为是可行的：添加新节点时，分配给它的新键多于旧节点。
这个场景有算法吗？
我可以想象出两个类似的变通办法，它们可以满足您的要求，但两者都带有可能无法接受的条件table:
- 如果缓存客户端知道第一次请求键的序列号，即如果缓存键包含单调递增的 ID 或某种版本号，那么您可以跟踪集群大小增加的序列号，并且根据当时存在的节点数计算hash。
- 如果您不介意两阶段查找，您可以保留一个键 → numnodes 查找 table 记录缓存键时有多少节点，然后用它来计算哈希码。或者只保留一个键→缓存节点查找 table.
（#2 的变体，如果两阶段查找没问题，但查找的大小 table 是一个问题：保留哈希（键）→ 缓存节点查找 table，以及使该散列尽可能小，以保持查找 table 小。如果两个键恰好具有相同的散列，它们最终会出现在同一个节点上——但如果不平衡，这不是问题t严格。）
这些技术都不依赖于一致的散列 — 只是简单的散列码 — 但两者都有很大的局限性。
在一般情况下，如果没有将密钥与首次缓存该密钥时的缓存状态信息相关联的东西，那么不，我认为您的要求是不可能的。
我理解经典的一致性缓存算法，当adding/removing一个节点时，一些键必须重新映射到不同的节点。如果我放宽一些要求，是否有完全不支持重新映射的算法？
在我的应用程序中，我想将键增量分配给节点：
一旦一个键被分配给一个节点，它就会永远留在那里。
节点已添加但未删除。一个节点在添加后永远不会关闭 - 假设一个 replication/backup 机制在工作。
密钥不需要在节点之间均匀分布。尽力而为是可行的：添加新节点时，分配给它的新键多于旧节点。
这个场景有算法吗？
我可以想象出两个类似的变通办法，它们可以满足您的要求，但两者都带有可能无法接受的条件table:
- 如果缓存客户端知道第一次请求键的序列号，即如果缓存键包含单调递增的 ID 或某种版本号，那么您可以跟踪集群大小增加的序列号，并且根据当时存在的节点数计算hash。
- 如果您不介意两阶段查找，您可以保留一个键 → numnodes 查找 table 记录缓存键时有多少节点，然后用它来计算哈希码。或者只保留一个键→缓存节点查找 table.
（#2 的变体，如果两阶段查找没问题，但查找的大小 table 是一个问题：保留哈希（键）→ 缓存节点查找 table，以及使该散列尽可能小，以保持查找 table 小。如果两个键恰好具有相同的散列，它们最终会出现在同一个节点上——但如果不平衡，这不是问题t严格。）
这些技术都不依赖于一致的散列 — 只是简单的散列码 — 但两者都有很大的局限性。
在一般情况下，如果没有将密钥与首次缓存该密钥时的缓存状态信息相关联的东西，那么不，我认为您的要求是不可能的。