服務流程檢索技術研究

張 林，吳曉銘，王凌陽

ZHANG Lin1,WU Xiaoming2,WANG Lingyang2

1.武漢大學 軟件工程國家重點實驗室，武漢430072

2.武漢大學 計算機學院，武漢430072

1.State Key Lab of Software Engineering,Wuhan University,Wuhan 430072,China

2.College of Computer,Wuhan University,Wuhan 430072,China

1 引言

在工作流和服務計算領域，流程片段的重用研究具有很大的研究價值。許多研究關注于如何分割和描述流程片段。例如，Vanhatalo[1]提出一種將原流程片段分割成更小的單入單出（Single-Entry-Single-Exit，SESE）片段的模型。在文獻[2]中，為更好地描述和提取片段信息，將流程片段描述成不同的零碎知識。Schumm[3]詳細討論了使用流程片段庫和集成應用的潛在影響。此外，一個全面的框架[4]關注于如何提取動態、漸進、上下文感知適應的流程片段。但是這些方法沒有考慮提取流程片段的潛在信息，特別是如何提取一個超出人工提取能力的大流程片段信息。

事實上，任意粒度的服務流程片段[5-7]都有被重用的潛力，尤其是那些已被手動編輯，且能夠直接運行的流程片段，其作用甚至高于原子服務。例如，一個僅包含順序關系的簡單服務流程S1 →S2 →S3，不僅能夠重用片 段S1 →S2 和S2 →S3，而且可以重用S1 →S2 →S3整個片段。

服務流程片段重用的目的是進一步利用現有的流程片段，即盡可能挖掘出更多的可重用子流程片段，從而滿足新的服務組合需求。此外，服務重用并未考慮重復使用的對象是否為原子或組合服務。例如，圖1 展示了一個與旅游相關的服務流程實例，它包含5 個原子服務。若一個客戶旅行乘坐火車改乘船，利用現有技術，開發人員不得不手動分析和重建全過程。盡管在上述組合服務中可以通過一個輪船訂票服務替換火車訂票服務，達到重用一些服務片段的目的，但是如果服務流程庫非常龐大，開發者很難找出哪些片段可以被重用。服務庫樣例如表1 所示。

圖1 一個服務流程樣例

表1 服務庫樣例

在不同的需求方面，為有效發現和重用服務流程片段，本文提出了一種新的索引機制（CLI）。由于其他流程關系可以被轉化為線性關系流程，所以本文中的流程都是具有線性關系的流程。首先，服務接口描述和服務之間依賴關系轉換成二進制編碼的標簽，圖2 給出對應于圖1 轉換后的標簽圖。在標簽圖中所有頂點和邊組成服務標簽樹（Service Label-tree，SL-tree），即每個流程對應于一棵SL-tree。然后，在統一實現原子服務和組合服務的檢索時，本文提出了一種新穎的數據結構，即服務標簽合并樹（SLM-tree）。這樣，搜索的服務將不僅僅局限于原子服務。通過快速計算將絕對不相關的流程片段過濾掉，剩下可能相關的流程片段，之后采用傳統考慮服務依賴性的方法進行匹配篩選。最后，擇優選取檢索到的流程片段。

圖2 轉換成標簽圖

2 CLI機制

本文僅關注于不同網絡服務的連接，而對于初始化服務流程并不重要的控制結構如if 與while 等不會過多關注。因此，本文需要犧牲一定的準確性來大幅提高服務流程片段的檢索效率。

在只考慮順序序列的情況下，流程可簡化為一個有向圖，稱為Web 服務圖（Web Service-graph，WS-graph），其中每個頂點和每條邊分別對應于Web 服務和連接服務之間的依賴關系。服務流程片段查詢類似于搜索限制寬泛的子圖匹配問題。因此，服務流程片段查詢（SFF-query）只關注于服務的輸入和輸出參數以及它們之間的依賴關系。

在WS-graph中，某個流程片段P可以用Gp=(W,E)表示，其中W={w1,w2,…,wm}是頂點集合，E={＜wi,wj＞}={＜wi.out→wj.in＞}(i，j∈m)是邊集合。每個頂點表示一個服務，每條邊代表wi和wj之間依賴關系。一個SFF-query 可以用Gq=(W′，E′)表示，如果查詢成功，則要求對Gq中任意一條邊＜wx′，wy′＞，wx′的輸入和wy′的輸出必須分別包含于Gp中服務集合的輸入集和輸出集內。

2.1 WS-graph 標簽

