コンシステントハッシュ法

2024年8月11日 #DHT

概要

コンシステントハッシュ法 (consistent hashing) は分散システムにおいて処理やデータを均等に分散させるためのハッシュ技術である。Chord のような分散ハッシュテーブルにおけるオブジェクトロケーションのアルゴリズムとして使用されている。

コンシステントハッシュはノードとデータを同じハッシュ空間上にマッピングし、データはその空間上で最も近いノードに割り当てられる。ハッシュによる単純な配置ではノードの追加や削除が発生したときに大規模なデータの再配置 (リハッシュ) が必要となるが、コンシステントハッシュでは追加/削除のノードに隣接するノードとの間でデータを移動するだけで済む。このためシステムのスケーラビリティが高く、負荷分散が効率的に行われることから大規模な分散システムに向いている。

あるリソースを担当できる機能をスロット (slot) と呼ぶ。分散ハッシュテーブルに参加するノードは 1 つ以上のスロットを持つ。リソースとスロットは共に \(R=[0,2^k-1]\) 範囲のユニークな ID を持っている。ID の形成する余剰環をハッシュリングと呼ぶ。