[發明專利]一種基于數據流預測的Storm任務伸縮調度算法

有效

• 申請號: 201710385355.0
• 申請日: 2017-05-26
• 公開（公告）號: CN107038071B
• 公開（公告）日: 2020-06-09
• 發明（設計）人: 熊安萍;段杭彪;蔣溢;祝清意;蔣亞雄
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 廖曦

1.一種基于數據流預測的Storm任務伸縮調度算法，其特征在于：該算法包括以下步驟：

S1：設置目標函數；

S2：求解Topology中worker數和各個組件的executor數；

S3：預測Topology要處理的數據流并求解開始組件spout所需的executor數；

S4：任務調度；

所述S2具體為：

S201：確定Topology中開始組件spout所需的executor數，通過公式依次求得后繼組件中的較優的executor數；其中，N_executori為第i個組件的executor數量，N_executori-1為第i-1個組件的executor數量，V_generate為前一組件的executor的tuple產生速度，通過監控Topology的運行數據然后取平均值獲得，t為一個周期開始后的時間，σ為通過多次試驗然后取得一個較優的值，V_proc為第i個組件中executor的tuple處理速度，通過監控Topology的運行數據然后取平均值獲得；

S202：求得Topology所需的executor總數；

S203：根據Storm官方建議每個worker中15個executor，求解得到Topology所需的worker數。

2.如權利要求1所述的一種基于數據流預測的Storm任務伸縮調度算法，其特征在于：所述S1設置目標函數為：其中，N_tuple為所處理tuple的數量，T_reci為tuple由發送節點到處理節點所需的接受時間，T_queuei為tuple到處理節點后因bolt繁忙tuple排隊的時間，T_proci為tuple的邏輯處理時間，T_sendi為tuple處理完后形成新的tuple的發送時間。

3.如權利要求1所述的一種基于數據流預測的Storm任務伸縮調度算法，其特征在于：所述S3具體為：

使用時間序列模型ARIMA預測Topology要處理的數據量，ARIMA(p,d,q)表示為：

X_t＝σ₁X_t-1+σ₂X_t-2+…+σ_pX_t-p+u_t-θ₁u_t-1-θ₂u_t-2-…-θ_qu_t-q，其中p為自回歸項數；q為滑動平均項數；X_t-1,X_t-2為X_t的前期值；u_t,u_t-1,u_t-2為X_t在t期，t-1期，t-2期的隨機誤差項，是相互獨立的白噪聲序列；d是使原序列X_t由非平穩時間序列轉換為平穩時間序列時對其成為平穩序列所做的差分次數；σ₁,σ₂,…,σ_p為自回歸系數，θ₁,θ₂,…,θ_q為移動平均系數，是模型的待估參數。

4.如權利要求1所述的一種基于數據流預測的Storm任務伸縮調度算法，其特征在于：所述S4具體為：當獲得topology中各組件較優的并行度后，進行Storm任務調度；使用線上調度算法，在運行時，通過監控獲得實時數據，包括executor的負載情況、executor的tuple接受率和發送率、集群中的節點負載；然后進行調度，在調度中最小化節點間的網絡通信，并保存集群中的節點負載均衡；

所述線上調度算法具體為：將executor按照traffic load降序排列，然后按序依次將executor分配到負載最輕的slot上，同時每個worker node上同一個Topology的executor會被分配到同一個slot上并且每個worker node不過載。