« 結婚しました。&ウィーンに行きます! | トップページ | [P2P]P2P入門講座、参加したいですか? »

2005.11.14

[P2P]「Winnyの技術」を読み解く~その1 世代とは?

新婚旅行のウィーンから帰ってきました。久しく離れていたP2Pの話題を少しずつBlogに書こうと思う。

当分の間は
・「Winnyの技術」を読んで
・Skypeがインフラになる日
・P2P勉強会のトピック
が中心になると思う。

まずは標題通り、「Winnyの技術」を読んだ感想+意見について書いてみたいと思う。
ただ感想を書くだけでは面白くないので、周辺技術などを絡めてみればと考えている。

「Winnyの技術」はご存知の通り、Winnyの開発者の金子氏が書いた書籍である。
これまで、P2Pに関する技術的書籍は少なかったので、金子氏のこの本はP2Pの研究そして啓蒙にもとても重要な役割を果たすと思われる。P2Pの技術的側面に関心がある人は必読の本である。

この本の感想をblog1日分で書くのにはあまりにも少なすぎる。そこで少しずつだが、書籍を所々引用しながら感想、解説、意見を書いていきたい。

まずこの本ではP2Pの形態について「世代」と言う言葉を通して整理している。具体的には

・第1世代:Hybrid-P2P:Napsterなど
・第2世代:Pure-P2P:Gnutellaなど
・第3世代:Puer-P2P:Freenet,Winnyなど

ここで、第2世代と第3世代の違いが気になるところだ。32Pによれば、金子氏は第3世代をPure-P2Pの中でもキャッシュ機構が入っているシステムと定義している。

まずここでキャッシュを使って第2世代と第3世代となにが違うのか考えてみよう。

私が第2世代との違いの特徴として挙げるのは
特徴1.匿名性の強化
特徴2.システム全体における.トラフィック効率の上昇
特徴3.オリジン(元祖ノード)が非オンラインでも情報提供が可能
の3つである。

特徴1.2.については「Winnyの技術」を読んで欲しい。特徴3についてはここで少し補足しよう。
そもそも、第2世代のPure-P2Pではオンラインしているノードのファイルしか共有ができない。しかし、キャッシュ機構によって、オリジンのノードがオフラインでもファイルが共有できる。
特徴3がWinnyの人気を押し上げた事を忘れがちであるが、とても重要が概念であると個人的には思っている。(もしかすると金子氏は利点3を突き詰めてWinnyのBBS機能を具備しようとしたと考えたのかもしれない。)

では金子氏が唱えたキャッシュ機構+Pure-P2PをP2P研究者が第3世代と考えているかと言うと、実は違う。
一般的にはP2Pの第3世代とは

・第3世代:DHT(分散ハッシュテーブル)を使ったPure-P2P:Skype(恐らく)、一部のファイル共有ソフトの部分機構

と言われている。DHTについては本blogやHPを見て欲しいが、第2世代とは明らかに違う特徴がある。
それは、

・全てのオンラインノードのコンテンツを検索可能である
・検索に伴うトラフィック負荷がとても軽い、検索が高速(log[O]程度)
・多数のノードの参入、離脱に耐えられる
・数10億以上のノード参加に耐えられる
ことが挙げられる。

(参考)
分散ハッシュテーブル(DHT)入門~その1
P2Pと分散ハッシュテーブル~その1


では、Winnyは第2世代のP2Pシステムか、というと、これは色々議論があるだろう。
大枠で区切ると確かにWinnyはGnutellaの延長である。この点でWinnyを第2世代と呼ぶのは間違いないかもしれない。しかし、何点か第2世代の先を行くシステムが見受けられる。その主たるものは、

・上流、下流の組織化による、検索トラフィック負荷の軽減
・クラスタリングによる、「意味」による自己組織化

の2点だろう。

まずは上流、下流について。
そもそもGnutellaに見られる第2世代はバケツリレーによって検索情報を伝播している。その特徴としてTTLと呼ばれる数字によって、検索できるノードを制限している。もしTTLがないと、検索トラフィックが膨大になりP2Pネットワークがダウンしてしまうからである。
この点でWinnyは先端的であった。上流、下流ノードを配する事で非常に効率的にコンテンツを検索することに成功したのだ。ノードに重みをつけて、自己組織化することはとてもユニークである。(それまでのP2Pシステムは、ノードの重みが全てフラットであることが多かった。)

そして、後者は更に重要な概念だ。現在でも意味によって自己組織することは大変なことである。
実はP2Pの第4世代というのは、意味情報によってルーティングすることを指す人がいる。例えばNTT研究所が開発したSIONetがそれである。
意味組織化を3つのキーワードの部分一致の大きさによって意味によるノードの自己組織化を行った事はとても大きな結果である。なによりもシステムの概念が明確であり、その実装も比較的容易と考えられる。
キーワードによる意味組織化は第3世代のDHTによるシステムにも、重要な影響を及ぼす事だろう。

