Competitive algorithms for the dynamic selection of component implementations.

Many applications are being built by integrating multiple distributed components in order to implement a particular business function. The increasing popularity of component programming models, such as JavaBeans ** (1) and Web services, (2) is predicted to further accelerate the adoption of component-based development (CBD).

An impediment to the adoption of CBD, however, is the inability of the "user" of the components to optimize their performance for use in a particular solution. Web services, with its premise of loosely coupled distributed components working together, makes this issue even more acute, as the development, deployment, and maintenance of components making up a single solution may come from different vendors and run in very different system environments.

In this paper, we propose a generic framework that addresses this issue. In our formulation, an adaptive component has multiple implementations, each optimized for a particular request workload. A mechanism for switching between implementations is also provided. The underlying system monitors the current request workload for a given component and adaptively switches to the implementation best suited to this workload. By shifting more of the performance optimization burden to the component, performance tuning is simplified and the resulting overall system performance is likely to be improved. Additionally, by having the ,system monitor the request workload and dynamically switch implementations based upon current usage patterns, the component can better accommodate changing request patterns.

Because switching between implementations can incur a heavy cost, good algorithms are needed for determining, at run time, when to switch between implementations. We call this the adaptive component problem. This paper describes an algorithm, named Delta, for the case when there are exactly two implementations. We show that Delta is (3 + [epsilon])-competitive. This algorithm is designed for the case when the cost of switching between implementations is very large compared to the cost of processing a single request. In this Case, the value of [epsilon] is guaranteed to be very small. Because we also show a 3-competitive lower bound, this algorithm is close to optimal.

We show the applicability of this framework to two problems. The first is an adaptive version of the distributed pub/sub problem, where multiple loosely coupled components are reading and writing from a shared data repository. A component can either read and write to this shared repository or create a local data cache for fast access. The second example is an adaptive version of the data structure selection problem, where an application must choose the appropriate internal data structure to use in order to provide the quickest answer to particular queries. We show that both of these are instances of the adaptive component problem and that Delta can be used to decide when to switch implementations, thus optimizing run-time performance. This illustrates the applicability of our framework to a wide range of problems.

Here is an outline for the rest of this paper. The next section "The adaptive component problem" is followed by "The Delta algorithm." Then, the section "Examples" contains our two case studies. In the section "Competitiveness" we prove that Delta is (3 + [epsilon])-competitive, and in the section "Lower bounds," we establish a 3-competitive lower bound for this problem. The section "Related work" is followed by "Summary and open issues."

The adaptive component problem

We propose a model where the component developer implements multiple versions of a component, each optimized for a specific request workload. The developer also writes the code that controls the switching between implementations at run time. For each request type that the component can service, and for each implementation of that component, we determine the cost for processing a request of that type. We similarly determine the cost of switching between any two implementations. These costs may be specified by the component developer or may be derived empirically (e.g., by profiling). An on-line algorithm will monitor request workloads at run time and determine when to switch implementations. The rest of this section formalizes these concepts and defines an optimality criterion for determining when to switch implementations.

