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

コンピュータ科学の分野で、コンシステントハッシュ法（Consistent hashing）とは、ハッシュテーブルのサイズが変更された時、$K$をキーの数、$n$をスロット数とすると、平均$K/n$個のキーのマッピングの変更のみでハッシュテーブルの機能を提供することのできる、特殊なハッシュ法である。それに対して、その他の多くのハッシュ法では、キーとスロット間のマッピングがモジュラ演算によって定義されているため、ハッシュテーブルのスロット数が変化するとほぼすべてのキーが再マッピングされてしまう。分散システムの一形態である分散キャッシュなどで利用されている。

コンシステントハッシュは、テンプレート:仮リンク（HRWハッシュとも呼ばれる）と同じ目的を達成するハッシュ法であるが、2つの手法は異なるアルゴリズムを使用しており、同時に独立して開発された。

アルゴリズム

スロットのハッシュ値をソートしてリストに管理する。前提条件として、スロットおよびキーにはハッシュ値が存在し、かつ、それぞれ相互に比較可能であることが必要であり、ハッシュ値に数値や文字列を利用していれば問題はない。

分散キャッシュとして使用する場合は、ノードごとに数百のスロットを用意する。そうすることにより、ノードを追加・削除した時に、スロットがハッシュテーブル全体に分散されているので、処理の負荷が全体に分散される。また、コンシステントハッシュにキーを追加・削除・取得するマシンがノードおよびスロットのリストを取得する仕組みも必要。

キーの追加・削除・取得

キーのハッシュ値と同じもしくはより大きな値の中では最も近いスロットを探す。二分探索を使うと高速に見つかる。自分よりも大きなハッシュ値を持つスロットが存在しない場合は、最小のハッシュ値を持つスロットを使用する。

そのスロットにキーの追加・削除・取得を行う。分散キャッシュで複数のスロットに格納したい場合は、その先複数個のスロットにキーの追加・削除を行い、取得する際はその中からランダムで選ぶ。

スロットの追加・削除

スロットを追加する時は、自分よりも大きいハッシュ値の中では最も近いスロットから、自分が担当するべきキーを移動する。

スロットを削除する時は、自分の担当していたキーを、自分よりも大きいハッシュ値の中では最も近いスロットに移動する。

歴史

もともと、MITでの分散キャッシュで使用するために、Kargerらによって考案された。アイデアは、現在では他の分野に拡張された。 1997年の学術論文で、リクエストを分散する手段としてWebサーバーの数を変化させる手法として、"consistent hashing" という言葉が導入された。各スロットは、分散システム内のノードで表される。ノードの追加（結合）と除去（除去/失敗）は、スロット数/ノードの変更するとき、K / n個の項目のみを再シャッフルする必要がある。

この同じ概念は、しかしながら、複数のキャッシングHTTPプロキシをWebブラウザで最適に使用するために SHARP が開発した Super Proxy Script の技法の中で1996年に登場した。

コンシステントハッシュ法はまた、障害のシステム全体の降下を招くことなく堅牢なキャッシュを可能にするために、大規模なWebアプリケーションの部分的なシステム障害の影響を低減するために使用されている。

コンシステントハッシュ法のコンセプトは、分散ハッシュテーブル（DHT）の設計にも適用される。DHTは、ノードの集合の間で、キー空間を分けるのにコンシステントハッシュを使用し、さらに任意のキーを担当するノードを効率的に特定できるようにノードを接続するオーバーレイネットワークを提供している。

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

キャッシングマシンのコレクションの実行中に、いくつかの制限が経験されている。負荷分散のnキャッシュマシンの一般的な方法は、キャッシュのマシンの番号 hash(o) mod n でオブジェクトoを置く。nが変化すると、すべてのオブジェクトが新しい位置にハッシュされるため、キャッシュのマシンが追加または削除されている場合はこれは動作しない。元のコンテンツサーバはキャッシュのマシンからのリクエストが殺到しているため、これは悲惨なことがおこる。したがって、コンシステントハッシュは、サーバの無力化を回避するために必要とされる。

可能な限り、コンシステントハッシュは同じキャッシュマシンにオブジェクトをマップする。すなわち、キャッシュマシンを追加するときは他のすべてのキャッシュマシンからのオブジェクトのシェアを取得し、キャッシュマシンを減らすときにはそのオブジェクトは残りのマシン間で共有される。

コンシステントハッシュアルゴリズムのベースとなる考え方は、ハッシュオブジェクトとキャッシュの両方に同じハッシュ関数を使用することである。これは、オブジェクトのハッシュの数を含む区間にキャッシュをマップするために行われる。キャッシュが削除された場合、その間隔は、隣接する間隔を持つキャッシュに引き継がれる。残りのすべてのキャッシュが変更されていない。

計算量

N個のノード（またはスロット）とK個のキーに対する漸近時間計算量

	一般的なハッシュテーブル	コンシステントハッシュ法
ノードの追加	O(K)	O(K/N + log(N))
ノードの削除	O(K)	O(K/N + log(N))
キーの追加	O(1)	O(log(N))
キーの削除	O(1)	O(log(N))

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

単調キー

もしあらかじめキーの値の増加が単調であることが分かっている場合、代わりにテンプレート:仮リンクを利用することもできる。

使用例

コンシステントハッシュ法が使われている具体例には以下のものがある。

• Couchbaseの自動的なデータのパーティショニング
• OpenstackのオブジェクトストレージサービスSwift
• AmazonのストレージシステムDynamoのパーティショニングコンポーネント
• Apache Cassandraのデータのパーティショニング
• テンプレート:仮リンクのデータのパーティショニング
• テンプレート:仮リンクのコンシステントハッシュルーター
• Riak - 分散キーバリューデータベース
• GlusterFS - ネットワークアタッチトストレージファイルシステムの
• テンプレート:仮リンク - オープンソースの分散オブジェクトストレージシステム
• Akamaiのコンテンツデリバリーネットワーク
• Discordチャットアプリケーション
• Maglev: A Fast and Reliable Software Network Load Balancer

外部リンク

• C++ でのコンシステントハッシュ法の実装
• Erlang でのコンシステントハッシュ法の実装
• C# でのコンシステントハッシュ法の実装
• Java でのコンシステントハッシュ法の実装
• Consistent Hashing - memcachedを知り尽くす：第4回　memcachedの分散アルゴリズム gihyo.jp … 技術評論社