2006-09-18

近況

第2回DHT勉強会 を見てきた. DHT は P2P 用語で Distributed Hath Table のこと. 去年も同じ主催者による P2P勉強会に 参加している. 我ながら野次馬だ.

以下メモ. 詳細は詳しいひとがどこかに書くと思うので主観駆動です.

"オーバレイ構築ツールキット Overlay Weaver" と DHT 入門講義

shudo.net のひとによる. Overlay Weaver (OW) というオーバーレイ・ネットワーク構築キットを作ったので試してね, という話... を期待していったのだけれど, その前の入門講義に時間を食われて肝心なところは スキップ気味だった. ちょっと残念. (でも入門は勉強になった.)

OW は 名前のとおり overlay network をつくるためのミドルウェアで, DHT 部分のアルゴリズムなど, 各レイヤが交換可能になのがミソ. アルゴリズムを交換して通信量やホップ数などのトレードオフを検証できるという. ルーティングの部分はアルゴリズムによっては数百行程度の Java で実装できるという話だった. 一体どういう抽象化がなされているのか, 詳しいところはよくわからない. API/コードを見ろということなんだろうね. コードは 3万数千行. 去年の 6 月に実装を始めて三ヶ月くらいでおおよそ実装, 1 月にリリースしたとのこと. スーパープログラマおそるべし.

可視化のデモが面白かった. スクリーンショット は 見たことがあったけれど, やっぱり動いてるのはいいね. (帰宅後手元でも動かしてみた. かっこいい...)

質疑では悪意を持ったノードや通信状況が悪いとき(ノードの入退が激しいとき)の シミュレーションについての質問があった. どちらも未対応/未実験とのこと.

"世界規模情報共有プラットフォームの実現に向けて"

自前の DHT 実装上で P2P の Web Browser 風アプリを作った話と, 様々な DHT 実装をエミュレートして実験, 比較した話. アプリの方はいまいちよくわからず. 実験の方は, 実際どうやって実験したのかの部分がよくわからなかったけれど, 実験結果が目をひいた.

発表者のつくった実験基盤をつかうと, 具体的な DHT 実装(コード)を使った実験ができるという. 理論上のアルゴリズムだけでなく実装までを含めたベンチマークができるのは面白い. たとえば Overlay Weaver だと, そのフレームワーク上で自らアルゴリズムを実装しなおして比較することになる. そうではなく, 実装そのもの を試したということらしい. (たぶん.) 私は専門家じゃないので, 結果で示された実装の優劣にはあまり興味がない. どちらかといと実験そのものに興味をひかれ, 理論値じゃなくて実装をもって比較するの意義を見直した. アルゴリズムのオーダーが同じなら, (実験でしかわからない)定数部分で大きく差がつくからね.

なお発表者の加藤さんの方法は他のものより通信量が少なく, 逆に Overlay Weaver はそれが大目という結果だった.

"P2Pエージェントプラットフォーム PIAX の理念と実装"

mobility とか agent とかいう言葉がとびかい, いかにも情報科学という感じの話だった.

それはさておき, このシステムでは DHT 相当の機能を実現するアルゴリズムに "Skip Graph" という方法を採用している. 発表者の吉田さんはこれを強く推していた. DHT と Skip Graph の違いは Java でいうと HashMap と TreeMap の違いようなもの だというのが私の解釈. たとえば, 値としてのキーの近さ ( ex. abs(key1 - key2)) ) と ネットワーク上でのノードの近さに相関がある. あとはキーを hash にせずそのまま使える. みんな Skip Graph 使おうぜ, というノリだった. (もうちょっと慎重な言い方でしたが.) モバイルのような位置情報が絡むシステムでは, 情報の "近さ" が重要な要素らしい. だから範囲検索ができる Skip Graph の性質が生きるわけね.

もう一つ面白かったのは, 一次元の値だけをキーにできる Skip Graph 上で どう二次元の位置 (緯度経度) をキーにするかという話. ヒルベルト曲線] で エンコードするらしい. かっこいいいーー!

この事実は発表後の質疑応答でぼそっと明らかになったのだが, むしろこれは大自慢ポイントじゃないの? ヒルベルト曲線を使った空間のエンコードは局所性を保存できて便利. そういう性質は, 以前 ヒルベルト曲線をラスタライズに使う話 で聞いていた. もしかしたら P2P 業界やネットワーク屋さんの間では当然なんだろうか. そもそも正しい計算機科学者の基礎知識なのかもしれない. 自分の無知軽薄にちょっとめげる. まあいいです...

"AsagumoWeb Web over P2P システムの設計と実装"

P2P のネットワーク上にウェブっぽいものを作りました, という話. localhost に P2P 世界への gateway して振る舞うノードがいて, そこにブラウザを繋いでつかう. 個人的にはこういう具体的なものを作った話が楽しい. 勢い余った感が面白かった.

技術的に面白かったのは, 動的なコンテンツを実現するために アプリケーションをダウンロードして gateway 内で実行するというアーキテクチャ. ダウンロードしてきたアプリケーションが ブラウザの中ではなくその一歩手間の gateway server で動くというのが ちょっと新しい気がする. まあ agent だと言ってしまえばそれまでだけど. 語感としての servlet はこういうものだよなと思った.

