【ITニュース解説】The Hard Part Was Finding the File: Rethinking Distributed Computing #2

システムエンジニアを目指す初心者の皆さん、今回は分散コンピューティング、特にピアツーピア（P2P）システムがどのように進化してきたかについて解説する。P2Pシステムは、巨大なサーバーを介さず、ユーザー同士が直接ファイルを共有するシンプルなアイデアから始まった。例えば、アリスが持っているファイルをボブが欲しがるとき、中央のサーバーを介さずにボブがアリスから直接ダウンロードできる仕組みだ。これにより、各参加者がクライアントとサーバーの両方の役割を担い、ネットワークの端にあるマシンが資源を提供するインフラの一部となる。

このP2Pの魅力は、全てのファイルを一箇所に保存する中央サーバーが不要である点にある。参加者が増えるにつれてストレージ容量も増え、ネットワーク資源も参加者自身によって提供されるため、システムは一台の中央マシンでは対応しきれないほど大規模に成長する可能性を秘めている。

しかし、ここで一つの重要な問題が浮上する。ボブが「目的のファイルを持っているピアはどこか？」と尋ねる瞬間だ。ファイル転送そのものは比較的容易だが、ファイルの場所を見つける「ルックアップ（探索）」こそが、P2Pシステムにおける最も困難な課題となるのだ。

P2Pシステムは、基本的に「参加：どうすればシステムに参加できるか」「公開：持っているファイルをどうやって他のピアに知らせるか」「検索：欲しいファイルをどうやって見つけるか」「取得：どうやってファイルを受け取るか」という四つの質問に答えなければならない。この中で「取得」は相手の場所が分かれば直接接続して転送できるため比較的簡単だが、その手前で「欲しいもの」と「それを持っているピア」を結びつける「検索」が厄介な問題となる。ピアはデータセンターに常駐する信頼性の高いサーバーとは異なり、自由に参加したり離脱したり、IPアドレスが変わったり、警告なしに消えたりすることが頻繁に起こる不安定な存在だからだ。数百万のファイルが、ネットワークのごく一部しか知らない無数のマシンに分散している中で、効率的な検索メカニズムが必要となる。

最初の解決策として登場したのがNapsterのアプローチだった。Napsterは、ファイル自体はユーザーのマシンに置いたまま、どのピアがどのファイルを持っているかという情報だけを中央ディレクトリで管理した。ピアが接続すると、自分のIPアドレスと共有ファイルを中央サービスに報告し、検索は全てその中央ディレクトリに対して行われた。そして、検索結果に基づいてファイル転送はピア間で直接行われたのだ。この方法は、データの保存を分散させつつ、データの場所に関する知識だけを中央に集約するという点で巧妙だった。検索は中央ディレクトリが答えを知っているため、ピアから見れば非常に高速かつ効率的だった。しかし、この中央ディレクトリはシステム全体の知識を持つ唯一のマシンとなり、システムの成長とともに膨大な情報処理と状態管理を担うことになった。もしこのディレクトリが利用不能になれば、ファイルが何千ものマシンに存在していても、ユーザーはそれらを見つける手段を失ってしまう。これは、データがどこにでも存在するのに、その地図が失われるという可用性の問題を生み出し、中央ディレクトリが性能上のボトルネックと単一障害点になってしまったのだ。

このNapsterの問題を解決するため、Gnutellaが登場した。Gnutellaは中央ディレクトリを完全に排除し、「どこにも全ての情報を持つマシンがないなら、隣のピアに聞いてみよう。知らなければ、さらにその隣に聞いてもらおう」というクエリフラッディングという手法を採用した。ピアは既存のピアを見つけて接続し、検索時にはクエリを隣接ピアに送信する。隣接ピアはさらに転送し、ファイルを持つピアが見つかれば結果を返す。これにより、Napsterのような中央集権的な依存関係はなくなり、検索処理はネットワーク全体に分散され、一台のピアが消失してもシステムは継続できるようになった。

