近年來，區(qū)塊鏈技術(shù)（部分人更愿意稱之為分布式賬本技術(shù)）的走紅將分布式技術(shù)的概念帶入大眾的視野舌缤。區(qū)塊鏈技術(shù)之所以備受追捧宇立，一方面是其展現(xiàn)了一種在計算機的輔助下，人類可以以無中心冲泥、無權(quán)威、無層級的方式來進行社會協(xié)作的美妙前景壁涎；另一方面凡恍，從物理上可論證，分布式的簡單協(xié)議怔球，比中心化的復(fù)雜協(xié)議更為高效嚼酝。分布式技術(shù)似乎能夠在帶來公平的同時，還帶來效率竟坛。

要理解分布式技術(shù)并不困難闽巩，因為分布式技術(shù)并不高深，但其設(shè)計上往往巧妙得令人拍手稱贊担汤。

本文介紹一種常見而巧妙的分布式技術(shù)涎跨，Kademlia算法。

Kademlia算法是一種分布式存儲及路由的算法崭歧。什么是分布式存儲隅很？試想一下，一所1000人的學(xué)校率碾，現(xiàn)在學(xué)校突然決定拆掉圖書館（不設(shè)立中心化的服務(wù)器）叔营，將圖書館里所有的書都分發(fā)到每位學(xué)生手上（所有的文件分散存儲在各個節(jié)點上）屋彪。即是所有的學(xué)生，共同組成了一個分布式的圖書館绒尊。

由中心圖書館到分布式圖書館

在這種場景下撼班，有幾個關(guān)鍵的問題需要回答。

1）關(guān)鍵問題

1. 每個同學(xué)手上都分配哪些書垒酬。即如何分配存儲內(nèi)容到各個節(jié)點砰嘁，新增/刪除內(nèi)容如何處理。
2. 當你需要找到一本書勘究，譬如《分布式算法》的時候矮湘，如何知道哪位同學(xué)手上有《分布式算法》（對1000個人挨個問一遍，“你有沒有《分布式算法》口糕？”缅阳，顯然是個不經(jīng)濟的做法），又如何聯(lián)系上這位同學(xué)景描。即一個節(jié)點如果想獲取某個特定的文件十办，如何找到存儲文件的節(jié)點/地址/路徑。

如何尋找需要的書籍超棺？

接下來向族，讓我們來看看Kademlia算法如何巧妙地解決這些問題。

2）節(jié)點的要素

首先我們來看看每個同學(xué)（節(jié)點）都有哪些屬性：

• 學(xué)號（Node ID棠绘，2進制件相，160位）
• 手機號碼（節(jié)點的IP地址及端口）

每個同學(xué)會維護以下內(nèi)容：

• 從圖書館分發(fā)下來的書本（被分配到需要存儲的內(nèi)容），每本書當然都有書名和書本內(nèi)容（內(nèi)容以<key, value>對的形式存儲氧苍，可以理解為文件名和文件內(nèi)容）夜矗；
• 一個通訊錄，包含一小部分其他同學(xué)的學(xué)號和手機號让虐，通訊錄按學(xué)號分層（一個路由表紊撕，稱為“k-bucket”，按Node ID分層赡突，記錄有限個數(shù)的其他節(jié)點的ID和IP地址及端口）对扶。

根據(jù)上面那個類比，可以看看這個表格：

概念對比

（Hash的概念解釋麸俘，可參見百度百科-哈希算法）

關(guān)于為什么不是每個同學(xué)都有全量通訊錄（每個節(jié)點都維護全量路由信息）：其一辩稽，分布式系統(tǒng)中節(jié)點的進入和退出是相當頻繁的惧笛，每次有變動時都全網(wǎng)廣播通訊錄更新从媚，通訊量會很大；其二患整，一旦任意一個同學(xué)被壞人綁架了（節(jié)點被黑客攻破）拜效，則壞人馬上就擁有了所有人的手機號碼喷众，這并不安全。

3）文件的存儲及查找

