[發明專利]一種適用于在線數據密集型應用的請求多副本任務執行方法

有效

• 申請號: 201510312591.0
• 申請日: 2015-06-08
• 公開（公告）號: CN104915205B
• 公開（公告）日: 2019-05-07
• 發明（設計）人: 楊海龍;張佐瑋;欒鐘治;錢德沛
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 李有浩

1.一種適用于在線數據密集型應用的請求多副本任務執行方法，所述在線數據密集型應用屬于云計算機系統中的任務執行單元，其特征在于：請求多副本任務執行方法包括有下列步驟：

步驟A，初始化系統并設置初始量和參考量

步驟A-1，設置服務質量目標SLO；

步驟A-2，對后端從節點進行標記，記為bs_N；

步驟A-3，設置任務對應的副本；

初始化在線數據密集型應用中的任務執行系統，設置任務執行系統中每個任務對應的副本總數為k，副本標記為r；

每個任務對應的所有副本采用集合形式表達為R＝{r₁,r₂,…,r_k}，r₁表示第一個副本，r₂表示第二個副本，r_k表示最后一個副本，k表示副本的標識號；

步驟A-4，設置無效周期數、恢復周期數；

初始化在線數據密集型應用中的任務執行系統，設置后端從節點bs_N的無效周期數和恢復周期數執行步驟A-5；初始時，

狀態條件一：且表示后端從節點bs_N處于無效狀態；處于無效狀態的所述bs_N只接收被標記后的任意副本r_k，同時不更新響應時延監控模塊的響應時延RL；

狀態條件二：且表示后端從節點bs_N處于恢復狀態；處于恢復狀態的所述bs_N能夠接收任意副本r_k，同時不更新響應時延監控模塊的響應時延RL；

狀態條件三：且時，表示后端從節點bs_N處于運行狀態；處于運行狀態的所述bs_N能夠接收任意副本r_k，同時更新響應時延監控模塊的響應時延RL；

步驟A-5，計算動態參考值

設置服務時延監控模塊(400)的滑動窗口Windows存儲的服務時延的個數，記為V，若服務時延監控模塊(400)收到的服務時延的個數記為v；當v＜V時，則服務時延監控模塊(400)繼續接收的服務時延；當v≥V時，則服務時延監控模塊(400)將先接收的服務時延剔除；

計算服務時延監控模塊(400)的存儲的服務時延的平均值ASL，

設置響應時延監控模塊(500)的滑動窗口Windows存儲的響應時延的個數，記為U，若響應時延監控模塊(500)收到的響應時延的個數記為u；當u＜U時，則響應時延監控模塊(500)繼續接收的響應時延；當u≥U時，則響應時延監控模塊(500)將先接收的響應時延剔除；

計算響應時延監控模塊(500)的存儲的響應時延的平均值ARL，且

計算響應時延監控模塊(500)的存儲的響應時延的方差VRL，且執行步驟B；

步驟B，副本標記及分發副本

步驟B－1，副本標記；

從R＝{r₁,r₂,…,r_k}中選取w個副本作為任務的標記副本，0＜w＜k；則將所述R＝{r₁,r₂,…,r_k}記為標記后副本的表達形式為s為副本被標記的標識的；

步驟B－2，分發副本；

后端主節點將同一任務的所述分發至N個后端從節點上，執行步驟C；

步驟C，獲取排隊時延；

計算后端從節點bs_N運行r₁副本的排隊時延記為且表示后端從節點bs_N運行r₁副本的時間，表示r₁副本到達后端從節點bs_N的時間；

計算后端從節點bs_N運行r₂副本的排隊時延記為且表示后端從節點bs_N運行r₂副本的時間，表示r₂副本到達后端從節點bs_N的時間；

計算后端從節點bs_N運行副本的排隊時延記為且表示后端從節點bs_N運行副本的時間，表示副本到達后端從節點bs_N的時間；

計算后端從節點bs_N運行副本的排隊時延記為且表示后端從節點bs_N運行副本的時間，表示副本到達后端從節點bs_N的時間；

計算后端從節點bs_N運行副本的排隊時延記為且表示后端從節點bs_N運行副本的時間，表示副本到達后端從節點bs_N的時間；

