Kademlia

Kademlia是一種通過分散式雜鬥表實現的協定演算法，伊是由 Petar Maymounkov 佮 David Mazières 為非集中式 P 二 P 電腦網路咧設計的。Kademlia規定了網路的結構，嘛規定通過節點查詢進行資訊交換的方式。參與通訊的所有節點形成一張虛擬網（抑是叫做崁網）。 遮的節點通過一組數字（抑是號做節點 ID）來進行身份標識。節點 ID 毋但會當用來做身份標識，閣會當用來進行值定位（值通常是檔案的雜鬥抑是關鍵詞）。 其實乎，節點 ID 佮檔案雜鬥直接對應，伊所表示的彼个儉點儲存佗位會當取得檔案佮資源的相關資訊。當阮佇網路內底咧搜揣某一寡值（即通常搜揣儲存檔案雜鬥抑是關鍵詞的節點）的時陣，Kademlia演算法需要知影佮遮的值相關的鍵，然後分步佇咧網路內底開始搜揣。每一步攏會揣著一寡節點，遮的鋩角的 ID 佮鍵閣較接近，若有節點直接倒轉來揣會著抑是較無法度揣著佮鍵更加接近的節點 ID 的時陣搜揣會停止。這種搜揣值得的方法是誠懸效：佮其他的分散式雜鬥表的實現類似，佇一个包括 n 個節點的系統的值的搜揣中，Kademlia干焦存取 O ( log ( n ) ) 個節點。非集中式網路結構閣有較大的優勢，彼就是伊會當顯示增強到阻斷服務攻擊的能力。即使網路中的規批節點遭受泛洪攻擊，嘛袂對網路的可用性造成誠大的影響，通過踅過遮的空（去予人攻擊的節點）來重新編織一張網路，網路的可用性就會使得著恢復。

系統鋩角

第一代 P 二 P 檔案分享網路，像 Napster，依賴中央資料庫來協調網路當中的查詢，第二代 P 二 P 網路，像 Gnutella，使用氾濫式查詢（query flooding）來查詢檔案，伊會揣著網路內面的所有節點，第三代 p 二 p 網路使用分散式雜鬥表來查詢網路中的檔案，分散式雜鬥表示佇咧規个網路內底儲存資源的位置，遮的協定追求的主要目標就是快速定位向望的節點。Kademlia因為兩个節點之間的距離計算，距離是兩个網路節點 ID 號的互斥抑是講（XOR distance）， 算的結果最終做規型數值倒轉來。關鍵字佮節點 ID 有仝款的格式佮長度，所以，會當使用仝款的方法計算關鍵字佮節點 ID 之間的距離。節點 ID 一般是一个大的亂數，選擇該數的時陣所追求的一个目標就是伊的唯一性（希望佇規个網路內底該節點 ID 是唯一的）。 互斥抑是距離佮實際上的地理位置無任何關係，干焦與 ID 相關。所致真有可能來自德國佮澳大利亞的節點因為選擇相𫝛的隨機 ID 變做是厝邊。選擇互斥抑是講因為通過伊計算的距離享有幾何距離公式的一寡特徵，尤其體這馬以下幾點：節點佮伊本身之間的相斥抑是距離是零；互斥抑是講距離是對稱的：即從 A 到 B 的互斥抑是講距離佮對 B 到 A 的互斥抑是講距離是等同的；互斥抑是講距離符合三角不等式：三个頂點 A B C，AC 互斥抑是講距離較細抑是等於 AB 互斥抑是講距離佮 BC 互斥抑是講距離之和。因為以上的遮的屬性，佇咧實際的節點距離的度量的過程當中算量將大大降低。Kademlia迵天的每一擺迵天代將距目標至少閣較近一 bit。一个基本的具有二的 n 遍方個節點的Kademlia網路佇上歹的狀況之下干焦需要開 n 伊就會當揣著予人搜揣的節點抑是值。

路由表

為著說明簡單，本部份是單个 bit 構建路由表，如需關於實際路由表的較濟資訊，請看「查詢加速」部份。

