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

　　Kademlia(簡(jiǎn)稱Kad)屬于一種典型的結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)(Structured P2P Overlay NETwork)，以分布式的應(yīng)用層全網(wǎng)方式來進(jìn)行信息的存儲(chǔ)和檢索是其嘗試解決的主要問題。在Kademlia網(wǎng)絡(luò)中，所有信息均以<key, value>的哈希表?xiàng)l目形式加以存儲(chǔ)，這些條目被分散地存儲(chǔ)在各個(gè)節(jié)點(diǎn)上，從而以全網(wǎng)方式構(gòu)成一張巨大的分布式哈希表。我們可以形象地把這張哈希大表看成是一本字典：只要知道了信息索引的key，我們便可以通過Kademlia協(xié)議來查詢其所對(duì)應(yīng)的value信息，而不管這個(gè)value信息究竟是存儲(chǔ)在哪一個(gè)節(jié)點(diǎn)之上。在eMule、BitTorrent等P2P文件交換系統(tǒng)中，Kademlia主要充當(dāng)了文件信息檢索協(xié)議這一關(guān)鍵角色，但Kad網(wǎng)絡(luò)的應(yīng)用并不僅限于文件交換。下文的描述將主要圍繞eMule中Kad網(wǎng)絡(luò)的設(shè)計(jì)與實(shí)現(xiàn)展開。
　　2. eMule的Kad網(wǎng)絡(luò)中究竟存儲(chǔ)了哪些信息?

　　只要是能夠表述成為<key, value>字典條目形式的信息Kad網(wǎng)絡(luò)均能存儲(chǔ)，一個(gè)Kad網(wǎng)絡(luò)能夠同時(shí)存儲(chǔ)多張分布式哈希表。以eMule為例，在任一時(shí)刻，其Kad網(wǎng)絡(luò)均存儲(chǔ)并維護(hù)著兩張分布式哈希表，一張我們可以將其命名為關(guān)鍵詞字典，而另一張則可以稱之為文件索引字典。

　　a. 關(guān)鍵詞字典：主要用于根據(jù)給出的關(guān)鍵詞查詢其所對(duì)應(yīng)的文件名稱及相關(guān)文件信息，其中key的值等于所給出的關(guān)鍵詞字符串的160比特SHA1散列，而其對(duì)應(yīng)的value則為一個(gè)列表，在這個(gè)列表當(dāng)中，給出了所有的文件名稱當(dāng)中擁有對(duì)應(yīng)關(guān)鍵詞的文件信息，這些信息我們可以簡(jiǎn)單地用一個(gè)3元組條目表示：(文件名，文件長(zhǎng)度，文件的SHA1校驗(yàn)值)，舉個(gè)例子，假定存在著一個(gè)文件“warcraft_frozen_throne.iso”，當(dāng)我們分別以“warcraft”、“frozen”、“throne”這三個(gè)關(guān)鍵詞來查詢Kad時(shí)，Kad將有可能分別返回三個(gè)不同的文件列表，這三個(gè)列表的共同之處則在于它們均包含著一個(gè)文件名為“warcraft_frozen_throne.iso”的信息條目，通過該條目，我們可以獲得對(duì)應(yīng)iso文件的名稱、長(zhǎng)度及其160比特的SHA1校驗(yàn)值。

　　b. 文件索引字典：用于根據(jù)給出的文件信息來查詢文件的擁有者(即該文件的下載服務(wù)提供者)，其中key的值等于所需下載文件的SHA1校驗(yàn)值(這主要是因?yàn)椋瑥慕y(tǒng)計(jì)學(xué)角度而言，160比特的SHA1文件校驗(yàn)值可以唯一地確定一份特定數(shù)據(jù)內(nèi)容的文件)；而對(duì)應(yīng)的value也是一個(gè)列表，它給出了當(dāng)前所有擁有該文件的節(jié)點(diǎn)的網(wǎng)絡(luò)信息，其中的列表?xiàng)l目我們也可以用一個(gè)3元組表示：(擁有者IP，下載偵聽端口，擁有者節(jié)點(diǎn)ID)，根據(jù)這些信息，eMule便知道該到哪里去下載具備同一SHA1校驗(yàn)值的同一份文件了。
　　3. 利用Kad網(wǎng)絡(luò)搜索并下載文件的基本流程是怎樣的?

