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

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

コンピュータ科学におけるコンシステントハッシュ法（Consistent hashing）とは、ハッシュテーブルのサイズが変更された際に、キーの再配置を最小限に抑えることを目的とした特殊なハッシュ法です。具体的には、キーの総数をK、スロット（ハッシュテーブルの格納場所）の数をnとしたとき、平均してK/n個のキーのマッピング変更のみで、ハッシュテーブルの機能を維持できます。

他のハッシュ法との違い

従来のハッシュ法では、キーとスロットのマッピングがモジュラ演算によって定義されるため、ハッシュテーブルのスロット数が変化すると、ほぼすべてのキーが再マッピングされてしまいます。しかし、コンシステントハッシュ法では、このような大規模な再配置を避けることが可能です。

ランデブーハッシュとの関係

コンシステントハッシュ法は、ランデブーハッシュ（HRWハッシュとも呼ばれる）と同じ目的を達成するハッシュ法ですが、異なるアルゴリズムを使用しており、それぞれ独立して開発されました。

アルゴリズムの詳細

コンシステントハッシュ法では、以下の手順でキーの配置と管理を行います。

1. スロットのハッシュ値のソート: スロットのハッシュ値をソートし、リストで管理します。スロットとキーにはハッシュ値が存在し、それぞれ比較可能であることが前提です。
2. 分散キャッシュでの利用: 分散キャッシュとして使用する場合は、ノードごとに数百のスロットを用意します。これにより、ノードの追加・削除時に負荷が分散されます。
3. キーの追加・削除・取得:
キーのハッシュ値と同じか、より大きな値を持つスロットの中で、最も近いスロットを探します。二分探索を利用すると高速に検索できます。
もし、より大きなハッシュ値を持つスロットが存在しない場合は、最小のハッシュ値を持つスロットを使用します。
キーの追加、削除、取得は、この特定されたスロットに対して行います。
4. スロットの追加・削除:
スロットを追加する際は、そのスロットが担当するべきキーを、より大きなハッシュ値を持つ最も近いスロットから移動させます。
スロットを削除する際は、そのスロットが担当していたキーを、より大きなハッシュ値を持つ最も近いスロットに移動させます。

歴史

コンシステントハッシュ法は、もともとMITで分散キャッシュのために考案されました。その後、さまざまな分野に応用され、1997年の学術論文で、Webサーバーの負荷分散手法として「consistent hashing」という言葉が導入されました。各スロットは、分散システム内のノードを表します。ノードの追加や削除の際、再配置が必要なキーの数を最小限に抑えることが可能です。

また、この概念は、1996年にSHARPが開発した、Webブラウザで複数のHTTPプロキシを最適に使用するための技術であるSuper Proxy Scriptにも登場しています。

コンシステントハッシュ法は、大規模Webアプリケーションにおけるシステム障害の影響を低減し、堅牢なキャッシュを実現するのに役立ちます。さらに、分散ハッシュテーブル（DHT）の設計にも応用されており、ノード間でキー空間を分割し、特定のキーを担当するノードを効率的に特定するためのオーバーレイネットワークを提供しています。

コンシステントハッシュ法の必要性

キャッシングシステムの運用において、負荷分散のためにオブジェクトをキャッシュマシンの数で分割する方法が一般的ですが、キャッシュマシンの数が増減すると、すべてのオブジェクトが再配置されるという問題があります。この問題に対処するために、コンシステントハッシュ法が導入されました。コンシステントハッシュ法では、キャッシュマシンの増減時に、オブジェクトの再配置を最小限に抑え、キャッシュの一貫性を維持します。

オブジェクトとキャッシュの両方に同じハッシュ関数を使用し、オブジェクトのハッシュ値が属する範囲にキャッシュをマッピングします。キャッシュが削除された場合、その範囲は隣接するキャッシュに引き継がれます。これにより、他のキャッシュの変更を避けることができ、システムの安定性を保つことができます。

計算量

コンシステントハッシュ法の計算量はO(log(N))です。これは、リング上の次のノードを発見するために、ノード間の角度を二分探索する必要があるためです。

単調キー

もしキーの値が単調増加することがわかっている場合は、代わりに単調キーを使用したハッシュテーブルを利用することもできます。

使用例

コンシステントハッシュ法は、以下のようなさまざまなシステムで利用されています。

Couchbaseの自動データパーティショニング
OpenstackのオブジェクトストレージサービスSwift
AmazonのストレージシステムDynamoのパーティショニングコンポーネント
Apache Cassandraのデータパーティショニング
Voldemortのデータパーティショニング
Akkaのコンシステントハッシュルーター
Riak - 分散キーバリューデータベース
GlusterFS - ネットワークアタッチトストレージファイルシステム
Skylable - オープンソースの分散オブジェクトストレージシステム
Akamaiのコンテンツデリバリーネットワーク
Discordチャットアプリケーション
* Maglev: 高速で信頼性の高いソフトウェアネットワークロードバランサー

まとめ

コンシステントハッシュ法は、分散システムにおいて、効率的かつ安定的なデータ管理を実現するための重要な技術です。特に、ノードの追加や削除が頻繁に発生する環境では、システムの可用性を高く維持するのに役立ちます。

もう一度検索