[發明專利]一種對等結構云平臺下節點任務的負載均衡方法

有效

• 申請號: 201210400650.6
• 申請日: 2012-10-19
• 公開（公告）號: CN102882981A
• 公開（公告）日: 2013-01-16
• 發明（設計）人: 吳家皋;袁航;鄒志強;劉林峰
• 申請（專利權）人: 南京郵電大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 奚幼堅

1.一種對等結構云平臺下節點任務的負載均衡方法，其特征是：構建對等結構云平臺，將各個主節點以及從節點分別組織成對等結構的Chord網絡。在任務處理過程中，有兩類任務要執行：第一類是由發出任務處理請求的用戶節點提交給主節點的任務，即主任務；另一類是主節點分配給從節點執行的任務，即從任務；在進行主任務以及從任務的分配時，利用Chord網絡自身的優點使得各節點所處理的任務量相同，達到負載均衡；任務執行過程中，將每個主節點負責執行的主任務通過冗余備份方法進行備份，將所有主任務通過對主任務編號取余進行分類，每類主任務數據分別進行備份，每個主任務備份多個完全相同的主任務數據副本均勻存儲在Chord網絡中相應的節點上；當主節點失效時，通過主任務恢復方法進行主任務數據恢復；當有新主節點加入Chord網絡時，通過新主節點加入方法進行主任務數據的轉移恢復；每個主節點中均存儲兩部分主任務數據，一部分是該主節點正在執行的主任務數據，另一部分是該主節點備份其他主節點上正在執行的主任務數據。

其中：

1）任務執行過程包括以下步驟：

步驟1，利用一致性哈希函數，提交主任務的用戶節點將準備提交執行的主任務，設為job_A，通過哈希其屬性信息，賦予該主任務唯一的主任務編號，并通過這一編號將其發送到主節點Chord網絡中對應的后繼主節點，設為master_A上，由該后繼主節點負責執行此主任務；

步驟2，主節點master_A將主任務job_A分配成多個從任務，并利用一致性哈希函數，通過哈希從任務的屬性信息，賦予每個從任務唯一從任務編號，并通過這一編號將各個從任務發送到從節點Chord網絡中對應的后繼從節點上，由對應的后繼從節點負責執行這些從任務；

步驟3，當由主節點master_A分配的所有從任務全部完成之后，主節點master_A負責將最終結果返回給用戶節點；

2）主節點任務備份方法包括如下步驟：

步驟1，為了避免主節點失效所導致的主任務數據的丟失，將所有主任務編號通過求模取余運算，按余數分成類，并將每個主任務備份個完全相同的副本均勻的分布在Chord網絡的主節點上進行備份，公式（1）為主任務備份的計算方法：

BjobIdi=(jobId+(jobId%2K2)·2M-K1-K2+i·2M-K1)%2M,1≤i≤2K1-1---(1)]]>

其中，jobId為需要備份的主任務的編號，BjobId_i為需要備份的主任務的第i個備份任務的編號，M為Chord網絡所用到的安全散列函數的哈希值長度，2^M為Chord網絡長度，K₁、K₂均為大于等于零的整數；

主節點根據BjobId_i將正在該節點上執行的需要備份的主任務數據發送到Chord網絡中對應的后繼主節點上備份；

步驟2，設置一個定時器T，由負責執行某主任務的主節點每隔時間T向所有備份該主任務的備份主節點發送主任務的更新信息，以保證任務數據的一致。

3）有主節點失效時，其任務恢復方法包括如下步驟：

3.1）失效主節點正在執行的主任務數據的恢復

步驟1，失效主節點在Chord網絡上的后繼主節點利用公式（2）計算出備份編號集BID：

BID={id|(X+2M-K1+j·2M-K1-K2)%2M<id≤(Y+2M-K1+j·2M-K1-K2)%2M,]]>

0≤j≤2K2-1}---(2)]]>

其中，Y為失效主節點的編號，X為失效節點在Chord網絡上的前驅主節點的編號；

步驟2，在步驟1求出的BID的后繼主節點中找出編號jobId∈(X，Y]的主任務備份數據，并將這些數據傳輸到失效主節點的后繼主節點中，繼續執行；

3.2）失效主節點備份的其他主節點正在執行的主任務數據的恢復

步驟1，失效主節點在Chord網絡上的后繼主節點利用公式（3）計算出應該備份到失效主節點中的主任務的編號集BJID：

BJID={id|(X-i·2M-K1-j·2M-K1-K2+2M)%2M<id≤(Y-i·2M-K1-j·2M-K1-K2]]>

+2M)%2M,id%2K2=j,1≤i≤2K1-1,0≤j≤2K2-1}---(3)]]>

其中，BJID為應該備份到失效主節點中的主任務的編號集，Y為失效主節點的編號，X為失效節點在Chord網絡上的前驅主節點的編號；

步驟2，由任務備份方法得知，基于存儲的對稱性，失效主節點存儲的備份主任務數據必定也全部存儲在與Y節點順時針間距為以及所對應的主節點序列中，利用公式（4）求出備份編號集：

BBID={id|(X+2M-K1)%2M<id≤(Y+2M-K1)%2M}∪]]>

{id|(X+2M-K1+1)%2M<id≤(Y+2M-K1+1)%2M}---(4)]]>

步驟3，在步驟2所求得的備份編號集BBID的后繼主節點中找出包含在步驟1所得BJID的所有主任務，并將這些主任務數據傳輸到失效主節點的后繼主節點中進行存儲備份；

4）有新的主節點加入Chord網絡時，其任務遷移方法包括如下步驟：

步驟1，新主節點加入后，新主節點的后繼主節點在自己正在執行的主任務中找出應該由新主節點負責執行的所有主任務，這些主任務的編號滿足jobId∈(X,Y]，其中，Y為新加入主節點的編號，X為Y的直接前驅主節點的編號，并將這些主任務傳送至新加入的主節點繼續執行，且在本節點刪除這些主任務數據；

步驟2，新主節點的后繼主節點利用公式（5）計算出備份編號集JBID，并在自身備份的主任務中取出屬于JBID的所有主任務，并傳送至新加入主節點進行備份，且在本節點刪除這些主任務數據：

JBID={id|(X-i·2M-K1-j·2M-K1-K2+2M)%2M<id≤(Y-i·2M-K1-j·2M-K1-K2]]>

+2M)%2M,id%2K2=j,1≤i≤2K1-1,0≤j≤2K2-1}---(5)]]>

其中，JBID為備份編號集，Y為新加入主節點的編號，X為Y的直接前驅主節點的編號。