Kademlia路由多个列表的組成，逐家列表對應的彼个節點 ID 的一位（比如講：假使節點 ID 把它有一百二十八位元，則節點的路由表會包含一百二十八个列表）， 包含幾若个條目，條目中包括定位其他的節點所必要的一寡資料。列表條目中的遮的資料通常是由其他節點的 IP 位址，埠佮節點 ID 組成。逐家列表對應該佮節點相距離特定範圍距離的一寡節點，節點的第 n 列表中所揣著的節點的第 n 位置佮該節點的第 n 位肯定無仝，抑若頭前 n 𫞼一位相仝，這就意味簡單使用網路中遠離該點的一半節點來填充第一个列表（第一位無仝款的節點上濟有一半）， 用網路中四分之一的節點來填充第二个列表（比第一个列表中的遐的節點離該節點閣較近一位）， 照這个次類推。若是 ID 有一百二十八个位元，則網路中的每一个節點按照無仝的互相爭抑是講距離共其他所有的節點分做一百二十八類，ID 每一位對應其中的一類。隨著網路中的節點去予某節點發現，𪜶予逐步加入到該節點的相應的列表內底，這个過程中包括向節點列表中存資訊佮對節點列表中取資訊的操作，甚至閣包括彼當陣協助其他所節點走揣相應鍵對應值的操作。這个過程內底發現的所有的點節點攏將予加入到節點列表內底，因此節點對規个網路的感知是動態的，這予網路一直保持頻繁地更新，增強矣抵禦錯誤佮攻擊的能力。

佇咧Kademlia相關的論文中，列表嘛講號做 K 桶，其中 K 是一个系統變數，如二十，彼每一个 K 桶是一個上濟包含 K 條目的列表，也就是講，網路中所有節點的一个列表（對應某一个，佮該節點距離一个足特定的距離）上濟包含二十个節點。隨著對應的 bit 位變低（即對應的互斥抑是講距離愈來愈短）， K 桶包含講的可能節點數窸倏降低（這是因為 K 桶對應的互斥抑是講距離愈近，節點數愈少）， 所以，對應於閣較低 bit 位的 K 桶顯然包含網路中所有相關部份的節點。因為網路中節點的實際數量遠遠細可能 ID 號的數量，所以對應遐的短距離的某一寡 K 桶可能一直是空的（若講互斥抑是講距離干焦一，可能的數量就上大干焦會當做一，這个互斥抑是講距離為一的點若無發現講，著愛對應互相斥抑是距離做一的 K 桶則是空的）。

予咱看正爿的彼个簡單網路，該網路上大會當有二 ^ 三，即八个關鍵字佮節點，目前共有七个節點加入，逐个節點用一个細箍仔表示（佇樹仔的下底）。 阮考慮彼个用烏箍標的節點六，伊共有三个 K 桶，節點空，一和二（二進位表示做零，一佮十）嘿頭一个 K 桶的候選節點，節點三目前（二進位表示為十一）猶未加入網路，節點四佮節點五（二進位表示分別為一百佮一百空一）是第二个 K 桶的候選節點，干焦有儉點七（二進位表示做一百十一）是第三个 K 桶的候選節點。圖當中，三个 K 桶仔攏用殕色箍仔表示，假使講 K 桶的大細（即 K 值）是二，按呢頭一个 K 桶只會當包含三个節點內底的兩个。眾所周知，彼長時間線頂連接的節點未來長時間線頂的可能性閣較大，因為這種靜態統計分布的規律，Kademlia選擇共遐的長時間線頂的節點行入去 K 桶，一方法增加未來某一時刻有效節點的數量，同時嘛提供著閣較穩定的網路。做某一个 K 桶已經滿，閣發現矣相應該桶的新節點的時陣，遐爾，就代先檢查 K 桶中上蓋早存取的節點，若準該節點猶閣活咧，遐爾新節點就予人安排去一个附屬列表中（成做一个替代緊號）. 干焦當 K 桶中的某一个節點停止回應的時，替代 cache 才有咧使用。嘛會使講，新發現的節點干焦佇咧老的節點消失了後才予人使用。

