アルゴリズム

論文翻訳: GossipSub: A Secure PubSub Protocol for Unstructured, Decentralised P2P Overlays

Takami Torao 2019年の論文 #GossipSub
  • このエントリーをはてなブックマークに追加

概要

このレポートでは IPFS エコシステムにおいて特に IPNS レコードのメッセージメカニズムプロトコルとして現在使用されている pubsub プロトコルである gossipsub の背後にある設計の選択について説明する。我々はこのプロトコルの要件、この分野の関連研究、およびその動作に影響を与える特定のパラメータについて議論している。

Table of Contents

  1. 概要
  2. 1 導入
  3. 2 背景と関連研究
    1. 2.1 PubSub のトレードオフ
    2. 2.2 スケーラブルなトピックベースの Pub/Sub
    3. 2.3 スケーラブルなコンテンツベース PubSub
  4. 3 Gossipsub プロトコルの詳細
    1. 3.1 FloodSub
      1. 3.1.1 アンビエントピア検出
      2. 3.1.2 Flood ルーティング
      3. 3.1.3 振り返り
    2. 3.2 Flood の制御
      1. 3.2.1 randomsub: ランダムメッセージルーター
      2. 3.2.2 meshsub: オーバーレイメッシュルーター
      3. 3.2.3 gossipsub: ゴシップメッシュルーター
    3. 3.3 gossipsub プロトコル実装
      1. 3.3.1 制御メッセージ
      2. 3.3.2 ハートビート
      3. 3.3.3 ルーターの状態
    4. 3.4 トピックのメンバーシップ
      1. 3.4.1 メッセージ処理
      2. 3.4.2 制御メッセージの便乗
  5. 4 結論
  6. REFERENCES
  7. 翻訳抄

1 導入

Publish/Subscribe システムは伝統的に Publisher と Subscriber のセットの間で非同期的にメッセージを配信するために使用されてきた。送信者 (Publisher) と受信者 (Subscriber) は直接通信するのではなく、pub/sub システムを通じて通信する。Subscriber は関心のあるトピックを宣言し、Publisher はシステムのトピックの一つを発行する。そして pub/sub システムは 2 つを照合し新しいメッセージ (またはより一般的にはイベントと呼ばれる) をトピックの下にあるすべての Subscriber に配信する。pub/sub システムはインターネットアプリケーション (Twitter、RSS フィード、Facebook を参照) だけでなく汎用の P2P (Peer-to-Peer) システムでも広く使用されている。

一般にピアツーピア (P2P) ネットワークは、i) 構造化された P2P オーバーレイと、ii) 非構造化された P2P オーバーレイの 2 つのカテゴリに分けることができる。構造化 P2P オーバーレイ (またはネットワーク) では、ネットワークは何らかの構造を持っており、例えばトポロジー階層またはノード階層に基づいている。このような場合、一部のノード (スーパーノードと呼ばれることが多い) には、例えば購読しているノードに公開されたイベントを中継するなど他のノードよりも多くの責任を割り当てることができる。これらのノードはまた専用サーバであると仮定されるため pub/sub メッセージングのルーティングや、システムに関連するその他の操作を安定的かつ継続的にサポートすることができる。一方、非構造化 P2P オーバーレイネットワークはどのノードに対しても接続特性を仮定していない。つまり非構造化 P2P ネットワークでは、ノードはどのようなタイプ (常時接続のラックサーバから一時的に接続されるラップトップやモバイルデバイスまで) にもなる可能性があるため、ランダムなタイミングで接続と切断が行われる。このようなランダムな接続パターンにより構造化されていない P2P ネットワークではどのノードにも追加的なイベントルーティングやメッセージキャッシングの責任を割り当てることができない。さらに、メッセージの伝播を設計しメッセージ配信の信頼性 (つまりメッセージがネットワーク内のすべてのノードに所定の時間内に到達すること) を保証することは非常に困難である。

このような理由により非構造化 P2P ネットワークでは Flooding に近い pub/sub プロトコルや、またはオーバーレイ上のランダムウォークを使用してイベントおよびメンバーシップ情報を伝播することが非常に多い。しかしナイーブな Flooding はネットワークに大量の余計なトラフィックをもたらし、ランダムウォークはすべてのノードに到達するまでに長時間かかる場合がある。

これまでの研究では構造化 P2P ネットワークにおける pub/sub 設計の様々な側面や要件が扱われてきたが、非構造化 P2P ネットワークについてはほとんど扱われてこなかった。"Gossip" は、すべての Publish されたメッセージがすべて Subscribe されたピアに転送される Flooding と比較して、pub/sub システムのピア間で伝播されるメッセージの数を制限する方法として導入された。Gossip ベースのアプローチでは、ピアはメッセージそのものをんそうせずに "Seen" (観測した) メッセージに関連するメタデータを転送する。Gossip ベースのシステムを調査した研究は数多くあるが、大規模で構造化されていない pub/sub システムのスケーラビリティについては十分に議論されていない。

近年、分散型のインターネットサービスやアプリケーション設計と展開に大きな勢いが見られる。このようなサービスにはとりわけ分散化されたストレージ [8], [7], [12], [34], [2] のみならず計算システム [3] も含まれている。その目的は従来の中央で管理・運営されているクラウドサービスを置き換える、あるいは補完することである。エンドユーザはリソースの一部をネットワークに提供し、貢献度に応じて報酬を得る。このような新たなシステムは地理的な広がりという意味では分散型 (distributed) であり、所有、管理、運用という観点からは非中央型 (decentralised) である。

