1. 背景介紹

1.1 DHT是一種分布式存儲、路由技術(shù)

設(shè)想一個(gè)場景：有一所1000人的學(xué)校，現(xiàn)在學(xué)校突然決定拆掉圖書館（不設(shè)立中心化的服務(wù)器），將圖書館里所有的書都分發(fā)到每位學(xué)生手上（所有的文件分散存儲在各個(gè)節(jié)點(diǎn)上）。那么所有的學(xué)生，共同組成了一個(gè)分布式的圖書館。

圖書館

關(guān)那么現(xiàn)在的關(guān)鍵問題就是這兩個(gè)：

1. 如何分配存儲內(nèi)容到各個(gè)節(jié)點(diǎn)，新增/刪除內(nèi)容如何處理？（每個(gè)同學(xué)手上都分配哪些書）
2. 一個(gè)節(jié)點(diǎn)如果想獲取某個(gè)特定的文件，如何找到存儲文件的節(jié)點(diǎn)/地址/路徑？（如何尋找需要的書籍）
   針對這兩個(gè)問題，有一種非常樸素的思想：向網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都發(fā)送查詢請求；每個(gè)節(jié)點(diǎn)都“幫忙”轉(zhuǎn)發(fā)其他節(jié)點(diǎn)查詢請求。這種思想叫做泛洪查詢。
   
   泛洪查詢
   
   顯然，這種查詢的效率非常低，也會造成所謂的“泛洪風(fēng)暴”。那么有沒有改進(jìn)方法呢？當(dāng)然有的，這種方法叫做Gossip，本質(zhì)上一種克制的泛洪。
   我們先看一個(gè)理論，六度分隔理論：你和任何一個(gè)陌生人之間所間隔的人不會超過五個(gè)。也就是說，最多通過五個(gè)人你就能夠認(rèn)識任何一個(gè)陌生人。以下就是關(guān)于Gossip的詳細(xì)介紹。

• Gossip 類似于疾病的傳染，被感染節(jié)點(diǎn)隨機(jī)選擇 k 個(gè)鄰接節(jié)點(diǎn)（fan-out）散播消息，假設(shè)把 fan-out 設(shè)置為2，每次最多往2個(gè)節(jié)點(diǎn)散播
• 每次散播消息都選擇尚未發(fā)送過的節(jié)點(diǎn)進(jìn)行散播

• 收到消息的節(jié)點(diǎn)不再往發(fā)送節(jié)點(diǎn)散播，比如 A -> B，那么 B 進(jìn)行散播的時(shí)候，不再發(fā)給 A

  
  
  Gossip

1.2 從哈希表到分布式哈希表

哈希表這種數(shù)據(jù)結(jié)構(gòu)，通常會包含K個(gè)bucket（k桶）?！巴啊庇脕泶鎯Χ鄠€(gè)鍵值對，可以看做一個(gè)動態(tài)數(shù)組。對某個(gè)KEY進(jìn)行查找時(shí)：先通過Hash函數(shù)，計(jì)算出散列值，然后取模，得到對應(yīng)的Bucket編號

哈希表

分布式哈希表

1.3 節(jié)點(diǎn)路由

問題描述：由于手上只有一部分同學(xué)的通訊錄（Bootstrap節(jié)點(diǎn)），你很可能并沒有00010000的手機(jī)號（IP地址）。那如何聯(lián)系上目標(biāo)同學(xué)，向他發(fā)出請求呢？
算法思想：如果一個(gè)同學(xué)離你越近，你手上的通訊錄里存有ta的手機(jī)號碼的概率越大。
當(dāng)你知道目標(biāo)同學(xué)Z與你之間的距離，你可以在你的通訊錄上先找到一個(gè)你認(rèn)為與同學(xué)Z最相近的同學(xué)B，請同學(xué)B再進(jìn)一步去查找同學(xué)Z的手機(jī)號。
那么，一種合適的舉例算法就非常重要。這里我們采用漢明距（XOR）作為距離度量：學(xué)號（Node ID）之間的異或距離（XOR distance）。0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（相異取真）。比如 01000000 與 00000001 距離為 01000001（換算為十進(jìn)制即為26+1，即65）

1.4 為什么需要DHT

DHT技術(shù)主要是為了解決P2P網(wǎng)絡(luò)發(fā)展中遇到的種種問題。在 P2P 網(wǎng)絡(luò)的發(fā)展過程中，出現(xiàn)過3種不同的技術(shù)路線：