協定訊息

Kademlia鬥陣四種訊息。

• PING 訊息—用來試節點敢是猶原線頂。
• STORE 訊息—佇咧某一个節點內底儲存一个鍵值著。
• FIND \ _ NODE 訊息—訊息請求的接收者共轉去家己桶內底離請求鍵值上近的 K 個節點。
• FIND \ _ VALUE 訊息，佮 FIND \ _ NODE 仝款，毋過當請求的接收者存有請求者所請求的鍵的時陣，伊共回回應鍵的值。彼每一个 RPC 訊息內底攏包括一个發起者加入的隨機值，這點確保回應訊息佇咧收著的時陣會當佮頭前傳送的請求訊息匹配。

定位節點

節點查詢會當非同步來進行，嘛會當同齊來進行，同時查詢的數量由 α 表示，一般是三。佇咧節點內底查詢的時陣，伊先得著伊 K 桶中離所查詢的鍵值上近的 K 個節點，然後向這个 K 個節點發起 FIND \ _ NODE 訊息請求，訊息接收者收著遮的請訊息了後將佇𪜶的 K 桶中進行查詢，若是𪜶知影離彼个予人查鍵閣較近的節點，𪜶就倒轉來遮的節點（上濟 K 個）。 訊息的請求者佇收著回應了後將使用伊所收著的回應結果來更新伊的結果列表，這結果列表總是保持 K 一个回應 FIND \ _ NODE 訊息請求的最佳節點（即離去予人搜揣鍵閣較近的 K 個節點）。 了後訊息發起者欲向這个 K 到落尾最佳節的發起查詢，不斷迵天代執行來述查詢過程。因為每一个節點比其他的節點對伊周邊的節點有閣較好的感知能力，自按呢回應結果將是一擺一擺離被搜揣鍵值是愈來愈近的某節點。若是閣再回應結果中央的節點無比前回應結果中的節點離被搜揣鍵值閣較近矣，這查詢迵天代嘛就終止矣。現現場迵天的終止的時陣，回應結果集中的 K 個最佳節點就是規个網路中離予人搜揣鍵值上近的 K 個節點（對以上的過程看，按呢顯然是局部的，非常的規个網路）。

節點資訊中會當增加一个往回時間，抑是講號做 RTT 的參數，這个參數會當予人用來定義一个針對每一个予人查詢節點的超時設定，準做向某一个節點發起的查詢超過的時陣，另外一个查詢才會發起，當然喔，針對某一个節點的查詢佇仝一个時刻從來無超過 α 個。

定位資源

通過共資源資訊佮鍵進行對映，資源就可進行定位，雜鬥表是典型的用來對映的手段。因為以前的彼 STORE 訊息，儉較節點會有對應 STORE 所儲存的相關資源的資訊。定位資源的時陣，若是一个儉點有相應的資源的值的時陣，伊就倒轉去資源，撨撨便結束矣，除了該點以外，定位資源佮定位離鍵上近的節點的過程相𫝛。

考慮著節點無一定攏線頂的狀況，資源的值予人存在多个節點上（節點內底的 K 個）， 並且，為著欲提供工作量，閣有可能佇閣較濟節點頂懸儉存值。儲存值的節點會定期搜揣網路內底佮儲存值所對應的一寡加上接近的 K 個節點並且共值複製到遮的節點頂懸，遮的節點會當做為遐的下線的節點的補充。另外咧，對彼普遍流行的內容，可能有較濟的請求需求，通過予遐的存取值的節點共值儲存佇咧附件的一寡節點上（無佇咧 K 個最近節點的範圍之類）來減少儉存值的遐的節點的負載，這款新的儲存技術就是咧欲取技術。通過這種技術，依賴佇咧請求的數量，資源的值被儲存佇離緣愈來愈遠的遐的節點上，這予遐的流行的搜揣會當較緊來揣著資源的儲存者。因為閣倒轉去值的儉點 NODE \ _ ID 遠離值所對應的關鍵字，網路中的「熱點」區域存在的可能性嘛降低矣。依據佮鍵的距離，緊取的遐的節點佇咧一站時間以後將會刪除所儲存的緊取值。分散式雜鬥表的某寡實現（如 Kad）就無欲提供趁食的（複製）節點嘛無欲提供緊取，這主要是為著會當快速減少系統中的陳舊資訊。佇這種網路內底，提供檔案遐的節點將會周期性地更新網路頂的資訊（通過 FIND \ _ NODE 訊息佮 STORE 訊息）。 當存是有某一个檔案的所有的點攏落線矣，關於該檔案的相關的值（源佮關鍵字）的換新也就停止矣，該檔案的相關資訊也就對網路頂頭完全無去。

