BT的基本運作原理

原貼 http://mmdays.wordpress.com/2007/04/06/bt1/

由於原貼已經連不進了，其它地方又參差不齊，還好數年前有備份，於2014年5月25日，轉貼至此。

透視BT（一）­­── BT的基本運作原理

Posted by Mr. Friday

談到BT，相信大家都不陌生。沒錯，今天要來談的就是這幾年在網路上非常重要，已經快要變成全民運動的──BT程式。筆者有鑒於BT已經變成非常火紅的應用程式，但是了解這個程式的基本運作原理與影響的人卻寥寥無幾，於是決定撰寫這個主題；本篇會先介紹BT的源起與運作原理，接下來的幾篇則會根據這一兩年學術上對BT的觀察，介紹BT在各種使用情境下對網路行為的影響（當中包含一些相當出人意表的發現）。

BitTorrent，簡稱BT，由Bram Cohen於2002年獨立完成其核心程式碼的撰寫。從Bram Cohen簡陋而陽春的個人網頁上看來，他於1993年進入紐約州立大學就讀，輟學之後陸續做過研究員、網路程式設計師，就履歷上看來並不是非常特出，2002年間他發表的BT一開始也沒有獲得很大的關注。隔年五月他把BT的理論基礎寫成一篇簡短五頁的學術文章發表在「Workshop on Economics of Peer-to-Peer Systems, 2003」上，文章本身沒有知名教授的背書、用字遣辭顯然也不夠精練，然而這篇文章至今卻已累積了474篇的reference數。2004年六月時，據CNN報導，BT已經佔據了網路上所有P2P流量的53%。至今，BT程式檔的下載量已經超過一億三千五百萬人次，而這些數字還不包含網路上經其他使用者修改過的版本，如BitComet、BitSpirit…等等。



Bram Cohen照片，在他blog裡還有各種用電腦變形過後的照片，例如變身成美少女戰士的樣子。

就Mr. Friday自己的觀察，BT程式已經成為眾多網路鄉民平日不可或缺的「資料來源」之一，就算沒有使用過，或多或少也會在生活中聽到相關的用語，比如說torrent檔、種子、斷種等等術語。更有甚者，許多網路應用也開始使用BT的模式，比如說某些Linux的ISO檔、魔獸世界WOW的更新檔就是透過BT方式在網路上散佈，也有一些網路電視程式是從BT處得到靈感來源，例如現在相當火紅的PPStream。

BT最讓人驚奇的地方在於下載的速度極快。使用過的人都曉得，BT下載往往比傳統的FTP、網頁下載來得快很多。這當中的原理可以從下圖解釋：



左圖是FTP與HTTP下載的基本原理，道理很簡單，擁有檔案的人負責將檔案傳送給所有想下載檔案的人。假設今天的同時下載這個檔案的人有三個（A、B、C），則每個人的下載速度就是檔案擁有者上傳速度的1/3。

BT的原理就比較複雜一點。擁有檔案（例如File.txt）的人（稱為種子）會將檔案切很多很多的小塊（例如File1.txt、File2.txt、…、File100.txt），每當有人（假設也叫A）想下載檔案時，種子（或者其他的下載者）就把一部份的小塊檔案寄給這個A，A就拿著這些檔案片段去跟另外一個也在下載的人B、C說：「Hey！我有一部分的小檔案，你也有一部分的小檔案，我們來互相交換彼此沒有的部分吧！」。對於A來說，他就可以同時從種子與B、C處抓取檔案片段，因此下載的速度就會變快，而不僅限於種子頻寬的1/3。如果今天網路上的下載者不只2個，而是成千上萬，那麼理論上A的速度就可以一飛千里。透過這個「下載者互通有無」的想法，讓下載的速度來得比以往的FTP、HTTP還快。

