摘  要： 以較為流行的網(wǎng)絡(luò)文件下載軟件BitTorrent為例，探討基于對(duì)等網(wǎng)技術(shù)的分布式模式下文件分發(fā)的工作原理，并采用簡(jiǎn)單而有效的算法實(shí)現(xiàn)了大型文件的高效和可靠下載。
　　關(guān)鍵詞： 文件分發(fā)  對(duì)等網(wǎng)  BitTorrent

 　　隨著網(wǎng)絡(luò)的普及，一些基于傳統(tǒng)媒介(光盤(pán)、磁帶等）的信息(影視、音樂(lè)等)逐漸以網(wǎng)絡(luò)作為傳播的媒介。這些網(wǎng)絡(luò)資源往往以較大的文件形式出現(xiàn)，供大家下載。方便、高效且可靠地獲取這類網(wǎng)絡(luò)文件是當(dāng)今網(wǎng)絡(luò)技術(shù)一個(gè)值得探索的課題。隨著連接網(wǎng)絡(luò)的終端數(shù)量急劇增加和網(wǎng)絡(luò)結(jié)構(gòu)的多樣化與復(fù)雜化，傳統(tǒng)的集中式文件分發(fā)模式面臨著伸縮性、連接突發(fā)性和可靠性問(wèn)題，因此迫切需要研究新的應(yīng)用模式。本文將以最近較流行的一種網(wǎng)絡(luò)文件下載軟件BitTorrent為例，討論基于P2P（Peer to Peer）對(duì)等網(wǎng)絡(luò)技術(shù)的分布式文件分發(fā)模式的工作原理和實(shí)用算法。
1  文件分發(fā)的二種模式
1.1 傳統(tǒng)的集中模式
　　傳統(tǒng)的集中式文件分發(fā)模式如圖1所示。當(dāng)有一個(gè)較大的文件要通過(guò)網(wǎng)絡(luò)向位置分散的用戶分發(fā)時(shí)，系統(tǒng)會(huì)把要發(fā)布的文件上傳到Web服務(wù)器或FTP服務(wù)器上，然后通知用戶從該中心服務(wù)器下載文件。服務(wù)器承擔(dān)了全部的上傳(服務(wù)器向下載者傳遞文件）開(kāi)銷，它的處理能力和傳輸速率是影響文件分發(fā)速度的瓶頸。隨著用戶數(shù)量的增多，每個(gè)用戶可獲得的下載速度將會(huì)降低，同時(shí)服務(wù)器也會(huì)因負(fù)載過(guò)大而宕機(jī)。因此很多服務(wù)器都會(huì)限制用戶人數(shù)和下載速度，給用戶帶來(lái)諸多不便。

1.2 基于P2P的分布式模式
　　P2P技術(shù)認(rèn)為所有互聯(lián)的設(shè)備互為對(duì)等體。由于用戶與服務(wù)器之間的連接是雙向的，用戶彼此之間也是可以互相訪問(wèn)的，所以，當(dāng)多個(gè)用戶同時(shí)下載同一個(gè)文件時(shí)，他們可以互相上傳已經(jīng)下載的文件的一部分。這樣重新分配向用戶上傳的開(kāi)銷之后，將大大減輕服務(wù)器的壓力，從而可以克服集中模式的缺點(diǎn)。這種基于P2P的分布式文件的分發(fā)模式如圖2所示。BitTorrent實(shí)現(xiàn)了這種分布式文件分發(fā)模式。

　　BitTorrent的基本工作原理是：在把文件上傳到服務(wù)器之前把它分成N個(gè)部分（塊）。假設(shè)用戶甲在服務(wù)器隨機(jī)下載了第i個(gè)塊，用戶乙在服務(wù)器隨機(jī)下載了第j個(gè)塊，則用戶甲的BitTorrent就會(huì)根據(jù)情況從用戶乙下載第j個(gè)塊，而用戶乙的BitTorrent就會(huì)根據(jù)情況從用戶甲下載第i個(gè)塊。這樣不但減輕了服務(wù)器的負(fù)載，也加快了用戶（甲和乙）的下載速度，提高了效率，還減少了地域之間的限制。例如用戶丙從服務(wù)器下載的速度可能很慢，但是從距離較近的用戶甲和用戶乙下載的速度就會(huì)快很多。所以與傳統(tǒng)的模式不同，用BitTorrent下載時(shí)用戶越多，下載速度越快。
1.3 技術(shù)難點(diǎn)
　　基于P2P技術(shù)的分布式文件分發(fā)模式有著優(yōu)良的伸縮性，但是如何保證效率和可靠性是其面臨的技術(shù)難題。具體來(lái)說(shuō)，需要解決下述幾個(gè)問(wèn)題。
　　(1)為了保證對(duì)等體（用戶）能夠盡快得到所需的文件，需要有效找出哪些對(duì)等體已有文件的哪些部分以及它們應(yīng)該被送到哪里。
　　(2)對(duì)等體的連接是隨機(jī)的，經(jīng)常只有幾分鐘。因此，實(shí)際的部署要考慮這個(gè)因素。
　　(3)為了維持網(wǎng)絡(luò)的穩(wěn)定，理論上所有對(duì)等體下載速度的總和應(yīng)該等于上傳速度的總和。即既需要保證對(duì)等體的下載速度，又要使每個(gè)對(duì)等體的下載速度與它們的上傳速度相當(dāng)。
　　(4)要盡量避免文件的某些部分落在極少數(shù)對(duì)等體中，而可能被永久丟失(擁有這些部分的對(duì)等體不再提供上傳）。
　　下面從原理入手探討B(tài)itTorrent是如何采用簡(jiǎn)單實(shí)用的算法解決這些問(wèn)題。
2 BitTorrent的技術(shù)框架
2.1 部  署
　　為建立一個(gè)BitTorrent式的文件分發(fā)部署，需要將一個(gè)帶.torrent擴(kuò)展名的靜態(tài)文件放到Web服務(wù)器上。該文件一般只有幾百KB，包含待下載的文件信息，如文件長(zhǎng)度、文件名、哈希數(shù)據(jù)和跟蹤器的URL。跟蹤器使用基于HTTP的非常簡(jiǎn)單的協(xié)議幫助對(duì)等體互相發(fā)現(xiàn)對(duì)方。在該協(xié)議中，對(duì)等體發(fā)出的請(qǐng)求消息包含要下載的文件信息和監(jiān)聽(tīng)的端口號(hào)等。跟蹤器返回的響應(yīng)消息包括正在下載同一個(gè)文件的對(duì)等體的信息。對(duì)等體根據(jù)這些信息彼此建立連接。為了使文件可以被下載，最初必須啟動(dòng)一個(gè)被稱為“種子”的對(duì)等體，它至少有該文件的一個(gè)拷貝。
2.2 分發(fā)機(jī)制
　　跟蹤器是對(duì)等體彼此發(fā)現(xiàn)的惟一途徑。通常，標(biāo)準(zhǔn)的跟蹤器算法返回一個(gè)隨機(jī)的對(duì)等體列表。這種隨機(jī)列表有非常好的健壯性。許多對(duì)等體選擇算法能夠共同形成一個(gè)有用的規(guī)則圖，綜合這些信息就能找到所需要的分塊信息。注意，所有對(duì)等體之間的連接是雙向傳輸?shù)摹?br /> 　　為了跟蹤每個(gè)對(duì)等體有哪些文件塊，BitTorrent把文件分割成固定長(zhǎng)度的塊，典型的長(zhǎng)度是256KB。每個(gè)對(duì)等體向它的所有對(duì)等體（對(duì)等體群）報(bào)告自己擁有哪些塊。為了校驗(yàn)數(shù)據(jù)的完整性，所有塊的數(shù)據(jù)經(jīng)SHA1哈希算法處理后被放在.torrent文件中。只有驗(yàn)證了一個(gè)塊的哈希數(shù)據(jù)之后，對(duì)等體才能報(bào)告它有這個(gè)塊。這種簡(jiǎn)單的方法被證明是可行的。
　　對(duì)等體從它們能連接到的對(duì)等體群下載塊。有時(shí)對(duì)等體群可能沒(méi)有它們想要的塊，或者當(dāng)前不允許它們下載。這種禁止對(duì)等體下載的策略（即阻塞）將在后面討論。讓對(duì)等體通告自己擁有哪些文件塊消耗的帶寬低于10%，但卻可以保證對(duì)等體利用其全部上傳能力。
2.3 請(qǐng)求的流水線
　　BitTorrent通過(guò)TCP傳遞數(shù)據(jù)。為避免2個(gè)塊發(fā)送之間的延遲總是保持幾個(gè)待處理的請(qǐng)求。BitTorrent通過(guò)在線上把塊進(jìn)一步分割成更小的子塊來(lái)充分利用這一優(yōu)點(diǎn)。子塊的典型長(zhǎng)度是16KB，并且總是保留一定數(shù)量，一般是5個(gè)。一旦有請(qǐng)求待發(fā)，立即被流水線化。這樣，每到達(dá)1個(gè)子塊，就有1個(gè)請(qǐng)求馬上被送出。
2.4 塊選擇算法
　　若選擇塊按照合適的順序下載將得到較高的性能；否則，會(huì)導(dǎo)致無(wú)法上傳所有的塊，或不能上傳某些塊。
2.4.1 優(yōu)先級(jí)
　　BitTorrent首選的塊選擇策略是：一旦某個(gè)子塊被請(qǐng)求，則它所屬塊的剩余子塊的請(qǐng)求將先于其他塊的子塊。這樣使對(duì)等體能夠盡可能快地獲得完整的塊。
2.4.2 稀有優(yōu)先原則
　　在選擇哪一個(gè)對(duì)等體作為下一個(gè)被下載對(duì)象時(shí)，對(duì)等體一般先下載自己的對(duì)等體群稀有的塊，該技術(shù)被稱為稀有優(yōu)先原則。這是為了確保對(duì)等體總是擁有它們的對(duì)等體群想要的塊，一旦需要就能開(kāi)始上傳。該技術(shù)也能確保那些較常見(jiàn)的塊被推遲上傳，以留住那些正在提供上傳的對(duì)等體，從而獲得那些較常見(jiàn)的塊。
　　信息理論指出直到種子上傳了文件的所有部分，下載才能完成。對(duì)于那些只有一個(gè)種子的部署，該種子的上傳能力略低于N個(gè)用戶的當(dāng)前速度和，顯然當(dāng)用戶從種子下載不同的塊時(shí)性能最好。由于每個(gè)對(duì)等體能獲知它的對(duì)等體群有種子已經(jīng)上傳的塊，因此稀有優(yōu)先原則在只從種子下載新塊時(shí)很有效。
　　對(duì)于有些部署，若原始的種子最終因?yàn)殚_(kāi)銷的原因宕機(jī)，只留下在線的用戶去上傳，則有可能導(dǎo)致某個(gè)特定的塊再也無(wú)法從任何在線的用戶那里得到。而稀有優(yōu)先原則會(huì)盡可能快地復(fù)制稀有塊，以避免此類問(wèn)題的產(chǎn)生。
2.4.3 尾塊的處理
　　文件的末尾塊有時(shí)會(huì)被非常低速的對(duì)等體請(qǐng)求，這不會(huì)影響下載的完成，但可能會(huì)延長(zhǎng)完成下載所用的時(shí)間。為了避免這種情況發(fā)生，如果對(duì)等體還沒(méi)有所請(qǐng)求塊的所有子塊，則向所有的對(duì)等體發(fā)出這些子塊的請(qǐng)求。一旦某子塊到達(dá)，就立即發(fā)送取消該子塊的消息以避免發(fā)送不必要的請(qǐng)求。
3  阻塞算法
　　在P2P分布式模式中，所有對(duì)等體之間的連接是雙向的，即每個(gè)對(duì)等體在下載數(shù)據(jù)的同時(shí)也可以向其他對(duì)等體上傳數(shù)據(jù)。BitTorrent采用分布式的資源分配策略。每個(gè)對(duì)等體從它的對(duì)等體群以最快速度下載所請(qǐng)求的塊，同時(shí)，它可以自主地通過(guò)一種算法（阻塞算法）選擇向哪些對(duì)等體提供上傳服務(wù)。起初，每個(gè)連接的上傳方向是被禁止的（即阻塞），因此每個(gè)對(duì)等體要向其他對(duì)等體上傳數(shù)據(jù)之前就必須清除阻塞。阻塞是暫時(shí)拒絕上傳，而下載仍然繼續(xù)。因此，當(dāng)要清除阻塞時(shí)，不需要重新建立連接。
　　阻塞算法不是BitTorrent通信協(xié)議的一部分，但對(duì)于取得好的性能是必要的。好的阻塞算法會(huì)利用所有可用的資源，為所有對(duì)等體提供一致的下載速度，并且在某種程度上阻止對(duì)等體只下載而不上傳。
　　一般，每個(gè)對(duì)等體總是清除固定數(shù)量（缺省值為4）的對(duì)等體的阻塞，所以需要確定要清除哪些對(duì)等體的阻塞。清除哪些對(duì)等體的阻塞是嚴(yán)格基于當(dāng)前的下載速度。為了避免因?yàn)閷?duì)等體快速的阻塞和清除阻塞而浪費(fèi)資源，要求每個(gè)對(duì)等體每10秒重新計(jì)算一次阻塞誰(shuí)。而10秒足夠TCP把新的傳輸速度提高到最大。
　　如果每個(gè)對(duì)等體只是簡(jiǎn)單地把當(dāng)前提供最佳下載速度的其他對(duì)等體作為上傳的對(duì)象，則無(wú)法知道當(dāng)前未被使用的連接的速度是否比正在使用的連接的速度更快。因此，任何時(shí)候每個(gè)對(duì)等體在它的對(duì)等體群中都指定一個(gè)作為“樂(lè)觀的清除阻塞”對(duì)等體，即總是清除對(duì)該對(duì)等體的阻塞而不考慮它當(dāng)前的下載速度。對(duì)等體群中的對(duì)等體以30秒（3個(gè)阻塞期）為周期依次被指定為“樂(lè)觀的清除阻塞”對(duì)象。而30秒足夠連接的雙方把上傳和下載速度提高到極限。
4  結(jié)束語(yǔ)
　　目前，BitTorrent已經(jīng)被廣泛地應(yīng)用，常?？梢詾閹装賯€(gè)并發(fā)的下載者提供幾百兆字節(jié)的文件服務(wù)。實(shí)踐證明這種新型的基于P2P技術(shù)的文件分發(fā)模式具有良好的伸縮性、高效率和可靠性，克服了傳統(tǒng)集中模式的困難，促使網(wǎng)絡(luò)應(yīng)用的核心從中央服務(wù)器向終端設(shè)備擴(kuò)散，使用戶在Internet上的共享行為被提到更高層次，用戶以更主動(dòng)的方式參與到網(wǎng)絡(luò)活動(dòng)中。這必將促進(jìn)更多新應(yīng)用的開(kāi)發(fā)。
參考文獻(xiàn)
1 Cohen B.Incentives Build Robustness in BitTorrent.http：//bitconjurer.org/Bit Torrent/bittorrentecon.pdf，2003
2 劉寶旭，李雪瑩，于傳松等.對(duì)等網(wǎng)技術(shù)及應(yīng)用概述.計(jì)算機(jī)工程與應(yīng)用，2003；（6）