17p2協(xié)議我下小電影99急死你

1、第17講 | P2P協(xié)議：我下 ，99%急死你筆記本： P.趣談 協(xié)議創(chuàng)建時(shí)間： 2018/6/26 9:11作者： hongfenghuojuURL：更新時(shí)間： 2018/6/26 9:11第17講 | P2P協(xié)議：我下 ，99%急死你2018-06-25如果你想 一個(gè) ，一般會(huì)通過(guò)什么方式呢？當(dāng)然，最簡(jiǎn)單的方式就是通過(guò)HTTP進(jìn)行 。但是相信你有過(guò)這樣的體驗(yàn)，通過(guò)瀏覽器 的時(shí)候，只要文件稍微大點(diǎn)， 的速度就奇慢無(wú)比。還有種 文件的方式，就是通過(guò)FTP，也即文件傳輸協(xié)議。FTP 采用兩個(gè) TCP 連接來(lái)傳輸一個(gè)文件。連接：服務(wù)器以 的方式，打開眾所周知用于 FTP 的端口 21，客戶端則主動(dòng)

2、發(fā)起連接。該連接將命令從客戶端傳給服務(wù)器，并傳回服務(wù)器的應(yīng)答。常用 令有：list獲取文件目錄；reter取一個(gè)文件；store存一個(gè)文件。數(shù)據(jù)連接：每當(dāng)一個(gè)文件在客戶端與服務(wù)器之間傳輸時(shí)，就創(chuàng)建一個(gè)數(shù)據(jù)連接。FTP 的兩種工作模式每傳輸一個(gè)文件，都要建立一個(gè)全新的數(shù)據(jù)連接。FTP 有兩種工作模式，分別是主動(dòng)模式（PORT）和被動(dòng)模式（PASV），這些都是站在 FTP 服務(wù)器的角度來(lái)說(shuō)的。主動(dòng)模式下，客戶端隨機(jī)打開一個(gè)大于 1024 的端口 N，向服務(wù)器 令端口 21 發(fā)起連接，同時(shí)開放N+1 端口 ，并向服務(wù)器發(fā)出 “port N+1” 命令，由服務(wù)器從 的數(shù)據(jù)端口 20，主動(dòng)連接到客戶端指

3、定的數(shù)據(jù)端口 N+1。模式下，當(dāng)開啟一個(gè) FTP 連接時(shí)，客戶端打開兩個(gè)任意的本地端口 N（大于 1024）和 N+1。第一個(gè)端口連接服務(wù)器的 21 端口，提交 PASV 命令。然后，服務(wù)器會(huì)開啟一個(gè)任意的端口 P（大于1024），返回“227 entering passive mode”消息，里面有 FTP 服務(wù)器開放的用來(lái)進(jìn)行數(shù)據(jù)傳輸?shù)亩丝??？蛻舳耸盏较⑷〉枚?之后，會(huì)通過(guò) N+1 號(hào)端口連接服務(wù)器的端口 P，然后在兩個(gè)端口之間進(jìn)行數(shù)據(jù)傳輸。P2P 是什么？但是無(wú)論是 HTTP 的方式，還是 FTP 的方式， 一個(gè)比較大的缺點(diǎn)，就是難以解決單一服務(wù)器的帶寬， 因?yàn)樗鼈兪褂玫亩际莻鹘y(tǒng)的客戶

4、端服務(wù)器的方式。后來(lái)，一種創(chuàng)新的、稱為 P2P 的方式流行起來(lái)。P2P就是peer-to-peer。 開始并不集中地 在某些設(shè)備上，而是分散地 在多臺(tái)設(shè)備上。這些設(shè)備我們姑且稱為 peer。想要 一個(gè)文件的時(shí)候，你只要得到那些已經(jīng) 了文件的 peer，并和這些 peer 之間，建立點(diǎn)對(duì)點(diǎn)的連接，而不需要到中心服務(wù)器上，就可以就近 文件。一旦 了文件，你也就成為 peer 中的一員，你旁邊的那些 ，也可能會(huì)選擇從你這里 文件，所以當(dāng)你使用 P2P 軟件的時(shí)候，例如BitTorrent，往往能夠看到，既有 流量，也有上傳的流量，也即你 也加入了這個(gè) P2P 的 ，從別人那里 ，同時(shí)也提供給其他人

