The Adapt Framework for Adaptable and Composa...

The Adapt Framework for Adaptable and Composable Web Services
 
Invited article from theWeb Systems topic area
Alberto Bartoli (University of Trieste),
Ricardo Jiménez-Peris (Universidad Politecnica de Madrid),
Bettina Kemme (McGill University),
Cesare Pautasso (ETH Zurich),
Simon Patarin (University of Bologna),
Stuart Wheater (Arjuna Technologies),
Simon Woodman (University of Newcastle).
1. Introduction.
Organizations are increasingly using the Web not only to sell products and deliver information, but also for providing their services to businesses and individual customers. Typically, the provision of such services by organizations requires the construction of applications that integrate existing enterprise information systems to offer new business functions. Organizations need to ensure that these services are available, scalable and also autonomic to guarantee that user interactions are promptly processed even under highly volatile conditions. In most cases, organizations deliver these services by means of application servers with a multi-tier architecture whose functionalities are accessed as web services. We refer to services not relying on other web services as Basic Services (BSs). The presence of a wide variety of BSs over the Internet has created an exciting new business opportunity of providing value added, inter-organizational services by composing multiple BSs into new Composite Services (CSs).
This novel scenario, however, raises many challenges. For example, composition of BSs usually involves incompatibilities in data models, sequencing constraints on operation invocations and mismatches in transactional semantics. In many cases, a CS will be composed of a mixture of transactional and non-transactional services, and CS functions will be required to preserve specific consistency properties in the presence of a variety of exceptions. Even when all individual BSs have clean "ACID" transactional semantics, the resulting CS could not have the same: it has long been realised that not all interactions can be structured as ACID transactions. These problems are magnified when using a CS as a building block for further composition with other BSs and CSs. We need a way to cope with all these issues, both at design time and at a run-time. Moreover, a CS should be able to adapt dynamically to changing availability or load conditions of individual services. A similar need for adaptability exists at the level of individual BSs, because a BS typically involves the interaction amongst different servers -- application servers and database servers -- with independent failure modes and executing different portions of the injected load. Of course, achieving adaptation within a CS will be quite different from achieving it within a BS.
In this paper we present our efforts in this area and provide an overview of theAdapt project1, that aims to provide autonomic support for both basic and composite web services.
2. Scenario
2.1. A composite application
Composite applications are the natural results of providing customers with services that are the product of interacting with multiple internal services. To make the presentation more concrete, we shall present the motivation for the Adapt framework by investigating an example that is representative of the Adapt framework's intended use. The example that will be used is that of a supply chain management application, the structure of this example is derived from the WS-I Sample Application specification []. This supply chain management application's design consists of three systems: a retailer system, a manufacturing system and a demo system. These systems provided services that enable the system to interact to achieve the desired purpose. The retailer system consists for three service types: a retailer service, a warehouse service and a warehouse callback service. The manufacturing system consists of a single service, a manufacturer service. The demo system consists of two services: a configurator service and a logging service. The services, and their use relationships, are illustrated inFigure 1. The service within the retailer and manufacturer systems are implemented by a set of services which interact via web-services, and are themselves composite applications, as each service makes use of other services, to achieve its desired goal.

