コンシステントハッシュ法
(Consistent hashing から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2013/06/17 07:57 UTC 版)
コンシステントハッシュ法 (Consistent hashing) はスロットの追加や削除に対して、最小限のキーのスロットへのマッピングの変更で、ハッシュテーブルの機能を提供することのできる特殊なハッシュ法。その他多くのハッシュテーブルでは、スロット数の変化はほぼすべてのキーが再マッピングされるのに対して、コンシステントハッシュの場合、K をキーの数、n をスロット数とすると、平均 K / n 個のキーの再マップですむ。分散システムの一形態である分散キャッシュなどで利用されている。
目次 |
アルゴリズム
スロットのハッシュ値をソートしてリストに管理する。前提条件として、スロットおよびキーにはハッシュ値が存在し、かつ、それぞれ相互に比較可能であることが必要であり、ハッシュ値に数値や文字列を利用していれば問題はない。
分散キャッシュとして使用する場合は、ノードごとに数百のスロットを用意する。そうすることにより、ノードを追加・削除した時に、スロットがハッシュテーブル全体に分散されているので、処理の負荷が全体に分散される。また、コンシステントハッシュにキーを追加・削除・取得するマシンがノードおよびスロットのリストを取得する仕組みも必要。
キーの追加・削除・取得
キーのハッシュ値と同じもしくはより大きな値の中では最も近いスロットを探す。二分探索を使うと高速に見つかる。自分よりも大きなハッシュ値を持つスロットが存在しない場合は、最小のハッシュ値を持つスロットを使用する。
そのスロットにキーの追加・削除・取得を行う。分散キャッシュで複数のスロットに格納したい場合は、その先複数個のスロットにキーの追加・削除を行い、取得する際はその中からランダムで選ぶ。
スロットの追加・削除
スロットを追加する時は、自分よりも大きいハッシュ値の中では最も近いスロットから、自分が担当するべきキーを移動する。
スロットを削除する時は、自分の担当していたキーを、自分よりも大きいハッシュ値の中では最も近いスロットに移動する。
歴史
もともと、MITでの分散キャッシュで使用するために、Kargerらによって考案された。アイデアは、現在では他の分野に拡張された。 1997年の学術論文で、リクエストを分散する手段としてWebサーバーの数を変化させる手法として、"consistent hashing" という言葉が導入された。各スロットは、分散システム内のノードで表される。ノードの追加（結合）と除去（除去/失敗）は、スロット数/ノードの変更するとき、K / n個の項目のみを再シャッフルする必要がある[1]。
この同じ概念は、しかしながら、複数のキャッシングHTTPプロキシをWebブラウザで最適に使用するために SHARP が開発した Super Proxy Script の技法の中で1996年に登場した[2]。
コンシステントハッシュ法はまた、障害のシステム全体の降下を招くことなく堅牢なキャッシュを可能にするために、大規模なWebアプリケーションの部分的なシステム障害の影響を低減するために使用されている[3]。
コンシステントハッシュ法のコンセプトは、分散ハッシュテーブル（DHT）の設計にも適用される。DHTは、ノードの集合の間で、キー空間を分けるのにコンシステントハッシュを使用し、さらに任意のキーを担当するノードを効率的に特定できるようにノードを接続するオーバーレイネットワークを提供している。
コンシステントハッシュ法の必要性
キャッシングマシンのコレクションの実行中に、いくつかの制限が経験されている。負荷分散のnキャッシュマシンの一般的な方法は、キャッシュのマシンの番号 hash(o) mod n でオブジェクトoを置く。nが変化すると、すべてのオブジェクトが新しい位置にハッシュされるため、キャッシュのマシンが追加または削除されている場合はこれは動作しない。元のコンテンツサーバはキャッシュのマシンからのリクエストが殺到しているため、これは悲惨なことがおこる。したがって、コンシステントハッシュは、サーバの無力化を回避するために必要とされる。
可能な限り、コンシステントハッシュは同じキャッシュマシンにオブジェクトをマップする。すなわち、キャッシュマシンを追加するときは他のすべてのキャッシュマシンからのオブジェクトのシェアを取得し、キャッシュマシンを減らすときにはそのオブジェクトは残りのマシン間で共有される。
コンシステントハッシュアルゴリズムのベースとなる考え方は、ハッシュオブジェクトとキャッシュの両方に同じハッシュ関数を使用することである。これは、オブジェクトのハッシュの数を含む区間にキャッシュをマップするために行われる。キャッシュが削除された場合、その間隔は、隣接する間隔を持つキャッシュに引き継がれる。残りのすべてのキャッシュが変更されていない。
参照
- ^ Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA. pp. 654–663. doi:10.1145/258533.258660 2008年6月17日閲覧。
- ^ Doi, Katsuo. “Super Proxy Script - How to make distributed proxy servers by URL hashing”. 2011年8月4日閲覧。
- ^ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). “Web Caching with Consistent Hashing”. Computer Networks 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9 2008年6月17日閲覧。.
外部リンク
- C++ でのコンシステントハッシュ法の実装
- Erlang でのコンシステントハッシュ法の実装
- C# でのコンシステントハッシュ法の実装
- Java でのコンシステントハッシュ法の実装
- Consistent Hashing - memcachedを知り尽くす：第4回 memcachedの分散アルゴリズム gihyo.jp … 技術評論社
|
||||||||||||||||||||||||||||||||||||||||||||||
- コンシステントハッシュ法のページへのリンク
