Linuxのディストリビューションの配布などで配布サーバの回線速度などがボトルネックになり（図1)、円滑にファイルを配布することはコストがかかります。BitTorrent(図2)は配布者の負担を軽減して、素早くファイルを配信することを目的にBram Cohenによって開発されたP2Pソフトウェア(図3)です。

BitTorrentでは、トラッカーとよばれる全てのピアとピアのアップロード/ダウンロード能力、ファイルの取得状況を管理するサーバが存在します。一般的なP2PシステムではP2Pネットワーク内を検索してからファイルの取得という動作を行いますが、BitTorrentでファイルの検索という作業は行ないません。代わりにトラッカーにファイルを持っているピアを問い合わせます。ファイルを持っているピアの検索をクライアント・サーバで行うということで、従来の分類ではハイブリッド型P2Pシステムになります。BitTorrentのクライアントとトラッカーとの通信は、HTTPを使用しています。

BitTorrentのクライアントがピアを検索する時に使用するのがtorrentファイルになります。torrentファイルとは、ダウンロードしようとしているファイルのメタ情報をもっています。具体的には、ファイルのハッシュ値や、トラッカーのURLです。クライアントがファイルをダウンロードしようとすると、まず、このtorrentファイルを取得しなければなりません。torrentファイルは、取得しようとしているファイルの提供元のWebサーバなどで公開されています。このtorrentファイルを取得して、BitTorrentで取得したファイルを開くことで、ファイルのダウンロードが開始されます。

BitTorrentがファイルをダウンロードを開始すると、クライアントはトラッカーに処理の開始通知を送信して、ダウンロードしようとしているファイルを持つピアの一覧を取得します。次に、ピアの一覧からピアを選択し、接続してファイルをダウンロードします。ピアがお互いを認識すると、以降はピア同士がお互いに協調して、ファイルのダウンロードを行います(図4:Fig4.gif)。ファイルをダウンロードする時には、ファイルをさらにピースと呼ばれる単位に分割して、そのピース単位でダウンロードします。一つのピースがダウンロードされるごとに、ピースの完全性を検証後、他のピアへのアップロードが可能になります。このため、すべてのファイルのダウンロードを待たずにアップロードが可能になるので、転送効率があがります。また、ネットワーク上のトラブルやファイルの改竄など起きた場合でも、ピース単位でリトライできるとことも特徴の一つです。ファイルのダウンロードが完了すると、クライアントは他のクライアントに対してアップロードだけを行うようになります。

BitTorrentが、ユーザ数が増加しても安定したファイルの配信が可能になるといわれています。これは、ダウンロードしているクライアントが、なるべく早い段階でアップロード機能を提供できるため、一ヶ所に負荷が集中しにくいためです。

BitTorrentでファイルを配信したい場合、まず、配信したいファイルとトラッカーのURLをもとにtorrentファイルを作成します。次にこのtorrentファイルをWebサーバなどに配置します。最後に配信したいファイルを持っているBitTorrentクライアントを起動します。このクライアントは、オリジンとなり、他のBitTorrentクライアントのダウンロード対象になります。一端、ファイルが他のクライアントにダウンロードされれば、オリジンとなったクライアントは終了しても他のクライアントはダウンロードを続けることができます。ただし、他のクライアントがすべて終了することありえるので、オリジンとなったクライアントは起動しづけることが望ましいでしょう。

bencode(「ビーエンコード」と読みます)は、ネットワーク経由でデータをやりとりするために、データをシリアライズする仕組み、フォーマットです。torrentファイルのフォーマットにも、このbencodeが使用されています。辞書やリスト、整数と文字列が扱えます。文字列はPythonの文法としての文字列です。つまり、実質バイト列です。bencodeでは、シリアライズするときの負荷が少なく、効率的に復元できます。また、高い拡張性も持ち合わせていますが、Pythonの標準のシリアラズ機能が提供しているような、複雑なデータ型は処理できません。

BitTorrentがtorrentファイル（メタファイル)を作成している部分のコードは、makemetafile.pyに記述されています。 まず、makemetafile.make_meta_files関数がコールされて、実際にtorrentファイルが作成される関数はmake_meta_fileになります。make_meta_filesは、複数のファイルへのパスを受け取り、個々のファイルへの処理をmake_meta_fileが行います。make_meta_fileの関数の実装は、次のようになります。