　　基于我們對(duì)eMule的Kad網(wǎng)絡(luò)中兩本字典的理解，利用Kad網(wǎng)絡(luò)搜索并下載某一特定文件的基本過程便很明白了，仍以“warcraft_frozen_throne.iso”為例，首先我們可以通過warcraft、frozen、throne等任一關(guān)鍵詞查詢關(guān)鍵詞字典，得到該iso的SHA1校驗(yàn)值，然后再通過該校驗(yàn)值查詢Kad文件索引字典，從而獲得所有提供“warcraft_frozen_throne.iso”下載的網(wǎng)絡(luò)節(jié)點(diǎn)，繼而以分段下載方式去這些節(jié)點(diǎn)下載整個(gè)iso文件。

　　在上述過程中，Kad網(wǎng)絡(luò)實(shí)際上所起的作用就相當(dāng)于兩本字典，但值得再次指出的是，Kad并不是以集中的索引服務(wù)器(如華語P2P源動(dòng)力、Razorback 2、DonkeyServer 等，騾友們應(yīng)該很熟悉吧)方式來實(shí)現(xiàn)這兩本字典的存儲(chǔ)和搜索的，因?yàn)檫@兩本字典的所有<key, value>條目均分布式地存儲(chǔ)在參與Kad網(wǎng)絡(luò)的各節(jié)點(diǎn)中，相關(guān)文件信息、下載位置信息的存儲(chǔ)和交換均無需集中索引服務(wù)器的參與，這不僅提高了查詢效率，而且還提高了整個(gè)P2P文件交換系統(tǒng)的可靠性，同時(shí)具備相當(dāng)?shù)姆淳芙^服務(wù)攻擊能力；更有意思的是，它能幫助我們有效地抵制FBI的追捕，因?yàn)樗自捳f得好：法不治眾…看到這里，相信大家都能理解“分布式信息檢索”所帶來的好處了吧。但是，這些條目究竟是怎樣存儲(chǔ)的呢?我們又該如何通過Kad網(wǎng)絡(luò)來找到它們?不著急，慢慢來。
　　4. 什么叫做節(jié)點(diǎn)的ID和節(jié)點(diǎn)之間的距離?

　　Kad網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)均擁有一個(gè)專屬ID，該ID的具體形式與SHA1散列值類似，為一個(gè)長(zhǎng)達(dá)160bit的整數(shù)，它是由節(jié)點(diǎn)自己隨機(jī)生成的，兩個(gè)節(jié)點(diǎn)擁有同一ID的可能性非常之小，因此可以認(rèn)為這幾乎是不可能的。在Kad網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)之間距離并不是依靠物理距離、路由器跳數(shù)來衡量的，事實(shí)上，Kad網(wǎng)絡(luò)將任意兩個(gè)節(jié)點(diǎn)之間的距離d定義為其二者ID值的逐比特二進(jìn)制和數(shù)，即，假定兩個(gè)節(jié)點(diǎn)的ID分別為a與b，則有：d=a XOR b。在Kad中，每一個(gè)節(jié)點(diǎn)都可以根據(jù)這一距離概念來判斷其他節(jié)點(diǎn)距離自己的“遠(yuǎn)近”，當(dāng)d值大時(shí)，節(jié)點(diǎn)間距離較遠(yuǎn)，而當(dāng)d值小時(shí)，則兩個(gè)節(jié)點(diǎn)相距很近。這里的“遠(yuǎn)近”和“距離”都只是一種邏輯上的度量描述而已；在Kad中，距離這一度量是無方向性的，也就是說a到b的距離恒等于b到a的距離，因?yàn)閍 XOR b==b XOR a
　　5. <key, value>條目是如何存儲(chǔ)在Kad網(wǎng)絡(luò)中的?

　　從上文中我們可以發(fā)現(xiàn)節(jié)點(diǎn)ID與<key, value>條目中key值的相似性：無論是關(guān)鍵詞字典的key，還是文件索引字典的key，都是160bit，而節(jié)點(diǎn)ID恰恰也是160bit。這顯然是有目的的。事實(shí)上，節(jié)點(diǎn)的ID值也就決定了哪些<key, value>條目可以存儲(chǔ)在該節(jié)點(diǎn)之中，因?yàn)槲覀兺耆梢园涯骋粋€(gè)<key, value>條目簡(jiǎn)單地存放在節(jié)點(diǎn)ID值恰好等于條目中key值的那個(gè)節(jié)點(diǎn)處，我們可以將滿足(ID==key)這一條件的節(jié)點(diǎn)命名為目標(biāo)節(jié)點(diǎn)N。這樣的話，一個(gè)查找<key, value>條目的問題便被簡(jiǎn)單地轉(zhuǎn)化成為了一個(gè)查找ID等于Key值的節(jié)點(diǎn)的問題。

