摘要：其中，文件信息里有以下內(nèi)容區(qū)指定該種子包含的文件數(shù)量文件大小及目錄結(jié)構(gòu)，包括目錄名和文件名字段指定頂層目錄名字每個段的大小協(xié)議把一個文件分成很多個小段，然后分段下載段哈希值將整個種子種，每個段的哈希值拼在一起。

【前五篇】系列文章傳送門：

網(wǎng)絡(luò)協(xié)議 10 - Socket 編程（上）：實踐是檢驗真理的唯一標(biāo)準(zhǔn)

網(wǎng)絡(luò)協(xié)議 11 - Socket 編程（下）：眼見為實耳聽為虛

網(wǎng)絡(luò)協(xié)議 12 - HTTP 協(xié)議：常用而不簡單

網(wǎng)絡(luò)協(xié)議 13 - HTTPS 協(xié)議：加密路上無盡頭

網(wǎng)絡(luò)協(xié)議 14 - 流媒體協(xié)議：要說愛你不容易

????“兄弟，有種子嗎？”
????“什么種子？小麥種嗎？”
????“......，來，哥今天帶你認(rèn)識下什么是種子”。

????大家說起種子，應(yīng)該都知道是用來下載資源的。那么資源下載都有哪些方式？種子下載又有什么優(yōu)勢呢？

????第一種是通過 HTTP 進(jìn)行下載。這種方式，有過經(jīng)歷的人應(yīng)該體會到，當(dāng)下載文件稍大點，下載速度簡直能把人急死。

????第二種方式就是是通過 FTP（文件傳輸協(xié)議）。FTP 采用兩個 TCP 連接來傳輸一個文件。

控制連接。服務(wù)器以被動的方式，打開眾所周知用于 FTP 的端口 21，客戶端則主動發(fā)起連接。該連接將命令從客戶端傳給服務(wù)器，并傳回服務(wù)器的應(yīng)答。常用的命令有：lsit - 獲取文件目錄，reter - 取一個文件，store - 存一個文件；

數(shù)據(jù)連接。每當(dāng)一個文件在客戶端與服務(wù)器之間傳輸時，就創(chuàng)建一個數(shù)據(jù)連接。

????在 FTP 的兩個 TCP 連接中，每傳輸一個文件，都要新建立一個數(shù)據(jù)連接?；谶@個數(shù)據(jù)連接，F(xiàn)TP 又有兩種工作模式：主動模式（PORT）和被動模式（PASV），要注意的是，這里的主動和被動都是站在服務(wù)器角度來說的。工作模式過程如下：

主動模式工作流程

客戶端隨機(jī)打開一個大于 1024 的端口 N，向服務(wù)器的命令端口 21 發(fā)起連接，同時開放 N+1 端口監(jiān)聽，并向服務(wù)器發(fā)出“port N+1” 命令；

由服務(wù)器從自己的數(shù)據(jù)端口 20，主動連接到客戶端指定的數(shù)據(jù)端口 N+1。

被動模式工作流程

客戶端在開啟一個 FTP 連接時，打開兩個任意的本地端口 N（大于1024）和 N+1。然后用 N 端口連接服務(wù)器的 21 端口，提交 PASV 命令；

服務(wù)器收到命令，開啟一個任意的端口 P（大于 1024），返回“227 entering passive mode”消息，消息里有服務(wù)器開放的用來進(jìn)行數(shù)據(jù)傳輸?shù)亩丝谔?P。

客戶端收到消息，取得端口號 P，通過 N+1 端口連接服務(wù)器的 P 端口，進(jìn)行數(shù)據(jù)傳輸。

????上面說了 HTTP 下載和 FTP 下載，這兩種方式都有一個大缺點-難以解決單一服務(wù)器的帶寬壓力。因為它們使用的都是傳統(tǒng) C/S 結(jié)構(gòu)，這種結(jié)構(gòu)會隨著客戶端的增多，下載速度越來越慢。這在當(dāng)今互聯(lián)網(wǎng)世界顯然是不合理的，我們期望能實現(xiàn)“下載人數(shù)越多，下載速度不變甚至更快”的愿望。

????后來，一種創(chuàng)新的，稱為 P2P 的方式實現(xiàn)了我們的愿望。

????P2P 就是 peer-to-peer。這種方式的特點是，資源一開始并不集中存儲在某些設(shè)備上，而是分散地存儲在多臺設(shè)備上，這些設(shè)備我們稱為 peer。

