P2P
\( \def\vector#1{\boldsymbol{#1}} \)

Peer to Peer

Takami Torao #P2P
  • このエントリーをはてなブックマークに追加

概要

P2P (peer to peer) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。従来のクライアント/サーバシステム (C/S システム) におけるサーバがクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P ではそれぞれのピアが状況に応じてサーバとクライアント両方の役割を持つ。

一般に使われている P2P という言葉には解釈の幅がある。狭義では「手元のコンシューマ向け PC を使って一般ユーザが参加できる相互接続ネットワーク」を前提としていることもあれば、広義では、インターネット初期の Usenet (1979) やメールリレーから現代の CDN に至るまで、分散システムの中でも対等なノードが相互にメッセージを交換するネットワークを含めることもある。

P2P ファイル共有

P2P ファイル共有は P2P ネットワーク技術を使用したファイルの配布と共有を行うサービス、アプリケーションまたはネットワーク。ダウンロードのネットワーク負荷をユーザ側で分散することから低コストでサービスを運営することができるが、一方で、データの管理を行うことができず、著作権管理や情報漏えいと言った法的な問題に巻き込まれることも多い。…

2020年7月28日(Tue) #P2P

分散ハッシュテーブル

分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。…

2020年7月21日(Tue) #P2P #DHT #DOLR #Tapestry

Table of Contents

  1. 概要
  2. 沿革
  3. P2P ネットワークの特徴
    1. 非 P2P ネットワークとの比較
    2. P2P ネットワークの分類
      1. ハイブリッド P2P
      2. ピュア P2P
      3. スーパーピア P2P
  4. P2P ネットワーク構造
    1. ランダムグラフ
      1. Flooding 探索
      2. ランダムウォーク探索
      3. 応答経路でのキャッシュ
    2. 分散ハッシュテーブル [under construction]
  5. 参考リンク

沿革

P2P が世間に認知されたのは 1999 年から 2003 年にかけての P2P 技術を使ったファイル共有が世界的な話題となったときからである。当時のサーバ環境1は極めて非力であったため、ダウンロードサイトのように大きなデータが一極集中するサービスの運営には膨大なコストが必要だった。そのような情勢で P2P 技術を使用して負荷の高い音楽ファイルのみをユーザ間で交換できる Napster は非常に野心的な試みであった。

Napster の話題性に乗って Gnutella や WinMX といった P2P 技術を使用したユーザ間のファイル共有ネットワークが乱立した。しかし同時にそれらは著作権法違反、個人情報の暴露、政府機関や企業情報の漏洩、ウイルスの拡散といったさまざまな問題を社会に露呈した。特に Napster や WinMX は運営主体が「音楽メディアの共有」という比較的明確な違法性を掲げていたことから司法によりサービス停止を余儀なくされた。一方で Gnutella のように運営主体が明確でないもの2はいくつかの点で違法性が問われはしたが存続した。

このようなファイル共有分野におけるアンダーグラウンドなイメージや、挑発的とも言える態度の反発で一時は世間から黙殺されていたものの、P2P の基礎となる技術や考え方は 2010 年以降の分散データストア (いわゆる NoSQL) やコンテナ技術、クラウドコンピューティングなどに取り入れられていった。

201x 年代前半の Bitcoin 高騰を皮切りに電子表現された通貨が P2P で交換できる暗号通貨のブームが起きて再び P2P が脚光を浴びることになった。ここでは、金融取引のような一貫性を必須とする処理には向かない考えられていた P2P ネットワークに (確率的ではあるが実用上は問題ない程度に収束する) 一貫性をもたらすブロックチェーン技術が注目を浴びた。

  • 1当時の標準構成のサーバ機で Pentium III Xeon 550MHz, メモリ 256MB, 100BASE-TX 程度。一般のユーザは ADSL が普及する前で、64kbps ISDN や 56kbps ダイヤルアップ接続でインターネットに接続していた。
  • 2当時 Unix 系 OS や GNU のようなフリーソフトウェアは大学や研究機関にミラーされた FTP サイトで配布されていたが Gnutella はそのような巨大なファイルを配布する FTP サイトの代替として受け入れられた。

P2P ネットワークの特徴

沿革で述べたように 2000 年前後の P2P ブーム当時はまだサーバもネットワークも極めて非力1であり、クラウドは存在せず分散システム構成も非常に高コストであった時代背景がある。このため、当時の書籍などから得られる言説や比較説明などは現代においては不適切であったり意味のないものとなっていることが多い。この記事を執筆するために調べていてそれを強く感じたことから、ここではなるべく現在の情勢と合うように言い換えを行っている。

非 P2P ネットワークとの比較

旧来のクライアント/サーバモデルと P2P ネットワークという区分けは、対象とする問題の説明や論議のために極端に単純化されたモデルであることに注意しなければならない。現代の分散システムの選択肢はそれら両方の要素が混在しうる。そして、それらの特徴的と言われる相違のいくつかは CAP 定理で言うところの CA と AP の違いで説明する方が適切である。

Consistent - Availability Availability - Partition Tolerance
ネットワーク Hub and Spoke 型 (スター型) メッシュ型
インタラクション クライアントは管理された固定個数のサーバと接続してサービスを得る。 ピアが相互に接続して情報の交換を行う。
スケーラビリティ システムの利用量が急増すると特定のサーバやネットワークに負荷が集中しやすい※1。 サーバ機能を各ノードが分散するため利用量の急増にも耐えられる。
障害耐性 サーバやサーバ周辺のネットワークが停止するとシステム全体が利用できなくなる※1。 一部のノードが停止したりネットワークが分断されてもサービスを継続することができる。
一貫性 処理結果に一貫性をもたせることができる。 分散したデータを短時間で同期させることが困難※2。
管理性 常に駆動状況を把握でき容量設計や構成変更も容易。 データ配置やノードの駆動状況を把握できる部分がない。
応答性 データやそのインデックスはサーバに存在するため効率的。 分散したデータの探索に時間がかかり非効率的。
Table 1. クライアント/サーバ構成のネットワーク (左) と Peer to Peer 構成のネットワーク (右)。

多くの P2P ネットワークは一度運用を開始するとシステム全体を停止することが困難である。ソフトウェアの設定やバージョンアップはノードの所有者個別の判断によって行われるものであり、その歩調を合わせるためにコミュニティを運営しガバナンスを機能させる必要が出てくる (個人的に、脱中央集権と担ぎ上げた P2P の行きつく先は共産主義政府であると言っているところでもある)。

データがネットワーク上に分散していることから、情報に生じた更新を短時間のうちに他の情報と同期させなければならないような用途には向かない。そして REST API のように粒度の高いリクエストを高速に処理するような用途には難しい。巨大なデータのやり取りによってゆっくりとした動作が問題とならないファイル共有は P2P にフィットする用途といえる。

  • ※1現在では負荷の集中する部分に分散システムを導入したりクラウド化でデータセンター規模の分散を構成することが容易であるため、スケーラビリティや障害耐性の観点での P2P の優位性はなくなっている。
  • ※2ブロックチェーンの導入により (リソース条件は厳しいが) P2P ネットワークでも一貫性を利用できるようになった。

P2P ネットワークの分類

ハイブリッド P2P

P2P ネットワークの中でもネットワークを構成するノードの一部が特権的な役割を持つネットワークをハイブリッド P2Pと呼ぶ。一貫性や即応性が必要な一部の機能を中央サーバ化することで、クライアント/サーバモデルと P2P のメリット (またデメリットも) が共存するようになる。

Fig 1. 初期のハイブリッド P2P ネットワーク。中央サーバがクエリーを処理しファイルはユーザ間で交換する。

初期の Napster や WinMX はオブジェクトのロケーションやノードのアドレスといったメタ情報を管理する中央サーバが存在し、音楽ファイルなどの大きなデータはユーザ間で直接交換する設計となっている。

分散データストアでは Master Node や Region Server がメタ情報を管理し Data Node 間で実データを分配する Hadoop や HBase はハイブリッド P2P と似た目的を意図する構成である。

ピュア P2P

すべてのノードが対等であり特権的な役割を持つノードが存在しない P2P ネットワークをハイブリッド P2P に対してピュア P2P と呼ぶ。ただし、ランダムグラフのように完全に何の前提も置かないネットワーク構造は極めて非効率であり貧弱な機能しか実装できないことから、一般に分散ハッシュテーブルやスーパーピアに似た役割となるような機構を持つ。

Fig 2. ピュア P2P。

スーパーピア P2P

P2P ネットワーク上の高性能で安定駆動しているノードがスーパーピアまたはスーパーノードとなり、他のノードより多くのデータをキャッシュしたりインデックスを分散保持するように偏重するネットワークをスーパーピア P2P と呼ぶことがある (サービス運用者がスーパーピアを用意することもある)。

Fig 3. スーパーピア P2P。

FastTrack (KaZaA) や Skype のスーパーピアはデータのインデックスを分散して保持する。Winny や BitTorrent は転送経路が高性能なノードを経由することでスーパーピアに相当するノードに多くのキャッシュが集まるように設計されている。

P2P ネットワーク構造

既存のネットワーク上に別の概念で構築された上位のネットワーク構造をオーバーレイネットワーク (overlay network) と呼ぶ。ただし、今の分散システムや P2P ネットワークはほぼすべて IP (TCP または UDP) 上に構築されているオーバーレイネットワークであるため、あえてオーバーレイであることを主張する必要性は現在はない。

また、特定のトポロジー構造を前提とするネットワークを構造化オーバーレイネットワーク (structured overlay network)、特定のトポロジー構造を前提としないネットワークを非構造化オーバーレイネットワーク (unstructured overlay network) と分類する慣習があるが、これらは実質的にランダムグラフを前提とするか分散ハッシュテーブル (またはその他の構造化アルゴリズム) を前提とするかの違いでしかないため、歴史的に使われた言葉としての紹介に留める。

ランダムグラフ

ランダムグラフを前提とする P2P ネットワークモデルはグラフ理論や複雑ネットワークによって特徴づけられるグラフ構造。各ノードは頂点 (vertex) として表されるのみで、役割や機能はすべて同じであり、自分と隣接するノードとのみメッセージを交換する。グラフ理論の観点での議論に加えて以下の機能が論点となる。

  1. クエリー: 目的のオブジェクトを持つノードを検索する方法。
  2. ルーティング: 目的のノードへのメッセージ伝達経路の決定方法。
  3. キャッシュ: よく参照されるオブジェクトを効率的に拡散する方法。
  4. 自己再構築: ネットワークがより効率的な構造に自然と収束する方法。

ランダムグラフの考え方は P2P として直感的で実装も比較的容易である。しかし実用面においてはその単純さから生じる非効率性によってパフォーマンスやスケーラビリティに大きな欠点を持っている。現代的な分散システムに適用可能な部分は gossipping を使ってすべてのノードに同じデータを拡散するようなユースケースだけである。これは例えば DNS のキャッシュのようなものが該当する。

Flooding 探索

ランダムグラフは一般にオブジェクトのロケーションを管理していない。このような状況ではクエリーをネットワーク全体に伝播させる Flooding または Gossipping という方法が取られる。

Fig 4. あるノードから発行されたクエリーが 4 ホップ目で伝播する距離。

ネットワークの全ノード数を \(n\) としたとき Flooding は \(O(\log n)\) ホップですべてのノードに到達するため通信複雑性は高くないが、本質的にそのほとんどが無駄でありネットワーク全体に高負荷がかかる操作である3。目的のオブジェクトが見つかった後でもネットワーク全体にクエリーが伝播され続けることを防ぐためメッセージには TTL (time to live) が設定される。

P2P ネットワークのクエリーは、目的のオブジェクトを見つけるか、すべてのノードに伝達されるか、または TTL の期限が切れるまでネットワークを伝播し続ける。小さな TTL で検索を開始してヒットがなければ TTL を増加して再発行するような反復深化深さ優先探索 (iterative deepening depth-first search) または拡大リング探索 (expanding ring search) という手法は、ネットワーク上に広くキャッシュが拡散していて見つかりやすいオブジェクトには特に効率的に機能する。

  • 3ピュア P2P はハイブリッド P2P より高いスケーラビリティを謳っていたが、Flooding に基づく初期の Gnutella は 200-300 程度のノード数でネットワークが飽和してしまいスケールしなかった。後に Gnutella はスーパーピア型 P2P に移行した。

ランダムウォーク探索

より緩慢なクエリーが許容できるケースであれば Flooding よりネットワーク負荷の低いランダムウォークが適していることもある。Fig 5 はランダムウォークで 3 つの方向に同じクエリーを送信している。

Fig 5. 3 方向に送信したクエリーがランダムウォークで 4 ホップ目で伝達した距離。

応答経路でのキャッシュ

クエリーに対する応答は要求を行ったノードに直接送信されることもあるが、グラフ上の経路をたどって送信することで、中継するノードがデータのコピーをキャッシュしよく参照されるデータが多くのノードにキャッシュされる。

Fig 6. 応答経路でキャッシュされるデータ。

分散ハッシュテーブル

ランダムグラフ以外では、目的とするオブジェクトを効率的に検索するために特定のスキームに基づいて P2P ネットワーク上にオブジェクトを配置する分散オブジェクトロケーション/ルーティング (DOLR; distributed (decentralized) object location and routing) と呼ばれる手法が取られる。ネットワークに特定の幾何学構造とルーティングメカニズムを追加することによってランダムグラフ (非構造化オーバーレイネットワーク) での制約に対処することを目的としている。

Consistent Hashingに基づいて分散ハッシュテーブルを構築する方法も DOLR の一つである。

参考リンク

  1. 滝沢誠、榎戸智也 (2014), 分散システム:P2Pモデル, コロナ社
  2. John Buford, Heather Yu, Eng Keong Lua. P2P Networking and Applications, Morgan Kaufmann; 1版 2008
  3. Andy Oram, "Peer-to-Peer: Harnessing the Power of Disruptive Technologies", O'Reilly Media (2001) - 1998-2001 年にかけての P2P ブームで起きた技術を広く説明している内容。Bitcoin やブロックチェーン前夜とも言える P2P マイクロペイメントの議論や、暗号通信 Tor のベースとなる onion routing などが詳述されている。