[發明專利]分布式哈希表網絡的負載均衡實現方法及裝置

有效

• 申請號: 201010522803.5
• 申請日: 2010-10-27
• 公開（公告）號: CN102457428A
• 公開（公告）日: 2012-05-16
• 發明（設計）人: 胡學川;李漓春
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/08
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 余剛;吳孟秋

技術領域

本發明涉及通信領域，具體而言，涉及一種分布式哈希表(Distributed?Hash?Table，簡稱為DHT)網絡的負載均衡實現方法及裝置。

背景技術

目前，分布式哈希表(DHT)已成為點對點(P2P)疊加網絡的主要組織形式，其存儲負載均衡主要使用虛擬標識的方法實現。在分布式哈希疊加網絡中同時具有節點ID與虛擬標識兩種不同屬性的標識。其中，節點ID用于區分不同節點，維護分布式哈希表疊加網絡；虛擬標識用于將哈希表空間分割成多個區間并分配到節點。在一個分布式哈希表疊加網絡中，每個節點ID都不相同，每個虛擬標識也都不相同。允許出現節點ID相同于虛擬標識的情況。疊加網絡中根據全部節點的全部虛擬標識和一定的分割規則，將哈希表空間分為多個區間。區間數量與虛擬標識數量等同，每個區間與一個虛擬標識互相關聯。哈希表區間由與其關聯的虛擬標識所屬的節點負責。由于每個節點擁有多個虛擬標識，因此，每個節點需要負責多個哈希表區間。而疊加網絡中的每個數據資源被分配一個唯一的資源標識，若某數據資源的資源標識位于某一哈希表區間內，該數據資源由與負責該哈希表區間的虛擬標識所在的節點保存。這樣，疊加網絡中的所有節點ID與虛擬標識組成兩個不同的邏輯環路。虛擬標識將哈希表空間進行更精細的劃分，每個虛擬標識負責相應的哈希塊，資源標識落在該哈希塊內的數據資源由該虛擬標識負責保存，從而起到提升網絡負載均衡效果的作用。

如圖1所示，假設哈希空間為0-63被12個虛擬標識均等分割成12份。網絡中有A、B、C和D四個節點，四個節點分別具有各自的節點ID：N1、N9、N28、N49，并且假設這四個節點能力相同。則每個節點均具有三個虛擬標識，如節點B具有三個虛擬標識：P8、P28和P43。資源對象根據資源標識與虛擬標識的關系由相應的虛擬標識負責保存(如資源標識為K5的，就由虛擬標識P8負責)。其中，如表1所示，節點B的三個虛擬標識所負責的哈希塊分別為：(1，8]、(23，28]、(38，43]，資源標識在此空間的資源屬于節點B負責。從而可以得到在該種負載均衡方法下，四個節點中存儲的數據資源空間都是15，具體如表1所示。由于資源標識在整個哈希空間是均勻分布的，因此，每個節點所負責的數據資源是均衡的。

表1.

發明人發現，在相關技術中，由于虛擬標識負載空間是等份的，而節點理論負載空間值很難正好等于X個虛擬標識負責空間之和。因此節點實際負責空間比理論負責空間會有一定區別，當網絡規模節點較少時，節點理論負責空間比較大，節點實際負責空間多/少一個虛擬標識，負載均衡度最大偏差值還是比較小的。但隨著業務的不斷發展，節點的規模不斷擴大，每個節點的理論負責空間不斷變小，這時如果節點實際負責空間多一個虛擬標識，每個虛擬標識對應的負載空間是固定的，其負載均衡度最大差值比較大，從而將導致節點的負載不均衡度超過負載不均衡度閾值，節點間的負載不均衡。

發明內容

本發明的主要目的在于提供一種DHT網絡的負載均衡實現方案，以至少解決上述由于節點增加而導致DHT網絡的節點間的負載不均衡的問題。

根據本發明的一個方面，提供了一種分布式哈希表網絡的負載均衡實現方法，包括：將所述分布式哈希表網絡中的已分配給各個節點的N個第一虛擬標識中各個第一虛擬標識對應的負載空間均分為M份，使用M×N個第二虛擬標識對均分后的各份負載空間進行標識，其中，M和N為自然數，且M≥2；將M×N個所述第二虛擬標識分配給當前所述DHT網絡中的各個節點，由各個節點負責分配給其的所述第二虛擬標識對應的負載空間。

根據本發明的另一方面，提供了一種DHT網絡的負載均衡實現裝置，包括：分裂模塊，用于將所述DHT網絡中已分配給各個節點的N個第一虛擬標識中各個所述第一虛擬標識對應的負載空間均分為M份，使用M×N個第二虛擬標識對均分后的各份負載空間進行標識，其中，M和N為自然數，且M≥2；分配模塊，用于將M×N個所述第二虛擬標識分配給當前所述DHT網絡的各個節點，由各個節點負責分配給其的所述第二虛擬標識對應的負載空間。

通過本發明，對已分配給各個節點的虛擬標識進行分裂，使每個虛擬標識對應的負載空間減少，從而使得每個節點的理論負載空間與實際的負載空間的差值減少，從而保證了DHT網絡中各個節點的負載均衡。

附圖說明

此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發明的示意性實施例及其說明用于解釋本發明，并不構成對本發明的不當限定。在附圖中：