史建燾，張宏莉

（哈爾濱工業(yè)大學(xué)計算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心 哈爾濱150001）

1 引言

分布式散列表(distributed Hash tables,DHT)技術(shù)的出現(xiàn)擴(kuò)展了對等網(wǎng)絡(luò)用戶的規(guī)模，徹底釋放了用戶的共享下載需求。相比之前的P2P網(wǎng)絡(luò)，DHT網(wǎng)絡(luò)具有可擴(kuò)展性好、可靠性高等優(yōu)點，但是網(wǎng)絡(luò)節(jié)點的異構(gòu)性也給這一技術(shù)的發(fā)展提出了許多挑戰(zhàn)。作為為數(shù)不多的在實際環(huán)境下實現(xiàn)的DHT系統(tǒng)，利用Kademlia協(xié)議[1]的eMule軟件的KAD網(wǎng)絡(luò)已經(jīng)擁有了數(shù)以百萬的用戶群，在Internet上產(chǎn)生了一定的影響。KAD協(xié)議是基于二進(jìn)制異或運(yùn)算（XOR）度量距離的DHT協(xié)議，每個KAD節(jié)點擁有一個128位的唯一標(biāo)識，所有節(jié)點構(gòu)成一個二叉樹結(jié)構(gòu)。通過若干操作實現(xiàn)對數(shù)據(jù)項映射的存儲和獲取。一個健壯的DHT系統(tǒng)中，不同節(jié)點應(yīng)該以很高的概率分配到相同數(shù)量的目標(biāo)對象，從而保證系統(tǒng)的高可靠性和容錯性。然而，由于應(yīng)用環(huán)境的特殊性和網(wǎng)絡(luò)節(jié)點的異構(gòu)性，實際系統(tǒng)中并沒有真正實現(xiàn)節(jié)點間負(fù)載的均衡性，KAD網(wǎng)絡(luò)同樣如此。本文通過測量實驗發(fā)現(xiàn)由于關(guān)鍵詞使用頻率的差異，導(dǎo)致KAD網(wǎng)絡(luò)中以關(guān)鍵詞作為鍵值的文件索引負(fù)載在不同節(jié)點上的分配是不均衡的，這嚴(yán)重限制了KAD網(wǎng)絡(luò)的擴(kuò)展性和可用性。如何提高KAD網(wǎng)絡(luò)這方面的負(fù)載均衡性是本文的研究重點。

負(fù)載均衡作為DHT系統(tǒng)重要的性能評價指標(biāo)已經(jīng)成為了當(dāng)前研究的熱點，大多數(shù)研究工作都是以ID空間作為研究對象的[2]。認(rèn)為理想狀態(tài)下，DHT系統(tǒng)的負(fù)載均衡是指每個節(jié)點負(fù)責(zé)管理的ID空間應(yīng)該根據(jù)其軟硬件承載能力按比例分配。解決這類負(fù)載均衡問題的辦法多是采用虛擬服務(wù)器的方式，該方法最初由參考文獻(xiàn)[3]提出，考慮了節(jié)點軟硬件能力的差異以及網(wǎng)絡(luò)結(jié)構(gòu)的異構(gòu)性，將一個物理節(jié)點虛擬為在ID空間內(nèi)獨立的幾個邏輯節(jié)點，并使系統(tǒng)中負(fù)責(zé)某一ID空間存儲任務(wù)的節(jié)點數(shù)大致相當(dāng)。但該方法增加了網(wǎng)絡(luò)的波動性，導(dǎo)致網(wǎng)絡(luò)維護(hù)代價增大。參考文獻(xiàn)[4]對虛擬服務(wù)器方法進(jìn)行了改進(jìn)，大幅度提高了該方法的性能。參考文獻(xiàn)[5]研究了具有超級節(jié)點的層次化DHT系統(tǒng)下的負(fù)載均衡問題。以上研究都是以負(fù)載在整個ID空間上的均勻分布作為假設(shè)的，而本文的研究以參考文獻(xiàn)[6]的研究為基礎(chǔ)，認(rèn)為實際KAD系統(tǒng)中文件索引信息在ID空間上的分布是不均勻的，參考文獻(xiàn)[6]提出的解決方法是通過存儲和搜索過程中過濾無用關(guān)鍵詞來防止某一ID子空間負(fù)載過重。但是，實際應(yīng)用中很難提供完備的無用關(guān)鍵詞集合，單獨依靠這種方法很難完全解決文件索引的負(fù)載均衡問題。本文從KAD協(xié)議本身出發(fā)，在文件索引發(fā)布和搜索階段對節(jié)點區(qū)域的負(fù)載進(jìn)行控制，引入多重目標(biāo)ID的方法分散熱點關(guān)鍵詞的負(fù)載，使系統(tǒng)在全局范圍內(nèi)達(dá)到負(fù)載均衡，從而保證KAD系統(tǒng)的健壯性和可用性。