しかし、Gnutellaのこの手法は別の問題を生み出した。アリスが何かを検索すると、クエリは多数の隣接ピアに転送され、それがさらに転送され、どんどん多くのピアに到達する。結果として、検索の範囲が最悪の場合、ネットワーク全体のピア数Nに比例するO(N)に近づき、Gnutellaのような大規模なP2Pネットワークでは膨大なメッセージトラフィックが発生することになった。分散化は中央のボトルネックを取り除いたが、中央サービスが行っていた「仕事」をなくしたわけではなく、それをネットワーク全体に分散させただけに過ぎなかったのだ。

このGnutellaの課題は、ネットワークにリソースとその場所を結びつける構造がほとんどないことに起因していた。アリスがファイルAを要求しても、クエリがネットワークの特定の部分に移動すべき必然的な理由はなく、ネットワークは「どこを探すべきか」を知らず、「誰に尋ねられるか」しか知らなかったのだ。

全てのピアを平等に扱うという考え方も、必ずしも効率的ではないことが分かってきた。例えばKaZaAのようなシステムでは、階層型クエリフラッディングというアプローチを採用し、「スーパーノード」を導入した。普通のピアはスーパーノードに接続し、自分のファイル情報をそこに公開する。検索はまずローカルのスーパーノードに行われ、もし答えが他のスーパーノードにある場合は、スーパーノード同士が連携して検索を行う。これは、一度排除した階層を部分的に再導入する試みであり、一部のピアがより大きな責任を担うことで、検索がより効率的に行われるようになったのだ。

BitTorrentのようなシステムは、ファイル共有の仕組みとして、異なるピアからファイルの異なる部分を同時にダウンロードする「スワーム」という概念を導入した。また、Freenetのような非構造化オーバーレイシステムは、単にクエリをフラッディングするのではなく、過去のリクエストから得た情報を使ってルーティングの意思決定を改善する「学習」の要素を取り入れた。これにより、クエリは必ずしも無作為にブロードキャストされるのではなく、より可能性の高いピアに転送されるようになった。しかし、これは経験則に基づいたものであり、リソース識別子とネットワーク内の特定の位置との間に全体的な関係があるわけではないため、ルーティングに強い予測可能性を与えるものではなかった。

そこで、P2Pシステムは根本的な発想の転換を図った。「ネットワークをどう検索するか」ではなく、「リソース自体がルーティング先を教えてくれるようにネットワークを組織できないか」という問いに変わったのだ。これが「分散ハッシュテーブル（DHT）」の概念だ。

DHTは、通常のハッシュテーブルのようにキーを与えると値が得られるという抽象化を、多くの独立したマシンに分散されたテーブルで実現しようとする。重要なのは、キー（リソースの識別子）とピア（ノードの識別子）が、定められたルールに従って共通の識別子空間に配置される点だ。これにより、リソースは単に名前を持つだけでなく、その識別子によって分散システム内のどの部分がそのリソースに責任を持つかが決まるようになる。ルックアップ問題は、ルーティング問題へと変化したのだ。

これにより、システムは任意のピアに「このリソースはどこにあるか知っているか？」と尋ねるのではなく、オーバーレイネットワークがリクエストをキーに関連付けられたピアへと段階的にルーティングしていくことが可能になった。この構造により、ルックアップがネットワーク全体へのフラッディングに頼るのではなく、決められた数のルーティングホップで完了できるようになる。この構造の維持には、ピアがルーティング情報を管理したり、参加や離脱に対応したりするコストがかかるが、その代償としてフラッディングでは得られなかった「予測可能性」が手に入る。

このDHTのアイデアを特に明快な形で実現したのが「Chord」である。Chordでは、ハッシュ関数を使ってキーとノードの両方に識別子を生成し、これらの識別子を円環状の同じ識別子空間に配置する。そして、あるキーの責任は、そのキーの識別子に続く最初のノードに割り当てられる。例えば、キー「60」を持つオブジェクトが必要な場合、システムは全てのピアに「60を持っているピアはいるか？」と尋ねるのではなく、識別子空間が「60」の責任を持つべきノードを教えてくれる。Chordの基本的なサービスは、キーが与えられたときに、そのキーをノードにマッピングすることに特化しており、ノードが参加したり離脱したりしても適応しながら、効率的なデータ位置特定というP2Pの核となる問題を解決する。