発表者は, もともとの動機として 資本のない個人で作ったサイトの人気が出てしまった時に負荷分散がしたいと話していた. それに対し, "採用しているプロトコルだとそういう負荷分散はできないのでは" と質疑でのツッコミが. 指摘どおりとのこと. なんてこったい...

"Chord プロトコルを活用したシステム開発の実際"

修士論文のために Chord の実装を使おうとしたら 腐りまくってて大変だったよまったく...という苦労話. 愚痴の内容がプログラマ的に面白かった. 発表者の藤田さんは割と年季の入ったかんじの UNIX ハカーなのだけれど, そんな人がハマるなんて手強いんだろうね.

彼の研究は P2P を使ったストレージを作ることらしい. その動機付けとして図書館学からの要請があるという話は面白かった. オンラインのデジタル資料すべてを数百年のオーダーで保存する, というのが 究極のゴールだという. そいつはなかなか...Google もびっくりの grand challenge だなあ. 官製検索エンジンを作る金はこっちに回した方がよさそうだ.

発表の中味とは全然関係ない話: 藤田という人は絵に描いたようなおっさんプログラマで, 妙にかっこよかったというか, おっさんになってもプログラマでいるというのはこういう感じなんだなと思った. (良い意味で.) ぐぐると 雑誌インタビュー を発見. 読むからに凄腕っぽいが, 企業勤めの凄腕プログラマが プログラマを続けるために独立してフリーランスになる必要を感じたというのは 日本の厳しさを直視させる事実だなあ. 凄腕じゃない私の未来に不安を禁じえない.

"ＤＨＴにおけるセキュリティ対策"

発表者の西谷さんの ページ でたびたび議論されている内容のまとめ. (たぶん. 新しい話もあったのかも.) セキュリティという話題の手前, おおよくわからんけどすごいぜ! という感じの内容ではない. ただ実用を考えると不可避な話題だけに, 眠いなりに聞いた. 別に話がつまらなかったわけではなく, 私はセキュリティが苦手なのでした...

所感

話題が DHT という狭いトピックに集中しているせいか, はたから見るとけっこう専門性の高い内容のものが多い. 質疑も議論が多くて面白かった.

私が DHT を知ったのは, Winny に触発されて P2P の勉強をしていたころのこと. その頃に CAN, Kademlia あたりまでは資料を読んだ気がする. 今日はそんな名前が色々でてきて面白かった. この頃は暇潰しに端から読んでいただけで概念を整理できていなかったけれど, 一連の発表や 首藤さんの入門講義 を聞いたおかげかだいぶ整理できた. 要するに Structured Overlay というゴールがあって, そのための経路管理に DHT やその亜種があるのだな. (この図みたいなかんじ.) こうやってアーキテクチャが整理されるとなんとなくわかった気になれて安心する. ただアーキテクチャの切り方にも難しさはあって, 現在の Overlay Weaver にも dirty な部分はあるという話だった. このへんは専門的すぎてわからず.

あと私はなぜか Skip Graph の論文も読んでいたことを話を聞いて思いだした. (グラフという言葉に弱い.) これを読んだ時は単に理論的な可能性を示しただけのネタだと思っていたので (アルゴリズムの世界ではそんなパターンがよくある), 実装したと聞いてとても驚いた. こんな複雑なものをよくもまあ...と. ただ他の DHT アルゴリズムの説明を聞いていると, どれもそれなりに複雑だった. Skip Graph だけが特別複雑ということではないのかもしれない. 作ってみないとわからないところだな. でも Structured Overley って複雑なんじゃなかろうか. 野良の世界でちゃんと生きていけるのかしら... 実際にものを作った上で対障害性などの運用を含めた 実装寄りのゴタゴタを乗り切れる体力と割り切りのある人が生き残るのかもしれない. 分散ってそんなかんじだよね. きっと.

もう一つ思ったのは, 分散というのは実験が大変な世界なんだということ. P2P は特にその傾向が強そう. これは仕事で分散環境を扱っている人にはあたりまえなんだろうけれど, 私はふだん単一 CPU 相手の仕事なので話を聞くまで想像できていなかった. 実験を考慮に入れている (と思われる) Overlay Weaver さえ PC 一台数百ノードで合計 PC 数十台の数万ノードという実験しかできない. ネットワークのスケーラビリティーが重大な関心であるにもかかわらず 実験が大変というのは, 大変だよなあ.

もっとも自然科学の世界だと実験が大変なのは当たり前, 実験スキルは学者の能力の一部だったりする. 対象が複雑になるにつれて, 計算機工学の世界でも自然科学のように 実験の重要性が高まるのかもしれない. 学問として, 複雑な対象をがんばって実験してデータとって考察する研究が 評価される方向に進む. それは健全な気がする. マルチキャストのシミュレータが修論だったという同僚をふと思いだした.

そんなかんじで仕事とまったく無関係な話を聞き, 連休最終日らしい一日を楽しみました.