DHTについて

ノート

P2Pのお勉強 適当編 - WebLab.otaの続き？ただのメモ

オーバレイネットワークの構築・保守する方式

非構造化オーバレイ

Gnutellaやwinnyの検索用ネットワークに代表され，どのノードを隣接ノードとするかについて方式上の制約なし．

構造化オーバレイ

隣接ノードが方式によって決まる．構造化オーバレイの応用としては，検索を行う方式，つまり分散ハッシュ表（DHT）や，マルチキャストを行う方式．
存在するオブジェクトは，（たいてい）発見できる．一般に効率はよいが，柔軟な検索が苦手．

DHT

すべてのコンテンツ及びノードにそれぞれユニークなGUID（コンテンツ名のハッシュ値やコンテンツ内容のハッシュ値などが用いられる），NodeID（IPアドレスのハッシュ値やランダムに選択された値などが用いられる）が付与される．
CAN，Chord，Kademlia，Pastry，Tapestry，Viceroy

技術的課題
  • P2Pクエリールーティング
  • オーバレイネットワーク
  • コンテンツ管理
    • キャッシング（アクセスの高速化）
    • ミラーリング（可用性，負荷分散）
    • 同期（一貫性）
  • セキュリティ
    • AAA（課金，グループ管理）
    • DoSへの対応（ロバスト性）
  • コンテンツネーミング
  • 実運用に向けた応用（アクセスパターンを考慮した最適化）

（分散コンテンツ発見の課題）
データの一貫性とスケーラビリティという相反する要求の両立（トレードオフをどうするか？）．
分散ストレージサービスにはLANベースのローカルストレージと同等の性能が要求される．従って，できる限り少ないクエリーホップ数で，つまりできる限り小さい遅延で目的のコンテンツを発見することが要求される．特に，関連する多数のコンテンツを同時に発見しなければならない場合は，この要求はされに厳しくなる．

利用例
  • ファイル共有 [CFS, Ivy]
  • Webキャッシュ [Coral]
  • 名前サービス [ChordDNS]
  • 通信プリミティブ [I3]
  • Webアーカイブ [Herodotus]

大規模データベース・分散データベース

OceanStore

（File System）
DHTとAttenuated Bloom Filtersの組み合わせによりコンテンツを発見する．（まず，Attenuated Bloom Filtersを用いて目的のコンテンツが近隣に存在するかどうかを確認し，発見できなければ次にDHTを用いて広域でコンテンツを発見する）
データの永久性を追求．

  • Attenuated Bloom Filters
    • DHTは広域コンテンツの発見には有効であるが，クエリー送信ノードから目的コンテンツまでのホップ数が小さい場合には有効ではない．局所的なP2P分散コンテンツ発見手法．
PAST

（File System）
Pastry 上に永続オブジェクトのための抽象層を提供．ファイル共有．
Contentそのものをhash tableがもつ

PIER（Peer-to-Peer Information Exchange and Retrieval）

CANを利用している．
DHTを利用してネットワーク上のノードが持つデータベースを検索するシステム．
各ノード上にあるデータはすべて共通のグローバルスキーマで定義されていることを前提とする．
インターネット規模で動作する大規模分散クエリー・エンジン．特に現在のDHTの弱点とされる高度なクエリーを可能にしている．

AmbientDB

Chordを利用している．

Pastiche

Pastryを利用している．

Ivy

（File System）
DHashを利用している．読み出し・書き込み可能なファイルシステム．

CFS(Content-Addresable Network)

（File System）
Chordを利用している
Chord location protocolを使った分散ファイルシステム(ファイルをブロック化して，DHTで探索)
負荷分散、対障害性、スケーラビリティの高い分散システムを実現

Squirrel

Pastry をベースとした P2P ウェブキャッシュ．

PeerDB

フラッディング方式（検索キューの多さ，検索結果の不確実性）
各ノードのスキーマが異なる場合に対してスキーママッチングを行うことで柔軟に対応している．
小規模データベースをP2Pによる分散する．しかし，セマンティックス的調停のためにセントラル・ディレクトリ・サーバを使用する．

Piazza（ PDMS : Peer Data Management System ）

早くから，データベースシステムへのP2P技術の導入を試みた．

実装

Overlay Weaver

アプリケーション開発者に対しては、分散ハッシュ表 (DHT) やマルチキャストといった高レベルサービスに対する共通 API を提供します。（中略）
Overlay Weaver は、ルーティングアルゴリズムとして Chord、Kademlia、Koorde、Pastry、Tapestry の実装を提供しています。
http://overlayweaver.sourceforge.net/index-j.html

Bamboo DHT
ReDiR
JXTA（Sunがオープンソースで推進するPeer-to-Peer基盤）

A loosely-consistent DHT（Consistent Viewの維持のコストを検索時に転化する）
with a limited-range (RendezVous) walker（DHTで発見できなかった場合に用いる）


関連性を有するコンテンツのための分散ストレージサービス
P2Pを活用した小規模データベースの集約化
Chord/DHashを活用したデータベースの分散化
大規模データベースシステムに関する研究動向
ユビキタスコンテンツ環境における分散コンテンツ発見
Amazon's Dynamo
structured P2P/DHT(Distributed Hash Table)メモ & リンク集
パーソナル・アーカイブのための律分散型データ共有システムの設計
P2Pを用いたWeb動向集計フレームワーク
Towards a Common API for Structured Peer-to-Peer Overlays