????在下載一個文件時，只要得到那些已經(jīng)存在了文件的 peer 地址，并和這些 peer 建立點對點的連接，就可以就近下載文件，而不需要到中心服務(wù)器上。一旦下載了文件，你的設(shè)備也就稱為這個網(wǎng)絡(luò)的一個 peer，你旁邊的那些機(jī)器也可能會選擇從你這里下載文件。

????通過這種方式解決上面 C/S 結(jié)構(gòu)單一服務(wù)器帶寬壓力問題。如果使用過 P2P2 軟件，例如 BitTorrent，你就會看到自己網(wǎng)絡(luò)不僅有下載流量，還有上傳流量，也就是說你加入了這個 P2P 網(wǎng)絡(luò)，自己可以從這個網(wǎng)絡(luò)里下載，同時別人也可以從你這里下載。這樣就實現(xiàn)了，下載人數(shù)越多，下載速度越快的愿望。

????上面整個過程是不是很完美？是的，結(jié)果很美好，但為了實現(xiàn)這個美好，我們還是有很多準(zhǔn)備工作要做的。比如，我們怎么知道哪些 peer 有某個文件呢？

????這就用到我們常說的種子（.torrent）。 .torrent 文件由Announce（Tracker URL）和文件信息兩部分組成。

????其中，文件信息里有以下內(nèi)容：

Info 區(qū)：指定該種子包含的文件數(shù)量、文件大小及目錄結(jié)構(gòu)，包括目錄名和文件名；

Name 字段：指定頂層目錄名字；

每個段的大小：BitTorrent（BT）協(xié)議把一個文件分成很多個小段，然后分段下載；

段哈希值：將整個種子種，每個段的 SHA-1 哈希值拼在一起。

????下載時，BT 客戶端首先解析 .torrent 文件，得到 Tracker 地址，然后連接 Tracker 服務(wù)器。Tracker 服務(wù)器回應(yīng)下載者的請求，將其他下載者（包括發(fā)布者）的 IP 提供給下載者。

????下載者再連接其他下載者，根據(jù) .torrent 文件，兩者分別對方自己已經(jīng)有的塊，然后交換對方?jīng)]有的數(shù)據(jù)。

????可以看到，下載的過程不需要其他服務(wù)器參與，并分散了單個線路上的數(shù)據(jù)流量，減輕了服務(wù)器的壓力。

????下載者每得到一個塊，需要算出下載塊的 Hash 驗證碼，并與 .torrent 文件中的進(jìn)行對比。如果一樣，說明塊正確，不一樣就需要重新下載這個塊。這種規(guī)定是為了解決下載內(nèi)容的準(zhǔn)確性問題。

????從這個過程也可以看出，這種方式特別依賴 Tracker。Tracker 需要收集所有 peer 的信息，并將從信息提供給下載者，使下載者相互連接，傳輸數(shù)據(jù)。雖然下載的過程是非中心化的，但是加入這個 P2P 網(wǎng)絡(luò)時，需要借助 Tracker 中心服務(wù)器，這個服務(wù)器用來登記有哪些用戶在請求哪些資源。

????所以，這種工作方式有一個弊端，一旦 Tracker 服務(wù)器出現(xiàn)故障或者線路被屏蔽，BT 工具就無法正常工作了。那能不能徹底去中心化呢？答案是可以的。

????DHT（Distributed Hash Table），這個網(wǎng)絡(luò)中，每個加入 DHT 網(wǎng)絡(luò)的人，都要負(fù)責(zé)存儲這個網(wǎng)絡(luò)里的資源信息和其他成員的聯(lián)系信息，相當(dāng)于所有人一起構(gòu)成了一個龐大的分布式存儲數(shù)據(jù)庫。

????而 Kedemlia 協(xié)議 就是一種著名的 DHT 協(xié)議。我們來基于這個協(xié)議來認(rèn)識下這個神奇的 DHT 網(wǎng)絡(luò)。

????當(dāng)一個客戶端啟動 BitTorrent 準(zhǔn)備下載資源時，這個客戶端就充當(dāng)了兩個角色：

peer 角色：監(jiān)聽一個 TCP 端口，用來上傳和下載文件。對外表明我這里有某個文件；

DHT Node 角色：監(jiān)聽一個 UDP 端口，通過這個角色，表明這個節(jié)點加入了一個 DHT 網(wǎng)絡(luò)。

