Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

現代の世界を動かす広大で目に見えないインフラの中で、データはコンピュータのネットワークを通じて絶えず書き込まれ、保存され、取り出されています。これらのシステムは、個々のマシンが故障したり、クラッシュしたり、あるいは悪意のある攻撃者によって侵害されたりしても、情報を安全に保持できるほど堅牢でなければなりません。これを実現するために、エンジニアはしばしば単一のファイルを多くの断片に分割し、異なる場所に分散させる手法をとります。これは「情報の分散（information dispersal）」として知られる技術です。これにより、一部の断片が失われたとしても、残りの断片から元のファイルを再構成することが可能になります。しかし、長年の課題は、この保護にかかるコストとのバランスを取ることでした。データを安全に保存するには通常、追加のコピーを保持する必要があり、これは容量を消費します。一方で、壊れた断片を修正したり、利用のためにデータを移動させたりすることは、膨大な帯域幅を消費します。長年、最も効率的なデータ保存方法は、修復に時間がかかりコストがかかるものであり、一方で、壊れたノードを修正する最も速い方法は、ストレージ容量を非常に浪費するものでした。

研究者のトーマス・ローハーとイヴォンヌ＝アン・ピニョレは、このトレードオフを打破する新しい手法を開発しました。これは、情報の保存、分散、および回収のすべてにおいて、同時に効率的な方法を提供します。彼らの研究は、「非同期検証可能情報分散（asynchronous verifiable information dispersal）」と呼ばれる特定のタイプのシステムに焦点を当てています。これは、コンピュータが正しく機能するためにメッセージの正確なタイミングに合意する必要はないものの、保持しているデータが有効かつ一貫していることを検証できるシステムです。チームは、データをグリッドのような構造に整理する新しいプロトコルを導入しました。これにより、ノードはファイル全体をダウンロードすることなく、欠落した部分を再構成するために必要な最小限の情報だけを共有できるようになります。このアプローチは、データの保存量と、故障したコンピュータを修復するために必要な帯域幅の両方を大幅に削減すると同時に、情報が要求された際の取得に必要な速度も維持しています。

この新システムの核心は、データが送信される前にどのように配置されるかにあります。情報を単なる断片のリストとして扱うのではなく、研究者たちはそれを2次元の行列、つまり行と列のグリッドへとエンコードしました。データを、すべてのセルに元のファイルの一部が含まれている巨大なスプレッドシートだと想像してください。システムは、このグリッドの空のセルを埋めるための数学的プロセスを適用し、冗長性のネットワークを作り出します。ネットワーク内の各コンピュータには、このグリッドの特定の行と特定の列が割り当てられます。各コンピュータは、その行と列に属するデータと、そのデータが正しいことを検証するための小さな暗号学的証明のみを保持します。この構造こそが、システムの効率性の鍵です。すべてのコンピュータが他のすべてのコンピュータの行と列の断片を保持しているため、あるマシンが故障した場合、中央の権威に連絡したり、データセット全体をダウンロードしたりすることなく、互いに助け合って欠落した部分を埋めることができるのです。

新しいデータが保存される必要があるとき、プロセスはクライアントがネットワークに初期のグリッド情報を送ることから始まります。研究者たちは、これが迅速に行われ、帯域幅を無駄にしないように、巧妙なハンドシェイク・メカニズムを設計しました。クライアントは必要なデータを各コンピュータに送り、データが受信されたという確認を待ちます。もしコンピュータが応答しない場合、クライアントは単に全員にファイル全体を再送するのではなく、それらを必要とする特定のコンピュータに対してのみ、欠落した部分を含む小さく的を絞ったアップデートを送信します。ネットワーク内の他のコンピュータは、自身のストレージ内に欠落したデータの断片をすでに保持しているため、それらの断片を苦戦しているノードへと転送します。この協力的なステップにより、ネットワークは、以前の手法のように全員にコピーを確保するためにデータセット全体を何度も送信する必要がなくなり、はるかに少ない総データ移動量で保存プロセスを完了できます。