加入網路

想欲加入網路的節點首先愛經歷一个引導過程。佇引𤆬過程當中，節點需要有知影其他已經加入該網路的某一个節點的 IP 位址佮埠號（會使用者抑是儲存的列表內得著）。 假使當咧引導的彼个節點猶未加入網路，伊會計算一个目前為止猶未分配予其他節點的隨機 ID 號，到離開網路，該當是會一直使用 ID 號。

當咧加入Kademlia網路的節點佇伊的某一个 K 桶內底插入去引導節點（負責加入節點的初始化工作）， 然後向伊的唯一厝邊（引𤆬節點）發起 FIND \ _ NODE 操作請求來定位家己，這種「自我定位」將會使得Kademlia的其他的節點（收著請求的截點）會當使用新加入節點的 Node Id 添充𪜶的 K 桶，同時嘛會當使用遐的查詢過程的中間節點（佇新加入節點佮引導節點的查詢路徑上的其他節點）來補充新加入節點的 K 桶。這自查詢過程會當予新加入節點自引導節點所佇咧的彼个 K 桶開始，由遠及近，每一個得到重新整理，這款重新整理只需要通過 K 桶範圍內底的一个隨機鍵的定位便會用達到。

上早的時陣，節點干焦有一个 K 桶（崁所有的 ID 範圍）， 當做有新節點愛插入去 K 桶的時，若是 K 桶已經滿，K 桶就開始分裂，（參見 APeer-to-peer Information System 二孵四）分裂發生佇節點的 K 桶的崁範圍（表現做二元樹某部份對左至右的所有值）包含講該節點本身的 ID 的時陣。對著節點內距離節點上近的彼个 K 桶，Kademlia會當放鬆限制（即可以到達 K 時無咧發生分裂）， 因為桶內的所有節點離該節點距離上近，遮的節點內底真可能超過 K 個，啊若節點希望知影所有的遮的最近的節點。所以，佇路由樹仔內底，該當選擇附近誠有可能出現懸度無平衡的二元子樹。假使講 K 是二十，新加入網路的節點 ID 為「xxx 一孵一千空一」，則字條呢「xxx 十一……」的點可能有二十一个人，甚至閣較濟的，新的儉點可能包括濟个有含二十一个以上節點的 K 桶。（是因為節點附近的 k 桶）。 這點保證會當予節點會當感覺網路中附近所有的所有節點。（參見 A Peer-to-peer Information System 二孵四）

查詢加速

Kademlia使用互斥抑是來定義距離。兩个節點 ID 的互斥抑是講（抑是節點 ID 佮關鍵字的互斥抑是）的結果就是兩个之間的距離。對每一个位元來講，若相仝，相斥抑是倒轉去，抑無，相斥抑是閣倒轉去。互斥或者是距離滿足三角形不等式：任何一爿的距離小於（抑是等於）其他兩爿距離之和。

