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

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

下載電影的兩種方式

第一種是通過 HTTP 進行下載。這種方式，有過經歷的人應該體會到，當下載文件稍大點，下載速度簡直能把人急死。

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

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

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

FTP 的工作模式

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

主動模式工作流程

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

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

被動模式工作流程

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

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

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

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

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

P2P

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

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

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

種子文件（.torent）

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

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

其中，文件信息里有以下內容：

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

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

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

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

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

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

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

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

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

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

去中心化網絡（DHT）

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

而Kedemlia 協(xié)議就是一種著名的 DHT 協(xié)議。我們來基于這個協(xié)議來認識下這個神奇的 DHT 網絡。

當一個客戶端啟動 BitTorrent 準備下載資源時，這個客戶端就充當了兩個角色：

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

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

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

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

Node ID 和文件哈希值

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

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

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

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

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

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

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

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

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

那么，Node new 只要在種子里面找到一個 DHT Node，就加入了網絡。

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

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

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

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

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

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

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

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

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

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

d = A XOR B

上面說過，每個節(jié)點都有一個哈希 ID，這個 ID 由 20 個字符，160 bits 位組成。這里，我們就用一個 5 bits ID 來舉例。
????我們假設，節(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 網絡中，位置近不算近，ID 近才算近。我們可以將這個距離理解為社交距離，也就是在朋友圈中的距離，或者社交網絡中的距離。這個和你的空間位置沒有多少關系，和人的經歷關系比較大。

DHT 網絡節(jié)點關系的維護

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

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

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

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

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

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

DHT 網絡中查找好友

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

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

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

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

如下圖，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é)點是否在線。相當于打個電話，看還能打通不；

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

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

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

節(jié)點的更新

整個 DHT 網絡，會通過相互通信，維護自己朋友圈好友的狀態(tài)。

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

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

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

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

小結

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

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