ジャンプコンシステントハッシュはハッシュリングを5行で置き換えた

コンシステントハッシュは分散システムの現実的な問題を解決した。バケットが追加または削除されたときに、すべてのキーを再マッピングすることを避けるという問題である。しかし、通常のKarger方式のリングには運用上の負担が伴った。仮想ノード、ストレージ、そして調整して解消すべき不均一さである。

LampingとVeachのジャンプコンシステントハッシュは、より狭い問いを立てた。バケットに連番が振られている場合、リングを一切保存せずにキーの行き先を計算できるだろうか。彼らの答えは約5行のコードに収まった。

arXivの論文によれば、この手法はストレージを必要とせず、Kargerらのアルゴリズムより高速で、バケット数が変化した際にキー空間とワークロードの両方をより均等に分割する。そのトレードオフは明示されている。バケット番号が連番であるため、任意のWebキャッシュメンバーシップよりもストレージに適している。

最後のバケット変更まで直接ジャンプする

バケットIDを連番に限定したことで、メンバーシップリングが不要になった。

最小限の再マッピングはジャンプ過程から自然に導かれる。キーは、追加されたバケットがそのキーを獲得したときにのみ移動する。

ルックアップテーブルがなければ、再構築や配布が必要なメモリフットプリントも存在しない。

この制約は正直で有用である。この手法は、流動的なキャッシュ群よりもストレージシャードに適している。

データ構造が主に確率法則を保持するために存在しているなら、その法則を直接サンプリングし、構造自体を消し去れる場合がある。

ジャンプコンシステントハッシュは、安定した配置を小さな実装コストで必要とするシャーディングストレージ、データベース、ライブラリにとって、コンパクトな選択肢となった。その優雅さは制約にある。任意のバケット名を諦めれば、リング全体が消えるのだ。