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

一般に、オーバーレイネットワークとしての分類により、前者を「非構造オーバーレイネットワーク(非構造化オーバーレイネットワークとも)」、後者を「構造化オーバーレイネットワーク」と呼ぶ。
分散ハッシュテーブルのアルゴリズム

分散ハッシュテーブルのアルゴリズムを特徴付ける大きな要素として、キーを写像する論理空間と、各ノードが保持する経路表の管理方法による分類を行う。
論理空間による分類
Chord
閉じた数直線
CAN
N次元トーラス
Kademlia、P-Grid
２分木
Pastry、Tapestry
アルゴリズム
Koorde
De Brujin グラフ
経路表の管理による分類

DHTネットワークにノードが参加、あるいは脱退することによって各ノードが担当する部分空間が変更されるため、それに伴い経路表を再構成する必要がある。その経路表の管理方法によって次のように分類される。
Chord、Pastry、Tapestry
ピアが能動的に保守
Kademlia
普段の通信を通して保守
関連項目

ファイル共有ソフト

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

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

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

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

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

Morpheus

Perfect Dark

参考文献.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}

この節には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。（2020年1月）


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.