匡雯 顧佳燕

摘 要：大規(guī)模服務(wù)存儲(chǔ)結(jié)構(gòu)模型研究中，多級(jí)索引模型被證明是非常高效的存儲(chǔ)結(jié)構(gòu)，具有穩(wěn)定、易管理、易維護(hù)、低冗余的優(yōu)勢(shì)。目前的研究建立在服務(wù)調(diào)用概率平均分布這一假設(shè)之上，然而現(xiàn)實(shí)服務(wù)調(diào)用是不等概率的，這意味著多級(jí)索引模型在服務(wù)調(diào)用的不等概率情況下還不是最優(yōu)。為提高服務(wù)調(diào)用不等概率條件下多級(jí)索引模型的檢索效率，通過(guò)分析多級(jí)索引模型的檢索特性，推導(dǎo)出檢索操作的時(shí)間復(fù)雜度函數(shù)。利用函數(shù)極值，設(shè)計(jì)了不等概率條件下鍵值的優(yōu)化選擇方法。實(shí)驗(yàn)結(jié)果顯示，該方法比隨機(jī)選鍵方法提高檢索效率15%左右，證明優(yōu)化選擇方法能有效提高服務(wù)檢索效率。

關(guān)鍵詞：服務(wù)計(jì)算;服務(wù)檢索;服務(wù)存儲(chǔ);多級(jí)索引模型

DOI：10. 11907/rjdk. 181798

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）001-0040-05

Abstract： Many works studied storage structures of services. Among them， a multilevel index model was proved to be very efficient for service storage for large-scale service repositories. It has the advantages of non-redundancy， stability， being easy managed and maintained. Previous works are proposed and evaluated on the assumption that the probability of service invoking is equal. However， it is too strict in reality， which means the efficiency of service retrieval is not optimal. In order to improve the efficiency of service retrieval under the condition of unequal probability of service invoking， the time complexity of the service retrieval is deduced and an optimal key selection method is proposed according to the function. Our experimental results show that the optimal key selection method reduces 15% of retrieval time. Therefore， the effectiveness and efficiency of the proposed optimal key selection method under unequal probability of service invoking are valid.

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和產(chǎn)業(yè)規(guī)模的不斷擴(kuò)大，Web服務(wù)呈現(xiàn)高速增長(zhǎng)趨勢(shì)[1]，這對(duì)軟件產(chǎn)業(yè)提出了更高要求。隨時(shí)可用性、松散耦合性、靈活的可擴(kuò)展性和分布式以及更高的可重用性，是現(xiàn)代軟件產(chǎn)業(yè)的突出特點(diǎn)[2]，服務(wù)組合是研究熱點(diǎn)。Web服務(wù)組合指提供復(fù)雜新功能的組合服務(wù)過(guò)程[3]。工作流技術(shù)[4-6]、自動(dòng)機(jī)[7]、Petri網(wǎng)[8-9]、人工智能規(guī)劃[10]等理論和方法在服務(wù)組合領(lǐng)域都有應(yīng)用。一些研究成果提出采用自己的服務(wù)存儲(chǔ)結(jié)構(gòu)減少服務(wù)組合時(shí)間，如Graph結(jié)構(gòu)[11-13]、倒排索引[14]、Service Net[15-17]等，但仍存在一些缺陷，如復(fù)雜度高、可靠性差、用戶(hù)滿(mǎn)意度低等。

Wu等[2]基于等價(jià)類(lèi)、等價(jià)劃分、商集理論，提出了一種大規(guī)模服務(wù)存儲(chǔ)結(jié)構(gòu)——多級(jí)索引模型， Wu，Xu等[2，18-20]提到的鍵值選擇策略與筆者先前[21]改進(jìn)的鍵值選擇策略，都是在服務(wù)等概率調(diào)用情況下的選擇策略，但這種假設(shè)在實(shí)際中很難實(shí)現(xiàn)。由于某些服務(wù)“很火”且經(jīng)常被調(diào)用，其它服務(wù)“很冷”且很少被調(diào)用，導(dǎo)致服務(wù)調(diào)用很可能是不等概率的，所以本文設(shè)計(jì)不等概率模塊，完善不等概率的多級(jí)索引模型并提出不等概率模型上的鍵值選擇策略。

1 多級(jí)索引模型

1.1 服務(wù)基本定義

定義1 一個(gè)服務(wù)s是一個(gè)三元組[s=s，？s，？O]，其中[s]表示服務(wù)的輸入?yún)?shù)集合，[s]表示服務(wù)的輸出參數(shù)集合，O表示服務(wù)其它元素集合，如服務(wù)聲譽(yù)等。

