ペストリー（DHT）

Pastry は、 Chordに似た分散ハッシュテーブル(DHT)を実装するためのオーバーレイネットワークおよびルーティングネットワークです。キーと値のペアは、接続されたインターネットホストの冗長ピアツーピアネットワークに格納されます。このプロトコルは、ネットワークにすでに存在するピアのIP アドレスを提供することでブートストラップされ、それ以降は動的に構築および修復されるルーティングテーブルを介して実行されます。冗長性と分散性を備えているため、単一障害点がなく、どのノードも警告なしにいつでもネットワークから離脱でき、データ損失の可能性はほとんどまたはまったくないと言われています。このプロトコルは、 pingやtracerouteなどの外部プログラムによって提供されるルーティングメトリックを使用して、ルーティングテーブルに格納する最適なルートを決定することもできます。

Pastry の分散ハッシュ テーブル機能は他のDHTとほぼ同じですが、 DHTコンセプトの上に構築されたルーティング オーバーレイ ネットワークが他の DHT と異なります。これにより、Pastry は他のネットワークのスケーラビリティとフォールト トレランスを実現しながら、パケットをフラッディングする必要がなくなるため、ノード間でパケットをルーティングする際の全体的なコストを削減できます。ルーティング メトリックはターゲット ノードの IP アドレスに基づいて外部プログラムによって提供されるため、メトリックは最短ホップ数、最小レイテンシ、最大帯域幅、またはメトリックの一般的な組み合わせに簡単に切り替えることができます。

ハッシュ テーブルのキー空間は、 Chordシステムのキー空間と同様に円形とみなされ、ノード ID は、円形キー空間内の位置を表す 128 ビットの符号なし整数です。ノード ID はランダムかつ均一に選択されるため、ノード ID が隣接するピアは地理的に分散しています。ルーティング オーバーレイ ネットワークは、各ピアがリーフ ノードのリスト、近隣リスト、およびルーティング テーブルで構成される状態情報を検出して交換することで、ハッシュ テーブルの上に形成されます。リーフ ノード リストは、円周の各方向でノード ID によって最も近い L /2 個のピアで構成されます。

リーフ ノードに加えて、近隣リストもあります。これは、ルーティング メトリックの観点から最も近いM個のピアを表します。ルーティング アルゴリズムでは直接使用されませんが、近隣リストはルーティング テーブル内の局所性原則を維持するために使用されます。

最後に、ルーティング テーブル自体があります。これには、割り当てられたアドレス ブロックごとに 1 つのエントリが含まれます。アドレス ブロックを形成するために、128 ビットのキーが各桁がbビットの長さの数字に分割され、2 ^{b を}基数とする番号体系が生成されます。これにより、クライアントの観点からアドレスが明確なレベルに分割され、レベル 0 は 2 つのアドレス間の 0 桁の共通プレフィックスを表し、レベル 1 は 1 桁の共通プレフィックスを表す、というようになります。ルーティング テーブルには、各アドレス レベルの可能な桁ごとに最も近い既知のピアのアドレスが含まれますが、その特定のレベルでピア自体に属する桁は除きます。これにより、レベルごとに連絡先が格納され、レベルの数は としてスケーリングされます。と の値は、一般的なネットワーク上の動作値を表します。 ${\displaystyle 2^{b}-1}$${\displaystyle (\log _{2}{N})/b}$${\displaystyle b\approx 4,L\approx 2^{b}}$${\displaystyle M\approx 2^{b}}$

パケットは、そのノード ID を持つピアがあるかどうかに関係なく、キースペース内の任意のアドレスにルーティングできます。パケットは、円形リング上の適切な場所に向かってルーティングされ、目的の宛先に最も近いノード ID を持つピアがパケットを受信します。ピアがルーティングするパケットを受信するかパケットを送信しようとすると、最初にリーフ セットを調べ、正しいノードが見つかった場合はそのノードに直接ルーティングします。これが失敗した場合、ピアは次にルーティング テーブルを参照し、宛先アドレスとピア自身よりも長いプレフィックスを共有するノードのアドレスを見つけます。ピアに長いプレフィックスを持つ連絡先がない場合、または連絡先が切断されている場合は、同じ長さのプレフィックスを持ち、ノード ID が数値的に宛先に近いピアを連絡先リストから選択し、そのピアにパケットを送信します。アドレス内の正しい桁数は常に増加するか同じままであるため (同じままの場合、パケットと宛先の間の距離は短くなります)、ルーティング プロトコルは収束します。

Pastry 自体は、キーがノード間でどのように配布されるか、およびキーを保持するノードを見つける方法を指定します。これを上位プロトコルの基盤として使用することで、Pastry は分散ファイル システム、サブスクリプションおよび公開システム、または値を保存して後で取得するだけの機能を持つその他のシステムなどの機能を実装できます。

