BitTorrent 性能卓越的原因

概要
BitTorrent 文件發(fā)布系統(tǒng)采用針?shù)h相對(duì)（tit_for_tat）的方法來(lái)達(dá)到帕累托有效，與當(dāng)前已知的協(xié)作技術(shù)相比，它具有更高的活力。本文將解釋BitTorrent 的用途，以及是怎樣用經(jīng)濟(jì)學(xué)的方法來(lái)達(dá)到這個(gè)目標(biāo)的。

1、BitTorrent 用來(lái)做什么？
當(dāng)通過(guò)HTTP協(xié)議來(lái)下載一個(gè)文件的時(shí)候，所有的上載開(kāi)銷都在主機(jī)上。而使用 BitTorrent，當(dāng)多個(gè)人同時(shí)下載同一個(gè)文件的時(shí)候，他們之間也相互為對(duì)方提供文件的部分片斷的下載。這樣，就把上載的開(kāi)銷分?jǐn)偟矫總€(gè)下載者那里，也就可以在理論上支持無(wú)限多個(gè)下載者來(lái)下載同一個(gè)文件。
研究人員以前也在尋找一種達(dá)到這種效果的可實(shí)用的技術(shù)[3]。這種技術(shù)原來(lái)并沒(méi)有在大的范圍內(nèi)運(yùn)用過(guò)，因?yàn)檫壿嫼偷膯?wèn)題非常棘手。如果僅僅計(jì)算哪些 peers 擁有文件的哪些片斷以及這些片斷應(yīng)該被發(fā)送給誰(shuí)，那么很難只產(chǎn)生比較小的系統(tǒng)開(kāi)銷。Peers之間的連接很少會(huì)超過(guò)幾個(gè)小時(shí)，通常是幾分鐘而已。最后，有一個(gè)普遍的問(wèn)題，就是公平性。
我們將解釋BitTorrent 是如何很好的解決這些問(wèn)題的。

1.1、BitTorrent接口
BitTorrent 的接口可能是最簡(jiǎn)單的。用戶點(diǎn)擊希望下載的文件的超級(jí)鏈接，然后會(huì)彈出一個(gè)標(biāo)準(zhǔn)的“保存到”對(duì)話框。此后，出現(xiàn)一個(gè)下載進(jìn)度的窗口，在這個(gè)窗口中，除了顯示下載速率外，還顯示一個(gè)上載速率。BT在使用上非常簡(jiǎn)單，使得BT能廣泛的被運(yùn)用。

1.2、部署
決定采用BitTorrent的原因是因?yàn)橛幸恍┪募枰l(fā)布。而下載者使用 BitTorrent，是因?yàn)檫@是他們獲取所需要的文件的唯一途徑。下載者經(jīng)常一完成下載，就停止為別人上載，雖然說(shuō)，在BT 客戶端完成下載之后，繼續(xù)為別人提供一段時(shí)間的上載是一種禮貌的行為。標(biāo)準(zhǔn)的實(shí)現(xiàn)是讓客戶端一直保持上載，除非窗口被關(guān)閉。
在一個(gè)典型的部署中，未完成的下載者
一臺(tái)主機(jī)負(fù)責(zé)提供原始的文件，下載者通過(guò)BT來(lái)下載這個(gè)文件。下載者在下載的同時(shí)，為其它人提供上載，最后，離開(kāi)這個(gè)系統(tǒng)。

2、技術(shù)框架

2.1發(fā)布內(nèi)容
為了部署 BT，首先將一個(gè)擴(kuò)展名為 .torrent 的文件放在一個(gè)普通的web服務(wù)器上。.torrent文件包含了要共享的文件的信息，包括文件名、大小、文件的散列信息和一個(gè)指向tracker的url。Tracker負(fù)責(zé)幫助下載者能夠獲取其它下載者的信息。Tracker和下載者之間使用一種很簡(jiǎn)單的基于HTTP的協(xié)議進(jìn)行交互，下載者告訴tracker自己要下載的文件、自己使用的端口以及類似的信息，tracker告訴下載者其它下載同樣文件的下載者的聯(lián)系信息。下載者利用這些信息相互之間建立連接。一個(gè)被成為“種子”的下載者，必須首先被啟動(dòng)，它知道完整的文件信息。對(duì)tracker和web服務(wù)器的帶寬需求很低，而種子必須至少發(fā)送原始文件的一份完整拷貝。