1. 中央服務(wù)器模式：每個(gè)節(jié)點(diǎn)都需要先連接到中央服務(wù)器，然后才能查找到自己想要的文件在哪里。中央服務(wù)器成為整個(gè) P2P 網(wǎng)絡(luò)的【單點(diǎn)故障】，典型代表：Napster
2. 廣播模式：要找文件的時(shí)候，每個(gè)節(jié)點(diǎn)都向自己相連的【所有節(jié)點(diǎn)】進(jìn)行詢問；被詢問的節(jié)點(diǎn)如果不知道這個(gè)文件在哪里，就再次進(jìn)行“廣播”如此往復(fù)，直至找到所需文件
3. DHT模式：承載海量數(shù)據(jù)。由于數(shù)據(jù)是海量的，每個(gè)節(jié)點(diǎn)只能存儲整個(gè)系統(tǒng)的一小部分?jǐn)?shù)據(jù)。需要把數(shù)據(jù)【均勻分?jǐn)偂康矫總€(gè)節(jié)點(diǎn)

2. DHT簡介

2.1 DHT需要解決的問題

1. 去中心化帶來的問題：如何設(shè)計(jì)高效的存儲、內(nèi)容路由算法。
2. 數(shù)據(jù)量大帶來的問題：如何設(shè)計(jì)高效的存儲、內(nèi)容路由算法。
3. 節(jié)點(diǎn)動態(tài)變化的問題：參與DHT的計(jì)算節(jié)點(diǎn)會頻繁變化，每時(shí)每刻都有新的節(jié)點(diǎn)上線、舊的節(jié)點(diǎn)下線。
4. 高效查詢困哪的問題：如何快速定位節(jié)點(diǎn)，同時(shí)又不消耗太多網(wǎng)絡(luò)資源？

2.2 DHT設(shè)計(jì)思路

1. 散列算法的選擇：DHT 通常是直接拿數(shù)據(jù)的散列值作為 key，數(shù)據(jù)本身作為 value。那么。散列函數(shù)產(chǎn)生的“散列值范圍”（keyspace）要足夠大，以防止太多的碰撞。那么我們更進(jìn)一步， 讓keyspace足夠大，使得“隨機(jī)碰撞”的概率小到忽略不計(jì)。這樣有助于簡化DHT的系統(tǒng)設(shè)計(jì)。通常的 DHT 都會采用大于等于 128 比特的散列值
2. 同構(gòu)的node ID與data key：給每一個(gè)node分配唯一的ID，將分布式系統(tǒng)與實(shí)際物理網(wǎng)絡(luò)解耦。邏輯上相鄰的節(jié)點(diǎn)，可能實(shí)際上相距很遠(yuǎn)。這樣設(shè)計(jì)，有以下好處：

• 散列值空間足夠大的時(shí)候，隨機(jī)碰撞忽略不計(jì)，因此也就確保了 node ID 的唯一性
• 可以簡化系統(tǒng)設(shè)計(jì)——比如簡化路由算法

3. 拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)：Key-based routing（key 本身已經(jīng)提供了足夠多的路由信息）
   當(dāng)某個(gè)分布式系統(tǒng)具有自己的拓?fù)浣Y(jié)構(gòu)，它本身成為一個(gè)覆蓋網(wǎng)絡(luò)（Overlay Network）所謂的覆蓋網(wǎng)絡(luò)，通俗地說就是“網(wǎng)絡(luò)之上的網(wǎng)絡(luò)”。由于前面分布式系統(tǒng)與實(shí)際物理網(wǎng)絡(luò)解耦的設(shè)計(jì)，使得DHT在設(shè)計(jì)拓?fù)浣Y(jié)構(gòu)和路由算法時(shí)，只需要考慮 node ID，而不用考慮其下層網(wǎng)絡(luò)的屬性。
4. 路由算法設(shè)計(jì)：由于 DHT 中的節(jié)點(diǎn)數(shù)可能非常多，而且這些節(jié)點(diǎn)是動態(tài)變化的。因此就不可能讓每一個(gè)節(jié)點(diǎn)都記錄所有其它節(jié)點(diǎn)的信息。所以，每個(gè)節(jié)點(diǎn)通常只知道少數(shù)一些節(jié)點(diǎn)的信息。這樣就需要設(shè)計(jì)某種路由算法，盡可能利用已知的節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)。

3. Kademlia DHT算法

3.1 簡介