PAST は、Pastry の上に階層化された分散ファイル システムです。ファイルは、ファイル名のハッシュを計算することによってシステムに保存されます。次に、Pastry は、ファイル名から取得されたハッシュに最も近い循環キースペース内のノードにファイルの内容をルーティングします。次に、このノードは、実際のキーに最も近いk 個のノードにファイルのコピーを送信します。これらのノードのほとんどは、このノードのリーフ ノードである可能性が高いため、直接アクセスできます。データの取得は、ファイル名を再ハッシュし、Pastry を介してキースペース内の適切な場所にデータ要求をルーティングすることによって行われます。要求は、データのコピーを持つk 個のノードのいずれかによって満たされます。これにより、データの冗長性と負荷分散の両方が実現されます。キースペース内の隣接するノードは地理的に分散しているため、 k個のノードすべてが同時にオフラインになる可能性は非常に低くなります。さらに重要なのは、Pastry ルーティング プロトコルは移動距離を最小限に抑えようとするため、リクエストを行ったマシンに最も近いノード (メトリックに従って) がデータで応答する可能性が高いということです。

SCRIBE は、基盤となるルート管理とホスト検索に Pastry を使用する分散型のパブリッシュ/サブスクライブ システムです。ユーザーは、他のユーザーがサブスクライブできるトピックを作成します。トピックが作成されると、トピックの所有者はトピックの下に新しいエントリをパブリッシュできます。このエントリは、トピックをサブスクライブしているすべての SCRIBE ノードにマルチキャストツリーで配布されます。システムは、トピック名とトピックを所有するユーザーの名前を連結したハッシュを計算することで機能します。このハッシュは Pastry キーとして使用され、パブリッシャーは、Pastry のルーティング プロトコルを使用してキーに最も近いノードにパケットをルーティングし、そのノード上にトピックのルート ノードを作成します。次に、トピックとパブリッシャーの名前からキーを計算し、Pastry を使用してトピックへのサブスクライブ メッセージをルート ノードにルーティングすることで、トピックをサブスクライブします。ルート ノードは、別のノードからサブスクライブ メッセージを受信すると、ノード ID を子のリストに追加し、トピックのフォワーダーとして動作し始めます。

分散化は、ネットワーク内のすべてのノードが、トピックのルート ノードに向かう途中で通過するサブスクライブ メッセージをスヌープすることで実現されます。トピックが現在のノードがサブスクライブしているトピックである場合、ルート ノードへのパケットの転送を停止し、サブスクライブしようとしているノードを子ノードの 1 つとして追加します。このようにして、ツリーのような構造が形成され、ルート ノードが最上部から最初のいくつかのサブスクライバー ノードに送信し、次にこれらの各ノードがメッセージを子ノードに転送する、というように続きます。Pastry ネットワーク上のランダム ノードから同じノードに宛てられたパケットは、途中ですぐに同じパスに沿って移動することが多いため、Pastry ネットワーク内で最も近いツリーの部分にアタッチされます。Pastry ルートに沿った各ホップは、使用されているルーティング メトリックに従ってローカルで最適なルートを表すため、サブスクライブ メッセージはツリーの最も近い部分を探し出し、そこにアタッチされます。

最後に、タイムアウトとキープアライブの使用により、分散ツリーのメンバー間のフォールト トレランスが実現されます。実際のデータ送信はキープアライブとしても機能し、トラフィックを最小限に抑えます。子ノードが親からしばらく受信しない場合は、新しいサブスクライブ メッセージをツリーのルート ノードにルーティングし、そのトピックのツリーにぶつかった場所に再接続します。親がタイムアウト期間内に子から受信しない場合は、子のリストから子を削除します (このアクションによって子リストが空になった場合、親は転送者としての動作を完全に停止します)。残っている唯一の障害点はルート ノードの障害点であり、Pastry 自体はこれを自動的に克服します。Pastry はキーの実際の値に最も近いいくつかのノード間でキーを複製するため、ルート ノードにはすでにミラーが設定されており、休止状態になっています。ルート ノードがオフラインになると (これもタイムアウトによって検出されます)、次に近い Pastry ノードがルート ノードとして動作を開始します。トピックの作成者が新しいマテリアルを公開しようとすると、古いルート ノードにはアクセスできなくなります。その後、パブリッシャーは Pastry ネットワークにフォールバックし、それを使用して公開メッセージを新しいルート ノードにルーティングします。これが完了すると、パブリッシャーは新しいルート ノードの IP アドレスのコピーをキャッシュし、将来の送信で Pastry ネットワークの使用を減らします。

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

• A. Rowstron & P.​​ Druschel (2001 年 11 月)。「Pastry: 大規模ピアツーピア システム向けのスケーラブルで分散化されたオブジェクトの場所とルーティング」(PDF)。IFIP /ACM 国際分散システム プラットフォーム会議 (ミドルウェア)、ハイデルベルク、ドイツ: 329–350。
• A. Rowstron、AM. Kermarrec、M. Castro、P. Druschel (2001 年 11 月)。「SCRIBE: 大規模イベント通知インフラストラクチャの設計」(PDF)。NGC2001 UCL ロンドン。

• ペストリープロジェクト
• Pastry実装を備えたOverSimシミュレータ