原來收藏在圖書館里紧憾，按索引號碼得整整齊齊的書到千，以一種什么樣的方式分發(fā)到同學(xué)們手里呢？大致的原則赴穗，包括：1）書本能夠比較均衡地分布在同學(xué)們的手里憔四，不會出現(xiàn)部分同學(xué)手里書特別多、而大部分同學(xué)連一本書都沒有的情況般眉；2）同學(xué)想找一本特定的書的時候了赵，能夠一種相對簡單的索引方式找到這本書。
Kademlia作了下面這種安排：
假設(shè)《分布式算法》這本書的書名的hash值是 00010000甸赃，那么這本書就會被要求存在學(xué)號為00010000的同學(xué)手上柿汛。（這要求hash算法的值域與node ID的值域一致。Kademlia的Node ID是160位2進制埠对。這里的示例對Node ID進行了簡略）
但還得考慮到會有同學(xué)缺勤络断。萬一00010000今天沒來上學(xué)（節(jié)點沒有上線或徹底退出網(wǎng)絡(luò)），那《分布式算法》這本書豈不是誰都拿不到了项玛？那算法要求這本書不能只存在一個同學(xué)手上貌笨，而是被要求同時存儲在學(xué)號最接近00010000的k位同學(xué)手上，即00010001襟沮、00010010躁绸、00010011…等同學(xué)手上都會有這本書。

同樣地臣嚣，當你需要找《分布式算法》這本書時净刮，將書名hash一下，得到 00010000硅则，這個便是索書號淹父，你就知道該找哪（幾）位同學(xué)了。剩下的問題怎虫，就是找到這（幾）位同學(xué)的手機號暑认。

書籍搜索定位

4）節(jié)點的異或距離

由于你手上只有一部分同學(xué)的通訊錄，你很可能并沒有00010000的手機號（IP地址）大审。那如何聯(lián)系上目標同學(xué)呢蘸际？

通訊錄上并沒有目標同學(xué)的情況

一個可行的思路就是在你的通訊錄里找到一位擁有目標同學(xué)的聯(lián)系方式的同學(xué)。前面提到徒扶，每位同學(xué)手上的通訊錄都是按距離分層的粮彤。算法的設(shè)計是，如果一個同學(xué)離你越近，你手上的通訊錄里存有ta的手機號碼的概率越大导坟。而算法的核心的思路就可以是：當你知道目標同學(xué)Z與你之間的距離屿良，你可以在你的通訊錄上先找到一個你認為與同學(xué)Z最相近的同學(xué)B，請同學(xué)B再進一步去查找同學(xué)Z的手機號惫周。

