グリッド協議会 第11回ワークショップ
2005年 2月 18日（土）

グリッドを支えるP2P技術
首藤 一幸
産業技術総合研究所 グリッド研究センター

内容
P2Pとは何か
グリッドに適用されるP2P技術
P2P分散処理ミドルウェア P3

P2P とは何かWhatʼs P2P ?
ネットワーク ソフトウェア
ファイル交換ソフトウェア ?
集中的なサーバが存在しないこと ?
非クライアントサーバ型 ?
…

明確な定義はなく、様々な主張がある。

P2P と呼ばれているシステムを概観してP2P とは何かを帰納的に考える。

P2P ファイル交換ソフトウェア
各種のファイルを、検索 & 入手、配布するためのソフトウェア


例: Napster, Gnutella, eDonkey, threedegrees, WinMX, Winny, …

末端（エンドユーザ）の PC 間でファイルを送受信する。

クライアント/サーバ

Hybrid P2P

Pure P2P

Webサーバなど
検索サーバ
ファイルの ファイルインデックス検索

転送

検索

ファイルのインデックス

転送

検索
ファイル

転送ファイル

P2P コンテンツ配信, ストリーミング
大容量ファイルや動画を配布/配信する仕掛け。


例: Kontiki社製品, ShareCast, BitTorrent, …

末端の PC が配信に協力する。

非 P2P
配信サーバ

コン
テンツ

P2P Content
DeliveryP2P Content Distribution
配信サーバ
コン
テンツ
(断片)

中継機器

配信Delivery

コン
テンツ
(断片)

コン
テンツ
(断片)

コン
テンツ

Distribution

P2P 分散コンピューティング
手持ちの計算機では足りないような大きな計算を行う。
計算プロジェクトの例: SETI@home, distributed.net
 ソフトウェアの例: United Devices社 Grid MP, Entropia社
DC Grid, BOINC, XtremWeb, …


末端の PC が計算やデータ保持を行う。
P2P 分散コンピューティング
タスク配布
サーバ

計算の内容
ワーカ

P3（産総研）

資源利用者

計算
結果
資源提供者

提供者、利用者の関係が固定的ではない。

P2P ミドルウェア
P2P ソフトウェアを構築するためのライブラリ、枠組。
ピア等の発見, ファイアウォール越しの通信, ピアグループの形成など
 例: JXTA, SOBA, Groove Development Kit, Advanced
Networking Pack for Windows XP, DECENTRA, …

JXTAが構成する
OverlayPeer ID

Peer ID

Overlay:
下位層の構造に縛られないネットワーク

Peer ID
Peer ID

Peer IDJXTA Virtual Network
Physical Network

Peer ID

Peer ID

Virtual Mapping

TCP/IP
NAT
FirewallHTTP

Peer ID

P2P ○○ いろいろ
P2P グループウェア

例: ifreestyle, Ariel AirOne, Groove

P2P 掲示板例: Winny, 新月

P2P Instant Messenger (IM)
例: threedegrees

P2P 電話

例: Skype

P2P

集中的なサーバが存在しない。
各ノードの役割が同じ。例えば、あるノードはサーバ/クライアント両方の役割を果たす。
厳しい

IRTF P2P Research Groupの憲章

システムの中で固定的なサーバを介さずにピア間で直接通信する場面があるシステム
日経バイト誌 2004年 8月号

末端の機器が重要な役割を果た
す分散システム

緩いPureHybrid
分散コンピューティング

では、P2P とは何か ?

P2P

P2P の性質
スケーラビリティが高い。


多くのノードをサポートできる。
 集中的なサーバが存在しない（pure P2P）か、サーバの負荷が軽減される（hybrid P2P）ため。
 ときに、数十万ノード以上。

耐故障性が高い。


一部のノードが落ちても、全体は落ちない。

集中的なサーバの管理コストが不要、または低い。
P2Pファイル共有と同じサービスを集中サーバで提供すると、数億ドル以上かかるという試算も。

利用の追跡/管理が困難。
集中サーバなしでの、全ノードを対象とした利用履歴の採取やアクセス制限は困難。
 場合や立場によって、利点であったり難点だったりする。
Peer-to-peer から P2P へ“Peer-to-peer”


遅くとも 1980年代には使われていた言葉。
 cf. UUCP を用いた USENET (1979年)
 cf. Macintosh の LocalTalk“P2P”
2000年前後に産み出された言葉。
 ウェブの反動 ?
 ダムクライアントであるウェブブラウザ


社会的意義

「P2P」の社会的意義
技術的な性質社会的な意義末端ノード間の直接通信