したがって我々は P2P オーバーレイを構築する傾向を目の当たりにしているが、ほとんどの場合、信頼性が低く専用でもないエンドユーザデバイスがネットワークへの積極的な貢献者となる。中央制御がない場合、これらのシステムにおけるメッセージングは操作プロセス (例えばファイルの検索や関数の実行) を伝達するだけではなく、管理イベントを伝播するために最も重要である。

pub/sub は分散チャットやソーシャルネットワーク [12], [10]、バックエンドサーバを持たない共同編集ツール [11]、非管理 P2P ネットワークにおける動的な Web サイトコンテンツホスティング [8]、進化するデータセットの保存と同期など、分散サービスの分野で分散アプリケーションからの利用が急増している。

分散ストレージシステム、特に InterPlanetary File System (IPFS) エコシステムの場合、pub/sub はシステムの最も中心的で重要な機能の 1 つであるコンテンツルーティングを含むいくつかの目的に使用することができる。IPFS はコンテンツアドレッシングが可能な分散 P2P ストレージネットワークであり、毎日数十万人のユーザが利用している。ユーザはラップトップデバイスを使用し頻繁に切断される信頼性の低いノードとしてネットワークに参加することができる。ここで提案する Gossip ベースの pubsub プロトコル (頭文字を取って "gossipsub") はこのようなシステムおよび環境要件 (つまり非管理ネットワークと停信頼のノード) を念頭に置いて開発され、現在 IPFS の分散型命名システム (頭文字を取って IPNS [9]) に命名レコードの更新をプッシュするために使用されている。

pubsub と、特に提案されている gossipsub プロトコルは ETH2 [4] や Filecoin [5] のような新しい P2P システムでも近い将来にトランザクションブロックのような主要なルーティングプロトコルとして使用されるだろう。ETH2 や Filecoin などのシステムは主に金融システムであり、金額に換算すると数百万ドル相当のトランザクションメッセージを伝送することが期待されている。とはいえ gossipsub のセキュリティ特性は詳細に調査する必要があり、このレポートの今後のバージョンで調査する予定である。

過去に提案された pubsub システムは管理されたクラウドベースの環境でのスケーラビリティ特性が証明されている。非構造化 P2P オーバーレイ用に提案された pubsub プロトコルは少数であり、その中で 10,000 ノードを超える高い離脱率 (rates of churn) で検証されたものはさらに少ない。IPFS には既に毎日数十万のユーザを抱えており、指数関数的に数百万人まで成長すると予想されている。ETH1.0 にはすでに 16,000 人を超えるユーザがおり、ETH2.0 が登場すればこの数は数桁増加すると予想される。

とはいえ、そのようなシステムに展開する前にプロトコルの徹底的な評価が不可欠である。これが本書が追求しようとしている目的である。現在のバージョンではこの分野の関連研究との概念的な比較と共に、プロトコルの主な設計上の選択を説明するところから始めている。

gossipsub 設計の概要: ここで提案する gossipsub プロトコルは Gossip ベースの pubsub プロトコルに分類される。その設計上の主な特性は Gossip 機能と遅延プッシュによって補完された連結メッシュである。遅延プッシュ (lazy push) とは pussub システムで使用される技術であり、メッセージ全体ではなくメタデータのみを Subscribe ノードに転送する。そしてノードは受信したメタデータの実際のメッセージに興味があればメッセージを明示的に要求する。多くの非構造化 P2P ネットワークと同様にプロトコルの最初のバージョンは Flooding ベースの pubsub に近かった。しかし IPFS ネットワークが時間と共に成長するにつれ Flooding が効率的なアプローチでないことは明らかになった。スケーラビリティの要求がすぐに表面化し、プロトコルのコア機能として Gossip と遅延プッシュによって補完される連結メッシュである meshsub の設計が行われた。これらの技術の組み合わせとカスタムルーティングヒューリスティックをプラグインする機能が gossipsub の主な新規性を構成している。gossipsub の設計の背景にある哲学は、実装のシンプルさと動的なネットワーク状況への対応することである。

Fig 1: トピックとピア
Fig 2: Subscriber に配信されたメッセージ

2.1 PubSub のトレードオフ