make_meta_fileの引数のpathはファイルへのパスになります。urlはトラッカーのURLになります。piece_len_expはファイルを複数の小さな断片に分割するときの、各断片のサイズになります。flagとprogressは、マルチスレッドで動作しているときや、GUIアプリケーションなどで、進行状況を把握したい場合などの、コールバック関数になどになります。encodingはファイルシステムの文字コードになります。

この関数の中で、まず、出力するmetafileの名前を設定しています(95-102行目)。targetが指定されている場合は、targetのファイル名、指定されていない場合は、実際のファイル名に.torrentを付加した物になります。次に、makeinfoによりファイルの各断片ごとのメタ情報を生成して(103行目)、最後にbencodeしてファイルに出力しています(107-112行目)。bencodeする内容は辞書形式で、断片化したファイルの情報(info)、トラッカーのURL(annouce)、作成日時(creation date)になります。

ファイルを断片化してメタ情報を作成している関数makeinfoでは、与えられたPathがディレクトリかファイルかで場合分けがされています。pathで指定されている物がファイルの場合は、ファイルをpiece_lengthのサイズごとに読み込んでsha1アルゴリズムで断片のハッシュ値を生成しています。ファイルを各断片ごとにハッシュ値を取得した後に、そのファイルのメタ情報として、辞書として、断片の長さ(piece_length)、ファイル名をUTF-8でエンコードした物(name)、各断片のハッシュ値を連結した物(piece)を返しています。

与えられたパスがディレクトリの場合は、ディレクトリを再帰的に検索して、ディレクトリ内に含まれるファイルをpiece_legnthのサイズごとにsha1アルゴリズムでハッシュ値を生成し、ファイル名とサイズからなる配列にディレクトリ内のファイルを全て追加します。最後にこれらの情報を辞書に格納したものを返しています。

これらの操作を実際に試してみます。操作はPythonのインターラクティブモードで実行しています。実行結果は次のようになります。

import BitTorrent.makemetafileでモジュールをメモり上にロードして、BitTorrent.makemetafile.make_meta_fileでビットトレントの配布用ソースコードからtorrentファイルを出力しています。実験用のトラッカーとして、ローカルでトラッカーを動作させるので、http://127.0.0.1:8080/を指定しています。ファイルの断片化は1024bitごとに行うように指定しています。出力ファイルはtargetで指定されているsize1024.torrentというファイルです。実際に出力されたファイルは次の内容になります。

sha1ハッシュ値はバイナリのため、省略しています。

BitTorrentクライアントを起動して、torrentファイルを選択すると、BitTorrentクライアントはtorrentファイルからトラッカーとファイルの情報(info。ファイルサイズと名前、ファイルピースのハッシュ値)のsha1ハッシュ値(*1)を取り出します。次に新たにピアIDを作成(*2)して、TCP/IPで外部からアクセスできるようにポート(*3)を開きます。ポート番号は6881番から6889番の間で最初にbindできるポートが使用されます。準備ができると、先ほど取得したトラッカーに対して、HTTPのGETリクエストを発行します。リクエストは、次に示すようなURLになります。

info_hashは(*1)で取り出したメタ情報のinfoのsha1ハッシュ値をエスケープしたものです。peer_idは(*2)で作成したピアID、portは(*3)でリッスンしているポート番号になります。uploadとdownloadはBitTorrentクライアントがアップロード、ダウンロードしたバイト数になります。leftはファイルの全体のサイズから現在ダウンロードが完了したピースのバイト数になります。compactはレスポンスで返すピアのリストを従来のbencodeで返すか、IPとポート番号のバイナリ値で返すかを制御します。1に設定されている場合はバイナリ値で返します。これは、以前のBitTorrentがbencodeで設定されていることを前提としていたため、下位互換性のために作成されました。eventは現在のステータスになります。ステータスは3種類用意されていて、ダウンロード中のステータスを示すstarted、ダウンロード完了時にcompleted、ダウンロード中断時にはstopedを指定します。以降のトラッカーとBitTorrentクライアントの情報の定期的な送受信にもこのURLが使用されますが、定期的な情報のやりとりでは、eventの値は指定されません。

これ以外には、ipアドレスを指定できます。ipアドレスは、トラッカーがTCP/IPのコネクションのソースIPからIPアドレスを特定できない場合に使用します。

