DHT全稱叫分布式哈希表(Distributed Hash Table)，是一種分布式存儲表，是分布式計算系統中的一類，用來將一個關鍵值（key）的集合分散到所有在分布式系統中的節點，并且可以有效地將消息轉送到唯一一個擁有查詢者提供的關鍵值的節點（Peers）。這里的節點類似散列表中的存儲位置。分布式散列表通常是為了擁有極大節點數量的系統，而且在系統的節點常常會加入或離開（例如網絡斷線）而設計的。在一個結構性的覆蓋網絡（overlay network）中，參加的節點需要與系統中一小部分的節點溝通，這也需要使用分布式散列表。分布式散列表可以用以創建更復雜的服務，例如分布式文件系統、點對點技術文件分享系統、合作的網頁緩存、多播、任播、域名系統以及即時通信等。 研究分布式散列表的主要動機是為了開發點對點系統。這些系統使用不同的方法來解決如何**找到擁有某資料的節點**的問題。任一個節點只需要與系統中的部分節點溝通。一般來說，若系統有n個節點，那么只有log n個節點是必須的  Kademlia算法是一種分布式存儲及路由的算法，IpfsDHT是Kademlia算法的一個實現。 我們不僅僅是創建一個新的DHT，而且要求每一個端維護它自己的本地DHT副本，這樣以來，DHT的引導節點可以關閉，不會影響后續的對等端發現。 ``` kademliaDHT, err := dht.New(ctx, host) ``` 其中上下文ctx來自主協程（上下文context是golang用于不同協程之間傳遞信息的機制，是golang的chan的一種實現）： ``` ctx, cancel := context.WithCancel(context.Background()) ``` 將主協程上下文作為參數傳入，構建kademliaDHT對象。 dht包是p2plib庫中的一個package，包含了ipfs的DHT的實現細節。 通過New函數（不是方法），構建一個kademliaDHT對象。 New 使用指定的主機和選項創建一個新的 DHT。 請注意，連接到 DHT 對等點并不一定意味著它也在 DHT 路由表中。 如果路由表有超過 "minRTRefreshThreshold" 的對等點，我們僅在以下情況下將對等點視為路由表候選者： 路由表成功地從它那里得到一個查詢響應，或者它向路由表發送了一個查詢。 kademliaDHT對象有個ID，其值被賦值為host的ID。（peer.ID是在節點主機創建過程中的用節點的公鑰構建的，這是一個Mutihash值）。 ## **Kademlia** Kademlia是一種通過分布式哈希表實現的協議算法，它是由Petar Maymounkov與David Mazières為非集中式P2P計算機網絡而設計的。 Kademlia基于兩個節點之間的距離計算，該距離是兩個網絡節點ID號的異或（ XOR distance ），計算的結果最終作為整型數值返回。關鍵字和節點ID有同樣的格式和長度，因此，可以使用同樣的方法計算關鍵字和節點ID之間的距離。節點ID一般是一個大的隨機數（或字符串），選擇該數值的時候所追求的一個目標就是它的唯一性（希望在整個網絡中該節點ID是唯一的）。異或距離跟實際上的地理位置沒有任何關系，只與ID相關。因此很可能來自德國和澳大利亞的節點由于選擇了相似的隨機ID而成為鄰居。選擇異或是因為通過它計算的距離享有幾何距離公式的一些特征，尤其體現在以下幾點：節點和它本身之間的異或距離是0；異或距離是對稱的：即從A到B的異或距離與從B到A的異或距離是等同的；異或距離符合三角不等式：三個頂點A B C，AC異或距離小于或等于AB異或距離和BC異或距離之和。由于以上的這些屬性，在實際的節點距離的度量過程中計算量將大大降低。Kademlia搜索的每一次迭代將距目標至少更近1 bit。一個基本的具有2的n次方個節點的Kademlia網絡在最壞的情況下只需花n步就可找到被搜索的節點或值。 **Kademlia**路由表由多個列表組成，每個列表對應節點ID的一位（例如：假如節點ID共有128位，則節點的路由表將包含128個列表），包含多個條目，條目中包含定位其他節點所必要的一些數據。列表條目中的這些數據通常是由其他節點的IP地址，端口和節點ID組成。每個列表對應于與節點相距特定范圍距離的一些節點，節點的第n個列表中所找到的節點的第n位與該節點的第n位肯定不同，而前n-1位相同，這就意味著很容易使用網絡中遠離該節點的一半節點來填充第一個列表（第一位不同的節點最多有一半），而用網絡中四分之一的節點來填充第二個列表（比第一個列表中的那些節點離該節點更近一位），依次類推。如果ID有128個二進制位，則網絡中的每個節點按照不同的異或距離把其他所有的節點分成了128類，ID的每一位對應于其中的一類。隨著網絡中的節點被某節點發現，它們被逐步加入到該節點的相應的列表中，這個過程中包括向節點列表中存信息和從節點列表中取信息的操作，甚至還包括當時協助其他節點尋找相應鍵對應值的操作。這個過程中發現的所有節點都將被加入到節點的列表之中，因此節點對整個網絡的感知是動態的，這使得網絡一直保持著頻繁地更新，增強了抵御錯誤和攻擊的能力。 在**Kademlia**相關的論文中，列表也稱為K桶，其中K是一個系統變量，如20，每一個K桶是一個最多包含K個條目的列表，也就是說，網絡中所有節點的一個列表（對應于某一位，與該節點相距一個特定的距離）最多包含20個節點。隨著對應的bit位變低（即對應的異或距離越來越短），K桶包含的可能節點數迅速下降（這是由于K桶對應的異或距離越近，節點數越少），因此，對應于更低bit位的K桶顯然包含網絡中所有相關部分的節點。由于網絡中節點的實際數量遠遠小于可能ID號的數量，所以對應那些短距離的某些K桶可能一直是空的（如果異或距離只有1，可能的數量就最大只能為1，這個異或距離為1的節點如果沒有發現，則對應于異或距離為1的K桶則是空的）。 ## IpfsDHT 我們看看IpfsDHT的結構： ``` // IpfsDHT is an implementation of Kademlia with S/Kademlia modifications. // It is used to implement the base Routing module. type IpfsDHT struct { host host.Host // 節點主機，提供網絡服務 self peer.ID //本地peer（自己，即host的peer ID） selfKey kb.ID //根據peer ID計算的hash peerstore peerstore.Peerstore // Peer 注冊表 datastore ds.Datastore // 本地數據，host的地址和密鑰存儲 庫 routingTable *kb.RoutingTable // 不同距離節點的路由表 // provider Store 存儲和管理此 Dht peer的提供者記錄。 providerStore providers.ProviderStore // 管理路由表刷新 rtRefreshManager *rtrefresh.RtRefreshManager birth time.Time // 本peer啟動的時間 Validator record.Validator //驗證器，用于驗證節點是否合法 ctx context.Context //創建它的協程的上下文 proc goprocess.Process //進程管理，詳細見后面分析 protoMessenger *pb.ProtocolMessenger//協議消息發送者，用于將DHT消息傳給peers并處理來自它們的響應，詳細見后面分析 msgSender pb.MessageSender //消息發送接口實現者 plk sync.Mutex 填充或修改DHT表互斥鎖，將當前已連接的節點加入DHT表，或者斷開連接更新DHT表，均為互斥操作 stripedPutLocks [256]sync.Mutex //用于將一個值存儲到本地peer的庫中 // 我們用它查詢DHT protocols. 我們只把那些講這些協議的peers加入到路由表中 // 缺省情況下，protocols=[]protocol.ID{v1proto}，其中v1proto="/ipfs//kad/1.0.0" protocols []protocol.ID protocolsStrs []string //我們可以響應的DHT protocols. //一般情況下，serverProtocols=protocols serverProtocols []protocol.ID //DHT內部操作的模式，詳細見后面的分析 auto ModeOpt mode mode //與auto值相同 modeLk sync.Mutex //mode讀取或設置互斥鎖 bucketSize int //K桶大小，這是Kademlia列表的一種稱呼，默認為20 alpha int // 每個path的并發參數 beta int // 最接近目標的peers數量，這些peers必須響應一個query path才能終止 queryPeerFilter QueryFilterFunc //查詢peers的過濾器 routingTablePeerFilter RouteTableFilterFunc //節點路由協議過濾器，用于檢查一個節點是否符合指定的路由表協議 rtPeerDiversityFilter peerdiversity.PeerIPGroupFilter //節點分組過濾器，一般而言，除非節點在白名單中，否則只有一個群組內的節點才能能通訊 autoRefresh bool //是否自動刷新，一般默認為自動刷新DHT路由表 //如果所有其他修復路由表的嘗試都失敗（或者，例如，這是該節點第一次連接到網絡），則返回一組引導peers的函數。 bootstrapPeers func() []peer.AddrInfo maxRecordAge time.Duration //節點key在本地庫中保存最長時間，超過該時間將刪除，默認36小時 //允許禁用 dht 子系統。 這些只應該設置在“分叉”的 DHT 上（例如，具有自定義協議和/或專用網絡的 DHT）。 enableProviders, enableValues bool disableFixLowPeers bool// 是否修正最低節點數量。如果節點數量低于臨界值（默認值為10個），將嘗試獲取更多的節點加入到DHT表中 fixLowPeersChan chan struct{} addPeerToRTChan chan addPeerRTReq//添加peer到RT（路由表） refreshFinishedCh chan struct{} //刷新結束通知 rtFreezeTimeout time.Duration //凍結時間，默認1分鐘 // 測試配置 testAddressUpdateProcessing bool } ``` ### 1 、proc goprocess.Process proc goprocess.Process：進程，仿照 UNIX 進程組思想，并且重 由 sync.WaitGroup 和 go.net/context.Context 通知。 進程（Process）是goprocess中的基本工作單元。 它定義了一個具有生命周期的計算： - 運行（在調用 Close 之前）， - 關閉（在調用 Close 至少一次之后）， - 關閉（在 Close 返回之后，并且所有teardown都完成了）。 goprocess 引入了一種在 go 中管理進程生命周期的方法。 它很像 go.net/context（它實際上使用了一個 Context），但它更像是一個 Context-WaitGroup 混合體。 goprocess 是關于能夠啟動和停止工作單元，這些工作單元可能會收到來自許多客戶端的關閉信號。 把它想象成一個 UNIX 進程樹，但里面是 go。 goprocess 力求對您的對象產生最小的影響，因此您可以將它與嵌入或組合一起使用。 goprocess 的核心是 Process 接口。 見開源項目：https://github.com/jbenet/goprocess ### 2、protoMessenger *pb.ProtocolMessenger ``` type ProtocolMessenger struct { ? ? m MessageSender } ``` ProtocolMessenger 可用于向peers發送 DHT 消息并處理它們的響應。 這將有線協議格式（wire protocol）與 DHT 協議實現、有線協議格式與 routing.Routing 接口的實現進行分離。這里是指發送DHT協議格式的消息。 注意：ProtocolMessenger 的 MessageSender 仍然需要處理一些有線協議（wire protocol）細節，例如使用 varint-delineated protobufs。 wire protocol： * 是一種傳輸數據的機制； * 不要從字面上將其理解為物理層上的協議； * 因為代碼層面的數據（鏈表、隊列、二叉樹）都是結構化的，但網絡層看到的都是二進制流，所以把結構化的數據序列化為二進制流發送出去，并且對方也能以同樣的格式反序列化出來，這就是wire protocol。 英文原文解釋： In a network, a wire protocol is the mechanism for transmitting data from point a to point b. The term is a bit confusing, because it sounds like layer 1 of the network, which physically places the bits "onto the wire." In some cases, it may refer to layer 1; however, it generally refers to higher layers, including Ethernet and ATM (layer 2) and even higher layer distributed object protocols such as SOAP, CORBA or RMI. See OSI model, communications protocol, data link protocol and distributed objects. ### 3、pb.MessageSender MessageSender為接口對象， 處理發送有線協議消息到指定的peer： ``` type MessageSender interface { // SendRequest sends a peer a message and waits for its response SendRequest(ctx context.Context, p peer.ID, pmes *Message) (*Message, error) // SendMessage sends a peer a message without waiting on a response SendMessage(ctx context.Context, p peer.ID, pmes *Message) error } ``` 其中，SendRequest為同步函數，SendMessage為異步函數。 從實際構建IpfsDHT對象來看，我們先創建MessageSender，然后將其作為參數創建ProtocolMessenger。 ### 4、auto ModeOpt const ( // ModeAuto utilizes EvtLocalReachabilityChanged events sent over the event bus to dynamically switch the DHT // between Client and Server modes based on network conditions ModeAuto ModeOpt = iota // ModeClient operates the DHT as a client only, it cannot respond to incoming queries ModeClient // ModeServer operates the DHT as a server, it can both send and respond to queries ModeServer // ModeAutoServer operates in the same way as ModeAuto, but acts as a server when reachability is unknown ModeAutoServer ) 在默認情況下，其值為0，但實際上一個DHT要么是ModeClient，要么是ModeServer，一般不設為ModeAuto。 在我們的區塊鏈中，我們使用dht.New(ctx, host)來構建節點，這種情況下使用默認的config，mode會被設為ModeClient，意味著我們不響應來自其它節點的DHT請求，只發送DHT消息給網絡。