基于過程劃分技術的服務組合拆分方法

劉惠劍，劉峻松，王佳偉，薛 崗

（云南大學軟件學院，昆明650000）

（*通信作者電子郵箱mess@ynu.edu.cn）

0 引言

Web 服務是面向服務體系架構實現的基礎技術［1］，該技術通過標準的網絡通信協議提供業務服務。單個Web 服務提供特定的功能，為了滿足用戶的需求，越來越多的實際項目使用服務組合技術（簡稱服務組合）將多個Web 服務集成、組合起來，以便提供綜合、復雜的增值服務［2］。服務組合中服務組件的執行順序和各服務組件之間的交互可通過業務過程來描述。服務組合包括集中式服務組合以及非集中式服務組合。非集中式服務組合不同于集中式服務組合，如圖1 所示，為了實現業務功能，集中式服務組合通過中心控制器來實現各個服務組件之間的協作，而非集中式服務組合通過協議來直接實現各個服務組件的協作。

基于業務過程服務組合可實現為:服務編排（service choreography）［3］和服務編制（service orchestration）［4］。服務編制通過中心控制器內的業務過程來實現服務組件之間的協作。服務編制已被廣泛應用的標準有:WS-BPEL（Web Services Business Process Execution Language）［5］等。與服務編制不同，服務編排更具有協作性，各個服務組件之間直接基于交互來實現服務組合中的業務過程。服務編排已被廣泛應用的標準有:WS-CDL（Web Services Choreography Description Language）［6］等，無中心控制器是服務編排應用的核心技術特征。

圖1 服務組合Fig.1 Service compositions

在實際的應用場景中，文獻［7］所提到在數據密集型計算流程例如蒙太奇工作流程［7］中，集中式組合的中心控制器傳遞大量中間數據，這些不必要的數據傳輸會引起中心控制器過載從而導致服務性能下降。文獻［8］中涉及的列車路線查詢服務，將集中式查詢服務拆分為非集中式服務組合可以減少中間查詢的步驟。在非集中式服務組合中，原中心控制器內程序被劃分為獨立的服務組件，服務組件之間交互可以提高服務的并行度以及減少服務組件之間的數據傳輸量。現有的研究結果表明，如果非集中式服務組合具有合理的結構，并且所有的服務組件都得到適當的部署，那么非集中式服務組合與集中式服務組合相比較可具有更少的網絡流量［9］、更大的吞吐量［8］以及更短的響應時間［10］。由于企業應用程序主要關注服務的性能以及吞吐量，有必要消除中心控制器產生的瓶頸，因此本文提出一種將集中式服務組合重構成非集中式服務組合的方法。

業務過程的基本構成包含活動以及活動之間關系。基于有向圖建立業務過程模型時，所謂“良構”模型滿足條件:當且僅當每個頂點都滿足當頂點（分離）有多條輸出有向邊時對應的頂點（連接）有多條輸入有向邊，使得分離頂點和連接頂點之間形成單一的區域；不滿足條件則為“非良構”模型［11］。“良構”模型相比較“非良構”模型更容易進行分析、執行和優化。在實際應用中，仍然存在大量“非良構”業務過程，而且它們能被正確執行。

本文實現了一種基于圖轉換的業務過程拆分方法，與已有方法相比，該方法能夠拆分“良構”和“非良構”的模型，并且可將集中式服務組合重構為非集中式服務組合。通過實驗表明，本文所實現的方法能有效地拆分服務組合中的業務過程。而且，如果部署得當，所構建的非集中式服務組合（與原有集中式服務組合相比）具有較好的執行效率。