BT對於分享檔案的種子也有好處。以往如果要讓所有的下載者都抓到檔案，種子就不能下線，直到所有人都抓完檔案為止。頻寬的消耗也是單方面的：只消耗種子的上傳頻寬，因此常常造成種子端的網路塞車。BT就不會這樣：只要網路上出現另外一個把整個檔案都下載成功的人，等於就是出現另外一個新種子，原來的種子就可以下線休息去了──甚至不用等到新種子出現！沿用前例，原先的種子把檔案片段1~3給了A，片段4~6給了B，片段7~10給了C，那麼就算種子下線休息去了，ABC之間仍然能夠透過互通有無的機制，把檔案下載成功。BT一方面減輕了單一種子的負擔，另一方面也延長了檔案的壽命－就算原先種子離開了，如果A、B、C當中有人志願留下來等到新下載者D出現，那麼檔案就能繼續流傳下去。

當然，要讓這套機制成功，還有幾個配套的措施：

（1） Torrent檔與Tracker：

由於BT中的種子、下載成員一直在變動，必須要有方法讓其他新成員找到他們，因此就出現了Torrent檔與Tracker。Tracker是個小程式，紀錄著目前所有下載成員的名單與網路位置。Torrent檔則是紀錄Tracker的位置與檔案片段的全部名稱。因此對於新成員來說，他首先要獲得的就是一個torrent檔，從torrent檔中他知道tracker的位置，然後再經由tracker與其他下載成員取得聯繫。

（2） Rarest First Policy

為了增進檔案分享的速度，每個成員會盡量分享網路上最少見的檔案片段。例如A擁有片段1、2、3，B擁有2、4、5，C擁有1、3、5，則網路上最罕見的是片段4，因此若有人想向B互通有無，B會優先傳給他片段4。

（3） Choking Policy

當一個檔案很流行的時候，一個BT系統可能會同時擁有成千上萬的下載者。A身為一個參與者，必定會收到非常多人希望跟他交換檔案的請求。但是A的頻寬很小，只允許同時上傳給4個人（在BT最初原始程式裡預設是4；其他軟體的設定就不一定了，我知道BitComet之前是10個），那麼A要如何決定拒絕這當中的誰呢？這叫做choking（拒絕）policy。BT的做法是：接受（unchoke）那些現在正上傳檔案給我、而且速度最快的前4個人！BT的Choking Policy至為重要，因為它傳達出一種「施比受更有福」的概念：願意付出更多上傳頻寬的人，將會收到其他人的回報－更快的下載速度。日後有許多關於BT的研究，都是針對這個特性作一番探討。

（4） Optimistic Unchoking

承續前述的理念，想要獲得更快的下載速度，就應該先將檔案分享給別人。Optimistic Unchoking是說，每個人每30秒就挑網路中任意一個人，將檔案上傳給他。這麼作的用意是發掘網路上未知的潛力檔案提供者：假如A與K之前並未有檔案的往來，但其實這兩個人住得很近，網路互傳的速度比其他人快。今天A透過Optimistic Unchoking隨機給K上傳了一些檔案片段，讓K驚覺A的上傳速度很快，進而允許A從K處下載檔案片段。如果A與K之間的連線速度很慢，那麼過30秒之後，A會停止提供檔案給K，而去別處尋找下一個候選人。

透過上述的幾種機制，Bram Cohen成功的開發出一套獨特的下載技術，也讓BT成為近幾年來最流行的話題，網路上更逐漸出現許多以BT為核心，內容卻略有不同的幾套下載軟體，如前述BitComet、BitSpirit等。這些軟體多少在技術上修改了BT，比如說改變檔案傳輸時使用的port、改變同時最多上傳人數等等，但技術的基本概念卻是不變的：透過鼓勵分享，達到更快的下載速度。

接下來的幾篇，會引述幾篇學術上研究BT機制的論文，讓我們看看BT這套機制透過長時間實驗與數學流體模型、機率模型、排隊模型、賽局理論……等等的驗證下，在各方面的效能如何？這些論文又會給我們什麼啟示？敬請大家拭目以待，下回再見。

返回主篇 → BT BitTorrent 基本 運作 原理 主篇

20140525 update this article