作者の書いた技術文書を読んでいると、アーキテクチャと言いつつ実装テクニックぎりぎりみたいな記述が混じったりしています。個人的には、こういう態度は好きで、好感が持てます(注2)。英語はあまり読みやすいとは思えませんが。


*かなり大雑把な動作イメージ
一般的なP2Pファイル交換とBTでは、解決しようとしている領域が異なります(注3)。
BTはファイルを探索(検索)する部分には焦点を当てていません。ノード群がある特定のファイルを求めている時、そのノード群に、いかに素早くファイルを行き渡らせるか(配布)、に機能を絞っています。

モデル的な説明をすると、与えられた初期状態と遷移は次のようになります(注4)。
リ ンク(線)で結ばれたノード群を考えます。最初に、いくつかのseedノードにファイルを渡します。各ノードはファイルを細切れ(ピースに分割)にしま す。ノードは、リンクを通してファイルの断片を交互に受け渡します。最終的に全ノードが全断片を手にいれられると終了です。
この協調動作をいかに効率良く行うかがポイントです。リンク上を、ファイルの断片がみっしりと行き交うように動作できることを目指しています。


*思想的な部分
次のふたつはBTの思想的な部分を特徴づけています。
+ 効率の追求
+ tit-for-tat戦略(囚人のジレンマの有名な戦略)(注5)

BTはファイルを行き渡らせることの効率を最優先しています。

ここはぼくの印象ですが、初期状態から安定解まで一気につっ走る解法のチューニングに命をかけているように感じました。
その他、TCPの性質(こういう話)にも気を使ったアーキテクチャにしていることが自慢気に書かれています。とにかく、効率第一、という態度が一貫しています。

tit -for-tat戦略は、Bram Cohen(作者)がいたるところでBTの思想的バックボーンとして引用しています。簡単に言うと、ダウンロードで恩恵を受けたら、アップロードでお返し する戦略です。P2Pファイル交換で問題になる「ただ乗り(Free riding)に対する解答のようです。


*動作ステップ
ファイルを配布したい人は、最初にいくつか準備をする必要があります。この辺は、よくあるP2Pファイル交換ソフトとは違う部分です。

以 下、ファイルを配布したい人を配信者と呼びます。配信者は、あらかじめ配布ファイルの信用できる情報をまとめた.torrentファイルを作成して公開し ます。.torrentファイルは、後で述べるtrackerのURLや、配布ファイルのSHA1(ハッシュ値)を含みます。正確には、配布ファイルは ピース(断片)に分断されるので、各ピースのSHA1値です(注6)。

分散システムには、一般に「信用(認証)の環」のブートストラップ的な問題があります。BTは、「.torrentファイルは信用する」ことをgivenとすることで問題を解決(回避?)しています。

BTのクライアント(ファイルを手にいれたい人。以下、単にピアと呼びます)は、.torrentファイルをWebなどで取得して、tracker(実体はWebサーバ)にアクセスします。
ピアとtrackerの間は、HTTPで通信します。
ピアは自分の状態(IPアドレスやポート番号など)を時々trackerに報告して、他のピアの状態を教えてもらいます(注7)。trackerはBTに参加している全ピアの状態を把握しています。
ピ アは、trackerから教えてもらったピアのリストに対して、TCPのセッションを張ります。ファイルのやりとり(ピースをお互いにダウンロード、アッ プロードし合う)は、ピア間のTCPセッション上で行います。ここの通信プロトコルはBTの独自プロトコルです(注8)。


*アルゴリズムの各論
効率を上げるためのポイントは、次のふたつの領域に大別されます。
+ ピースの選択。ピースをどういう順序でダウンロードすべきか? ノード群のレベルで見ると、いかにピースをばらけさせるか?
+ ピアの選択。ダウンロード、アップロードするピアをどう選択するか?

** ピースの選択アルゴリズム
*** 最優先事項
ピースを取り始めたら、他のピースに目移りせず、そのピース全体の取得を最優先します。
ピースは固定長で、全長が揃って初めてSHA1の検証を行うことができます。この段階でアップロード(誰かからダウンロードされる)の対象になります。このため、ピースの全長を揃えることが、ダウンロード時の最優先事項となります。

*** Rarest First戦略
他のピアが持っていないピースを優先的にダウンロードしようと試みます。ちょっと面白い戦略かもしれません。ピースをノード間にばらけさせるための戦略です。本当に機能するかは微妙な気もしますが。

*** Random First Piece戦略
最初のダウンロード時は、rarest first戦略では無く、とりあえず適当なピースの全長を揃えます。

*** endgame mode戦略
最後のピースを遅いピアからダウンロードし始めてしまうと、ダウンロード完了が有意に遅くなる危険があります。
こ れを避けるため、最後のピースの残り部分へのダウンロード要求を全ピアに出すモードがあります。こうして、一番速いピアから最後のピースを取得してダウン ロードを完了します。最後のピースを揃えたら、キャンセルを送り、ダウンロード要求を取り消します。あまり美しいとは言えないアルゴリズムですが、名前が 恰好良いので許しましょう。