服務(wù)檢索指根據(jù)用戶(hù)需求接受一組參數(shù)，并返回由該組參數(shù)調(diào)用的一組服務(wù)。根據(jù)當(dāng)前參數(shù)集合查找到可發(fā)生服務(wù)的集合，通過(guò)服務(wù)組合和發(fā)現(xiàn)來(lái)調(diào)用，定義如下：

定義2 服務(wù)的檢索運(yùn)算可定義為[Re（A，？S）={s | ][s？A∧s∈S}]，其中，A為一個(gè)參數(shù)集合，S表示服務(wù)集合，s表示一個(gè)服務(wù)，[Re（A，？S）]表示從服務(wù)集S中找出服務(wù)的輸入?yún)?shù)均包含在A中的所有服務(wù)，即在狀態(tài)A下可以引發(fā)的所有服務(wù)。

定義3 用戶(hù)需求可定義為一個(gè)二元組[Q=（Qp，Qr）]，其中Qp表示用戶(hù)可提供的參數(shù)集合，Qr表示用戶(hù)需要的參數(shù)集合。

1.2 多級(jí)索引及模型

大規(guī)模服務(wù)存儲(chǔ)庫(kù)通過(guò)服務(wù)的輸入輸出參數(shù)進(jìn)行服務(wù)組合操作。由于大規(guī)模服務(wù)庫(kù)可能存在一些包含相同輸入輸出參數(shù)的服務(wù)集合，必然導(dǎo)致服務(wù)組合存在大量冗余。

由于等價(jià)類(lèi)和等價(jià)元素具有完整性、無(wú)冗余性、正確性特征，Wu等[2]基于等價(jià)類(lèi)和等價(jià)元素關(guān)系，將多級(jí)索引模型分為4個(gè)級(jí)別，分別是第1級(jí)索引（The First Level Index，L1 I）：如果服務(wù)s∈Cs，那么服務(wù)s和相似類(lèi)Cs之間存在一個(gè)索引鏈接;第2級(jí)索引（The Second Level Index，L2 I）：如果相似類(lèi)Cs∈Cis，那么相似類(lèi)Cs和半相似類(lèi)Cis之間存在一個(gè)索引鏈接;第3級(jí)索引（The Third Level Index，L3I）：如果半相似類(lèi)Cis∈Ck，那么半相似類(lèi)Cis和鍵類(lèi)Ck之間存在一個(gè)索引鏈接;第4級(jí)索引（The Fourth Level Index，L4 I）：對(duì)于“Ck∈[？3]，”k∈К， 如果fk（Ck）=k，那么在鍵類(lèi)Ck和鍵k之間存在一條索引鏈接。

Wu等[2]基于4個(gè)索引級(jí)別提出了3種索引模型：全索引包括L1I-L4I;中級(jí)索引包括L2I-L4I;初級(jí)索引包括L3I和L4I。在多級(jí)索引服務(wù)存儲(chǔ)模型中，基于等價(jià)關(guān)系和等價(jià)類(lèi)劃分的各類(lèi)索引函數(shù)關(guān)系，可以有效避免相互之間服務(wù)信息冗余情況，從而解決重復(fù)檢索帶來(lái)的模型效率問(wèn)題。

為了應(yīng)對(duì)不同的服務(wù)存儲(chǔ)倉(cāng)庫(kù)情形，多級(jí)索引服務(wù)存儲(chǔ)模型提供了彈性部署方案，對(duì)于不同的存儲(chǔ)狀況和用戶(hù)需求采用不同方案。彈性部署方案包括基于L1I-L4I的完整模型、基于L2I-L4I中級(jí)模型和基于L3I-L4I的初級(jí)模型。L1I-L4I構(gòu)建了一個(gè)服務(wù)的多級(jí)索引模型，總體結(jié)構(gòu)如圖1所示。由于每級(jí)索引是完整的、無(wú)冗余的，所以整個(gè)索引模型也是完整的、無(wú)冗余的。

2 不等概率模塊設(shè)計(jì)與實(shí)現(xiàn)

2.1 不等概率下的多級(jí)索引模型結(jié)構(gòu)

服務(wù)的數(shù)據(jù)結(jié)構(gòu)包括服務(wù)及其輸入輸出、四級(jí)索引關(guān)系。下面以一組簡(jiǎn)單且易于理解的Web服務(wù)為例說(shuō)明服務(wù)參數(shù)之間的關(guān)系。表1為一組Web服務(wù)例子，包括4個(gè)服務(wù)及輸入輸出參數(shù)。