Figure 1: Supply chain management application's structure
In this example the Demo System initiates a dialog with the Retailer System by firstly requesting from the retailer their catalog. Based on the content of this catalog an order can be submitted to the retailer service. To response to an order submission the retailer service will contact the warehouse services to determine availability of the ordered items. If this results in stock level that is below the desired threshold then the warehouse service will send a purchase order to a manufacturer service, when the desired goods are ready the manufacturer service will send a shipment notice to the warehouse call-back service. This shows how a relatively simple service could be made up of a number of other services, spread over different administrative domains. In addition these service could in turn be composite, making use of other previously existing and specially created services. For example, the manufacturer service could make use of an existing production line management services to initiate goods to be produced, also any existing inventory and storehouse services could be also be integrated.
2.2. Which are the component services?
In Adapt we consider services accessed viaweb services and described by aWSDL document. We distinguish among two kinds of services: Basic Services and Composite Services. A Basic Service, BS for short, is a service whose implementation does not invoke other services. A Composite Service, CS for short, is a service whose implementation may invoke other services. The invoker of a service does not need to know whether it is accessing a BS or a CS. A BS is typically offered by a single organization. A CS is typically implemented by a form of "glue" offered by a single organization. This glue hides the internal interaction with other BSs or CSs, that can be implemented by either the same or different organizations. For example, in the scenario outlined inSection 2.1 the Manufacturer service is clearly a composite service, as it makes use of services from other systems and also potentially utilizes other service internal to the Manufacturing system, such as production line management, inventory and storehouse services. There internal service would be classified a basic services, if they weren't required to interact with other services.
2.3. How are component services implemented?
We make no assumptions as to how a BS or CS is implemented. As long as a service can be accessed as a web service and is described by a WSDL document, that service can be part of an application based on the Adapt framework. This standpoint makes it easier to integrate existing services and is important in order to simplify and promote practical usage of the framework. When a BS or a CS is described and implemented following certain Adapt-specific techniques, however, that service will be able to exploit the advanced features of the framework. These techniques and features will be described in the rest of this paper.
2.4. How are component services described?
When using web services we describe the functional properties of a service by means of a WSDL document. To handle the complexity of constructing composite applications it is necessary to in addition describe non-functional properties of services, we do this by the means of a service specification language, which we have developed specifically for this purpose. This description may be useful for simplifying composition of services, e.g., for predicting the properties of a CS based on the properties of its constituent services.
We have identified three families of non-functional attributes that may be of interest for compositions (full details can be found in [Deliverable D6]):
Attributes related to transactional capabilities of web services. These attributes help to build transactional compositions of web services. Traditional ACID transactions are not applicable in the composition of web services, in order to preserve the autonomy of the organizations that provide these services. The main problem is the isolation property: a long lasting transactional composite service can block the resources of the organizations providing the web-services for long periods of time. We shall discuss this issue in more detail inSection 3.1.4. Attributes regarding sequencing constraints on web service invocations (conversations). These attributes define the order in which the operations of a service should/can be invoked. The definition should be complete, i.e. describe all legal options available to the user of the service based on the previous operations they have called. It should also be possible to validate that a client for a service conforms to the interaction constraints which have been placed upon it. Attributes dealing with web service performance.
The first and the second set of attributes are static in the sense that their specification does not change after deployment. It is useful to publish static attributes at deployment time. This allows the CS to use the static attributes at composition time to derive the properties of the composition. These attributes are described in the same WSDL document describing the functional properties of the service, using the extensibility features of WSDL.
The third set of attributes are dynamic: performance values, like response times, throughput, and availability, change continuously during service execution. These dynamic attributes are useful at run-time to choose the most appropriate service with respect to its actual performance. Unlike the above static attributes, these are associated with dedicated operations: the CS can call this operation whenever it wants to know the current performance values of the web service.
To illustrate the value of this additional non-functional properties let us examine a scenario from the example described inSection 2.1. Consider the sending of a submit purchase order message from the Warehouse service to the Manufacturer service, it will be clear from the WSDL that an acknowledgement or error message will be send in response, but not evident that Manufacturer service will also, at some later point in time, send a message to the Warehouse Callback service. This shipment notice message is crucial the composite application execution, but is not apparent in the WSDL for the Manufacturer service.
Description of the non-functional properties of a service is one of the Adapt-specific features mentioned in the previous section. We provide tools for providing and exploiting such description, as shown in the rest of the paper. However, a service need not include a description of its non-functional properties to be part of an Adapt application. Similarly, the invoker of a service that does describe its non-functional properties might just ignore this description.
2.5. How are they composed together?
When composing services the resulting service could have a long execution duration. So implementing a composite service as a workflow process is an attractive approach. Workflows provide a good abstraction to model the composition of web services. A workflow process is composed of a set of service invocations (or tasks) and its structure defines the control and data flow dependencies between them. Following this approach, it becomes possible to give a high-level description over the partial order of invocation of the services and their interactions while maintaining well-defined, executable semantics. The composite service support can also utilize the workflow system's ability to recommence execution after failure, and the service integration support of workflow system's can be utilized to circumvent small semantic differences between services, such argument and result formats.
In Adapt, a process can be modeled with different syntaxes. Developers of the composition may use a visual representation to draw the interactions between the services that should be composed [Pautasso and Alonso, 2003]. However, in order to facilitate the development and the interoperability of the various tools of the Adapt composition platform (e.g., editors, model checkers, compilers, monitoring tools) composite service definitions are stored behind the scenes using the XML syntax following the schema of the Adapt composition language [Deliverable D7].

Figure 2: Process Lifecycle as managed by the ADAPT Composition Environment
The Adapt composition environment provides an integrated toolkit to manage the whole lifecycle of a process, as shown inFigure 2. This begins with the service library, where web services can be imported as reusable components. The developer can browse the library, select a set of basic services and drag and drop them into a process. Then, he or she may begin to define their interactions by drawing the data flow graph. This operation is partially automatic, since the Adapt visual composition editor can bind parameters with matching names (Figure 3). Manual intervention is only required to resolve ambiguities and connect parameters that could not be automatically matched. To get an overview over the order of execution of the tasks and add additional constraints, the user may view and edit the control flow graph. The visual editor automatically keeps the two graphs synchronized and provides advanced model checking facilities that can be used to validate the composition [Deliverable D8]. For instance, it verifies the structure of the composition is free of deadlocks and livelocks such as infinite loops, unreachable execution branches etc. In addition, the visual editor verifies that the messages sent and received from the process to each component service form a valid conversation with that service [Woodman et. al 2004].

