如果你想下載一個電影棍现，一般會通過什么方式呢？

當(dāng)然镜遣，最簡單的方式就是通過 HTTP 進行下載己肮。但是相信你有過這樣的體驗，通過瀏覽器下載的時候悲关，只要文件稍微大點谎僻，下載的速度就奇慢無比。

還有種下載文件的方式寓辱，就是通過 FTP艘绍，也即文件傳輸協(xié)議。FTP 采用兩個 TCP 連接來傳輸一個文件秫筏。

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

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

FTP 的兩種工作模式

每傳輸一個文件，都要建立一個全新的數(shù)據(jù)連接帝雇。FTP 有兩種工作模式涮俄，分別是主動模式（PORT）和被動模式（PASV），這些都是站在 FTP 服務(wù)器的角度來說的尸闸。

主動模式下彻亲，客戶端隨機打開一個大于 1024 的端口 N，向服務(wù)器的命令端口 21 發(fā)起連接吮廉，同時開放 N+1 端口監(jiān)聽苞尝，并向服務(wù)器發(fā)出 “port N+1” 命令，由服務(wù)器從自己的數(shù)據(jù)端口 20宦芦，主動連接到客戶端指定的數(shù)據(jù)端口 N+1宙址。

被動模式下，當(dāng)開啟一個 FTP 連接時调卑，客戶端打開兩個任意的本地端口 N（大于 1024）和 N+1抡砂。第一個端口連接服務(wù)器的 21 端口，提交 PASV 命令恬涧。然后注益，服務(wù)器會開啟一個任意的端口 P（大于 1024），返回“227 entering passive mode”消息溯捆，里面有 FTP 服務(wù)器開放的用來進行數(shù)據(jù)傳輸?shù)亩丝诹那场？蛻舳耸盏较⑷〉枚丝谔栔笙质梗瑫ㄟ^ N+1 號端口連接服務(wù)器的端口 P低匙，然后在兩個端口之間進行數(shù)據(jù)傳輸。

P2P 是什么碳锈？

但是無論是 HTTP 的方式顽冶，還是 FTP 的方式，都有一個比較大的缺點售碳，就是難以解決單一服務(wù)器的帶寬壓力强重， 因為它們使用的都是傳統(tǒng)的客戶端服務(wù)器的方式。

后來贸人，一種創(chuàng)新的间景、稱為 P2P 的方式流行起來。P2P 就是 peer-to-peer艺智。資源開始并不集中地存儲在某些設(shè)備上倘要，而是分散地存儲在多臺設(shè)備上。這些設(shè)備我們姑且稱為 peer十拣。

想要下載一個文件的時候封拧，你只要得到那些已經(jīng)存在了文件的 peer志鹃，并和這些 peer 之間，建立點對點的連接泽西，而不需要到中心服務(wù)器上曹铃，就可以就近下載文件。一旦下載了文件捧杉，你也就成為 peer 中的一員陕见，你旁邊的那些機器，也可能會選擇從你這里下載文件味抖，所以當(dāng)你使用 P2P 軟件的時候淳玩，例如 BitTorrent，往往能夠看到非竿，既有下載流量蜕着，也有上傳的流量，也即你自己也加入了這個 P2P 的網(wǎng)絡(luò)红柱，自己從別人那里下載承匣，同時也提供給其他人下載〈盖模可以想象韧骗，這種方式，參與的人越多零聚，下載速度越快袍暴，一切完美。

種子（.torrent）文件

但是有一個問題隶症，當(dāng)你想下載一個文件的時候政模，怎么知道哪些 peer 有這個文件呢？

這就用到種子啦蚂会，也即咱們比較熟悉的.torrent 文件淋样。.torrent 文件由兩部分組成，分別是：announce（tracker URL）和文件信息胁住。

文件信息里面有這些內(nèi)容趁猴。

info 區(qū)：這里指定的是該種子有幾個文件、文件有多長彪见、目錄結(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ù)器的負(fù)擔(dān)啸澡。

