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

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

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

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

0引言

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

1國內外研究現(xiàn)狀

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

2方法

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

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

算法概述

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

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

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

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

3實驗

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

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

4結語

隨著服務的數(shù)量和工作流數(shù)量的增加，如果沒有好的調度算法可能帶來嚴重的系統(tǒng)可伸縮問題，這些問題包括不必要的網(wǎng)絡消耗帶寬，服務之間數(shù)據(jù)量傳輸?shù)母哐舆t以及性能瓶頸。本文提出了一種新的分布式云工作流調度算法，將工作流程分解為較小的自工作流程，然后可以將其傳輸?shù)竭m當?shù)奈恢蒙?。使用依賴于業(yè)務約束、環(huán)境約束、容量約束、系統(tǒng)約束等條件來確定自工作流的位置。在未來的工作將集中在實時分布式監(jiān)視和重新部署正在執(zhí)行的自工作流，以適環(huán)境中的動態(tài)變化。

參考文獻

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

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

[3] 林文敏.云環(huán)境下大數(shù)據(jù)服務及其關鍵技術研究[D].南京：南京大學，2015.

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

收稿日期：2020-08-24

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

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

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