分散ハッシュテーブル

分散ハッシュテーブルの最新ニュースをまとめて検索！

分散ハッシュテーブル (Distributed Hash Table, DHT) とは、ハッシュテーブルを複数のピアで管理する技術のこと。2001年に発表されたCAN, Chord, Pastry, Tapestryが代表的なアルゴリズムとして挙げられる。

[編集] 概要

アドホック性とスケーラビリティの両立を目指す探索 (lookup) 手法で、コンピュータネットワーク上に構築されることから、オーバレイネットワークの一つといえる。アドレスとコンテンツのハッシュ値を空間に写像し、その空間を複数のピアで分割管理することで、特定ピアに負荷が集中することなく大規模なコンテンツ探索を実現する。

[編集] 特徴

Peer to Peer(P2P)ネットワークはその構造によってNapsterなどが採用するハイブリッドP2Pと、Gnutellaに代表されるピュアP2Pに分類される。

ハイブリッドP2Pは、コンテンツとそれが配置されるピアのアドレスを中央サーバがインデックスすることでコンテンツ探索機能を提供する。参加する全てのピアを中央サーバが管理でき、P2Pネットワークに存在するコンテンツを確実に見つけることが出来る。その反面、ピアやコンテンツの増加に対し中央サーバがボトルネックとなるため、サーバ管理コストの増大やスケーラビリティに弱点を抱える。

一方、ピュアP2Pでは中央サーバが存在せず、互いのピアがアドホックに接続する形を取る。旧来のピュアP2Pではコンテンツ検索にFloodingなどが一般的に用いられるが、ユーザが増えることでネットワークトラフィックが増大する、またネットワーク上のコンテンツを漏れなく完全に探索することが難しいという問題がある。

DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数十万ピアぐらいが限界だとされているが、DHTを使うと数十億ものピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。

DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。

[編集] 分散ハッシュテーブルのアルゴリズム

分散ハッシュテーブルのアルゴリズムを特徴付ける大きな要素は、コンテンツとそのアドレスを写像する空間と、各ピアが保持する経路表の管理である。

[編集] コンテンツとそのアドレスの写像による分類

Chord

円状スキップリスト

CAN

N次元トーラス

Kademlia、P-Grid

２分木

Tapestry、Pastry

Plaxtonアルゴリズム

[編集] 経路表の管理による分類

DHTネットワークにピアが参加、あるいは脱退することによって各ピアが担当する部分空間が変更されるため、それに伴い経路表を再構成する必要がある。その経路表の管理方法によって次のように分類される。

Chord、Pastry、Tapestry

ピアが能動的に保守

Kademlia

普段の通信を通して保守

[編集] 関連項目

アルゴリズムはKademlia、プロトコル部は独自

BitComet

アルゴリズムはKademlia、プロトコル部はBitTorrent互換

BitTorrent

アルゴリズムはKademlia、プロトコル部はKhashmirで実装

eMule

アルゴリズムはKademlia、プロトコル部はKadネットワークと呼ばれる

LimeWire

アルゴリズムはKademlia、プロトコル部はMojitoDHT

[編集] 参考文献

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: 161 - 172. New York, NY, USA: ACM Press. 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 31 (4): 149 - 160. New York, NY, USA: ACM Press. 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, 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.

[編集] 外部リンク

分散ハッシュテーブルおよびそのシミュレーション機能を提供するソフトウェア。

この「分散ハッシュテーブル」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる協力者を求めています（Portal:コンピュータ）。

フリー百科事典『ウィキペディア（Wikipedia）』 Text is available under GNU Free Documentation License.

最終更新 2009年10月5日 (月) 02:03 （日時は個人設定で未設定ならばUTC）。
【分散ハッシュテーブル】変更履歴