汎用 pub/sub メッセージングシステムは P2P ネットワークのにおけるいくつかの異なる側面 (管理運用から性能まで) から非常に有用であることが証明されており、多くのトレードオフが伴っている [19], [20]。pubsub システム上には多種多様なアプリケーションが構築されており、すべてのトレードオフがすべてのシステムに当てはまるわけではなく、その多くは互いに矛盾している。以下ではこれらのトレードオフについて議論し、必要に応じてそれらが gossipsub の設計にどのような影響を与えたかに注目する。

  1. 信頼性のある配信 (Reliable Delivery). ノードのダウンタイムがない場合、すべての Publish メッセージはすべての Subscribe ノードに配信されなければならない。pub/sub システムはノードの離脱に対して堅牢 (robust) である必要があり、ほとんどのノードに到達できる (すなはち高いヒット率を達成できる) べきである。堅牢性とは別に離脱からの高速な回復も必要である。gossipsub では Gossip メッセージングを使用することでノードの離脱と切断の環境に対処している。これは IPFS ネットワークでプロトコルを使用するための厳しい要件だが、libp2p の機能としてより一般的な要件でもある。

  2. 負荷分散 (Load Balancing). イベントメッセージの中継負荷はノード間でほぼ均等に分割される必要がある。ノードが 5K イベントを Subscribe するようなスケールアップされたシステムを想定すると、メッセージの中継は重いタスクになるため、ノードが (次数的に) より多くのノードと接続すればするほどより多くの中継タスクを実行しなければならなくなる。

  3. スケーラビリティ (Scalability). クラウド環境だけではなく分散型 P2P 環境でもネットワークシステムが成長していることを考慮すると、システムは何百万ノード1までスケールアップできる必要がある。非管理 P2P 環境においてこれほどのスケーラビリティを達成しながら今日の基準で許容できるパフォーマンス (ルックアップはミリ秒単位、配信は 1 秒未満) を達成したシステムは (存在したとしても) ほとんどない。

  4. 回復力とリソース効率 (Resilience & Resource-Efficientcy). pub/sub システムではメッセージが Subscribe ノードに 2 回配信されることが一般的である。これは明らかに個々の中継ノードの負荷が増加するだけでなくシステム全体の帯域幅要件も増加させる。一方、冗長配信はシステムのセキュリティと回復力の特性を高めることができる。回復力を実現すると同時にリソース効率の面で悪影響を与えないようにするためには、メッセージの重複配信を一定のレベル内に抑える必要がある。

上記のトレードオフの多くに対処するための過去の [22], [23] では、ブロードキャスト (スパニング (spanning)) ツリーの構築が提案されているが、ツリーはその長さに対して線形にしかスケールできない。最も重要なことは離脱に対して堅牢ではないことである。一方、Gossip は本質的にノードの傷害や離脱に対し堅牢だがリソース効率と負荷分散に苦しむ可能性がある。

特に管理されておらず構造化されていない P2P オーバーレイにおいて適切なバランスを取るという解決策はこれまでのところ解決されていない。提案する解決策はシンプルな設計でありながらリソース効率に優れ、このギャップを埋めるアプローチである。

この分野の文献は膨大である。このセクションの目的は提案の大部分を調査することではなく、非構造化、非管理の P2P pub/sub オーバーレイに教訓を学び、適用できる最も重要な貢献を指摘することである。

  1. 1 Bittorent ネットワークは 1 日に数千万ノードがアクティブだったが、IPFS は現在数十万ノード、ETH2 ネットワークは数百万ノードになると予想されている。

2.2 スケーラブルなトピックベースの Pub/Sub

クラウドベースのシステムは需要に応じて拡張する必要があるため、pub/sub システムにおけるスケーラビリティはクラウド環境における重要な要件だった。Amazon [1] と Google Cloud Messaging [6] は共に pub/sub プロトコルを運用しているが、その運用の詳細はあまり明らかにされていない。

Scribe [18] は Pastry DHT 上に分散型マルチキャストオーバーレイを提案した最初の pub/sub システムの 1 つである。DHT はいくつかの pub/sub システムで使用されている (Meghdoot [21], Bayeux [36] 参照)。ほとんどの場合、DHT は Subscribe の場所を見つけてそこへルーティングするため [21]、またはトピックへのランデブーポイント [18] として使用されている。Poldercast [31] はリングオーバーレイ (および最適化としての追加リンク) を使用する興味深いアプローチである。トピックの Subscriber はこのリングに接続され、メッセージは他のすべての Subscriber に伝播される。直接のリンクが存在して利用できない限り、すべてのノードに通知するための待ち時間が線形に増加することは明らかである。Dynatops [35] は期間の短い Subscribe を処理できる自己構成されたトピックベースの pub/sub システムとして提案された。これらすべてのシステムには Subscriber をカバーするために広域ネットワーク全体に広がるブローカーネットワークが必要である。Dynamoth [20] は仲介の pub/sub と直接接続されたクライアント/サーバモデルとのハイブリッドとしてレイテンシーを削減するために提案された。しかしこれはクラウドベースのシステムにのみ適用可能であり P2P オーバーレイには適用できない。

我々の研究に近いものは Vitis [29], Tera [13], Rappel [27], StAN [26] などのシステムである。これらは情報を伝播するために Gossip を使用し非構造化 P2P オーバーレイを構築する。Gossip ベースのプロトコルはフルメッセージ (full message) とメタデータピアリング (metadata peering) の 2 つの種類のピアリングを区別する (Fig 3 と Fig 4 を参照)。2 つのノードがフルメッセージピアリングの場合、一方のノードが受信したメッセージはそのフルメッセージピアに転送される。対照的に、2 つのデータがメタデータピアの場合、受信したメッセージのメタデータのみを交換する。メタデータピアは Publish されたメッセージを "認識" (aware) しているが実際には Publish されたメッセージを持っていない。gossipsub はメタデータピアリングの概念を拡張して、以前に提案された遅延プッシュの概念を実装している。この概念にしたがってネットワーク内のピアはメッセージの存在のみを (例えばメッセージ ID を通じて) 通知されるが、ノードが新しく公表されたメッセージを明示的に要求したときにのみメッセージは転送される。