人と人を直接結びつける
技術 (P2P: person-to-person説)

末端ノードが重要な役割を果たす

個人中心の社会各ノードの役割が同じ階層的ではなくフラットな個人間ネットワーク「P2P」には、暗に社会的な期待が込められていることが多い。

グリッドに適用されるP2P技術

Grid と P2P の関係・相乗作用
極めて直観的

広域分散システム

これまであったアクティビティ

一般的、概念的な議論
アクティビティ、プロジェクト紹介
要素技術の特性・応用可能性
比較

GGF9 workshop（2003年 10月）

Peer-to-Peer and Grids: Synergies and Opportunities
http://www-csag.ucsd.edu/P2P-Grid/

APAN and Internet2 joint meeting（2004年 1月）


P2P and GRID: Convergence and Challenges
http://apan.net/meetings/honolulu2004/ws-application.htm#appl3

ここでは、Grid/P2P 連係の具体例を概観し、連係パターンを抽出する。

Grid / P2P 要素技術
P2P 技術とその性質


ノードその他資源の 発見 (discovery) 分散ハッシュテーブル(DHT), ピアのクラスタリング

オーバレイ (overlay) ピアの論理 ID, NA(P)T 越え, マルチプロトコル

スケーラビリティ, 耐故障性, 低管理コスト, …

Grid 技術
資源の集約 (aggregation)
 資源 / 処理の割り当て
 スケジューリング、ジョブ投入

並列 / 分散処理
 PKI ベースに基づく 認証 / 権限付与
分類
P2P Grid, P2P 分散処理
P2P over Grid パターン
Grid over P2P パターンP2P Grid, P2P 分散処理
P2P 技術で計算機資源を集約し、分散処理。
例

P2Pミドルウェア JXTA上の分散処理ミドルウェア

 P3, JNGI

(XtremWeb, SETI@home, distributed.net, …)処理を投入

P2P 技術で集約

P2P over Grid パターン
Grid 技術で集約した計算機資源を、
P2P 技術で発見する。
例

Grid Information Service（例: Globus MDS）に P2P 技術を応用。
 P2P GIS（ISTI-CNR,イタリア）, GAIS（韓国）, 他

Sun ONE Grid Engine (SGE) + JXTAP2P 技術で発見

発見
PCクラスタ等

Grid 技術で集約（クラスタ技術で集約 &グリッド技術で expose）

Grid over P2P パターン
P2P 技術で集約した計算機資源に対して、Grid 技術で処理を割り当てる。


Grid 技術で、安全に、複数資源にまたがって…等

例United Devices社 Grid MP + Globus Toolkit

Grid 技術で処理を割り当て
P2P 技術で集約

ジョブ投入

組織内、インターネット上のPC群

整理

通常の Grid

P2P over Grid
パターン

資源の発見
資源のexpose, 処理の割り当て
資源の集約

目的

Grid over P2P
パターン

GridP2P
GridCluster

P2P

技術

他の分類法は？
他の連係パターンは？ 要素技術の適用法は？
新たな連係パターンによる新たな価値？

P2P分散処理ミドルウェア P3

P3: Personal Power Plant
分散計算ミドルウェア


従来的な目標 Cycle scavenging


組織内の既存PCの計算能力をかき集める。

 インターネット上

分散コンピューティング

例: distributed.net, SETI@home

伝統的なインターネット上
分散コンピューティング将来 多数のPCを集約して、グリッド上の資源として見せる。


グリッドミドルウェアとの連携？
cf. Community Scheduler Framework

 計算機資源の取引・流通
個人の資源（C2C, C2B）、組織の資源（B2B） 計算能力以外の資源
 商取引のための市場と、それを支えるソフトウェアシステム


計算機資源の授受と集約

分散処理を支援するP2P技術

www.jxta.org

P3はあらゆる通信にJXTAを使用。
JXTA: P2Pソフトウェアに共通する機能を提供するプロトコル、参照実装（Java,C）、プロジェクト。


様々なアプリケーション、再利用可能サービスが実装されている。jxta.org上に数十のプロジェクト。
 コラボレーション: MyJXTA2, JXCube, …
 分散処理: JNGI, P3
 ファイル共有, ストリーミング, ゲーム, …



携帯電話機（J2ME）向け実装もある。
APIが、2001年末の時点でほぼ固定されている。

語源は “Jxtapose”（並置する）


Client-serverといった既存モデルと並存。別に競合するわけではない。