下載者每得到一個塊袖订，需要算出下載塊的 Hash 驗證碼，并與.torrent 文件中的對比嗅虏。如果一樣洛姑，則說明塊正確，不一樣則需要重新下載這個塊皮服。這種規(guī)定是為了解決下載內(nèi)容的準(zhǔn)確性問題楞艾。

從這個過程也可以看出，這種方式特別依賴 tracker龄广。tracker 需要收集下載者信息的服務(wù)器硫眯，并將此信息提供給其他下載者，使下載者們相互連接起來择同，傳輸數(shù)據(jù)舟铜。雖然下載的過程是非中心化的，但是加入這個 P2P 網(wǎng)絡(luò)的時候奠衔，都需要借助 tracker 中心服務(wù)器谆刨，這個服務(wù)器是用來登記有哪些用戶在請求哪些資源。

所以归斤，這種工作方式有一個弊端痊夭，一旦 tracker 服務(wù)器出現(xiàn)故障或者線路遭到屏蔽，BT 工具就無法正常工作了脏里。

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

那能不能徹底非中心化呢她我？

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

有一種著名的 DHT 協(xié)議恨狈，叫 Kademlia 協(xié)議疏哗。這個和區(qū)塊鏈的概念一樣，很抽象禾怠，我來詳細(xì)講一下這個協(xié)議返奉。

任何一個 BitTorrent 啟動之后，它都有兩個角色吗氏。一個是 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é)任掌握一些知識包颁，也就是文件索引，也即它應(yīng)該知道某些文件是保存在哪些節(jié)點上压真。它只需要有這些知識就可以了娩嚼，而它自己本身不一定就是保存這個文件的節(jié)點。

哈希值

當(dāng)然滴肿，每個 DHT node 不會有全局的知識岳悟，也即不知道所有的文件保存在哪里，它只需要知道一部分泼差。那應(yīng)該知道哪一部分呢贵少？這就需要用哈希算法計算出來。

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

DHT 算法是這樣規(guī)定的：如果一個文件計算出一個哈希值，則和這個哈希值一樣的那個 DHT node吼肥，就有責(zé)任知道從哪里下載這個文件录平，即便它自己沒保存這個文件麻车。

當(dāng)然不一定這么巧，總能找到和哈希值一模一樣的斗这，有可能一模一樣的 DHT node 也下線了动猬，所以 DHT 算法還規(guī)定：除了一模一樣的那個 DHT node 應(yīng)該知道，ID 和這個哈希值非常接近的 N 個 DHT node 也應(yīng)該知道表箭。

什么叫和哈希值接近呢赁咙？例如只修改了最后一位，就很接近燃逻；修改了倒數(shù) 2 位序目，也不遠(yuǎn)臂痕；修改了倒數(shù) 3 位伯襟，也可以接受∥胀總之姆怪，湊齊了規(guī)定的 N 這個數(shù)就行。

剛才那個圖里澡绩，文件 1 通過哈希運算稽揭，得到匹配 ID 的 DHT node 為 node C，當(dāng)然還會有其他的肥卡，我這里沒有畫出來溪掀。所以，node C 有責(zé)任知道文件 1 的存放地址步鉴，雖然 node C 本身沒有存放文件 1揪胃。

同理，文件 2 通過哈希運算氛琢，得到匹配 ID 的 DHT node 為 node E喊递，但是 node D 和 E 的 ID 值很近，所以 node D 也知道阳似。當(dāng)然骚勘，文件 2 本身沒有必要一定在 node D 和 E 里，但是碰巧這里就在 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 會計算文件 1 的哈希值伙单，并根據(jù)這個哈希值了解到，和這個哈希值匹配哈肖，或者很接近的 node 上知道如何下載這個文件吻育，例如計算出來的哈希值就是 node C。

但是 node new 不知道怎么聯(lián)系上 node C淤井，因為種子里面的 node 列表里面很可能沒有 node C布疼，但是它可以問，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)系方式。DHT 網(wǎng)絡(luò)中止吐，節(jié)點之間通過互相通信宝踪，也會交流聯(lián)系方式，也會刪除聯(lián)系方式祟印。和人們的方式一樣肴沫，你有你的朋友圈，你的朋友有它的朋友圈蕴忆，你們互相加微信颤芬，就互相認(rèn)識了，過一段時間不聯(lián)系套鹅，就刪除朋友關(guān)系站蝠。