5、?？梢韵胂螅@種方式，參與的人越多， 速度越快，一切完美。（.torrent）文件但是有一個(gè)問(wèn)題，當(dāng)你想 一個(gè)文件的時(shí)候，怎么知道哪些 peer 有這個(gè)文件呢？這就用到 啦，也即咱們比較熟悉的.torrent 文件。.torrent 文件由兩部分組成，分別是： announce（tracker URL）和文件信息。文件信息里面有這些內(nèi)容。info 區(qū)：這里指定的是該 有幾個(gè)文件、文件有多長(zhǎng)、目錄結(jié)構(gòu)，以及目錄和文件的名字。Name 字段：指定頂層目錄名字。每個(gè)段的大?。築itTorrent（簡(jiǎn)稱 BT）協(xié)議把一個(gè)文件分成很多個(gè)小段，然后分段 。段 值：將整個(gè) 中，每個(gè)段的 SHA-1 值拼在一

6、起。時(shí)，BT 客戶端首先 .torrent 文件，得到 tracker 地址，然后連接 tracker 服務(wù)器。tracker 服務(wù)器回應(yīng) 者的請(qǐng)求，將其他 者（包括發(fā)布者）的 IP 提供給 者。 者再連接其他 者，根據(jù).torrent 文件，兩者分別對(duì)方告知 已經(jīng)有的塊，然后交換對(duì)方?jīng)]有的數(shù)據(jù)。此時(shí)不需要其他服務(wù)器參與，并分散了單個(gè)線路上的數(shù)據(jù)流量，因此減輕了服務(wù)器的負(fù)擔(dān)。者每得到一個(gè)塊，需要算出 塊的 Hash ，并與.torrent 文件中的對(duì)比。如果一樣，則說(shuō)明塊正確，不一樣則需要重新 這個(gè)塊。這種規(guī)定是為了解決 內(nèi)容的準(zhǔn)確性問(wèn)題。從這個(gè)過(guò)程也可以看出，這種方式特別依賴 tracker

7、。tracker 需要收集 者信息的服務(wù)器，并將此信息提供給其他 者，使 者們相互連接起來(lái)，傳輸數(shù)據(jù)。雖然 的過(guò)程是非中心化的，但是加入這個(gè) P2P 的時(shí)候，都需要借助 tracker 中心服務(wù)器，這個(gè)服務(wù)器是用來(lái)登記有哪些用戶在請(qǐng)求哪些。所以，這種工作方式有一個(gè)弊端，一旦 tracker 服務(wù)器出現(xiàn)故障或者線路遭到 ，BT 工具就無(wú)法正常工作了。去中心化 （DHT）那能不能徹底非中心化呢？于是，后來(lái)就有了一種叫作DHT（Distributed Hash Table）的去中心化 。每個(gè)加入這個(gè) DHT的人，都要負(fù)責(zé) 這個(gè) 里的 信息和其他成員的 信息，相當(dāng)于所有人一起 了一個(gè)龐大的分布式 數(shù)據(jù)

