一種新的分布式云工作流調度算法

摘要：云計算環境中當解決大數據相關應用問題時，服務之間面臨數據傳輸的高延遲以及不必要的網絡帶寬消耗。尤其是當數據量大并且同時數據分散時，這些問題更加特別突出。本研究提出一種新的分布式云工作流調度算法。該算法允許將工作流移向提供數據的服務，以獲得最佳性能。該算法將工作流程分解為較小的工作流流程以并行執行，并確定這些工作流程部署到最合適的網絡位置上并執行。

關鍵詞：面向服務的工作流;工作流切分;工作流部署

中圖分類號：TP301.6? ? 文獻標識碼：A? ? 文章編號：1007-9416（2020）10-0000-00

0引言

服務工作流表示服務的自動化，在此過程中，數據在服務之間的傳遞以進行處理，通常，工作流是基于集中式設計模型來編排的，該模型提供對工作流的控制，支持流程自動化，并將工作流邏輯封裝在執行它的中央位置。有幾種用于描述服務工作流的語言，例如已被接受為標準服務編排的業務流程執行語言（BPEL），BPEL是一種描述業務流程、計算機可執行的標準語言，它把若干個現有的服務按照一定的業務邏輯組合起來形成業務流程，然后部署到執行引擎中，由執行引擎對流程進行解析和編譯，逐步調用外部服務，完成整個業務流程的功能。[1]云工作流調度一直是工作流領域研究的熱點問題。多數工作通過設計目標函數進行優化。一個良好的調度算法可以提高效率，節約成本。本文提出一種新的分布式云工作流調度算法。服務組合在大數據環境下的應用，同時構思了一種適用于大數據環境下的服務組合系統，能有效的收集和整理海量的服務數據，滿足用戶的個性化需求。[2]

1國內外研究現狀

隨著互聯網技術、虛擬化技術的發展和成熟，云計算成為一種新的社會基礎設施。云計算作為一種彈性高效的計算模式，則為構建大數據服務提供了強大的技術支撐[3]?；ヂ摼W、物聯網、云計算、大數據的迅猛發展，計算服務化的趨勢日益明顯，“萬物皆服務（EaaS）”從內涵到環境都在發生著巨大的變化.物理世界與數字世界相互融合構成了物理信息空間（CPS），網絡世界內外線上線下（O2O）的服務系統通過互聯網構成了服務網絡世界，“務聯網（Internet of Services，IoS）”應運而生.務聯網的進一步發展，形成了“大服務（big service）。[4]云服務已經成為當前主要互聯網服務模式。云計算環境下工作流的調度是一個NP完全問題，針對此問題提出許多算法，包括基于元啟發式算法來解決NP問題，如粒子群算法（PSO）、禁忌搜索（TS）、模擬退火（SA）、遺傳算法（GA）等。本文的調度算法是，先選擇目標VM，然后將工作流圖進行切分，部署到合適的VM上，經驗證本文提出的方法對于與工作流的執行效率有顯著提高。本文的主要貢獻是一種分解工作流的方法，該方法允許將將工作流分解為較小的自工作流，以便在云上并行執行。他確定這些自工作流傳輸并隨后執行的最適合的位置。與依賴數據放置的現有方法不同，我們的方法允許將工作流計算移近提供數據的服務。通過采用這種方法，分布式引擎可以一起協作以執行整個工作流。

2方法

工作流引擎將工作流程邏輯與其執行分開。本節提供了一個簡單的工作流示例，將使用該示例來說明我們的方法。圖1顯示了他的結構，其中輸入A用于調用服務S1，該輸出用于調用S2，然后將其輸出傳遞到S3，S3的輸出用于調用S4和S4，S4和S5的輸出用作S6的輸入，從而產生最終的工作流輸出X。

通過遞歸下降編譯器來分析工作流程規范，以確保其正確性。他不會從工作流程中生成機器代碼表示，而是構造一個可執行圖的數據結構，該結構由表示服務調用的定點組成，他們之間的邊作為數據依賴項。該數據結構的組件可以分不到任意網絡位置的遠程工作流引擎。這樣可以在運行時處于優化的目的對其進行重構。

算法概述

