Consistent Hashing

一貫性ハッシュとは、ノードの追加や削除時に再割り当てが行われるキーを 1/n だけに抑えるハッシュ技法であり、分散キャッシュやシャーディングで使われる。

目的

ノードの参加や離脱に伴うデータ移動を最小化する、分散ストレージと分散キャッシュの中核技術である。

メカニズム

ノードとキーを両方 0〜2^32 のハッシュリングへ配置し、各キーはそこから時計回りで最初のノードに属する。ノードの追加や削除は隣接区間のキーにのみ影響する。仮想ノード（ノードごとに複数のハッシュ点を置く）はバランスを改善する。負荷はほぼ均等に分散する。

ユースケース

分散キャッシュ（Memcached）
CDN ノードの分割
データベースのシャーディング（Cassandra）
サーバーの負荷分散

例

入力

Node C joins

Output

Only keys in C's adjacent arc migrate

Minimal migration

よくあるエラー

Too few virtual nodes causes uneven load: Use 150+ virtual nodes per node

関連用語

ハッシュテーブル（Hash Table）はハッシュ関数でキーをバケット配列に写し、平均 O(1) の検索・挿入・削除を提供する、最も使われるデータ構造の一つである。

ブルームフィルタは k 個のハッシュ関数とビット配列で集合の所属を近似し、偽陽性率と引き換えに容量効率を得る。

マークルツリーは葉にデータのハッシュ、内部ノードに子のハッシュを置く木構造である。大規模データの整合性検証を効率化し、Git やブロックチェーンで使われる。

References