みんな大好き consistent hash ですね!
最近提案された Multi-probe consistent hashing が素晴らしいですね.
Jump consistent hash http://qiita.com/syoyo/items/96fb03e3d26c8c8a8c83 に続く, cool な consitent hash 関数になります.
特徴
- ハッシュテーブル以外にストレージを必要としない
Jump consitent hash との違い.
Jump consitent hash も効率のよいハッシュを計算しますが, 任意のノードを削除することができないという欠点がありました. つまり N ノードあれば, 1, 2, 3, 4, ... N と連続している必要があり, どれかのノードが任意に消えてしまうような想定がある分散 KVS な用途では使えませんでした.
Multi-probe consistent hashing は, Karger らの手法(Ring consitent hash)と, Lamping and Veach(Jump consitent hash) のいいとこ取りのような手法になっています.
実装
まとめ
分散 KVS 用途に最適そう.
Acknowledgement に Google を救った男, Eric Veach がいますね. 素晴らしい!