基于分布式哈希表的协作式Web服务组合

摘要：集中式的基于案例推理（CBR）应用于感知服务质量（QoS）的Web服务组合时，面临信息维护量大、节点负载高、中心失效等问题。为解决上述问题，提出了基于分布式哈希表（DHT）的协作式Web服务组合方法COCO，利用哈希函数和空间填充曲线（SFC）将组合服务的工作流和服务质量映射为一维数据键，并利用底层DHT Overlay以PeertoPeer的方式查询满足用户请求的已知组合服务，一次成功查询可获得同时满足功能性要求和非功能性要求的组合服务。实验结果表明，COCO在查询时延和查询命中率方面均有较好性能，适用于大规模网络计算环境。

关键词：Web服务；服务合成；分布式哈希表；覆盖网络；空间填充曲线

0引言

在感知服务质量（Quality of Service，QoS）的服务组合[1]的研究中，有较多文献采用数学规划的方法求解服务组合问题。如文献[2]采用整数规划（Integer Programming，IP），文献[3]采用多选择背包问题（MultipleChoice Knapsack Problem，MCKP）。其主要问题在于很多数学规划方法都是NPComplete的，不能在多项式时间内求解。以IP为例，最

坏情况下的时间复杂度为O（∏ni=1mi），

其中n为组合服务的任务数，mi为第i个任务的候选Web service个数。随着mi和n的增大，特别是n的增大，IP的求解时延呈指数方式显著增大。

为解决上述问题，文献[4-5]提出采用基于案例推理（CaseBased Reasoning，CBR）来求解服务组合问题。如文献[4]计算用户服务组合请求同已知组合服务的近似度，当两者近似度达到一定阈值之后，将采用该组合服务来响应用户服务组合请求。同数学规划方法相比，CBR方法时延性能较好。在上述文献中，CBR一般以集中方式（centralized）提供查询服务，即若干固定数量（一般数量较少）的高性能CBR Server存储已知组合服务，形成已知组合服务记录库（Service Repository，SR），并负责处理查询请求。在集中方式下，高性能CBR Server节点数量较少，要保证查询成功，每个CBR Server的SR的规模将会较大，数据的维护代价高昂。此外，用户请求将会集中在这些CBR Server，形成较重的节点网络负载。若在本地CBR Server查询失败，查询请求随机转发到其他CBR Server，但并不能保证转发后具有更高的命中可能性。更严重的是，若某个CBR Server失效，由于其负责的SR规模较大，将会对查询命中率产生严重影响，CBR的扩展性较差。

为了解决上述问题，在CBR的基础上，本文提出了基于分布式哈希表（Distributed Hash Table，DHT）的协作式Web服务组合方法COCO （DHT based COllaborative Web Service COmposition），通过在底层引入DHT Overlay（如Chord[6]、Kademlia[7]等），削弱对集中节点的依赖，降低对节点性能的要求，避免中心失效问题，并通过DHT Overlay的高效信息路由，提供具有良好伸缩性（scalable）的高性能查询服务，查询满足用户服务组合请求的已知组合服务。DHT Overlay将数据值映射为数据键： f：valuekey，将DHT Overlay节点映射

为节点ID： f：nodeID，根据key和ID之间的“距离”特征，节点将存储与自身ID相近的数据data=〈key，value〉，从而形成了结构化的分布式哈希表。同时节点也根据“距离”保存了查找其他节点的路由表。由于节点分布式哈希表和路由表均根据“距离”构建，因而在分布式哈希表中查询数据键相当于在路由表中查找节点，从而数据键查询能沿着数据键和节点ID之间“距离”不断缩小的方向进行，避免转发的随机性。因此只要一个数据确实被存储于分布式哈希表，就一定能够在距其较近的节点上被找到，因而DHT可提供带保障（guaranteed）的高效查询服务。

为了利用基于数据键的DHT Overlay通过一次查询便能获得同时满足用户请求的功能性要求和非功能性要求的组合服务，COCO将用户服务组合请求、已知组合服务均映射为数据键，并将组合服务数据键存储于DHT以供查询。COCO采用哈希函数构建工作流数据子键；同时为支持多维范围查询[8-9]，COCO采用空间填充曲线（SpaceFilling Curve， SFC）[10]构建服务质量数据子键，并将两部分数据子键合成为完整数据键，交由DHT Overlay进行查询，进行感知QoS的服务组合。实验结果表明，COCO在查询时延和查询命中率方面均有较好性能。

1基于DHT的协作式Web服务组合方法

2模拟实验及分析

2.1实验目的

模拟实验主要对比COCO、IP（整数规划）、CBR（基于案例推理）在求解时延、求解成功率方面的性能。COCO方案利用PeerSim[12]仿真，DHT Overlay采用Kademlia，SFC采用Z曲线，哈希函数采用SHA1；IP方案利用Lingo数学软件进行求解。实验环境为Intel CORE i32310M 2.1GHz，3GB DDR3 RAM，Windows 7 32位。

2.2求解时延对比

2.4实验结论