國內外有許多非集中式服務組合的相關研究。文獻［12］提出基于信任的非集中式服務組合方法。該方法基于格模型建立非集中式服務信任評估框架，分別在組件和組合級評估服務信任度以避免不可信的數據傳輸；通過分析服務依賴關系，實現滿足全局和局部信任約束可信服務選擇；基于蒙特卡羅方法建立可信路徑選擇、優化和容錯算法傳輸服務評估調用信息。文獻［13］提出一種適用于跨安全管理域的非集中式服務調用方法，該方法使用對等的服務訪問代理實現跨管理域的服務請求路由和調用，利用信息隱藏和加密技術保障服務響應結果的安全傳輸。文獻［14］考慮到云服務提供商之間的服務價格和服務質量（Quality of Service，QoS）差異，提出一種根據討價還價博弈模型來構建非集中式云服務組合的方法。文獻［15］提出一個基于人工勢場的非集中式服務組合模型，在該模型中根據用戶請求服務的百分比和服務節點的能力來形成人工勢場，人工勢場通過平衡服務請求和服務節點之間的作用力來構建非集中式服務組合。

在Web 服務領域已經有關于服務拆分的相關工作。文獻［8］將單個BPEL 程序編寫的業務過程拆分為一組等效的分散子程序。該方法使用線程控制流程圖（Threaded Control Flow Graph，TCFG）來對業務過程建模，并生成過程的程序依賴圖（Program Dependence Graph，PDG）。基于PDG 提出頂點合并算法，根據合并算法產生的結果進行服務拆分。文獻［16］提出基于一組協作代理來執行BPEL 業務過程，每個代理根據其資源和過程中活動執行的成本來標記將要執行的活動，并且代理之間基于共享空間來進行通信。國內文獻［17］提出一種BPEL 業務過程解析方法，以與服務直接相關的活動為基礎，將過程劃分出若干基本單元，通過遞歸算法將其他活動歸屬到相關單元，產生多個子過程，實現對原有過程的分割，使業務過程可以分布式執行。

文獻［18］提出一種基于圖變換來構建非集中式服務組合的技術，該技術將業務過程表示為類型有向圖，然后根據該類型有向圖形成相應的過程結構圖（Process Structure Graph，PSG），并提出頂點合并算法用于對PSG 中的頂點進行分組，所生成的分組結果可作為構建非集中式服務組合的參考依據。根據該工作，本文基于多線程技術來對PSG 中的頂點進行分組，從而實現業務過程的拆分，并能支持構建非集中式服務組合。與文獻［18］相比，本文所實現的方法能夠提供多種業務過程拆分方案，而這些方案可被用于不同的業務場景。與其他工作相比，本文所實現的方法具有通用性，該方法能夠直接拆分“非良構”的模型。實驗結果表明，該技術可高效地拆分“良構”和“非良構”業務過程模型，所生成的非集中式服務組合具有更高的吞吐量以及更低的響應時間。

1 相關技術基礎

本部分將介紹論文工作的技術基礎，包括過程建模以及圖轉換技術。

1.1 過程建模

業務過程可用有向圖來進行表示。類型有向圖［19］是在有向圖的基礎上添加類型屬性，不同頂點和有向邊可具有不同類型屬性。基于類型有向圖，一個過程模型可被定義為:

定義1 一個過程模型表示為一個類型有向圖P?，且P?:=(PG，T，τ)［18］。其中:PG是一個有向圖，即PG=（V，E，s，t）；T=(TV，TE)是PG的類型集合；τ=(τV，τE)表示類型映射（函數）。具體而言:

1）在PG中，V為頂點集，E為有向邊集，s是E→V的源函數，t是E→V的目標函數。

2）在T中，TV指定PG的頂點類型，TE指定PG的有向邊類型。

3）τ中包括頂點類型映射函數τV:V→TV和有向邊類型映射函數τE:E→TE。

本文中的過程模型具有以下特點。PG中的V內元素類型有活動頂點和控制頂點，控制頂點的類型包括判斷、匯合、分支和合并。T中的TV={“f”，“p”}，“f”代表該頂點是與外部環境交互的固定頂點，“p”代表該頂點是服務器內部操作的可動頂點；TE={“c”，“d”}，“c”代表控制依賴，“d”代表數據依賴。控制依賴代表過程模型中的執行關系，數據依賴代表過程模型中的數據流動關系。每個過程模型P?都包含唯一的起始和停止頂點。