2 負(fù)載分布測量

2.1 KAD資源發(fā)布機(jī)制

KAD的資源發(fā)布過程分為文件索引信息發(fā)布和源節(jié)點發(fā)布兩部分。本文的研究內(nèi)容僅涉及第一個發(fā)布過程：文件索引信息的發(fā)布，本節(jié)僅對這一過程做簡單介紹。文件索引信息的發(fā)布涉及3個基本操作。

（1）候選節(jié)點收集（lookup）

對于給定的目標(biāo)鍵值 （目標(biāo)ID），lookup操作通過鄰居節(jié)點之間的并發(fā)迭代查找，提供ID空間中可能負(fù)責(zé)目標(biāo)ID的一些候選節(jié)點。其中初始節(jié)點并發(fā)查找分支數(shù)為α，后繼節(jié)點并發(fā)查找分支數(shù)為β。除了初始節(jié)點采用α=3路并發(fā)查找外，后繼節(jié)點會根據(jù)不同的操作目的選擇并發(fā)迭代分支數(shù)。如果后續(xù)操作是發(fā)布（publish）操作，采用β=4路并發(fā)查找；后續(xù)操作是搜索（search）操作，則采用β=2路并發(fā)查找。當(dāng)查找收斂到發(fā)現(xiàn)不了新節(jié)點時，Lookup操作停止，去掉和目標(biāo)ID的公共前綴小于8的節(jié)點后，返回一個候選節(jié)點列表（candidate list）。

（2）發(fā)布

在最新的eMule實現(xiàn)中，選擇距離目標(biāo)ID最近的10個節(jié)點，通過Kademlia2_publish_key_req消息將映射發(fā)布到這些目的節(jié)點上。目的節(jié)點會返回Kademlia2_publish_res消息，消息包含一個代表當(dāng)前目的節(jié)點負(fù)載的load標(biāo)識，其值表示0～100的百分?jǐn)?shù)，KAD網(wǎng)絡(luò)中每個節(jié)點的負(fù)載上限是50 000。也就是說，如果load=100，表示目的節(jié)點上存儲的索引信息已經(jīng)達(dá)到50 000條，繼續(xù)在該節(jié)點上發(fā)布的索引信息會被丟棄。

（3）搜索

選擇距離目標(biāo)ID最近的候選節(jié)點，通過Kademlia2_search_key_req消息，請求候選節(jié)點提供有關(guān)目標(biāo)關(guān)鍵詞的文件索引。候選節(jié)點收到該消息后，隨機(jī)返回最多300個符合條件的索引項，并通過Kademlia2_publish_res消息返回。初始節(jié)點在收集滿300個結(jié)果或者搜索超時后，立即停止搜索操作。

2.2 測量系統(tǒng)的設(shè)計

為了獲取文件索引負(fù)載的分布情況，需要對KAD網(wǎng)絡(luò)進(jìn)行測量分析。出于不同的目的，本文的測量系統(tǒng)采用主動測量和被動測量兩種方法。圖1是整個測量系統(tǒng)的示意。

