[發明專利]一種基于Storm的流式計算二分圖任務調度方法

在審

• 申請號: 201611203987.2
• 申請日: 2016-12-23
• 公開（公告）號: CN108241530A
• 公開（公告）日: 2018-07-03
• 發明（設計）人: 馬力;吳江;田小偉
• 申請（專利權）人: 西北大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

1.一種基于Storm的流式計算二分圖任務調度方法，其特征在于：將Storm作業有向無環圖DAJG(Directed Acyclic Job Graph)節點和集群物理機節點無向圖(UndirectedNode Graph)節點看作二分圖的兩類頂點，構建二分圖模型，綜合集群物理機各節點的計算能力以及集群中網絡傳輸延遲，根據任務與節點資源之間的可調度關系，采用解決二分圖最大權值匹配算法進行任務調度，具體步驟如下：

(1)分別對集群中異構的物理機所擁有的資源和需調度的任務集合進行形式化描述，建立兩者之間的可調度關系，建立集群物理節點資源與任務之間的二分圖數學模型；

(2)在調度過程中，并不是所有物理節點的可用資源都能滿足作業的請求，為了滿足使作業得到及時的響應，考慮根據作業的資源請求類型及集群節點提供的可用資源類型，總是將當前需要處理的作業調度到集群中資源負載相對較低的節點，通過引入數學統計值來評價作業與物理節點的可調度性；

(3)根據作業有向無環圖DAJG(Directed Acyclic Job Graph)的拓撲結構，考慮將具有前后依賴關系的任務，根據當前集群節點之間的數據傳輸速率選擇“就近”調度，使得每一階段的調度過程中再集群之間的數據元組傳輸總速率最大，以此降低網絡傳輸帶來的延遲，為二分圖模型引入可調度權值，即在作業可以調度到當前物理節點的條件下，利用權值衡量任務調度后數據元組遷移的速率；

(4)采用帶權二分圖最小權值匹配(最大權值的相反數)算法，求解物理機節點與待調度任務之間的匹配關系，使得待調度任務能獲得執行所需資源的前提下，數據在集群物理機之間通過網絡傳輸數據的總延遲最小。