KAD網絡負載均衡技術研究*

史建燾，張宏莉

（哈爾濱工業大學計算機網絡與信息安全技術研究中心 哈爾濱150001）

1 引言

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

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

2 負載分布測量

2.1 KAD資源發布機制

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

（1）候選節點收集（lookup）

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

（2）發布

在最新的eMule實現中，選擇距離目標ID最近的10個節點，通過Kademlia2_publish_key_req消息將映射發布到這些目的節點上。目的節點會返回Kademlia2_publish_res消息，消息包含一個代表當前目的節點負載的load標識，其值表示0～100的百分數，KAD網絡中每個節點的負載上限是50 000。也就是說，如果load=100，表示目的節點上存儲的索引信息已經達到50 000條，繼續在該節點上發布的索引信息會被丟棄。

（3）搜索

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

2.2 測量系統的設計

為了獲取文件索引負載的分布情況，需要對KAD網絡進行測量分析。出于不同的目的，本文的測量系統采用主動測量和被動測量兩種方法。圖1是整個測量系統的示意。

（1）主動測量

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

（2）被動測量

被動測量通過設計虛擬客戶段，將其節點ID設置為與目標ID非常接近的值，然后插入KAD網絡，接收來自其他節點的索引發布和關鍵詞搜索請求，統計和分析流量的分布情況和自身負載變化規律。

2.3 測量結果

（1）負載分布

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

（2）流量統計

為了發現負載強度對網絡中節點性能的影響，通過被動測量實驗統計了不同子區間內，節點在單位時間接收到的消息數。測量節點ID分別被設置為與關鍵詞the、dream和盜夢空間的ID，即成為網絡中距離目標關鍵詞最近的節點。表1的結果是當節點路由表達到穩定狀態后的1 h內收到的消息數。可見，負責關鍵詞the的節點接收到的消息數最多，其中發布消息將近是查詢消息的10倍，而其他兩個關鍵詞發布消息僅是查詢消息的3～4倍。可以發現，大量的發布消息會集中在負責常用詞的ID空間，位于這一區域的節點常常付出更多的通信開銷。

表1 不同ID空間流量統計結果

（3）候選節點正確性

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

表2 候選節點正確性測量結果

3 改進的索引信息發布策略

3.1 發布過程

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

改進的索引搜索過程如算法2所示。同樣通過lookup過程選擇10個節點加入候選隊列，第一輪先從后4個節點中隨機選擇一個節點發出搜索請求，如果該節點返回的索引信息超過預設的閾值rMax，則再通過lookup過程選擇hash+L空間內的節點加入候選隊列，并且將rMax值增加150；否則，繼續向前選擇節點。第二輪選擇新隊列的后3個節點隨機發送請求，過程與第一輪類似。這樣最多會把hash、hash+L、hash+2L的3個ID空間內的一定節點加入候選隊列。從第3輪開始同傳統算法相同，選擇最近的候選節點進行搜索，這樣保證了算法的搜索效率。對負載較大的關鍵詞，會更多地從較遠節點獲得索引信息，從而保證了更多的返回值。在MaxRefer參數選擇上，對負責原散列hash的第10到第7個節點，MaxRefer=150；第6到第4個節點，MaxRefer=200；負責散列hash+L的第6到 第4個節點，MaxRefer=100，第3到第1個節點，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 仿真實驗

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

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

5 結束語

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

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 張宇翔，張宏科.一種層次結構化P2P網絡中的負載均衡方法.計算機學報，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