　　由于在實(shí)際的Kad網(wǎng)絡(luò)當(dāng)中，并不能保證在任一時(shí)刻目標(biāo)節(jié)點(diǎn)N均一定存在或者在線，因此Kad網(wǎng)絡(luò)規(guī)定：任一<key, value>條目，依據(jù)其key的具體取值，該條目將被復(fù)制并存放在節(jié)點(diǎn)ID距離key值最近(即當(dāng)前距離目標(biāo)節(jié)點(diǎn)N最近)的k個(gè)節(jié)點(diǎn)當(dāng)中；之所以要將<key, value>重復(fù)保存k份，這完全是考慮到整個(gè)Kad系統(tǒng)穩(wěn)定性而引入的冗余；這個(gè)k的取值也有講究，它是一個(gè)帶有啟發(fā)性質(zhì)的估計(jì)值，挑選其取值的準(zhǔn)則為：“在當(dāng)前規(guī)模的Kad網(wǎng)絡(luò)中任意選擇至少k個(gè)節(jié)點(diǎn)，令它們?cè)谌我鈺r(shí)刻同時(shí)不在線的幾率幾乎為0”；目前，k的典型取值為20，即，為保證在任何時(shí)刻我們均能找到至少一份某<key, value>條目的拷貝，我們必須事先在Kad網(wǎng)絡(luò)中將該條目復(fù)制至少20份。

　　由上述可知，對(duì)于某一<key, value>條目，在Kad網(wǎng)絡(luò)中ID越靠近key的節(jié)點(diǎn)區(qū)域，該條目保存的份數(shù)就越多，存儲(chǔ)得也越集中；事實(shí)上，為了實(shí)現(xiàn)較短的查詢響應(yīng)延遲，在條目查詢的過程中，任一條目可被cache到任意節(jié)點(diǎn)之上；同時(shí)為了防止過度cache、保證信息足夠新鮮，必須考慮<key, value>條目在節(jié)點(diǎn)上存儲(chǔ)的時(shí)效性：越接近目標(biāo)結(jié)點(diǎn)N，該條目保存的時(shí)間將越長(zhǎng)，反之，其超時(shí)時(shí)間就越短；保存在目標(biāo)節(jié)點(diǎn)之上的條目最多能夠被保留24小時(shí)，如果在此期間該條目被其發(fā)布源重新發(fā)布的話，其保存時(shí)間還可以進(jìn)一步延長(zhǎng)。
　　6. Kad網(wǎng)絡(luò)節(jié)點(diǎn)需要維護(hù)哪些狀態(tài)信息?

　　在Kad網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)均維護(hù)了160個(gè)list，其中的每個(gè)list均被稱之為一個(gè)k-桶(k-bucket)，如下圖所示。在第i個(gè)list中，記錄了當(dāng)前節(jié)點(diǎn)已知的與自身距離為2^i~2^(i+1)的一些其他對(duì)端節(jié)點(diǎn)的網(wǎng)絡(luò)信息(Node ID，IP地址，UDP端口)，每一個(gè)list(k-桶)中最多存放k個(gè)對(duì)端節(jié)點(diǎn)信息，注意，此處的k與上文所提到的復(fù)制系數(shù)k含義是一致的；每一個(gè)list中的對(duì)端節(jié)點(diǎn)信息均按訪問時(shí)間排序，最早訪問的在list頭部，而最近新訪問的則放在list的尾部。