有個理論是，社交網(wǎng)絡(luò)中卓鹿，任何兩個人直接的距離不超過六度菱魔，也即你想聯(lián)系比爾蓋茨，也就六個人就能夠聯(lián)系到了吟孙。

所以澜倦，node new 想聯(lián)系 node C聚蝶，就去萬能的朋友圈去問，并且求轉(zhuǎn)發(fā)藻治，朋友再問朋友碘勉，很快就能找到。如果找不到 C桩卵，也能找到和 C 的 ID 很像的節(jié)點验靡，它們也知道如何下載文件 1。

在 node C 上雏节，告訴 node new胜嗓，下載文件 1，要去 B钩乍、D辞州、 F，于是 node new 選擇和 node B 進行 peer 連接件蚕，開始下載孙技，它一旦開始下載产禾，自己本地也有文件 1 了排作，于是 node new 告訴 node C 以及和 node C 的 ID 很像的那些節(jié)點，我也有文件 1 了亚情，可以加入那個文件擁有者列表了妄痪。

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

好了黄伊，一切都分布式了泪酱。

這里面遺留幾個細(xì)節(jié)的問題。

DHT node ID 以及文件哈希是個什么東西还最？

節(jié)點 ID 是一個隨機選擇的 160bits（20 字節(jié)）空間墓阀，文件的哈希也使用這樣的 160bits 空間。

所謂 ID 相似拓轻，具體到什么程度算相似斯撮？

在 Kademlia 網(wǎng)絡(luò)中，距離是通過異或（XOR）計算的扶叉。我們就不以 160bits 舉例了勿锅。我們以 5 位來舉例帕膜。

01010 與 01000 的距離，就是兩個 ID 之間的異或值溢十，為 00010泳叠，也即為 2。 01010 與 00010 的距離為 01000茶宵，也即為 8,危纫。01010 與 00011 的距離為 01001，也即 8+1=9 乌庶。以此類推种蝶，高位不同的，表示距離更遠(yuǎn)一些瞒大；低位不同的螃征，表示距離更近一些，總的距離為所有的不同的位的距離之和透敌。

這個距離不能比喻為地理位置盯滚，因為在 Kademlia 網(wǎng)絡(luò)中，位置近不算近酗电，ID 近才算近魄藕，所以我把這個距離比喻為社交距離，也即在朋友圈中的距離撵术，或者社交網(wǎng)絡(luò)中的距離背率。這個和你住的位置沒有關(guān)系，和人的經(jīng)歷關(guān)系比較大嫩与。

還是以 5 位 ID 來舉例寝姿，就像在領(lǐng)英中，排第一位的表示最近一份工作在哪里划滋，第二位的表示上一份工作在哪里饵筑，然后第三位的是上上份工作，第四位的是研究生在哪里讀处坪，第五位的表示大學(xué)在哪里讀根资。

如果你是一個獵頭，在上面找候選人稻薇，當(dāng)然最近的那份工作是最重要的嫂冻。而對于工作經(jīng)歷越豐富的候選人，大學(xué)在哪里讀的反而越不重要塞椎。

DHT 網(wǎng)絡(luò)中的朋友圈是怎么維護的桨仿？

就像人一樣，雖然我們常聯(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é)點歸為“k-bucket 1”骨坑。

如果一個節(jié)點的 ID，前面所有位數(shù)都相同柬采，從倒數(shù)第 2 位開始不同欢唾，這樣的節(jié)點只有 2 個，即 01000 和 01001粉捻，與基礎(chǔ)節(jié)點的異或值為 00010 和 00011礁遣，即距離范圍為 2 和 3；對于 01010 而言杀迹，這樣的節(jié)點歸為“k-bucket 2”亡脸。

如果一個節(jié)點的 ID押搪，前面所有位數(shù)相同树酪，從倒數(shù)第 i 位開始不同，這樣的節(jié)點只有 2^(i-1) 個大州，與基礎(chǔ)節(jié)點的距離范圍為[2^(i-1), 2^i)续语；對于 01010 而言，這樣的節(jié)點歸為“k-bucket i”厦画。

