P2P掲示板の考察【前編】


さて、今度はWinnyで良く知られてるP2P掲示板について 説明します。現在、P2P掲示板については匿名性等を高くしたり、 掲示板の内容を広範囲に広めるためにいろいろなプロジェクトが 進んでいますが、多くの課題がありWinnyを超えるソフトは未だ完成していません。 ここでは個々のプロジェクトのシステムを説明するよりも、簡単なモデルを立てて、 P2P掲示板システムの課題について浮かび上がらせるアプローチを取らせて 頂きます。
(注意)分散ハッシュを応用するとこの章で述べる課題を比較的容易にクリヤ できるP2P掲示板を作ることができます。詳しくは後ろの章にある 分散ハッシュテーブルのP2Pアプリへの応用〜その1 をご覧になって下さい。
掲示板別サーバ型
これはWinnyがP2P掲示板を実現している方式の一種です。 下図を見てください。

各ユーザはそれぞれ掲示板サーバとして働きます。 例えば、Dには掲示板1「P2Pとは?」、Fには掲示板2「現代音楽って?」が立っていたとします。 ユーザAが掲示板内容を把握するためにはP2Pネットワークにブロードキャスト して掲示板タイトルを要求します。各ユーザは自分のPCで管理している 掲示板のタイトルをユーザAに返答します。もし、掲示板「P2Pとは?」 を見たければユーザDから掲示板内容をバケツリレーでユーザAに転送します。 一方掲示板「現代音楽って?」を見たければユーザFから掲示板内容を バケツリレーでユーザAに転送します。 逆に掲示板に書き込みをするにはどうでしょうか?たとえば、掲示板「P2Pとは?」 に書き込みするにはバケツリレーでユーザAがユーザDに書き込み内容を伝える必要があります。

もう少し考察しましょう。ユーザAが掲示板を見られる内容はブロードキャスト が到達するユーザが保有している掲示板のみです。すなわち、ユーザA の近辺に限られるわけです。

さて、仮にユーザDがネットワークから外れたらどうなるでしょう? 掲示板「P2Pとは?」はユーザDが管理しているので、このネットワーク にいる人は掲示板「P2Pとは?」を見ることができません。つまり ユーザ間で同期したり、掲示板内容をキャッシュすることはありません。 逆に掲示板内容が一箇所で管理しているので、掲示板の内容の消去が簡単 であることが挙げられます。

このシステムの特徴をまとめましょう。