互斥抑是講距離予得Kademlia的路由表會當起佇咧單一个 bit 之上，就會使用位組（幾个位聯合）來構建路由表。會當用來表示相應的 K 桶，伊有一个專業術語叫做字首，著一个 m 位的字首來講，可對應二 ^ m 擗一个 K 桶。（m 位的字首本來會當對應二 ^ m 個 K 桶）另外的彼个 K 桶會當進一步擴充做包含講該節點本身 ID 的路由樹仔。一个 b 阮的字首會當共查詢的上大的次數對 logn 減到 logn / b . 這干焦查詢次數的上大值，因為家己 K 桶可能比字首有閣較濟的位佮目標鍵仝款，（這會增加佇家己的 K 桶中揣著節點的機會，假使字首有 m 位，真可能查詢一个鋩角就會當配二 m 甚至閣較濟的位組）， 所以其實平均的查詢次數愛少的濟。（參考 Improving Lookup Performance over a Widely-DeployedDHT 第三部份）

節點會當佇𪜶的路由表中使用混合字首，就親像 eMule 中的 Kad 網路。若以增加查詢的複雜性做代價，Kademlia網路佇路由表示的具體實現甚至會當是有異構的。

學術意義

就算講互斥抑是標準對理解Kademlia並毋是必要的，猶毋過對協定的分析煞誠重要。互斥抑是運算形成做允准合分析的迴圈群，為著會當預見網路的行為佮正確性，其他的一寡分散式雜鬥表協定和演算法攏要求類比抑是複雜的形式分析，而且Kademlia並無需要，另外咧，共位組做路由資訊嘛簡化Kademlia演算法。

佇檔案分享網路中的應用

Kademlia會當做案分享網路內底使用，通過製作Kademlia關鍵字搜揣，咱會當做伙來分享網路內底揣著咱需要的檔案以供咱下載。因為無中央侍服器儲存檔案的索引，這部份的工課就予平均分配著所有的客戶捀著去：親像一个節點希望分享某一个檔案，伊先根據檔案的內容來處理該檔案，通過運算，共檔案的內容雜鬥做一組數字，該數字佇檔案分享網路中會當被用來標識檔案。這組雜鬥數字著愛佮節點 ID 有仝款的長度，然後，該當是佇網路頂懸搜揣 ID 值佮檔案的雜鬥陣值相倚節點，並共伊家己的 IP 位址儲存佇遐的搜揣著的節點頂懸，也就是講，伊共家己做做檔案的源進行矣發布。當咧進行檔案搜揣的客戶捀將使用Kademlia協定來走揣網路頂懸 ID 值得佮希望走揣的檔案的雜鬥值最近的彼个節點，然後取得儲存佇咧彼个節點上的檔案源列表。

因為一个鍵會當對應足濟值，即仝一个檔案會當有偌个源，每一个儲存源列表的儉點可能有無仝款的檔案的資訊，若按呢，源列表會使對佮鍵值相近的 K 較節咧著。檔案的雜鬥值通常會當對其他的一寡特別的 Internet 連結的所在得著，抑是去予包括佇咧對其他某處獲得的索引檔案當中。

檔名的搜揣會使使用關鍵詞來實現，檔名會當分割著連紲的幾个關鍵詞，遮的關鍵詞攏會當雜鬥並且會當佮相應的檔名佮檔案雜鬥陣儲存佇咧網路內底。搜尋者會當使用其中的某一个關鍵詞，聯絡 ID 值佮關鍵詞雜鬥最近的彼个節點，取得包含該關鍵詞的檔案列表。因為你佇檔案列表中的檔案攏有相關的雜鬥值，通過該雜鬥值就會當利用上述通常取檔案的方法得著欲搜揣的檔案。

參考資料

• http : / / blog . csdn . net / cz \ _ hyf / archive / 十二分之二千空九 / 五百空七石六千九百八十八分之二十五 . aspx
• http : / / blog . csdn . net / cz \ _ hyf / archive / 一分之二千空一十 / 五百一十七石八千三百三十分之十一 . aspx
• 《Kademlia: A of Peer to peer information system Based on the XOR Metric》\ * https : / / web . archive . org / web / 二十五空五百一十二孵一千一百空一孵一千六百空五 / http : / / www . cs . rice . edu / Conferences / IPTPS 一百空九分之二 . pdf