最終到從倒數(shù) 160 位就開始都不同疮茄。

你會發(fā)現(xiàn)，差距越大根暑，陌生人越多力试，但是朋友圈不能都放下，所以每一層都只放 K 個排嫌，這是參數(shù)可以配置畸裳。

DHT 網(wǎng)絡(luò)是如何查找朋友的？

假設(shè)淳地，node A 的 ID 為 00110怖糊，要找 node B ID 為 10000帅容，異或距離為 10110，距離范圍在[2^4, 2^5)伍伤，所以這個目標(biāo)節(jié)點可能在“k-bucket 5”中并徘，這就說明 B 的 ID 與 A 的 ID 從第 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佣渴，相當(dāng)于比 A辫狼、B 之間的距離縮短了一半以上。

再請求 C辛润，在它自己的通訊錄里膨处，按同樣的查找方式找一下 B。如果 C 知道 B砂竖，就告訴 A真椿；如果 C 也不知道 B，那 C 按同樣的搜索方法乎澄，可以在自己的通訊錄里找到一個離 B 更近的 D 朋友（D突硝、B 之間距離小于 2^3），把 D 推薦給 A置济，A 請求 D 進行下一步查找解恰。

Kademlia 的這種查詢機制，是通過折半查找的方式來收縮范圍浙于，對于總的節(jié)點數(shù)目為 N护盈，最多只需要查詢 log2(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漱贱。當(dāng)然這是最最不巧的情況槐雾，每次找到的朋友都不遠(yuǎn)不近，正好在中間幅狮。

如果碰巧了募强，在 A 的朋友圈里面有 G，距離 B 只有 3崇摄，然后在 G 的朋友圈里面一下子就找到了 B擎值，兩次就找到了。

在 DHT 網(wǎng)絡(luò)中配猫，朋友之間怎么溝通呢幅恋？

Kademlia 算法中，每個節(jié)點只有 4 個指令泵肄。

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

STORE：要求一個節(jié)點存儲一份數(shù)據(jù)玄括，既然加入了組織冯丙，有義務(wù)保存一份數(shù)據(jù)。

FIND_NODE：根據(jù)節(jié)點 ID 查找一個節(jié)點，就是給一個 160 位的 ID胃惜，通過上面朋友圈的方式找到那個節(jié)點泞莉。

FIND_VALUE：根據(jù) KEY 查找一個數(shù)據(jù)，實則上跟 FIND_NODE 非常類似船殉。KEY 就是文件對應(yīng)的 160 位的 ID鲫趁，就是要找到保存了文件的節(jié)點。

DHT 網(wǎng)絡(luò)中利虫，朋友圈如何更新呢挨厚？

每個 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)系不上了疙描，刪了吧诚隙。

這個機制保證了任意節(jié)點加入和離開都不影響整體網(wǎng)絡(luò)。

小結(jié)

好了起胰，今天的講解就到這里了久又，我們總結(jié)一下：

下載一個文件可以使用 HTTP 或 FTP，這兩種都是集中下載的方式，而 P2P 則換了一種思路地消，采取非中心化下載的方式炉峰；

P2P 也是有兩種，一種是依賴于 tracker 的脉执，也即元數(shù)據(jù)集中疼阔，文件數(shù)據(jù)分散；另一種是基于分布式的哈希算法适瓦，元數(shù)據(jù)和文件數(shù)據(jù)全部分散竿开。

接下來，給你留兩個思考題：

除了這種去中心化分布式哈希的算法玻熙，你還能想到其他的應(yīng)用場景嗎否彩？

在前面所有的章節(jié)中，要下載一個文件嗦随，都需要使用域名列荔。但是網(wǎng)絡(luò)通信是使用 IP 的，那你知道怎么實現(xiàn)兩者的映射機制嗎枚尼？

歡迎你留言和我討論贴浙。趣談網(wǎng)絡(luò)協(xié)議，我們下期見署恍！