Let Comp be an adaptive component, and let Req-Types = {[typ.sub.i]} be the set of request types that Comp can process. Let Impls = {[impl.sub.j]} be the set of implementations of Comp, with [impl.sub.1] being the default implementation. Let Cost:ReqTypes x Impls [right arrow] R be the function that gives the cost for Comp to process a request of a given type using a particular implementation (R denotes the set of reals). Let SwitchCost:Impls x Impls [right arrow] R be the function that determines the cost in Comp of switching from one implementation to another. SwitchCost([impl.sub.i], [impl.sub.j) = [infinity] iff Comp cannot switch from [impl.sub.i] to [impl.sub.j]. The cost functions may reflect internal computation costs, network message costs, or a combination of these and other metrics, depending upon the application environment.

We represent the computation to be performed as a sequence of requests, [r.sub.1], ..., [r.sub.k]. The empty sequence is denoted by [OMEGA]. To facilitate the modeling of many different sorts of problems, we allow a single request to be processed by either a single component or by multiple components. Given such a sequence of requests, a switch of implementations may occur after processing any request in the sequence. We represent this by the operation switch([impl.sub.i], [impl.sub.j]), where [impl.sub.i] is the current implementation of the component, and [impl.sub.j] is the implementation being switched to. Hence, given a sequence of requests a = [r.sub.1], ..., [r.sub.k], we model the adaptive behavior of the component Comp as transforming this sequence to the sequence [alpha]' = [s.sub.1], ..., [s.sub.f] such that the following comments are true:

* For 1 [less than or equal to] i [less than or equal to] f, either [s.sub.i] is a request or [s.sub.i] is a switch operation.

* Removing the switch operations from [alpha]' produces [alpha].

* If [s.sub.m] = switch([impl.sub.j], [impl.sub.k] then either [s.sub.m] is the first switch operation in the sequence and j = 1 or the closest preceding switch operation in the sequence is of the form switch([impl.sub.i], [impl.sub.j).

An on-line algorithm is one that transforms the sequence [alpha] by deciding whether or not to insert a switch operation after request [r.sub.i] based only upon the sequence seen so far, [r.sub.1], ..., [r.sub.i]. We write [alpha] [[right arrow].sub.A] [alpha]' to indicate that on-line algorithm A (used by Comp) maps [alpha] into [alpha]' when processing it. For any request [s.sub.i] in the transformed sequence [alpha]', we say that the implementation [impl.sub.k] is active at [s.sub.i] if the closest switch operation preceding [s.sub.i] in the sequence is of the form switch([impl.sub.j], [impl.sub.k]), or k = 1 and there is no switch operation preceding [s.sub.i]. When algorithm A and sequence [alpha] are understood from the context, we simply denote this by ImplIs([s.sub.i], [impl.sub.k]).

[Cost.sup.A.sub.[alpha]] is the cost of Comp to process request sequence [alpha] using algorithm A. [Cost.sup.A.sub.[alpha]] = Cost([alpha]') = [[summation of].sup.n.sub.i=1] C([s.sub.i]) where [alpha] [[right arrow].sub.A] [alpha]' = [s.sub.1], ..., [s.sub.n] and where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let O be an optimal algorithm; that is, for any sequence [alpha] and any on-line algorithm A, [Cost.sup.O.sub.[alpha]] [less than or equal to] [Cost.sup.A.sub.[alpha]]. An on-line algorithm A is c-competitive (3,4) iff, for any sequence [alpha], there exist constants c and d such that [Cost.sup.A.sub.[alpha]] [less than or equal to] c * [Cost.sup.O.sub.[alpha]] + d. Given Comp, RegTypes, Impls, Cost, and SwitchCost, the adaptive component problem is to find an on-line competitive algorithm for this problem instance, that is, to find a c-competitive algorithm for some constant c.

Now consider a special case of the adaptive component problem where Impls = {[impl.sub.1], [impl.sub.2]}, which we call the adaptive two-implementation-component problem (the adjective "adaptive" is sometimes omitted, for conciseness). We assume that there is at least one request r such that Cost(r, [impl.sub.1]) < Cost(r, [impl.sub.2]), and at least one request r' such that Cost(r', [impl.sub.1]) > Cost (r', [impl.sub.2]). Also, we assume that there are no constraints on the order in which requests must be composed in a sequence (i.e., any interleaving of requests is a legitimate request sequence).

Let S[C.sub.1] = SwitchCost([impl.sub.1], [impl.sub.2]), S[C.sub.2] = SwitchCost([impl.sub.2], [impl.sub.1]), and SC = S[C.sub.1] + S[C.sub.2]. We call SC the round trip switching cost. The Delta algorithm described in the next section will perform close to optimal when, for any request r, |Cost(r, [impl.sub.1]) - Cost(r, [impl.sub.2]) | [much less than] SC. That is, the difference in processing cost for a single request when one implementation is active as opposed to' the other implementation, is significantly less than the switching cost.

The Delta algorithm