Kademlia

eMule中的分布式哈希表技術: Kademlia

前兩天在網上看到世界知名的電騾伺服器Razorback 2被查封、4人被拘禁的消息，深感目前做eMule / BitTorrent等P2P檔案交換軟體的不易。以分布式哈希表方式(DHT，Distributed Hash Table)來代替集中索引伺服器可以說是目前可以預見到的為數不多的P2P軟體發展趨勢之一，比較典型的方案主要包括：CAN、CHORD、Tapestry、Pastry、Kademlia和Viceroy等，而Kademlia協定則是其中應用最為廣泛、原理和實作最為實用、簡潔的一種，目前主流的P2P軟體無一例外地采用了它作為自己的輔助檢索協定，如eMule、Bitcomet、Bitspirit和Azureus等。鑒于Kademlia日益增長的強大影響力，今天特地在blog裡寫下這篇小文，算是對其相關知識系統的總結。

1. Kademlia簡述

Kademlia(簡稱Kad)屬于一種典型的結構化P2P覆寫網絡(Structured P2P Overlay Network)，以分布式的應用層全網方式來進行資訊的存儲和檢索是其嘗試解決的主要問題。在Kademlia網絡中，所有資訊均以<key, value>的哈希表條目形式加以存儲，這些條目被分散地存儲在各個節點上，進而以全網方式構成一張巨大的分布式哈希表。我們可以形象地把這張哈希大表看成是一本字典：隻要知道了資訊索引的key，我們便可以通過Kademlia協定來查詢其所對應的value資訊，而不管這個value資訊究竟是存儲在哪一個節點之上。在eMule、BitTorrent等P2P檔案交換系統中，Kademlia主要充當了檔案資訊檢索協定這一關鍵角色，但Kad網絡的應用并不僅限于檔案交換。下文的描述将主要圍繞eMule中Kad網絡的設計與實作展開。

2. eMule的Kad網絡中究竟存儲了哪些資訊?

隻要是能夠表述成為<key, value>字典條目形式的資訊Kad網絡均能存儲，一個Kad網絡能夠同時存儲多張分布式哈希表。以eMule為例，在任一時刻，其Kad網絡均存儲并維護着兩張分布式哈希表，一張我們可以将其命名為關鍵詞字典，而另一張則可以稱之為檔案索引字典。

a. 關鍵詞字典 ：主要用于根據給出的關鍵詞查詢其所對應的檔案名稱及相關檔案資訊，其中key的值等于所給出的關鍵詞字元串的160比特SHA1散列，而其對應的value則為一個清單，在這個清單當中，給出了所有的檔案名稱當中擁有對應關鍵詞的檔案資訊，這些資訊我們可以簡單地用一個3元組條目表示：(檔案名，檔案長度，檔案的SHA1校驗值)，舉個例子，假定存在着一個檔案“warcraft_frozen_throne.iso”，當我們分别以“warcraft”、“frozen”、“throne”這三個關鍵詞來查詢Kad時，Kad将有可能分别傳回三個不同的檔案清單，這三個清單的共同之處則在于它們均包含着一個檔案名為“warcraft_frozen_throne.iso”的資訊條目，通過該條目，我們可以獲得對應iso檔案的名稱、長度及其160比特的SHA1校驗值。

b. 檔案索引字典 ：用于根據給出的檔案資訊來查詢檔案的擁有者(即該檔案的下載下傳服務提供者)，其中key的值等于所需下載下傳檔案的SHA1校驗值(這主要是因為，從統計學角度而言，160比特的SHA1檔案校驗值可以唯一地确定一份特定資料内容的檔案)；而對應的value也是一個清單，它給出了目前所有擁有該檔案的節點的網絡資訊，其中的清單條目我們也可以用一個3元組表示：(擁有者IP，下載下傳偵聽端口，擁有者節點ID)，根據這些資訊，eMule便知道該到哪裡去下載下傳具備同一SHA1校驗值的同一份檔案了。