Fig 3: フル vs. メタデータピアリング
Fig 4: Gossip ベースのメッセージ配信

[29] の著者は特に、ほとんどの類似システムはトピックごとに 1 つの個別のオーバーレイを構築しており、その結果、ノードは膨大な数のオーバーレイのメンバーになっていると主張している。これは Vitis [29] によると、中継ノードのオーバーヘッドを増加させ、中継ノードが意欲を失ってシステムから離脱する可能性がある。対照的に、Vitis はノードごとの接続数を制限することでこの問題に対処している。これは Gossip メッセージを使用して他のノードが購読しているトピックをサンプリングすることによって行われる。そしてトピックが重複するノードを同じオーバーレイにグループ化することで、必要なオーバーレイの数を減らすと同時にノードが選択したトピックへの Subscribe を維持する。

Rappel [27] は Subscriver ノードに対する低オーバーヘッドと低ノイズ、つまりノードが Subscribe していないトピックのメッセージを受信することをターゲットとしている。Rappel は関心の局所性に基づいて構築された "友達オーバーレイ" のネットワークを構築することでこれを実現する。Rappel はまた関心の局所性に加えてネットワークの局所性を考慮することによりメッセージの高速な拡散も目標としている。

これらは非構造化 P2P オーバーレイに対する Gossip ベースの pub/sub への非常に興味深いアプローチだが、いずれも大規模なスケール (例えば数百万ノード) でのスケーラビリティや、ノードの大幅な離脱についてはテストされていない。Rappel [27] は最大 25% のノード離脱に対して堅牢であると主張しているが、Tera [13 はこの部分を将来の評価に残している。

IPNS での名前レジストリの伝搬、Filecoin でのリクエストルーティング、ETH2 でのトランザクションルーティングなどのシステムで必要とされるスケールは、非構造化および非管理の P2P オーバーレイに対して過去にテストされたシステムよりも桁違いに高くなる可能性がある。ノードの離脱もまた大きなものになる可能性があるが、我々は 30% のしきい値が許容範囲であると予想している。

gossipsub は、我々が必要とするネットワークの規模にあわせて拡張して対処できるように、設計と実装の両方でシンプルにすることを目指して構築されている。信頼性の低い環境でのノードの離脱など変化するネットワーク条件に対応することも gossipsub の設計によって実現された特徴である。

2.3 スケーラブルなコンテンツベース PubSub

コンテンツベースの pub/sub システムは、例えば [17] のように過去に広く研究されてきたが [15], [16] のように情報中心ネットワークの文脈でも研究されている。一般にコンテンツベース (または属性ベースとも呼ばれる) pub/sub システムでは、Publisher と Subscriber の間でより細かい粒度のマッチングを提供できるが、これを実現するためにはより多くの計算リソースが必要となる。gossipsub はコンテンツベースの pub/sub に基づいて構築されているわけではないため、このセクションでは念のためいくつかのアプローチについて議論する。

BlueDove [24] はこの分野ではよく知られたアプローチの一つである。これは多次元の属性をサポートし、スケーラブルなトポロジーでオーバーレイサーバを構成する。E-StreamHub [14] は負荷に応じてノードを追加・削除するという興味深い特徴を持つミドルウェアとして提案されている。これらのアプローチはいずれもクラウドベースでスケーラビリティと低レイテンシーを実現しているが非管理 P2P ネットワークには適用できない。実際、ほとんどのコンテンツベース pub/sub システムはクラウド環境または何らかのブローカーベースのインフラスト落車をターゲットとしている (Elvin, Sienna [17], HERMES [28], Gryphon [33])。Subscriber の情報を保護するためのプライバシー保護技術も [30], [32] のようないくつかの注目すべき研究によりコンテンツベースの pub/sub システムで広範囲に研究されている。

3 Gossipsub プロトコルの詳細

3.1 FloodSub

libp2p の最初の pubsub プロトコルは floodsub だった。floodsub は最も基本的な方法で pubsub を実装している: i) アンビエントピアの検出, ii) 最も基本的なルーティングおよびメッセージ伝播プロトコルとして Flooding。

3.1.1 アンビエントピア検出

アンビエントピア検出では、ピア検出タスクが pubsub プロトコルの範囲外に押し出され、代わりにピア検出のメカニズムが環境によって提供される。実際には IPFS の場合、これは DHT ウォーク、ランデブーポイント、または同様の技術によって実現できる。libp2p のモジュール設計によりこのようなレベルでの分離が可能になっている。FloodSub はこれらの検出メカニズムが生成するアンビエント接続イベントに依存する。新しいピアが接続されるたび、プロトコルはピアが FloodSub や gossipsub を実装しているかを確認し、実装している場合は現在購読しているトピックを通知する 'hello' パケットを送信する。

これによりピアは関心のあるすべてのトピックのソフトオーバーレイを維持できるようになる。オーバーレイはトピックリストに変更があるときはいつでもサブスクリプション制御メッセージを交換することによって維持される。サブスクリプチョンメッセージはそれ以上伝達されないため、各ピアはその直接のピアのみトピックビューを維持する。ピアが切断されるとそのピアはオーバーレイから削除される。

アンビエントピア検出は任意の外部手段によって駆動でき、プロトコルの実装に外部依存することなく直感的な開発が可能となる。