Kademlia是分布式哈希表（Distributed Hash Table, DHT）的一種。而DHT是一類去中心化的分布式系統(tǒng)。在這類系統(tǒng)中，每個(gè)節(jié)點(diǎn)（node）分別維護(hù)一部分的存儲內(nèi)容以及其他節(jié)點(diǎn)的路由/地址，使得網(wǎng)絡(luò)中任何參與者（即節(jié)點(diǎn)）發(fā)生變更（進(jìn)入/退出）時(shí)，對整個(gè)網(wǎng)絡(luò)造成的影響最小。DHT可以用于構(gòu)建更復(fù)雜的應(yīng)用，包括分布式文件系統(tǒng)、點(diǎn)對點(diǎn)技術(shù)文件分享系統(tǒng)、合作的網(wǎng)頁高速緩存、域名系統(tǒng)以及實(shí)時(shí)通信等。
Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所設(shè)計(jì)，以異或距離來對哈希表進(jìn)行分層是其特點(diǎn)。Kademlia后來被eMule、BitTorrent等P2P軟件采用作為底層算法。
Kademlia的優(yōu)點(diǎn)在于：

• 對于任意一個(gè)有[ 2(n?1) ,2??)個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，最多只需要n步搜索即可找到目標(biāo)節(jié)點(diǎn)；
• K-bucket的更新機(jī)制一定程度上保持了網(wǎng)絡(luò)的活性和安全性。

3.2 Kademlia DHT拓?fù)浣Y(jié)構(gòu)：二叉樹

Kademlia采用了“node ID 與 data key 同構(gòu)”的設(shè)計(jì)思路。Kademlia 采用某種算法把 key 映射到一個(gè)二叉樹，每一個(gè) key 都是這個(gè)二叉樹的葉子。在映射之前，先做以下預(yù)處理。

1. 先把 key 以二進(jìn)制形式表示，然后從高位到低位依次處理
2. 二進(jìn)制的第 n 個(gè) bit 就對應(yīng)了二叉樹的第 n 層
3. 如果該位是 1，進(jìn)入左子樹，是 0 則進(jìn)入右子樹

4. 把每一個(gè) key 縮短為它的最短唯一前綴。

   
   
   拓?fù)浣Y(jié)構(gòu)
   
   

   Kad 使用 160比特 的散列算法（比如 SHA1），完整的 key 用二進(jìn)制表示有 160 個(gè)數(shù)位（bit）。實(shí)際運(yùn)行的 Kad 網(wǎng)絡(luò)，即使有幾百萬個(gè)節(jié)點(diǎn)，相比 keyspace（2^160）也只是很小很小很小的一個(gè)子集。其次，由于散列函數(shù)的特點(diǎn)，key 的分布是高度隨機(jī)的。因此任何兩個(gè) key 都不會非常臨近。所以，使用“最短唯一前綴”來處理 key 的二進(jìn)制形式，得到的結(jié)果就會很短

3.3 二叉樹拆分

二叉樹拆分：對每一個(gè)節(jié)點(diǎn)，都可以按照自己的視角對整個(gè)二叉樹進(jìn)行拆分。
拆分規(guī)則：先從根節(jié)點(diǎn)開始，把不包含自己的那個(gè)子樹拆分出來；然后在剩下的子樹再拆分不包含自己的下一層子樹；以此類推，直到最后只剩下自己。

拆分

Kademlia 默認(rèn)的散列值空間是 m = 160（散列值有 160 bits），因此拆分出來的子樹最多有 160 個(gè)（考慮到實(shí)際的節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)小于2^160，子樹的個(gè)數(shù)會明顯小于 160）。對于每一個(gè)節(jié)點(diǎn)而言，當(dāng)它以自己的視角完成子樹拆分后，會得到 n 個(gè)子樹；對于每個(gè)子樹，如果它都能知道里面的一個(gè)節(jié)點(diǎn)，那么它就可以利用這 n 個(gè)節(jié)點(diǎn)進(jìn)行遞歸路由，從而到達(dá)整個(gè)二叉樹的任何一個(gè)節(jié)點(diǎn)。

3.4 距離定義：XOR