データの取得も同様に合理化されています。ユーザーがファイルを読み取りたいときは、十分な数のコンピュータに対してその行のデータを要求します。グリッドが構築された仕組みのおかげで、ユーザーはネットワーク内のすべてのノードに連絡することなく、これらの行から元のファイルを再構成できます。システムは、断片と共に保存されている暗号学的証明を使用してデータの完全性を検証し、破損した情報や悪意のある情報が返されないことを保証します。この取得プロセスは既存の最良の方法と同等に効率的であり、これは、他の改善を得るためにデータの読み取り速度が犠牲になっていないことを意味します。

おそらく最も重要な進歩は、コンピュータが故障した際の修復方法にあります。古いシステムでは、壊れたノードを置き換える際、新しいマシンが自身のシェアを再構築するためにネットワークからデータセット全体をダウンロードする必要があることが多く、これは大きなファイルの場合、数日間かかり、膨大な帯域幅を消費するプロセスでした。この新しいプロトコルでは、交換用のノードは、自身の特定の行と列のデータを回復するために、わずか数台の他のコンピュータに連絡するだけで済みます。隣接するノードは、新しいノードのグリッド上の位置と交差する小さな断片のみを送信します。新しいノードは、これらの断片を使用して、自身のフル・ストレージ・シェアを数学的に再構成します。これにより、修復中に転送されるデータ量が大幅に削減され、ノードが頻繁に参加したり離脱したりする大規模な実世界のアプリケーションにおいても、このシステムが実行可能になります。

研究者たちは、彼らのプロトコルを既存の標準と比較して分析し、あらゆる面で一貫してそれらを凌駕していることを見出しました。1ギガバイトのファイルを保存する100台のコンピュータのネットワークにおいて、彼らの手法では各ノードが保持するデータはわずか30メガバイトですが、主要な代替案では45メガバイトを必要とします。単一のファイルに対してはこの差は小さく見えるかもしれませんが、グローバルなネットワークにおけるペタバイト規模のデータにスケールさせた場合、これは総ストレージ要件の1.5ペタバイトの削減に相当します。同様に、ノードが故障した場合、新しいシステムでは修復のために45テラバイトのデータをダウンロードする必要がありますが、従来の最良の方法では75テラバイトが必要です。これにより30テラバイトのトラフィックが節約され、これはフルネットワーク容量において、不要となった約3日分の修復トラフィックに相当します。

チームはまた、ユーザーがニーズに基づいてシステムを調整できる、プロトコルのバリエーションも検討しました。単一のパラメータを調整することで、オペレーターは修復や取得のための帯域幅要件を多少犠牲にする代わりに、使用されるストレージ容量をさらに最小化することを選択できます。この柔軟性により、このプロトコルは、長期保存の効率を優先する分散型アーカイブから、高速なデータアクセスを必要とする高性能システムまで、幅広いシナリオに適応します。この研究は、単に一つの領域において理論的に最適であるだけでなく、データの書き込みから修復、取得に至るまでのライフサイクル全体において実用的に効率的な分散ストレージシステムを設計することが可能であることを示しています。

この研究は、その拡張性を制限してきたボトルネックに対処することで、次世代の分散ストレージシステムへの具体的な道筋を示しています。低いストレージオーバーヘッド、低い書き込み通信コスト、そして効率的なノード回復が共存できることを証明することで、著者らは、堅牢で分散型のデータネットワークの展開における大きな障壁を取り除きました。その結果は単なる理論的なものではありません。研究で導き出された具体的な定数は、運用コストとネットワーク容量の具体的な節約に直結します。分散型アーカイブやブロックチェーン・ソリューションのようなシステムが成長し続ける中で、信頼性を犠牲にすることなくデータを効率的に管理できるプロトコルはますます不可欠となり、この新しい手法はその未来に向けたバランスの取れた高性能な基盤を提供します。