コンシステントハッシュ法
もともと、MITでの分散キャッシュで使用するために、Kargerらによって考案された。アイデアは、現在では他の分野に拡張された。 1997年の学術論文で、リクエストを分散する手段としてWebサーバーの数を変化させる手法として、"consistent hashing" という言葉が導入された。各スロットは、分散システム内のノードで表される。ノードの追加(結合)と除去(除去/失敗)は、スロット数/ノードの変更するとき、K / n個の項目のみを再シャッフルする必要がある。
この同じ概念は、しかしながら、複数のキャッシングHTTPプロキシをWebブラウザで最適に使用するために SHARP が開発した Super Proxy Script の技法の中で1996年に登場した。
コンシステントハッシュ法はまた、障害のシステム全体の降下を招くことなく堅牢なキャッシュを可能にするために、大規模なWebアプリケーションの部分的なシステム障害の影響を低減するために使用されている。
コンシステントハッシュ法のコンセプトは、分散ハッシュテーブル(DHT)の設計にも適用される。DHTは、ノードの集合の間で、キー空間を分けるのにコンシステントハッシュを使用し、さらに任意のキーを担当するノードを効率的に特定できるようにノードを接続するオーバーレイネットワークを提供している。
スロットのハッシュ値をソートしてリストに管理する。前提条件として、スロットおよびキーにはハッシュ値が存在し、かつ、それぞれ相互に比較可能であることが必要であり、ハッシュ値に数値や文字列を利用していれば問題はない。
分散キャッシュとして使用する場合は、ノードごとに数百のスロットを用意する。そうすることにより、ノードを追加・削除した時に、スロットがハッシュテーブル全体に分散されているので、処理の負荷が全体に分散される。また、コンシステントハッシュにキーを追加・削除・取得するマシンがノードおよびスロットのリストを取得する仕組みも必要。