検出機能の標準的なアプローチとして検討しているいくつかの選択肢がある:

  • プロバイダレコードを使用した DHT ランデブー。トピック内のピアはトピックにちなんで名付けられたプロバイダレコードをアナウンスする。

  • 既知のランデブーポイントまたは動的に検出されたランデブーポイントを介してランデブーする。

3.1.2 Flood ルーティング

Flooding を使用するとルーティングはほとんど簡単になる。受信メッセージごとにトピック内の既知のピアにすべて転送される。我々の実装では、ルーターは以前のメッセージの時間指定されたキャッシュを維持するため、過去に見たメッセージが 2 回以上転送されることはない。またこのプロトコルはメッセージを転送元やメッセージを送信したピアに転送することもない。

3.1.3 振り返り

実行可能な pubsub プロトコルとして FloodSub を評価すると次のような非常に望ましい特性が明らかになる:

  • 実装が簡単である。

  • 遅延を最小限に抑える。メッセージは最小遅延パス (minimum latency path)、モジュロオーバーレイ接続を介して配信される。

  • 高い堅牢性。メンテナンスのロジックや状態はほとんどない。

しかし問題はメッセージが最小遅延パスをたどるだけではなく、すべてのエッジ (辺) をたどるため Flood (洪水) が発生することである。ネットワークのアウトバウンドの次数には制限がない。これはピアの帯域幅が冗長なトラフィックで飽和することを意味する。一方、冗長なトラフィックはネットワークの回復力を高め、無制限の度合いにより Sybil 攻撃に対する耐性レベルが自然に生み出される。gossipsub が利用しようとするメッセージの冗長性は明らかなり点があるが、同時にピアノリソースを圧迫することはない。これはスケーラビリティを向上させ分散化をサポートするために不可欠である。

同様に、増幅幅はすべてのノードの次数の合計によってのみ制限されるため、密に接続されたオーバーレイではスケーリングの問題が生じる。

3.2 Flood の制御

過剰な帯域幅の浪費やピアの過負荷を生じさせずに pubsub を拡張するには、各ピアの次数を制限し増幅率をグローバルに制御するルーターが必要である。

3.2.1 randomsub: ランダムメッセージルーター

最初のステップとして randomsub と呼ばれる最も単純な bounded floodsub の変種を検討する。この構成は、トピック内の既知のピアのリストを除けばルーターはステートレスである。ただしすべてのピアにメッセージを転送するのではなく、最大 \(D\) 個のピアのランダムなサブセットに転送する。ここで \(D\) はネットワークの必要な次数である。

この構造の問題はメッセージの伝播ターンが非決定論的なことである。その結果、メッセージ経路が極端に不安定になり、メッセージの順序が入れ替わったりタイミングパターンが変化する。これは多くのアプリケーションによって望ましくない特性である。

3.2.2 meshsub: オーバーレイメッシュルーター

meshsub は pubsub ネットワーク内のメッセージ数を制限することで randomsub 構造を改善している。これは帯域幅要件、ネットワーク、ノード/ルーターの負荷を軽減するために不可欠である。ただしメッセージごとにピアをランダムに選択するのではなく、各ピアが安定的にピアのサブセットに転送するオーバーレイメッシュを形成する。この方法で meshsub と呼ばれるルーターを構築した。

各ピアはトピックごとにメッシュの独自ビューを維持する。これは他のピアへの双方向相互リンクリストである。つまり定常状態であれば、ピア A がピア B のメッシュ内にあるときはいつでも、ピア B もピア A のメッシュにいる。

オーバーレイは最初トピックのみに基づいてランダムな方法で構築される。ピアがトピックに参加するたびに (トピック内の) \(D\) 個のピアをランダムに選択してメッシュに追加し、制御メッセージで通知する。トピックを離れるときはそのピアに通知し、トピックのメッシュを忘却する。

メッシュは以下の定期的な安定化アルゴリズムで維持される:

  at each peer:
loop:
if |peers| < D_low:
select D - |peers| non-mesh peers at random and add them to the mesh
if |peers| > D_high:
select |peers| - D mesh peers at random and remove them from the mesh
sleep t

meshsub アルゴリズムのパラメータは次の通り: \(D\) は目標次数であり、2 つの緩和次数パラメータ D_low と D_high は許容可能なメッシュ次数境界を表す。その目的は弾力性を導入し、過度のバタつきを抑制することである。

3.2.3 gossipsub: ゴシップメッシュルーター

meshsub ルーターは優れた増幅制御特性を備えたベースライン構造を提供する。これをメッセージフローに関する Gossip で補強する。Gossip は現在メッシュに属していないピアのランダムなサブセットに対して発信される。Gossip メッセージを使ってネットワーク全体にメッセージフローに関するメタデータを伝播することができる。メタデータは任意だが、ベースラインとして Gossip を発信しているルーターが過去数秒以内に確認したメッセージ ID を含める。実際のメッセージ自体はキャッシュされているため Gossip を受信したピアは制御メッセージで送信を要求することができる。

ルーターはこのメタデータを使ってメッシュを改善し、感染 (epidemic) ブロードキャストツリーを作成できる。さらにメタデータはダウンストリームのメッセージ損失を修正するためにオーバーレイの様々なポイントでメッセージ送信を再開することができる。あるいは単に便宜的にホップをジャンプしてメッシュ内のある程度の距離にあるピアのメッセージ送信を加速することもできる。

