旧・無印吉澤

昔はてなダイアリーに書いていた記事のアーカイブです

P2P掲示板「新月」のプロトコルとデータ構造（「新月」開発者 Fuktommy氏）

P2P

▼勉強会告知での紹介文

「新月」は書き込みを積極的に送信・中継することで内容を広めていく。ファイル構造が単純なので、参加者は気軽にキャッシュを削除することができる。こうしてネットワークが最適化されていく。このような仕組みについて述べる。

▼関連サイト

▼講演内容補足

  • （「はじめに」の前に、新月を理解するためのアドバイスとして）何故「新月」を作るようになったか、という背景が分かるとプロトコルの全体的なイメージが掴めるのではないかと思う。
  • 各P2P掲示板の、書き込みの伝播方法
    • 新月：ブロードキャスト
    • WinnyBBS：各スレッド毎にサーバを立てて、そこに接続する
    • RinGOch：（解説文書によると）リクエストがあった時に取りに行く。ブロードキャストとは違う
  • （書き込みの伝播(6)にて）書き込みがあったノードと同じように振る舞うのは、誰が発言したのかをわかりにくくするため。「発言者が特定されないようにする」
  • アプリケーション層の本質は、キャッシュファイルのデータ形式。「削除信号」のページにある例で言うと、name:で始まる行以下の部分。
  • 新月の本体はライブラリ
    • 新月はP2P掲示板と名乗っているがその本体はライブラリみたいなもので、その上には複数のアプリケーションを乗せることができる、というのが当初からの考え方。
  • 新月の野望 → RFC化
    • RinGOchは、アプリケーションを良い物にするためにプロトコルをバンバン変えてる。
    • 逆に新月は、プロトコルは固定しておいて、アプリケーションは使える物は使う。JXTAのような方向に寄りたい。*2

▼質疑応答

  • Q)データ補完の方法について質問。新月は幅優先探索のようだが、全てのノードを探索するのか？((参考：幅優先探索)）
  • A)ある程度探したら諦める。
    何故このような動作をしているかというと、「記事を気軽に削除できる」ことに関わっている。DHTのような方向で、例えば「RinGOchのスレは○○さんが持ちなさい」という形にすると、「私はRinGOchなんか嫌いだから削除しちゃうよー」なんて気軽に削除できない。*3
    それは辛いので、みんながデータを均一に持つようにしている。そうなると、幅優先探索になる。
  • Q)幅優先探索だと新月のユーザが増えたときに、ネットワークの端から端まで書き込みが伝わらないのではないか。
  • A)伝わると……思いますけどねぇ。それほど現実的な状況ではないのでは。誰かしら繋いでますよ、多分。
  • Q)その証明が出来てないのは大丈夫なのか。
  • A)ダメでしょう。証明は多分できないと思いますよ。
  • Q)そうなると、削除信号でも同じ問題が起こって、削除してコピーして削除してコピーして……といつまでたっても削除できなくなるのでは。
  • A)削除したというのは覚えているので、多分大丈夫。削除信号が伝播しないのは逆にいいことがあって、「なんで削除しないんだ」と怒られたときに「削除信号が届かなかったから削除できなかったんだ」という言い訳ができる。
  • Q)それは……「なんでしっかり削除できる機能を作らなかったんだ」って突っ込まれたら大変ですよね？
  • A)だから、削除じゃない情報も時々伝わらなくなって、まぁバランスが取れてるかなぁと。
  • （会場から拍手）
  • C)（開発者の一人として）用語の統一は出来るだけ早くお願いしたい。IDの規範もあったらいいなぁ、と思う。エンドユーザ向けのドキュメント書きを募集中。2ちゃんねらを巻き込みたい。
  • C)先程の「幅優先の全数探索になってしまうのではないか」という話の関連。
    BarkeleyがやっているOceanStoreのアンダーレイのTapestryというネットワークでは、Bloom Filterという古典的な技術を使っている。
    これは、「ここから先にどういう情報があるのか」という情報を100ビットや200ビットに圧縮して流すことで、探索が一通り終わったあとにどちらの深さを取っていくかという選択を確率的に最適化するようなアルゴリズム。そういったものを採用すると良いかもしれない。*4

*1:岩田氏の講演でも触れられていた「P2Pはプロトコルである」という言葉はここで公開されていたような気がするのですが、過去ログは無くなってしまったんでしょうか。→（追記）コメント欄のFuktommy氏からの書き込みを参照。

*2:JXTAプロトコルのInternet Draftは時々発表されているものの、今のところRFCになる様子はなさそうです。参考：draft-duigou-jxta-protocols

*3:これは、誰が記事を削除したか（＝誰が記事を持っていたか）が周囲の人に分かってしまうから、ということ？→（追記）こちらも、コメント欄のFuktommy氏からの書き込みを参照。

*4:日本語で書かれたBloom Filterの参考サイトは見つけられませんでした。英語ではUsing Bloom Filters(perl.com)あたりが参考になるかと。