In distributed software contexts, Web Services (WSs) that provide transactional properties are useful to guarantee reliable Transactional Composite WSs (TCWSs) execution and to ensure the whole system consistent state even in presence of failures. Fails during the execution of a TCWS can be repaired by forward or backward recovery processes, according to the component WSs transactional properties. In this paper, we present the architecture and an implementation of a framework, called FaCETa, for efficient, fault tolerant, and correct distributed execution of TCWSs. FaCETa relies on WSs replacement, on a compensation protocol, and on unrolling processes of Colored Petri-Nets to support fails. We implemented FaCETa in a Message Passing Interface (MPI) cluster of PCs in order to analyze and compare the behavior of the recovery techniques and the intrusiveness of the framework.
Large computing infrastructures, like Internet increase the capacity to share
information and services across organizations. For this purpose, Web Services
(WSs) have gained popularity in both research and commercial sectors. Semantic
WS technology [
WS Composition and the related execution issues have been extensively
treated in the literature by guaranteeing user QoS requirements and fault
tolerant execution [
Generally, the control flow and the order of WSs execution is represented
with a structure, such as workflows, graphs, or Petri-Nets [
In previous works [
In this paper, we present an implementation of our Executer framework, called FaCETa (FAult tolerant Cws Execution based on Transactional properties), for efficient, fault tolerant, and correct distributed execution of TCWSs. We implemented FaCETa in a Message Passing Interface (MPI) cluster of PCs in order to analyze and compare the efficiency and performance of the recovery techniques and the intrusiveness of the framework. The results show that FaCETa efficiently implements fault tolerant strategies for the execution of TCWSs with small overhead. 2
This Section recall some important issues related to transactional properties
and backward and forward recovery, presented in our previous works [
We define a query in terms of functional conditions, expressed as input
and output attributes; QoS constraints, expressed as weights over criteria; and
the required global transactional property as follows. A Query Q is a 4-tuple
(IQ, OQ, WQ, TQ), where:
– IQ is a set of input attributes whose values are provided by the user,
– OQ is a set of output attributes whose values have to be produced by the
system,
– WQ = {(wi, qi) | wi ∈ [
The transactional property (T P ) of a WS allows to recover the system in case of
failures during the execution. The most used definition of individual WS
transactional properties (T P (ws)) is as follows [
In [
According to these transactional properties, we can establish two possible recovery techniques in case of failures: – Backward recovery: it consists in restoring the state (or a semantically closed state) that the system had at the beginning of the TCWS execution; i.e., all the successfully executed WSs, before the fail, must be compensated to undo their produced effects. All transactional properties (p, a, c, pr, ar, and cr) allow backward recovery; – Forward recovery: it consists in repairing the failure to allow the failed WS to continue its execution. Transactional properties pr, ar, and cr allow forward recovery. 1 A marked CPN is a CPN having tokens in its places, where tokens represent that the values of attributes (inputs or outputs) have been provided by the user or produced by a WS execution. 2.2
The global T P of CPN-T CW SQ ensures that if a component WS, whose T P
does not allow forward recovery fails, then all previous executed WSs can be
compensated by a backward recovery process. For modeling TCWS backward
recovery, we have defined a backward recovery CPN, called BRCPN-T CW SQ,
associated to a CPN-T CW SQ [
The execution control of a TCWS is guided by a unrolling algorithm of its corresponding CPN-T CW SQ. A WS is executed if all its inputs have been provided or produced, i.e., each input place has as many tokens as WSs produce them or one token if the user provide them. Once a WS is executed, its input places are unmarked and its output places (if any) are marked.
The compensation control of a TCWS is also guided by a unrolling algorithm. When a WS represented by a transition s fails, the unrolling process over CPNT CW SQ is halted,an Initial Marking on the corresponding BRCPN-T CW SQ is set (tokens are added to places associated to input places of the faulty WS s, and to places representing inputs of BRCPN-T CW SQ, i.e., places without predecessors) and a backward recovery is initiated with the unrolling process over BRCPN-T CW SQ. We illustrate a backward recovery in Figure 1. The marked CPN-T CW SQ depicted in Figure 1(a) is the state when ws4 fails, the unrolling of CPN-T CW SQ is halted, and the Initial Marking on the corresponding BRCPNT CW SQ is set to start its unrolling process (see Figure 1(b)), after ws03 and ws05 are executed and ws7 is abandoned before its invocation, a new Marking is produced (see Figure 1(c)), in which ws01 and ws02 are both ready to be executed and can be invoked in parallel. Note that only compensatable transitions have their corresponding compensation transitions in BRCPN-T CW SQ. 2.3
During the execution of TCWSs, if a failure occurs in an advanced execution
point, a backward recovery may incur in high wasted resources. On the other
hand, it is hard to provide a retriable TCWS, in which all its components
are retriable to guaranty forward recovery. We proposed an approach based
on WS substitution in order to try forward recovery [
In a service class, the functional equivalence is defined according the WSs input and output attributes. A WS s is a functional substitute, denoted by ≡F , to another WS s∗, if s∗ can be invoked with at most the input attributes of s and s∗ produces at least the same output attributes produced by s. s is an Exact Functional substitute of s∗, denoted by ≡EF , if they have the same input and output attributes. Figure 2 illustrates several examples: ws1 ≡F ws2, however ws2 6≡F ws1, because ws1 does not produce output a5 as ws2 does. ws1 ≡F ws3, ws3 ≡F ws1, and also ws1 ≡EF ws3. WS because all transactional properties allow backward recovery. A WS with T P (s) = pr can be replaced by any other retriable WS (pr,ar,cr), because all of them allow forward recovery. An atomic WS allows only backward recovery, then it can be replaced by any other WS which provides backward recovery. A compensatable WS can be replaced by a WS that also provides compensation as c and cr WSs. A cr WS can be only replaced by another cr WS because it is the only one allowing forward and backward recovery. Thus, a WS s is Transactional substitute of another WS s∗, denoted by ≡T , if s is a Functional substitute of s∗ and their transactional properties allow the replacement.
In Figure 2, ws1 ≡T ws2, because ws1 ≡F ws2 and T P (ws2) = cr, then ws2 can behave as a pr WS; however ws1 6≡T ws3, even ws1 ≡F ws3, because as T P (ws3) = p, w3 cannot behave as a pr WS. Transactional substitution definition allows WSs substitution in case of failures.
When a substitution occurs, the faulty WS s is removed from the CPNT CW SQ, the new s∗ is added, but we keep the original sequential relation defined by the input and output attributes of s. In that way, the CPN-T CW SQ structure, in terms of sequential and parallel WSs, is not changed. For compensatable WSs, it is necessary Exact Functional Substitute to do not change the compensation control flow in the respective BRCPN-T CW SQ. In fact, when a compensatable WS is replaced, the corresponding compensate WS must be also replaced by the new corresponding one in the BRCPN-T CW SQ. The idea is to try to finish the TCWS execution with the same properties of the original one.
In case of failure of a WS s, depending on the T P (s), the following actions could be executed: – if T P (s) is retriable (pr, ar, cr), s is re-invoked until it successfully finish (forward recovery); – otherwise, another Transactional substitute WS, s∗, is selected to replace s and the unrolling algorithm goes on (trying a forward recovery); – if there not exist any substitute s∗, a backward recovery is needed, i.e., all executed WSs must be compensated in the inverse order they were executed; for parallel executed WSs, the order does not matter.
When in a service class there exist several WSs candidates for replacing a
faulty s, it is selected the one with the best quality measure. The quality of a
transition depends on the user query Q and on its QoS values. WSs
Substitution is done such that the substitute WS locally optimize the QoS. If several
transitions have the same value of quality, they can be randomly selected to be
the substitute. A similar quality measure is used in [
In this Section we present the overall architecture of FaCETa, our execution framework. The execution of a TCWS in FaCETa is managed by an Execution Engine and a collection of software components called Engine Threads, organized in a three levels architecture. In the first level the Execution Engine receives the TCWS (represented by a CPN). It is in charge of initiating, controlling, and monitoring the execution of the TCWS. To do so, it launches, in the second layer, an Engine Thread for each WS in TCWS. Each Engine Thread is responsible for the execution control of its WS. They receive WS inputs, invoke the respective WS, and forward its results to its peers to continue the execution flow. In case of failure, all of them participate in the backward or forward recovery process. Actual WSs are in the third layer. Figure 3 roughly depicts the overall architecture.
By distributing the responsibility of executing a TCWS across several
Engine Threads, the logical model of our Executer allows distributed execution
of a TCWS and is independent of its implementation, i.e., this model can be
implemented in a distributed memory environment supported by message passing
(see Figure 4(a)) or in a shared memory platform, e.g., supported by a
distributed shared memory [
Typically, a component of a TCWS can be a simple transactional WS or TCWS. Thus, we consider that transitions in the CPN, representing the TCWS, (a) Distributed memory system
(b) Distributed shared memory system could be WSs or TCWSs. WSs have its corresponding WSDL and OWLS documents. TCWSs can be encapsulated into an Executer; in this case the Execution Engine has its corresponding WSDL and OWLS documents. Hence, TCWSs may themselves become a WS, making TCWS execution a recursive operation (see Figure 3). 3.1
We implemented FaCETa in a MPI Cluster of PCs (i.e., a distributed memory platform) following a Master/Slaves-SPDM (Single Process Multiple Data) parallel model. The Execution Engine run in the front-end of the Cluster waiting user execution requests. To manage multiple client requests, the Execution Engine is multithreading. The deployment of a TCWS implies several steps: Initial, WS Invocation, and Final phases. In case of failures, recovery phases could be executed: Replacing phase, allowing forward recovery or Compensation phase for backward recovery.
Whenever the Execution Engine (master) receives a CPN-T CW SQ and its corresponding BRCPN-T CW SQ, it performs the Initial phase: (i) start, in different nodes of the cluster, an Engine Thread (peer slaves) responsible for each transition in CPN-T CW SQ, sending to each one its predecessor and successor transitions as CPN-T CW SQ indicates (for BRCPN-T CW SQ the relation is inverse) and the corresponding WSDL and OWLS documents (they describe the WS in terms of its inputs and outputs, its functional substitute WSs, and who is the compensation WS, if it is necessary); and (ii) send values of attributes in IQ to Engine Threads representing WSs who receive them. Then the master wait for a successfully execution or for a message compensate in case of a backward recovery is needed.
Once Engine Threads are started, they receive the part of CPN-T CW SQ and BRCPN-T CW SQ that each Engine Thread concerns on, sent by the Execution Engine in the Initial phase. Then, they wait for the input values needed to invoke its corresponding WS. When an Engine Thread receives all input values (sent by the master or by other peers) and all its predecessor peers have finished, it executes the WS Invocation phase, in which the actual WS is remotely invoked. If the WS finishes successfully, the Engine Thread sends WS output values to Engine Threads representing its successors and wait for a finish or compensate message. If the WS fails during the execution, the Engine Thread tries a forward recovery: if T P (WS) is retriable, the WS is re-invoked until it successfully finish; otherwise the Engine Thread executes the Replacing phase: the Engine Thread has to determine the best substitute among the set of functional substitute WSs; it calculates the quality of all candidates according their QoS criteria values and the preferences provided in the user query; the one with the best quality is selected to replace the faulty WS; this phase can be executed for a maximum number of times (M AXT ries). If replacing is not possible, the Compensation phase has to be executed: the Engine Thread responsible of the faulty WS sends the message compensate to Execution Engine and control tokens to successor peers of the compensation WS, in order to inform about this failure and start the unrolling process over BRCPN-T CW SQ; once an Engine Thread receives all control tokens, it invokes the compensation WS; the unrolling of BRCPN-T CW SQ ensure the invocation of compensation WSs, s0, in the inverse order in which their corresponding WS, s, were executed. Note that forward recovery is executed only by the Engine Thread responsible of the faulty WS, without intervention of the master neither other peers; while backward recovery need the intervention of all of them.
If the TCWS was successfully executed, in the Final phase the master receives all values of attributes of OQ, in which case it broadcasts a finish message to all slaves to terminate them, and returns the answer to user; otherwise it receive a compensate message indicating that a backward recovery has to be executed, as it was explained above, and return an error message to user. Assumptions: In order to guarantee the correct execution of our algorithms, the following assumptions are made: (i) the network ensures that all packages are sent and received correctly; (ii) the Execution Engine and Engine Threads run in a reliable cluster, they do not fail; (iii) the Engine Threads receive all WS outputs when its corresponding WS finishes, they cannot receive partial outputs from its WS; and (iv) the component WSs can suffer silent or stop failures (WSs do not response because they are not available or a crash occurred in the platform); we do not consider runtime failures caused by error in inputs attributes (e.g., bad format or out of valid range) and byzantine faults (the WS still responds to invocation but in a wrong way). 4
We developed a prototype of FaCETa, using Java 6 and MPJ Express 0.38 library to allow the execution in distributed memory environments. We deployed FaCETa in a cluster of PCs: one node for the Execution Engine and one node for each Engine Thread needed to execute the TCWS. All PCs have the same configuration: Intel Pentium 3.4GHz CPU, 1GB RAM, Debian GNU/Linux 6.0, and Java 6. They are connected through a 100Mbps Ethernet interface.
We generated 10 compensatable TCWSs. All those TCWSs were
automatically generated by a composition process [
The OWLS-API 3.0 was used to parse the WS definitions and to deal with the OWL classification process.
The first group of experiments were focussed on a comparative analysis of the recovery techniques. The second group of experiments evaluates the overhead incurred by our framework in control operations to perform the execution of a TCWS and to execute the fault tolerant mechanisms.
To simulate unreliable environments, we define five different conditions wherein all WSs have the same probability of failure: 0.2, 0.15, 0.1, 0.005, and 0.001. The executions on these unreliable environments were done in three scenarios to support the fails: (i) backward recovery (compensation, red bars in Figure 5), (ii) forward recovery because all WSs are retriable (retry, light blue bars in Figure 5), and (iii) forward recovery (substitution, gray bars in Figure 5). On each scenario all TCWSs were executed 10 times.
Each TCWS was also executed 10 times in a reliable environment, in which all WSs have 0 as probability of failures (no-faulty, blue bars in Figure 5) in order to classify them according their average total execution time in three groups: less than 1500ms (Figure 5(a)), (ii) between 1500ms and 3500ms (Figure 5(b), and (more than 3500ms (Figure 5(c)).
In Figure 5 we plot the average of the total execution time according the number of failed WSs, in order to compare all recovery techniques. The results show that when the number of failed WSs is small (i.e., the probability of failures is less than 20%) backward recovery (compensation) is the worst strategy because almost all component WSs had been executed and have to be compensated. Moreover, when the average of the total execution time of TCWSs is high (greater than 1500ms) forward recovery with retry strategy is better than forward recovery with substitution due to the substitute normally has a bigger response time than the faulty WS. By the other side, in cases in which the probability of failure is greater than 30%, backward recovery whit compensation behaves better than the other ones (even the final results is not produced) because there are many faulty services and only few have to be compensated.
Another issue that can be observed it is the number of outputs received before the backward recovery mechanism has to be executed. In this experiment, the average percentage of outputs received before compensation was 37%. All these outputs are lost or delivered as a set of incomplete (and possibly meaningless and useless) outputs to the user. This percentage is related to the average percentage of compensated services, which is 80%, confirming the overhead, the possible unfulfillment of QoS requirements, and the lost outputs. Definitely, backward (a) Total Exec. Time less than 1500ms
(b) Total Exec. Time between 1500ms and 3500ms (c) Total Exec. Time more than 3500ms recovery should be executed only in absence of another alternative, at early stages of execution of a TCWS, or high faulty environments.
To measure the intrusiveness of FaCETa incurred by control activities, we execute the same set of experiments describe above, but we set to 0 the response time of all WSs. Table 4 shows the average overhead under all different scenarios.
The average overhead of FaCETa only depends on the number of components WSs in a TCWS. It does not depend on the total response time of TCWS. It means that while the total response time is higher the overhead % will decrease. It is clear that the reason behind the backward recovery strategy overhead (increased by 2%) is the amount of coordination required to start the compensation and the fact that a new WS execution (the compensation WS execution) has to be performed for each successfully executed WS, in order to restore the consistent system state. Additionally, the compensation process has to be done following the unrolling algorithm of the respective BRCPN-T CW SQ. We do not consider to wait before the retry of a failed WS execution; therefore, the increased overhead of retry a WS is almost imperceptible.
As the service class for each WS is sent by the Execution Engine in the Initial phase, each Engine Thread has the list of the functional substitute WSs sorted according their quality, then there is virtually no overhead when searching for a functional substitute WS to replace a faulty one.
Based on the results presented above, we can conclude that FaCETa
efficiently implements fault tolerant strategies for the execution of TCWSs with
admissible small overhead.
Regarding fault tolerant execution of Composite WSs (CWSs), there exist
centralized and distributed approaches. Generally centralized approaches [
In distributed approaches, the execution process proceeds with
collaboration of several entities. We can distinct two kinds of distributed coordination
approach. In the first one, nodes interact directly based on a peer-to-peer
application architecture and collaborate, in order to execute a CWS with every node
executing a part of it [
FENECIA framework [
Another series of works rely on a shared space to exchange information
between nodes of a decentralized architecture, more specifically called a tuple
space [
Facing our approach against all these works, we overcome them because the
execution control is distributed and independent of the implementation (it can
be implemented in distributed or shared memory platforms), it efficiently
executes TCWSs by invoking parallel WSs according the execution order specified
by the CPN, and it is totally transparent to users and WS developers, i.e., user
only provides its TCWS, that could be automatically generated by the
composition process [
There exist some recent works related to compensation mechanism of CWSs
based on Petri-Net formalism [
In this paper we have presented FaCETa, a framework for ensuring correct and fault tolerant execution order of TCWSs. The execution model is distributed, can be implemented in distributed or share memory systems, is independent of implementation of WS providers, and is transparent to users and developers. To support failures, FaCETa implements forward recovery by replacing the faulty WS and backward recovery based on a unrolling process over a CPN representing the compensation flow. We have presented a distributed memory implementation of FaCETa in order to compare the behavior of both recovery techniques. The results show that FaCETa efficiently implements fault tolerant strategies for the execution of TCWSs with small overhead.
We are currently working on implementing FaCETa in a distributed shared memory platform in order to test the performance of the framework in centralized and decentralized platforms. Our intention is to compare both implementations under different scenarios (different characterizations of CPNs) and measure the impact of compensation and substitution on QoS.