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

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

下載電影的兩種方式

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

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

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

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

FTP 的工作模式

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

主動(dòng)模式工作流程

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

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

被動(dòng)模式工作流程

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

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

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

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

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

P2P

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

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

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

種子文件（.torent）

上面整個(gè)過程是不是很完美？是的，結(jié)果很美好，但為了實(shí)現(xiàn)這個(gè)美好，我們還是有很多準(zhǔn)備工作要做的。比如，我們?cè)趺粗滥男?peer 有某個(gè)文件呢？

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

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

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

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

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

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

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

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

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

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

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

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

去中心化網(wǎng)絡(luò)（DHT）

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

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

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

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

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

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

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

Node ID 和文件哈希值

每個(gè)文件可以計(jì)算出一個(gè)哈希值，而DHT Node 的 ID 是和哈希值相同長(zhǎng)度的串。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

d = A XOR B

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

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

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

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

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

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

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

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

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

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

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

你會(huì)發(fā)現(xiàn)，差距越大，陌生人就越多。但是朋友圈不能把所有的都放下，所以每一層都只放 K 個(gè)，這個(gè) 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 里隨便找一個(gè) C。因?yàn)槭嵌M(jìn)制，C、B 都和 A 的第 5 位不停，那么 C 的 ID 第5 位肯定與 B 相同，即它與 B 的距離小于 2^4，相當(dāng)于 A、B 之間的距離縮短了一半以上。

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

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

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

圖中過程如下：

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é)點(diǎn)的溝通

在 Kademlia 算法中，每個(gè)節(jié)點(diǎn)下面 4 個(gè)指令：

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

STORE：要錢一個(gè)節(jié)點(diǎn)存儲(chǔ)一份數(shù)據(jù)；

FIND_NODE：根據(jù)節(jié)點(diǎn) ID 查找一個(gè)節(jié)點(diǎn)；

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

節(jié)點(diǎn)的更新

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

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

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

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

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

小結(jié)

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

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