為便于理解，假設每個Web服務只有一個操作。WSgraph 標簽包括頂點標簽vLab(w)和邊標簽eLab(wiwj)，其中每個標簽都對應于一個二進制串。Web 服務可以描述為wi=＜wi.in，wi.out＞，其中wi.in和wi.out分別表示服務的輸入和輸出參數集。由于可以通過本體映射、近義詞替換等將服務語義概念統一，之后采用合適的哈希函數，例如DJBHash 和PJWHash，可以將服務wi編碼成統一格式的二進制位串。

給定服務w包含輸入參數集w.in={in1，in2，…，inp}和輸出參數集w.out={out1，out2，…，outq}。

vLab(w)定義如下：

eLab(wiwj)定義如下：

其中“|”表示或操作，“*”表示連接操作。對于任何服務的連接，連接服務的輸入參數必須完全滿足要求，但一些連接服務的輸出參數可以不使用。因此，在公式（2）中有q′=p≤q。

圖3 和圖4 分別顯示如何分配標簽給圖1 中天氣服務以及旅行計劃服務和旅行估價服務之間的關系。

圖3 服務標簽實例

2.2 服務標簽合并樹

通過編碼Web 服務和不同服務之間的依賴關系，WS-graph 將被轉換成一個標簽圖，稱為流程標簽圖（Flow Label-graph，FL-graph）。本節將討論如何將這些標簽組織成CLI。CLI 將提供更加便捷、高效的服務流程片段查詢，其過程僅僅使用有限的位運算組織這些標簽。

圖4 服務連接標簽實例

對于服務流程片段查詢（SFF-query），查詢條件可以轉換成一個查詢標簽圖（Query Label-graph，QL-graph），轉換過程類似于對WS-graph 轉化為FL-graph。因此要解決的本質問題是如何在FL-graph 中有效找到匹配的QL-graph。一個簡單的算法如下：

步驟1對每個vi∈V（QL-graph），找到點集Ri={ui1，ui2，…，uin}滿足條件vi&uij=vi，uij∈V（FL-graph）以及uij∈Ri。其中“&”是二進制與操作，V(*)是頂點集合。

步驟2通過依賴關系進一步驗證這些點集，最終選取一些相匹配的QL-graph。

在本文中，S-tree[8]是一種提供包含檢索功能的高度平衡樹。在S-tree 中，每一個中間結點是通過位與運算疊加所有子標簽而組成。因此，利用一棵S-tree 可以有效地完成第一步。然而，S-tree 不能支持累加服務之間的依賴關系。因此，本文提出一種新的索引結構即服務標簽樹（Service Label-tree，SL-tree），支持任意粒度的服務流程片段查詢。如圖5 所示，該圖對應于圖1 例子的一棵SL-tree。

圖5 圖1 轉化為SL-tree

盡管可以通過SL-tree 搜索任意粒度的服務流程片段，但是仍然需要檢索大量SL-tree。因此，將所有SL-tree的根結點再通過一棵S-tree 進行組織，以此進一步提高搜索流程片段的效率，這棵S-tree 定義為服務標簽合并樹（Service Label Merge-tree，SLM-tree）。此外，SLMtree 的葉結點可能是一個原子服務，但是組合服務必須有自邊，由此通過判定SLM-tree 中葉結點是否存在自邊，區分對待原子服務和組合服務的搜索。所以CLI 可以統一檢索這兩種類型服務。

3 檢索過程

本章將討論如何通過SLM-tree進行服務片段查詢。具體策略是自頂向下通過SLM-tree 在一個龐大的服務流程存儲庫中過濾尋找一些候選集，并且按照一定策略從中擇優選取。

3.1 片段檢索原理

在2.2節介紹過，一個SFF-query可以轉換為QL-graph，而SFF-query 可分為嚴格或非嚴格檢索。對于嚴格SFFquery，結果必須完全滿足查詢條件，它們可以直接被重復利用。與此相反，在非嚴格SFF-query 中，允許結果部分滿足查詢條件。由于篇幅所限，本文只介紹嚴格的SFF-query。

定義3.1對于一個FL-graphG*和一個QL-graphQ*，其 中G*，Q* 分 別 包 含Web 服 務 集 合W={w1，w2，…，wm}和U={u1，u2，…，un}，當且僅當以下條件成立時G*是滿足嚴格查詢Q*：

條件1對于任何ui∈U，存在wj∈W，使得vLab(wj).in&vLab(ui).in=vLab(wj).in并且vLab(wj).out&vLab(ui).out=vLab(wj).out。這意味著所有查詢條件的Web 服務是被包含在流程中。