譯注：
P2P的核心思想就是沒(méi)有服務(wù)器的概念，任何一個(gè)下載者既是client，又是server。
下載者從別人那里取文件的時(shí)候，稱為下載，而為別人提供文件的時(shí)候，稱為上載（傳）。
為了完成一次部署，至少需要一個(gè) tracker和一個(gè)seed。所謂tracker，是一個(gè)服務(wù)器，負(fù)責(zé)幫助peers之間相互建立連接。而seed，通常是第一個(gè)向tracker注冊(cè)，然后它就開(kāi)始進(jìn)入循環(huán)，等待為別人提供文件，也就是說(shuō)，第一個(gè)seed只負(fù)責(zé)上傳文件。一旦有一個(gè)peer向tracker注冊(cè)后，就可以取得seed的信息，從而與seed建立連接。從seed處讀取文件。由于原始的文件，只有seed擁有，所有說(shuō)，seed至少要上傳原始文件的一份完整拷貝。如果又有一個(gè)peer加入進(jìn)來(lái)，那么它可以同時(shí)和seed和前一個(gè)peer建立連接，然后從這兩者處獲取文件。

2.2對(duì)等發(fā)布
所有和文件下載相關(guān)的邏輯問(wèn)題，通過(guò) peers之間的交互來(lái)解決。一些關(guān)于下載和上傳的速率的信息被發(fā)送給tracker，tracker搜集這些信息用于統(tǒng)計(jì)。Tracker的職責(zé)被嚴(yán)格限定為“幫助peers相互發(fā)現(xiàn)對(duì)方”。
盡管tracker是peers之間相互發(fā)現(xiàn)的唯一途徑，也是peers之間相互協(xié)作的唯一地點(diǎn)，標(biāo)準(zhǔn)的tracker算法返回一個(gè)隨機(jī)的 peers的列表。隨機(jī)圖具有非常強(qiáng)大的特性，許多的peer選擇算法最終產(chǎn)生了一個(gè)冪律圖，冪律圖能以少量的攪拌來(lái)獲得分片。注意，peers之間的連接都是雙向傳輸?shù)摹?br>為了跟蹤每個(gè)peers都擁有什么，BT將文件切割為固定大小的片（典型的大小是256k）。每個(gè)下載者必須通知其它peers，它擁有哪些片。為了驗(yàn)證文件的完整性，對(duì)每個(gè)片斷都通過(guò)SHA1算法計(jì)算出它的hash信息，并保存在torrent文件中。Peers只有在檢查了片斷的完整性之后，才會(huì)通知其它peers它擁有這個(gè)片斷。刪除代碼是一種被建議使用的幫助文件分布的技術(shù)，但是這種更簡(jiǎn)單的方法（既分片）也是可用的。
Peers不斷的從它能連接到的peers那里下載文件片斷。當(dāng)然，它不能從沒(méi)有跟它建立連接的peers那里下載任何東西。即使是建立了連接的peers，有的也并不包含它想要的片斷，或者還不允許它去下載。關(guān)于不允許其它peers從它那里下載文件片斷的策略，被稱為 阻塞choking，后文將進(jìn)行討論。其它關(guān)于文件分布的方法通常都要用到麻煩的樹(shù)結(jié)構(gòu)，而且樹(shù)葉的上載能力并沒(méi)有被利用起來(lái)。簡(jiǎn)單的讓 peers 宣布它擁有什么會(huì)導(dǎo)致不到 10 % 的帶寬開(kāi)支，卻可以可靠的使用所有的上載能力。

