A Study of Caching Strategies for Web Service Discovery

Web Service discovery a fundamental operation in SOA-based systems. In a landscape of Web Services that is growing in size and complexity, discovering a suitable atomic or composite Service for a given task requires a considerable amount of computation and communication resources, including semantic reasoning, the use of composition algorithms, and communication with multiple Service repositories. We study the approach of introducing a cache for Service discovery results to reduce the load on the backend discovery system. In this setting the bottleneck is the cache refresh frequency rather than the cache size, thus the caching algorithm needs to decide in which order to refresh the cached contents. We derive a theoretical upper bound on the number of cache hits possible to achieve for a given set of discovery queries, and we propose a number of heuristics for this caching problem, some of which turn out to have provable approximation guarantees. In an extensive experimental study we evaluate these methods. Our findings are that the best algorithms lead to a cache performance of more than 95 percent of the theoretical upper bound in all tested scenarios.