（1）主動測量

主動測量方法包括KAD爬蟲和基于主動測量的虛擬客戶端。其中KAD爬蟲負(fù)責(zé)搜索網(wǎng)絡(luò)中一定ID空間范圍內(nèi)的活動節(jié)點，是通過構(gòu)造針對一系列特殊目標(biāo)ID的lookup操作，獲取目標(biāo)節(jié)點部分或全部路由表的方法實現(xiàn)的，具體實現(xiàn)過程類似參考文獻(xiàn)[7]。虛擬客戶端負(fù)責(zé)并發(fā)Kademlia2_publish_key_req請求，收集活動節(jié)點Kademlia2_publish_res消息中的load負(fù)載標(biāo)識以及測量lookup操作得到的候選節(jié)點與目標(biāo)ID的距離分布。

（2）被動測量

被動測量通過設(shè)計虛擬客戶段，將其節(jié)點ID設(shè)置為與目標(biāo)ID非常接近的值，然后插入KAD網(wǎng)絡(luò)，接收來自其他節(jié)點的索引發(fā)布和關(guān)鍵詞搜索請求，統(tǒng)計和分析流量的分布情況和自身負(fù)載變化規(guī)律。

2.3 測量結(jié)果

（1）負(fù)載分布

KAD系統(tǒng)中負(fù)責(zé)某一關(guān)鍵詞的節(jié)點在ID空間上是相鄰的，本文以ID值的8位公共前綴來標(biāo)記對應(yīng)的ID子區(qū)間。通過測量實驗統(tǒng)計了負(fù)責(zé)關(guān)鍵詞the(0xe3)、China(0xe6)、dream(0xca)、Baidu(0xe4)的4個ID子區(qū)間內(nèi)的節(jié)點負(fù)載狀況。具體過程是通過爬蟲獲得ID子空間內(nèi)的所有節(jié)點，由索引發(fā)布模塊向所有節(jié)點發(fā)送Kademlia2_publish_key_req消息，收集節(jié)點回饋消息中攜帶的load負(fù)載標(biāo)識。實驗發(fā)現(xiàn)最近節(jié)點一般與關(guān)鍵詞ID有23～24個相同公共前綴，從最近節(jié)點開始，以公共前綴數(shù)排序統(tǒng)計了節(jié)點的平均負(fù)載情況。結(jié)果如圖2所示，關(guān)鍵詞the和China所在子區(qū)間節(jié)點負(fù)載最重，距離較遠(yuǎn)的節(jié)點也有較大負(fù)載，這是因為這兩個關(guān)鍵詞屬于高頻關(guān)鍵詞。關(guān)鍵詞Baidu所在區(qū)間的節(jié)點負(fù)載較輕，只有距離關(guān)鍵詞ID最近的一些節(jié)點有一些負(fù)載，較遠(yuǎn)節(jié)點幾乎沒有負(fù)載。由此可見，以關(guān)鍵詞為鍵值的文件索引信息在KAD網(wǎng)絡(luò)的不同子區(qū)間的分布是不均勻的，存在一些超負(fù)荷區(qū)域。

（2）流量統(tǒng)計

為了發(fā)現(xiàn)負(fù)載強(qiáng)度對網(wǎng)絡(luò)中節(jié)點性能的影響，通過被動測量實驗統(tǒng)計了不同子區(qū)間內(nèi)，節(jié)點在單位時間接收到的消息數(shù)。測量節(jié)點ID分別被設(shè)置為與關(guān)鍵詞the、dream和盜夢空間的ID，即成為網(wǎng)絡(luò)中距離目標(biāo)關(guān)鍵詞最近的節(jié)點。表1的結(jié)果是當(dāng)節(jié)點路由表達(dá)到穩(wěn)定狀態(tài)后的1 h內(nèi)收到的消息數(shù)?？梢?，負(fù)責(zé)關(guān)鍵詞the的節(jié)點接收到的消息數(shù)最多，其中發(fā)布消息將近是查詢消息的10倍，而其他兩個關(guān)鍵詞發(fā)布消息僅是查詢消息的3～4倍?？梢园l(fā)現(xiàn)，大量的發(fā)布消息會集中在負(fù)責(zé)常用詞的ID空間，位于這一區(qū)域的節(jié)點常常付出更多的通信開銷。