????在 DHT 網(wǎng)絡(luò)里面，每一個 DHT Node 都有一個 ID。這個 ID 是一個長字符串。每個 DHT Node 都有責(zé)任掌握一些“知識”，也就是文件索引。也就是說，每個節(jié)點要知道哪些文件是保存哪些節(jié)點上的。注意，這里它只需要有這些“知識”就可以了，而它本身不一定就是保存這個文件的節(jié)點。

????當(dāng)然，每個 DHT Node 不會有全局的“知識”，也就是說它不知道所有的文件保存位置，只需要知道一部分。這里的一部分，就是通過哈希算法計算出來的。

Node ID 和文件哈希值

????每個文件可以計算出一個哈希值，而 DHT Node 的 ID 是和哈希值相同長度的串。

????對于文件下載，DHT 算法是這樣規(guī)定的：

如果一個文件計算出一個哈希值，則和這個哈希值一樣的那個 DHT Node，就有責(zé)任知道從哪里下載這個文件，即便它自己沒保存這個文件。

????當(dāng)然不一定總這么巧，都能找到和哈希值一模一樣的，有可能文件對應(yīng)的 DHT Node 下線了，所以 DHT 算法還規(guī)定：

除了一模一樣的那個 DHT Node 應(yīng)該知道文件的保存位置，ID 和這個哈希值非常接近的 N 個 DHT Node 也應(yīng)該知道。

????以上圖為例。文件 1 通過哈希運算，得到匹配 ID 的 DHT Node 為 Node C（當(dāng)然還會有其他的，為了便于理解，咱們就先關(guān)注 Node C），所以，Node C 就有責(zé)任知道文件 1 的存放地址，雖然 Node C 本身沒有存放文件 1。

????同理，文件 2 通過哈希計算，得到匹配 ID 的 DHT Node 為 Node E，但是 Node D 和 E 的值很近，所以 Node D 也知道。當(dāng)然，文件 2 本身不一定在 Node D 和 E 這里，但是我們假設(shè) E 就有一份。

????接下來，一個新節(jié)點 Node new 上線了，如果要下載文件 1，它首先要加入 DHT 網(wǎng)絡(luò)。如何加入呢？

????在這種模式下，種子 .torrent 文件里面就不再是 Tracker 的地址了，而是一個 list 的 Node 地址，所有這些 Node 都是已經(jīng)在 DHT 網(wǎng)絡(luò)里面的。當(dāng)然，隨著時間的推移，很有可能有退出的，有下線的，這里我們假設(shè)，不會所有的都聯(lián)系不上，總有一個能聯(lián)系上。

????那么，Node new 只要在種子里面找到一個 DHT Node，就加入了網(wǎng)絡(luò)。

????Node new 不知道怎么聯(lián)系上 Node C，因為種子里面的 Node 列表里面很可能沒有 Node C，但是沒關(guān)系，它可以問。DHT 網(wǎng)絡(luò)特別像一個社交網(wǎng)絡(luò)，Node new 會去它能聯(lián)系上的 Node 問，你們知道 Node C 的聯(lián)系方式嗎？

????在 DHT 網(wǎng)絡(luò)中，每個 Node 都保存了一定的聯(lián)系方式，但是肯定沒有所有 Node 的聯(lián)系方式。節(jié)點之間通過相互通信，會交流聯(lián)系方式，也會刪除聯(lián)系方式。這和人們的溝通方式一樣，你有你的朋友圈，他有他的朋友圈，你們互相加微信，就互相認(rèn)識了，但是過一段時間不聯(lián)系，就可能會刪除朋友關(guān)系一樣。

????在社交網(wǎng)絡(luò)中，還有個著名的六度理論，就是說社交網(wǎng)絡(luò)中的任何兩個人的直接距離不超過六度，也就是即使你想聯(lián)系比爾蓋茨，最多通過六個人就能夠聯(lián)系上。

????所以，Node New 想聯(lián)系 Node C，就去萬能的朋友圈去問，并且求轉(zhuǎn)發(fā)，朋友再問朋友，直到找到 C。如果最后找不到 C，但是能找到離 C 很近的節(jié)點，也可以通過 C 的相鄰節(jié)點下載文件 1。