Figure 3: Screenshot of the ADAPT composition environment ( Click here to see a video demo)
Once all of the services have been connected and the process passes the verification step, the composition is compiled and deployed to the Adapt composition engine and it becomes ready for execution. For debugging purposes, processes can be started by developers, which can monitor their progress in the same visual representation used to define the composition. Additionally, it is possible to inspect the content of the messages exchanged within the process to check their correctness. Once in production, compositions can be published as web services.
3. Adaptability
3.1. What does adaptability mean at the composite service level?
Due to the properties of the distributed setting in which composite services are deployed, it is essential that a composite service can be modified dynamically to reflect changes in the underlying environment. Adaptability is thus a very important property of a composite service that can be expressed along several orthogonal dimensions:
Dynamic binding. The references linking the composite service to its component services are evaluated at the latest possible time. Thus, it becomes possible to retarget some of the services to be invoked dynamically, ensuring the forward progress of the composition. Fault-tolerance. The composite service should appropriately handle application-level failures that are encountered during the invocation of its basic services. Similarly, if a service becomes unavailable it should be possible to retry the invocation using a backup service provider. Resolution of interface mismatches. Bottom-up composition may result in incompatibilities in the data models of the basic services to be integrated. Thus, a suitable mechanism to adapt mismatching services to fit with one another is required. Advanced Transactional Semantics. Advanced transactional semantics enables composing web services that adapt smoothly to exceptional conditions and perform semantic compensation automatically when required.
In Adapt, the service composition language has been designed to allow the specification of the structure of a composite service at a level of abstraction which allows the composite service designer to concentrate on modeling the correct functional behavior of the process. The corresponding notations and structures for representing fault handlers, dynamic binding and interface adaptation will be introduced in the following sections.
Introducing adaptability in a composite service through the composition language is not enough, as adaptability needs to be appropriately supported by the underlying composition infrastructure. In this regard, the Adapt distributed engine for executing compositions can be adapted to provide different levels of performance in terms of both scalability and reliability. In [Pautasso and Alonso, 2004] we show that replication can be applied to key components of the engine in order to increase the overall system's throughput as the engine runs over a cluster of computers. Similarly, we evaluated the cost of providing reliable execution of the composition by comparing different strategies for the adding persistence to the engine. In [Pautasso et al, 2005], we discuss how the engine features autonomic self-tuning properties. A closed feedback loop controller has been introduced that monitors the current workload running on the distributed engine and adapts its configuration in order to optimize the system's performance based on several policies (e.g., minimize response time or maximize the efficient resource utilization).

Figure 4: Feedback loop of the Adapt composition engine.
3.1.1. Dynamic Binding
The notion of binding captures the relationship between the composition and its component services. In Adapt, a composition only includes a reference identifying which service should be invoked as part of the execution of a specific task [Pautasso and Alonso, 2005]. This enables the system to offer a form of dynamic late binding, where the decision about which service should be actually invoked is delayed until the latest possible time, i.e., when a service is about to be invoked. In fact, only at this time such reference is evaluated in order to pick the service to be invoked. Although services are normally bound into a composition at design-time, a binding may be updated at run-time, enabling to dynamically adapt the composition. With this, a composition may be adapted to changing availability conditions of its component services since each execution of the composition may target the optimal services according to some quality-of-service metric.
3.1.2. Fault tolerance and forward error recovery
A Web service can become unavailable for several reasons. The connection across the Internet to the Web service provider can fail during aSOAP message round. Alternatively, the Web service may have been taken offline temporarily for maintenance. As a consequence, the binding information in its WSDL description may be out-of-date. Whatever the reason, from the point of view of the composite application, a failure to contact a Web service can have very serious consequences. To ensure a successful invocation, failure handling actions can be taken at different levels in the communication stack as well as at the process level itself.
In Adapt we offer a set of language constructs to deal appropriately with irrecoverable failures of a certain Web service. This means that, when everything else fails, it is still possible to model explicitly, at the process level, what to do, using a form of retry on exception. This approach is based on the basic exception handling construct of Adapt. As shown inFigure 5, service invocations can be connected by a failed control flow dependency, which will be triggered only by a failed invocation. The example shows this pattern applied to four services, which are sequentially connected in a failure triggered chain.