しかし、どの識別子がキーを所有すべきかを知ることと、そのノードに効率的に連絡する方法を知ることは同じではない。ここでChordはエンジニアリング上のトレードオフに直面する。

もし全てのChordノードが他の全てのノードのアドレスを知っていれば、ルックアップは簡単だ。キーをハッシュし、ローカルのルーティングテーブルで責任を持つノードを見つけ、直接そのノードに連絡すれば良い。これはネットワークホップ1回で完了するが、全てのピアがO(N)のルーティング状態（ネットワーク内の全ピアの数に比例する情報量）を維持しなければならず、非現実的だ。逆に、各ノードが円環上で自分に続く直近のピアのMアドレスだけを知っているとすれば、ルーティング状態は最小限になるが、遠くにあるキーを見つけるには、リング上を一つずつたどっていかなければならず、ルックアップには最悪の場合O(N)のメッセージが必要となる。これは遅すぎる。

そこでChordが採用したのが「フィンガーテーブル」だ。各ノードは、全てのピアを覚えるのではなく、識別子リング上で指数関数的に離れた位置にあるピアへの参照を保持する。つまり、近くのピア、少し遠いピア、もっと遠いピアといった具合に、戦略的に配置された少数のピアだけを知っているのだ。こうすることで、欲しいキーが遠くにある場合、現在のピアは目的のキーに最も近づくフィンガーを選んでリクエストを転送する。次のピアも同様に、一番効率の良いフィンガーを使ってリクエストをさらに転送していく。各ホップで残りの識別子空間の距離を大幅に短縮できるため、まるでバイナリサーチのように効率的に探索が進む。結果として、各ノードのルーティング状態はO(log N)に、そしてルックアップに必要なメッセージ数もO(log N)に削減される。これは、全てのピアを知るコストが大きすぎ、ごく一部しか知らないと遅すぎるという二つの極端な選択肢の間にある、非常にバランスの取れた解決策だ。フィンガーテーブルは、このトレードオフの中で「ちょうど十分な」構造を各ピアに持たせることで、検索空間を素早く絞り込むことを可能にしたのだ。

このようにP2Pシステムは進化してきた。Napsterは全てを知る中央の機械に尋ねることで高速かつシンプルだったが、集中型であった。Gnutellaは中央がなければ到達可能な全員に尋ねることで分散化したが、コストがかかりすぎた。階層型アプローチは、より能力のあるピアを優先することで実用性を増したが、それでも分散探索に大きく依存した。非構造化ルーティングは、ネットワークが学んだ知識を使って賢い推測をしたが、強い検索保証がなかった。そしてDHTは、リソースとピアに構造を与え、責任を持つ場所へとルーティングするという問題の形自体を変革した。Chordはそれをリング状の構造で実現し、各ノードに効率的にルーティングするための最小限の知識を持たせたのだ。

この進化の過程から学ぶべき重要な教訓は、分散化が構造の不在を意味するわけではないということだ。中央サーバーがない、階層がない、権威がないといった状態は、一見すると美しい分散型システムに思えるかもしれない。しかし、それはシステムが大規模にスケールするための良い保証とはならない。P2Pシステムは依然として、参加、公開、検索、取得のためのルールや、ピアの出入りへの対応、負荷分散、ノードの能力の不均一性への対処、そして何よりも、大規模になってもコストが破滅的に増大しないルックアップメカニズムを必要とする。

ここで重要な区別は、「中央集権型か、構造化されているか」ではなく、「中央集権的な権威か、分散された構造か」である。Chordは、中央ディレクトリがネットワーク全体を知る必要がないにもかかわらず、識別子空間、リソース配置、ルーティング、ルックアップといった全てに構造を持っている。

当初、私たちは地図を一台のサーバーに置いた。次に、地図を捨てて大声で叫んだ。そして、部分的な地図を作り始めた。最終的には、発見を無制御な検索として扱うことをやめ、目的地に体系的に近づけるようにネットワークを設計したのだ。ファイルそのものが最も難しい部分だったことは一度もなく、常に「どこを探すべきか」を知ることが最も難しい問題だった。これは失敗ではなく、P2Pシステムの必然的な進化の道のりである。