????在 Node C上，告訴 Node new，要下載文件 1，可以去 B、D、F，這里我們假設(shè) Node new 選擇了 Node B，那么新節(jié)點就和 B 進(jìn)行 peer 連接，開始下載。它一旦開始下載，自己本地也有文件 1 了，于是，Node new 就告訴 C 以及 C 的相鄰節(jié)點，我也有文件 1 了，可以將我加入文件 1 的擁有者列表了。

????你可能會發(fā)現(xiàn)，上面的過程中漏掉了 Node new 的文件索引，但是根據(jù)哈希算法，一定會有某些文件的哈希值是和 Node new 的 ID 匹配的。在 DHT 網(wǎng)絡(luò)中，會有節(jié)點告訴它，你既然加入了咱們這個網(wǎng)絡(luò)，也就有責(zé)任知道某些文件的下載地址了。

????好了，完成分布式下載了。但是我們上面的過程中遺留了兩個細(xì)節(jié)性的問題。

1）DHT Node ID 以及文件哈希值是什么？
????其實，我們可以將節(jié)點 ID 理解為一個 160bits（20字節(jié)）的字符串，文件的哈希也使用這樣的字符串。

2）所謂 ID 相似，具體到什么程度算相似？
????這里就要說到兩個節(jié)點距離的定義和計算了。

????在 Kademlia 網(wǎng)絡(luò)中，兩個節(jié)點的距離采用的是邏輯上的距離，假設(shè)節(jié)點 A 和 節(jié)點 B 的距離為 d，則：

d = A XOR B

????上面說過，每個節(jié)點都有一個哈希 ID，這個 ID 由 20 個字符，160 bits 位組成。這里，我們就用一個 5 bits ID 來舉例。
????我們假設(shè)，節(jié)點 A 的 ID 是 01010，節(jié)點 B 的 ID 是 01001，則：

距離 d = A XOR B = 01010 XOR 00011 = 01001 = 9

????所以，我們說節(jié)點 A 和節(jié)點 B 的邏輯距離為 9。

????回到我們上面的問題，哈希值接近，可以理解為距離接近，也即，和這個節(jié)點距離近的 N 個節(jié)點要知道文件的保存位置。

????要注意的是，這個距離不是地理位置，因為在 Kademlia 網(wǎng)絡(luò)中，位置近不算近，ID 近才算近。我們可以將這個距離理解為社交距離，也就是在朋友圈中的距離，或者社交網(wǎng)絡(luò)中的距離。這個和你的空間位置沒有多少關(guān)系，和人的經(jīng)歷關(guān)系比較大。

DHT 網(wǎng)絡(luò)節(jié)點關(guān)系的維護(hù)

????就像人一樣，雖然我們常聯(lián)系的只有少數(shù)，但是朋友圈肯定是遠(yuǎn)近都有。DHT 網(wǎng)絡(luò)的朋友圈也一樣，遠(yuǎn)近都有，并且按距離分層。

????假設(shè)某個節(jié)點的 ID 為 01010，如果一個節(jié)點的 ID，前面所有位數(shù)都與它相同，只有最后 1 位不停，這樣的節(jié)點只有 1 個，為 01011。與基礎(chǔ)節(jié)點的異或值為 00001，也就是距離為 1。那么對于 01010 而言，這樣的節(jié)點歸為第一層節(jié)點，也就是k-buket 1。

????類似的，如果一個節(jié)點的 ID，前面所有位數(shù)和基礎(chǔ)節(jié)點都相同，從倒數(shù)第 2 位開始不同，這樣的節(jié)點只有 2 個，即 01000 和 01001，與基礎(chǔ)節(jié)點的亦或值為 00010 和 00011，也就是距離為 2 和 3。這樣的節(jié)點歸為第二層節(jié)點，也就是k-bucket 2。

????所以，我們可以總結(jié)出以下規(guī)律：

如果一個節(jié)點的 ID，前面所有位數(shù)相同，從倒數(shù)第 i 位開始不同，這樣的節(jié)點只有 2^(i-1) 個，與基礎(chǔ)節(jié)點的距離范圍為 [2^(i-1), 2^i]，對于原始節(jié)點而言，這樣的節(jié)點歸為k-bucket i。

????你會發(fā)現(xiàn)，差距越大，陌生人就越多。但是朋友圈不能把所有的都放下，所以每一層都只放 K 個，這個 K 是可以通過參數(shù)配置的。

DHT 網(wǎng)絡(luò)中查找好友

????假設(shè)，Node A 的 ID 為 00110，要找 B（10000），異或距離為 10110，距離范圍在 [2^4, 2^5)，這就說明 B 的 ID 和 A 的從第 5 位開始不同，所以 B 可能在 k-bucket 5 中。