條件2對Q*中的任何uiuj，在G*中，存在wiwj使得eLab(uiuj)&eLab(wiwj)=eLab(uiuj)，其中wiwj可能是一條被許多葉結點合成的邊。

利用SLM-tree 的特性，反復通過定義3.1 從上到下實現過濾操作。因為樹狀結構的每個分支都含有大量流程或原子服務，所以每一步操作都有可能過濾大量不相關結果。

3.2 使用SLM-tree

基于SLM-tree 創建的索引能夠統一實現原子和組合服務兩種查詢。事實上，原子服務查詢可以看成是僅包含一個服務的特殊SFF-query。因此，下文只詳細描述SFF-query 的步驟。

SFF-query 主要包含兩個步驟。第一步，查詢輸入標簽和輸出標簽分別與SLM-tree 的根結點標簽做位與操作，判斷是否匹配。如果匹配不成功，快速排除即可。如果查詢條件與根結點或任何內部結點匹配，由于在SLM-tree 中位或操作的模糊積累并不能表明查詢流程片段存在，所以只獲得流程片段的候選集，即許多SL-tree 根結點組成的集合。

在上一步的匹配過程中，為了快速篩選最不相關的流程片段，只考慮頂點的存在，而忽略頂點之間的依賴關系。在第二步中，將進一步利用關系標簽找到包含查詢流程片段的流程片段。如果第一步產生的候選集中某個流程片段與查詢條件中的頂點標簽和邊標簽任何一項不匹配，該流程片段將會被排除。

3.3 選取SFF

服務質量（Quality of Service，QoS）代表Web 服務的許多非功能特性，例如響應時間，吞吐量和可達性等。由于每一個服務質量特性不盡相同，根據文獻[9]需要將它們歸一化到區間[0，1]，具體公式如下：

其中公式（3）表示正向屬性歸一公式，公式（4）表示負向屬性歸一公式，vi是第i維QoS 屬性值，v′i是歸一化后的結果。

現假設某流程片段P={s1，s2，…，sn}，該流程片段總體服務質量為QoSp。針對不同QoS 屬性，QoSp的每一維屬性累加方法不相同，具體策略如表2。

表2 累加方法

為便于理解，現考慮二維屬性，例如響應時間和價格。假設經過索引機制CLI檢索出前7 個候選服務流程片段，如表3 所示。

表3 候選流程片段樣例

根據文獻[10-12]提出的紙帶模型，第一步需按照Skyline 點集合在Skyline 空間坐標系中的位置將整個Skyline 空間坐標系分成三個區域，分別為支配區域A，盲點區域B和被支配區域C。三個區域劃分事例如圖6所示，其中有7個服務片段被按照二維QoS映射至Skyline坐標系中，Skyline集合為{SFF-3，SFF-4，SFF-6，SFF-7}。

圖6 基于紙帶的Skyline坐標實例

（1）支配區域A。此區域位于Skyline 集合各點左連線的下部，包括連線部分，但不包括Skyline 上的各個服務片段點，為圖6 所示的淺藍色標有區域A的部分。在算法運行過程中，新服務片段按QoS 映射至此坐標系時，若落到區域A，則新服務片段必然會支配已經生成的Skyline 集合中某些數據點，亦即某些服務片段。此時在將新服務片段映射到坐標系中的同時，需要從原Skyline 集合中刪除被新進服務片段支配的服務片段。若無服務片段點位于支配區域A，則判斷為支配區域A的點必然為增加服務片段操作。

（2）盲點區域B。此區域位于Skyline 集合各點左連線的上部，右連線的下部，不包含左右連線，但包括Skyline 集合各點，為圖6 中標有區域B的深藍色部分。因其不歸原Skyline 各點支配，也不支配原Skyline 中的元素，所以稱為盲點區域。若新進服務片段與原Skyline無相互支配關系，則新進服務片段直接加入到Skyline集合。如果為刪除服務片段操作，則刪除的服務片段必為Skyline點。

（3）被支配區域C。此區域位于Skyline 集合各點右連線的上部，包括連線上的各點，不包括Skyline 集合各點，為圖6 中淺黃色部分標有C區域標記的部分。此區域的各點被Skyline 支配，所以稱為被支配區域。如新進服務片段位于此區域，并不影響原Skyline 各點，可直接將服務片段隱身進空間坐標系即可；若欲刪除部分位于此區域，亦不影響原Skyline，可直接將服務片段從空間坐標系刪除即可。