次に、このHTTP GETリクエストに対してのレスポンスが返されます。レスポンスは、ダウンロードが完了しているピア数とダウンロード中のピア数、BitTorrentクライアントが続けてリクエストを送る場合の間隔と、peerのリストがセットされます。compactが1にセットされている場合は、peerはIPアドレスとポート番号のバイナリ値になります。今回の例では、ファイルを持っているピアが一つしかないため、リストの中にピアは一つしか設定されていませんが、複数のピアがファイルを持っている場合、複数のピアからランダムにいくつかのピアの情報が返されます。返されるピアの数は次の式を元に算出されます。

  (BitTorrentクライアントが要求しているピアの数または、デフォルト値)*(現在ダウンロード中のピア数)/(現在ダウンロード中のピア数+全てダウンロードしているピア数)

ピアの数が十分ない場合は、すべてのピアの情報が返されます。トラッカーによるピアの選択はほとんどランダムに行われます。

トラッカーからピアの情報を取得すると、BitTorrentクライアントは複数のピアからピアを選択して直接ピアにTCP/IPで接続し、お互いがデータを送受信します。

トラッカーと各ピアの通信はHTTPでのクライアント・サーバモデルで動作しますが、その後のファイルのダウンロードは各ピア同士が能動的に通信するピア・ツー・ピアモデルになります。この時の各ピア間でやりとりされるプロトコルがBitTorrentのピアプロトコルです。ピアプロトコルでは、TCP/IPセッション上で双方向にバイナリ形式で直接データをやりとりします。

まず、BitTorrentクライアントが他のピアに接続するとハンドシェークを行います。ハンドシェークは最初の一バイト目が19(16進数で13)で始まり、その後に「Bittorrent protocol」という文字列が続きます。この文字列がピアプロトコルのメッセージで最初のバイトがそのメッセージの長さになります。その次ぎに8バイトの領域が将来的な拡張のために確保されて、0で初期化されています。この拡張領域は現在は使用されていません。その後にトラッカーとの通信で使用したinfo_hashの20バイトのバイナリ値がセットされています。

次に接続先ピアからの応答が返されます。接続先からの応答も接続要求とほとんど同じですが、最後に接続先ピアがトラッカーにアナウンスした20バイトのピアIDが追加されています。応答で返されるinfo_hashの値が接続要求の時に使用したinfo_hashの値と異なる場合には接続は拒否されます。この値のチェックが成功すると接続は完了します。

接続が完了すると、BitTorrentのメッセージが相互に転送されます。メッセージの形式は、次の図のように最初にメッセージ長(int)を表すプレフェックス、次にメッセージのタイプとそれに続くペイロードという構成になっています。メッセージ長0のメッセージは、キープアライブとして使用され、通常無視されます。

メッセージタイプには次の図の8種類が用意されています。

次にハンドシェーク直後のメッセージのやりとりの一部を見てみます。最初のメッセージは、接続先からの送信されてきます。最初の4バイトがメッセージ長で、この例では2バイトを示しています。次のメッセージタイプはbitfieldでです。これは、接続先が持っているピースの一覧になります。f8は2真数で11111000になります。今回の実験で使用したファイルは5つのピースに分割されていました。このため、上位5ビットが有効な範囲になります。ビットがたっている位置がピースを持っていることを示しています。上位5ビット全てがたっているので、接続先は完全なファイルを持っていることになります。

続けて、unchokeメッセージが送信されてきます。choke、unchokeの仕組みは後述します。そして、pieceメッセージによるピースのダウンロードが開始されます。

今見てきたように、BitTorrentのピアプロトコル自体は単純なものです。しかし、各BitTorrentクライアントのピアやファイルピース、転送制御のアルゴリズムによって、お互いが効率的にファイルをダウンロードしあうことができるようになります。

ダウンロードするファイルピースの順番は、ダウンロード効率に大きく影響します。例えば、各ピアにいきわたっていないピースを最後にダウンロードしようとすると、一斉に他のピアもそのピースをダウンロードしようとして、ファイルの転送効率が落ちる可能性があります。そのため、ピースのダウンロード順序は重要になってきます。

BitTorrentではいくつかの4つのピース選択戦略でダウンロード順が決められています。