このように実はWinnyはGnutellaの意味する自己組織化をさらにユニークな形でパワーアップしていて、当時として(そして現在でも)先端的なシステムであることがわかる。そこで私はWinnyを2.5世代のP2Pシステムと呼びたい。

本書を読むと金子氏はDHTシステムに近いモデルを模索していた事がわかる。(159P)もし、金子氏が当時DHT
に関する文献を読んでいたら一体どんなシステムになっていたのだろうか?とても興味が沸くところである。
本書の同じページにはこのようなことが書かれている。

「いまなら分散ハッシュテーブル(DHT)を使う事も考えられますし、現在のWinnyはP2Pネットワーク上で遠方にあるノードへの検索を諦めてしまっているので、もう少し効率のよい方法もあるでしょう。」

次回は上流、下流について考えてみたい。

|

« 結婚しました。&ウィーンに行きます! | トップページ | [P2P]P2P入門講座、参加したいですか? »

P2P」カテゴリの記事

コメント

Nobodyさん:
コメントありがとうございます。
P2Pに関わっている人間にとっては、やはり単なるPure-P2PからDHTへは劇的な変化だと思います。つまり世代が変わるぐらいのインパクトがあるのでは。と考えるのです。もちろん、世代は厳密な定義があるものではないので、個人の主観で変わると思います。

確かに金子氏はP2Pファイル共有の世代」ですね。
ただ、ファイル共有の世代は、ほぼP2Pの世代なのでそれほど間違った内容ではないと思います。いずれDHTのファイル共有が普通のものとなるでしょう。

skypeが第2世代という金子氏の解説は、キャッシュなしのPure-P2Pを第2世代と指しているからです。
もし、DHTが第三世代であれば、skypeは第三世代に入るでしょう。(もちろんDHTが使われている事は予想に過ぎません。)

Kiyoshiさま
コメントありがとうございます。
確かにハッシュの信頼性については疑問視される論文がでていますが、これはある実装について述べているわけで、「理想的な」ハッシュ関数であれば問題はないでしょう。(どの程度理想と現実が乖離しているか客観的に判断するのは難しそうですが。)
現在のSHA-1が100ビット程度ですから、数10ビット程度の範囲であれば、ある程度耐えられるのかなっと思っています。

ちなみにSkype社はまだ公式にDHTをskypeで使っているとは明言してなかったと思います。

投稿: Tomo | 2005.11.16 23:27

■ハッシュ関数■
japan.linux.comで、中国の学者がMD5とSHA1の欠陥を指摘して、大騒ぎになった、という記事を最近読みました。(http://japan.linux.com/security/05/11/08/0213251.shtml?topic=1
Tomoさんの『[P2P]分散ハッシュ(DHT)入門~その3』(http://toremoro.tea-nifty.com/tomos_hotline/2005/01/p2pdht.html)に「ちなみにハッシュ関数としてはSHA-1をよく使うが、これは0~数10億までハッシュ値が存在する。つまり数10億ノードが参加しても大丈夫!ということだ。これがDHTでは非常に多くのノードの参加が可能である理由のひとつとなる。」と書いてありますが、大丈夫なんでしょうか。分散ハッシュテーブル技術の根底にある、ハッシュ関数の品質は。
ところで、池嶋俊『入門Skypeの仕組み』(日経BP社・2005年10月24日発行)という本の第4章「P2Pで電話をどうつなぐのか?「スーパーノードが相手を見つける」」の第2節「ハッシュ関数を使ってグループを分ける」(51ページ)に「どんなハッシュ関数を使っているのかや、出力の数字をどう使ってグループ分けをしているのかなどの詳細はわからない。スカイプ・テクノロジーズが企業秘密として公開していないからだ」と書いてあります。

投稿: Kiyoshi | 2005.11.16 11:52

第1世代から第2世代への変化は時代背景から
単純に「進歩」と呼べるでしょうけど、
第2世代からの進歩・発展はさまざまな方向性があって、
1次元に投影して第3世代、第4世代と呼ぶのはもともと無理があるように思います。
例えば金子氏の区分ではSkypeは第2世代となっています。

蛇足だけど金子氏の区分は「P2Pファイル共有の世代」で、
「P2Pの世代」ではないです。

投稿: | 2005.11.15 15:02

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: [P2P]「Winnyの技術」を読み解く~その1 世代とは?:

« 結婚しました。&ウィーンに行きます! | トップページ | [P2P]P2P入門講座、参加したいですか? »