Figure 5: This chain of four Service invocations is traversed as each call fails. Adapt attempts to contact the four alternative, equivalent services in the order specified by the control flow graph drawn by the developer.
3.1.3. Data transformation
Both when searching for alternative implementations of a given service or when attempting to find a service which can directly receive an input request message produced by another service, it may be rather difficult to find exact matches. Instead, it is likely that some form of adaptation is required to integrate the mismatching services.
To address this problem, a transformation of the data to be exchanged between the services is required. As the data exchanged by Web services is mostly encoded inXML format, Adapt leverages different standard XML transformation technologies, such asXSLT orXPATH. More precisely, it is possible to include data transformation services as part of a composition and provide the corresponding XSLT/XPATH implementation. Adapt will then efficiently apply the transformation to the data as it flows between the adapted services.
In practice, adapters between pairs of services can be defined once and automatically reused. Whenever parameters of the corresponding types are connected the Adapt visual development environment suggests a list of applicable adapters. The developer may choose to apply an existing one directly, or to customize one to fit with the specific pair of services.
3.1.4. Advanced transactional semantics
The traditional transaction model is simple and provides clear semantics. However, the model does not fit all application needs. For instance, if a long-duration business process (it can take hours or months) is run as a transaction, it is not desirable to undo completely the transaction if there is a crash just before finishing. At the same time, such a long-lived transaction may access many data items. If another (short) transaction needs to access any of these items, then it will end up waiting for the long-lived transaction to finish. A wide variety of extended transaction models have been proposed over the last decade in order to overcome the limitations of traditional transactions found in different application scenarios [Jajodia et al. 1997,Elmagarmid 1992].
The problem has been addressed by implementing new developing standards on advanced transactions that are being proposed in the context ofJ2EE, such as JSR 95 J2EE Activity Service, and web services, such as OASIS WS-Composite Application Framework (WS-CAF). The J2EE Activity Service enables the creation of advanced transaction models with a close coordination with the Java Transaction Service. WS-CAF defines a stack of protocols for context representation and propagation, transactional coordination and advanced transaction models and two-phase commit.
The implementation of both standards is available through theObjectWeb JASS (Java Advanced Transaction Support) project.
3.2. What does adaptability mean at the basic service level?
A BS is often required to satisfy non-functional requirements, such as high availability and high throughput. Addressing such needs is complex for several reasons. A BS typically involves the interaction amongst large pieces of software running on different servers -- i.e., application servers and database servers. Such servers have independent failure modes and execute different portions of the injected load. Their effect on the overall availability and performance of a BS as a whole is thus very hard to predict and control. Moreover, a BS is required to work in environments where the injected load may be subject to wide and frequent dynamic changes, in a way that can neither be predicted nor controlled. When a BS makes use of replication internally, which is often the case for improving performance and/or availability, all these problems are magnified.
In Adapt we address these issues by means of an adaptive infrastructure, i.e., one that perceives the surrounding context and the effect of its reactions on this context. We do not rely on human operators required to intervene promptly and frequently for turning the right knobs in the system configuration. We developed a middleware that enables implementing adaptable BSs. By this we mean that the BS internally reacts automatically -- i.e., "adapts" itself -- to internal failures and dynamically changing load conditions, so as to maintain high levels of availability and throughput. This form of adaptation occurs in several parts of the BS internals, as shown in the rest of this section.
3.2.1. A J2EE three-tier approach
Our middleware can be used for BSs implemented as three-tier services based on the J2EE architecture. We remark, though, that we do not make any hypothesis as to how a BS (or a CS) is implemented. Therefore, nothing precludes the use of BSs not implemented with our middleware or not even implemented with J2EE.
A J2EE three-tier service requires an application server and a database server. The two servers typically run on distinct machines, although this is not strictly necessary. A J2EE application is deployed as a set of components, i.e., objects whose lifecycle and invocation is managed by the application server rather than directly by the developer. J2EE components are called Enterprise Java Beans, EJB for short. The developer writes deployment descriptors for EJBs specifying such properties as transactional behavior, security, and persistence. The application server logic will enforce these properties automatically. The main advantage of this approach is that it can partially automate important aspects of the application's logic. For example, the developer may express transactional logic in simple, centralized declarations, rather than in many lines of scattered imperative code. Interaction between the application server and database server is hidden behind a standard API and, in many cases, the developer does not even need to access the database server programmatically.
Our middleware for J2EE-based BSs uses replication as the key technique for providing adaptability. It allows replicating the application server and/or the database server. The degree of replication will influence the ability of a BS to adapt to failures and to changing load conditions, as discussed in the next sections.
Replication at the application server layer is done with the algorithms in [Wu et al. 2004,Wu and Kemme 2005]. These algorithm allows replicating EJBs assuming different transaction patterns. In the simplest pattern, each client request defines exactly one transaction and only one database is accessed. Advanced patterns allow a client request to generate more than one transaction, several client requests to be bundled in one transaction, or more than one database to be accessed. The cited papers actually describe replication algorithms for EJBs whose clients are RMI clients. Subsequent work has allowed exposing EJBs as web services to remote clients with minor changes to the algorithm, also including techniques from [Bartoli et al. 2005]. The general idea of the algorithms is briefly outlined in the next section.
The implementation is based on a J2EE replication framework that we designed and implemented [Babaoglu et al. 2004]. We developed this framework to ease the prototyping of replication algorithms at the application server layer, on the grounds that to design and evaluate a replication algorithm for J2EE (or any practical component architecture) requires a substantial investment in development. With this approach, the task of developing a replication algorithm is factored into two portions: the framework itself, which handles all the detailed interactions with the underlying application server code, and the specific replication algorithm, which is written in terms of a high-level API and is plugged into the framework. The framework is implemented once and for all, allowing the developers to concentrate on the relevant details of the specific replication algorithm. The framework has been implemented for theJBoss open-source application server and theAxis SOAP engine. Clients of a service based on our framework need to run locally a replication-aware stub that is also part of the framework. This stub handles some replication-specific information, stored in a dedicated portion of the SOAP header, and performs failover when necessary. Another replication algorithm that has been implemented on top of our framework is described in [Bartoli et al. 2005] (this algorithm does not address three-tier architectures, however).
Concerning the database layer, our BS middleware incorporates a replication middleware called Middle-R [Patiño-Martinez et al. 2005,Lin et al. 2005]. It consists of a layer on top of each database server without any changes to the servers themselves. Database servers do not share any storage and each server stores a full copy of the database. We use the open-sourcePostgreSQL as database server. This replication infrastructure is briefly outlined inSection 3.2.3. We also looked at database replication at the kernel level [Wu and Kemme 2005-b] but will not discuss this for space reasons.
One can combine replication at the two layers in all possible ways [Kemme et al. 2005] . If only the application server layer is replicated, any J2EE-compliant database server can be used. If only the database server is replicated (i.e., Middle-R), the application server must access the database through our Middle-R driver. This option requires no changes to the application server because the Middle-R driver is J2EE compliant. If, finally, both the application server layer and the database server layer are replicated, use of the Middle-R driver is again all that is needed for integrating the two layers. This driver hides all the complexity related to coordination between the application server replicas. This coordination follows a primary-backup scheme, i.e., only one application server at a time is responsible for interacting with database server replicas. The details can be found in [Deliverable D13].
Our BS middleware includes an infrastructure that implements automatically some of the performance-related attributes of a service described inSection 2.3. The infrastructure consists of a set of sensors capable of calculating mean latency, number of successful invocations, number of faulty invocations. These counts are kept separately for each service. Sensors come in two flavors: a continuous sensor monitors a given service since the monitoring has been activated. A periodic sensor monitors a service over a given time interval, that is, it tracks the number of invocations and the mean latency in the last N milliseconds, N being a configurable parameter. All data collected by the monitoring tool are exposed through a single web service. Configuration of the monitoring tool is performed through that web service as well. All configuration tasks can be performed dynamically, without interfering in any way with the web services being monitored.

