基于不等概率的多級索引模型及其鍵值選擇策略研究

匡雯 顧佳燕

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

關鍵詞：服務計算;服務檢索;服務存儲;多級索引模型

DOI：10. 11907/rjdk. 181798

中圖分類號：TP301文獻標識碼：A文章編號：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)技術的飛速發(fā)展和產(chǎn)業(yè)規(guī)模的不斷擴大，Web服務呈現(xiàn)高速增長趨勢[1]，這對軟件產(chǎn)業(yè)提出了更高要求。隨時可用性、松散耦合性、靈活的可擴展性和分布式以及更高的可重用性，是現(xiàn)代軟件產(chǎn)業(yè)的突出特點[2]，服務組合是研究熱點。Web服務組合指提供復雜新功能的組合服務過程[3]。工作流技術[4-6]、自動機[7]、Petri網(wǎng)[8-9]、人工智能規(guī)劃[10]等理論和方法在服務組合領域都有應用。一些研究成果提出采用自己的服務存儲結構減少服務組合時間，如Graph結構[11-13]、倒排索引[14]、Service Net[15-17]等，但仍存在一些缺陷，如復雜度高、可靠性差、用戶滿意度低等。

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

1 多級索引模型

1.1 服務基本定義

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

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

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

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

1.2 多級索引及模型

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

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

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

為了應對不同的服務存儲倉庫情形，多級索引服務存儲模型提供了彈性部署方案，對于不同的存儲狀況和用戶需求采用不同方案。彈性部署方案包括基于L1I-L4I的完整模型、基于L2I-L4I中級模型和基于L3I-L4I的初級模型。L1I-L4I構建了一個服務的多級索引模型，總體結構如圖1所示。由于每級索引是完整的、無冗余的，所以整個索引模型也是完整的、無冗余的。

2 不等概率模塊設計與實現(xiàn)

2.1 不等概率下的多級索引模型結構

服務的數(shù)據(jù)結構包括服務及其輸入輸出、四級索引關系。下面以一組簡單且易于理解的Web服務為例說明服務參數(shù)之間的關系。表1為一組Web服務例子，包括4個服務及輸入輸出參數(shù)。

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

在多級索引模型中，輸出參數(shù)對檢索操作沒有影響，因此本文只討論構建服務的輸入?yún)?shù)不等概率情況。每組服務都有一組輸入?yún)?shù)，服務輸入?yún)?shù)的不等概率以兩個服務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ī)模服務存儲庫中，必然存在有的服務部分輸入?yún)?shù)相同，有的服務輸入?yún)?shù)完全不同，這就是服務輸入?yún)?shù)的不等概率情況，其關鍵算法如下：

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

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

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

3 鍵值選擇策略設計與實現(xiàn)

3.1 鍵定義

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

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

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

3.3 鍵值選擇算法設計

初級索引模型中對服務的檢索過程根據(jù)用戶提出的檢索參數(shù)集，先對鍵集合進行檢索，比較檢索參數(shù)集和鍵集合中的鍵，找到符合的鍵類。每個鍵類對應一些服務，對這些服務進行比較，找到請求的服務，并返回用戶需要的參數(shù)集合。結合理論分析，不等概率情況下提高檢索效率可以盡可能縮短整體調用時間，即整體調用次數(shù)，而整體調用次數(shù)取決于每個鍵類的調用次數(shù)。

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

4 實驗結果與分析

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

4.1 基礎參數(shù)設置

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

4.2 實驗結果對比分析

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

5 結語

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

參考文獻：

[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.