John pan

  如果你想要下載一集不存在的回形針視頻，你會怎麼做？
  最簡單的方法當然是我找一個有資源的哥們每羊，讓他把這期視頻發給你。
  早期互聯網，大家就是這樣共享文件的，但是這樣也有很多問題？比如說下載的人一多，每個人分享到的頻寬就變小了，下載速度會變慢，更危險的是，這些視頻是敏感資源，你的哥們本來就不應該分享給你，如果每羊被抓了，大家也都別下載了。
  針對這些問題，美國工程師Bram Cohen在2001年發布了BitTorrent協議，資源不再由一個人或一個中心服務器提供，而是所有人提供給所有人，下載的人越多速度越快，這種模式也叫peer-to-peer，也就是我們常說的P2P下載。
  BitTorrent的核心思想是把文件分成很多個小塊，讓下載者互相連接，以這支117.3MB的視頻為例，被分成了895個128KB的文件塊後，下載了第306塊的用戶A，就可以和下載了第11塊的用戶B，交換彼此下載好的部份，參與的人越多，互相交換的就越密集，下載的越快。為了做到這一點，BitTorrent協議需要資源共享者，生成一個包含下載信息的種子文件，後綴是.torrent，這就是我們常說的BT種子。
  種子文件包含：文件的名字、大小，分塊後每塊文件的大小、哈希值以及Tracker服務器的地址，Tracker很重要，通過Tracker，我們才能找到其他下載者的聯係方式，當你用下載軟體打開種子，就會開始聯係種子文件裡內置的Tracker服務器，告訴Tacker我要下載這文件，服務器會記錄下你的IP，並把其它正在下載或下載完成的人(IP)返回給你，這樣你們就可以愉快的組隊下載了。
  當然，如果沒有找到正在下載的人，資源發布者也不在線，你就只能以0 Kb/s的速度等著了，不難發現，Tracker服務器是P2P網路的弱點，如果Tracker被關閉或封禁，你就無法找到同伴，也難以完成下載。

  為了擺脫對Tracker服務器的依賴，今天最流行的下載方式是磁力鏈接，通常是一串這樣的神祕代碼，前面都是標準格式，最重要的是這40個16進制的數字，任何文件丟進哈希算法都能得到一串這樣字符，40位16進制數字只屬於這文件，你可以把它當成一個文件ID，它能幫助我們找到我們要下載的東西，磁力鏈接的本質，是把所有人都變成一個小型Tracker，每一個人都拿著一份動態更新的地址和文件信息，我要找與我連接的10個人，他們再各自找10個人，一傳十，十傳佰、仟、萬，最後是我找到小明，小明找到老王，老王找到郭冬臨，郭冬臨找到每羊，我和每羊就連上線了，但這種所有人找到所有人的方案，其實不太行，不僅佔用大量的資源，效率也非常低，還有可能重覆傳播，造成廣播災難，這時就需要補充一個關鍵信息"距離"，注意！這裏的距離，不是空間上的距離，而是邏輯上的距離。

  重點來了！接下來！我會詳細解釋磁力鏈接，磁力鏈接用到的DHT網路的構建過程，會有一點點難。但是，如果你理解了會非常有意思，讓我們開始吧！
  剛剛說了，每個磁力鏈接都有一串唯一的文件ID，可以產生2的(4乘40)即2的160次方組合，用的只有0和1的二進制表示，就是160個0和1，而每個節點，也有一串160位的0和1，做為節點ID，根據這160位數，我們可以計算節點和節點之間，節點和資源之間的距離。假設每羊發布了一個文件，就能計算他所知道的節點ID，與這個文件ID的距離，讓算出來距離最短的節點，再計算他知道的節點和文件ID的距離，重覆這個過程，就能找到與文件ID的距離最短的一批節點ID，把每羊提供的下載信息存在這裏，這樣下載者也只需要找到和文件ID距離接近的節點ID，就能建立連接，開始下載，但這距離到底是怎麼算出來的呢？這就是有趣的地方了，
 

 
  用異或算法來計算節點之間的邏輯距離，相同就是0，不同就是1，為了方便你理解，我們簡化一下模型，把160位縮減到4位，假設你的節點ID是0100，目標節點ID是1111，那麼你們之間的二進制距離就是1011，換算成十進制就是11，有了距離，我們就可以在一個這樣的二叉樹裏，快速查找目標了，所有可能的節點ID都在這棵二叉樹上，4位數需要分叉4次，生成2的4次方即16條路徑，每條路徑的終點，就是一個節點ID，接下來，稱作為0100，就可以拆分這棵二叉樹了，從第一次分叉開始，把不包含你的那棵子樹拆分，然後在剩下子樹的第二次分叉處，再次拆分，直到只剩下你自己，這樣，就拆分出了4棵子樹，我們在每個子樹裏選2個點，就得到了4個K桶，呃！不是這個！是這個K-bucket，暫停下來，想想你就會發現，用異或算法計算0號K桶和你的距離是0001，換算成十進制就是1，1號k桶的兩個點，和你的距離是2-3，以此類推，2號K桶的距離區間是4-7，3號K桶的距離區間是8-15，我們剛剛算過，你的節點ID 0110和目標ID 1111之間的二進制距離是1011，換算成十進制是11，也就是說，離1111最近的肯定是3號K桶裏的2個節點，接下來，我們就可以聯係這兩個節點，讓他們幫忙我們找1111，以1110為例，1110也能拆分出4棵子樹，得到4個K桶，計算1110和1111之間的距離，結果是0001，換算成十進制是1，也就是0號K桶，1111就在這裏，這種網路結構被稱為DHT，分布式哈希表，一個高寬容度的去中心網路，只需要一串文件ID，和存儲在本地的K桶數據，你就可以高效的找到要下載的文件。
  而資源的發布者和傳播者，也只需要分享40個數字就好，足夠簡單，方便和隱私，在真實的DHT網路，每個K桶裏至少記錄了8個節點，任何一個節點下線，都不會影響整個網路運行，作為文件和節點ID 2的160次方也是足夠大，大到全地球70億人，每秒下載一萬個種子，也足夠下載百萬億年直到宇宙盡頭。

BT種子設計國外開發者：
David Mazieres  DHT協議-Kademlia網路設計者；美國電腦教授、目前加州矽谷總工程師
Petar Maymounkov  DHT協議-Kademlia網路設計者；東歐工程師
Sylvia Ratnasamy  DHT協議-CAN網路設計者；美國名教授學者
Robert Tappan Morris  DHT協議-Chord網路設計者；他曾經是網路黑客
Ben Y.Zhao  DHT協議-Tapestry網路設計者
Leonard Harris Sassaman  (Zimmermann-Sassaman密鑰簽名協議)；他是化名中本聰創造比特幣？
Bram Cohen -BitTorrent協議設計者；他的生平-維基百科

謝謝收看