基于類型有向圖，圖2展示一個過程模型實例。

圖2 過程模型實例1Fig. 2 Process model example 1

該模型中，活動表示為矩形，分支與合并表示為條形，判斷為菱形，匯合為三角形，開始和停止表示為圓形。起始頂點的唯一輸出邊稱為入口邊，而停止頂點的唯一輸入邊稱為出口邊。圖2標記有"f"代表的固定頂點例如{F0，F1，…，F4}，其余表示可動頂點例如{P0，P1，…，P7}。在可動頂點中，P1與P5表示活動；P0與P2表示判斷；P4表示分支；P3與P7表示匯合；P6表示合并。模型中的實線箭頭表示過程中的控制依賴，虛線箭頭表示過程中的數據依賴。根據文獻［20-21］中的判斷標準，該實例為一個“非良構”的模型，但是根據結構語義該過程可以正常執行。

1.2 圖轉換技術

圖轉換是一種基于規則的圖修改技術［22］。其基本思想是將一個系統的計算狀態表示為圖形，并將每步計算步驟表示為圖形的轉換規則。轉換規則包括“模式圖”以及“替換圖”，在一個實際的圖形轉換中，“模式圖”需要與待轉換圖進行匹配，并基于“替換圖”產生新的圖形。圖轉換的原理可基于范疇 理 論［19］來 進 行 描 述，常 用 方 法［22］有:雙 推 出（Double-PushOut，DPO）和單推出（Single-PushoOut，SPO）等。

圖3 表示一個基于SPO 方法的圖轉換實例。該圖中，轉換規則為p:L→R，而圖L與圖R分別是規則p的“模式圖”和“替換圖”；另外，m:L→G為圖L到圖G映射。基于規則p和映射m，圖3中的圖H是圖G推導出的新圖。

圖3 圖轉換例子Fig. 3 Graph transfermation example

針對類型有向圖，相關研究［18］表明:該類圖形的變換可基于SPO的圖轉換技術來實現。

2 過程拆分

本章基于過程模型實現對服務組合內的業務過程拆分。步驟如下:1）使用類型有向圖對業務過程進行建模；2）將過程模型轉換為過程結構圖；3）對過程結構圖中的頂點進行分組；4）根據頂點分組實現業務過程的拆分。

2.1 過程結構圖

過程模型的結構可以表示為過程結構圖（PSG），PSG是一種基于程序結構樹（Program Structure Tree，PST）［23］的類型有向圖。PST 表示過程模型中單入單出（Single Entry Single Exit，SESE）區域［23］的嵌套關系，單個SESE區域內的頂點位于PST的同一層次中。在一個過程模型中，SESE應該是一個控制依賴有向邊的最小區域。基于過程模型，PSG可被定義為:

定義2 一個過程結構圖S?是一個三元組，即S?:=(S，TS，τS)，其中:

1）S=(VS，ES，sS，tS)是S?的基本有向圖，VS為頂點集，ES為有向邊集，sS是ES→VS的源函數，tS是ES→VS的目標函數。

2）TS=()為S的類型集合，為頂點的類型集合，為有向邊的類型集合。

3）τS=()為類型映射函數，頂點和有向邊的類型映射函數分別為:VS→和:ES→。

本文中的PSG 具有以下特點。S內頂點位于SESE 區域中，并且其中的部分頂點為過程模型的頂點。S內有向邊的類型包括SESE的嵌套關系、過程模型中的數據依賴或控制依賴。TS內的=“{f”，“p”，“u”}，“f”表示固定頂點，“p”表示可動頂點，“u”表示無類型頂點，無類型頂點表示SESE 區域；=“{c”，“d”，“b”}，“c”代表控制依賴，“d”代表數據依賴，“b”代表SESE的嵌套關系。