DHT將其他的peer節(jié)點(diǎn)，按照與自己的距離，劃分到不同的k桶（k-bucket）當(dāng)中
以0000110為基礎(chǔ)節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)的ID，前面所有位數(shù)都與它相同，只有最后1位不同，這樣的節(jié)點(diǎn)只有1個(gè)——0000111，與基礎(chǔ)節(jié)點(diǎn)的異或值為0000001，即距離為1；對于0000110而言，這樣的節(jié)點(diǎn)歸為“k-bucket 1”
如果一個(gè)節(jié)點(diǎn)的ID，前面所有位數(shù)相同，從倒數(shù)第2位開始不同，這樣的節(jié)點(diǎn)只有2個(gè)：0000101、0000100，與基礎(chǔ)節(jié)點(diǎn)的異或值為0000011和0000010，即距離范圍為3和2；對于0000110而言，這樣的節(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), 2^i）；對于0000110而言，這樣的節(jié)點(diǎn)歸為“k-bucket i”
將整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)梳理為一個(gè)按節(jié)點(diǎn)ID排列的二叉樹，樹最末端的每個(gè)葉子便是一個(gè)節(jié)點(diǎn)，則下圖就比較直觀的展現(xiàn)出，節(jié)點(diǎn)之間的距離的關(guān)系

節(jié)點(diǎn)距離

3.5 K-Bucket

每個(gè)節(jié)點(diǎn)在完成子樹拆分后，只需要知道每個(gè)子樹里面的一個(gè)節(jié)點(diǎn)，就足以實(shí)現(xiàn)全遍歷。但是考慮到健壯性，只知道一個(gè)節(jié)點(diǎn)顯然是不夠的，需要知道多個(gè)才比較保險(xiǎn)。
所以 Kademlia 論文中給出了一個(gè)K-桶（K-bucket）的概念：每個(gè)節(jié)點(diǎn)在完成子樹拆分后，要記錄每個(gè)子樹里面的 K 個(gè)節(jié)點(diǎn)。這里所說的 K 是一個(gè)常量，由使用 Kademlia的軟件自行設(shè)定（比如 BitTorent 下載軟件使用的 Kademlia網(wǎng)絡(luò)，K 設(shè)定為 8）。
這個(gè)K-桶其實(shí)就是路由表。對于某個(gè)節(jié)點(diǎn)而言，如果以它自己為視角拆分了 n 個(gè)子樹，那么它就需要維護(hù) n 個(gè)路由表，并且每個(gè)路由表的上限是 K。
K 只是一個(gè)上限，因?yàn)橛袃煞N情況使得 K 桶的尺寸會小于 K：

1. 距離越近的子樹就越小。如果整個(gè)子樹可能存在的節(jié)點(diǎn)數(shù)小于 K，那么該子樹的 K 桶尺寸永遠(yuǎn)也不可能達(dá)到 K。
2. 有些子樹雖然實(shí)際上線的節(jié)點(diǎn)數(shù)超過 K，但是因?yàn)榉N種原因，沒有收集到該子樹足夠多的節(jié)點(diǎn)，這也會使得該子樹的 K 桶尺寸小于 K。

（以K=2舉例，每個(gè)子樹只保留2個(gè)節(jié)點(diǎn)，既：每層路由表中只保存兩個(gè)節(jié)點(diǎn)的路由信息）

子樹拆分

每個(gè)節(jié)點(diǎn)只維護(hù)一部分的路由表，這個(gè)路由表按照距離分層，即k-bucket1, k-bucket 2, k-bucket 3
雖然每個(gè)k-bucket中實(shí)際存在的節(jié)點(diǎn)數(shù)逐漸增多，但每個(gè)節(jié)點(diǎn)在它自己的每個(gè)k-bucket中只記錄k個(gè)節(jié)點(diǎn)的路由信息（IP地址與端口號）。
由于節(jié)點(diǎn)的ID有160位，所以每個(gè)節(jié)點(diǎn)的路由表總共分160層，既：節(jié)點(diǎn)共有160個(gè)k-bucket。整個(gè)網(wǎng)絡(luò)最多可以容納2^160個(gè)節(jié)點(diǎn)，但是每個(gè)節(jié)點(diǎn)最多只維護(hù)160 * k 行路由信息。

K桶

3.5 Kad DHT的Peer交流機(jī)制

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

• PING：測試一個(gè)節(jié)點(diǎn)是否在線
• STORE：要求一個(gè)節(jié)點(diǎn)存儲一份數(shù)據(jù)
• FIND_NODE：根據(jù)節(jié)點(diǎn)ID查找一個(gè)節(jié)點(diǎn)
• FIND_VALUE：根據(jù)KEY查找一個(gè)數(shù)據(jù)，實(shí)則上跟FIND_NODE非常類似
  K-桶的刷新機(jī)制大致有如下幾種，該機(jī)制保證了任意節(jié)點(diǎn)加入和離開都不影響整體網(wǎng)絡(luò)