2001年 4月 25日、Sun Microsystems社からアナウンス
オープンソースコミュニティApache Software License 1.1ほとんどそのままのライセンス条文…@jxta.orgの登録者は焼く17,000名（2004年 4月）
ダウンロード数 200万以上（2003年12月）

P3が利用するJXTAの諸機能
アドホックなピア組織化（ad-hoc self-organization）


事前設定なしに、発見、通信が可能。

発見（discovery）


PCや投入されたジョブは、PCによって動的に発見される。

ピアグループ（peer group）


ジョブごとにピアグループが作られる。その中で、コードの配布、ジョブの実行制御、並列処理のためのグループ通信が行われる。

オーバレイ（overlay）
ピアには、下位ネットワークの構造と独立のピアIDが付与される。
cf. IPアドレスやMACアドレス
 NA(P)T越え、（一方向HTTPの）ファイアウォール越え これによってメッセージパッシング型の並列処理も可能となる。
cf. マスタ-ワーカ型
JXTAの強み
スケーラビリティ
具体的な目標が設定されている：
1,500,000ピア中 300,000ピアがアクティブ
 JXTAが良くなると、その恩恵を受けられる。
事前の設定が不要

他のピアやジョブは、動的に発見できる。
マルチキャストドメイン（サブネット）を越えるためには、外のピアを指定する必要があるが、ごく容易。マウスクリック程度で済む。

マルチプロトコル
下位プロトコルとしてTCP, HTTP, IPマルチキャス
トをサポート。自動的に使い分け。
 Bluetooth等、他のネットワークも使い得る。
要件
アプリケーション中立
従来のインターネット上分散処理プロジェクトでは、少数のアプリケーションがソフトウェアに組み込まれていた。
 P3では、アプリケーションはミドルウェア（P3）とは独立。
求まった アプリケーションは、後からPC群に投入する。

蛋白質の立体構造

実用的研究 + 実用ソフトウェア開発
 アプリケーションを載せることで、実用性を確認して、開発にフィードバック。
 蛋白質の立体構造決定アプリを実装。
スケーラブル
これまで、〜三十数台で試験。
 スケーラビリティを制限し得る箇所を対象に、試験＆改善をしている。
 例: マスタ・ワーカ型並列処理での、マスタの処理効率

要件
PC提供者によるアプリケーションの選択
計算機を提供する側で、ジョブを選ぶことができるべき。
 従来の分散処理プロジェクトでは、選択の余地がなかった。
 P3では、PC提供者は（ジョブの署名を検証した後）その計算を行うか否かを決められる。
インターネット上、組織内の双方への対応

インターネット上では、悪意あるPC提供者の存在を想定する必要あり。
 計算完了を装う。嘘の結果を返す。サービス不能攻撃をしかける。等。
P3では、計算結果を検証可能。
 投票方式: 同一の計算を複数のPCに依頼して、結果を照合。
 この検証機能は無効化できる。組織内向け。
 検証ロジックを差し替えることも可能。

要件
容易なインストールと自動更新

PCへのインストール、更新の手間は、台数に比例して増える。
 1台3分だとしても、20台で1時間。100台では…
 セキュリティホールが発見されたら…
多くのPCが対応されず、放置されるだろう。
 2003年 4月、SETI@homeのクライアントソフトにセキュリティホールが発見された。
 どのくらいのPCが危険なまま放置されただろうか？


P3の場合
 マウス数クリックでのインストール /新版への自動更新
 手段: Java Web Start (JWS)P3の設計
3つのサブシステム
ジョブ管理ソフトウェア
Host: 計算PCで動作させておくデーモン
 Controller: ジョブを投入するツール並列プログラミングライブラリ
マスタ・ワーカ ライブラリ メッセージパッシング ライブラリ cf. MPI

エミュレータ 1台上で並列アプリケーションを動作

ジョブモニタジョブ、ホストの状態を表示。
 ウェブブラウザで閲覧する。
ジョブ管理:Controller
計算を行いたい利用者が、これを使ってジョブを投入する。

参加しているPC

投入されているジョブジョブ管理:

Host
計算を行うPC上で動作させておくデーモン。
GUI（ウィンドウ）なしでも動作可能。
その場合Hostは、設定したポリシーに応じて、ジョブへの参加/不参加を決める。
複数のジョブを並行して実行可能。

発見したジョブ

ジョブからの出力内容

ジョブモニタ
ウェブブラウザ

Total view

処理したワークユニット数

ワークユニット:
マスタ・ワーカ型
並列処理でのワーカへの処理配布単位

処理速度

Host viewジョブモニタ

Host Information

Job Information

ピアグループの活用方法
Net Peer Group