** ピアの選択アルゴリズム
*** choke
chokeとは、接続ピアに対して アップロードを禁止することです(ダウンロードは行います)。アップロードにネットワーク帯域を取られすぎてもいけないですし、ダウンロードばかりに専念 してBT全体が機能しなくなっては本末転倒、という微妙なバランスのために使う機能です。
実装上、同時に4つのunchokeピア接続を持つようです。逆に言うと、4つ以外の接続ノードはchoke状態なので、ダウンロードだけしてアップロードは行いません。
今から説明するピアの選択戦略は、「4つのunchokeピアをどう選択するか」、に帰着します。

***tit-for-tat戦略
ダウンロードの速いピアをunchokeします(アップロードを許します)。BTの基本動作です。

いくつか実装上の工夫があるようです。
ダウンロード速度(rate)の計測は、20秒の平均を使っているようです(長い時間の平均は良くなかったという経験則が語られています)。
chokeとunchokeが頻繁に切り替わると効率が落ちるので、10秒おきに切り替えるようになっています。

*** optimistic unchoking
tit-for-tat戦略を続けていると、もっと良い接続の有効利用を見逃す危険があります。
このため、一定期間(30秒)おき順々(rotate)に、接続ピアに対してunchokeするアルゴリズムが組み込まれています。
一種の、局所最適からの脱出手段です。

*** anti-snubbing
(これ、良く分かりません)
tit-for-tat戦略の元では、全接続ピアからchokeされるピアがでてくる危険があります。つまり、どこからもダウンロードできなくなります。
こ れに対する防衛策がanti-snubbingらしいのですが、説明が良く分かりません。一定期間、ダウンロードを許してくれないピアに対しては、 unchokeしない(=ダウンロードさせない)、とも読めるのですが、これで何が解決できるか分かりません(お互いがchokeしあう(首を締めあう) だけのような...)。

* upload only
ダウンロードを完了したピアはtit-for-tat戦略を止めて、アップロード速度が速いピアをunchokeするモードにシフトします。
BT内にこういうピアが増えた段階で、新規のピアが飛び込んでくると、速いピア群から並行ダウンロードできるので、快適だと思います(注9)。


2004/5/25のblogを加筆修正して公開


*リンク集
+ 本家
+ 学生?のレポート
+ MLへのBram Cohenの書き込み(アーキテクチャがまだまだ流動的なことが分かります)
+プレゼン資料
+ 作者Bram Cohenのホームページ
+ Bram Cohenの別サイト?
+ BitTorrent News
+ BTのトラフィック分析
+ BitTorrent FAQ

** 日本語
+BT Mania: かなり充実したwikiサイト
+BitTorrent News: 日本語のBitTorrentニュースサイト
+プロトコル仕様書の翻訳
+BitT.マイン.ヌー: 各種BTクライアントの紹介があります
+psychic.goo:1008: BTを追いかけていたblog。残念ながら更新停止。

** オリジナル以外の実装
+Azureus: Java実装。本家より先にDHTを実装。
+BitComet: C++実装。

脚注
注1. 技術メモ
実はソースを参照しているのではなく、公開文書を読んだだけのメモです。なので、嘘や古い情報があるかもしれません。いずれ、Python勉強を兼ねて、勉強会でソースを読むのもありかもしれません。

注2. 実装テクニック
実装テクニックは重要です。実装テクニックをアーキテクチャより不当に低く位置づけるのは間違っていると思っています(手を動かさない人間にありがちな態度)。

注3. P2Pの応用
ぼ く自身、この3年で、P2Pの解釈のスタンスを微妙に変えつつあります。昔は、探索(検索)してピアを見つければ、その後はエンドトゥーエンドの通信で す、という言い方をしていました。今は、P2Pを「多ノードによる協調実行環境」と解釈しています。探索は、協調動作で行う行為のone of themというとらえ方です。

注4. 状態遷移
初期状態や遷移という説明の仕方は、BTの一般的な説明ではないので注意してください。ぼくがBTから受けた印象で使っている説明方法です。

注5. tit-for-tat戦略
囚人のジレンマ(The Prisoner's Dilemma)で、有効とされている戦略です。
詳しくはWebで探せば色々と見つかると思いますが、簡単に説明すると、次のような戦略です。
+ 寛容に始めて、相手が寛容なら寛容に、相手が裏切ったら裏切る戦略。
これを見て、弱気と見るか強気と見るかは、その人の人間性にかかわるので興味深いところです。

注6. ピースのデフォルトサイズ
ピースは固定長です。
昔は1MByteで、今(v3.1以降)は256KByteになったようです。変更理由は知りません。

注7. trackerから教えてもらうピアのリスト
全ピアのリストではなく、ランダムなリストを返す実装になっているようです。下手な選択アルゴリズムより、ランダムに返す方が良いということらしいです。

注8. BTの通信プロトコル
「ピースID、(ピース内の)offset、length」でダウンロード要求を出して、その結果を受け取るのが基本動作です。

注9. upload onlyのピア
upload だけのピアは、ある意味、ボランティア状態です。義務は無いので、当然ながらピアの離脱は自由です。ピアがどんどん離脱していくと、最終的にはseedピ ア(配布ファイルの全体を持っているピア)だけになります。seedピアが離脱した時、BTが機能するかどうかは運次第です。参加ピア内の全ピースが配布 ファイルの全体を構成できればBTは機能します。足りなければダメです。
BT全体で1ピースだけ足りないとかだと悲惨です。