3. 利用Kad網絡搜尋并下載下傳檔案的基本流程是怎樣的?

基于我們對eMule的Kad網絡中兩本字典的了解，利用Kad網絡搜尋并下載下傳某一特定檔案的基本過程便很明白了，仍以“warcraft_frozen_throne.iso”為例，首先我們可以通過warcraft、frozen、throne等任一關鍵詞查詢關鍵詞字典，得到該iso的SHA1校驗值，然後再通過該校驗值查詢Kad檔案索引字典，進而獲得所有提供“warcraft_frozen_throne.iso”下載下傳的網絡節點，繼而以分段下載下傳方式去這些節點下載下傳整個iso檔案。

在上述過程中，Kad網絡實際上所起的作用就相當于兩本字典，但值得再次指出的是，Kad并不是以集中的索引伺服器(如華語P2P源動力、Razorback 2、DonkeyServer 等，騾友們應該很熟悉吧)方式來實作這兩本字典的存儲和搜尋的，因為這兩本字典的所有<key, value>條目均分布式地存儲在參與Kad網絡的各節點中，相關檔案資訊、下載下傳位置資訊的存儲和交換均無需集中索引伺服器的參與，這不僅提高了查詢效率，而且還提高了整個P2P檔案交換系統的可靠性，同時具備相當的反拒絕服務攻擊能力；更有意思的是，它能幫助我們有效地抵制FBI的追捕，因為俗話說得好：法不治衆…看到這裡，相信大家都能了解“分布式資訊檢索”所帶來的好處了吧。但是，這些條目究竟是怎樣存儲的呢?我們又該如何通過Kad網絡來找到它們?不着急，慢慢來。

4. 什麼叫做節點的ID和節點之間的距離?

Kad網絡中的每一個節點均擁有一個專屬ID，該ID的具體形式與SHA1散列值類似，為一個長達160bit的整數，它是由節點自己随機生成的，兩個節點擁有同一ID的可能性非常之小，是以可以認為這幾乎是不可能的。在Kad網絡中，兩個節點之間距離并不是依靠實體距離、路由器跳數來衡量的，事實上，Kad網絡将任意兩個節點之間的距離d定義為其二者ID值的逐比特二進制和數，即，假定兩個節點的ID分别為a與b，則有：d=a XOR b。在Kad中，每一個節點都可以根據這一距離概念來判斷其他節點距離自己的“遠近”，當d值大時，節點間距離較遠，而當d值小時，則兩個節點相距很近。這裡的“遠近”和“距離”都隻是一種邏輯上的度量描述而已；在Kad中，距離這一度量是無方向性的，也就是說a到b的距離恒等于b到a的距離，因為a XOR b==b XOR a

5. <key, value>條目是如何存儲在Kad網絡中的?

從上文中我們可以發現節點ID與<key, value>條目中key值的相似性：無論是關鍵詞字典的key，還是檔案索引字典的key，都是160bit，而節點ID恰恰也是160bit。這顯然是有目的的。事實上，節點的ID值也就決定了哪些<key, value>條目可以存儲在該節點之中，因為我們完全可以把某一個<key, value>條目簡單地存放在節點ID值恰好等于條目中key值的那個節點處，我們可以将滿足(ID==key)這一條件的節點命名為目标節點N。這樣的話，一個查找<key, value>條目的問題便被簡單地轉化成為了一個查找ID等于Key值的節點的問題。

由于在實際的Kad網絡當中，并不能保證在任一時刻目标節點N均一定存在或者線上，是以Kad網絡規定：任一<key, value>條目，依據其key的具體取值，該條目将被複制并存放在節點ID距離key值最近(即目前距離目标節點N最近)的k個節點當中；之是以要将<key, value>重複儲存k份，這完全是考慮到整個Kad系統穩定性而引入的備援；這個k的取值也有講究，它是一個帶有啟發性質的估計值，挑選其取值的準則為：“在目前規模的Kad網絡中任意選擇至少k個節點，令它們在任意時刻同時不線上的幾率幾乎為0”；目前，k的典型取值為20，即，為保證在任何時刻我們均能找到至少一份某<key, value>條目的拷貝，我們必須事先在Kad網絡中将該條目複制至少20份。