8、庫(kù)。有一種著名的 DHT 協(xié)議，叫Kademlia 協(xié)議。這個(gè)和 的概念一樣，很抽象，我來(lái)詳細(xì)講一下這個(gè)協(xié)議。任何一個(gè) BitTorrent 啟動(dòng)之后，它 兩個(gè) 。一個(gè)是peer， 一個(gè) TCP 端口，用來(lái)上傳和文件，這個(gè) 表明，我這里有某個(gè)文件。另一個(gè) DHT node， 一個(gè) UDP 的端口，通過(guò)這個(gè)角色，這個(gè)節(jié)點(diǎn)加入了一個(gè) DHT 的 。在 DHT 里面，每一個(gè) DHT node 一個(gè) ID。這個(gè) ID 是一個(gè)很長(zhǎng)的串。每個(gè) DHT node 責(zé)任掌握一些知識(shí)，也就是文件索引，也即它應(yīng)該知道某些文件是保 哪些節(jié)點(diǎn)上。它只需要有這些知 識(shí)就可以了，而它 本身不一定就是保存這個(gè)文件的節(jié)點(diǎn)。值

9、當(dāng)然，每個(gè) DHT node 有全局的知識(shí)，也即不知道所有的文件保 哪里，它只需要知道一部分。那應(yīng)該知道哪一部分呢？這就需要用 算法計(jì)算出來(lái)。每個(gè)文件可以計(jì)算出一個(gè) 值，而DHT node 的 ID 是和 值相同長(zhǎng)度的串。DHT 算法是這樣規(guī)定的：如果一個(gè)文件計(jì)算出一個(gè) 值，則和這個(gè) 值一樣的那個(gè) DHT node，就有責(zé) 從哪里 這個(gè)文件，即便它 沒(méi)保存這個(gè)文件。當(dāng)然不一定這么巧，總能找到和 值一模一樣的，有可能一模一樣的 DHT node 也下線了，所以DHT 算法還規(guī)定：除了一模一樣的那個(gè) DHT node 應(yīng)該知道，ID 和這個(gè) 值非常接近的 N 個(gè) DHT node 也應(yīng)該知道。什么

10、叫和 值接近呢？例如只修改了最后一位，就很接近；修改了倒數(shù) 2 位，也不遠(yuǎn)；修改了倒數(shù) 3 位，也可以接受。總之，湊齊了規(guī)定的 N 這個(gè)數(shù)就行。剛才那個(gè) ，文件 1 通過(guò) 運(yùn)算，得到匹配 ID 的 DHT node 為 node C，當(dāng)然還會(huì)有其他的，我這里沒(méi)有畫出來(lái)。所以，node C 有責(zé) 文件 1 的存放地址，雖然 node C 本身沒(méi)有存放文件 1。同理，文件 2 通過(guò) 運(yùn)算，得到匹配 ID 的 DHT node 為 node E，但是 node D 和 E 的 ID 值很近， 所以 node D 也知道。當(dāng)然，文件 2 本身沒(méi)有必要一定在 node D 和 E 里，但是碰巧這里就在

11、E 那有一份。接下來(lái)一個(gè)新的節(jié)點(diǎn) node new 上線了。如果想 文件 1，它首先要加入 DHT ，如何加入呢？在這種模式下， .torrent 文件里面就不再是 tracker 的地址了，而是一個(gè) list 的 node 的地址，而所有這些 node 都是已經(jīng)在 DHT 里面的。當(dāng)然隨著時(shí)間的推移，很可能有 的，有下線的，但是我們假設(shè)， 所有的都 不上，總有一個(gè)能 上。node new 只要在 里面找到一個(gè) DHT node，就加入了 。node new 會(huì)計(jì)算文件 1 的 值，并根據(jù)這個(gè) 值了解到，和這個(gè) 值匹配，或者很接近的node 上知道如何 這個(gè)文件，例如計(jì)算出來(lái)的 值就是 nod

