是否有一致的哈希算法支持密鑰的零重新映射？

Question

我明白經典的一致性緩存算法，當添加/刪除一個節點時，一些密鑰必須重新映射到不同的節點。如果我放鬆了一些要求，是否有算法支持不重映射？

在我的申請，我希望逐漸分配鍵節點：

1. 一旦密鑰已經被分配到一個節點，它保持永遠存在。

2. 節點已添加但未刪除。一個節點在添加後永遠不會關閉 - 假設工作中有一個複製/備份機制。

3. 密鑰不需要在節點間均勻分佈。盡力而爲：當新節點被添加時，與舊節點相比，更多的新密鑰被分配給它。

   有沒有這種情況下的算法？

Answer 1

我可以像兩個相似的解決方法，可以給你，你要問什麼，但都配備了條件，可能是不能接受的：

1. 如果緩存客戶知道按什麼順序按鍵分別爲首先要求的，即如果緩存鍵包括某種單調增加的id或版本號，則可以跟蹤簇大小增加的序列號，並根據當時存在的節點數計算散列值。
2. 如果您不介意兩階段查找，您可以保留一個密鑰→numnodes查找表，記錄在密鑰緩存時有多少個節點，然後使用它來計算哈希代碼。或者只保留一個鍵→cachenode查找表。

（如果兩階段查找正常，但查找表的大小是一個問題，請注意以下問題：保留哈希（密鑰）→cachenode查找表，並使該哈希小至您需要的是保持查找表小。如果兩個鍵碰巧具有相同的哈希，他們最終在同一個節點上 - 但如果平衡不嚴格，這不是一個問題）

這些都不。技術甚至依賴於一致的哈希 - 只是天真的哈希代碼 - 但兩者都相當有限。

在一般情況下，沒有什麼能夠在密鑰首次緩存時將關鍵字與關於緩存狀態的信息聯繫起來，那麼不，我不認爲你所要求的是可能的。