BitTorrentのピースの選択アルゴリズムの中でも最優先の戦略は、現在ダウンロードしようとしているピースに集中することです。BitTorrentでは、一つのピースに対して16kバイトごとの複数のサブピースに分割してダウンロードします。この時、複数のピアから一つのピースの別々のサブピースをダウンロードすることで、完全なピースにすることに全力を注ぎます。次の図は、ピースをダウンロードしているときのものです。ピースを4kバイトごとのサブピースに分割してダウンロードしているのがわかると思います。

BitTorrentは、完全なピースが取得できるとSHA1ハッシュにより、そのピースの完全性をチェックします。ピースの完全性が保証されると、そのピースはシードとなって、他のピアからのダウンロード対象になります。他のファイル共有ソフトが、一つのファイルを複数のピアから同時ダウンロードして転送効率をあげることが一般的ですが、BitTorrentは一つのファイルを複数のピースにわけることで、他のピアにより早く自分のピースをダウンロードさせようとしています。

ピースが複数のピアからダウンロードされると、次にどのピースをダウンロードするかが問題になります。BitTorrentでは、自分が接続している複数のピアで、各ピアが持っているピースのうちもっとも少ないピースをダウンロードしようとします。ピアが離脱した時に、離脱したピアしか特定のピースを持っていなかった場合、そのピースを取得できなくなる可能性があるため、なるべくピースを分散させようという戦略です。

自分がピアA、B、Cと接続しており、全体としてファイルが5つのピースに分割さていて、Aがピース1,2,3、Bがピース1,2,4,Cがピース3,4,5を持っていた場合、次にダウンロードするピースは5になります。もし、ピース5を取得する前にピアCが終了すると、ピース5を持っているピアを探す必要ができ、転送効率が悪くなります。

希少ピース優先戦略が採用されない例外が一つあります。それは、BitTorrentクライアントの起動直後です。BitTorrentクライアントの起動直後はアップロードするピースが何もありません。そのため、他のピアに一切貢献することができません。他のピアに貢献できるようになるためには、なるべく早く完全なピースを取得して、アップロードできる状態にしなければなりません。希少ピース優先戦略を採用すると、希少ピースを持っているノードが少ないため、同時に一つのピースを複数のピアからダウンロードできなくなり、転送効率が悪くなります。一方、転送効率を優先して、なるべく多くのピアが持っているピースをダウンロードしても、どのピアもそのピースを持っているので、他のピアに貢献することができなくなります。このため、一番最初はランダム戦略を採用しています。ランダム戦略は、ダウンロードするピースを完全にランダムに選択します。BitTorrentでは、下手に難しく考えるよりもある程度の割り切りを採用しています。

ランダム戦略で一端完全なピースが取得できると、次は希少ピース優先戦略が採用されます。

ファイルのダウンロードの最終段階で最後のサブピースのダウンロードをネットワーク帯域の細いピアから行おうとすると、ダウンロードの完了が遅くなる危険があります。この危険を回避するために、ピアが持っていない全てのサブピースのダウンロード要求を、接続している全てのピアに送信します。このため、同じサブピースを複数のピアから同時に冗長的にダウンロードします。どこかのピアから完全なサブピースを受け取ると、ダウンロード要求を送信したピアにダウンロードのキャンセル要求を送信して、ダウンロードを終了します。これは、一時的に大きなネットワーク帯域を消費しますが、一時的で短時間で終わるため大きな問題にはなりません。

このモデルのことをEndGameモデルと名付けられています。1の集中戦略や2の希少ピース優先戦略に比べると、理論的な背景よりも、実際に運用してみての問題を俗人的に解決している印象を受けます。

クライアント・サーバモデルでは、ファイルの供給はサーバが行い、クライアントはサーバからファイルをダウンロードします。

P2Pシステムではファイルの供給者と利用者は各PCに分散され、各PCはファイルの利用者であると同時にファイルの供給者でもあります。つまり、ファイルの需要と供給のバランスの上に成り立っています。このバランスの調整がP2Pでのファイル配信を効率化する上で重要になります。BitTorrentでは、このバランスを囚人のジレンマのしっぺ返し戦略をもとに調整しています。