除了PST自身特點外，PSG還具有以下結構特點:

1）PSG中的頂點為SESE區域或過程模型內的頂點。

2）PSG中包含所有過程模型的數據依賴和控制依賴。

將圖2的過程模型生成規范的SESE區域如圖4所示。由于SESE區域是根據控制依賴進行定義，因此圖4已隱藏了圖2模型中的數據依賴。基于圖4將無嵌套關系的SESE區域轉為樹的同一層頂點，SESE區域所包含的子區域轉為對應的子樹，可生成相對應的PST，PST中的有向邊表示SESE的嵌套關系。

圖4 基于圖2模型劃分SESE區域Fig. 4 SESE regions partitioned by the model in Figure 2

在圖5的PST各層中增加與SESE區域并列的控制頂點，并添加各頂點的標簽以及所關聯的數據依賴和控制依賴，即可生成圖2過程模型對應的PSG。如圖6所示，SESE區域所代表的頂點為實線框，控制頂點表示為虛線框；PST分支表示為實線箭頭，類型為“b”；數據依賴表示為虛線箭頭，類型為“d”；控制依賴表示為點線箭頭，類型為“c”；root，0和1是無類型頂點，代表該頂點下還有子頂點，類型為“u”；F0，F1，…，F4是固定頂點，類型為“f”；P0，P1，…，P7是可動頂點，所對應類型為“p”。

圖5 基于圖2模型構建PSTFig. 5 Construction of PST based on the model in Figure 2

圖6 基于圖2模型構建PSGFig. 6 Construction of PSG based on the model in Figure 2

2.2 基于多線程的頂點分組算法

PSG 中的頂點可根據文獻［8］提出的基本準則進行分組。該準則的核心思想為:類型“p”頂點能和類型“p”、“f”頂點合并，類型“f”頂點不能與類型“f”頂點合并。若直接根據準則分組將進行大量運算，由1.2 節可知，基于SPO 方法的圖轉換可以應用在PSG 上，因此本文定義圖7 規則來減少PSG 頂點的分組計算量。如圖7 所示，規則中的SESE 嵌套關系表示為實線箭頭，數據依賴關系表示為虛線箭頭，控制依賴關系表示為點線箭頭。頂點的類型帶有標簽“:”。在規則中，可動頂點的類型標簽為“:p”，無類型頂點的類型標簽為“:u”。

圖7 規則中的一些頂點帶有標簽“:*”，標簽“:*”代表該類型為“f”或“p”，該標簽所代表的具體類型在轉換過程中不發生改變。

圖7 PSG轉換規則Fig. 7 Transformation rules for PSG

根據圖7中的規則，設計如下頂點分組算法1。

對于SESE 區域中(a，b)，如果a的目標頂點是分支頂點，則區域(a，b)被稱為“分支區域”；如果a的目標頂點不是分支頂點，則區域(a，b)稱為“非分支區域”。“分支區域”代表該區域內運行多個子線程程序。

算法1 的時間復雜度為O(ep)，e取過程模型中單個頂點出入度和的最大值，p取SESE 區域中頂點數的最大值。運用算法1 對圖6 中的PSG 進行重新分組將產生123 種分組結果，并在服務外部數據流出總量最小的結果組中隨機挑選一個結果如圖8所示。

圖8 圖6的PSG分組結果Fig. 8 Grouping result of PSG in Figure 6

具體該結果的生成步驟如下:

1）將頂點1 和頂點0 合并（規則1）；將頂點0 和頂點root合并（規則1）；