Figure 6: Replication schemes enabled by Adapt: (1) at the application server layer, (2) at the database layer, (3) at both layers.
3.2.2. Fault tolerance
Our middleware adapts to internal failures in the sense that it masks them to clients, by exploiting replication: a BS will be available as long as there is one application server and one database server available. A key feature of our middleware is that adaptation to failures always preserves correctness (we shall clarify our notion of correctness in a moment). That is, unlike most existing replication infrastructures, correctness does not depend on the hope that certain failure patterns either do not occur at all or at least they do not occur within certain vulnerability windows. In other words, use of replication improves the adaptability features of a BS without introducing any risk of exposing incorrect behavior to clients -- i.e., a behavior that a non-replicated BS could not exhibit.
Our notion of correctness for a replicated BS encompasses both the application server layer and the database server layer: as long as the client does not crash, a transaction is executed exactly-once (if the client crashes the semantics is at-most-once) [Frølund and Guerraoui 2001]. Note that clients and BS usually belong to different organizations, thus their interaction occurs through an unreliable network. It follows that, for example, a client might retransmit the same transaction request multiple times and such retransmissions might be routed to different application server replicas. Also note that the correctness requirement implies that a replicated BS must maintain state consistency internally. That is, if a transaction commits at the database, each available replica of the application server must have the state changes performed by this transaction. If the transaction aborts at the database, all available replicas must know about the abort and be able to return to the previous state.
The algorithm follows a primary-backup, passive replication approach, to allow non-deterministic execution of replicas and to eliminate redundant computations. Transactions are executed only at the primary. Before committing a transaction, the primary multicasts the state of EJBs modified by the transaction and inserts a marker in the database. The former is necessary for supporting state consistency, the latter enables a backup to determine the outcome of in-progress transactions in case the primary fails. After committing a transaction, the primary multicasts the outcome of the transaction. Replicas interact through group communication, which provides powerful guarantees regarding message delivery and membership information in spite of failures [CACM 1996]. Our group communication infrastructure isSpread. We access Spread through JBora, a thin middleware layer developed by us (see [Bartoli et al. 2005] for its features).
Although good performance and strong consistency guarantees in the presence of failures are rather conflicting requirements, we obtained a satisfactory trade-off between the two. We run theECPerf benchmark on our algorithm, by replicating only the application server layer, and found that our system compares favorably against the JBoss clustering solution for high availability. This is a significant result, having considered that JBoss clustering provides neither exactly-once execution nor state consistency (see [Wu et al. 2004] for details). At the database layer, we run a read-only load and obtained linear scalability up to 15 replicas (the maximum number of replicas that we tested). We run an update-only load and obtained a scalability of at least 30% of the number of replicas, which is a significant gain over conventional database replication protocols (see [Jiménez-Peris et al. 2002] and [Patiño-Martínez et al. 2005] for details). A new approach has defined 1-copy-snapshot isolation as correctness criterion, that enables to boost replication scalability [Lin et al. 2005] while preserving a degree of consistency very close to 1-copy-serializability. We have not yet benchmarked the system where both the application servers and database servers are replicated. This activity will be done by the end of the Adapt project (October 2005) and the results will be made publicly available on the Adapt web site.
3.2.3. Online recovery
Adaptation to internal failures would not be very useful without the ability to adapt to recoveries. Our middleware does provide this feature in the sense that reintegration of a previously failed replica is also masked to clients. A recovering replica acquires the "up-to-date state" of the service and resumes its role automatically, in particular, without suspending the service offered to clients. This feature is provided both at the application server layer and at the database layer. Online recovery at the application server layer is relatively simple to achieve, because the amount of state to be transferred is sufficiently "small" and it can be kept in main memory. Online recovery at the database layer, on the other hand, is a much more challenging task [Kemme et al. 2001]. Middle-R provides this functionality by implementing a protocol that we developed [Jiménez-Peris et al. 2002-b].
3.2.4. Load control
Our BS middleware provides several forms of internal adaptation to dynamically changing load conditions. Here we concentrate on adaptation at the database layer by summarizing the results in [Milan-Franco et al. 2004]. Other adaptability features can be found in [Bartoli et al. 2003,Bartoli et al. 2005,Antoniutti 2005]. Load balancing at the application server level is currently under development. The performance of a database system for a given workload greatly depends on the multiprogramming level (MPL), i.e., the number of transactions that are allowed to run concurrently within the database system. In particular, (I) each workload has a different optimal value for MPL; (II) optimal values may span across a wide range; and (III) a value that is "good" for a certain workload may lead to poor throughput for a different workload. This fact has important implications. One could manually tune the database system by carefully characterizing the expected workload and then tuning the MPL appropriately. However, any change in the workload could lead to sub-optimal performance. What is more important, this strategy would not be effective in environments where the workload is intrinsically dynamic.

