分散ハッシュテーブル
分散ハッシュテーブル (英: Distributed Hash Table, DHT) とは、ハッシュテーブルを複数のピアで管理する技術のこと。2001年に発表されたCAN, Chord, Pastry, Tapestryが代表的なアルゴリズムとして挙げられる。
概要
[編集]アドホック性とスケーラビリティの両立を目指す探索 (lookup) 手法で、コンピュータネットワーク上に構築されることから、オーバレイネットワークの一つといえる。 アドレスとコンテンツのハッシュ値を空間に写像し、その空間を複数のピアで分割管理することで、特定ピアに負荷が集中することなく大規模なコンテンツ探索を実現する。
特徴
[編集]DHTはサーバの集合により構成され、主な機能はハッシュテーブルと同等である。あるキー(ビット列)をハッシュ関数、あるいは何らかの直線化関数により論理的な空間の1点に射影し、射影された点に値を関連づけることを特徴とする。DHTは高いスケーラビリティを持つことが特徴である。スケーラビリティは、DHTに参加するノード数Nに対して、どのノードから探索を開始しても、全てのノードにO(N)オーダよりも良いオーダ (Chord等の代表的なアルゴリズムではO(log(N))) の通信により到達可能なことが確率的に保証されていることによる。この性質は、スケーラビリティを実現するための自律分散的なアルゴリズムに従った多数のノードによる、ハッシュテーブルを管理する論理空間の分割統治によるものである。論理空間の一部の管理を分担したDHTノード間で構成するオーバーレイネットワークの構成と、その上でのルーティングを工夫することでスケーラビリティを実現している。
以上から、キーに対するハッシュ関数の適用方法、ハッシュ値を射影する論理空間の定義、ハッシュ値の論理空間への射影方法、分割統治のための論理空間の分割方法、ノードの空間への射影方法、ノードで構成するオーバーレイネットワークの構成方法(参加・脱退・経路の学習など)などの差異により、さまざまな特徴のDHTが存在する。
P2Pシステムとしての分類
[編集]DHTはしばしば、旧来のGnutellaのようなPure P2Pネットワークと対比される。しかし、本質的には全く異なるものである。旧来のGnutellaのようなPure P2Pは基本的にはメッセージフラッディングによる資源探索システムであり、例えばファイル共有システムのように、ネットワーク上に流布する多くのコピーのうちの一つのありかがわかれば目的を達成できる場合がほとんどである。
一方、DHTの研究はおおきくわけて二つのルーツに分かれている。一つはTapestryからはじまる、DOLR(Decentralized Object Location and Routing)と呼ばれる、分散オブジェクト管理のためのオブジェクト間のメッセージルーティングの方式である。同じ方式によりハッシュテーブルを構成することができるので、Tapestryは広義にDHTに分類される。もう一つの研究は分散ファイルシステムの研究であり、Chordは元々はChord/DHash Projectとして分散ファイルシステムを多ノード間でスケーラブルに取り扱うための研究から生まれている。また、DHTの研究の源流として、コンシステントハッシュ法を挙げる場合もある。いずれにせよ、DHTの原理は、putするノードとgetするノードが、キーにより論理空間上の同じ場所を探索するための分散アルゴリズムであり、あるキーに対応するファイルは高々1種類(実装によってさまざまな拡張が存在するが)である。
一般に、オーバーレイネットワークとしての分類により、前者を「非構造オーバーレイネットワーク(非構造化オーバーレイネットワークとも)」、後者を「構造化オーバーレイネットワーク」と呼ぶ。
分散ハッシュテーブルのアルゴリズム
[編集]分散ハッシュテーブルのアルゴリズムを特徴付ける大きな要素として、キーを写像する論理空間と、各ノードが保持する経路表の管理方法による分類を行う。
論理空間による分類
[編集]経路表の管理による分類
[編集]DHTネットワークにノードが参加、あるいは脱退することによって各ノードが担当する部分空間が変更されるため、それに伴い経路表を再構成する必要がある。その経路表の管理方法によって次のように分類される。
- Chord、Pastry、Tapestry
- ピアが能動的に保守
- Kademlia
- 普段の通信を通して保守
関連項目
[編集]- ファイル共有ソフト
- Azureus
- アルゴリズムはKademlia、プロトコル部は独自
- BitComet
- アルゴリズムはKademlia、プロトコル部はBitTorrent互換
- BitTorrent
- アルゴリズムはKademlia、プロトコル部はKhashmirで実装
- eMule
- アルゴリズムはKademlia、プロトコル部はKadネットワークと呼ばれる
- LimeWire
- アルゴリズムはKademlia、プロトコル部はMojitoDHT
- Morpheus
- Perfect Dark
参考文献
[編集] |
- Sylvia Ratnasamy; Paul Francis, Mark Handley, Richard Karp, Scott Schenker (2001). “A scalable content-addressable network”. Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications (New York, NY, USA: ACM Press): 161 - 172. doi:10.1145/383059.383072.
- Ion Stoica; Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan (2001). “Chord: A scalable peer-to-peer lookup service for internet applications”. ACM SIGCOMM Computer Communication Review (New York, NY, USA: ACM Press) 31 (4): 149 - 160. doi:10.1145/964723.383071.
- Antony Rowstron; Peter Druschel (2001). Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. Lecture Notes in Computer Science. 2218/2001. Springer Berlin. pp. 329
- Ben Y. Zhao; John D. Kubiatowicz, Anthony D. Joseph (2001). “Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing”. Technical Report: CSD-01-1141 (Berkeley, CA, USA: University of California at Berkeley).
外部リンク
[編集]- Kazuyuki Shudo / 首藤 一幸
- 分散ハッシュテーブルおよびそのシミュレーション機能を提供するソフトウェア。