　　k-桶中節(jié)點(diǎn)信息的更新基本遵循Least-recently Seen Eviction原則：當(dāng)list容量未滿(k-桶中節(jié)點(diǎn)個(gè)數(shù)未滿k個(gè))，且最新訪問的對(duì)端節(jié)點(diǎn)信息不在當(dāng)前l(fā)ist中時(shí)，其信息將直接添入list隊(duì)尾，如果其信息已經(jīng)在當(dāng)前l(fā)ist中，則其將被移動(dòng)至隊(duì)尾；在k-桶容量已滿的情況下，添加新節(jié)點(diǎn)的情況有點(diǎn)特殊，它將首先檢查最早訪問的隊(duì)首節(jié)點(diǎn)是否仍有響應(yīng)，如果有，則隊(duì)首節(jié)點(diǎn)被移至隊(duì)尾，新訪問節(jié)點(diǎn)信息被拋棄，如果沒有，這才拋棄隊(duì)首節(jié)點(diǎn)，將最新訪問的節(jié)點(diǎn)信息插入隊(duì)尾。可以看出，盡可能重用已有節(jié)點(diǎn)信息、并且按時(shí)間排序是k-桶節(jié)點(diǎn)更新方式的主要特點(diǎn)。從啟發(fā)性的角度而言，這種方式具有一定的依據(jù)：在線時(shí)間長(zhǎng)一點(diǎn)的節(jié)點(diǎn)更值得我們信任，因?yàn)樗呀?jīng)在線了若干小時(shí)，因此，它在下一個(gè)小時(shí)以內(nèi)保持在線的可能性將比我們最新訪問的節(jié)點(diǎn)更大，或者更直觀點(diǎn)，我這里再給出一個(gè)更加人性化的解釋：MP3文件交換本身是一種觸犯版權(quán)法律的行為，某一個(gè)節(jié)點(diǎn)反正已經(jīng)犯了若干個(gè)小時(shí)的法了，因此，它將比其他新加入的節(jié)點(diǎn)更不在乎再多犯一個(gè)小時(shí)的罪……-_-b

　　由上可見，設(shè)計(jì)采用這種多k-bucket數(shù)據(jù)結(jié)構(gòu)的初衷主要有二：a. 維護(hù)最近-最新見到的節(jié)點(diǎn)信息更新；b. 實(shí)現(xiàn)快速的節(jié)點(diǎn)信息篩選操作，也就是說，只要知道某個(gè)需要查找的特定目標(biāo)節(jié)點(diǎn)N的ID，我們便可以從當(dāng)前節(jié)點(diǎn)的k-buckets結(jié)構(gòu)中迅速地查出距離N最近的若干已知節(jié)點(diǎn)。
　　7. 在Kad網(wǎng)絡(luò)中如何尋找某特定的節(jié)點(diǎn)?

　　已知某節(jié)點(diǎn)ID，查找獲得當(dāng)前Kad網(wǎng)絡(luò)中與之距離最短的k個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的網(wǎng)絡(luò)信息(Node ID，IP地址，UDP端口)的過程，即為Kad網(wǎng)絡(luò)中的一次節(jié)點(diǎn)查詢過程(Node Lookup)。注意，Kad之所以沒有把節(jié)點(diǎn)查詢過程嚴(yán)格地定義成為僅僅只查詢單個(gè)目標(biāo)節(jié)點(diǎn)的過程，這主要是因?yàn)镵ad網(wǎng)絡(luò)并沒有對(duì)節(jié)點(diǎn)的上線時(shí)間作出任何前提假設(shè)，因此在多數(shù)情況下我們并不能肯定需要查找的目標(biāo)節(jié)點(diǎn)一定在線或存在。

　　整個(gè)節(jié)點(diǎn)查詢過程非常直接，其方式類似于DNS的迭代查詢：
　　a. 由查詢發(fā)起者從自己的k-桶中篩選出若干距離目標(biāo)ID最近的節(jié)點(diǎn)，并向這些節(jié)點(diǎn)同時(shí)發(fā)送異步查詢請(qǐng)求；
　　b .被查詢節(jié)點(diǎn)收到請(qǐng)求之后，將從自己的k-桶中找出自己所知道的距離查詢目標(biāo)ID最近的若干個(gè)節(jié)點(diǎn)，并返回給發(fā)起者；
　　c. 發(fā)起者在收到這些返回信息之后，再次從自己目前所有已知的距離目標(biāo)較近的節(jié)點(diǎn)中挑選出若干沒有請(qǐng)求過的，并重復(fù)步驟1；
　　d. 上述步驟不斷重復(fù)，直至無法獲得比查詢者當(dāng)前已知的k個(gè)節(jié)點(diǎn)更接近目標(biāo)的活動(dòng)節(jié)點(diǎn)為止。
　　e. 在查詢過程中，沒有及時(shí)響應(yīng)的節(jié)點(diǎn)將立即被排除；查詢者必須保證最終獲得的k個(gè)最近節(jié)點(diǎn)都是活動(dòng)的。

