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

有效

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

1.一種分布式哈希表DHT網絡的負載均衡實現方法，其特征在于，包括：

將所述DHT網絡中的已分配給各個節點的N個第一虛擬標識中各個第一虛擬標識對應的負載空間均分為M份，使用M×N個第二虛擬標識對均分后的各份負載空間進行標識，其中，M和N為自然數，且M≥2；

將M×N個所述第二虛擬標識分配給當前所述DHT網絡中的各個節點，由各個節點負責分配給其的所述第二虛擬標識對應的負載空間。

2.根據權利要求1所述的方法，其特征在于，在各個所述第一虛擬標識對應的負載空間均分為M份之前，所述方法還包括：所述DHT網絡中一個節點的負載不均衡度超過負載不均衡度閾值。

3.根據權利要求2所述的方法，其特征在于，所述將M×N個所述第二虛擬標識分配當前所述DHT網絡中的各個節點包括：

根據當前所述DHT網絡中各個節點的負載不均衡度，對各個節點負責的所述第二虛擬標識的數量進行調整，使負載不均衡度超過負載不均衡度閾值的節點的負載不均衡度下降。

4.根據權利要求2所述的方法，其特征在于，所述將M×N個所述第二虛擬標識分配當前所述DHT網絡中的各個節點包括：

新節點加入所述DHT網絡；

根據所述新節點的能力，計算所述新節點應該負責的所述第二虛擬標識的數量；

將所述DHT網絡中負責的所述第二虛擬標識數超過理論值的節點負責的部分所述第二虛擬標識分配給所述新節點負責，使所述新節點負責的所述第二虛擬標識的數量接近所述新節點應該負責的所述第二虛擬標識的數量。

5.根據權利要求1所述的方法，其特征在于，在各個所述第一虛擬標識對應的負載空間均分為M份之前，所述方法還包括：新節點加入所述DHT網絡。

6.根據權利要求5所述的方法，其特征在于，所述將M×N個所述第二虛擬標識分配各個所述節點包括：

根據所述新節點的能力，計算所述新節點應該負責的所述第二虛擬標識的數量；

將所述DHT網絡中負責的所述第二虛擬標識數超過理論值的節點負責的部分所述第二虛擬標識分配給所述新節點負責，使所述新節點負責的所述第二虛擬標識的數量接近所述新節點應該負責的所述第二虛擬標識的數量。

7.根據權利要求6所述的方法，其特征在于，將所述DHT網絡中負責的所述第二虛擬標識數超過理論值的節點負責的部分所述第二虛擬標識分配給所述新節點負責包括：

根據所述DHT網絡中各個節點的能力，計算加入所述新節點后各個所述節點應該負責的所述第二虛擬標識的理論值；

判斷各個所述節點當前負責的所述第二虛擬標識的數量是否超過該節點的所述理論值，如果是，則將該節點負責的所有所述第二虛擬標識中隨機取超出該理論值部分的所述第二虛擬標識分配給所述新節點。

8.根據權利要求1至7中任一項所述的方法，其特征在于，在所述DHT網絡初建時，所述N根據所述DHT網絡的節點規劃及負載不均衡度閾值確定。

9.根據權利要求8所述的方法，其特征在于，按照以下方式確定所述N：

獲取所述DHT網絡中能力最差的節點；

根據所述負載不均衡度閾值，確定所述第一虛擬標識的數量N，使得所述能力最差的節點的負載不均衡度小于所述負載不均衡度閾值。

10.一種DHT網絡的負載均衡實現裝置，其特征在于，包括：

分裂模塊，用于將所述DHT網絡中已分配給各個節點的N個第一虛擬標識中各個所述第一虛擬標識對應的負載空間均分為M份，使用M×N個第二虛擬標識對均分后的各份負載空間進行標識，其中，M和N為自然數，且M≥2；

分配模塊，用于將M×N個所述第二虛擬標識分配給當前所述DHT網絡的各個節點，由各個節點負責分配給其的所述第二虛擬標識對應的負載空間。

11.根據權利要求9所述的裝置，其特征在于，所述裝置還包括：

判斷模塊，用于判斷所述DHT網絡是否存在負載不均衡度超過負載不均衡度閾值的節點，如果是，則觸發所述分裂模塊。

12.根據權利要求9所述的裝置，其特征在于，所述裝置還包括：

發現模塊，用于發現所述DHT網絡是否有新節點加入，如果是，則觸發所述分裂模塊。