基本的に gossipsub はデータ用の meshsub とメッシュメタデータ用の randomsub を組み合わせ、遅延プッシュ型で実現したものである。これらの技術を組み合わせることで切断されたメッシュ、"不法占拠ピア" (squatting peers)、ネットワーク状況への応答性、そして最も重要なスケーラビリティの要件を満たす強力な構造を提供する。gossipsub は meshsub 構造で制限された次数と増幅率を提供し、randomsub の技術でメタデータの Gossip 伝搬を使用して拡張する。

3.3 gossipsub プロトコル実装

ルーターの実装を概略的に示し gossipsub プロトコルの使用を提供する。ルーターは FloodSub を下位互換があり、FloodSub ピアを受け入れてそれらに対して FooldSub のように動作する。

3.3.1 制御メッセージ

プロトコルは 4 つの制御メッセージを定義する:

  • GRAFT: メッシュリンクの接ぎ木; これはピアがローカルメッシュビューに追加されたことを通知する。
  • PRUNE: メッシュリンクの刈り込み; これはピアがローカルメッシュビューから削除されたことを通知する。
  • IHAVE: ゴシップ; 続くメッセージが最近観測され、要求に応じて利用可能であることを通知する。
  • IWANT: IHAVE メッセージでアナウンスされたメッセージの送信を要求する。

3.3.2 ハートビート

ルーターは定期的にハートビート手順を実行する。これはメッシュの維持、Gossip の発行、およびメッセージキャッシュのシフトを行う。

3.3.3 ルーターの状態

ルーターは次の状態を維持する:

  • peer: すべての既知のピアセット; peers.gossipsub は gossipsub ピアを示し、peers.floodsub は floodsub ピアを示す。
  • mesh: トピックのピアリストへのマップとしてのオーバーレイメッシュ。
  • ranout: トピックのピアリストへのマップとしての、トピックメンバーシップなしで Publish するメッシュピア。
  • seen: これは時間指定されたメッセージ ID キャッシュであり、観測されたメッセージを追跡する。
  • mcache: 最後の数回のハートビート tick のメッセージを含むメッセージキャッシュ。

メッセージキャッシュはメッセージ ID のウィンドウと対応するメッセージを格納するデータ構造である。次の操作をサポートする:

  • mcache.put(m): 現在のウィンドウとキャッシュにメッセージを追加する。
  • mcache.get(id): メッセージがまだ存在する場合、ID によってキャッシュからメッセージを取得する。
  • mcache.window(): 現在の履歴ウィンドウのメッセージの ID を取得する。
  • mcache.shift(): 現在のウィンドウをシフトし、キャッシュの履歴の長さよりも古いメッセージを破棄する。

観測済みキャッシュはフロー制御メカニズムである。過去 2 分間に観測したメッセージのメッセージ ID を追跡する。Go での実装上の理由からこれは mcache とは別のものだが (観測済みキャッシュは pubsub フレームワークから継承されている)、同じデータ構造にすることもできる。ルーターはある程度健全なマージンを持ってオーバーレイの伝播遅延を近似するために選択された別の値を使用することができる。

3.4 トピックのメンバーシップ

トピックのメンバーシップはローカルの pubsub SDK API の一部としてルーターによってサポートされている 2 つの操作によって制御される:

  • JOIN(topic) ではルーターはトピックに参加する。これを行うために、トピックの fanout ピアの \(D\) 個のピアが既にある場合はそれらを mesh[topic] に追加し、GRAFT(topic) 制御メッセージで通知する。そうでない場合、トピックの fanout に \(D\) 個未満 (この数を \(x\) とする) のピアがある (またはトピックが fanout にない) 場合、やはり上記のようにそれらを追加する (もしあれば)。またアルゴリズムは peers.gossipsub[topic] からピアの残りの数 (\(D - x\)) を選択し、それらを mesh[topic] に追加して GRAFT(topic) 制御メッセージで通知する。

  • LEAVE(topic) ではルーターはトピックから離脱する。PRUNE(topic) メッセージで mesh[topic] のピアに通知し mesh[topic] を忘れる。

ルーターはトピックのメンバーシップがなくてもメッセージを発行できることに注意。この場合、安定したルートを維持するために、ルーターは fanout マップで公開した各トピックのピアのリストを維持する。ルーターがしばらくの間トピックをのメッセージを Publish しない場合、そのトピックの fanout ピアは忘れられる。つまりこれはソフト状態である。

また pubsub API の一部として、ピアがトピックに参加または離脱するたび、ピアはすべてのピアに SUBSCRIBE と UNSUBSCRIBE 制御メッセージを発行することに注意。これはアンビエントピア検出メカニズム (ambient peer discovery mechanism) によって提供されるものであり、名目上はルーターの一部ではない。スタンドアロンの実装ではこれらの制御メッセージを実装する必要がある。

3.4.1 メッセージ処理

メッセージを受信するとルーターはまずペイロードを処理する。それが以前に観測したことのない有効なメッセージを含んでいる場合は、そのメッセージを Publish する。特に

  • peers.floodsub[topic] 内のピアがメッセージの送信元ではない場合、それらすべてのピアにメッセージを転送する。

  • mesh[topic] 内のピアがメッセージの送信元ではない場合、それらすべてのピアにメッセージを転送する。