Figure 7: Dynamic adaptation of the mupltiprogramming level (MPL) at the database layer.
Middle-R is capable of adapting the MPL to dynamic changes in the workload (seeFigure 7). Experiments with several constant workloads showed that Middle-R reaches an MPL very close to the optimal one in seconds. We remark that Middle-R obtains this result automatically, without any prior knowledge of the actual workload. Interestingly, a constant load provides little information to an adaptive system and thus constitutes a worst case scenario for adaptive algorithms [Heiss and Wagner 1991]. Middle-R varies MPL by simply varying the number of connections between Middle-R and the local database replica, since each transaction requires its own connection. The parameter measured for controlling the variations of MPL is simply the achieved throughput. This approach does not require any specific knowledge of the database internals.
Adaptation of MPL is a local feature: it occurs at each database replica and each replica adapts its MPL without any interaction with the other replicas. Middle-R implements a further global level of adaptation to load, ensuring that the load submitted to the database system as a whole is evenly distributed across the replicas. Again, this form of load balancing occurs dynamically without prior knowledge of the actual workload. We provide a brief description of this mechanism below, full details can be found in [Milan-Franco et al. 2004].
Middle-R [Patiño-Martinez et al. 2005] implements asymmetric transaction processing: each update transaction is executed at only one "primary" replica; the other replicas do not execute the transaction and simply change the affected records in an efficient manner; transactions that do not contain any update operation can be executed at any replica. Several analyses have shown that asymmetric transaction processing can outperform the symmetric approach, where all replicas execute all transactions [Jiménez-Peris et al. 2003]. Moreover, symmetric transaction processing is not feasible for systems with triggers or non-deterministic behavior. For these reasons, most commercial systems use asymmetric transaction processing. Clearly, the full power of asymmetric processing can be exploited only provided the role of primary is fairly distributed across replicas. Middle-R selects the primary for a given transaction as a function of the object sets accessed by the transaction. If the workload were static, then one could find an optimal way for determining which replica has to be the primary for which object sets. When the workload cannot be characterized in advance and/or is highly dynamic, a reassignment is necessary. In Middle-R this is achieved as follows. A selected replica analyzes its locally available information to obtain an estimate of the load of each replica (i.e., based on the object sets to be accessed by each in-progress transaction). Then it attempts to redefine the mapping between object sets and primaries so as to obtain a better load distribution. If a mapping is found that is "much better" than the current one, then the new mapping is multicast to all replicas. Experiments show that this form of global adaptation enables Middle-R to achieve a throughput very close to the optimal one (i.e, the throughput obtained with the primary assignment that is optimal for that specific workload) and that the adaptation itself occurs at basically no cost.
4. Concluding remarks
The emergence and diffusion of web services technology is creating a new business opportunity for providing value added, inter-organisational services by composing multiple basic services (BSs) into composite services (CSs). In this paper we have provided an overview of the ADAPT framework that we have developed for addressing this novel challenging scenario. On the one hand, ADAPT provides middleware support for developing higly available and dynamically adaptive BSs that can be used to build higher-level CSs. On the other hand, ADAPT includes the technology and software infrastructure necessary for defining, enacting, and monitoring inter-enterprise business processes that are implemented as CSs with guarantees of availability, scalability and adaptability not only to changing network conditions and user requirements but also to reconfigurations and repairs.
Acknowledgments
This work has been partly supported by the European Commission, Adapt project: Middleware Technologies for Adaptive and Composable Distributed Components, IST-2001-37126. Many people participated in this work: Gustavo Alonso, Etienne Antoniutti, Ozalp Babaoglu, Win Bausch, Biörn Biörnstad, Daniel Jönsson, Thomas Heinis, Yi Lin, Marta Patiño-Martínez, Vance Maverick, Milan Prica, Francisco Pérez-Sorrosal, Damián Serrano, Jorge Salas, Santosh Shrivastava, Jaksa Vuckovic, Huaigu Wu, Shuqing Wu. All of their support is gratefully acknowledged.
References
All deliverables of the Adapt project can be freely downloaded from theAdapt web site.
[Antoniutti 2005] E. Antoniutti "Performance and Adaptability of Replicated Web Services Through Message Packing", Proc. of IADIS International Conference on Applied Computing 2005, Algarve, Portugal.
[Bartoli et al. 2005] A. Bartoli, M. Prica, E. Antoniutti "A Replication Framework for Program-to-Program Interaction across Unreliable Networks and its Implementation in a Servlet Container", Concurrency and Computation: Practice and Experience, to appear, John Wiley and Sons.
[Bartoli et al. 2003] A. Bartoli, C. Calabrese, M. Prica, E. Antoniutti Di Muro, A. Montresor, "Adaptive Message Packing for Group Communication Systems", Workshop on Reliable and Secure Middleware, OTM 2003 Workshops, Lecture Notes in Computer Science 2889, Springer Verlag (November 2003).
[Babaoglu et al. 2004] O. Babaoglu, A. Bartoli, V. Maverick, S. Patarin, J. Vuckovic, H. Wu "A Framework for Prototyping J2EE Replication Algorithms", International Conference on Distributed Objects and Applications (DOA) 2004, pages 1413-1426.
[CACM 1996]Special Issue on Group Communication, Communications of the ACM, 39(4), April 1996.
[Deliverable D6]Service Specification Language, September 2003.
[Deliverable D7]Composition Language, September 2003.
[Deliverable D8]Analysis Tool, September 2004.
[Deliverable D13]BS Middleware, January 2005.
[Elmagarmid 1992] A. K. Elmagarmid, editor.Database Transaction Models. Morgan Kaufmann Publishers, San Mateo, CA, 1992.
[Frølund and Guerraoui 2001] S. Frølund and R. Guerraoui, "Implementing E-Transactions with Asynchronous Replication", IEEE Transactions on Parallel and Distributed Systems, 12 (2), February 2001.
[Heiss and Wagner 1991] H. Heiss, R.Wagner "Adaptive Load Control in Transaction Processing Systems", Proc. of 17th VLDB, 1991.
[Jajodia et al 1997] S. Jajodia and L. Kerschberg, editors.Advanced Transaction Models and Architectures. Kluwer Academic Publishers, 1997.
[Jiménez-Peris et al. 2002] R. Jiménez-Peris, M. Patiño-Martínez, B. Kemme, G. Alonso"Improving the Scalability of Fault-Tolerant Database Clusters" IEEE 22nd Int. Conf. on Distributed Computing Systems, ICDCS'02, pp. 477-484. Vienna, Austria. July 2002.
[Jiménez-Peris et al. 2002-b] R. Jiménez-Peris, M. Patiño-Martínez, G. Alonso"An Algorithm for Non-Intrusive, Parallel Recovery of Replicated Data and its Correctness", IEEE 21nd Int. Symposium on Reliable Distributed Systems, SRDS'02, pp. 477-484.
[Jiménez-Peris et al. 2003] R. Jiménez-Peris, M. Patiño-Martínez, G. Alonso, and B. Kemme.Are Quorums an Alternative for Data Replication?, ACM Transactions on Database Systems, Vol. 28, N. 3, Sept. 2003, pp. 257-294, ACM Press.
[Kemme et al. 2001] B. Kemme, A. Bartoli, O. Babaoglu "On-line reconfiguration in replicated databases based on group communication", Proc. IEEE/IFIP Conference on Dependable Systems and Networks DSN-2001, pp.117-126.
[Kemme et al. 2005] B. Kemme, R. Jimenez, M. Patiño, J. Salas "Exactly once interaction in a multi-tier architecture", VLDB Workshop on Design, Implementation, and Deployment of Database Replication.
[Lin et al. 2005] Y. Lin, B. Kemme, M. Patiño-Martínez, R. Jiménez-Peris."Middleware based Data Replication providing Snapshot Isolation". ACM SIGMOD Int. Conf. on Management of Data. Baltimore, Maryland, USA. Jun. 2005.
[Milan-Franco et al. 2004] J. M. Milan-Franco, R. Jiménez-Peris, M. Patiño-Martínez, B. Kemme"Adaptive Distributed Middleware for Database Replication", ACM/IFIP/USENIX Middleware Conference, Toronto (Canada). Oct. 2004.
[Patiño-Martínez et al. 2005] M. Patiño-Martinez, R. Jimenez-Peris, B. Kemme, G. Alonso."Consistent Database Replication at the Middleware Level". ACM Transactions on Computer Systems (TOCS). In Press.
[Pautasso and Alonso 2003] C. Pautasso, G. Alonso, "Visual Composition of Web Services", Proc. the 2003 IEEE Symposia on Human Centric Computing Languages and Environments (HCC 2003), Auckland (New Zealand), Oct. 2003.
[Pautasso and Alonso 2004] C. Pautasso, G. Alonso. "JOpera: a Toolkit for Efficient Visual Composition of Web Services", International Journal of Electronic Commerce (IJEC), 9(2):107-141, Winter 2004/2005
[Pautasso and Alonso 2005] C. Pautasso, G. Alonso, "Flexible Binding for Reusable Composition of Web Services", Workshop on Software Composition (SC 2005), Edinburgh (Scotland), Apr. 2005.
[Pautasso et al, 2005] C. Pautasso, T. Heinis, G. Alonso, "Autonomic Execution of Service Compositions", Proc. of the 3rd International Conference on Web Services (ICWS 2005), Orlando (Florida), July 2005.
[WS-I 2003], Web Services Interoperability Consortium, " Supply Chain Management Sample Application Architecture", WS-I, Version 1.0, December 2003.
[Woodman et al. 2004] S. Woodman, D. Palmer, S. Shrivastava, S. Wheater "Notations for the Specification and Verification of Composite Web Services", Proc. 8th IEEE International Enterprise Distributed Object Computing Conference, Monterey, USA, Sept. 2004.
[Wu et al. 2004] H. Wu, B. Kemme, V. Maverick, "Eager Replication for Stateful J2EE Servers", Int. Symposium on Distributed Objects and Applications (DOA) 2004.
[Wu and Kemme 2005] H. Wu, B. Kemme, "Fault-tolerance for Stateful Application Servers in the Presence of Advanced Transactions Patterns", Proc. Int. Symposium on Reliable Distributed Systems (SRDS) 2005.
[Wu and Kemme 2005-b] S. Wu, B. Kemme, "Postgres-R(SI): Combining Replica Control with Concurrency Control based on Snapshot Isolation", Proc. Int. Int. Conference on Data Engineering (ICDE) 2005.
1 The Adapt project is funded by the European Commission: Middleware Technologies for Adaptive and Composable Distributed Components, IST-2001-37126.