[發明專利]一種面向邊緣計算環境基于多副本的任務調度方法和系統

有效

• 申請號: 202010147501.8
• 申請日: 2020-03-05
• 公開（公告）號: CN111381950B
• 公開（公告）日: 2023-07-21
• 發明（設計）人: 錢柱中;王甜甜;陸桑璐
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 南京泉為知識產權代理事務所(特殊普通合伙) 32408
• 代理人: 許丹丹

本發明公開了一種面向邊緣計算環境基于多副本的任務調度方法和系統。所述方法包括：定期測量和收集每個邊緣集群內任務的執行狀態，建立本集群的任務時間延遲因子分布概率模型，所述模型描述了集群的資源性能；基于最短剩余處理時間原則和公平共享原則預估各作業可執行任務需要的副本數；基于各作業當前進度和集群的資源性能，采用迭代分配方式將各集群的空閑節點，根據預估的副本數，分配給各個任務；將分配到節點的任務調度到相應的集群來執行。利用本發明能夠在真實系統中有效利用邊緣計算環境中的空閑資源，通過合理的設定任務副本，降低作業的運行時延。

技術領域

本發明涉及邊緣計算環境中作業處理系統中的任務調度以及資源分配，具體涉及一種面向邊緣計算環境基于多副本降低大數據處理應用時延的任務調度方法及調度系統。

背景技術

如今，用戶與云端數據交互日益頻繁，云服務提供者在部署骨干數據中心的同時，加快“邊緣”集群的建設。谷歌在全球建有15個數據中心，同時也被探測出有來自139個國家1400余個端服務器為終端用戶服務；阿里云建立了18個數據中心，而其內容分發網絡產品(CDN)覆蓋超過1200個加速端服務器，跨越6大洲的多個運營商(ISP)網絡。對于依賴云端建立的IT服務商，各類型的用戶數據也越來越分散于地域分布的多個集群中，由這些異構的集群與跨ISP網絡連接構成云-邊緣融合的廣域存儲與計算環境。

一個大數據處理、機器學習等作業由多個存在數據依賴的階段組成，同一階段中的多個任務并行執行，對不同的數據分區執行相似的計算。一次作業可能涉及多個集群數據的處理與匯聚，并依靠廣域網絡進行必要的數據傳輸。例如，搜索引擎應用基于關鍵字的廣告投放，需要定期收集指定區域內各類廣告點擊量。統計表明谷歌在2016年每天的搜索量達55億次，會產生至少1.1TB數據分散于各邊緣集群。由于廣域網絡帶寬受限，這類跨域大數據分析通常采用將大量原始數據留在原地，而分派并行任務到相應邊緣集群處理數據，以求更快完成計算。

基于并行處理的作業通常會被一些“慢”任務拖延。微軟的一個商用集群顯示約一半的作業至少被“慢”任務拉長34％的完成時間?！奥比蝿债a生的原因十分復雜且不可避免，包括間歇性的組件故障、底層資源爭用、廣域網絡擁塞等，都會導致計算節點(也可以稱機器或者容器，用于承載任務的計算單位)的實際服務能力在短時間內發生較大波動，使得計算任務真實執行時間遠遠超出預期，成為“慢”任務。而且，隨著云服務計算基礎設施規模的擴張，上述現象愈加普遍，尤其是在資源有限的邊緣集群。

當前應用最廣泛的“慢”任務處理方案是多副本執行，即任務復制，為已變(或可能變)“慢”的任務執行多個副本，然后基于最快副本的處理結果推進后續計算。對于邊緣計算環境中的大數據處理作業，如圖1所示，人們可能希望不僅在本地復制任務，還可以遠程復制任務，利用其它邊緣集群的空閑資源，降低大數據處理應用時延。

然而，涉及多集群的跨域任務調度和復制實際上面臨著嚴峻的挑戰。首先，系統環境是高度動態且不確定的。例如，作業的到來可能是隨時間變化且不可預測的，系統的可用資源相應變化，使用邊緣集群的空閑資源復制任務不應影響到系統正常/即將到達作業的資源使用；節點性能的不穩定也會造成在實際執行副本之前，副本執行時間未知，尤其是邊緣服務器通常能力有限易發生過載。加上廣域網絡波動大，這些都會影響副本的執行。設計出不斷適應這種動態性和不確定性的在線算法并非易事。其二，系統環境是異構的，任務副本的執行集群會影響能夠為作業帶來的性能提升。例如，各邊緣集群異構的節點性能會影響執行，而集群之間異構的傳輸網絡會影響數據傳輸。第三，任何大規模系統的任務復制和調度都不應在系統上強加過多的開銷，需要在算法復雜性和預期的作業加速間取得平衡。

面對上述挑戰，現有的任務復制和調度方法是不適用的。現有的研究工作中，任務復制策略主要分為兩類，分別是基于監控的復制和主動式克?。呵罢弑O控任務運行并收集執行信息，在發現異常任務后為其啟動新副本以減少異常的影響；后者在任務執行一開始，依據歷史執行信息主動復制任務，以降低其成為慢任務的可能性。