DHT算法的一知半解
如果所有的數(shù)據(jù)結(jié)構(gòu)只能留下一種，那可能就是哈希表。
哈希表是一種能高效進(jìn)行數(shù)據(jù)讀取/寫(xiě)入的數(shù)據(jù)結(jié)構(gòu)，通過(guò)哈希函數(shù)可以將任意的數(shù)據(jù)映像到固定長(zhǎng)度的隨機(jī)字符串，由于函數(shù)具有單向性與唯一性，因此這個(gè)隨機(jī)字符串可以作為辨識(shí)數(shù)據(jù)的指紋，即Key。讀取哈希表的數(shù)據(jù)(Value)，只需提供key，哈希表即可取得映像到該鍵值的完整數(shù)據(jù)。
DHT，Distributed Hash Table，即分布式哈希表，應(yīng)用于網(wǎng)絡(luò)之上的覆蓋網(wǎng)絡(luò)，典型的應(yīng)用場(chǎng)景就是點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)（P2P網(wǎng)絡(luò)）。關(guān)于P2P 網(wǎng)絡(luò)，可以參考《這是你所了解的P2P么》一文。在P2P網(wǎng)絡(luò)中，有著結(jié)構(gòu)化，半結(jié)構(gòu)化和非結(jié)構(gòu)化的系統(tǒng)分類。在結(jié)構(gòu)化P2P系統(tǒng)中，每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定的信息或特定信息的索引。當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時(shí)，必須知道這些信息(或索引)可能存在于那些節(jié)點(diǎn)中。由于用戶預(yù)先知道應(yīng)該搜索哪些節(jié)點(diǎn)，避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的洪泛式查找，因此提高了信息搜索的效率。
結(jié)構(gòu)化P2P 用純分布式的消息路由，目前的主流方法是采用分布式哈希表(DHT)技術(shù)。在不需要服務(wù)器的情況下，每個(gè)客戶端負(fù)責(zé)一個(gè)小范圍的路由，并負(fù)責(zé)存儲(chǔ)一小部分?jǐn)?shù)據(jù)，從而實(shí)現(xiàn)整個(gè)DHT網(wǎng)絡(luò)的尋址和存儲(chǔ)。DHT 各節(jié)點(diǎn)并不需要維護(hù)整個(gè)網(wǎng)絡(luò)的信息，節(jié)點(diǎn)僅存儲(chǔ)其臨近的后繼節(jié)點(diǎn)信息，因此較少的路由信息就可以有效地實(shí)現(xiàn)資源定位。該P(yáng)2P 網(wǎng)絡(luò)模式有效減少了資源定位的開(kāi)銷，提高了P2P 網(wǎng)絡(luò)的可擴(kuò)展性。
DHT的去中心化提供了相比于傳統(tǒng)的鍵值對(duì)存儲(chǔ)更好的優(yōu)勢(shì)。包括：
擴(kuò)展性：哈希請(qǐng)求最多為對(duì)數(shù)次查找即可解決。
通過(guò)冗余進(jìn)行容錯(cuò)。即可能每一個(gè)節(jié)點(diǎn)都加入或離開(kāi)DHT。另外，如果一個(gè)節(jié)點(diǎn)反應(yīng)緩慢或者不可達(dá)，請(qǐng)求可以連接到其他節(jié)點(diǎn)。
負(fù)載均衡，請(qǐng)求可以發(fā)送到任何節(jié)點(diǎn)，沒(méi)有任何一個(gè)節(jié)點(diǎn)處理所有的請(qǐng)求，例如基于DHT的DNS服務(wù)能夠擁有更好的負(fù)載均衡特性。
那么，DHT 是如何實(shí)現(xiàn)P2P網(wǎng)絡(luò)中的尋址或者路由呢？
如果key是某個(gè)實(shí)體的標(biāo)識(shí)，value是實(shí)體的具體地址，則DHT 就可以用來(lái)選址。在Ethereum中，DHT就作為一種高效的對(duì)等節(jié)點(diǎn)選擇機(jī)制(PeerSelection)。所有可能出現(xiàn)的實(shí)體識(shí)別集合，稱之為鍵值空間(Key Space)。如果以m表示識(shí)別符的位數(shù)，若m=160，則鍵值空間大小為21??。于是，通過(guò)對(duì)鍵值空間進(jìn)行不同的設(shè)計(jì)，就出現(xiàn)了不同的DHT算法，通過(guò)這些算法即可實(shí)現(xiàn)在P2P網(wǎng)絡(luò)中的尋址或者路由。
DHT 算法之 Kademlia
Kademlia于2002年被Petar Maymounkov和David Mazieres兩人發(fā)表，Ethereum也使用Kademlia作為GossipProtocol的節(jié)點(diǎn)選擇機(jī)制，IPFS更是引入改良后的S/Kademlia作為核心。
Kademlia 使用 m 位整數(shù)作為節(jié)點(diǎn)和資源的唯一標(biāo)識(shí)。與 Chord 中的 "區(qū)間負(fù)責(zé)制" 不同, Kademlia 中的資源都是被離它最近的節(jié)點(diǎn)負(fù)責(zé)。出于容錯(cuò)考慮, 每個(gè)資源通常都被距離它最近的 k 個(gè)節(jié)點(diǎn)負(fù)責(zé), 這里 k 是一個(gè)常量, 通常取 k 使得在系統(tǒng)中任意 k 個(gè)節(jié)點(diǎn)都不太可能在一小時(shí)之內(nèi)同時(shí)失效。
Kademlia的鍵值空間可以表示成一棵二叉樹(shù) 每個(gè)節(jié)點(diǎn)都可以看作一顆高度為 m + 1 的二叉樹(shù)上的葉子節(jié)點(diǎn)。把 ID 二進(jìn)制展開(kāi), 從最高位開(kāi)始, 自根節(jié)點(diǎn)逢 1 向左逢 0 向右, 直到抵達(dá)葉子節(jié)點(diǎn)。節(jié)點(diǎn)的距離則定義為XOR運(yùn)算結(jié)果。也就是說(shuō)，兩實(shí)體標(biāo)識(shí)的距離可以視為其差異程度。異或運(yùn)算的特點(diǎn)是異為真同為假, 如果兩個(gè) ID 高位相異低位相同, 它們異或的結(jié)果就大; 如果它們高位相同低位相異, 異或的結(jié)果就小。這與二叉樹(shù)中葉子的位置分布是一致的: 如果兩個(gè)節(jié)點(diǎn)共有的祖先節(jié)點(diǎn)少(高位相異), 它們的距離就遠(yuǎn); 反之, 如果共有的祖先節(jié)點(diǎn)多(高位相同), 它們的距離就近。
這種通過(guò)“異或”進(jìn)行的距離測(cè)量，具有以下幾何特征：
(A ⊕ B) == (B ⊕ A): XOR 符合“交換律”，具備對(duì)稱性。A和B的距離從哪一個(gè)節(jié)點(diǎn)計(jì)算都是相同的。
(A ⊕ A) == 0: 反身性，自己和自己的距離為零。
(A ⊕ B) > 0: 兩個(gè)不同的 key 之間的距離必大于零。
(A ⊕ B) + (B ⊕ C) >= (A ⊕ C): 三角不等式, A經(jīng)過(guò)B到C的距離總是大于A直接到C的距離。
Kademlia 的路由
Kademlia的路由表切分成不同的距離區(qū)間，查詢過(guò)程可視為從一棵子樹(shù)跳到另一棵子樹(shù)，直到找到與目標(biāo)最近的子樹(shù)為止。因此，Kademlia屬于高效的二元搜尋。Kademlia的距離對(duì)稱性使得每個(gè)新節(jié)點(diǎn)加入后可以同步更新其每個(gè)新鄰員的路由表，大幅增加網(wǎng)絡(luò)效率。而最近更新的節(jié)點(diǎn)，則會(huì)是k桶當(dāng)中的查詢的第一順位，這又再次增加了Kademlia的強(qiáng)健性。
對(duì)于任意一個(gè)給定節(jié)點(diǎn), 二叉樹(shù)從根節(jié)點(diǎn)開(kāi)始不斷向下分成一系列不包含該節(jié)點(diǎn)的子樹(shù)。最高的子樹(shù)由不包含該節(jié)點(diǎn)的二叉樹(shù)的一半組成, 下一個(gè)子樹(shù)又由不包含該節(jié)點(diǎn)的剩余樹(shù)的一半組成, 以此類推。如果這個(gè)二叉樹(shù)的高度為 m + 1, 最終會(huì)得到 m 個(gè)子樹(shù)。接著，在每個(gè)子樹(shù)中任取 k 個(gè)節(jié)點(diǎn), 形成 m 個(gè) k 桶(k-bucket), 這 m 個(gè) k 桶就是 Kademlia 節(jié)點(diǎn)的路由表。下圖展示了 m = 3, k = 2 時(shí)節(jié)點(diǎn) 101 的 k 桶。
Kademlia 中每個(gè)節(jié)點(diǎn)都有一個(gè)基礎(chǔ)操作, 稱為 FIND_NODE 操作。FIND_NODE 接受一個(gè) Key 作為參數(shù), 返回當(dāng)前節(jié)點(diǎn)所知道的 k 個(gè)距離這個(gè) Key 最近的節(jié)點(diǎn)。基于 k 桶, 先求出這個(gè) Key 與當(dāng)前節(jié)點(diǎn)的的距離 d, 第 i個(gè) k 桶中節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離總是在區(qū)間2^i~2^(i+1)之內(nèi), 這些區(qū)間都不會(huì)互相重疊, 那么，d落在的區(qū)間所屬的 k 桶中的節(jié)點(diǎn)就是距離這個(gè) Key 最近的節(jié)點(diǎn)。如果這個(gè) k 桶中的節(jié)點(diǎn)不足 k 個(gè), 則在后一個(gè) k 桶中取節(jié)點(diǎn)補(bǔ)充, 如果還不夠就再在后一個(gè) k 桶中取。如果這個(gè)節(jié)點(diǎn)所有的 k 桶中的節(jié)點(diǎn)數(shù)之和都不足 k 個(gè), 就返回它所知道的所有節(jié)點(diǎn)。
Kademlia 中最重要的過(guò)程是節(jié)點(diǎn)查找,給定一個(gè) Key, 找出整個(gè)系統(tǒng)中距離它最近的 k 個(gè)節(jié)點(diǎn)。這是一個(gè)遞歸過(guò)程: 首先初始節(jié)點(diǎn)調(diào)用自己的FIND_NODE, 找到 k 個(gè)它所知的距離 Key 最近的節(jié)點(diǎn)。接下來(lái)，在這 k 個(gè)節(jié)點(diǎn)中取 α個(gè)最近的節(jié)點(diǎn), 同時(shí)請(qǐng)求它們?yōu)?Key 執(zhí)行 FIND_NODE。這里的 α也是一個(gè)常量, 作用是同時(shí)請(qǐng)求提高效率, 例如 α=3。
在接下來(lái)的遞歸過(guò)程中, 初始節(jié)點(diǎn)每次都在上一次請(qǐng)求后返回的節(jié)點(diǎn)中取 α個(gè)最近的, 并且未被請(qǐng)求過(guò)的節(jié)點(diǎn), 然后請(qǐng)求它們?yōu)?Key 執(zhí)行FIND_NODE, 以此類推。每執(zhí)行一次, 返回的節(jié)點(diǎn)就距離目標(biāo)近一點(diǎn)。如果某次請(qǐng)求返回的節(jié)點(diǎn)不比上次請(qǐng)求返回的節(jié)點(diǎn)距目標(biāo) Key 近, 就向所有未請(qǐng)求過(guò)的節(jié)點(diǎn)請(qǐng)求執(zhí)行 FIND_NODE。如果還不能獲取更近的節(jié)點(diǎn), 過(guò)程就終止。這時(shí)，在其中取 k 個(gè)距離 Key 最近的節(jié)點(diǎn), 就是節(jié)點(diǎn)查找的結(jié)果。
Kademlia 的拓?fù)浣Y(jié)構(gòu)是單向的, 其他離目標(biāo)資源比自己遠(yuǎn)的節(jié)點(diǎn)在查找時(shí)就很可能會(huì)經(jīng)由緩存的節(jié)點(diǎn), 這樣就能提前終止查找, 提高了查找效率。
Kademlia節(jié)點(diǎn)的加入與退出
要想加入 Kademlia, 首先使用一些算法生成自己的 ID, 然后它需要通過(guò)一些外部手段獲取到系統(tǒng)中的任意一個(gè)節(jié)點(diǎn) n′, 把 n′加入到合適的 k 桶中。然后對(duì)自己的 ID 執(zhí)行一次節(jié)點(diǎn)查找。在查找的過(guò)程中新節(jié)點(diǎn) n′就能自動(dòng)構(gòu)建好自己的 k 桶, 同時(shí)把自己插入到其他合適節(jié)點(diǎn)的 k 桶中。
節(jié)點(diǎn)加入時(shí)除了構(gòu)建 k 桶之外, 還應(yīng)該可以取回這個(gè)節(jié)點(diǎn)應(yīng)負(fù)責(zé)的資源。Kademlia 的做法是每隔一段時(shí)間（如按小時(shí)），所有的節(jié)點(diǎn)都對(duì)其擁有的資源執(zhí)行一次發(fā)布操作; 此外，在每隔一段時(shí)間(如按天)節(jié)點(diǎn)就會(huì)丟棄這段時(shí)間內(nèi)未收到發(fā)布消息的資源。這樣新節(jié)點(diǎn)就能收到自己須負(fù)責(zé)的資源, 同時(shí)資源總能保持被 k 個(gè)距離它最近的節(jié)點(diǎn)負(fù)責(zé)。
為了優(yōu)化重復(fù)發(fā)布, 當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)資源的發(fā)布消息, 它就不會(huì)在下一個(gè)小時(shí)重發(fā)它。因?yàn)楫?dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)資源的發(fā)布消息, 它就可以認(rèn)為有 k - 1 個(gè)其他節(jié)點(diǎn)也收到了這個(gè)資源的發(fā)布消息。只要節(jié)點(diǎn)重發(fā)資源的節(jié)奏不一致, 這就能保證每個(gè)資源都始終只有一個(gè)節(jié)點(diǎn)在重發(fā)。
鑒于此, 不需要為節(jié)點(diǎn)的失效和離開(kāi)做任何其它的工作，這也是 Kademlia 的容錯(cuò)性要高于其他分布式哈希表算法。
DHT算法之 Chord
Chord 中每個(gè)key和節(jié)點(diǎn)都分別擁有一個(gè)m 比特的標(biāo)識(shí)符。Key標(biāo)識(shí)符K 通過(guò)哈希關(guān)鍵字本身得到，而節(jié)點(diǎn)標(biāo)識(shí)符N 則通過(guò)哈希節(jié)點(diǎn)的IP 地址得到。哈希函數(shù)可以選用SHA-1。所有節(jié)點(diǎn)按照其節(jié)點(diǎn)標(biāo)識(shí)符從小到大（取模2^m 后）沿著順時(shí)針?lè)较蚺帕性谝粋€(gè)邏輯的標(biāo)識(shí)圓環(huán)上，稱為Chord 環(huán)。
Chord 的映射規(guī)則是：關(guān)鍵字標(biāo)識(shí)為K 的(K, V)對(duì)存儲(chǔ)在這樣的節(jié)點(diǎn)上，該節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)等于K 或者在Chord 環(huán)上緊跟在K 之后，這個(gè)節(jié)點(diǎn)被稱為K 的后繼節(jié)點(diǎn)，表示為successor(K)。因?yàn)闃?biāo)識(shí)符采用m 位二進(jìn)制數(shù)表示，并且從0 到2^m－1 順序排列成一個(gè)圓圈successor(K)就是從K 開(kāi)始順時(shí)針?lè)较蚓嚯xK 最近的節(jié)點(diǎn)。
Chord 的路由
為了快速查詢，Chord每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)路由表，稱為指針表。如果關(guān)鍵字和節(jié)點(diǎn)標(biāo)識(shí)符用m 位二進(jìn)制位數(shù)表示，那么指針表中最多含有m 個(gè)表項(xiàng)。節(jié)點(diǎn)n 的指針表中第i 項(xiàng)是圓環(huán)上標(biāo)識(shí)大于或等于n+2^(i-1) 的第一個(gè)節(jié)點(diǎn)。例如若s=successor(n+2^(i-1)), 1≤i≤m，則稱節(jié)點(diǎn)s為節(jié)點(diǎn)n 的第i 個(gè)指針，就是節(jié)點(diǎn)n 的后繼節(jié)點(diǎn)。指針表中每一項(xiàng)既包含相關(guān)節(jié)點(diǎn)的標(biāo)識(shí)，又包含該節(jié)點(diǎn)的IP 地址和端口號(hào)。
維護(hù)指針表使得每個(gè)節(jié)點(diǎn)只需要知道網(wǎng)絡(luò)中一小部分節(jié)點(diǎn)的信息，而且離它越近的節(jié)點(diǎn)，它就知道越多的信息。
任何一個(gè)節(jié)點(diǎn)收到查詢關(guān)鍵字K 的請(qǐng)求時(shí)，首先檢查K 是否落在該節(jié)點(diǎn)標(biāo)識(shí)和它的后繼節(jié)點(diǎn)標(biāo)識(shí)之間，如果是的話，這個(gè)后繼節(jié)點(diǎn)就是存儲(chǔ)目標(biāo)(K, V)對(duì)的節(jié)點(diǎn)。否則，節(jié)點(diǎn)將查找它的指針表，找到表中節(jié)點(diǎn)標(biāo)識(shí)符最大但不超過(guò)K 的第一個(gè)節(jié)點(diǎn)，并將這個(gè)查詢請(qǐng)求轉(zhuǎn)發(fā)給該節(jié)點(diǎn)。通過(guò)重復(fù)這個(gè)過(guò)程，最終可以定位到K 的后繼節(jié)點(diǎn)，即存儲(chǔ)有目標(biāo)(K, V)對(duì)的節(jié)點(diǎn)。
Chord節(jié)點(diǎn)的加入和退出
為了應(yīng)對(duì)系統(tǒng)的變化，每個(gè)節(jié)點(diǎn)都周期性地運(yùn)行探測(cè)協(xié)議來(lái)檢測(cè)新加入節(jié)點(diǎn)或失效節(jié)點(diǎn)，從而更新自己的指針表和指向后繼節(jié)點(diǎn)的指針。新節(jié)點(diǎn)n 加入時(shí)，將通過(guò)系統(tǒng)中現(xiàn)有的節(jié)點(diǎn)來(lái)初始化自己的指針表。這時(shí)，系統(tǒng)中一部分關(guān)鍵字的后繼節(jié)點(diǎn)也變?yōu)樾鹿?jié)點(diǎn)n，因而先前的后繼節(jié)點(diǎn)要將這部分關(guān)鍵字轉(zhuǎn)移到新節(jié)點(diǎn)上。當(dāng)節(jié)點(diǎn)n 失效時(shí)，所有指針表中包括n的節(jié)點(diǎn)都必須把它替換成n 的后繼節(jié)點(diǎn)。為了保證節(jié)點(diǎn)n 的失效不影響系統(tǒng)中正在進(jìn)行的查詢過(guò)程，每個(gè)Chord 節(jié)點(diǎn)都維護(hù)一張包括r 個(gè)最近后繼節(jié)點(diǎn)的后繼列表。
DHT算法之Pastry
Pastry 是自組織的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都被分配一個(gè)128 位的nodeId。nodeId 用于在環(huán)形的節(jié)點(diǎn)空間中（從0 到2^128－1）標(biāo)識(shí)節(jié)點(diǎn)的位置，它是在節(jié)點(diǎn)加入系統(tǒng)時(shí)隨機(jī)分配的，隨機(jī)分配的結(jié)果是使得所有的nodeId 在128 位的節(jié)點(diǎn)號(hào)空間中均勻分布。nodeId 可以通過(guò)計(jì)算節(jié)點(diǎn)公鑰或者IP 地址的哈希函數(shù)值來(lái)獲得。Pastry使用一致性哈希作為哈希算法。哈希所得的鍵值為一維(實(shí)際上使用的是128bit的整數(shù)空間)。Pastry并沒(méi)有規(guī)定具體應(yīng)該采用何種哈希算法。
假設(shè)網(wǎng)絡(luò)包含N 個(gè)節(jié)點(diǎn)，Pastry 可以把一個(gè)給定的關(guān)鍵字路由到nodeId 和該關(guān)鍵字最接近的節(jié)點(diǎn)。即使發(fā)生節(jié)點(diǎn)失效，Pastry 也可以保證關(guān)鍵字送達(dá)目標(biāo)節(jié)點(diǎn)，除非nodeId和關(guān)鍵字臨近的節(jié)點(diǎn)中有半數(shù)同時(shí)失效。每個(gè)節(jié)點(diǎn)把查詢消息轉(zhuǎn)發(fā)給下一個(gè)節(jié)點(diǎn)時(shí)，要保證這個(gè)節(jié)點(diǎn)的nodeId 和關(guān)鍵字的相同前綴至少要比當(dāng)前節(jié)點(diǎn)的nodeId 和關(guān)鍵字的相同前綴長(zhǎng)一個(gè)數(shù)位（即b 個(gè)比特）。如果找不到這樣的鄰居節(jié)點(diǎn)，消息將轉(zhuǎn)發(fā)給前綴長(zhǎng)度相同但是節(jié)點(diǎn)號(hào)數(shù)值更接近關(guān)鍵字的節(jié)點(diǎn)。為此，每個(gè)Pastry 節(jié)點(diǎn)都需要維護(hù)狀態(tài)表：一張路由表，一個(gè)鄰居節(jié)點(diǎn)集和一個(gè)葉子節(jié)點(diǎn)集。在應(yīng)用層能夠及時(shí)準(zhǔn)確地獲得這兩個(gè)集合的節(jié)點(diǎn)信息時(shí)，可以大大加快路由查找的速度，同時(shí)降低因路由引起的網(wǎng)絡(luò)傳輸開(kāi)銷；不過(guò)在動(dòng)態(tài)變化的P2P網(wǎng)絡(luò)中如何理想地做到這一點(diǎn)的確有很大的難度。
Pastry 的路由
Pastry的路由利用了成熟的最大掩碼匹配算法，實(shí)現(xiàn)時(shí)可以利用很多現(xiàn)成的軟件算法和硬件框架，可以獲得很好的效率。
Pastry 的節(jié)點(diǎn)收到一條查詢消息時(shí)，首先檢查該消息的關(guān)鍵字是否落在葉子節(jié)點(diǎn)集范圍內(nèi)。如果是，則直接把消息轉(zhuǎn)發(fā)給對(duì)應(yīng)的節(jié)點(diǎn)，也就是葉子節(jié)點(diǎn)集中nodeId和關(guān)鍵字最接近的節(jié)點(diǎn)。如果關(guān)鍵字沒(méi)有落在葉子節(jié)點(diǎn)集范圍內(nèi)，節(jié)點(diǎn)就會(huì)把消息轉(zhuǎn)發(fā)給路由表中的一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的nodeId 和關(guān)鍵字的相同前綴至少要比當(dāng)前節(jié)點(diǎn)的nodeId 和關(guān)鍵字的相同前綴長(zhǎng)一個(gè)數(shù)位。如果路由表中相應(yīng)的表項(xiàng)為空，或者表項(xiàng)中對(duì)應(yīng)的節(jié)點(diǎn)不可達(dá)，這時(shí)候查詢消息將被轉(zhuǎn)發(fā)給前綴長(zhǎng)度相同但是節(jié)點(diǎn)號(hào)數(shù)值更接近關(guān)鍵字的節(jié)點(diǎn)。
Pastry節(jié)點(diǎn)的加入和退出
Pastry是完全分布式的、可擴(kuò)展的和自組織的，它能夠自動(dòng)應(yīng)對(duì)節(jié)點(diǎn)加入、離開(kāi)和失效。
新節(jié)點(diǎn)加入時(shí)需要初始化自身的狀態(tài)表，并通知其他節(jié)點(diǎn)自己已經(jīng)加入系統(tǒng)。假定新加入節(jié)點(diǎn)的nodeId 為Y，同時(shí)Y 在加入Pastry 之前已經(jīng)知道系統(tǒng)中和自己距離相近的節(jié)點(diǎn)C。新節(jié)點(diǎn)Y 首先請(qǐng)求C 路由一條“加入”消息，消息的關(guān)鍵字就是Y。這條消息最終會(huì)到達(dá)nodeId和Y 最接近的節(jié)點(diǎn)Z。Pastry 一旦節(jié)點(diǎn)檢測(cè)出其葉子節(jié)點(diǎn)集L 中的某個(gè)節(jié)點(diǎn)失效，它就會(huì)請(qǐng)求該集合中nodeId 最大或最小的節(jié)點(diǎn)把其葉子節(jié)點(diǎn)集L’發(fā)送過(guò)來(lái)。當(dāng)前節(jié)點(diǎn)將從L’中選擇一個(gè)L 中沒(méi)有的活動(dòng)節(jié)點(diǎn)來(lái)替代失效節(jié)點(diǎn)。如果節(jié)點(diǎn)檢測(cè)出其路由表中某項(xiàng)對(duì)應(yīng)的節(jié)點(diǎn)失效，它將從該項(xiàng)所在的路由表行中選擇另一個(gè)節(jié)點(diǎn)，要求該節(jié)點(diǎn)把路由表中對(duì)應(yīng)位置的項(xiàng)發(fā)過(guò)來(lái)。
DHT算法之Tapestry
Tapestry 目前使用160 比特的標(biāo)識(shí)符空間，標(biāo)識(shí)符用一個(gè)全局統(tǒng)一的進(jìn)制表示，所有的節(jié)點(diǎn)依據(jù)標(biāo)識(shí)符自組織成一個(gè)覆蓋網(wǎng)絡(luò)。Tapestry 動(dòng)態(tài)地把每個(gè)標(biāo)識(shí)符G 映射到當(dāng)前系統(tǒng)中一個(gè)節(jié)點(diǎn)上，該節(jié)點(diǎn)稱為G 的根節(jié)點(diǎn)。如果某節(jié)點(diǎn)的NodeID＝G，則這個(gè)節(jié)點(diǎn)就是G 的根節(jié)點(diǎn)。為了轉(zhuǎn)發(fā)查詢消息，每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)鄰居映射表，每個(gè)表項(xiàng)包括一個(gè)鄰居節(jié)點(diǎn)的標(biāo)識(shí)符和IP 地址。往GR 路由時(shí)，消息將沿著鄰居指針向節(jié)點(diǎn)標(biāo)識(shí)符在標(biāo)識(shí)符空間中更接近G 的節(jié)點(diǎn)轉(zhuǎn)發(fā)。
Tapestry 中的每個(gè)節(jié)點(diǎn)都保存有鄰居映射表。鄰居映射表可以用于把消息按照目的地址一位一位地向前傳遞，這種方式類似于IP 分組轉(zhuǎn)發(fā)過(guò)程中的最長(zhǎng)前綴匹配。節(jié)點(diǎn)N 的鄰居映射表分為多個(gè)級(jí)別，每個(gè)級(jí)別包含的鄰居節(jié)點(diǎn)的數(shù)量等于標(biāo)識(shí)符表示法的基數(shù)，而每個(gè)級(jí)別中鄰居節(jié)點(diǎn)標(biāo)識(shí)符和本節(jié)點(diǎn)標(biāo)識(shí)符的相同前綴都比前一級(jí)別多一個(gè)數(shù)位。
Tapestry 的路由
Tapestry 采用的基本查找和路由機(jī)制，當(dāng)一條查找消息到達(dá)傳遞過(guò)程中的第n 個(gè)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)和目的節(jié)點(diǎn)的共同前綴長(zhǎng)度至少大于n。為了進(jìn)行轉(zhuǎn)發(fā)，該節(jié)點(diǎn)將查找鄰居映射表的第n+1 級(jí)中和目的標(biāo)識(shí)符下一數(shù)位相匹配的鄰居節(jié)點(diǎn)。轉(zhuǎn)發(fā)過(guò)程將在每個(gè)節(jié)點(diǎn)中依次進(jìn)行直到到達(dá)目的節(jié)點(diǎn)。
Tapestry 中的節(jié)點(diǎn)在共享數(shù)據(jù)時(shí)被稱為服務(wù)器，請(qǐng)求數(shù)據(jù)時(shí)被稱為客戶，轉(zhuǎn)發(fā)消息時(shí)被稱為路由器。也就是說(shuō)每個(gè)節(jié)點(diǎn)可以同時(shí)具有客戶、服務(wù)器和路由器的功能。服務(wù)器S通過(guò)向?qū)ο蟮母?jié)點(diǎn)定期的發(fā)送消息來(lái)報(bào)告S保存有該對(duì)象。在這條發(fā)布路徑上的每個(gè)節(jié)點(diǎn)都保存關(guān)于這個(gè)對(duì)象的位置信息指針，當(dāng)多個(gè)都存有同一對(duì)象拷貝的服務(wù)器分別向根結(jié)點(diǎn)發(fā)布消息時(shí)，路徑上的每個(gè)節(jié)點(diǎn)按各個(gè)服務(wù)器離自己的網(wǎng)絡(luò)時(shí)延遞增的順序保存這些位置指針列表。
Tapestry節(jié)點(diǎn)的加入和退出
Tapestry 的節(jié)點(diǎn)加入算法和Pastry 類似。節(jié)點(diǎn)N 在加入Tapestry 網(wǎng)絡(luò)之前，也需要知道一個(gè)已經(jīng)在網(wǎng)絡(luò)中的節(jié)點(diǎn)G。然后N 通過(guò)G 發(fā)出路由自己的節(jié)點(diǎn)ID 的請(qǐng)求，根據(jù)經(jīng)過(guò)的節(jié)點(diǎn)的對(duì)應(yīng)的鄰居節(jié)點(diǎn)表構(gòu)造自己的鄰居節(jié)點(diǎn)表。構(gòu)造完自己的數(shù)據(jù)結(jié)構(gòu)后，節(jié)點(diǎn)N 將通知網(wǎng)絡(luò)中的其他節(jié)點(diǎn)自己已經(jīng)加入網(wǎng)絡(luò)。通知只針對(duì)在N 的鄰居映射表中的主鄰居節(jié)點(diǎn)和二級(jí)鄰居節(jié)點(diǎn)進(jìn)行。
Tapestry 采用兩種機(jī)制處理節(jié)點(diǎn)的退出。一種情況是節(jié)點(diǎn)從網(wǎng)絡(luò)中自行消失（主要原因是節(jié)點(diǎn)失效），在這種情況下，它的鄰居可以檢測(cè)到它已經(jīng)退出網(wǎng)絡(luò)并可以相應(yīng)的調(diào)整路由表。另一種機(jī)制是節(jié)點(diǎn)在退出系統(tǒng)之前通過(guò)后向指針通知所有把它作為鄰居的節(jié)點(diǎn)，這些節(jié)點(diǎn)會(huì)相應(yīng)調(diào)整路由表并通知對(duì)象服務(wù)器該節(jié)點(diǎn)已經(jīng)退出網(wǎng)絡(luò)。檢測(cè)正常操作過(guò)程中的鏈路和服務(wù)器失效，可以使用TCP 連接超時(shí)機(jī)制。
DHT算法之 CAN
CAN 的設(shè)計(jì)基于虛擬的維笛卡爾坐標(biāo)空間，這個(gè)坐標(biāo)空間完全是邏輯上的，和任何物理坐標(biāo)系統(tǒng)都沒(méi)有關(guān)系。在任何時(shí)候，整個(gè)坐標(biāo)空間動(dòng)態(tài)地分配給系統(tǒng)中的所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)負(fù)責(zé)維護(hù)獨(dú)立的互不相交的一塊區(qū)域。CAN 中的節(jié)點(diǎn)自組織成一個(gè)代表這個(gè)虛擬坐標(biāo)空間的覆蓋網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)要了解并維護(hù)相鄰區(qū)域中節(jié)點(diǎn)的IP 地址,用這些鄰居信息構(gòu)成自身的坐標(biāo)路由表?；诼酚杀?，CAN 可以在坐標(biāo)空間中任意兩點(diǎn)間進(jìn)行尋址。
虛擬坐標(biāo)空間當(dāng)保存（K1, V1）時(shí)，使用統(tǒng)一的哈希函數(shù)把關(guān)鍵字K1 映射成坐標(biāo)空間中的點(diǎn)P。那么這個(gè)值將被保存在該點(diǎn)所在區(qū)域的節(jié)點(diǎn)中。當(dāng)需要查詢關(guān)鍵字K1 對(duì)應(yīng)的值時(shí)，任何節(jié)點(diǎn)都可以使用同樣的哈希函數(shù)找到K1 對(duì)應(yīng)的點(diǎn)P，然后從該點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)取出相應(yīng)的值V1。如果此節(jié)點(diǎn)不是發(fā)起查詢請(qǐng)求的節(jié)點(diǎn)，CAN 將負(fù)責(zé)將此查詢請(qǐng)求轉(zhuǎn)發(fā)到P 所在區(qū)域的節(jié)點(diǎn)上。
CAN 的路由
CAN 中的路由很簡(jiǎn)單，沿著坐標(biāo)空間中從發(fā)起請(qǐng)求的點(diǎn)到目的點(diǎn)之間的一條路徑轉(zhuǎn)發(fā)即可。為此，每個(gè)CAN 節(jié)點(diǎn)都要保存一張坐標(biāo)路由表，其中包括它的鄰居節(jié)點(diǎn)的IP 地址和其維護(hù)的虛擬坐標(biāo)區(qū)域。兩個(gè)節(jié)點(diǎn)互為鄰居是指：在d維坐標(biāo)空間中，兩個(gè)節(jié)點(diǎn)維護(hù)的區(qū)域在d-1 維的坐標(biāo)上有重疊而在剩下的一維坐標(biāo)上相互鄰接。每條CAN 消息都包括目的點(diǎn)坐標(biāo)。進(jìn)行路由的時(shí)候，節(jié)點(diǎn)只要朝著目標(biāo)節(jié)點(diǎn)的方向把消息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)即可。
如果一個(gè)d 維空間劃分成n 個(gè)相等的區(qū)域，每個(gè)節(jié)點(diǎn)只需要維護(hù)2d 個(gè)鄰居節(jié)點(diǎn)的信息。這個(gè)結(jié)果表明CAN 的可擴(kuò)展性很好，節(jié)點(diǎn)數(shù)增加時(shí)每個(gè)節(jié)點(diǎn)維護(hù)的狀態(tài)信息不變，而路由長(zhǎng)度只是以n/d的數(shù)量級(jí)增長(zhǎng)。坐標(biāo)空間中兩點(diǎn)之間可以有許多條不同的路徑，所以單個(gè)節(jié)點(diǎn)的失效對(duì)CAN 基本上沒(méi)有太大的影響。遇到失效節(jié)點(diǎn)時(shí)，CAN 會(huì)自動(dòng)沿著其他的路徑進(jìn)行路由。
CAN的節(jié)點(diǎn)加入和退出
因?yàn)檎麄€(gè)CAN 空間要分配給系統(tǒng)中現(xiàn)有的全部節(jié)點(diǎn)，當(dāng)一個(gè)新的節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)必須得到自己的一塊坐標(biāo)空間。CAN 通過(guò)分割現(xiàn)有的節(jié)點(diǎn)區(qū)域?qū)崿F(xiàn)這一過(guò)程。它把某個(gè)現(xiàn)有節(jié)點(diǎn)的區(qū)域分裂成同樣大小的兩塊，自己保留其中的一塊而另一塊分給新加入的節(jié)點(diǎn)。
當(dāng)節(jié)點(diǎn)離開(kāi)CAN 時(shí)，必須保證它的區(qū)域被系統(tǒng)中剩余的節(jié)點(diǎn)接管，也即分配給其他仍然在系統(tǒng)中的節(jié)點(diǎn)。一般是由某個(gè)鄰居節(jié)點(diǎn)來(lái)接管這個(gè)區(qū)域和所有的索引數(shù)據(jù)（K，V）對(duì)。如果某個(gè)鄰居節(jié)點(diǎn)負(fù)責(zé)的區(qū)域可以和離開(kāi)節(jié)點(diǎn)負(fù)責(zé)的區(qū)域合并形成一個(gè)大的區(qū)域，那么將由這個(gè)鄰居節(jié)點(diǎn)執(zhí)行合并操作。否則，該區(qū)域?qū)⒔唤o其鄰居節(jié)點(diǎn)中區(qū)域最小的節(jié)點(diǎn)負(fù)責(zé)。也就是說(shuō)，這個(gè)節(jié)點(diǎn)將臨時(shí)負(fù)責(zé)兩個(gè)區(qū)域。
有些研究人員己經(jīng)認(rèn)識(shí)到基于結(jié)構(gòu)化分布式哈希表的路由機(jī)制也有無(wú)法解決的問(wèn)題。首先，經(jīng)過(guò)哈希之后，結(jié)點(diǎn)的位置信息被破壞了，來(lái)自同一個(gè)子網(wǎng)的站點(diǎn)很可能結(jié)點(diǎn)號(hào)相距甚遠(yuǎn)，這不利于查詢性能的優(yōu)化。其次，基于哈希表的系統(tǒng)不能利用應(yīng)用本身的信息，許多應(yīng)用(比如文件系統(tǒng))的數(shù)據(jù)本身是按照層次結(jié)構(gòu)組織的，而使用哈希函數(shù)后，這些層次信息就丟失了。
小結(jié)
DHT 有很多的應(yīng)用場(chǎng)景，P2P網(wǎng)絡(luò)只是其中的典型應(yīng)用之一。本文初步梳理了DHT的主流算法，這些算法的核心在于鍵值空間的設(shè)計(jì)。Kademlia 采用的是二叉樹(shù)，Chord和astry 采用的是環(huán)狀空間，Tapestry采用的是線性空間，而CAN 采用的則是笛卡爾坐標(biāo)空間，不同數(shù)據(jù)結(jié)構(gòu)的鍵值空間導(dǎo)致了不同的路由效率，以及物理網(wǎng)絡(luò)距離的不同影響。基于不同的DHT算法，P2P網(wǎng)絡(luò)的負(fù)載均衡會(huì)會(huì)同樣導(dǎo)致路由延遲不同。P2P網(wǎng)絡(luò)的動(dòng)態(tài)性造成其穩(wěn)定性不佳，像IPFS/Filecoin 則通過(guò)激勵(lì)機(jī)制來(lái)試圖保證網(wǎng)絡(luò)的穩(wěn)定性。
有沒(méi)有更好的鍵值空間設(shè)計(jì)方式呢？拭目以待。
【參考資料與關(guān)聯(lián)閱讀】
https://link.springer.com/chapter/10.1007/3-540-45748-85 https://dl.acm.org/doi/abs/10.1145/964723.383071 https://www.springer.com/us/book/9783540291923 http://www.bittorrent.org/beps/bep0005.html https://blog.csdn.net/mergerly/article/details/7989281 https://blog.csdn.net/hll174/article/details/45823923 http://www.eetchina.com/ART8800409196675277ee5cfd08.HTM https://en.wikipedia.org/wiki/Pastry(DHT) https://en.wikipedia.org/wiki/Content_addressable_network https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html 穩(wěn)定幣的一知半解 NFT 的一知半解 服務(wù)可用性的一知半解 人工智能倫理學(xué)的一知半解 對(duì)AI產(chǎn)品經(jīng)理的一知半解 ES的一知半解 移動(dòng)產(chǎn)品的指標(biāo)初探 物聯(lián)網(wǎng)要點(diǎn)深入淺出 難以捉摸？機(jī)器學(xué)習(xí)模型的可解釋性初探 沒(méi)有被了解的API？一個(gè)老碼農(nóng)眼中的API世界