Host

Host

Base PeerGroup


Host
Host
HostController
Job Peer GroupController

Job Peer Group

Base Peer Group
Controller

Host

Net Peer Group(always existing JXTA’s base group)

P3のピアグループ
PCやジョブの発見が行われる。

Job Peer GroupJob Peer GroupJXTAでは常に存在するジョブごとに作られるピアグループジョブ制御や、並列処理のための通信が行われる。

並列プログラミングライブラリ
主なもの
マスタ・ワーカ メッセージパッシング
cf. MPI

エミュレータ
1台上で並列アプリを動作させる。
 アプリの開発・デバッグに非常に有用。
 マスタ・ワーカライブラリも、エミュレータ上で開発された。
アプリケーション

マスタ・ワーカ API
マスタ・ワーカ
ライブラリ
オブジェクトパッシング
エミュレータアプリケーション

メッセージパッシング API
メッセージパッシング
ライブラリ

他のライブラリ

オブジェクトパッシング
ライブラリ

JXTA

性能測定
JXTAは便利だけれど、遅いんじゃないの？


確かに、速くない。けれど、たいてい充分。

性能測定


通信性能
 遅延とスループット



アプリケーション RC5暗号化鍵の総当たり探索 cf. distributed.net

環境
2.4 GHz Xeon PC、Gigabit Ethernet
 Linux 2.4.19, Java 2 SDK 1.4.2, JXTA 2.1
 インターネットと比べてネットワークが太い。
しかしそれだけ、P3自体の限界が顕れる。
通信の遅延1バイトのピンポン。
片道あたり
TCP (in C)
0.062 ミリ秒
 TCP (in Java)
0.064 ミリ秒
 P3のメッセージパッシング 4.5 ミリ秒


速くない
マスタ・ワーカ型アプリでは、単位時間あたりのワークユニット処理性能を制限し得る。
 しかし、たいていの用途には充分。
 そもそも、ワークユニット1つの処理時間を数秒以上に調整すれば、数ミリ秒は問題とならない。



そうは言っても、JXTAの改善が望まれる。

通信のスループット
メッセージパッシング ライブラリを使用。
およそ 100 Mbps (100 x 10 ** 6 bps)

ギガビットイーサネット上にしては速くないが、この先数年のインターネット接続（ex. FTTH）を埋めるくらいの性能はある。

メッセージサイズが巨大（512KB〜）になると、スループットが低下している。
本来は分割すべき。
100 Mbps

1210.97 MB/s
10Throughput（MB/s）JXTA-MPI
10 x 10**6 bps

8100 x 10**6 bps
64

2012481632

64

Data size（KB）

128

256

5121024

アプリケーションでの性能
小さなワークユニットに対する耐性試験。
RC5共通鍵暗号方式の暗号化鍵を総当たり探索。
 RSA社RC5 Challengeに参加しているdistributed.netと同じ。



1.0E1 秒前後の粒度、数十台のPCという条件には充分耐えた。

32

ワークユニットの粒度:# of keys a workunit: 0x8000

280x8000 : 1.4秒
 0x4000 : 0.69秒
 0x2000 : 0.36秒
# of keys a workunit: 0x4000# of keys a workunit: 0x2000

24

Speedup Ratio

Ideal Speedup

201612840048121620

Number of Workers

242832

インターネット上分散処理
では、通常は数分以上に設定される。

関連アクティビティ
JNGI


Sun Microsystemsが開発
JXTAを使用
ピアグループの使い方が、P3とは異なる。
 計算を行うピアのグループをいくつか事前に作っておく。ピアの効率的な管理が目的？


計算PCはジョブを選べない。
cf. P3はジョブごとにピアグループを作り、計算PC（Host）側でジョブを選べる。

XtremWeb, GreenTea, Javelin, Bayanihan, Ninflet, …


それぞれの強みがある。
計算PC側でアプリケーションを選べない。
プログラミングモデルが、マスタ・ワーカや分割統治に限定されている。
ファイアウォール/NA(P)T越えができない。
 Java RMIやTCPをそのまま使うため

悪意のあるPCを考慮していない。（か、対応状況不明）

BOINC, United Devices社Grid MP, Entropia社DC Grid

略現状と今後の計画
オープンソース化が完了
http://p-three.sf.net/
 ライセンスは Apache License 2.0 BSDライセンス的で、かなり制約が少ない。
2004年 9月公開。

研究・試験


分散ストレージとの組み合わせ(by INRIA)

アプリケーションを載せていく

アプリケーションホスト環境として(by 阪大 and NICT)