我們的算法包括三個階段，包括工作流分解、放置分析和工作流的組合。為了實現我們的方法，我們創建了一個完全分布式的業務流程架構。與現有的編排技術不同，現有的編排技術由控制工作流的決策邏輯的集中引擎來代表控制位置，我們的體系結構中不存在單個控制位置的概念。在工作流程執行期間，我們可以在一個或幾個引擎上找到決策邏輯。

（1）工作流分解：通過創建一個流程遍歷器，將工作流程圖分解為代表子工作流流程的較小數據結構。通過該方法可以了解并檢測工作流程圖的復雜并行部分，并且通過該方法可以獲取有關工作流的輸入、輸出、服務調用和關聯類型的信息，而且同時還能夠獲取最小子工作流程的最大數量。工作流分解結果如圖2所示。

（2）放置分析：流程遍歷器分解了工作流之后，將進行放置分析以確定子工作流程的最合適引擎。此階段主要進行集群引擎的選擇和確定子流程放置在合適的引擎上。對每個子流程來說，可以通過使用k-means聚類算法以及業務約束、環境約束、容量約束、系統約束外加上代表網絡延遲的QoS指標將工作流引擎進行分組。每個子流程將獲得其最合適的引擎。放置分析的最終的結果是選擇帶寬最高，延遲最低的的計算節點如圖3所示。

（3）工作流組合：當所有的子流程放置到相應的引擎上之后，既第二部完成之后。將會檢測每個引擎中的服務之間的關系，如果檢測到他們之間又數據依賴關系則將他們組合在一起形成一個復合工作流程。這樣便完成了將一個復雜工作流程分解為不同引擎上規模較小的子工作流程，通過這種方式便將工作流分布到不同的集群上了，增加執行并行的能力。如圖4子工作流程組合分布圖所示。

3實驗

實現是基于Java，可以在任何物理或虛擬機上部署web服務包。他一來java運行時環境（JRE）和Apache Tomcat服務器。我們設計了一組實驗工作流程來評估我們的方法，每個工作流程都是根據特定的數據流模式指定的。其實驗結果如表1所示。

從表格可以看出這種新的分布式云工作流調度算法有了明顯的時間性能的提高。隨著服務數量的增加，相應的服務會找數據分布的引擎上這樣便減少了數據量的傳輸，相比輪詢算法來說更加節約時間。

4結語

隨著服務的數量和工作流數量的增加，如果沒有好的調度算法可能帶來嚴重的系統可伸縮問題，這些問題包括不必要的網絡消耗帶寬，服務之間數據量傳輸的高延遲以及性能瓶頸。本文提出了一種新的分布式云工作流調度算法，將工作流程分解為較小的自工作流程，然后可以將其傳輸到適當的位置上。使用依賴于業務約束、環境約束、容量約束、系統約束等條件來確定自工作流的位置。在未來的工作將集中在實時分布式監視和重新部署正在執行的自工作流，以適環境中的動態變化。

參考文獻

[1]江澄.大數據環境下基于QoS歷史記錄的服務組合推薦方法研究[D].南京：南京大學，2014.

[2]方若潔.基于BPMN/BPEL的全過程建模工具的設計與實現[D].北京：北京郵電大學，2015.

[3] 林文敏.云環境下大數據服務及其關鍵技術研究[D].南京：南京大學，2015.

[4] 徐曉飛，王忠杰，馮志勇.大數據環境下的大服務與應用及其影響[J].中國計算機學會通訊，2017（2）：24-30.

收稿日期：2020-08-24

基金項目：北京市自然科學基金（4192020）

作者簡介：何中秋（1993—），男，河北衡水人，碩士，研究方向：云計算、大數據、工作流。

A new Workflow Scheduling Algorithm

HE Zhong-qiu

（North China University of Technology Infomation Institute，BeiJing? 100144）

Abstract：These problems are especially prominent when the amount of data is large and the same data is scattered.When solving big data-related issues in a cloud computing environment， services face high data transmission delays and unnecessary network bandwidth consumption. This research proposes a new distributed cloud workflow scheduling algorithm.It permits the workflow computation to be moved towards the services providing the data in order to garner optimal performance results. This is achieved by decomposing the workflow into smaller sub workflows for parallel execution， and determining the most appropriate network locations to which these sub workflows are transmitted and subsequently executed.

Keywords：Service-oriented workflows;Workflow segmentation;Workflow deployment