由上述可知，對于某一<key, value>條目，在Kad網絡中ID越靠近key的節點區域，該條目儲存的份數就越多，存儲得也越集中；事實上，為了實作較短的查詢響應延遲，在條目查詢的過程中，任一條目可被cache到任意節點之上；同時為了防止過度cache、保證資訊足夠新鮮，必須考慮<key, value>條目在節點上存儲的時效性：越接近目标結點N，該條目儲存的時間将越長，反之，其逾時時間就越短；儲存在目标節點之上的條目最多能夠被保留24小時，如果在此期間該條目被其釋出源重新釋出的話，其儲存時間還可以進一步延長。

6. Kad網絡節點需要維護哪些狀态資訊?

在Kad網絡中，每一個節點均維護了160個list，其中的每個list均被稱之為一個k-桶(k-bucket)，如下圖所示。在第i個list中，記錄了目前節點已知的與自身距離為2^i~2^(i+1)的一些其他對端節點的網絡資訊(Node ID，IP位址，UDP端口)，每一個list(k-桶)中最多存放k個對端節點資訊，注意，此處的k與上文所提到的複制系數k含義是一緻的；每一個list中的對端節點資訊均按通路時間排序，最早通路的在list頭部，而最近新通路的則放在list的尾部。

k-桶中節點資訊的更新基本遵循Least-recently Seen Eviction原則：當list容量未滿(k-桶中節點個數未滿k個)，且最新通路的對端節點資訊不在目前list中時，其資訊将直接添入list隊尾，如果其資訊已經在目前list中，則其将被移動至隊尾；在k-桶容量已滿的情況下，添加新節點的情況有點特殊，它将首先檢查最早通路的隊首節點是否仍有響應，如果有，則隊首節點被移至隊尾，新通路節點資訊被抛棄，如果沒有，這才抛棄隊首節點，将最新通路的節點資訊插入隊尾。可以看出，盡可能重用已有節點資訊、并且按時間排序是k-桶節點更新方式的主要特點。從啟發性的角度而言，這種方式具有一定的依據：線上時間長一點的節點更值得我們信任，因為它已經線上了若幹小時，是以，它在下一個小時以内保持線上的可能性将比我們最新通路的節點更大，或者更直覺點，我這裡再給出一個更加人性化的解釋：MP3檔案交換本身是一種觸犯版權法律的行為，某一個節點反正已經犯了若幹個小時的法了，是以，它将比其他新加入的節點更不在乎再多犯一個小時的罪……-_-b

由上可見，設計采用這種多k-bucket資料結構的初衷主要有二：a. 維護最近-最新見到的節點資訊更新；b. 實作快速的節點資訊篩選操作，也就是說，隻要知道某個需要查找的特定目标節點N的ID，我們便可以從目前節點的k-buckets結構中迅速地查出距離N最近的若幹已知節點。

7. 在Kad網絡中如何尋找某特定的節點?

已知某節點ID，查找獲得目前Kad網絡中與之距離最短的k個節點所對應的網絡資訊(Node ID，IP位址，UDP端口)的過程，即為Kad網絡中的一次節點查詢過程(Node Lookup)。注意，Kad之是以沒有把節點查詢過程嚴格地定義成為僅僅隻查詢單個目标節點的過程，這主要是因為Kad網絡并沒有對節點的上線時間作出任何前提假設，是以在多數情況下我們并不能肯定需要查找的目标節點一定線上或存在。

整個節點查詢過程非常直接，其方式類似于DNS的疊代查詢：

a. 由查詢發起者從自己的k-桶中篩選出若幹距離目标ID最近的節點，并向這些節點同時發送異步查詢請求；