????然后，A 看看自己的 k-bucket 5 有沒有 B，如果有，結(jié)束查找。如果沒有，就在 k-bucket 5 里隨便找一個 C。因為是二進(jìn)制，C、B 都和 A 的第 5 位不停，那么 C 的 ID 第5 位肯定與 B 相同，即它與 B 的距離小于 2^4，相當(dāng)于 A、B 之間的距離縮短了一半以上。

????接著，再請求 C，在 C 的通訊里里，按同樣的查找方式找 B，如果 C 找到了 B，就告訴 A。如果 C 也沒有找到 B，就按同樣的搜索方法，在自己的通訊里里找到一個離 B 更近一步的 D（D、B 之間距離小于 2^3），把 D 推薦給 A，A 請求 D 進(jìn)行下一步查找。

????你可能已經(jīng)發(fā)現(xiàn)了，Kademlia 這種查詢機(jī)制，是通過折半查找的方式來收縮范圍，對于總的節(jié)點數(shù)目為 N 的網(wǎng)絡(luò)，最多只需要 log2(N) 次查詢，就能夠找到目標(biāo)。

????如下圖，A 節(jié)點找 B 節(jié)點，最壞查找情況：

????圖中過程如下：

A 和 B 的每一位都不一樣，所以相差 31，A 找到的朋友 C，不巧正好在中間，和 A 的距離是 16，和 B 的距離是 15；

C 去自己朋友圈找，碰巧找到了 D，距離 C 為 8，距離 B 為 7；

D 去自己朋友圈找，碰巧找到了 E，距離 D 為 4，距離 B 為 3；

E 在自己朋友圈找，找到了 F，距離 E 為 2，距離 B 為 1；

F 在距離為 1 的地方找到了 B。

節(jié)點的溝通

????在 Kademlia 算法中，每個節(jié)點下面 4 個指令：

PING：測試一個節(jié)點是否在線。相當(dāng)于打個電話，看還能打通不；

STORE：要錢一個節(jié)點存儲一份數(shù)據(jù)；

FIND_NODE：根據(jù)節(jié)點 ID 查找一個節(jié)點；

FIND_VALUE：根據(jù) KEY 查找一個數(shù)據(jù)，實則上和 FIND_NODE 非常類似。KEY 就是文件對應(yīng)的哈希值，找到保存文件的節(jié)點。

節(jié)點的更新

????整個 DHT 網(wǎng)絡(luò)，會通過相互通信，維護(hù)自己朋友圈好友的狀態(tài)。

每個 bucket 里的節(jié)點，都按最后一次接觸時間倒序排列。相當(dāng)于，朋友圈里最近聯(lián)系的人往往是最熟的；

每次執(zhí)行四個指令中的任意一個都會觸發(fā)更新；

當(dāng)一個節(jié)點與自己接觸時，檢查它是否已經(jīng)在 k-bucket 中。就是說是否已經(jīng)在朋友圈。如果在，那么就將它移到 k-bucket 列表的最底，也就是最新的位置（剛聯(lián)系過，就置頂下，方便以后多聯(lián)系）。如果不在，就要考慮新的聯(lián)系人要不要加到通訊錄里面。假設(shè)通訊錄已滿，就 PING 一下列表最上面的節(jié)點（最舊的），如果 PING 通了，將舊節(jié)點移動到列表最底，并丟棄新節(jié)點（老朋友還是要留點情面的）。如 PING 不同，就刪除舊節(jié)點，并將新節(jié)點加入列表（聯(lián)系不上的老朋友還是刪掉吧）。

????通過上面這個機(jī)制，保證了任意節(jié)點的加入和離開都不影響整體網(wǎng)絡(luò)。

下載一個文件可以通過 HTTP 或 FTP。這兩種都是集中下載的方式，而 P2P 則換了一種思路，采用非中心化下載的方式；

P2P 有兩種。一種是依賴于 Tracker 的，也就是元數(shù)據(jù)集中，文件數(shù)據(jù)分散。另一種是基于分布式的哈希算法，元數(shù)據(jù)和文件數(shù)據(jù)全部分散。

參考：

維基百科-DHT 網(wǎng)絡(luò)詞條；

維基百科-Kademlia 詞條；

劉超 - 趣談網(wǎng)絡(luò)協(xié)議系列課；