1. 主動收集節(jié)點(diǎn)：任何節(jié)點(diǎn)都可以主動發(fā)起“查詢節(jié)點(diǎn)”的請求（對應(yīng)于協(xié)議類型 FIND_NODE），從而刷新 K 桶中的節(jié)點(diǎn)信息
2. 被動收集節(jié)點(diǎn)：如果收到其它節(jié)點(diǎn)發(fā)來的請求（協(xié)議類型 FIND_NODE 或 FIND_VALUE），會把對方的 ID 加入自己的某個(gè) K 桶中。
3. 探測失效節(jié)點(diǎn)：Kad 還是支持一種探測機(jī)制（協(xié)議類型 PING），可以判斷某個(gè) ID 的節(jié)點(diǎn)是否在線。因此就可以定期探測路由表中的每一個(gè)節(jié)點(diǎn)，然后把下線的節(jié)點(diǎn)從路由表中干掉。

那么一個(gè)節(jié)點(diǎn)加入DHT的流程就如下所描述：

1. 任何一個(gè)新來的節(jié)點(diǎn)（假設(shè)叫 A），需要先跟 DHT 中已有的任一節(jié)點(diǎn)（假設(shè)叫 B）建立連接。
2. A 隨機(jī)生成一個(gè)散列值作為自己的 ID（對于足夠大的散列值空間，ID 相同的概率忽略不計(jì)）
3. A 向 B 發(fā)起一個(gè)查詢請求（協(xié)議類型 FIND_NODE），請求的 ID 是自己（通俗地說，就是查詢自己）
4. B 收到該請求之后，會先把 A 的 ID 加入自己的某個(gè) K 桶中。然后，根據(jù) FIND_NODE 協(xié)議的約定，B 會找到K個(gè)最接近 A 的節(jié)點(diǎn)，并返回給 A。
5. A 收到這 K 個(gè)節(jié)點(diǎn)的 ID 之后，開始初始化自己的 K 桶。
6. 然后 A 會繼續(xù)向剛剛拿到的這批節(jié)點(diǎn)發(fā)送查詢請求（協(xié)議類型 FIND_NODE），如此往復(fù)，直至 A 建立了足夠詳細(xì)的路由表。

4. DHT應(yīng)用舉例

回到我們最初找書的案例當(dāng)中，假設(shè)有1000名學(xué)生，Kademlia取m=8，K=4
場景：學(xué)生A尚未加入DHT網(wǎng)絡(luò)，但他想從網(wǎng)絡(luò)中獲取《分布式系統(tǒng)設(shè)計(jì)》這本書

舉例

1. 學(xué)生A加入網(wǎng)絡(luò)，自行隨機(jī)生成一個(gè)ID，例： 00000110
2. 建立路由表（細(xì)節(jié)忽略）
3. 計(jì)算《分布式系統(tǒng)設(shè)計(jì)》書的Hash，假設(shè)是：00010000
4. 假設(shè)學(xué)生Z的ID就是00010000，那么意味著這本書在Z那里，或者與Z臨近的K個(gè)同學(xué)那里
5. 計(jì)算Z與A的距離：XOR得出結(jié)果00010110，從第5位開始不同，離范圍在[2^4, 2^5)。所以Z可能在k-bucket 5中
6. A查看自己的路由表，k-bucket 5中有無Z
   · 如果有，那么直接聯(lián)系Z，獲取書籍
   · 如果沒有，在A的k-bucket 5中隨機(jī)找一個(gè)學(xué)生B（B學(xué)號的第五位一定是與Z相同的，既B與Z的距離小于2^4，距離縮短了一半以上）。B將會重復(fù)相同的流程（步驟5-6）遞歸。

5. 總結(jié)

• Kademlia的這種查詢機(jī)制，每次要么找到，要么將搜索范圍減半。網(wǎng)絡(luò)中節(jié)點(diǎn)2^n個(gè)，最多只需要n步搜索即可找到目標(biāo)節(jié)點(diǎn)。DHT網(wǎng)絡(luò)中，通常n=160
• K-bucket的更新機(jī)制一定程度上保持了網(wǎng)絡(luò)的活性和安全性：每個(gè)節(jié)點(diǎn)的K-bucket都不相同，并且只包含了少部分節(jié)點(diǎn)的信息
• 拓?fù)浣Y(jié)構(gòu)簡單、距離算法也很簡單
• 天生支持并發(fā)
• 節(jié)點(diǎn)退出無需任何操作，適合波動大的分布式網(wǎng)絡(luò)