上文提到的距離尘惧，是學(xué)號（Node ID）之間的異或距離(XOR distance）。異或是針對yes/no或者二進制的運算.

異或的運算法則為：0⊕0=0递递，1⊕0=1喷橙，0⊕1=1，1⊕1=0（同為0登舞，異為1）
百度百科-異或

舉2個例子：
01010000與01010010距離（即是2個ID的異或值）為00000010（換算為十進制即為2）重慢；
01000000與00000001距離為01000001（換算為十進制即為2⁶+1，即65）逊躁；
如此類推似踱。

那通訊錄是如何按距離分層呢？下面的示例會告訴你稽煤，按異或距離分層核芽，基本上可以理解為按位數(shù)分層。設(shè)想以下情景：
以0000110為基礎(chǔ)節(jié)點酵熙，如果一個節(jié)點的ID轧简，前面所有位數(shù)都與它相同，只有最后1位不同匾二，這樣的節(jié)點只有1個——0000111哮独，與基礎(chǔ)節(jié)點的異或值為0000001，即距離為1察藐；對于0000110而言皮璧，這樣的節(jié)點歸為“k-bucket 1”；
如果一個節(jié)點的ID分飞，前面所有位數(shù)相同悴务，從倒數(shù)第2位開始不同，這樣的節(jié)點只有2個：0000101譬猫、0000100讯檐，與基礎(chǔ)節(jié)點的異或值為0000011和0000010，即距離范圍為3和2染服；對于0000110而言别洪，這樣的節(jié)點歸為“k-bucket 2”；
……
如果一個節(jié)點的ID柳刮，前面所有位數(shù)相同挖垛，從倒數(shù)第n位開始不同痒钝，這樣的節(jié)點只有2^(i-1)個，與基礎(chǔ)節(jié)點的距離范圍為[2^(i-1), 2ⁱ）晕换；對于0000110而言午乓，這樣的節(jié)點歸為“k-bucket i”站宗；

按位數(shù)區(qū)分k-bucket

對上面描述的另一種理解方式：如果將整個網(wǎng)絡(luò)的節(jié)點梳理為一個按節(jié)點ID排列的二叉樹闸准，樹最末端的每個葉子便是一個節(jié)點，則下圖就比較直觀的展現(xiàn)出梢灭，節(jié)點之間的距離的關(guān)系夷家。

k-bucket示意圖：右下角的黑色實心圓，為基礎(chǔ)節(jié)點（按wiki百科的配圖修改）

回到我們的類比敏释。每個同學(xué)只維護一部分的通訊錄库快，這個通訊錄按照距離分層（可以理解為按學(xué)號與自己的學(xué)號從第幾位開始不同而分層），即k-bucket1, k-bucket 2, k-bucket 3…雖然每個k-bucket中實際存在的同學(xué)人數(shù)逐漸增多钥顽，但每個同學(xué)在它自己的每個k-bucket中只記錄k位同學(xué)的手機號（k個節(jié)點的地址與端口义屏，這里的k是一個可調(diào)節(jié)的常量參數(shù)）。
由于學(xué)號（節(jié)點的ID）有160位蜂大，所以每個同學(xué)的通訊錄中共分160層（節(jié)點共有160個k-bucket）闽铐。整個網(wǎng)絡(luò)最多可以容納2^160個同學(xué)（節(jié)點），但是每個同學(xué)（節(jié)點）最多只維護160 * k 行通訊錄（其他節(jié)點的地址與端口）奶浦。

5）節(jié)點定位

我們現(xiàn)在來闡述一個完整的索書流程兄墅。

A同學(xué)（學(xué)號00000110）想找《分布式算法》，A首先需要計算書名的哈希值澳叉，hash(《分布式算法》) = 00010000隙咸。那么A就知道ta需要找到00010000號同學(xué)（命名為Z同學(xué)）或?qū)W號與Z鄰近的同學(xué)。
Z的學(xué)號00010000與自己的異或距離為 00010110成洗，距離范圍在[2⁴, 2⁵)五督，所以這個Z同學(xué)可能在k-bucket 5中（或者說，Z同學(xué)的學(xué)號與A同學(xué)的學(xué)號從第5位開始不同瓶殃，所以Z同學(xué)可能在k-bucket 5中）概荷。
然后A同學(xué)看看自己的k-bucket 5有沒有Z同學(xué)：

• 如果有，那就直接聯(lián)系Z同學(xué)要書碌燕；
• 如果沒有误证，在k-bucket 5里隨便找一個B同學(xué)（注意任意B同學(xué)，它的學(xué)號第5位肯定與Z相同修壕，即它與Z同學(xué)的距離會小于2⁴愈捅，相當于比Z、A之間的距離縮短了一半以上）慈鸠，請求B同學(xué)在它自己的通訊錄里按同樣的查找方式找一下Z同學(xué)：
  -- 如果B知道Z同學(xué)蓝谨，那就把Z同學(xué)的手機號（IP Address）告訴A；
  -- 如果B也不知道Z同學(xué)，那B按同樣的搜索方法譬巫，可以在自己的通訊錄里找到一個離Z更近的C同學(xué)（Z咖楣、C之間距離小于2³），把C同學(xué)推薦給A芦昔；A同學(xué)請求C同學(xué)進行下一步查找诱贿。

查詢方式示意

Kademlia的這種查詢機制，有點像是將一張紙不斷地對折來收縮搜索范圍咕缎，保證對于任意n個學(xué)生珠十，最多只需要查詢log₂(n)次，即可找到獲得目標同學(xué)的聯(lián)系方式（即在對于任意一個有[2^(n?1), 2ⁿ)個節(jié)點的網(wǎng)絡(luò)凭豪，最多只需要n步搜索即可找到目標節(jié)點）焙蹭。

每次搜索都將距離至少收縮一半

以上便是Kademlia算法的基本原理。以下再簡要介紹協(xié)議中的技術(shù)細節(jié)嫂伞。

6）算法的三個參數(shù)：keyspace孔厉，k和α

• keyspace
  -- 即ID有多少位
  -- 決定每個節(jié)點的通訊錄有幾層
• k
  -- 每個一層k-bucket里裝k個node的信息，即<node ID, IP Adress, port>
  -- 每次查找node時帖努，返回k個node的信息
  -- 對于某個特定的data撰豺，離其key最近的k個節(jié)點被會要求存儲這個data
• α
  -- 每次向其他node請求查找某個node時，會向α個node發(fā)出請求

7）節(jié)點的指令

Kademlia算法中然磷，每個節(jié)點只有4個指令

• PING
  -- 測試一個節(jié)點是否在線
• STORE
  -- 要求一個節(jié)點存儲一份數(shù)據(jù)
• FIND_NODE
  -- 根據(jù)節(jié)點ID查找一個節(jié)點
• FIND_VALUE
  -- 根據(jù)KEY查找一個數(shù)據(jù)郑趁，實則上跟FIND_NODE非常類似

8)k-bucket的維護及更新機制