无论是查询时延还是命中率，COCO均依赖于较大规模的DHT Overlay。IP具有最高的时效性，但是处理时延较大，对于复杂（尤其是任务数较多）的组合服务，处理时延过大，影响用户体验。当COCO具有较大规模的DHT Overlay时，查询时延性能明显优于IP，且具有良好的伸缩性。在查询成功的情况下，CBR的时延性能最好，但CBR的集中式处理方式对节点的性能要求较高，并需要在CBR Server存储较多已知组合服务记录。若CBR Server查询失败，需要转发查询请求时，由于没有DHT Overlay带保障查询的支持，是随机方式转发的，并不能保证转发后具有更高的命中可能性。COCO可以认为是CBR on DHT Overlay，利用DHT Overlay削弱了对本地节点性能的要求，提供了带保障的查询处理，使得每一次转发均沿着同待查数据键异或距离减小的方向进行，适用于大规模网络的协作式服务组合。

3结语

文献[13-14]采用了同本文相似的技术路线，均利用P2P基础设施对服务计算进行支持，以期获得服务组合节点的可靠性、可伸缩性及高效的信息路由。上述文献主要处理Web服务的发现。本文提出了基于DHT的协作式Web服务组合方法COCO，利用哈希函数和空间填充曲线将组合服务的工作流和服务质量映射为一维数据键，并利用底层DHT Overlay以P2P的方式查询满足用户请求的已知组合服务，一次查询就能获得同时满足功能性要求和非功能性要求的组合服务。实验结果表明，COCO在查询时延和查询命中率方面均有较好性能。

今后的工作中将从如下几个方面完善COCO：1） COCO将提供哈希函数、SFC和DHT Overlay的封装类，以实现哈希函数、SFC、DHT Overlay的灵活替换；2）保证已知组合服务数据键的时效性。

参考文献：

[1]

邓水光，黄龙涛，尹建伟，等.Web服务组合技术框架及其研究进展[J].计算机集成制造系统，2011，17（2）：404-412.

[2]

ZENG L， BENATALLAH B， NGU A H H， et al.QoSaware middleware for Web services composition[J]. IEEE Transactions on Software Engineering， 2004， 30（5）： 311-327.

[3]

YU T， ZHANG Y， LIN KJ. Efficient algorithms for Web services selection with endtoend QoS constraints[J]. ACM Transactions on the Web， 2007， 1（1）： 1-26.

[4]

YE X， MOUNLA R. A hybrid approach to QoSaware service composition [C]// Proceedings of the 6th IEEE International Conference on Web Services. Washington， DC： IEEE Computer Society， 2008： 62-69.

[5]

CHENG R， SU S， YANG F， et al. Using casebased reasoning to support Web service composition[C]// Proceedings of the 6th International Conference on Computational Science. Washington， DC： IEEE Computer Society， 2006： 87-94.

[6]

STOICA I， MORRIS R， LIBENNOWELL D， et al. Chord： a scalable peertopeer lookup protocol for Internet applications[J]. IEEE/ACM Transactions on Networking， 2003， 11（1）： 17-32.

[7]

MAYMOUNKOV P， MAZI D. Kademlia： A peertopeer information system based on the XOR metric[C]// Proceedings of the 1st International Workshop on PeertoPeer Systems. London： SpringerVerlag， 2002： 53-65.

[8]

ZHANG Y， LIU L， LI D， et al.DHTbased range query processing for Web service discovery[C]// Proceedings of the 7th IEEE International Conference on Web Services.Washington， DC： IEEE Computer Society， 2006： 87-94.

[9]

TANG Y， XU J， ZHOU S， et al.A lightweight multidimensional index for complex queries over DHTs[J]. IEEE Transactions on Parallel and Distributed Systems， 2011， 22（12）： 2046-2054.

[10]

MOKBEL M F， AREF W G. Spacefilling curves[M]// SHEKHAR S， XIONG H. Encyclopedia of GIS. Heidelberg： Springer， 2008： 1068-1072.

[11]

CHEN X， ZENG H， WU T. Decentralized orchestration with local centralized orchestration for composite Web services[C]// Proceedings of the 11th International Conference on Parallel and Distributed Computing， Applications and Technologies. Washington， DC： IEEE Computer Society， 2010： 255-260.

[12]

MOKBEL M F， AREF W G. Irregularity in highdimensional spacefilling curves[J]. Distributed and Parallel Databases， 2011， 29（3）： 217-238.

[13]

KAZMI I， BUKHARI S F Y. PeerSim： an efficient scalable testbed for heterogeneous clusterbased P2P network protocols[C]// UkSim 2011：the 13th International Conference on Computer Modelling and Simulation. Washington， DC： IEEE Computer Society， 2011： 420-425.

[14]

张龙昌，邹华，杨放春.一种基于多QoS注册中心和模型异构的Web服务选择算法[J].电子与信息学报，2011，33（1）：168-174.

[15]

张莹，黄厚宽，杨冬，等.基于Chord的带有QoS的语义Web服务发现方法研究[J].电子与信息学报，2009，31（3）：711-715.