表1 不同ID空間流量統(tǒng)計結(jié)果

（3）候選節(jié)點正確性

候選節(jié)點收集過程對KAD網(wǎng)絡(luò)的索引發(fā)布和搜索非常重要，正確的候選節(jié)點可以提高搜索命中率。理論上如果節(jié)點在ID空間上的分布是均勻的，一個具有大約400萬（≈222）個節(jié)點的網(wǎng)絡(luò)，相鄰節(jié)點的距離約為2128-22，也就是說相鄰節(jié)點ID公共前綴的長度約為22位。筆者通過爬蟲獲得了網(wǎng)絡(luò)中距離某一關(guān)鍵詞ID最近的10個節(jié)點，與真正客戶端候選節(jié)點收集過程得到的結(jié)果進(jìn)行了對比。結(jié)果見表2，主動測量實驗的結(jié)果與理論分析值很接近；而實際客戶端由于搜索并發(fā)數(shù)的限制，除了前幾個節(jié)點，并沒有得到所有最近的10個節(jié)點，也就是說實際客戶端得到的后幾個候選節(jié)點動態(tài)性較大。對于高頻關(guān)鍵詞，由于索引信息量很大，大量距離較遠(yuǎn)的節(jié)點也會分配到一些索引信息，這就大大降低了其他節(jié)點的搜索命中率。為了改進(jìn)KAD網(wǎng)絡(luò)這種索引信息分配不均衡問題，提高搜索過程中索引信息的命中率，本文對索引信息的發(fā)布和搜索過程做了一定的改進(jìn)。

表2 候選節(jié)點正確性測量結(jié)果

3 改進(jìn)的索引信息發(fā)布策略

3.1 發(fā)布過程

改進(jìn)的資源發(fā)布過程如算法1所示。先通過lookup過程選擇離關(guān)鍵詞ID最近的10個節(jié)點加入候選隊列。與傳統(tǒng)的發(fā)布過程不同，改進(jìn)算法從隊列的第10個節(jié)點開始前向分3輪選擇發(fā)布節(jié)點。統(tǒng)計前兩輪節(jié)點返回的負(fù)載值，如果大于系統(tǒng)預(yù)設(shè)的該節(jié)點最大負(fù)載閾值，則在輪次內(nèi)累加負(fù)載值。如果該累加值超過最大誤差值D=5%，則表明負(fù)責(zé)該關(guān)鍵詞的節(jié)點區(qū)間負(fù)載過重。改進(jìn)算法在下一輪將通過lookup過程選擇新的節(jié)點區(qū)間發(fā)布該關(guān)鍵詞信息，ID偏移量L=2120，即散列值的8位二進(jìn)制公共前綴加1。最多會有以hash、hash+L、hash+2L為中心的3個ID空間負(fù)責(zé)負(fù)載量較大的關(guān)鍵詞，通過更多的節(jié)點分擔(dān)了負(fù)載。在最大負(fù)載MaxLoad的參數(shù)選擇上，對于負(fù)責(zé)原散列hash的第10到第7個節(jié)點，MaxLoad=45%；第6到第4個節(jié)點，MaxLoad=65%；負(fù)責(zé)散列hash+L的第6到第4個節(jié)點，MaxLoad=35%。

算法1：m-Publish(hash)

{C0,C1,…,C9}←Lookup(hash);

ContactSet←{C9,C8,C7,C6};

for round←0 to 2 do

SumLoad=0;

for p∈ContactSet do

p.load←publish(p);

if round<2 then