• 每個bucket里的節(jié)點都按最后一次接觸的時間倒序排列
• 每次執(zhí)行四個指令中的任意一個都會觸發(fā)更新
• 當一個節(jié)點與自己接觸時，檢查它是否在K-bucket中
  -- 如果在姿搜，那么將它挪到k-bucket列表的最底（最新）
  -- 如果不在寡润，PING一下列表最上面（最舊）的一個節(jié)點
  -- a) 如果PING通了，將舊節(jié)點挪到列表最底舅柜，并丟棄新節(jié)點
  -- b) 如果PING不通梭纹，刪除舊節(jié)點，并將新節(jié)點加入列表

該機制保證了任意節(jié)點加入和離開都不影響整體網(wǎng)絡(luò)致份。

9）總結(jié)

Kademlia是分布式哈希表（Distributed Hash Table, DHT）的一種变抽。而DHT是一類去中心化的分布式系統(tǒng)。在這類系統(tǒng)中氮块，每個節(jié)點（node）分別維護一部分的存儲內(nèi)容以及其他節(jié)點的路由/地址绍载，使得網(wǎng)絡(luò)中任何參與者（即節(jié)點）發(fā)生變更（進入/退出）時，對整個網(wǎng)絡(luò)造成的影響最小滔蝉。DHT可以用于構(gòu)建更復(fù)雜的應(yīng)用击儡，包括分布式文件系統(tǒng)、點對點技術(shù)文件分享系統(tǒng)蝠引、合作的網(wǎng)頁高速緩存阳谍、域名系統(tǒng)以及實時通信等蛀柴。
Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所設(shè)計，以異或距離來對哈希表進行分層是其特點矫夯。Kademlia后來被eMule鸽疾、BitTorrent等P2P軟件采用作為底層算法。Kademlia可以作為信息安全技術(shù)的奠基之一训貌。
Kademlia的優(yōu)點在于：

• 對于任意一個有[ 2^(n?1) ,2^??)個節(jié)點的網(wǎng)絡(luò)制肮，最多只需要n步搜索即可找到目標節(jié)點；
• K-bucket的更新機制一定程度上保持了網(wǎng)絡(luò)的活性和安全性旺订。

參考文獻
wiki百科-分布式哈希表
wiki百科-Kademlia
Kademlia: A Peer-to-peer information system based on the XOR Metric
王子亭的Kademlia筆記
韓鋒.《區(qū)塊鏈的人工智能》.新星出版社《區(qū)塊鏈新經(jīng)濟藍圖及導(dǎo)讀》的譯后注