計算后端從節點bs_N運行r_k副本的排隊時延記為且表示后端從節點bs_N運行r_k副本的時間，表示r_k副本到達后端從節點bs_N的時間；執行步驟D；

步驟D，檢查副本中是否是標記副本；

步驟D-1，任意一后端從節點bs_N對接收到任意一副本r_k進行檢查，從而獲取所述r_k副本是否是帶有標記的副本；

步驟D-2，若后端從節點bs_N接收到的副本r_k為標記副本則執行步驟H；

步驟D-3，若后端從節點bs_N接收到的副本r_k不是標記副本則執行步驟E；

步驟E，判斷后端從節點的運行狀態；

步驟E-1，若后端從節點bs_N滿足狀態條件一時，后端從節點bs_N處于無效狀態，則結束在線數據密集型應用中的任務執行；

步驟E-2，若后端從節點bs_N不滿足狀態條件一時，后端從節點bs_N不處于無效狀態，則執行步驟F；

步驟F，獲取副本排隊時延，并計算副本的預期響應時延

計算r₁副本的預期響應時延且

計算r₂副本的預期響應時延且

計算副本的預期響應時延且

計算副本的預期響應時延且

計算副本的預期響應時延且

計算r_k副本的預期響應時延且執行步驟G；

步驟G，檢查副本的預期響應時延是否滿足服務質量目標

若則結束在線數據密集型應用中的任務執行；若則執行步驟H；

若則結束在線數據密集型應用中的任務執行；若則執行步驟H；

若則結束在線數據密集型應用中的任務執行；若則執行步驟H；

若則結束在線數據密集型應用中的任務執行；若則執行步驟H；

若則結束在線數據密集型應用中的任務執行；若則執行步驟H；

則結束在線數據密集型應用中的任務執行；則執行步驟H；

步驟H，獲取副本的服務時延和響應時延

計算后端從節點bs_N運行所述r₁副本的服務時延記為且表示后端從節點bs_N執行完成r₁副本的時間；

計算后端從節點bs_N運行所述r₂副本的服務時延記為且表示后端從節點bs_N執行完成r₂副本的時間；

計算后端從節點bs_N運行所述副本的服務時延記為且表示后端從節點bs_N執行完成副本的時間；

計算后端從節點bs_N運行所述副本的服務時延記為且表示后端從節點bs_N執行完成副本的時間；

計算后端從節點bs_N運行所述副本的服務時延記為且表示后端從節點bs_N執行完成副本的時間；

計算后端從節點bs_N運行所述r_k副本的服務時延記為且表示后端從節點bs_N執行完成r_k副本的時間；

計算后端從節點bs_N運行所述r₁副本的響應時延記為且

計算后端從節點bs_N運行所述r₂副本的響應時延記為且

計算后端從節點bs_N運行所述副本的響應時延記為且

計算后端從節點bs_N運行所述副本的響應時延記為且

計算后端從節點bs_N運行所述副本的響應時延記為且

計算后端從節點bs_N運行所述r_k副本的響應時延記為且執行步驟J；

步驟J，檢查節點狀態參考量

步驟J-1，檢查后端從節點bs_N若不滿足狀態條件三，則更新即遞減1；執行步驟J-2；

步驟J-2，檢查后端從節點bs_N若滿足狀態條件一，則更新無效周期數即遞減1；同時結束在線數據密集型應用中的任務執行；檢查后端從節點bs_N若不滿足狀態條件一，執行步驟J-3；

步驟J-3，檢查后端從節點bs_N若滿足狀態條件三，則后端從節點bs_N處于運行狀態，執行步驟K；

步驟K，更新節點狀態參考量

依據ARL和VRL更新后端從節點bs_N的狀態參考量，即無效周期數和恢復周期數

若且VRL＜ζ，η表示預設的響應時延偏移量上限，ζ表示預設的響應時延方差上限；表明系統負載較高，一方面更新恢復周期數為副本等待隊列模塊200中的副本數；另一方面更新無效周期數將所述的更新為0≤λ≤1；λ表示預設的無效周期數的比例參數。

2.根據權利要求1所述的一種適用于在線數據密集型應用的請求多副本任務執行方法，其特征在于：初始時，無效周期數恢復周期數