2.2 服務(wù)參數(shù)的不等概率設(shè)計(jì)

在多級(jí)索引模型中，輸出參數(shù)對(duì)檢索操作沒(méi)有影響，因此本文只討論構(gòu)建服務(wù)的輸入?yún)?shù)不等概率情況。每組服務(wù)都有一組輸入?yún)?shù)，服務(wù)輸入?yún)?shù)的不等概率以?xún)蓚€(gè)服務(wù)s1、s2舉例：s1的輸入?yún)?shù)為{a， b}，輸出參數(shù)為{g， h}，s2的輸入?yún)?shù)為{a， c}，輸出參數(shù)為{j， k}，那么輸入?yún)?shù)a被使用兩次，而b、c只被使用一次。在大規(guī)模服務(wù)存儲(chǔ)庫(kù)中，必然存在有的服務(wù)部分輸入?yún)?shù)相同，有的服務(wù)輸入?yún)?shù)完全不同，這就是服務(wù)輸入?yún)?shù)的不等概率情況，其關(guān)鍵算法如下：

2.3 檢索參數(shù)的不等概率設(shè)計(jì)

由于服務(wù)調(diào)用是通過(guò)對(duì)檢索參數(shù)進(jìn)行查詢(xún)實(shí)現(xiàn)的，因此服務(wù)被調(diào)用的概率不相等，即檢索參數(shù)不等于概率分布。服務(wù)檢索參數(shù)由用戶(hù)請(qǐng)求調(diào)用行為產(chǎn)生，每個(gè)用戶(hù)的調(diào)用行為是隨機(jī)的，同時(shí)各用戶(hù)調(diào)用行為之間基本獨(dú)立，對(duì)所有用戶(hù)的調(diào)用行為進(jìn)行統(tǒng)計(jì)可得到各個(gè)服務(wù)的檢索概率。滿(mǎn)足要素獨(dú)立、隨機(jī)和相加3個(gè)屬性，用戶(hù)檢索請(qǐng)求數(shù)據(jù)的分布較接近于正態(tài)分布。表2為jumpshot設(shè)備的主要搜索服務(wù)情況統(tǒng)計(jì)，從理論和統(tǒng)計(jì)數(shù)據(jù)可得出檢索參數(shù)的非等概率分布近似收斂于正態(tài)分布的結(jié)論。

將實(shí)驗(yàn)所產(chǎn)生的檢索參數(shù)，如樣本容量為3200，均值為500，標(biāo)準(zhǔn)差分別為200的檢索參數(shù)集合，導(dǎo)出到Excel并用spss統(tǒng)計(jì)工具分析，結(jié)果如圖4所示。顯然這3200個(gè)檢索參數(shù)基本符合正態(tài)分布趨勢(shì)。

3 鍵值選擇策略設(shè)計(jì)與實(shí)現(xiàn)

3.1 鍵定義

初級(jí)索引包括L3I和L4I，L3I和L4I是基于鍵構(gòu)造的，鍵是多級(jí)索引結(jié)構(gòu)中的一個(gè)創(chuàng)新性概念。在多級(jí)索引模型的添加操作中引入鍵，不僅能有效移除冗余，而且能提高添加和檢索操作效率。Wu等[2]提出最原始的鍵值選擇策略，簡(jiǎn)稱(chēng)為原始選鍵策略。筆者在文獻(xiàn)[21]中對(duì)該策略進(jìn)行改進(jìn)，簡(jiǎn)稱(chēng)為隨機(jī)選鍵策略。本文提出服務(wù)調(diào)用不等概率情況下的多級(jí)索引模型，并基于此提出一種新型的鍵值選擇策略。

鍵在L3I和L4I上部署，由于初級(jí)索引模型、中級(jí)索引模型、全索引模型都包含第三和第四級(jí)索引，因此本文提出的鍵值策略將在初級(jí)索引模型上進(jìn)行部署和實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果和效率分析同樣適用于中級(jí)和全索引模型。

圖5顯示了初級(jí)索引結(jié)構(gòu)。S是一個(gè)服務(wù)存儲(chǔ)庫(kù)，當(dāng)s被添加到S中時(shí)，鍵值選擇方法會(huì)為每個(gè)服務(wù)選擇鍵值。鍵值是用作索引條目的參數(shù)。如果si和sj具有相同的鍵，則它們將被分類(lèi)到相同的鍵值類(lèi)別中。Ck表示一個(gè)鍵值類(lèi)，它是一組具有相同鍵值的服務(wù)，[？3]表示所有鍵值類(lèi)，К表示所有鍵值類(lèi)的鍵值集合。