b .被查詢節點收到請求之後，将從自己的k-桶中找出自己所知道的距離查詢目标ID最近的若幹個節點，并傳回給發起者；

c. 發起者在收到這些傳回資訊之後，再次從自己目前所有已知的距離目标較近的節點中挑選出若幹沒有請求過的，并重複步驟1；

d. 上述步驟不斷重複，直至無法獲得比查詢者目前已知的k個節點更接近目标的活動節點為止。

e. 在查詢過程中，沒有及時響應的節點将立即被排除；查詢者必須保證最終獲得的k個最近節點都是活動的。

簡單總結一下上述過程，實際上它跟我們日常生活中去找某一個人打聽某件事是非常相似的，比方說你是個Agent Smith，想找小李(key)問問他的手機号碼(value)，但你事先并不認識他，你首先肯定會去找你所認識的和小李在同一個公司工作的人，比方說小趙，然後小趙又會告訴你去找與和小李在同一部門的小劉，然後小劉又會進一步告訴你去找和小李在同一個項目組的小張，最後，你找到了小張，喲，正好小李出差去了(節點下線了)，但小張恰好知道小李的号碼(cache)，這樣你總算找到了所需的資訊。在節點查找的過程中，“節點距離的遠近”實際上與上面例子中“人際關系的密切程度”所代表的含義是一樣的。

最後說說上述查詢過程的局限性：Kad網絡并不适合應用于模糊搜尋，如通配符支援、部分查找等場合，但對于檔案共享場合來說，基于關鍵詞的精确查找功能已經基本足夠了(值得注意的是，實際上我們隻要對上述查找過程稍加改進，并可以令其支援基于關鍵詞比對的布爾條件查詢，但仍不夠優化)。這個問題反映到eMule的應用層面來，它直接說明了檔案共享時其命名的重要性所在，即，檔案名中的關鍵詞定義得越明顯，則該檔案越容易被找到，進而越有利于其在P2P網絡中的傳播；而另一方面，在eMule中，每一個共享檔案均可以擁有自己的相關注釋，而Comment的重要性還沒有被大家認識到：實際上，這個檔案注釋中的關鍵詞也可以直接被利用來替代檔案名關鍵詞，進而指導和友善使用者搜尋，尤其是當檔案名本身并沒有展現出關鍵詞的時候。

8. 在Kad網絡中如何存儲和搜尋某特定的<key, value>條目?

從本質上而言，存儲、搜尋某特定<key, value>條目的問題實際上就是節點查找的問題。當需要在Kad網絡中存儲一個條目時，可以首先通過節點查找算法找到距離key最近的k個節點，然後再通知它們儲存<key, value>條目即可。而搜尋條目的過程則與節點查詢過程也是基本類似，由搜尋發起方以疊代方式不斷查詢距離key較近的節點，一旦查詢路徑中的任一節點傳回了所需查找的value，整個搜尋的過程就結束。為提高效率，當搜尋成功之後，發起方可以選擇将搜尋到的條目存儲到查詢路徑的多個節點中，作為友善後繼查詢的cache；條目cache的逾時時間與節點-key之間的距離呈指數反比關系。

9. 一個新節點如何首次加入Kad網絡?

當一個新節點首次試圖加入Kad網絡時，它必須做三件事，其一，不管通過何種途徑，獲知一個已經加入Kad網絡的節點資訊(我們可以稱之為節點I)，并将其加入自己的k-buckets；其二，向該節點發起一次針對自己ID的節點查詢請求，進而通過節點I擷取一系列與自己距離鄰近的其他節點的資訊；最後，重新整理所有的k-bucket，保證自己所獲得的節點資訊全部都是新鮮的。

參考文獻

1. Kademlia: A Peer-to-peer Information System Based on the XOR Metric , Petar Maymounkov, Proc. IPTPS 2002

2. 到底什麼是Kad, http://bbs.5qzone.net/read.php?tid=321431

3. Kademlia原理介紹, http://www.edonkey2000.cn/bbs/viewthread.php?tid=58238