SumLoad+=Max(p.load-p.MaxLoad,0);

if SumLoad>D then

{C0,C1,…,C9}←Lookup(hash+L));

if round=0 then

ContactSet←{C3,C4,C5};

if round=1 then

ContactSet←{C0,C1,C2};

3.2 搜索過程

改進(jìn)的索引搜索過程如算法2所示。同樣通過lookup過程選擇10個節(jié)點加入候選隊列，第一輪先從后4個節(jié)點中隨機(jī)選擇一個節(jié)點發(fā)出搜索請求，如果該節(jié)點返回的索引信息超過預(yù)設(shè)的閾值rMax，則再通過lookup過程選擇hash+L空間內(nèi)的節(jié)點加入候選隊列，并且將rMax值增加150；否則，繼續(xù)向前選擇節(jié)點。第二輪選擇新隊列的后3個節(jié)點隨機(jī)發(fā)送請求，過程與第一輪類似。這樣最多會把hash、hash+L、hash+2L的3個ID空間內(nèi)的一定節(jié)點加入候選隊列。從第3輪開始同傳統(tǒng)算法相同，選擇最近的候選節(jié)點進(jìn)行搜索，這樣保證了算法的搜索效率。對負(fù)載較大的關(guān)鍵詞，會更多地從較遠(yuǎn)節(jié)點獲得索引信息，從而保證了更多的返回值。在MaxRefer參數(shù)選擇上，對負(fù)責(zé)原散列hash的第10到第7個節(jié)點，MaxRefer=150；第6到第4個節(jié)點，MaxRefer=200；負(fù)責(zé)散列hash+L的第6到 第4個節(jié)點，MaxRefer=100，第3到第1個節(jié)點，MaxRefer=150。

算法2：m-Search(hash)

{C0,C1,…,C9}←Lookup(hash);

Candidates←{C0,C1,…,C9};

ContactSet←{C9,C8,C7,C6};

round←0;rMax←300;

while references.size()

if round<2 then

p←ContactSet.getRandom();

R←search(p);references.add(R);

if R.size()>p.MaxRefer then

{C0,C1,…,C9}←Lookup(hash+L);

rMax+=150;

if round=0 then

Candidates.add({C0,C1,…,C5});

ContactSet←{C0,C1,…,C5};

if round=1 then

Candidates.add{C0,C1,C2};

ContactSet←{C0,C1,C2};

else

p←Candidates.getFirst();

.add(search(p));

Candidates.remove(p);

retrun references;

4 仿真實驗

本節(jié)通過仿真實驗驗證前面所提出的方法，仿真程序以一個離散事件模擬引擎為基礎(chǔ)，實現(xiàn)了基本的eMule的KAD協(xié)議。為提高仿真效率，節(jié)點空間的規(guī)模為3個連續(xù)的具有8位公共ID前綴的子空間。節(jié)點數(shù)目按照真實環(huán)境的比例分配，假設(shè)網(wǎng)絡(luò)已經(jīng)達(dá)到穩(wěn)定狀態(tài)，每個子空間保證有15 000個在線節(jié)點，節(jié)點上下線頻率以采集到的真實環(huán)境下的數(shù)據(jù)為基礎(chǔ)。仿真實驗以一個給定的關(guān)鍵詞生成文件索引。和真實協(xié)議一樣，發(fā)布成功后每個索引在存儲節(jié)點上保留24 h的模擬時鐘時間。通過一個模擬客戶端以每秒20個索引的頻率在KAD網(wǎng)絡(luò)發(fā)布文件索引。索引量基本飽和后，通過搜索過程提取當(dāng)前系統(tǒng)中的文件索引，客戶端分別采用傳統(tǒng)算法和改進(jìn)算法進(jìn)行發(fā)布和搜索操作。