3.3 鍵值選擇算法設(shè)計(jì)

初級(jí)索引模型中對(duì)服務(wù)的檢索過(guò)程根據(jù)用戶(hù)提出的檢索參數(shù)集，先對(duì)鍵集合進(jìn)行檢索，比較檢索參數(shù)集和鍵集合中的鍵，找到符合的鍵類(lèi)。每個(gè)鍵類(lèi)對(duì)應(yīng)一些服務(wù)，對(duì)這些服務(wù)進(jìn)行比較，找到請(qǐng)求的服務(wù)，并返回用戶(hù)需要的參數(shù)集合。結(jié)合理論分析，不等概率情況下提高檢索效率可以盡可能縮短整體調(diào)用時(shí)間，即整體調(diào)用次數(shù)，而整體調(diào)用次數(shù)取決于每個(gè)鍵類(lèi)的調(diào)用次數(shù)。

由于鍵的調(diào)用概率和調(diào)用次數(shù)事前未知，那么不等概率下，提高檢索操作的效率可從減少服務(wù)比較時(shí)間著手，即保持每個(gè)鍵對(duì)應(yīng)的服務(wù)個(gè)數(shù)盡可能少。首先對(duì)比鍵集合和輸入?yún)?shù)集，選擇一個(gè)鍵集合中沒(méi)有的輸入?yún)?shù)作為鍵，如果該服務(wù)的所有輸入?yún)?shù)在鍵集合中都包含了，就遍歷每個(gè)輸入?yún)?shù)作為鍵對(duì)應(yīng)的服務(wù)個(gè)數(shù)，選擇一個(gè)對(duì)應(yīng)服務(wù)個(gè)數(shù)最少的作為該服務(wù)的鍵。為方便與其它鍵值選擇方法進(jìn)行對(duì)比，將此方法命名為整體最優(yōu)鍵值選擇方法。整體最優(yōu)鍵值選擇算法設(shè)計(jì)如下：

4 實(shí)驗(yàn)結(jié)果與分析

本系統(tǒng)開(kāi)發(fā)軟件環(huán)境：Microsoft Visual Studio 2012中的控制臺(tái)應(yīng)用程序和Windows窗體應(yīng)用程序，開(kāi)發(fā)語(yǔ)言為Visual C#，采用面向?qū)ο箝_(kāi)發(fā)技術(shù)。各個(gè)組成部分耦合性低，從應(yīng)用層模塊到結(jié)構(gòu)層模塊均可單獨(dú)修改、升級(jí)或替換。實(shí)驗(yàn)步驟：首先根據(jù)服務(wù)參數(shù)和檢索參數(shù)不等概率分布算法進(jìn)行編碼，實(shí)現(xiàn)不等概率下的多級(jí)索引模型搭建;接著將整體最優(yōu)選鍵方法編碼實(shí)現(xiàn)，與等概率下吳等[2]提出的原始選鍵方法及筆者之前提出的優(yōu)化過(guò)的選鍵方法——隨機(jī)選鍵方法[21]進(jìn)行檢索效率比較。

4.1 基礎(chǔ)參數(shù)設(shè)置

生成10個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集包括20 000個(gè)服務(wù)，令n=20 000;參數(shù)集合大小是1 000，令m=1 000;每個(gè)服務(wù)有10個(gè)輸入?yún)?shù)，令q=10;每個(gè)檢索請(qǐng)求包括32個(gè)參數(shù)，令r=32;數(shù)據(jù)集包含100個(gè)檢索請(qǐng)求。

4.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

表3總結(jié)了服務(wù)輸入?yún)?shù)和檢索參數(shù)不等概率情況下，3種方法在初級(jí)索引模型上的檢索效率。服務(wù)輸入?yún)?shù)不等概率條件下，整體最優(yōu)選鍵方法與隨機(jī)[21]、原始選鍵方法[2]相比，檢索效率提高20%左右;服務(wù)檢索參數(shù)不等概率條件下，整體最優(yōu)選鍵方法與隨機(jī)[21]、原始選鍵方法[2]相比檢索效率提高15%左右。因此不等概率情況下，整體最優(yōu)選鍵方法是最優(yōu)方法。

5 結(jié)語(yǔ)

