解決方案
一致性雜湊解決了一個真實的分散式系統問題:當桶(bucket)增加或移除時,避免重新對映每一個鍵。但常見的 Karger 式環帶來了維運上的包袱:虛擬節點、儲存空間,以及需要調校消除的不均勻性。
Lamping 與 Veach 的跳躍一致性雜湊提出了一個更狹窄的問題:如果桶是依序編號的,能否在不儲存任何環的情況下計算出鍵的目的地?他們的答案大約五行程式碼就能寫完。
arXiv 論文指出,此方法不需要儲存空間,比 Karger 等人的演算法更快,且在桶數量變動時,能更均勻地劃分鍵空間與工作負載。它的取捨很明確:依序的桶編號讓它更適合儲存用途,而非任意成員組成的網頁快取。
它達成了什麼
直接跳躍到最後一次桶變動
為何有效
限制桶必須使用依序的 ID,消除了對成員環的需求。
最小重新對映是跳躍過程自然產生的結果:只有當新增的桶贏得某個鍵時,該鍵才會移動。
沒有查表就意味著沒有需要重建或分發的記憶體佔用。
這項限制誠實且有用:這個技巧更適合儲存分片,而非變動頻繁的快取叢集。
可套用之處
如果某個資料結構主要只是為了維持某種機率法則而存在,有時可以直接對該法則取樣,讓整個結構消失。
後續發展
跳躍一致性雜湊成為分片儲存、資料庫與函式庫的一個精簡選項,適合需要穩定配置且實作成本極低的情境。它的優雅之處在於這項限制:放棄任意的桶名稱,整個環就消失了。
追溯依據
參考來源
- A Fast, Minimal Memory, Consistent Hash Algorithm arXiv · arxiv.org ·