ペイロードを処理した後、エンベロープ内の制御メッセージを処理する:

  • GRAFT(topic) では、トピックに Subscribe されている場合、ピアを mesh[topic] に追加する。Subscribe されていない場合は PRUNE(topic) 制御メッセージで応答する。

  • PRUNE(topic) では、mesh[topic] からピアを削除する。

  • IHAVE(ids) では、観測済みセットをチェックし IWANT メッセージで未知のメッセージを要求する。

  • IWANT(ids) では、mcache に存在するすべての要求メッセージを要求側ピアに送信する。

ルーターが (アプリケーション層で) ルーター自身から発信されたメッセージを Publish する場合、ペイロードの反応と同様に進行する:

  • メッセージは peers.floodsub[topic] 内のすべてのピアに転送される。

  • トピックに Subscribe されている場合、メッセージの転送先となる一連のピアが mesh[topic] 内に存在しなければならない。

  • トピックに Subscribe されていない場合、fanout[topic] のピアにメッセージを転送する。この集合が空であれば、peers.gossipsub[topic] から \(D\) 個のピアを選択し新しい fanout[topic] ピアとしてそれらに転送する。

3.4.2 制御メッセージの便乗

Gossip や他の制御目セージはそれ自身のメッセージで転送する必要はない。代わりに、任意のトピックについて、通常のフロー内の他のメッセージを結合して便乗 (piggyback) させることができる。これは、トピック間に何らかの相関フローがある場合にメッセージのレート低下に繋がる可能性があり、高度に接続されたピアでは重大な影響を与える可能性がある。我々が選択したメタデータ (すはなちメッセージ ID) はベースラインとして使用されるが (セクション 3.2.3 参照)、便乗はネットワークに余計なトラフィックを挿入することなく、この種の情報を伝播するために非常に優れた方法で、遙かに大きなネットワークサイズに拡張できる。

4 結論

IPFS エコシステムで使用されている pubsub プロトコルの設計上の選択と、その選択の背後にある理由を示した。また pubsub の分野における関連研究の簡単な調査を提供し、gossipsub の設計上の選択を関連文献のものと概念的に比較した。本レポートは決して包括的な文献調査と見なされるべきではないが、我々は全体像を描く調査論文を紹介している。

Filecoin ネットワークにおけるトランザクションメッセージ/ブロックの主要なルーティングプロトコルとして gossipsub がまもなく導入されるため、現在 gossipsub のセキュリティ対策を調査しており、最初のセキュリティ強化が設計されたらこのレポートを更新する予定である。

Figure 5: 新しいピアリングノードの接ぎ木
Figure 6: 既存ノードの枝切り
Figure 7: フルピアリングノードの接ぎ木
Figure 8: フルピアリングノードの枝切り

