分散ハッシュテーブル

分散ハッシュテーブル (英: 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種類(実装によってさまざまな拡張が存在するが)である。

一般に、オーバーレイネットワークとしての分類により、前者を「非構造オーバーレイネットワーク(非構造化オーバーレイネットワークとも)」、後者を「構造化オーバーレイネットワーク」と呼ぶ。