2）將頂點F0 和頂點P0 合并為頂點“F0，P0”（規則3）；將頂點F1 和頂點P3 合并為頂點“P3，F1”（規則3）；將頂點F4 和頂點P7 合并為頂點“P7，F4”（規則2）；將頂點P2 和頂點F2 合并為頂點“P2，F2”（規則2）；將頂點P1 和頂點“P2，F2”合并為頂點“P1，P2，F2”（規則2）；將頂點“P3，F1”和頂點P4 合并為頂點“P3，P4，F1”（規則3）；將頂點“P3，P4，F1”和頂點P5 合并為頂點“P3，P4，P5，F1”（規則3）；

3）將頂點“P3，P4，P5，F1”和頂點P6 合并為頂點“P3，P4，P5，P6，F1”（規則5）；

4）輸出結果。

2.3 過程分區

應用算法1 后將重新組織PSG。分組后的PSG 結果包括頂點組和依賴關系，每個非根頂點組可以表示出業務過程中的部分過程，依賴關系對應業務過程中存在的依賴關系。因此，可根據算法1 產生的結果來指導拆分業務過程。運用算法1 處理圖2 生成的部分結果如圖9 中（b）、（c）所示，圖9（a）所示為初始集中式服務組合。

圖9 中的“S1”“S2”和“S3”代表服 務 組件，圖9（a）中“Control”代表業務過程，圖9（b）、（c）中的拆分出來子服務例如“F0P0”代表“Control”中的部分業務過程，服務之間聯系為消息通信。

圖9 算法1生成部分結果Fig. 9 Part of results generated by algorithm 1

3 實驗與分析

為了驗證本文所提方法的有效性，本部分從兩個方面來進行實驗驗證:頂點分組算法的執行情況；服務組合的執行效率。

3.1 頂點分組算法的執行情況

本部分針對頂點分組算法的運行效率進行測試，實驗環境 為Intel Core i5-6300U 2.40 GHz×4 CPU，8 GB RAM，Ubuntu 16.04。實驗分別測出單線程算法（算法1在單線程環境下）和算法1拆分圖2以及圖10過程模型所需要的時間。

圖10 過程模型例子2Fig. 10 Process model example 2

圖2 模型中包含13 個頂點、27 條依賴有向邊，由表1 可得，圖2 模型在單線程算法下的平均運行時間為947 ms，在算法1下的平均運行時間為744 ms，耗時減小21.4%；圖10模型中包含18 個頂點、40 條依賴有向邊，圖10 模型在單線程算法下的平均運行時間為16 106 ms，在算法1 下的平均運行時間為6 674 ms，耗時減小58.6%。由此可得，運行算法1 耗時要少于單線程算法；過程模型內的頂點數和有向邊數越多，算法1的執行效率相比較單線程算法提升越明顯。

表1 頂點分組算法的實驗結果 單位：ms Tab. 1 Experimental result of node grouping algorithm unit:ms

實驗結果的箱線圖如圖11 所示。從箱線圖可得，算法1的執行效率更高，并且算法1 整體運行情況比單線程算法更加穩定。

圖11 服務拆分速度對比Fig. 11 Service partitioning speed comparison

3.2 非集中式服務組合性能評估

在集中式服務組合中，業務過程在中心控制器內執行。業務過程拆分后，使用Web 服務構造將對中心控制器內的過程進行分散配置。本節將討論關于非集中式服務組合的配置、部署、實現和性能。

3.2.1 實驗環境

該實驗使用3臺計算機作為服務端，1臺計算機作為客戶端。服務端使用Flask［24］和Flask-RESTful［25］將業務過程實現為Web 服務，客戶端采用Apache JMeter［26］作為負載測試工具，用于分析和測量服務性能。整個實驗環境總結在表2 中。

表2 實驗環境Tab. 2 Experimental environment

3.2.2 服務組合部署

非集中式服務組合的服務可以部署在任意不同的服務器上，但這種配置可能會引起額外的網絡負載、更多的測試和維護工作。因此，可以將拆分出來的服務和被調用的服務組件部署在相同環境中。

如圖12 的部署情況，圖12（a）為集中服務組合的部署情況，中心控制器內的業務過程實現為“P”，服務組件實現為“S1”“S2”以及“S3”；圖12（b）為非集中式服務組合的部署情況。