　　簡(jiǎn)單總結(jié)一下上述過程，實(shí)際上它跟我們?nèi)粘Ｉ钪腥フ夷骋粋€(gè)人打聽某件事是非常相似的，比方說你是個(gè)Agent Smith，想找小李(key)問問他的手機(jī)號(hào)碼(value)，但你事先并不認(rèn)識(shí)他，你首先肯定會(huì)去找你所認(rèn)識(shí)的和小李在同一個(gè)公司工作的人，比方說小趙，然后小趙又會(huì)告訴你去找與和小李在同一部門的小劉，然后小劉又會(huì)進(jìn)一步告訴你去找和小李在同一個(gè)項(xiàng)目組的小張，最后，你找到了小張，喲，正好小李出差去了(節(jié)點(diǎn)下線了)，但小張恰好知道小李的號(hào)碼(cache)，這樣你總算找到了所需的信息。在節(jié)點(diǎn)查找的過程中，“節(jié)點(diǎn)距離的遠(yuǎn)近”實(shí)際上與上面例子中“人際關(guān)系的密切程度”所代表的含義是一樣的。

　　最后說說上述查詢過程的局限性：Kad網(wǎng)絡(luò)并不適合應(yīng)用于模糊搜索，如通配符支持、部分查找等場(chǎng)合，但對(duì)于文件共享場(chǎng)合來說，基于關(guān)鍵詞的精確查找功能已經(jīng)基本足夠了(值得注意的是，實(shí)際上我們只要對(duì)上述查找過程稍加改進(jìn)，并可以令其支持基于關(guān)鍵詞匹配的布爾條件查詢，但仍不夠優(yōu)化)。這個(gè)問題反映到eMule的應(yīng)用層面來，它直接說明了文件共享時(shí)其命名的重要性所在，即，文件名中的關(guān)鍵詞定義得越明顯，則該文件越容易被找到，從而越有利于其在P2P網(wǎng)絡(luò)中的傳播；而另一方面，在eMule中，每一個(gè)共享文件均可以擁有自己的相關(guān)注釋，而Comment的重要性還沒有被大家認(rèn)識(shí)到：實(shí)際上，這個(gè)文件注釋中的關(guān)鍵詞也可以直接被利用來替代文件名關(guān)鍵詞，從而指導(dǎo)和方便用戶搜索，尤其是當(dāng)文件名本身并沒有體現(xiàn)出關(guān)鍵詞的時(shí)候。
　　8. 在Kad網(wǎng)絡(luò)中如何存儲(chǔ)和搜索某特定的<key, value>條目?

　　從本質(zhì)上而言，存儲(chǔ)、搜索某特定<key, value>條目的問題實(shí)際上就是節(jié)點(diǎn)查找的問題。當(dāng)需要在Kad網(wǎng)絡(luò)中存儲(chǔ)一個(gè)條目時(shí)，可以首先通過節(jié)點(diǎn)查找算法找到距離key最近的k個(gè)節(jié)點(diǎn)，然后再通知它們保存<key, value>條目即可。而搜索條目的過程則與節(jié)點(diǎn)查詢過程也是基本類似，由搜索發(fā)起方以迭代方式不斷查詢距離key較近的節(jié)點(diǎn)，一旦查詢路徑中的任一節(jié)點(diǎn)返回了所需查找的value，整個(gè)搜索的過程就結(jié)束。為提高效率，當(dāng)搜索成功之后，發(fā)起方可以選擇將搜索到的條目存儲(chǔ)到查詢路徑的多個(gè)節(jié)點(diǎn)中，作為方便后繼查詢的cache；條目cache的超時(shí)時(shí)間與節(jié)點(diǎn)-key之間的距離呈指數(shù)反比關(guān)系。
　　9. 一個(gè)新節(jié)點(diǎn)如何首次加入Kad網(wǎng)絡(luò)?

　　當(dāng)一個(gè)新節(jié)點(diǎn)首次試圖加入Kad網(wǎng)絡(luò)時(shí)，它必須做三件事，其一，不管通過何種途徑，獲知一個(gè)已經(jīng)加入Kad網(wǎng)絡(luò)的節(jié)點(diǎn)信息(我們可以稱之為節(jié)點(diǎn)I)，并將其加入自己的k-buckets；其二，向該節(jié)點(diǎn)發(fā)起一次針對(duì)自己ID的節(jié)點(diǎn)查詢請(qǐng)求，從而通過節(jié)點(diǎn)I獲取一系列與自己距離鄰近的其他節(jié)點(diǎn)的信息；最后，刷新所有的k-bucket，保證自己所獲得的節(jié)點(diǎn)信息全部都是新鮮的。

　　參考文獻(xiàn)
　　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

it知識(shí)庫(kù)：eMule中的分布式哈希表技術(shù): Kademlia，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。