12、e C。但是 node new 不知道怎么 上 node C，因?yàn)?里面的 node 列表里面很可能沒(méi)有 node C，但是它可以問(wèn)，DHT 特別像一個(gè)社交 ，node new 只有去它能 上的 node 問(wèn)， 知道不知道node C 的 方式呀？在 DHT 中，每個(gè) node 都保存了一定的 方式，但是肯定沒(méi)有 node 的所有 方式。DHT 網(wǎng)絡(luò)中，節(jié)點(diǎn)之間通過(guò)互相通信，也會(huì)交流 方式，也會(huì)刪除 方式。和人們的方式一樣，你有你的，你的朋友有它的 ， 互相加 ，就互相認(rèn)識(shí)了，過(guò)一段時(shí)間不 ，就刪除朋友關(guān)系。有個(gè)理論是，社交 中，任何兩個(gè)人直接的距離不超過(guò)六度，也即你想能夠 到了。，也就六個(gè)人

13、就所以，node new 想 node C，就去萬(wàn)能的 去問(wèn)，并且求轉(zhuǎn)發(fā)，朋友再問(wèn)朋友，很快就能找到。如果找不到 C，也能找到和 C 的 ID 很像的節(jié)點(diǎn)，它們也知道如何 文件 1。在 node C 上，告訴 node new， 文件 1，要去 B、D、 F，于是 node new 選擇和 node B 進(jìn)行peer 連接，開始 ，它一旦開始 ， 本地也有文件 1 了，于是 node new 告訴 node C 以及和 node C 的 ID 很像的那些節(jié)點(diǎn)，我也有文件 1 了，可以加入那個(gè)文件擁有者列表了。但是你會(huì)發(fā)現(xiàn) node new 上沒(méi)有文件索引，但是根據(jù) 算法，一定會(huì)有某些文件的 值

14、是和 node new 的 ID 匹配上的。在 DHT 中，會(huì)有節(jié)點(diǎn)告訴它，你既然加入了咱們這個(gè) ，你也有責(zé)某些文件的 地址。好了，一切都分布式了。這里面遺留幾個(gè)細(xì)節(jié)的問(wèn)題。DHT node ID 以及文件 是個(gè)什么東西？節(jié)點(diǎn) ID 是一個(gè)隨機(jī)選擇的 160bits（20 字節(jié)）空間，文件的 也使用這樣的 160bits 空間。所謂 ID 相似，具體到什么程度算相似？在 Kademlia 中，距離是通過(guò)異或（XOR）計(jì)算的。我們就不以 160bits 舉例了。我們以 5 位來(lái)舉例。01010 與 01000 的距離，就是兩個(gè) ID 之間的異或值，為 00010，也即為 2。 01010 與 0

15、0010 的距離為 01000，也即為 8,。01010 與 00011 的距離為 01001，也即 8+1=9 。以此類推， 不同的，表示距離更遠(yuǎn)一些；低位不同的，表示距離更近一些，總的距離為所有的不同的位的距離之和。這個(gè)距離不能比喻為地理位置，因?yàn)樵?Kademlia 中，位置近不算近，ID 近才算近，所以我把這個(gè)距離比喻為社交距離，也即在 中的距離，或者社交 中的距離。這個(gè)和你住的位置沒(méi)有關(guān)系， 和人的經(jīng)歷關(guān)系比較大。還是以 5 位 ID 來(lái)舉例，就像在領(lǐng)英中，排第一位的表示最近一份工作在哪里，第二位的表示上一份工作在哪里，然后第三位的是上上份工作，第四位的是 在哪里讀，第五位的表示大學(xué)

16、在哪里讀。如果你是一個(gè)獵頭，在上面找候選人，當(dāng)然最近的那份工作是最重要的。而對(duì)于工作經(jīng)歷越豐富的候選學(xué)在哪里讀的反而越不重要。DHT 中的 是怎么維護(hù)的？就像人一樣，雖然我們常 人的只有少數(shù)，但是 里肯定是遠(yuǎn)近 。DHT 的 也是一樣，遠(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)歸為“k-bucket 1”。如果一個(gè)節(jié)點(diǎn)的 ID，前面所有位數(shù)都相同，從倒數(shù)第 2 位開始不同，這樣的節(jié)點(diǎn)只有

