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