筆者根據(jù)節(jié)點ID值對每個子空間內(nèi)的節(jié)點進(jìn)行了分組，組間ID距離相等，每組大概有8個真實節(jié)點，由于大量文件索引發(fā)布在距目標(biāo)ID較近的節(jié)點中，每個子空間只抽取了最近的32個分組并記錄下節(jié)點的平均負(fù)載。實驗結(jié)果如圖3所示，當(dāng)客戶端采用傳統(tǒng)方法時，大量節(jié)點出現(xiàn)了過飽和現(xiàn)象，其中距離目標(biāo)ID最近的2個分組中，所有節(jié)點的負(fù)載率達(dá)到了100%，大量文件索引發(fā)布在距目標(biāo)ID較遠(yuǎn)的節(jié)點上。而采用了改進(jìn)的索引發(fā)布算法后，目標(biāo)子空間的文件負(fù)載大大降低，基本達(dá)到了算法所控制的閾值，并且相鄰子空間的部分節(jié)點也分擔(dān)了大量的負(fù)載。模擬實驗還記錄了當(dāng)索引發(fā)布達(dá)到飽和后，單位時間內(nèi)能搜索到的最新文件的數(shù)量。由于大量候選節(jié)點達(dá)到了飽和狀態(tài)，很多文件索引在傳統(tǒng)協(xié)議下無法被成功發(fā)布和提取，實驗獲得的最新文件的提取率僅為18.7%；而采用改進(jìn)方法后，文件的提取率可以達(dá)到89.3%。由此可見，改進(jìn)的索引發(fā)布和搜索算法，能夠大幅提高KAD網(wǎng)絡(luò)的健壯性和文件發(fā)布效率。

5 結(jié)束語

基于DHT結(jié)構(gòu)的P2P網(wǎng)絡(luò)的發(fā)展給當(dāng)今的互聯(lián)網(wǎng)注入了活力，為用戶提供了更多的便利和實惠。但是，由于應(yīng)用環(huán)境的特殊性和網(wǎng)絡(luò)節(jié)點的異構(gòu)性，大多數(shù)DHT網(wǎng)絡(luò)都存在著各種負(fù)載不均衡問題，需要進(jìn)一步的優(yōu)化和改進(jìn)。本文通過測量實驗發(fā)現(xiàn)了擁有大量用戶群的eMule的KAD網(wǎng)絡(luò)下，索引資源在ID空間上的分布是不均勻的，網(wǎng)絡(luò)中存在的一些負(fù)載過重節(jié)點會威脅到用戶對系統(tǒng)的正常使用。為了解決這一問題，本文提出了一種基于多重目標(biāo)ID的索引發(fā)布和搜索機(jī)制，仿真實驗表明該方法能夠有效地提高索引負(fù)載分配的均衡性。

1 Maymounkov P,Mazieres D.Kademlia:a peer-to-peer information system based on the XOR metric.Proceedings of the International Workshop on Peer-to-Peer Systems,Cambrige,USA,2002:53～65

2 Godfrey P B,Stoica I.Heterogeneity and load balance in distributed Hash tables.Proceedings of IEEE INFOCOM,Miami,FL,USA,2005

3 Rao A，Lakshminaraynan K,Surana S,et al.Load balancing in structured P2P systems.Proceedings of the 2nd International Workshop Peer-to-Peer Systems,Berkeley,USA,2003:68～79

4 Hung-Chang Hsiao,Che-Wei Chang.A symmetric load balancing algorithm with performance guarantees for distributed hash tables.IEEE Transactions on Computers,2012(1)

5 張宇翔，張宏科.一種層次結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的負(fù)載均衡方法.計算機(jī)學(xué)報，2010，33（9）

6 Steiner M,Effelsberg W,En-Najjary T,et al.Load reduction in the KAD peer-to-peer system.Proceedings of the Fifth International Workshop on Databases,Information Systems and Peer-to-Peer Computing,Austria,2007

7 Steiner M,En-Najjary T,Biersack E W.Long term study of peer behavior in the KAD DHT.IEEE/ACM Transactions on Networking,2009,17(5):1 371～1 384