2.3流水作業(yè)
構(gòu)架在TCP之上的應(yīng)用層協(xié)議，例如BT，很重要的一點(diǎn)是應(yīng)該同時(shí)發(fā)送多個(gè)請(qǐng)求，以避免在兩個(gè)片斷發(fā)送之間的延遲，因?yàn)槟菢訒?huì)嚴(yán)重影響傳輸速率。為了達(dá)到這種目的，BT將每個(gè)片斷又進(jìn)一步分為子片斷，每個(gè)子片斷的大小一般是16k，同時(shí)，它一直保持幾個(gè)請(qǐng)求（通常是5個(gè)）被流水的同時(shí)發(fā)送。流水作業(yè)所選擇的data（應(yīng)該是指的同時(shí)發(fā)送的請(qǐng)求數(shù)目，也就是5個(gè)request）的依據(jù)是能使得大多數(shù)連接變得飽和。
譯注：也就是說(shuō)，每次發(fā)送5個(gè)請(qǐng)求，然后過(guò)一段時(shí)間，又發(fā)送5個(gè)請(qǐng)求。流水作業(yè)在HTTP 協(xié)議1.1版本中被廣泛運(yùn)用。

2.4片斷選擇
選擇一個(gè)好的順序來(lái)下載片斷，對(duì)提高性能非常重要。一個(gè)差的片斷選擇算法可能導(dǎo)致所有的片斷都處于下載中，或者另一種情況，沒(méi)有任何片斷被上載給其它 peers。

2.4.1嚴(yán)格的優(yōu)先級(jí)
片斷選擇的第一個(gè)策略是：一旦請(qǐng)求了某個(gè)片斷的子片斷，那么該片斷剩下的子片斷優(yōu)先被請(qǐng)求。這樣，可以盡可能快的獲得一個(gè)完整的片斷

2.4.2最少的優(yōu)先
對(duì)一個(gè)下載者來(lái)說(shuō)，在選擇下一個(gè)被下載的片斷時(shí)，通常選擇的是它的peers們所擁有的最少的那個(gè)片斷，也就是所謂的“最少優(yōu)先”。這種技術(shù)，確保了每個(gè)下載者都擁有它的peers們最希望得到的那些片斷，從而一旦有需要，上載就可以開(kāi)始。這也確保了那些越普通的片斷越放在最后下載，從而減少了這樣一種可能性，即某個(gè)peer當(dāng)前正提供上載，而隨后卻沒(méi)有任何的被別人感興趣的片斷了。

譯注：
也就說(shuō)說(shuō)，每個(gè)peer都優(yōu)先選擇整個(gè)系統(tǒng)中最少的那些片斷去下載，而那些在系統(tǒng)中相對(duì)較多的片斷，放在后面下載，這樣，整個(gè)系統(tǒng)就趨向于一種更優(yōu)的狀態(tài)。如果不用這種算法，大家都去下載最多的那些片斷，那么這些片斷就會(huì)在系統(tǒng)中分布的越來(lái)越多，而那些在系統(tǒng)中相對(duì)較少的片斷仍然很少，最后，某些 peer 就不再擁有其它 peer 感興趣的片斷了，那么系統(tǒng)的參與者越來(lái)越少，整個(gè)系統(tǒng)的性能就下降。
在BT系統(tǒng)中，充分考慮了經(jīng)濟(jì)學(xué)的概念，處處從整個(gè)系統(tǒng)的性能出發(fā)，參與者越多，系統(tǒng)越優(yōu)化。

信息理論顯示除非種子上傳了文件的所有片斷，否則沒(méi)有任何下載者可以完成所有文件的下載。如果在一個(gè)部署中，只有一個(gè)種子，而且種子的上載能力比它的大多數(shù)下載者都要差，那么，不同的下載者從種子那里下載不同的片斷，性能就會(huì)變得比較好，因?yàn)?，重?fù)的下載浪費(fèi)了種子獲取更多信息的機(jī)會(huì)。“最少優(yōu)先”使得下載者只從種子處下載新的片斷（也就是整個(gè)系統(tǒng)中其它peer都沒(méi)有的片斷），因?yàn)?，下載者能夠看到其它peers那里已經(jīng)有了種子已經(jīng)上傳的片斷。

在某些部署中，原始的種子由于某些原因最終關(guān)閉，只好由剩下的這些下載者們來(lái)負(fù)責(zé)上傳。這樣顯然會(huì)帶來(lái)一個(gè)風(fēng)險(xiǎn)：某些片斷任何一個(gè)下載者都不擁有。“最少優(yōu)先”也很好的處理了這種情況。通過(guò)盡快的復(fù)制最少的片斷，減少了這種由于當(dāng)前的peers停止上載后帶來(lái)的風(fēng)險(xiǎn)。