將Skyline 集合中按單屬性進行排序組織成屬性紙帶，在此以圖6 Skyline 空間坐標系為例，建立此集合的二維紙帶模型，所需2 條紙帶分別為響應時間紙帶和價格紙帶。其中響應時間紙帶對應坐標系的豎軸表示服務片段的響應時間，按從小到大排序；價格紙帶對應坐標系的橫軸表示服務片段的價格，按從大到小排序。圖6 Skyline 空間坐標系中Skyline 集合形成的二維紙帶模型如圖7 所示。

圖7 紙帶模型實例

計算新增服務片段或欲刪除服務片段在所有紙帶中的位置，規則如下：

規則1若變動服務片段SFF 在某一紙帶P的K編號服務片段和K+1 編號服務片段之間，規則定義SFF在紙帶P上的編號為K+0.5。

規則2若變動服務片段SFF 在某一紙帶P有與其相等的編號K，此時編號為K的服務片段與服務片段SFF 在此維度上QoS 相等。規則定義SFF 在此紙帶P上的編號為K。

規則3若變動服務片段SFF 在某一紙帶P在第一個服務片段之前，規則定義SFF 在此紙帶P上的編號為0.5。若在最后一個服務片段之后，算法定義SFF 在此紙帶P上的編號為N+0.5，其中N為此紙帶上服務片段的個數。

依據上述規則，假設現加入SFF-8 響應時間屬性與SFF-7 相等，其價格屬性與SFF-4 相等。由于SFF-7 在響應時間紙帶上的編號為1，根據規則2 得SFF-8 在響應時間紙帶上的編號為1，同理可知在價格紙帶上SFF-8 的編號為3。

落入A支配區域的變化服務片段SFF 必然會支配某個或者某些原Skyline 集合中的服務片段，根據上示紙帶模型可知，如果SFF 支配原Skyline 集合中的SFF-X服務片段，可知在響應時間和價格紙帶上的編號的值不大于SFF-X 服務片段在對應紙帶上的值，并且在某一維度SFF 的編號小于SFF-X 的編號。從上述紙帶中可知在響應時間紙帶上比SFF-8 差或相等集合為{SFF-3，SFF-4，SFF-6，SFF-7}，在價格紙帶上比SFF-8 差或相等的集合為{SFF-4，SFF-6，SFF-7}。當兩個集合有交集時可知原Skyline中有被SFF-8支配的服務片段，所以SFF-8服務片段落至A支配區域，同理，可推出落入B盲點區域或者C被支配區域編碼的關系。

4 實驗分析

本文中的索引CLI 和SFF-query 算法均采用C++實現。設計并開展了一系列評估準確性和效率的實驗，實驗使用的個人電腦配置是CPU：2.8 GHz和內存：4 GB。

通過CTG[13]生成了一個包含大約20 萬個流程片段和1.05 億個原子服務的服務庫，每個流程片段包含100～300 個不等的隨機原子服務。此外，每個服務包含5～10個輸入或輸出參數。

CLI 的性能可能與許多參數有關，如在流程庫中流程的數量（Amount Process，AP）、原子服務的平均數目（Average Atomic Service，AAS）、每個流程之間服務的依賴關系（Process Relation，PR）、抽象服務平均數量（Average abstract Service，AS）、每次查詢條件依賴關系（Query Relation，QR）、標簽編碼的長度（Length Label，LL）和SLM-tree 中每個結點的孩子結點數量范圍（Number range of Children，NC）NC=[r1，r2]。r1 是SLM-tree 內任意結點的孩子最小數目，r2 是任意結點的孩子最大數目。在本章中，通過改變上面不同參數進行了一系列評估性能的實驗，所有實驗重復5 次，每一種情況取平均值。LL 是CLI 最重要的參數指標之一，圖8 和圖9 分別顯示通過采用不同的LL 對效率和準確性的影響，其中AP=500 KB，AAS=100 和NC=[8，16]。

圖8 不同LL 效率比較

圖9 不同LL 準確性比較

如圖8 所示，查詢效率明顯隨LL的增加而提高，因為高層SLM-tree 將明顯不相干的流程片段較早過濾掉，但是更大的LL消耗更多內存，所以需要找到效率和內存成本之間的平衡點。此外，當LL＞240 時，所有曲線顯示突然發生強烈變化，現象出現原因是當CLI 的規模大于可用內存時，額外的I/O 操作降低了效率。