本文針對(duì)服務(wù)調(diào)用頻率不同的情況，提出了多級(jí)索引模型的新的鍵值選擇方法，完善不等概率下的多級(jí)索引模型，使其更貼近實(shí)際情況。從理論和實(shí)驗(yàn)上驗(yàn)證了新方法的高效性。通過(guò)在初級(jí)索引模型上與原始、隨機(jī)選鍵方法比較，發(fā)現(xiàn)不等概率下整體最優(yōu)選鍵方法可縮短檢索操作時(shí)間，提高檢索效率，在檢索參數(shù)重復(fù)率較高的情況下效果更佳。

參考文獻(xiàn)：

[1] SERRAI W，ABDELLI A，MOKDAD L，et al. Towards an efficient and a more accurate web service selection using MCDM methods[J]. Journal of Computational Science， 2017（22）： 253-267.

[2] WU Y， YAN C， DING Z， et al. A multilevel index model to expedite web service discovery and composition in large-scale service repositories[J]. IEEE Transactions on Services Computing， 2016， 9（3）： 330-342.

[3] SHENG Q Z， QIAO X， VASILAKOS A V， et al. Web services composition： a decades overview[J]. Information Sciences， 2014（280）： 218-238.

[4] CASATI F， ILNICKI S， JIN L J， et al. Adaptive and dynamic service composition in eFlow[J]. Seminal Contributions to Information Systems Engineering，2000（1789）： 13-31.

[5] SCHUSTER H， GEORGAKOPOULOS D， CICHOCKI A， et al. Modeling and composing service-based and reference process-based multi-enterprise processes[M]. Berlin： Springer publishing international， 2000.

[6] CASATI F， SAYAL M， SHAN M C. Developing e-services for composing e-services[J]. Lecture Notes in Computer Science， 2001（2068）： 171-186.

[7] BERARDI D， CALVANESE D， GIACOMO G D， et al. Automatic service composition based on behavioral descriptions[J]. International Journal of Cooperative Information Systems， 2005， 14（4）： 333-376.

[8] BALDAN B， CORRADINI A， EHRIG H， et al. Compositional semantics for open Petri nets based on deterministic processes[J]. Mathematical Structures in Computer Science， 2001， 15（1）： 1-35.

[9] HAMADI R， BENATALLAH B. A Petri net-based model for web service composition[C]. Australasian Database Conference， 2003： 191-200.

[10] WU D， PARSIA B， SIRIN E， et al. Automating DAML-S web services composition using SHOP2 [J]. Lecture Notes in Computer Science， 2003（2870）：195-210.

[11] WAN Z， WANG P. A novel pattern based dynamic service composition framework[C]. IEEE International Conference on Services Computing， 2016： 235-242.

[12] PUKHKAIEV D，OLEKSENKO O，KOT T，et al. Advanced approach to web service composition[M]. Berlin： Springer International Publishing， 2015.

[13] CHATTOPADHYAY S，BANERJEE A，BANERJEE N. A scalable and approximate mechanism for web service composition[C]. IEEE International Conference on Web Services， 2015： 9-16.

[14] KUANG L，LI Y，WU J，et al. Inverted indexing for composition-oriented service discovery[C]. IEEE International Conference on Web Services，2007： 257-264.

[15] LALEH T，PAQUET J，MOKHOV S A，et al. Efficient constraint verification in service composition design and execution （Short Paper）[M]. Rhodes：On the Move to Meaningful Internet Systems： OTM 2016 Conferences，2016.

[16] JEONG H Y，YI G， PARK J H. A service composition model based on user experience in Ubi-cloud comp[J]. Telecommunication Systems， 2016， 61（4）：1-11.

[17] SUNAINA X，KAMATH S S. Enhancing service discovery using cat swarm optimization based web service clustering[J]. Perspectives in Science， 2016， 8（C）： 715-717.

[18] WU Y，YAN C， DING Z， et al. A relational taxonomy of services for large scale service repositories[C]. IEEE International Conference on Web Services， 2012： 644-645.

[19] WU Y，YAN C G，LIU L，et al. An adaptive multilevel indexing method for disaster service discovery[J]. IEEE Transactions on Computers， 2015， 64（9）： 2447-2459.

[20] XU W， WU Y， LIU L. Performance analysis of multilevel indices for service repositories[C]. International Conference on Semantics， Knowledge and Grids， 2016： 103-108.

[21] KUANG W， WU Y， LIU L. Key selection for multilevel indices of large-scale service repositories[C]. IEEE/ACM International Conference on Big Data Computing， Applications and Technologies， 2017：139-144.