2.4.3隨機(jī)的第一個(gè)片斷
“最少優(yōu)先”的一個(gè)例外是在下載剛開(kāi)始的時(shí)候。此時(shí)，下載者沒(méi)有任何片斷可供上傳，所以，需要盡快的獲取一個(gè)完整的片斷。而最少的片斷，通常只有某一個(gè)peer擁有，所以，它可能比多個(gè)peers都擁有的那些片斷下載的要慢。因此，第一個(gè)片斷是隨機(jī)選擇的，直到第一個(gè)片斷下載完成，才切換到“最少優(yōu)先”的策略。

2.4.4最后階段模式
有時(shí)候，從一個(gè)速率很慢的peer那里請(qǐng)求一個(gè)片斷。在下載的中間階段，這不是什么問(wèn)題，但是卻可能潛在的延遲下載的完成。為了防止這種情況，在最后階段，peer向它的所有的peers們都發(fā)送某片斷的子片斷的請(qǐng)求，一旦某些子片斷到了，那么就會(huì)向其它peer發(fā)送cancel 消息，取消對(duì)這些子片斷的請(qǐng)求，以避免帶寬的浪費(fèi)。實(shí)際上，用這種方法并沒(méi)有浪費(fèi)多少帶寬，而文件的結(jié)束部分也一直下載的非常快。

3 阻塞（choking）算法
BT并不集中分配資源。每個(gè)peer自己有責(zé)任來(lái)盡可能的提高它的下載速率。Peers從它可以連接的peers處下載文件，并根據(jù)對(duì)方提供的下載速率給予同等的上傳回報(bào)（你敬我一尺，我敬你一丈）。對(duì)于合作者，提供上傳服務(wù)，對(duì)于不合作的，就阻塞對(duì)方。所以說(shuō)，阻塞是一種臨時(shí)的拒絕上傳策略，雖然上傳停止了，但是下載仍然繼續(xù)。在阻塞停止的時(shí)候，連接并不需要重新建立。
阻塞算法并不屬于BT對(duì)等協(xié)議（指peers 之間交互的協(xié)議）的技術(shù)部分，但是對(duì)提高性能是必要的。一個(gè)好的阻塞算法應(yīng)該利用所有可用的資源，為所有下載者提供一致可靠的下載速率，并適當(dāng)懲罰那些只下載而不上傳的peers。

3.1帕累托有效
帕累托有效是指資源配置已達(dá)到這樣一種境地，即任何重新改變資源配置的方式，都不可能使一部分人在沒(méi)有其他人受損的情況下受益。這一資源配置的狀態(tài)，被稱為“帕累托最優(yōu)”（Pareto optimum）狀態(tài)，或稱為“帕累托有效”（Pareto efficient）
在計(jì)算機(jī)領(lǐng)域，尋求帕累托有效是一種本地優(yōu)化算法
BitTorrent的阻塞算法，用一種針?shù)h相對(duì)的方式來(lái)試圖達(dá)到帕累托最優(yōu)。（原文不太好翻譯，我簡(jiǎn)化了）。Peers對(duì)那些向他提供上傳服務(wù)的peers給予同樣的回報(bào)，目的是希望在任何時(shí)候都有若干個(gè)連接正在進(jìn)行著雙向傳輸。

