DHT 算法：
在不需要服務(wù)器的情況下，每個(gè)客戶端負(fù)責(zé)一個(gè)小范圍的路由，并負(fù)責(zé)存儲(chǔ)一小部分?jǐn)?shù)據(jù)，從而實(shí)現(xiàn)整個(gè)DHT網(wǎng)絡(luò)的尋址和存儲(chǔ)。（百度百科）
結(jié)構(gòu)式拓?fù)洌?/p>
1.無中央服務(wù)器，各結(jié)點(diǎn)的功能和地位都是相同。
2.結(jié)點(diǎn)間的邏輯拓?fù)潢P(guān)系是按照某種決定性的算法嚴(yán)格控制的。資源的放置按照該算法決定性地放置在特定的結(jié)點(diǎn)上。資源定位信息與P2P拓?fù)涫蔷o耦合的。資源的查詢也是按照決定性的算法進(jìn)行。
3.適于對可用性要求高、需服務(wù)質(zhì)量保證的系統(tǒng)，如分布式存儲(chǔ)系統(tǒng)Oceanstore，CFS，PAST。典型例子：分布哈希表（Distributed Hash Table,DHT）方法。
分布哈希表DHT的特點(diǎn)：
數(shù)據(jù)(key)由大量分布自組織的結(jié)點(diǎn)來協(xié)作存儲(chǔ)，兩個(gè)基本操作： Insert(key, value)，Lookup (key)，功能上非常像一個(gè)hash表：Hash（key）－>node。引入哈希函數(shù)以將要搜索的對象映射到唯一標(biāo)識(shí)符：例如，hash（“Hey Jude”）→8045
在網(wǎng)絡(luò)中的所有節(jié)點(diǎn)之間分配散列函數(shù)的范圍，每個(gè)節(jié)點(diǎn)都包含標(biāo)識(shí)符空間的一部分，每個(gè)節(jié)點(diǎn)必須“了解”每個(gè)對象的至少一個(gè)副本，該對象在其范圍內(nèi)（當(dāng)存在時(shí)）。
分布哈希表(DHT)方法：
1.以分布式存儲(chǔ)為背景解釋DHT方法：海量數(shù)據(jù)文件由大量peer結(jié)點(diǎn)來協(xié)作存儲(chǔ)，peer結(jié)點(diǎn)通過DHT方法來組織。
2.每個(gè)Peer都有唯一邏輯地址PeerID：結(jié)點(diǎn)間根據(jù)PeerID，按照DHT拓?fù)錁?gòu)造算法形成P2P網(wǎng)絡(luò)拓?fù)洌幻總€(gè)結(jié)點(diǎn)上都有一個(gè)“路由表”，保存了一些鄰居結(jié)點(diǎn)的信息。
3.每個(gè)Peer負(fù)責(zé)存儲(chǔ)一部分文件：各數(shù)據(jù)文件（根據(jù)其關(guān)鍵字key）有唯一的邏輯地址GUID；根據(jù)資源屬性值ID，按照一定的映射關(guān)系將其放置到特定的結(jié)點(diǎn)上；Peer加入或退出時(shí)，相關(guān)Peer重新劃分所負(fù)責(zé)的文件
4.文件的發(fā)布與定位：文件發(fā)布和查找過程都類似于IP路由過程；根據(jù)peer結(jié)點(diǎn)的“路由表”轉(zhuǎn)發(fā)數(shù)據(jù)的定位消息。
DHT的數(shù)據(jù)發(fā)布：兩種選擇
1.節(jié)點(diǎn)可以緩存其范圍內(nèi)哈希值的每個(gè)（現(xiàn)有）對象
2.基于指針：(間接級別)節(jié)點(diǎn)緩存指向?qū)ο笪恢玫闹羔槨?/p>
DHT 數(shù)據(jù)查詢/路由：
1.對于每個(gè)對象，其范圍覆蓋該對象的節(jié)點(diǎn)必須通過“短”路徑到達(dá)。可以通過查詢器節(jié)點(diǎn)（假設(shè)可以任意選擇）?？梢酝ㄟ^由具有對象副本的節(jié)點(diǎn)（當(dāng)使用基于指針的方法時(shí)）。
2.不同的方法（CAN，Chord，Pastry，Tapestry）僅在路由方法上有根本的不同：任何“好”的隨機(jī)散列函數(shù)就足夠了。
DHT overlay的基本功能：構(gòu)建拓?fù)洹⑼負(fù)渚S護(hù)：節(jié)點(diǎn)動(dòng)態(tài)加入退出、資源查詢：分布式查詢
DHT overlay的評價(jià)指標(biāo)：節(jié)點(diǎn)度數(shù)，路由路徑/網(wǎng)絡(luò)直徑，負(fù)載均衡，穩(wěn)定性….
DHT 方法的挑戰(zhàn)：
1.每個(gè)節(jié)點(diǎn)的鄰居應(yīng)該隨覆蓋參與的增長而擴(kuò)展，例如，時(shí)間復(fù)雜度不應(yīng)該是O(N)
2.DHT機(jī)制應(yīng)該是完全分布式的（沒有集中點(diǎn)可以阻塞吞吐量，或者可以作為單點(diǎn)故障）
3.DHT機(jī)制應(yīng)該優(yōu)雅地處理加入/離開疊加層的節(jié)點(diǎn)。a.需要在現(xiàn)有節(jié)點(diǎn)上重新劃分范圍空間b.需要重新組織鄰居集c.需要引導(dǎo)機(jī)制將新節(jié)點(diǎn)連接到現(xiàn)有的DHT基礎(chǔ)架構(gòu).
從下列角度(包括上面說的挑戰(zhàn))考慮為什么DHT算法實(shí)現(xiàn)起來很困難：DHT采取權(quán)力下放機(jī)制：沒有中央權(quán)威服務(wù)器?？蓴U(kuò)展：低網(wǎng)絡(luò)流量開銷。高效：快速查找項(xiàng)目（延遲）。動(dòng)態(tài)：節(jié)點(diǎn)發(fā)生故障，新節(jié)點(diǎn)加入。通用：靈活命名
設(shè)計(jì)DHT算法要考慮的問題：
1.高性能DHT Overlay拓?fù)洌和負(fù)錁?gòu)建、拓?fù)渚S護(hù)；結(jié)點(diǎn)度數(shù)與P2P網(wǎng)絡(luò)直徑的折衷：給定結(jié)點(diǎn)度數(shù)，如何最小化查詢開銷。
2.DHT邏輯拓?fù)渑c物理IP網(wǎng)絡(luò)拓?fù)涞钠ヅ?，P2P overlay網(wǎng)絡(luò)中相鄰兩點(diǎn)，在物理網(wǎng)絡(luò)中可能相距甚遠(yuǎn)。
3.DHT網(wǎng)絡(luò)的穩(wěn)定性負(fù)載平衡，各Peer間存儲(chǔ)負(fù)載、鏈路負(fù)載的均衡。
3.豐富的搜索能力等，DHT方法通常只支持基于關(guān)鍵字的精確匹配，如何支持模糊匹配、區(qū)間匹配等。
————————————————
版權(quán)聲明：本文為CSDN博主「vieo」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_41803874/article/details/86154089
