タペストリー (DHT)

Tapestryは、分散アプリケーションに分散ハッシュテーブル、ルーティング、マルチキャストインフラストラクチャを提供するピアツーピアオーバーレイ ネットワークです。 ^[1] Tapestryピアツーピアシステムは、近くのリソースへの効率的でスケーラブルな自己修復型の位置認識ルーティングを提供します。

Napster、Gnutellaなどの第 1 世代のピアツーピア アプリケーションには、Napster の中央ディレクトリや Gnutella のスコープ付きブロードキャスト クエリなど、スケーラビリティを制限する制約がありました。これらの問題に対処するために、 Tapestry、Chord、Pastry、およびCANなどの第 2 世代の P2P アプリケーションが開発されました。これらのオーバーレイは、基本的なキーベースのルーティング メカニズムを実装しています。これにより、オーバーレイ ネットワークでのメッセージの決定論的ルーティングとノード障害への適応が可能になります。名前の付いたネットワークのうち、 Pastry は Tapestry に非常に近く、どちらも Plaxton らによる同じルーティング アルゴリズムを採用しています。

Tapestry は、効率性とメッセージ遅延の最小化に重点を置いた分散オブジェクトの配置とルーティングを提供する拡張可能なインフラストラクチャです。これは、Tapestry が初期化からローカルに最適なルーティング テーブルを構築し、ルーティングの拡張を減らすためにそれらを維持するため実現されます。さらに、Tapestry では、特定のアプリケーションのニーズに応じてオブジェクトの配布を決定できます。同様に、Tapestry では、アプリケーションがオーバーレイ ネットワークでマルチキャストを実装できます。

各ノードには、大きな識別子空間に均一に分散された一意のノード ID が割り当てられます。Tapestry はSHA-1 を使用して、40 桁の 16 進キーで表される 160 ビットの識別子空間を生成します。アプリケーション固有のエンドポイントGUID にも同様に一意の識別子が割り当てられます。ノード ID と GUID はオーバーレイ ネットワークにほぼ均等に分散され、各ノードには複数の異なる ID が格納されます。実験から、Tapestry の効率はネットワーク サイズとともに向上することが示されており、複数のアプリケーションが同じオーバーレイ ネットワークを共有すると効率が向上します。アプリケーションを区別するために、一意のアプリケーション ID が使用されます。Tapestry は、オブジェクトの公開とルーティングにベスト エフォートを使用します。

• オブジェクトの公開
• オブジェクトの公開解除
• ルートオブジェクト
• RouteToNode (最も近い一致ではなく、完全に一致する)

各識別子は、ルートと呼ばれるライブ ノードにマップされます。ノードのノード ID がGの場合、それがルートです。それ以外の場合は、ルーティング テーブルのノード ID とIP アドレスを使用して、ノードのネイバーを検索します。各ホップで、メッセージは増分サフィックス ルーティングによって徐々にGに近づいてルーティングされます。各ネイバー マップには複数のレベルがあり、各レベルには、ID の特定の桁位置まで一致するノードへのリンクが含まれています。j^{番目のレベルのプライマリ i番目}のエントリは、プレフィックス ( N、j -1)+ iで始まる最も近いノードの ID と場所です。つまり、レベル 1 には共通点のないノードへのリンクがあり、レベル 2 には最初の桁が共通している、などです。このため、サイズNでベースB (16 進数: B=16)の ID のネットワークでは、ルーティングには約ホップが必要です。正確な ID が見つからない場合、ルーティング テーブルは最も近い一致するノードにルーティングします。フォールト トレランスのために、ノードはルーティング テーブルのサイズが になるようにセカンダリ リンクを保持します。 ${\displaystyle \log_{B}N}$${\displaystyle c}$${\displaystyle c*B*\log _{B}N}$

ネットワークの参加者は、定期的に公開メッセージをルート ノードにルーティングすることでオブジェクトを公開できます。パス上の各ノードには、オブジェクトをマッピングするポインタが格納されます。複数のサーバーが同じオブジェクトへのポインタを公開できます。冗長リンクは、レイテンシや局所性によって優先順位が付けられます。

オブジェクトは、オブジェクトのルートに向けてメッセージをルーティングすることによって特定されます。パスに沿った各ノードはマッピングをチェックし、要求を適切にリダイレクトします。ルーティングの効果は、同じ宛先に向かう近くのパスの収束です。

新しいノードは、そのノード ID のルートになります。ルートは、共有する ID の最長プレフィックスの長さを調べます。次に、同じプレフィックスを共有するすべての既存のノードに届くマルチキャスト メッセージを送信します。次に、これらのノードは新しいノードをルーティング テーブルに追加します。新しいノードは、ルートのオブジェクトの一部に対してルートの役割を引き継ぐ場合があります。ノードは新しいノードに連絡して、一時的な近隣リストを提供します。次に、新しいノードは、反復的な最近隣検索を実行して、ルーティング テーブルのすべてのレベルを埋めます。

ネットワークから離脱するには、ノードは離脱の意思をブロードキャストし、他のノードのルーティング テーブルの各レベルの代替ノードを送信します。離脱ノードのオブジェクトは、冗長コピーから再配布または補充されます。

予期しないノード障害は、ネットワークの冗長性とバックアップ ポインターによって処理され、損傷したリンクを再確立します。

Tapestry は、さまざまなネットワーク条件下で安定したオーバーレイ ルーティング ネットワークを提供します。これにより、分散アプリケーションおよびサービスに最適なインフラストラクチャが実現します。Tapestry に基づくアプリケーションは次のとおりです。

• OceanStore − PlanetLab の分散ストレージ ユーティリティ
• Mnemosyne − ステガノグラフィファイルシステム
• Bayeux − 自己組織化マルチキャストアプリケーション
• Spamwatch − 分散型スパムフィルター

Tapestry は、Ben Y. Zhao、Ling Huang、Jeremy Stribling、Sean C. Rhea、Anthony D. Joseph、および John D. Kubiatowicz によって開発されました。

• コンテンツアドレスネットワーク(CAN)
• Chord（ピアツーピア）
• カデムリア
• ペストリー（DHT）

• Chimera プロジェクト、Tapestry の実装 (2007 年頃)