3.2 BitTorrent的阻塞算法
從技術(shù)層面上說(shuō)，BT的每個(gè)peer一直與固定數(shù)量的其它 peers 保持疏通（通常是4個(gè)），所以問(wèn)題就變成了哪些peers應(yīng)該保持疏通？這種方法使得TCP的擁塞控制性能能夠可靠的飽和上傳容量。（也就是說(shuō)，盡量讓整個(gè)系統(tǒng)的上傳能力達(dá)到最大）。
嚴(yán)格的根據(jù)當(dāng)前的下載速率來(lái)決定哪些peers應(yīng)該保持疏通。令人驚訝的是，計(jì)算當(dāng)前下載速率是個(gè)大難題。當(dāng)前的實(shí)現(xiàn)實(shí)質(zhì)上是一個(gè)每隔20秒的輪詢。而原來(lái)的算法是對(duì)一個(gè)長(zhǎng)時(shí)間的網(wǎng)絡(luò)傳輸進(jìn)行總計(jì)，但這種方法很差勁，因?yàn)橛捎谫Y源可用或者不可用，帶寬會(huì)變化的很快。
為了避免因?yàn)轭l繁的阻塞和疏通 peers造成的資源浪費(fèi)，BT每隔10秒計(jì)算一次哪個(gè)peer需要被阻塞，然后將這種狀態(tài)保持到下一個(gè)10秒。10秒已經(jīng)足夠使得TCP來(lái)調(diào)整它的傳輸性能到最大。

3.3、optimistic unchoking
如果只是簡(jiǎn)單的為提供最好的下載速率的peers們提供上載，那么就沒(méi)有辦法來(lái)發(fā)現(xiàn)那些空閑的連接是否比當(dāng)前正使用的連接更好。為了解決這個(gè)問(wèn)題，在任何時(shí)候，每個(gè)peer都擁有一個(gè)稱為“optimistic unchoking”的連接，這個(gè)連接總是保持疏通狀態(tài)，而不管它的下載速率是怎樣。每隔30秒，重新計(jì)算一次哪個(gè)連接應(yīng)該是“optimistic unchoking”。30秒足以讓上載能力達(dá)到最大，下載能力也相應(yīng)的達(dá)到最大。這種和針?shù)h相對(duì)類似的思想非常的偉大。“optimistic unchoking”非常和諧的與“囚徒困境”合作。

3.4、反對(duì)歧視
某些情況下，一個(gè)peer可能被它所有的peers都阻塞了，這種情況下，它將會(huì)保持較低的下載速率直到通過(guò)“optimistic unchoking”找到更好peers。為了減輕這種問(wèn)題，如果一段時(shí)間過(guò)后，從某個(gè)peer那里一個(gè)片斷也沒(méi)有得到，那么這個(gè)peer認(rèn)為自己被對(duì)方“怠慢”了，于是不再為對(duì)方提供上傳，除非對(duì)方是“optimistic unchoking”。這種情況頻繁發(fā)生，會(huì)導(dǎo)致多于一個(gè)的并發(fā)的“optimistic unchoking”。

3.5僅僅上傳
一旦某個(gè)peer完成了下載，它不能再通過(guò)下載速率（因?yàn)橄螺d速率已經(jīng)為0了）來(lái)決定為哪些 peers 提供上載了。目前采用的解決辦法是，優(yōu)先選擇那些從它這里得到更好的上載速率的peers。這樣的理由是可以盡可能的利用上載帶寬。

4、真實(shí)世界的體驗(yàn)
BitTorrent不僅僅早已經(jīng)實(shí)現(xiàn)，而且早已經(jīng)被廣泛的使用，它為許多并發(fā)的下載者提供成百兆的文件下載。已知的最大的部署中，同時(shí)有超過(guò)1000個(gè)的下載者。當(dāng)前的瓶頸（實(shí)際還沒(méi)有達(dá)到）看來(lái)是tracker的帶寬。它（trakcer的帶寬）大概占用了帶寬總量的千分之一，一些小的協(xié)議擴(kuò)展可能會(huì)使它降到萬(wàn)分之一。

參考資料：

[1] E. Adar and B. A. Huberman. Free riding on gnutella. First Monday, 5(10), 2000.
[2] A.-L. Barab´asi. Linked: The New Science of Networks.Perseus Publishing, 2002.
[3] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. Splitstream: High-bandwidth content distribution in cooperative environments. In Proceedings of IPTPS03, Berkeley, USA, Feb. 2003.
[4] P. Maymounkov and D. Mazieres. Kademlia: A peer-to-peer information system based on the xormetric. In Proceedings of IPTPS02, Cambridge, USA, Mar. 2002.

原文見(jiàn):http://tb.blog.csdn.net/TrackBack.aspx?PostId=376238