17、 2 個(gè)，即 01000 和 01001，與基礎(chǔ)節(jié)點(diǎn)的異或值為 00010 和 00011，即距離范圍為 2 和 3；對(duì)于 01010 而言，這樣的節(jié)點(diǎn)歸為“k-bucket 2”。如果一個(gè)節(jié)點(diǎn)的 ID，前面所有位數(shù)相同，從倒數(shù)第 i 位開始不同，這樣的節(jié)點(diǎn)只有 2(i-1) 個(gè)，與基礎(chǔ)節(jié)點(diǎn)的距離范圍為 2(i-1), 2i)；對(duì)于 01010 而言，這樣的節(jié)點(diǎn)歸為“k-bucket i”。最終到從倒數(shù) 160 位就開始都不同。你會(huì)發(fā)現(xiàn)，差距越大，陌生人越多，但是 不能都放下，所以每一層都只放 K 個(gè)，這是參數(shù)可以配置。DHT 是如何查找朋友的？假設(shè)，node A 的 ID 為 00110，要

18、找 node B ID 為 10000，異或距離為 10110，距離范圍在 24, 25)，所以這個(gè)目標(biāo)節(jié)點(diǎn)可能在“k-bucket 5”中，這就說(shuō)明 B 的 ID 與 A 的 ID 從第 5 位開始不同， 所以 B 可能在“k-bucket 5”中。然后，A 看看 的 k-bucket 5 有沒(méi)有 B。如果有，太好了，找到你了；如果沒(méi)有，在 k-bucket 5 里隨便找一個(gè) C。因?yàn)槭嵌M(jìn)制，C、B 都和 A 的第 5 位不同，那么 C 的 ID 第 5 位肯定與 B 相同，即它與 B 的距離會(huì)小于 24，相當(dāng)于比 A、B 之間的距離縮短了一半以上。再請(qǐng)求 C，在它 的 里，按同樣的查找方

19、式找一下 B。如果 C 知道 B，就告訴 A；如果 C 也不知道 B，那 C 按同樣的搜索方法，可以在 的 里找到一個(gè)離 B 更近的 D 朋友（D、B 之間距離小于 23），把 D 推薦給 A，A 請(qǐng)求 D 進(jìn)行 查找。Kademlia 的這種 機(jī)制，是通過(guò)折半查找的方式來(lái)收縮范圍，對(duì)于總的節(jié)點(diǎn)數(shù)目為 N，最多只需要log2(N) 次，就能夠找到。例如，圖中這個(gè) 的情況。A 和 B 每一位都不一樣，所以相差 31，A 找到的朋友 C，不巧正好在中間。和 A 的距離是 16，和 B 距離為 15，于是 C 去找的時(shí)候，不巧找到 D，正好又在中間，距離 C 為 8，距離 B 為 7。于是 D 去找

20、的時(shí)候，不巧找到 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 中，朋友之間怎么 呢？ Kademlia 算法中，每個(gè)節(jié)點(diǎn)只有 4 個(gè)指令。PING：測(cè)試一個(gè)節(jié)點(diǎn)是否 ，還活著沒(méi)，相當(dāng)于打個(gè) ，看還能打通不。STORE：要求一個(gè)節(jié)點(diǎn) 一份數(shù)據(jù)，既然加入了組織，有義務(wù)保存一份數(shù)據(jù)。FIND_NODE：根據(jù)節(jié)點(diǎn) ID 查找一個(gè)節(jié)點(diǎn)，就是給一個(gè) 160 位的 ID，通過(guò)上面的方式找到那個(gè)節(jié)點(diǎn)。FIND_VALUE：根據(jù) KEY 查找一個(gè)數(shù)據(jù)，實(shí)則上跟 FIND_NODE 非常類似。KEY 就是文件對(duì)應(yīng)的160 位的 ID，就是要找到保存了文件的節(jié)