BitTorrentは、各ピアが自律的にダウンロードを効率化し、アップロード帯域は確保しようとします。つまり、自分の利益は最大にして、他のピアへの貢献はなるべく控えようとします。ただし、他のピアへの貢献を全く行わないと、他のピアへ貢献するピアが全く存在しなくなるため、自分の利益が減ります。このため、自分の利益に貢献してくれたピア(ピースをダウンロードさせてくれたピア)には、恩返しとしてピースのアップロードを許可します。

ダウンロードできるところからダウンロードして、アップロード帯域を確保するためにどのピアへのアップロードを許可するかを各ピアが決めなければなりません。他のピアに貢献するためにはピアはアップロードしなければなりません。貢献しないためにはピアはアップロードを抑制(チョーク)しなければなりません。アップロードを抑制しているとき(チョーク状態)でも、ダウンロードは継続して常にTCP/IPのコネクションは張られています。

よいチョークアルゴリズムであれば、ダウンロード効率が高くて、他のピアへの貢献は少なくてすみます。つまり、ファイルの供給と需要のバランスが最適化されます。

BitTorrentでは、各ピアはアップロードを一定数のピアに対してアップロードを許可(アンチョーク状態)しています。デフォルトでは、アンチョーク状態のピアの数は4つです。接続している複数のピアのうち、アンチョーク状態する4つのピアを選択することが重要になります。

アンチョーク状態するピアの選択は、基本的には現在のダウンロード速度によって決まります。ダウンロード速度は20秒間のダウンロード量の平均を使用します。チョーク状態とアンチョーク状態が頻繁に切り替わると、返って効率が悪くなるため、10秒ごとにアンチョーク状態のピアを選択します。

単純にダウンロード速度だけを元にしたチョーク判定では、もっとよい接続先を見つけ出すことができません。このため、4つのアンチョーク状態のピアのうち、一つのピアには1の基本的なチョークアルゴリズムではなく、楽観的なアンチョーク戦略をとります。楽観的なアンチョーク戦略では、30秒ごとに自分が持っているピアのリストから順番にアンチョーク状態にします。30秒と言う時間も経験的なもので、その時間でピアのアップロードとダウンロードの速度を計測します。

ファイルが完全にダウンロードされていない時に、他のピアに貢献している（ピースをアプロードしている）にもかかわらず、接続しているすべてのピアからチョーク状態にされてることがあります。一分以上アンチョーク状態のピアからピースをまったく取得できなかった場合は、そのピアをチョーク状態にして相手のピアに自分は冷遇されていると意志表示します。この場合、楽観的アンチョーク戦略が働いて、変わりのアンチョーク状態のピアを見つけ出します。

一度冷遇されたピアに対しては、それ以降のチョークアルゴリズムでアンチョーク状態にしないようになります。BitTorrentは意外とねにもつタイプです。

全てのピースのダウンロードが終了すると、ダウンロード速度を元にアンチョーク状態のピアを選択する必要がなくなります。このため、ダウンロード速度を元にした戦略からアップロード速度が早いピアをアンチョーク状態にする戦略に変更します。

こうしたピアが増えることにより、他のピアのダウンロード効率が上昇します。

BitTorrentは優れたP2P型ファイル配信システムで、効率的に動作します。最後に筆者が他のP2Pのファイル共有ソフトに比べて優れていると考える点をまとめます。

P2Pファイル共有ソフトからのウィルスの感染が騒がれている今日、ファイル自体身元保証の仕組みは重要です。ダウンロードしたものが本当に、一次配布元のファイルと同一のものか、ダウンロードの経路の途中でウィルスなどが混入していないかが重要になります。

また、3つめの回転率が高くなることですが、全てをダウンロードしてからアップロードに転じるよりダウンロードしながらアップロードも並行して行うことで、ファイルを供給するピアの数が急激に増えます。つまり、一つのピースさえダウンロードしてしまえば、ピアの数は多ければ多い程、アップロードできるピアが増えます。逆に言うと、ピアの数が少なければBitTorrentのメリットを受けることができません。例えばLinuxのディストリビューションの新しいバージョンが出た直後はアクセスが集中するのでBitTorrentは有効に機能しますが、その後アクセス数が少ない時期ではダウンロード速度や効率はわるく、Webサーバからのダウンロード速度と大差がなくなります。

ファイル配信のシステムとしてBitTorrentは既存のWebなどのシステムを完全に駆逐することはありませんが、それらを補完して効率的な負荷分散を提供することできるでしょう。