[發明專利]一種基于網絡流量優化的Storm任務調度方法

有效

• 申請號: 201810092610.7
• 申請日: 2018-01-31
• 公開（公告）號: CN108415761B
• 公開（公告）日: 2021-11-05
• 發明（設計）人: 谷建華;周興社;周健華;閆旭濤
• 申請（專利權）人: 西北工業大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 金鳳

1.一種基于網絡流量優化的Storm任務調度方法，其特征在于包括下述步驟：

步驟1：進程間流量統計

通過tcpdump命令采用抓包的方式統計進程間發送的信息，統計運行時Storm各個Worker進程間的數據傳輸速率，即可得到通信關系矩陣；

在n個進程中，進程d_i和進程d_j間的數據傳輸速率為進程d_i到d_j和d_j到d_i的通信速率之和，其中，1≤i≤n，1≤j≤n，通信關系矩陣W中的i行j列的W_ij表示進程d_i和進程d_j間的數據傳輸速率，將n個進程間的數據傳輸速率進行匯總得到通信關系矩陣W，通信關系矩陣如下所示：

步驟2：根據Worker進程間的通信關系矩陣，將n個進程劃分到k個機器上，本發明采用遺傳算法進行網絡k劃分，所述遺傳算法的步驟包括編碼表示、定義適應度、選擇操作、雜交操作和變異操作；

首先按照步驟1得到通信關系矩陣，隨機產生m個初始例子染色體，其中，m取值范圍為20～100，據編碼產生初始種群，計算每個染色體的適應度，然后執行選擇操作，根據每個個體的適應度比例確定選擇概率，根據選擇概率和輪盤選擇策略在種群中選擇個體，若隨機概率大于雜交概率α則進行雜交操作，若隨機概率大于變異概率β則進行變異操作；不斷循環整個過程，進行選擇產生新種群、變異和雜交操作，進行r次循環，其中r的取值范圍為100～500，直到適應度值達到穩定，即適應度值不再變化，將種群中適應度值最大的個體所代表的方案作為劃分方案，得到機器對應的進程表；

具體步驟如下：

步驟2.1：編碼表示

共n個進程，運行在k個機器上，進行編碼表示時將n個進程劃分到k個子集，即等于現在使用的機器數量k，編碼中染色體x表示為{g₁,g₂,...g_i,...,g_n}，1≤i≤n，且g_i取值范圍為{0,1,2,...,k-1}，表示每個進程屬于一個子集，且每個染色體應包含0到k-1的所有值；

步驟2.2：定義適應度

定義無向圖G＝(V,E,W)，頂點集V＝{v₁,v₂,v₃...v_n}，邊的集合用w(v_i,v_j)表示各個邊之間的權值，邊的權值即是步驟1中的通信關系矩陣的權值，將無向圖G劃分為k個子集，P₁，P₂...,P_k，且子集間互不相交，最大化各個子集內的通信量如公式2所示：

其中v_i∈P_s,v_j∈P_t,s,t∈{1,2,...,n}且s＝t表示同一個子集，在子集內累加邊的權值為且系統storm運行的應用不變的情況下總的權值和是固定的，當各子集中權值和最大時，子集間權重達到最小；

fit表示每個染色體的適應度，適應度公式如下所示：

其中，g_i,g_j∈{0,1,...,k-1}表示子集，g_i表示劃分的子集，g_i＝g_j表示劃分到同一個子集中，traffic表示子集內所有節點間的w(v_i,v_j)傳輸速率和，balance表示均衡參數，均衡參數balance定義如下所示：

s_i表示子集i包含的節點數，表示平均每個子集應得到的節點數，n代表進程個數，|s_i-n/k|表示每個子集節點數與平均節點數差的絕對值；

p表示均衡系數，為所有染色體中最小傳輸速率和與最大均衡參數的比值，定義如下所示：

p＝min(traffic)/max(balance) (5)

定義參數σ改變對均衡度和傳輸量的重視程度，其中0≤σ≤1；

步驟2.3：選擇操作

選擇操作采用輪盤選擇方法，根據步驟2.2計算個體適應度fit除以總的適應度表示選擇概率，選擇概率P_i如下所示：

b為總群中染色體的個數，以P_i為概率選擇新的個體；

步驟2.4：雜交操作

設置雜交概率為α，雜交概率取值范圍為0.4～0.9，同時在此時產生隨機數δ，其中，0＜δ＜1，當δ大于α時進行雜交操作，雜交時交換種群中兩個染色體的u個對應位，其中，u取值范圍為2～10，如果雜交操作使得部分基因缺少，即每個染色體x沒有包含0到k-1的所有值，則雜交失敗，不進行該次雜交，雜交成功則保留染色體對u個位置改變；

步驟:2.5：變異操作

設置變異概率β，取值范圍為0.0001～0.2，此時產生新的隨機數δ′,當δ′大于β時進行變異操作，隨機選擇兩個點，對換這兩個點的數值即實現變異操作，連續v次隨機對換一個染色體兩個基因位即實現變異操作，其中，v取值為3～10；

步驟3：機器內Worker進程間流量優化

當兩個進程間傳輸速率大于閾值h,h為網卡速度的1％～10％，將兩個進程中的線程進行重新組織，詳細步驟如下：

步驟3.1：設定數據傳輸速率閾值h，h為網卡速度的2％，兩個進程間數據傳輸速率大于閾值h的兩兩進程，得到進程配對表{c₀c1,c₁c₂,...,c_ic_i+1}，0ik/2；將大于閾值h的配對進程，按照傳輸速率對進程配對表降序排列；

步驟3.2：根據步驟3.1得到的降序排列的進程配對表，依次得到流量最大的兩個配對進程c_ic_i+1，根據配對的兩個進程c_ic_i+1內的線程關系，得到線程上下游關系表{e₁,e₂,e₃,...,e_i}；

步驟3.3：根據配對進程c_ic_i+1的線程上下游關系表，將進程內的線程按照如下的方式進行重新分配線程：

分配最上游線程e_i，將最上游的各個線程以輪詢的方式分配到c_ic_i+1進程中；然后再分配線程e_i的直接下游線程e_i+1，將線程e_i+1分配到存在線程e_i的進程中；即e_i和e_i+1總是成對出現，得到新的進程和線程對應表；

步驟4：任務分配

根據步驟2得到機器和進程的對應表和步驟3得到的進程和線程對應表，可知每個線程所屬的進程，每個進程所屬的機器得到了任務分配的全部信息，進行任務分配時，采用Storm的Cluster類的setAssignments函數依次將進程分配到機器上，進程信息及包含的線程通過進程和線程對應表進行查詢，機器信息通過機器和進程的對應表查詢獲得，任務分配過程通過Storm命令rebalance來觸發實施任務分配。