DHT
Distributed Hash Table (分散ハッシュテーブル)
構造化オーバーレイのために設計されたP2Pの抽象化システム。DHTベースのP2Pネットワークでは、あるキーが与えられると、そのキーに対して責任を持つノードのアドレスを返す。「責任を持つ」と言うのは、サービスを提供できるか、サービスのアドレスを提供できることである。 複数のピアでハッシュ表を作るからDistributed Hash Tableと呼ばれている
メリット
ハッシュテーブルをP2Pネットワーク上で再現することで、高速かつ正確な検索を可能にしている
サービス提供の流れ
1. あるサービス$ Sを提供しようとする提供者$ Pは、$ k = hash(S)を求める
2.$ Pは$ kに対して責任のあるノード$ Rを検索し、$ Rに対して、「$ Pが$ kをキーとして$ Sを提供してるよ」という情報を通知する。
ノードの加入や離脱があった場合、システムの一貫性を保つためにマッピングを即座に変更しなければならない。局所的に更新しつつシステム全体の生合成を保つマッピング方法としてConsistent Hashingが利用されている。 アルゴリズムの比較点
オブジェクトロケーション
ノードが担当するオブジェクトの決め方。完全にランダムにして負荷分散を重視するか、偏りを許容して範囲検索性を上げるか
ルーティング
あるノードから目的のコンテンツを持つノードへの経路選択。単純なパフォーマンスや、ノードがクラッシュした時の時の時の代替経路選択の方法も評価される。最短経路を目指す場合、あるノードから他のノードに参照しなければならないので内部状態の情報量増加が必至になる
内部状態
DHTとしての機能を維持するために各ノードが保持する必要のある内部状態(=ルーティングテーブル)の情報量。要は他のノードへの参照数
ノードの参加・離脱時の仕組み
ノードの参加や離脱が非同期に発生しても、最終的にネットワークが安全な状態に保たれ、通常通りの動作が保証されるかどうか。内部状態が肥大するほどノードの参加や離脱の他ノードへ与える影響は大きくなるためここの仕組みは難解になる。