Distributed Hash Table (分散ハッシュテーブル)

構造化オーバーレイのために設計されたP2Pの抽象化システム。DHTベースのP2Pネットワークでは、あるキーが与えられると、そのキーに対して責任を持つノードのアドレスを返す。「責任を持つ」と言うのは、サービスを提供できるか、サービスのアドレスを提供できることである。

ハッシュテーブルをP2Pネットワーク上で再現することで、高速かつ正確な検索を可能にしている

1. あるサービスSを提供しようとする提供者Pは、k = hash(S)を求める

2.Pはkに対して責任のあるノードRを検索し、Rに対して、「PがkをキーとしてSを提供してるよ」という情報を通知する。

ノードの加入や離脱があった場合、システムの一貫性を保つためにマッピングを即座に変更しなければならない。局所的に更新しつつシステム全体の生合成を保つマッピング方法としてConsistent Hashingが利用されている。

オブジェクトロケーション

ノードが担当するオブジェクトの決め方。完全にランダムにして負荷分散を重視するか、偏りを許容して範囲検索性を上げるか

ルーティング

あるノードから目的のコンテンツを持つノードへの経路選択。単純なパフォーマンスや、ノードがクラッシュした時の時の時の代替経路選択の方法も評価される。最短経路を目指す場合、あるノードから他のノードに参照しなければならないので内部状態の情報量増加が必至になる

内部状態

DHTとしての機能を維持するために各ノードが保持する必要のある内部状態(=ルーティングテーブル)の情報量。要は他のノードへの参照数

ノードの参加・離脱時の仕組み

ノードの参加や離脱が非同期に発生しても、最終的にネットワークが安全な状態に保たれ、通常通りの動作が保証されるかどうか。内部状態が肥大するほどノードの参加や離脱の他ノードへ与える影響は大きくなるためここの仕組みは難解になる。

ノードが能動的に経路表を保守：Chord, Pastry, Tapestry

普段の通信を通して経路表を保守保守：Kademlia