なお、Winnyの掲示板はNYch(http://nych.info/main.php)というゲートウェイ サービスがありブラウザから掲示板への読み書きが可能です。 実際のどのようなスレッドがあるか見てみるのもいいでしょう。


キャッシュ型
さて、先ほどの「掲示板別サーバ型」の一番の難点はユーザがネットワーク からいなくなると、そのユーザが保有する掲示板が見られなくなることです。 これを改善するために、Winnyのファイル交換で使われるキャッシュを 応用するアプローチが考えられます。まずは簡単なモデルを作ってみましょう。

今、Dに掲示板「P2Pとは?」があったとします。ユーザAはブロードキャストして ネットワーク上の掲示板タイトル情報を取得します。さてユーザAが掲示板「P2Pと は?」を見たければユーザDからバケツリレーで掲示板内容を転送します。この時 ユーザAと経路上のユーザは掲示板「P2Pとは?」をキャッシュします。 (ただし、後で述べるように単純なキャッシュにしない方が利便性が向上します。)

掲示板「P2Pとは?」はキャッシュされていますから、例えユーザDがいなくなっても ユーザC、ユーザB、ユーザAがいれば近辺のユーザは掲示板「P2Pとは?」を 見ることができます。

少し戻ってみましょう。このシステムでは掲示板内容がキャッシュされているので、 ネットワーク上に多くのPCが同じ掲示板のタイトルを保有しています。 では、どのユーザから掲示板内容を入手すればよいでしょうか?例えばレスの多い 掲示板やレス(または更新)が一番新しい掲示板を保有しているユーザから 掲示板内容を入手すればよいことになります。

さて今度は書き込みを考えて見ましょう。掲示板に書き込むときに、いまの キャッシュ方式では自分の PC内のみに書き込み内容を追加してもそれだけでは周りに伝播しない 可能性があります。これでは ユーザがネットワーク上から離れるとその書き込み内容は全く掲示板には 反映されないことになります。そこで、書き込む時には更新が一番新しい掲示板 を保有しているユーザに対して掲示板内容を転送することにします。先ほどの図で ユーザDが最新の 掲示板があれば、ユーザAは自分の書き込みを含んだ掲示板をユーザB、 ユーザCにキャッシュしながらユーザDに伝えます。こうすれば、ユーザAが ネットワークから離れても書き込んだ内容はユーザB,C,Dに残ります。

ではキャッシュの動作についてより深く考察しましょう。 もうピン来る人がいるとも思いますが、各ユーザ毎に ある特定の掲示板についてのキャッシュ内容は違う可能性があります。 例えば全てのユーザが掲示板1 のキャッシュを持っていたとします。ところがユーザ毎に掲示板1の キャッシュ内容が違う場合があります。下図をご覧になって下さい。

前提:
今、ユーザAが9時に更新した掲示板1のキャッシュがあるとします。 一方ユーザFは9時30分に掲示板1のキャッシュが更新したとしましょう。

今、エリア3のユーザCはユーザFにもユーザAにもブロードキャストでき ます。ユーザFはユーザAより掲示板1の書き込み時間 が最新ですから、ユーザCはユーザFから掲示板内容を入手して、 ユーザFに掲示板書き込むを行うことになります。 この書き込み更新はユーザAに反映しません。そのため、ユーザF とユーザAの掲示板1のキャッシュ内容が異なる事がわかりました。

もう少し考え見ましょう。Cが掲示板1に書き込んだ後、 ユーザPが掲示板1に書き込みをしようとしています。 ブロードキャストは隣の隣までですから、ユーザPから見て 最新のファイルを持っているのはユーザCではなくユーザA です。そこでこんなことが起きてしまいます。

また、ユーザがP2Pネットワークに長時間離脱すると、 それだけキャッシュの更新がないので、掲示板1のキャッシュ内容 は他の人と違ってしまいます。

さて、キャッシュのあり方について考察しましょう。 どのようにすればこのキャッシュ内容の違いを吸収できるでしょうか? 先ほどの図でエリア1、エリア3を含めてユーザAが最新の掲示板1 のキャッシュを持っているとしましょう。 ユーザCからユーザAへのキャッシュ経路はC⇒B⇒Aですね。 今、次のように仮定します。

まず、ユーザCはユーザBにCのキャッシュを渡します。 ユーザBはユーザCから得た情報を追記し、レスの順番 を並び替えます。つまりこの時点でBの掲示板キャッシュ内容は 「レス1、レス2、レス3、レス5、レス6」 です。この内容をBはAに転送します。結局Aは同様の操作で
「レス1、レス2、レス3、レス4、レス5、レス6、レス7」
を得ます。このようにレスの入れ替えをするのでレスは XMLで記述した方が操作しやすいかもしれません。

さて、次に参照の話をしましょう。 2chの掲示板で良くある話ですが、例えば、

「42 名前:Tomo:
お久しぶり!Nanaさん。 >> 40 あの試験は正直大変だった。」

というレスがあるとします。これは42番のレスが40番を参照して 欲しいということになります。ところが先ほどのキャッシュ の方法ではレスの順番が変わってしまう場合があります。 そのため、レスの参照番号>>40を適切に変えないと、別のレスを参照 可能性があります。

それを防止するためにはレスに対してレス番号だけでなく、 レス毎にユニークな値を付随させ、それを参照するという仕組みに する必要があります。ユニークな値としてレス内容等のハッシュ値 が挙げられるでしょう。つまり、先ほどの40番にレスする というのは、実は内部ではレス40番のハッシュ値にリンクを することになります。またキャッシュでのレスの順番 入れ替えの時、当然そのハッシュ値のリンクを基にレスの参照先番号 も変える必要があります。このような作業をするにはXMLでレス を整形し、DOM等で処理を行えば良いでしょう。例えば先ほど のレスのXMLとして

 <res>
   <time>2004/2/7/11:00:15</time>
   <res-number>42</res-number>
  <res-name>Tomo</res-name>
   <res-document>
   <res-link>
        <linknumber>none<linknumber>
        <doc>お久しぶり、Nanaさん。</doc>
   </res-link>
     <res-link>
        <linknumber>40</linknumber>
        <linkhash>sak#dkjsacS(レス40のハッシュ値)</linkhash>
        <doc>あの試験は正直大変だった。</doc>
   </res-link>
   <reshash>sanfdlkn3#SA(レス42のハッシュ値)</reshash>  
  </res-document>
   <password>gf&(lzlksanfda(レス42の削除用ハッシュ値)</password >
  <flag > 0(削除されたレスなら1を立てる)</flag>
 </res>
とすれば良いでしょう。 

最後にレスの削除の話をします。キャッシュ方式なので、 このレスは自然とネットワークを通じて拡散していきます。 これは「噂話」と同じ原理です。お互いに興味のある話は 人を通じて遠方に拡散するわけです。しかし、興味がなくなれば レスを見ることも無いので拡散はストップします。 キャッシュ方式ではネットワーク全体に広がったレスを 全て消去するには非常に困難を伴います。

消去する方法として、レス毎のハッシュ値を 使う方法があります。まず、消去したいレスのハッシュ値 とスレッドのハッシュ値、それとレスの削除用パスワードを ブロードキャストします。ブロードキャスト内のユーザは削除用パスワード をハッシュ関数にかけて、レスのパスワードハッシュ値と照らし合わせます。 レスのパスワードハッシュ値と削除用パスワードのハッシュ値が一致すれば レスの内容を削除します。ただし、レスのハッシュ値は残しておき、 フラグを1に変更します。

他のユーザから削除対象の掲示板キャッシュが転送された 時に、削除されたレスのハッシュ値を見て、それと一致するレスが あれば、それをキャッシュから削除します。また、 削除されたレスのハッシュ値は他の掲示板のキャッシュと共に伝播して、そこで 伝播されたユーザにおいて先ほど削除されたレスのハッシュ値に対応する キャッシュ内のレスを 強制的に消す事も考えられます。この方法で あるエリア内に限ればレスが消去し、拡散もある程度防ぐ事が できます。スレッドの削除も同様な方法で対処できます。

さて、このようにキャッシュ方式の場合、広範囲のエリアで 掲示板内容が完全には同期されないことがわかりました。 次の章では広範囲のエリアで掲示板内容が同期できるシステムを 提案します。

NEXT

TOPページに戻る