關(guān)于 BitTorrent 的 Fast Extension 你必須要知道的

Fast Extension 協(xié)議擴(kuò)展的開(kāi)啟方式,需要在 BitTorrent 握手協(xié)議中設(shè)置一位特定的二進(jìn)制位來(lái)開(kāi)啟。在 BitTorrent 握手協(xié)議中的保留字節(jié)(reserved byte)的第三個(gè)最低有效位(third least significant bit)設(shè)置為 1,即將其與 0x04 進(jìn)行按位或運(yùn)算,來(lái)啟用 Fast Extension 。例如:
reserved[7] |= 0x04
如果連接的兩端都設(shè)置了這一位,那么 Fast Extension 就會(huì)被啟用,并且可以使用其中的四個(gè)擴(kuò)展功能:Have None/Have All 、 Reject Requests 、 Suggestions 和 Allowed Fast 。
需要注意的是,F(xiàn)ast Extension 只有在支持該協(xié)議擴(kuò)展的兩個(gè) BitTorrent 客戶端之間建立連接時(shí)才能生效。否則,即使設(shè)置了這一位,也無(wú)法啟用 Fast Extension 。
BitTorrent 協(xié)議中消息的語(yǔ)法指定所有整數(shù)都是四個(gè)字節(jié)的大端序,并且所有消息都以一個(gè)整數(shù)的消息長(zhǎng)度開(kāi)始。此外,它還指定除 Keep-Alive 外的所有消息將具有單個(gè)字節(jié)的操作碼和零個(gè)或多個(gè)依賴于操作碼的參數(shù)。聲明應(yīng)按照 IETF RFC 2119 中所述的方式解釋某些關(guān)鍵詞(MUST 、 MUST NOT 、 REQUIRED 、 SHALL 、 SHALL NOT 、 SHOULD 、 SHOULD NOT 、 RECOMMENDED 、 MAY 和 OPTIONAL)。這意味著這些單詞具有在 RFC 中定義的特定含義,它們用于指示對(duì)特定動(dòng)作或行為的要求或建議水平。例如,“MUST” 表示必須遵循某項(xiàng)要求,“SHOULD” 則表示應(yīng)該遵循某項(xiàng)建議,除非存在充分理由不這樣做。
現(xiàn)有消息語(yǔ)義的修改
Fast Extension 對(duì)請(qǐng)求(Request)、阻塞(Choke)、取消阻塞(Unchoke)和取消請(qǐng)求(Cancel)消息的語(yǔ)義進(jìn)行修改,并添加了一個(gè)拒絕請(qǐng)求(Reject Request)消息?,F(xiàn)在,每個(gè)請(qǐng)求都保證只會(huì)收到一個(gè)響應(yīng),即相應(yīng)的拒絕或相應(yīng)的 piece 消息。即使請(qǐng)求被取消,接收到取消請(qǐng)求的節(jié)點(diǎn)也應(yīng)該發(fā)送相應(yīng)的拒絕或相應(yīng)的 piece :正在處理中的請(qǐng)求仍然允許完成。阻塞不再隱含地拒絕所有掛起的請(qǐng)求,從而消除了一些可能導(dǎo)致重復(fù)請(qǐng)求不必要的 piece 的競(jìng)爭(zhēng)條件。此外,如果一個(gè)節(jié)點(diǎn)收到了一個(gè)從未請(qǐng)求的 piece ,那么它必須關(guān)閉連接。
Have All/Have?None
*Have All*: <len=0x0001> <op=0x0E>
? ? ?*Have None*: <len=0x0001><op=0x0F>
? ? ?這兩種消息都包含一個(gè)長(zhǎng)度為 1 字節(jié)的整數(shù)和一個(gè)操作碼,其中 "Have All" 的操作碼是 0x0E,"Have None" 的操作碼是 0x0F 。當(dāng)存在這兩個(gè)消息時(shí),它們會(huì)替換掉 “Have Bitfield” 消息。在握手之后,必須恰好出現(xiàn)一個(gè) “Have All” 、"Have None" 或 "Have Bitfield" 中的一個(gè)。
“Have All” 和 “Have None” 是 BitTorrent 協(xié)議中的消息類(lèi)型,表示發(fā)送方已經(jīng)擁有所有或者沒(méi)有任何 piece 。當(dāng)存在這兩個(gè)消息時(shí),它們會(huì)替換掉 “Have Bitfield” 消息。在握手之后,必須恰好出現(xiàn)一個(gè) “Have All” 、”Have None” 或 “Have Bitfield” 中的一個(gè)。
這些消息的目的是為了節(jié)省帶寬,并且避免沒(méi)有 piece 時(shí)不發(fā)送任何消息的特殊情況。當(dāng) Fast Extension 被禁用時(shí),如果某個(gè)節(jié)點(diǎn)接收到 “Have All” 或 “Have None” 消息,則該節(jié)點(diǎn)必須關(guān)閉連接。
建議性 Piece
*Suggest Piece*: <len=0x0005><op=0x0D><index>
“Suggest Piece“ 是一個(gè)建議性的消息,意味著” 您可能想要下載這個(gè) piece” 。它的預(yù)期用途是為了在不降低吞吐量的情況下進(jìn)行超級(jí)共享(super-seeding1),以避免重復(fù)下載,并使磁盤(pán) I/O 受限的種子可以上傳連續(xù)或相同的數(shù)據(jù)塊,以避免過(guò)多的磁盤(pán)查找。在所有情況下,種子應(yīng)該操作以在網(wǎng)絡(luò)中維護(hù)大致相等數(shù)量的每個(gè)塊的副本。
對(duì)于任何給定時(shí)間,節(jié)點(diǎn)可以發(fā)送多個(gè)”Suggest Piece” 消息。如果接收方收到多個(gè)”Suggest Piece” 消息,則可能會(huì)將其解釋為表示所有建議的塊都同樣適合下載。
當(dāng)禁用 Fast Extension 時(shí),如果一個(gè)節(jié)點(diǎn)收到了一個(gè)”Suggest Piece” 消息,則該節(jié)點(diǎn)必須關(guān)閉連接。
Reject Request?拒絕請(qǐng)求
*Reject Request*: <len=0x000D><op=0x10><index><begin><length>
? ? ?通過(guò)發(fā)送這個(gè)消息,Peer 可以告訴其他 Peer 自己無(wú)法提供所請(qǐng)求的數(shù)據(jù)塊。接收方在收到該消息后,會(huì)將相應(yīng)的請(qǐng)求從隊(duì)列中刪除,并嘗試向其他 Peer 請(qǐng)求相同的數(shù)據(jù)塊。
Reject Request 用于通知請(qǐng)求方,它所請(qǐng)求的數(shù)據(jù)塊無(wú)法被滿足。
如果 Fast Extension 沒(méi)有啟用,且一個(gè)節(jié)點(diǎn)接收到了 Reject Request 消息,則該節(jié)點(diǎn)必須關(guān)閉與請(qǐng)求方之間的連接。
啟用 Fast Extension 時(shí),節(jié)點(diǎn)在處理 Reject Request 消息時(shí)的規(guī)范行為:
如果一個(gè)節(jié)點(diǎn)接收到一個(gè)未曾發(fā)送請(qǐng)求的 Reject Request 消息,則它應(yīng)該關(guān)閉與發(fā)出該消息的節(jié)點(diǎn)之間的連接。
當(dāng)一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)發(fā)送 Choke 消息時(shí),它必須拒絕該節(jié)點(diǎn)發(fā)出的所有請(qǐng)求,除非這些請(qǐng)求涉及允許的快速集合中的數(shù)據(jù)塊。節(jié)點(diǎn)應(yīng)該先 choke 再拒絕請(qǐng)求,這樣收到 Choke 消息的節(jié)點(diǎn)不會(huì)重新請(qǐng)求那些被 choke 的數(shù)據(jù)塊。
如果一個(gè)節(jié)點(diǎn)收到了來(lái)自被 choke 的節(jié)點(diǎn)的請(qǐng)求,則它會(huì)拒絕該請(qǐng)求,除非所請(qǐng)求的數(shù)據(jù)塊在允許的快速集合中。
如果一個(gè)節(jié)點(diǎn)收到了太多來(lái)自被 choke 的節(jié)點(diǎn)的請(qǐng)求,則它可以選擇關(guān)閉連接而不是拒絕這些請(qǐng)求。但是,要考慮到一旦一個(gè)節(jié)點(diǎn)被 choke,緩沖區(qū)可以需要幾秒鐘才能排空并且消息傳播才能完成。因此,需要在決定關(guān)閉連接之前仔細(xì)考慮這個(gè)問(wèn)題。
Allowed Fast
*Allowed Fast*: <len=0x0005><op=0x11><index>
使用指定的 BitTorrent 協(xié)議,新加入的節(jié)點(diǎn)由于缺少數(shù)據(jù)片段,需要等待一段時(shí)間才能與其他節(jié)點(diǎn)進(jìn)行有效的文件共享。在這個(gè)過(guò)程中,節(jié)點(diǎn)可能會(huì)不斷地被 choke(阻止上傳),導(dǎo)致共享效率降低。
為了解決這個(gè)問(wèn)題,BitTorrent 協(xié)議中引入了 “Allowed Fast” 消息。這個(gè)消息告訴其他節(jié)點(diǎn),即使自己處于 choke 狀態(tài),也可以向它請(qǐng)求某些數(shù)據(jù)片段,并保證會(huì)立即響應(yīng)。這樣,其他節(jié)點(diǎn)就可以更快地獲取到需要的數(shù)據(jù),而新加入節(jié)點(diǎn)也可以更快地開(kāi)始參與 tit-for-tat 的交換過(guò)程,從而提高整個(gè)網(wǎng)絡(luò)的文件共享效率。
在這個(gè)協(xié)議中,當(dāng)一個(gè)節(jié)點(diǎn)擁有某個(gè)文件的一部分時(shí),它可以把這些 piece 分享給其他節(jié)點(diǎn)。當(dāng)其他節(jié)點(diǎn)需要下載這個(gè)文件時(shí),它們可以從那個(gè)節(jié)點(diǎn)處請(qǐng)求這些 piece,以便更快地完成文件的下載。
而 “Allowed Fast 集合” 則是指每個(gè)節(jié)點(diǎn)所允許請(qǐng)求的一組 piece 的集合。為了保證所有節(jié)點(diǎn)之間的數(shù)據(jù)請(qǐng)求都是公平的,在協(xié)議中使用了一個(gè)經(jīng)過(guò)驗(yàn)證的生成算法來(lái)生成這個(gè)集合。這個(gè)算法會(huì)為每個(gè)接收消息的節(jié)點(diǎn)生成唯一的 piece 索引,使得當(dāng)兩個(gè)節(jié)點(diǎn)都提供了 k 個(gè) piece 時(shí),它們所能夠請(qǐng)求的 piece 的數(shù)量也是相同的;如果其中一個(gè)節(jié)點(diǎn)提供了 k+1 個(gè) piece,則請(qǐng)求數(shù)量也會(huì)相應(yīng)增加一個(gè)。 k 的值應(yīng)該足夠小以避免濫用,但又足夠大以實(shí)現(xiàn) “以牙還牙” 的策略。作者目前將 k 的默認(rèn)值設(shè)置為 10,但節(jié)點(diǎn)可以自由更改這個(gè)數(shù)字,以適應(yīng)不同的負(fù)載情況。
發(fā)送方可以在 Allowed Fast 消息中列出它還沒(méi)有實(shí)際擁有的 pieces ,接收方不能根據(jù) Allowed Fast 消息認(rèn)為發(fā)送方確實(shí)擁有這些 pieces 。這樣做的目的是為了允許節(jié)點(diǎn)在連接開(kāi)始時(shí)生成和通信允許快速集合。然而,發(fā)送方隨時(shí)都可以發(fā)送 Allowed Fast 消息。
一個(gè)節(jié)點(diǎn)如果有足夠的資源,應(yīng)該向任何一個(gè)起始節(jié)點(diǎn)發(fā)送 Allowed Fast 消息,以提高其他節(jié)點(diǎn)下載文件分塊的速度。但是,在某些情況下,節(jié)點(diǎn)可以拒絕已經(jīng)發(fā)送了 Allowed Fast pieces 的請(qǐng)求,例如本地節(jié)點(diǎn)資源不足、請(qǐng)求的 pieces 已經(jīng)發(fā)送給請(qǐng)求的節(jié)點(diǎn)、或者請(qǐng)求節(jié)點(diǎn)并非一個(gè)起始節(jié)點(diǎn)。此外,當(dāng)前實(shí)現(xiàn)的規(guī)則還規(guī)定了一種情況,即當(dāng)請(qǐng)求節(jié)點(diǎn)已經(jīng)下載了超過(guò) k 個(gè) pieces 時(shí),請(qǐng)求被拒絕。
當(dāng) Fast 擴(kuò)展被禁用時(shí),只要節(jié)點(diǎn)收到了 Allowed Fast 消息,它就沒(méi)有能力處理這種消息,因此必須斷開(kāi)與發(fā)送方的連接。這個(gè)規(guī)則的目的是確保協(xié)議的兼容性和正確性,保證所有節(jié)點(diǎn)都能夠按照相同的規(guī)則進(jìn)行通信,從而實(shí)現(xiàn)文件分塊的有效下載和傳輸。
Allowed Fast Set?機(jī)制
計(jì)算對(duì)等節(jié)點(diǎn)的快速列表的標(biāo)準(zhǔn)算法中所有的整數(shù)都是四個(gè)字節(jié)(32 位)的網(wǎng)絡(luò)字節(jié)序(大端序)。 [a:b] 表示從 a 到 b 的連續(xù)字節(jié)序列,不包括 b,即 (a, a+1, a+2,…, b-1) 。 x[a:b] 表示數(shù)組 x 中從索引 a 開(kāi)始到索引 b(但不包括 b)的子序列。
計(jì)算網(wǎng)絡(luò)地址的方法。其中,“ip” 代表 P’*s IPv4 地址。該方法目前不支持 IPv6 地址。如果對(duì)等方在 NAT 后面,則 “ip” 應(yīng)為 NAT 的外部 IP 地址。由于發(fā)送 “Allowed Fast” 消息的節(jié)點(diǎn)計(jì)算集合,因此通常正確的 “ip” 是連接另一端的 “ip” 地址。計(jì)算集合的主機(jī)可以根據(jù)需要使用連接另一端的 “ip” 地址。簡(jiǎn)而言之,這意味著,在計(jì)算集合時(shí),可以選擇使用連接另一端的 IP 地址作為計(jì)算中的 IP 地址,而不一定是自己的 IP 地址。
用 “sz” 代表種子文件中分片的數(shù)量。而 “a” 代表允許快速下載的集合,該集合包含一些不在正常下載順序中的分片。最后,“k” 代表被允許以快速方式下載的分片數(shù)量,即允許快速下載的集合中所包含的分片數(shù)目。
x = 0xFFFFFF00 & ip ? ? ? ? ? ? ? ? ? ? ? ? ? (1)
? ? ?x.append(infohash) ? ? ? ? ? ? ? ? ? ? ? ? ? ?(2)
? ? ?while |a| < k:
? ? ? ?x = SHA1(x) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3)
? ? ? ?for i in [0:5] and |a| < k: ? ? ? ? ? ? ? ? (4)
? ? ? ? ?j = i*4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5)
? ? ? ? ?y = x[j:j+4] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(6)
? ? ? ? ?index = y % sz ? ? ? ? ? ? ? ? ? ? ? ? ? ?(7)
? ? ? ? ?if index not in a: ? ? ? ? ? ? ? ? ? ? ? ?(8)
? ? ? ? ? ?add index to a ? ? ? ? ? ? ? ? ? ? ? ? ?(9)
第一步(1)選擇節(jié)點(diǎn) P’*s 的 IP 地址中最重要的八位字節(jié)。這樣可以防止同一個(gè)網(wǎng)絡(luò)上的用戶獲得多個(gè) Allowed Fast Set 。使用三個(gè)字節(jié)是基于經(jīng)驗(yàn)和歷史原因的。
第三步(3)在每個(gè)調(diào)用上生成一個(gè) 20 字節(jié)的隨機(jī)數(shù)。通過(guò)對(duì)前一次迭代的哈希執(zhí)行 SHA-1 哈希,我們可以生成任意長(zhǎng)度的偽隨機(jī)序列。
步驟(4)到(9)將 20 字節(jié)哈希劃分為若干片段索引,并將其添加到允許快速集合中。簡(jiǎn)單來(lái)說(shuō),該過(guò)程將隨機(jī)數(shù)分成了 5 個(gè) 4 字節(jié)的片段,并將每個(gè)片段作為指向表示內(nèi)容不同部分的索引集合中的一個(gè)索引。如果該索引尚未被添加到允許快速集合中,則將其添加到集合中。這確保只有擁有特定索引的一部分節(jié)點(diǎn)才能被選入 “允許快速” 節(jié)點(diǎn)集合。
Example Implementation 示例實(shí)現(xiàn)
以下的 C++ 實(shí)現(xiàn)由 CacheLogic 提供
void generate_fast_set(
?uint32 k, ? ? // number of pieces in set
?uint32 sz, ? ?// number of pieces in torrent
?const char infohash[20], // infohash of torrent
?uint32 ip, // in host byte order, ie localhost is 0x7f000001
?std::
vector<uint32> &a) // generated set of piece indices
{
? a.clear();
? std::string x;
? char buf[4];
? *(uint32*)buf = htonl(ip & 0xffffff00);
? x.assign(buf, 4);
? x.append(infohash, 20); // (3)
? while (a.size()<k) {
? ? x = SHA1(x); // (4)
? ? for ( int i=0 ; i<5 && a.size()<k; i++ ) { // (5)
? ? ? int j = i*4; // (6)
? ? ? uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7)
? ? ? uint32 index = y % sz; // (8)
? ? ? if (std::find(a.begin(), a.end(), index)==a.end()) { // (9)
? ? ? ? a.push_back(index); // (10)
? ? ? }
? ? }
? }
}
此函數(shù)生成的示例結(jié)果:
7 piece allowed fast set for torrent with 1313 pieces and hex infohash
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
?1059,431,808,1217,287,376,1188
9 piece allowed fast set for torrent with 1313 pieces and hex infohash
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
?1059,431,808,1217,287,376,1188,353,508
總結(jié)
BitTorrent 的 Fast Extension(簡(jiǎn)稱 FAST)是一種加速下載的協(xié)議擴(kuò)展,它能夠顯著提高文件下載速度。 FAST 利用了一些技術(shù)手段來(lái)優(yōu)化下載過(guò)程,如多線程下載、數(shù)據(jù)塊預(yù)取和請(qǐng)求重排等。
具體地說(shuō),F(xiàn)AST 通過(guò)請(qǐng)求多個(gè)數(shù)據(jù)塊,并在這些數(shù)據(jù)塊到達(dá)之前對(duì)它們進(jìn)行排序以減少延遲,從而使下載更快。此外,F(xiàn)AST 還利用多線程下載技術(shù),同時(shí)從不同的上傳者處獲取數(shù)據(jù)塊,進(jìn)一步提高下載速度。
需要注意的是,F(xiàn)AST 只適用于支持該協(xié)議擴(kuò)展的 BitTorrent 客戶端之間的通信,因此如果你使用的客戶端不支持 FAST,那么即使有其他客戶端支持該協(xié)議擴(kuò)展,也無(wú)法加速你的下載。
參考鏈接
http://www.bittorrent.org/beps/bep_0006.html
https://blog.imfile.io/zh_cn/2023/06/13/bittorrent-xie-yi-gui-fan/