REFERENCES

  1. Amazon SND. https://aws.amazon.com/pub-sub-messaging/.
  2. DAT Protocol Foundation. https://dat.foundation.
  3. Dfinity: The Internet Computer. https://dfinity.org.
  4. Ethereum 2.0. https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/.
  5. filecoin: A decentralised market for storage.
  6. Google/Firebase Cloud Messaging. https://firebase.google.com/docs/cloudmessaging/.
  7. IPFS - Content Addressed, Versioned, P2P File System. https://ipfs.io/ipfs/QmR7GSQM93Cx5eAg6a6yRzNde1FQv7uL6X1o4k7zrJa3LX/ipfs.draft3.pdf.
  8. IPFS: InterPlanetary File System. https://ipfs.io.
  9. Ipns: Interplanetary naming system. https://docs.ipfs.io/guides/concepts/ipns/.
  10. Mastodon Social Network. https://joinmastodon.org.
  11. PeerPad. https://peerpad.net.
  12. Secure Scuttlebutt. https://scuttlebutt.nz/.
  13. Baldoni, R., Beraldi, R., Quema, V., Querzoni, L., and Tucci-Piergiovanni, S. Tera: Topic-based event routing for peer-to-peer architectures. In Proceedings of the 2007 Inaugural International Conference on Distributed Event-based Systems (New York, NY, USA, 2007), DEBS ’07, ACM, pp. 2–13.
  14. Barazzutti, R., Felber, P., Fetzer, C., Onica, E., Pineau, J.-F., Pasin, M., Rivière, E., and Weigert, S. Streamhub: A massively parallel architecture for highperformance content-based publish/subscribe. pp. 63–74.
  15. Carzaniga, A., Khazaei, K., Papalini, M., and Wolf, A. L. Is informationcentric multi-tree routing feasible? SIGCOMM Comput. Commun. Rev. 43, 4 (Aug. 2013), 3–8.
  16. Carzaniga, A., Papalini, M., and Wolf, A. L. Content-based publish/subscribe networking and information-centric networking. In Proceedings of the ACM SIGCOMM Workshop on Information-centric Networking (New York, NY, USA, 2011), ICN ’11, ACM, pp. 56–61.
  17. Carzaniga, A., Rosenblum, D. S., and Wolf, A. L. Design and evaluation of a wide-area event notification service. ACM Transactions on Computer Systems 19, 3 (Aug. 2001), 332–383.
  18. Castro, M., Druschel, P., Kermarrec, A. ., and Rowstron, A. I. T. Scribe: a large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications 20, 8 (Oct 2002), 1489–1499.
  19. Eugster, P. T., Felber, P. A., Guerraoui, R., and Kermarrec, A.-M. The many faces of publish/subscribe. ACM Comput. Surv. 35, 2 (June 2003), 114–131.
  20. Gascon-Samson, J., Garcia, F.-P., Kemme, B., and Kienzle, J. Dynamoth: A scalable pub/sub middleware for latency-constrained applications in the cloud. Proceedings - International Conference on Distributed Computing Systems 2015 (07 2015), 486–496.
  21. Gupta, A., Sahin, O. D., Agrawal, D., and Abbadi, A. E. Meghdoot: Content-based publish/subscribe over p2p networks. In Proceedings of the 5th ACM/IFIP/USENIX International Conference on Middleware (Berlin, Heidelberg, 2004), Middleware ’04, Springer-Verlag, pp. 254–273.
  22. Leitao, J., Pereira, J., and Rodrigues, L. Epidemic broadcast trees. In 2007 26th IEEE International Symposium on Reliable Distributed Systems (SRDS 2007) (Oct 2007), pp. 301–310.
  23. Leitao, J., Pereira, J., and Rodrigues, L. Hyparview: A membership protocol for reliable gossip-based broadcast. In Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (Washington, DC, USA, 2007), DSN ’07, IEEE Computer Society, pp. 419–429.
  24. Li, M., Ye, F., Kim, M., Chen, H., and Lei, H. Bluedove: A scalable and elastic publish/subscribe service. In IEEE IPDPS 2011 (05 2011), pp. 1254–1265.
  25. Malekpour, A., Carzaniga, A., Pedone, F., and Toffetti Carughi, G. Endto- end reliability for best-effort content-based publish/subscribe networks. In Proceedings of the 5th ACM International Conference on Distributed Event-based System (New York, NY, USA, 2011), DEBS ’11, ACM, pp. 207–218.
  26. Matos, M., Nunes, A., Oliveira, R., and Pereira, J. Stan: Exploiting shared interests without disclosing them in gossip-based publish/subscribe. In Proceedings of the 9th International Conference on Peer-to-peer Systems (Berkeley, CA, USA, 2010), IPTPS’10, USENIX Association, pp. 9–9.
  27. Patel, J., Riviere, E., Gupta, I., and Kermarrec, A.-M. Rappel: Exploiting interest and network locality to improve fairness in publish-subscribe systems. Computer Networks 53 (08 2009), 2304–2320.
  28. Pietzuch, P. R., and Bacon, J. M. Hermes: a distributed event-based middleware architecture. In Proceedings 22nd International Conference on Distributed Computing Systems Workshops (July 2002), pp. 611–618.
  29. Rahimian, F., Girdzijauskas, S., Payberah, A. H., and Haridi, S. Vitis: A gossipbased hybrid overlay for internet-scale publish/subscribe enabling rendezvous routing in unstructured overlay networks. In Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium (Washington, DC, USA, 2011), IPDPS ’11, IEEE Computer Society, pp. 746–757.
  30. Rao,W., Chen, L., and Tarkoma, S. Toward efficient filter privacy-aware contentbased pub/sub systems. IEEE Transactions on Knowledge and Data Engineering 25, 11 (Nov 2013), 2644–2657.
  31. Setty, V., van Steen, M., Vitenberg, R., and Voulgaris, S. Poldercast: Fast, robust, and scalable architecture for p2p topic-based pub/sub. In Proceedings of the 13th International Middleware Conference (New York, NY, USA, 2012), Middleware ’12, Springer-Verlag New York, Inc., pp. 271–291.
  32. Shikfa, A., Önen, M., and Molva, R. Privacy-preserving content-based publish/ subscribe networks. vol. 297, pp. 270–282.
  33. Strom, R., Banavar, G., Chandra, T., Kaplan, M., Miller, K., Mukherjee, B., Sturman, D., and Ward, M. Gryphon: An information flow based approach to message brokering. CoRR cs.DC/9810019 (10 1998).
  34. Tarr, D., Lavoie, E., Meyer, A., and Tschudin, C. Secure scuttlebutt: An identitycentric protocol for subjective and decentralized applications. In Proceedings of the 6th ACM Conference on Information-Centric Networking (New York, NY, USA, 2019), ICN ’19, ACM, pp. 1–11.
  35. Zhao, Y., Kim, K., and Venkatasubramanian, N. Dynatops: A dynamic topicbased publish/subscribe architecture. pp. 75–86.
  36. Zhuang, S. Q., Zhao, B. Y., Joseph, A. D., Katz, R. H., and Kubiatowicz, J. D. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In Proceedings of the 11th International Workshop on Network and Operating Systems Support for Digital Audio and Video (New York, NY, USA, 2001), NOSSDAV '0, ACM, pp. 11-20.

翻訳抄

非構造化分散型 P2P オーバーレイで使用される安全な pub/sub プロトコルである gosshipsub について説明する 2019 年の論文。

  1. VYZOVITIS, Dimitris; PSARAS, Yiannis. GossipSub: A Secure PubSub Protocol for Unstructured, Decentralised P2P Overlays. Proceedings of the Protocol Labs TechRep, PL-TechRep-gossipsub-v0, 2019.