コンシステントハッシュ法
コンピュータ科学の分野で、コンシステントハッシュ法（Consistent hashing）とは、ハッシュテーブルのサイズが変更された時、をキーの数、をスロット数とすると、平均個のキーのマッピングの変更のみでハッシュテーブルの機能を提供することのできる、特殊なハッシュ法である。それに対して、その他の多くのハッシュ法では、キーとスロット間のマッピングがモジュラ演算によって定義されているため、ハッシュテーブルのスロット数が変化するとほぼすべてのキーが再マッピングされてしまう。分散システムの一形態である分散キャッシュなどで利用されている。
コンシステントハッシュは、ランデブーハッシュ（HRWハッシュとも呼ばれる）と同じ目的を達成するハッシュ法であるが、2つの手法は異なるアルゴリズムを使用しており、同時に独立して開発された。
アルゴリズム
[編集]スロットのハッシュ値をソートしてリストに管理する。前提条件として、スロットおよびキーにはハッシュ値が存在し、かつ、それぞれ相互に比較可能であることが必要であり、ハッシュ値に数値や文字列を利用していれば問題はない。
分散キャッシュとして使用する場合は、ノードごとに数百のスロットを用意する。そうすることにより、ノードを追加・削除した時に、スロットがハッシュテーブル全体に分散されているので、処理の負荷が全体に分散される。また、コンシステントハッシュにキーを追加・削除・取得するマシンがノードおよびスロットのリストを取得する仕組みも必要。
キーの追加・削除・取得
[編集]キーのハッシュ値と同じもしくはより大きな値の中では最も近いスロットを探す。二分探索を使うと高速に見つかる。自分よりも大きなハッシュ値を持つスロットが存在しない場合は、最小のハッシュ値を持つスロットを使用する。
そのスロットにキーの追加・削除・取得を行う。分散キャッシュで複数のスロットに格納したい場合は、その先複数個のスロットにキーの追加・削除を行い、取得する際はその中からランダムで選ぶ。
スロットの追加・削除
[編集]スロットを追加する時は、自分よりも大きいハッシュ値の中では最も近いスロットから、自分が担当するべきキーを移動する。
スロットを削除する時は、自分の担当していたキーを、自分よりも大きいハッシュ値の中では最も近いスロットに移動する。
歴史
[編集]もともと、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が変化すると、すべてのオブジェクトが新しい位置にハッシュされるため、キャッシュのマシンが追加または削除されている場合はこれは動作しない。元のコンテンツサーバはキャッシュのマシンからのリクエストが殺到しているため、これは悲惨なことがおこる。したがって、コンシステントハッシュは、サーバの無力化を回避するために必要とされる。
可能な限り、コンシステントハッシュは同じキャッシュマシンにオブジェクトをマップする。すなわち、キャッシュマシンを追加するときは他のすべてのキャッシュマシンからのオブジェクトのシェアを取得し、キャッシュマシンを減らすときにはそのオブジェクトは残りのマシン間で共有される。
コンシステントハッシュアルゴリズムのベースとなる考え方は、ハッシュオブジェクトとキャッシュの両方に同じハッシュ関数を使用することである。これは、オブジェクトのハッシュの数を含む区間にキャッシュをマップするために行われる。キャッシュが削除された場合、その間隔は、隣接する間隔を持つキャッシュに引き継がれる。残りのすべてのキャッシュが変更されていない。
計算量
[編集]| 一般的なハッシュテーブル | コンシステントハッシュ法 | |
|---|---|---|
| ノードの追加 | O(K) | O(K/N + log(N)) |
| ノードの削除 | O(K) | O(K/N + log(N)) |
| キーの追加 | O(1) | O(log(N)) |
| キーの削除 | O(1) | O(log(N)) |
コンシステントハッシュ法のという計算量は、リング上の次のノードを発見するために、ノード間の角度の二分探索が必要であることに由来する。
単調キー
[編集]もしあらかじめキーの値の増加が単調であることが分かっている場合、代わりに単調キーを使用したハッシュテーブルを利用することもできる。
使用例
[編集]コンシステントハッシュ法が使われている具体例には以下のものがある。
- Couchbaseの自動的なデータのパーティショニング
- OpenstackのオブジェクトストレージサービスSwift[4]
- AmazonのストレージシステムDynamoのパーティショニングコンポーネント[5]
- Apache Cassandraのデータのパーティショニング[6]
- Voldemortのデータのパーティショニング[7]
- Akkaのコンシステントハッシュルーター[8]
- Riak - 分散キーバリューデータベース[9]
- GlusterFS - ネットワークアタッチトストレージファイルシステムの[10]
- Skylable - オープンソースの分散オブジェクトストレージシステム[11]
- Akamaiのコンテンツデリバリーネットワーク[12]
- Discordチャットアプリケーション[13]
- Maglev: A Fast and Reliable Software Network Load Balancer[14]
脚注
[編集]- ^ 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日閲覧。.
- ^ http://docs.openstack.org/developer/swift/ring.html
- ^ DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P. et al. (2007). “Dynamo: Amazon's Highly Available Key-Value Store”. Proceedings of the 21st ACM Symposium on Operating Systems Principles 2018年6月7日閲覧。.
- ^ Lakshman, Avinash; Malik, Prashant (2010). “Cassandra: a decentralized structured storage system”. ACM SIGOPS Operating Systems Review.
- ^ “Design -- Voldemort”. www.project-voldemort.com/. 9 February 2015時点のオリジナルよりアーカイブ。9 February 2015閲覧。 “Consistent hashing is a technique that avoids these problems, and we use it to compute the location of each key on the cluster.”
- ^ Akka Routing
- ^ “Riak Concepts”. 2014年5月5日閲覧。
- ^ http://www.gluster.org/2012/03/glusterfs-algorithms-distribution/
- ^ “Skylable architecture”. 2014年6月21日閲覧。
- ^ “Modern Algorithmic Toolbox”. 2016年11月8日閲覧。
- ^ “How Discord Scaled Elixir to 5,000,000 Concurrent Users”. 2017年7月12日閲覧。
- ^ “Maglev: A Fast and Reliable Software Network Load Balancer”. 2017年7月30日閲覧。
