IPFSコンテンツ公開を10倍高速化した方法

序論 分散ハッシュテーブル（DHT）におけるコンテンツの公開は、特にi)ネットワークが大きく、ii)ネットワークに参加しているノードが頻繁に入れ替わる場合、従来は遅い操作でした。IPFSのAmino DHTもこれらの条件の両方を満たしており、例外ではありません。ProbeLabチームは、数年前から広範な測定を通じてこの問題を特定し、パフォーマンスを向上させる最適化、すなわちコンテンツ公開時間を1桁以上短縮し、同時にネットワークオーバーヘッドを40%削減する最適化を提案しました。この最適化はOptimistic Provideと名付けられ、最近IPFSのKubo 0.39.0でデフォルトとして出荷されました！この研究はIEEE INFOCOM 2024で発表されており、より詳細で濃い内容についてはそちらを参照してください。このブログ投稿では、私たちのチームが提案した技術の概要、基本的な技術詳細、そしてもちろん、その有効性に関する最初の主張を証明する結果を提供します。この機能が本番環境に導入されるまでのサポートと最後の推進をしてくれたIPShipyardチームに感謝します。結果によれば、それは努力に値しました。 TL;DR Optimistic Provideの基本的なアイデアは次のとおりです。 1. DHTをウォークしながら、ネットワーク全体で20の最も近いピアの中にいる可能性が高いピアにレコードを即座に保存します。 2. 発見された20の最も近いピアのセットが、ネットワーク全体で最も近いピアを構成する可能性が高い場合、DHTウォークをすぐに終了します。 3. ほとんどの（すべてではない）PUT RPCが成功した後、ユーザーに制御を返し、残りのRPCはバックグラウンドで続行します。 ポイント1と2は、ネットワーク全体のサイズに関する知識を必要としますが、これはルーティングテーブルのリフレッシュメカニズムに便乗する軽量な推定方法から導き出し、追加のネットワークオーバーヘッドは発生しません。Optimistic Provideはアップロードレイテンシを13秒以上（しばしば20秒近く）から1秒未満に大幅に短縮し、IPFSのパフォーマンスに計り知れない価値と影響をもたらします。これが実際に意味すること：コンテンツパブリッシャーは、コンテンツがネットワークにプッシュされてから約1秒後、つまりほぼリアルタイムでコンテンツを公開できるようになりました。これは、以前の10秒以上と比較して大幅な改善であり、開発者、ユーザー、アプリケーションプロバイダーはリアルタイムで再試行およびデバッグできます。 従来のプロバイド操作 これらの最適化がどのように機能するかを理解するには、まず従来の「プロバイド」操作を見る必要があります。IPFSが使用するAminoネットワークのようなKademliaベースの分散ハッシュテーブル（DHT）では、レコードを保存するために、そのデータの識別子に最も近いk個のピアを特定する必要があります。Amino DHTではkは20に設定されています。この文脈での「近さ」は地理的な近接性ではなく、XOR距離メトリックによって定義されます。このメトリックは、ピアの一意のPeerIDとデータのコンテンツ識別子（CID）のIDに対してビットごとのXOR操作を実行することで、それらの間の距離を計算します。 ハードコードされたブートストラップピアのセットから開始して、ノードはローカルルーティングテーブルを埋めます。これらの20の最も近いピアを見つけるプロセスはDHTウォークとして知られています。これは反復的な検索であり、ノードはローカルルーティングテーブルで最も近い既知のピアをクエリし、さらに近い候補を求めます。このサイクルは、イニシエーターが発見した3つの最も近いピアから成功した応答を受け取るまで続きます。ウォークが終了すると、フォローアップフェーズが開始されます。イニシエーターは、一部のノードがネットワークから離脱してもデータの可用性を確保するために、プロバイダーレコードをこれら20の最も近いピアすべてにプッシュします。したがって、結論として、プロバイドプロセスは2つのフェーズで構成されます。 DHTウォーク ネットワーク全体で20の最も近いピアを見つける フォローアップ これら20のピアにレコードをプッシュする パフォーマンスのボトルネック このシステムは堅牢ですが、歴史的に遅く、完了までに数十秒、あるいは数分かかることもありました。ProbeLabの研究では、主要な遅延はDHTウォークの終了条件であることが特定されました。「従来の」アルゴリズムは厳格です。DHTウォークフェーズ中に、発見された3つの最も近いピアからの応答を待つことに固執します。ピアが頻繁に入れ替わるパーミッションレスネットワークでは、これらの特定のピアはしばしば到達不能です。システムはその後、「バックトラック」し、ギャップを埋めるためにより遠いピアをクエリしますが、実際の20の最も近いピアはすでに発見されているかもしれません。 下のグラフは、これまで最速の地域であったヨーロッパからのプロバイド操作の合計期間の累積分布関数を示しています。元のグラフはこちらで見ることができます。グラフは、中央値のレイテンシが約20秒であり、最悪の場合、単一のプロバイド操作に2分以上かかることを示しています。このパフォーマンス特性は、遅延に敏感なアプリケーションにとって阻害要因であり、これがOptimistic Provideで対処しようとしたことです。 Optimistic Provide Optimistic Provideは、厳格な待機を統計的なヒューリスティクスに置き換えることで、遅いプロバイド操作に対処します。Kubo v0.39.0以降、これはデフォルトの動作となり、3つの主要なメカニズムを通じて秒以下のレコードストレージを可能にします。 ネットワークサイズ推定：個々のノードは、軽量でバイアス補正された近接モデルを使用して、グローバルネットワークサイズをローカルで推定するようになりました。 予測的終了：DHTウォーク中に、イニシエーターはネットワークサイズ推定を使用して、個々のピアとその現在の最も近いピアのセットが「十分に近く」である確率を計算します。ネットワーク全体で20の最も近いピアの1つを発見したと90%確信すると、すぐにレコードを保存します。ターゲットセットを見つけたと90%確信すると、ウォークをすぐに終了します。 早期リターン：フォローアップフェーズでは、20のピアのサブセット（例：15）がストレージを確認するとすぐに、システムはユーザーに制御を返します。残りの5つのリクエストはバックグラウンドで非同期に続行され、ユーザーを待たせることなくレコードが完全に複製されます。 ネットワークサイズ推定 ネットワークサイズ推定を導き出すための一見直感的な解決策は、ネットワーク全体をクロールして参加ピアの数を導き出すことかもしれません。しかし、このアプローチは、それが導入する過剰なオーバーヘッドのために非現実的であることが判明します。タスクを情報の共有を行うピアのサブセットに分散させるには、彼らの誠実さに対する信頼が必要であり、これはパーミッションレスネットワークでは困難な提案です。代わりに、ノードがすでに収集しているデータに便乗する軽量な推定アルゴリズムを設計しました。これにより、追加のネットワークオーバーヘッドはゼロになります。それはルーティングテーブルのリフレッシュです。 リフレッシュ中に、ノードは維持している各バケットのランダムなキーをルックアップします。Kuboの場合、これは16回のルックアップとノード自身のIDを意味します。各ルックアップは、ランダムなターゲットキーに最も近いネットワーク全体のピアを返します。したがって、単一のリフレッシュラウンドは、異なるスケールでキー空間にまたがるピア距離のサンプルを自然に生成します。核となる洞察は、ピアIDが均一に分布していると仮定すると、任意のキーに最も近い20のピアの距離は予測可能な統計的分布、具体的には順序統計のベータ分布に従うということです（この素晴らしいブログ記事を参照）。これにより、ルックアップ結果の各ピアを独立したネットワークサイズ推定値として扱うことができます。したがって、単一のルックアップが20のピアを返すと、キー空間の密度のみを考慮した場合の1つではなく、20の推定値が得られ、数回のルックアップで平均化することで、Nebulaクローラーからの真のカウントに対して良好な結果が得られます。1つの複雑な点があります。ルーティングテーブルのリフレッシュメカニズムが行うように、自身のキー空間の近傍内でクエリすると、密度バイアスが発生します。密なキー空間領域に位置するピアは、グローバルネットワークサイズを過大評価します。疎な領域に位置するピアは、過小評価します。当社のバイアス補正は、非満杯バケットからのデータポイントを指数関数的に重み付けを減らすことでこれに対処します。直感的には、満杯のバケットは、カバーされているキー空間領域が十分に密であることを示します。