P2Pファイル配信
文章
実装
P2Pファイル配信で考えたこと垂れ流し
最近別のことをしているので、去年〜今年の４月くらいまで考えていたことのまとめ。
実装はポエニーとちょっとしたシミュしかやっていないので怪しい意見てんこ盛りですし、専門にやっている人的には当然だったり、どうでもよかったり、もっとひどいと間違っていることもあるかもしれませんけど、個人的に垂れ流し。
一人でやっていたので造語とか妙な表現が多いかもしれないです。
まず設計すべき重要なこと２つ
- ファイルの検索
- ファイルの配信
ファイルを検索できて、選択したファイルをダウンロードできれば全てOK。
それ以上のことは、もっと上の層に任せる。
ファイルの検索
一番難しいのがこれ。たくさんのコンピュータからどうやってファイルを検索するのか？
基本は、１つのコンピュータをノード、ノード間のコネクションをポインターとおいて、ネットワーク上に検索のためのデータ構造を作り、それを使って検索する方法。
LikedListクラスやHashMapクラスやSkipListクラスやB_Treeクラスようなものをネットワークを舞台に作って、それに対してファイル情報を追加したり、ファイル情報を検索したりすると考えれば分かりやすい。
通常プログラムのライブラリとして作る場合と違うのは、『神』のごとく参加ノードにランダムアクセスできないという点で、各ノードを中心としてそのノードの保持する情報のみでデータ構造を構築、検索できるアルゴリズムを実装しなければならない。さらに、いつのまにか消えるノード（離脱）が出てくるので、消えた場合の復旧処理も必要になる。全てのノードが同じアルゴリズムで動くので、検索は再起手順で行える必要がある。
イメージは……各ノードを１つのスレッドにして、たくさんのスレッド群で検索アルゴリズムのための１つのデータ構造を作る。各スレッド間では、メッセージング機構を利用して通信をすることはできるが、共有メモリがないので、共有すべき情報はメッセージで送り合わなければならない。……という感じ。
制限を科せられたプログラミングに、わくわくしちゃう人にオススメ。
実装例
DHTいろいろ
分散ハッシュテーブル。パケットのルーティングアルゴリズム。
例としてChordがよく紹介される。
Chordは、ノードを円形に繋げたスキップリストを舞台に、検索パケットを２分探索経路にルーティングさせるようなアルゴリズム（たぶん）。
eMuleやBitCometが使っているのは、KademliaベースのDHTらしい。
ファイルのハッシュ値をキーにして検索するのが基本。
はい、詳しくない。
ハッシュテーブルは完全一致検索になるので、ファイル共有でのキーワード検索には向いてないかもしれない。対応させるには、ファイル名を細切れにして撒くなどの方法があるが、検索結果が膨大になってしまうことがあるので、それを分割送信する方法も考える必要がある。（これはもうDHTじゃない？）
Winny
上流、下流という方向性と、クラスタリングキーワードによる相対的な座標概念を持ったグラフ。
通信速度の速いノードほど上流とし、構築段階としてファイル情報をできるだけ上流に吸い上げるように集める。
そうすることによって、検索は上流方向へ検索パケットを投げるだけでよくなる。
検索パケットは上方向にランダムにルーティングされ、最大６ステップすると検索結果を乗せて戻ってくる（６という数字はスモールワールドから？）。何度も検索を行うことで、少しずつ検索結果を集めてくる。
- 短所
ノード数が増えてくると検索効率が悪くなる。これを回避するために、自分とクラスタリングキーワード（趣向を表す要素）の似ているノードと優先的に繋がることで、横方向にも階層を作る。しかしこうすると、クラスタリングキーワードの離れているノードの持っているファイルは検索しづらくなる（できないかもしれない）。あいまいなまったり検索。
- 長所
仕組みがシンプルなので、実装が簡単。
100万ユーザ（ノード）で『実用的』に運用できていたWinnyの実績がある。
ファイル配信
ただ配るだけならApacheでよい。
Winnyはファイル配信だけをそのままApacheで置き換えることができる（やろうと思えば）。
ミラーリングタイプ
ファイルの配信元のコピーを大量に作成し、ダウンロードを先を分散させる。
ミラーサイトを動的に作るイメージ。
Winnyが、このタイプ。
- 短所
まず１つのノードが同時に配信できるファイル数は限られている。多くても４つ程度。そうすると、100個のファイルをミラーしているノードがあったとしても、同時には4つしか配信できない。ダウンロード側からすると、ファイルを検索するだけでなく、ファイルを持っていてかつ今すぐにダウンロードできるノードを探す必要が出てくる。ファイルを持っているノードのアドレスが分かったからといってダウンロードできるとは限らないのである。よって、ファイルを検索したときにダウンロードできないノードのアドレス、つまりはごみデータがいくつか返ってくることになり、さらに情報をろ過する必要が出てくる。
また、ネットワーク上にただ１つしか配信ノードがいないファイルAあるとし、そのファイルAを保持するノードが、別の４つのファイルを配信中だった場合は、ネットワーク上にファイルAを配信できるノードがいなくなってしまう。
- 長所
ダウンロードフォルダを配信フォルダと同じにするだけでいいという超簡単な実装。
なんだかんでそこそこ動くことは、Winnyで実証済み。
バケツリレータイプ
超造語なので、簡単に説明。
まず二分木を思い浮かべて欲しい。そしてルート（根）を配信元とし、それにぶら下がる全てのノードはダウンロードノードとする。
ルートは、まず直接繋がっている２つのノードにファイルブロックを配信する。その２つのノードはそれぞれさらに直接繋がっている２つのノード（２つあわせて４つ）に配信する。さらに……と、各ノードの通信負荷を一定にしたまま指数的に配信可能なノードを増やす方法が基本的な考え方。
実装では、ノードの途中離脱を考慮して二分木とは違った構造にしないともちろん動かない。
たぶん、これをうまく実装したのがBitTorrent。
リアルタイムなストリーミング配信をしようと思ったら、この方法。
- 短所
１つのノードが配信できるファイル数が限られる。同時配信４つとすると、４つ以上は配信可能とするべきではない。
配信元のミラーを行うと、ダウンロードユーザの集合が分割されてしまうので、効果が軽減してしまう。ミラー数がダウンロード者数を上回ると、１対１の配信になってしまう。
しかし、配信ノードの離脱を考えてのミラーリングは必要である。
同時刻にダウンロードしているノードが２つ以上いないと役に立っていない。
- 長所
配信ノードのアドレスが分かれば、ただちにダウンロードできる（かもしれない。というか、そう作るべき）。
理想系
バケツリレー＋ミラーリング。
ネットワーク全体を見通して、配信ミラーの数を調節しつづける。
例:
- 自分の持っているファイルを持っている別ノードを検索する（foreachする）
- 結果数が一定数より少ない場合は、そのファイルの配信優先度を上げる
- 検索結果が一定数より多い場合は、そのファイルの配信優先度を下げる
- ファイルごとの需要数によって配信優先度を微調整する（被参照量やファイルサイズなど考慮）
- 配信優先度でソートし、上位４つ（同時配信４の場合）を配信対象とする
これを定期的に行い、動的に配信ミラー数を調節する。
この実装のためには、ネットワーク全体を一定時間で完全検索できるファイル検索の実装も必要になる。うげ。
