Kademlia
維基百科,自由的 encyclopedia
Kademlia是一種通過分散式雜湊表實現的協定演算法,它是由Petar Maymounkov與David Mazières為非集中式P2P電腦網絡而設計的。Kademlia規定了網絡的結構,也規定了通過節點查詢進行資訊交換的方式。參與通訊的所有節點形成一張虛擬網(或者叫做覆蓋網)。這些節點通過一組數字(或稱為節點ID)來進行身份標識。節點ID不僅可以用來做身份標識,還可以用來進行值定位(值通常是檔案的雜湊或者關鍵詞)。其實,節點ID與檔案雜湊直接對應,它所表示的那個節點儲存着哪兒能夠取得檔案和資源的相關資訊。當我們在網絡中搜尋某些值(即通常搜尋儲存檔案雜湊或關鍵詞的節點)的時候,Kademlia演算法需要知道與這些值相關的鍵,然後分步在網絡中開始搜尋。每一步都會找到一些節點,這些節點的ID與鍵更為接近,如果有節點直接返回搜尋的值或者再也無法找到與鍵更為接近的節點ID的時候搜尋便會停止。這種搜尋值的方法是非常高效的:與其他的分散式雜湊表的實現類似,在一個包含n個節點的系統的值的搜尋中,Kademlia僅訪問O(log(n))個節點。非集中式網絡結構還有更大的優勢,那就是它能夠顯著增強抵禦阻斷服務攻擊的能力。即使網絡中的一整批節點遭受泛洪攻擊,也不會對網絡的可用性造成很大的影響,通過繞過這些漏洞(被攻擊的節點)來重新編織一張網絡,網絡的可用性就可以得到恢復。