從圖9 可以看出，準確性隨著標簽長度增加而提高。就像其他標簽樹，如果LL很短，將節省大量內存空間，裝載更多的索引結點到內存中。但是，同時也導致更多的服務或關系被映射到相同的標簽中，短小的LL將導致標簽重復，造成精度降低。此外，更復雜的查詢條件依賴于較長的LL，因為需要更多的比特位確保查詢標簽的真實性。總結圖8 和圖9 中實驗結果，最終選擇LL=218，可以支持非常復雜的查詢，并且將被用于后續的實驗中。

NC=[r1，r2]直接影響SLM-tree 深度，是另一個重要的參數指標。較大的NC將獲得更高的查詢效率，然而這樣會導致大多數無用的結果不能被SLM-tree 的高層過濾掉。所以，有必要確定r1 和r2 的合適值以及它們之間的比率。如圖10 所示，當AP=500 KB 和AAS=100 時，對所有AS來說其效率更穩定的比率為1∶2。此外，選擇圖10 中穩定性最高的3 個不同NC的曲線，分析它們對于不同規模的流程不同表現。圖11 展示了它們效率與靈敏度之間的關系。雖然當AP＜300 KB 時，r1=8 和r2=16 的曲線不是最高效率的曲線，但對更大規模流程顯示出更好的優越性。最終，本文確定NC=[8，16]。

圖10 不同NC 穩定性比較

圖11 不同NC 效率比較

5 結束語

在傳統服務計算研究領域[14-15]中，很少考慮服務流程的重用。但是，能夠最大努力地重用流程片段，不僅能夠提高服務組合的效率，而且對企業也可以節省人力和物力成本。本文提出了一種可變索引機制CLI，它能夠檢索任意粒度的流程片段，并達到重用的目的以滿足更復雜的業務需求。結合數字標簽和編碼匹配技術，CLI 可以同時實現原子服務及組合服務的檢索。最后通過一系列的實驗驗證了方法的可行性和有效性。今后工作主要目標是針對非嚴格SFF-query，進一步提高流程片段的利用率。

[1] Vanhatalo J，V?lzer H，Leymann F.Faster and more focused control-flow analysis for business process models through sese decomposition[M].Berlin Heidelberg：Springer，2007.

[2] Eberle H，Unger T，Leymann F.Process fragments[M]//On the Move to Meaningful Internet Systems：OTM 2009.Berlin Heidelberg：Springer，2009：398-405.

[3] Schumm D，Karastoyanova D，Kopp O，et al.Process fragment libraries for easier and faster development of processbased applications[J].Journal of Systems Integration，2011，2（1）：39-55.

[4] Bucchiarone A，Marconi A，Pistore M，et al.Dynamic adaptation of fragment-based and context-aware business processes[C]//2012 IEEE 19th International Conference on Web Services（ICWS），2012：33-41.

[5] Granell C，Gould M，Gr?nmo R，et al.Improving reuse of web service compositions[M]//E-Commerce and Web Technologies.Berlin Heidelberg：Springer，2005：358-367.

[6] Sonntag M，Karastoyanova D，Leymann F.The missing features of workflow systems for scientific computations[C]//Software Engineering（Workshops），2010：209-216.

[7] Granell C，Ramos J F.An object-oriented approach to GI web service composition[C]//15th International Workshop on Database and Expert Systems Applications，2004：835-839.

[8] Deppisch，Uwe.S-tree：a dynamic balanced feature index for offline retrieval[C]//SIGIR，1986.

[9] Alrifai M，Skoutas D，Risse T.Selecting skyline services for QoS-based web service composition[C]//Proceedings of the 19th International Conference on World Wide Web，2010：11-20.

[10] 胡建強，李涓子，廖桂平.一種基于多維服務質量的局部最優服務選擇模型[J].計算機學報，2010，33（3）：526-534.

[11] Ma Y，Chen L，Hui J，et al.Cbbcm：clustering based automatic service composition[C]//2011 IEEE International Conference on Services Computing（SCC），2011：354-361.

[12] Kolb J，Kammerer K，Reichert M.Updatable process views for user-centered adaption of large process models[M]//Service-Oriented Computing.Berlin Heidelberg：Springer，2012：484-498.

[13] Zheng Z，Zhang Y，Lyu M R.Distributed qos evaluation for real-world web services[C]//2010 IEEE International Conference on Web Services（ICWS），2010：83-90.

[14] Yu T，Zhang Y，Lin K J.Efficient algorithms for Web services selection with end-to-end QoS constraints[J].ACM Transactions on the Web（TWEB），2007，1（1）.

[15] Yang J，Papazoglou M P.Service components for managing the life-cycle of service compositions[J].Information Systems，2004，29（2）：97-125.