近年來，區塊鏈技術（部分人更願意稱之為分布式賬本技術）的走紅將分布式技術的概念帶入大眾的視野。區塊鏈技術之所以備受追捧，壹方面是其展現了壹種在計算機的輔助下，人類可以以無中心、無權威、無層級的方式來進行社會協作的美妙前景；另壹方面，從物理上可論證，分布式的簡單協議，比中心化的復雜協議更為高效。分布式技術似乎能夠在帶來公平的同時，還帶來效率。
要理解分布式技術並不困難，因為分布式技術並不高深，但其設計上往往巧妙得令人拍手稱贊。
本文介紹壹種常見而巧妙的分布式技術，Kademlia算法。
Kademlia算法是壹種分布式存儲及路由的算法。什麽是分布式存儲？試想壹下，壹所1000人的學校，現在學校突然決定拆掉圖書館（不設立中心化的服務器），將圖書館裏所有的書都分發到每位學生手上（所有的文件分散存儲在各個節點上）。即是所有的學生，***同組成了壹個分布式的圖書館。
在這種場景下，有幾個關鍵的問題需要回答。
接下來，讓我們來看看Kademlia算法如何巧妙地解決這些問題。
首先我們來看看每個同學（節點）都有哪些屬性：
每個同學會維護以下內容：
根據上面那個類比，可以看看這個表格：
（Hash的概念解釋，可參見 百度百科-哈希算法 ）
關於為什麽不是每個同學都有全量通訊錄（每個節點都維護全量路由信息）：其壹，分布式系統中節點的進入和退出是相當頻繁的，每次有變動時都全網廣播通訊錄更新，通訊量會很大；其二，壹旦任意壹個同學被壞人綁架了（節點被黑客攻破），則壞人馬上就擁有了所有人的手機號碼，這並不安全。
原來收藏在圖書館裏，按索引號碼得整整齊齊的書，以壹種什麽樣的方式分發到同學們手裏呢？大致的原則，包括：1）書本能夠比較均衡地分布在同學們的手裏，不會出現部分同學手裏書特別多、而大部分同學連壹本書都沒有的情況；2）同學想找壹本特定的書的時候，能夠壹種相對簡單的索引方式找到這本書。
Kademlia作了下面這種安排：
假設《分布式算法》這本書的書名的hash值是 00010000 ，那麽這本書就會被要求存在學號為 00010000 的同學手上。（這要求hash算法的值域與node ID的值域壹致。Kademlia的Node ID是160位2進制。這裏的示例對Node ID進行了簡略）
但還得考慮到會有同學缺勤。萬壹 00010000 今天沒來上學（節點沒有上線或徹底退出網絡），那《分布式算法》這本書豈不是誰都拿不到了？那算法要求這本書不能只存在壹個同學手上，而是被要求同時存儲在學號最接近 00010000 的k位同學手上，即 00010001 、 00010010 、 00010011 …等同學手上都會有這本書。
同樣地，當妳需要找《分布式算法》這本書時，將書名hash壹下，得到 00010000 ，這個便是索書號，妳就知道該找哪（幾）位同學了。剩下的問題，就是找到這（幾）位同學的手機號。
由於妳手上只有壹部分同學的通訊錄，妳很可能並沒有 00010000 的手機號（IP地址）。那如何聯系上目標同學呢？
壹個可行的思路就是在妳的通訊錄裏找到壹位擁有目標同學的聯系方式的同學。前面提到，每位同學手上的通訊錄都是按距離分層的。算法的設計是，如果壹個同學離妳越近，妳手上的通訊錄裏存有ta的手機號碼的概率越大。而算法的核心的思路就可以是：當妳知道目標同學Z與妳之間的距離，妳可以在妳的通訊錄上先找到壹個妳認為與同學Z最相近的同學B，請同學B再進壹步去查找同學Z的手機號。
上文提到的距離，是學號（Node ID）之間的異或距離(XOR distance）。異或是針對yes/no或者二進制的運算.
舉2個例子：
01010000 與 01010010 距離（即是2個ID的異或值）為 00000010 （換算為十進制即為2）；
01000000 與 00000001 距離為 01000001 （換算為十進制即為2 6 +1，即65）；
如此類推。
那通訊錄是如何按距離分層呢？下面的示例會告訴妳，按異或距離分層，基本上可以理解為按位數分層。設想以下情景：
以 0000110 為基礎節點，如果壹個節點的ID，前面所有位數都與它相同，只有最後1位不同，這樣的節點只有1個—— 0000111 ，與基礎節點的異或值為 0000001 ，即距離為1；對於 0000110 而言，這樣的節點歸為 “k-bucket 1” ；
如果壹個節點的ID，前面所有位數相同，從倒數第2位開始不同，這樣的節點只有2個： 0000101 、 0000100 ，與基礎節點的異或值為 0000011 和 0000010 ，即距離範圍為3和2；對於 0000110 而言，這樣的節點歸為 “k-bucket 2” ；
……
如果壹個節點的ID，前面所有位數相同，從倒數第n位開始不同，這樣的節點只有2 (i-1) 個，與基礎節點的距離範圍為[2 (i-1) , 2 i ）；對於 0000110 而言，這樣的節點歸為 “k-bucket i” ；
對上面描述的另壹種理解方式：如果將整個網絡的節點梳理為壹個按節點ID排列的二叉樹，樹最末端的每個葉子便是壹個節點，則下圖就比較直觀的展現出，節點之間的距離的關系。
回到我們的類比。每個同學只維護壹部分的通訊錄，這個通訊錄按照距離分層（可以理解為按學號與自己的學號從第幾位開始不同而分層），即k-bucket1, k-bucket 2, k-bucket 3…雖然每個k-bucket中實際存在的同學人數逐漸增多，但每個同學在它自己的每個k-bucket中只記錄k位同學的手機號（k個節點的地址與端口，這裏的k是壹個可調節的常量參數）。
由於學號（節點的ID）有160位，所以每個同學的通訊錄中***分160層（節點***有160個k-bucket）。整個網絡最多可以容納2^160個同學（節點），但是每個同學（節點）最多只維護160 * k 行通訊錄（其他節點的地址與端口）。
我們現在來闡述壹個完整的索書流程。
A同學（學號 00000110 ）想找《分布式算法》，A首先需要計算書名的哈希值，hash(《分布式算法》) = 00010000 。那麽A就知道ta需要找到 00010000 號同學（命名為Z同學）或學號與Z鄰近的同學。
Z的學號 00010000 與自己的異或距離為 00010110 ，距離範圍在[2 4 , 2 5 )，所以這個Z同學可能在k-bucket 5中（或者說，Z同學的學號與A同學的學號從第5位開始不同，所以Z同學可能在k-bucket 5中）。
然後A同學看看自己的k-bucket 5有沒有Z同學：
Kademlia的這種查詢機制，有點像是將壹張紙不斷地對折來收縮搜索範圍，保證對於任意n個學生，最多只需要查詢log 2 (n)次，即可找到獲得目標同學的聯系方式（即在對於任意壹個有[2 (n?1) , 2 n )個節點的網絡，最多只需要n步搜索即可找到目標節點）。
以上便是Kademlia算法的基本原理。以下再簡要介紹協議中的技術細節。
Kademlia算法中，每個節點只有4個指令
該機制保證了任意節點加入和離開都不影響整體網絡。
Kademlia是分布式哈希表（Distributed Hash Table, DHT）的壹種。而DHT是壹類去中心化的分布式系統。在這類系統中，每個節點（node）分別維護壹部分的存儲內容以及其他節點的路由/地址，使得網絡中任何參與者（即節點）發生變更（進入/退出）時，對整個網絡造成的影響最小。DHT可以用於構建更復雜的應用，包括分布式文件系統、點對點技術文件分享系統、合作的網頁高速緩存、域名系統以及實時通信等。
Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所設計，以異或距離來對哈希表進行分層是其特點。Kademlia後來被eMule、BitTorrent等P2P軟件采用作為底層算法。Kademlia可以作為信息安全技術的奠基之壹。
Kademlia的優點在於：
參考文獻
wiki百科-分布式哈希表
wiki百科-Kademlia
Kademlia: A Peer-to-peer information system based on the XOR Metric
王子亭的Kademlia筆記
韓鋒.《區塊鏈的人工智能》.新星出版社《區塊鏈新經濟藍圖及導讀》的譯後註