圖12 服務組合的組件部署Fig. 12 Component deployment of service compositions

過程模型包含數據依賴和控制依賴。由于服務是由消息驅動，所以服務之間的依賴被實現成消息傳遞。

3.2.3 實驗結果

本部分將測試圖2 過程模型的集中和非集中服務組合性能。測試實驗設置為統計字符串中的各字母出現次數，請求數據為指定長度大小的隨機字符串，結果返回各字母的出現次數以及次數最高的字母。在圖2 過程模型中，“F1”“F2”和“F3”分別調用服務組件“S1”“S2”和“S3”，“F0”用于接收客戶端的請求，“F4”用于返回客戶端需要的內容。

“S1”服務設置為返回指定長度的字符串，“S2”服務設置為返回給定字符串中各字母的出現次數，“S3”服務設置為返回給定字符串中出現次數最高的字母。“P1”設置為隨機生成指定長度的字符串，“P5”設置為統計字符串中各字母的出現次數。

非 集 中 式 服 務 組 合 中，組 件“F0P0”“P1P2F2”“P3P4P5P6F1”“F3”以及“P7F4”被實現為服務。

在集中式服務組合中，將業務過程“P”部署在服務器1中，將“S1”和“S3”部署在服務器2 中，將“S2”部署在服務器3中。而在非集中式服務組合中，將“F0P0”和“P7F4”部署在服務器1 中，將“P3P4P5P6F1”“F3”“S1”和“S3”部署在服務器2中，將“P1P2F2”和“S2”部署在服務器3中。

在測試時，客戶端請求速率從10 qps（每秒請求數）到45 qps。數據集包括0.1 KB、1 KB、50 KB、100 KB、150 KB和200 KB 固定大小的隨機字符串。實驗每次測試時間60 s，重復測試3 次取得平均響應時間和吞吐量，100 KB 到150 KB的請求結果如表3所示。

表3 兩種服務組合在不同請求速率下的實驗結果Tab. 3 Experimental results of two service compositions with different request rates

兩種組合方式的請求速率和平均響應時間關系如圖13所示。由圖表可得，隨著請求速率的增加，集中式服務組合的響應時間急速增加并且吞吐量出現下降；而非集中式服務組合保持良好的響應時間和吞吐量。

表4 列出在30 qps、35 qps 和40 qps 請求速率下，不同請求數據量的平均響應時間和吞吐量變化情況。

表4 兩種服務組合在不同請求數據量下的實驗結果Tab. 4 Experimental results of two service compositions with different request data size

圖14 表示請求速率為30 qps 時，請求數據量大小和響應時間的關系。從圖表可以看出，在相同請求速率下，集中式服務組合的響應時間隨請求數據量增加而快速增加，到達瓶頸后集中式服務組合的吞吐量開始出現下降；而非集中式服務組合保持良好的平均響應時間和吞吐量。

由于非集中式服務組合可以減少服務和數據之間的交互，因此將交互的服務組件部署在同一服務器上可以改善組合中的傳輸情況。上述實驗結果表明，使用算法1 拆分過程模型產生的非集中式服務組合相比較集中式服務組合具有更好的服務性能。

圖13 不同請求速率下的響應時間變化Fig. 13 Response time variations with different request rates

圖14 不同請求數據大小下的響應時間變化Fig. 14 Response time variations with different request data sizes

4 結語

集中式服務組合容易在中心控制器上出現瓶頸，本文基于過程拆分技術提出一種構建非集中式服務組合方法。該方法將中心控制器內的業務過程建模為類型有向圖，并基于圖轉換的方法來重組過程模型。經過實驗驗證，本文所提的方法能有效拆分中心控制器內的業務過程；并且在部署得當的情況下，所生成的非集中式服務組合相比較原有集中式服務組合具有更高的執行效率。