Software replication in three-tiers architectures:
is it a real challange?
R. Baldoni and C. Marchetti,
Dipartimento di Informatica e Sistemistica
Universit`a di Roma “La Sapienza”
Via Salaria 113, 00198, Roma, Italy
E.mail:
baldoni,marchet
@dis.uniroma1.it
Abstract
This paper is a first attempt to study the problem of han- dling software replication in three tiers architectures. In particular a study based on sychronization and communi- cation patterns imposed by replication is presented. We show how the complexity of the replication scheme is af- fected by the determinitic (or not) behavior of the members of the backtier. We also give two generic synchronization and communication patterns used in two and three tiers replication. Well-known schemes such us active and pas- sive replication are particular instances of these generic patterns.
Keywords: replication, message patterns, fault tolerance, three tiers distributed systems.
1 Introduction
In the last twenty years there has been a moving from software and/or hardware custom systems to “Commer- cial Off-The-Shelf” (COTS) systems. Roughly speaking, a COTS system is something “catalog orderable” rather than custom developed. In particular, early-90s were the take off time of software implemented on off-the shelf hardware.
This solution was motivated by economic reasons to reduce the cost of hardware. More recently the notion of COTS has been proposed also for software. Using COTS software components reduces both the cost of components and the risk of the integration activity while increasing the modu- larity of the system.
COTS systems have also give a shot to the passage from two-tiers architecture to three-tiers distributed systems ar- chitecture. In the past distributed systems were built as
This work is partially supported by the MURST (Ministero dell’Universit`a e della Ricerca Scientifica e Tecnologica) and by the CNR (National Research Council.
two-tiers: client and servers. Clients embed the presentation part, servers embed processing and the application logic is usually split on clients and servers. This scheme matches systems with custom hardware and/or software. Thanks to the increasing modularity of COTS systems, three-tier ar- chitectures are becoming widespread in current distributed applications. The middle tier actually separates clients from backend servers implementing many of the applica- tion logic. As an example, a WWW server can be con- sidered as a sort of unsophisticated middletier between a WWW browser and a backend database (it actually orches- trates the right access to the database server). At network level a Server Load Balancer (SLB) is a middletier between a WWW server farm and Web browsers. SLB is used in high performance WEB servers to dispatch incoming http requests from external browsers. From the operational point of view, a middleware, such as CORBA, DCOM etc, is a typical software used to glue distinct tiers.
To get the market requirements, in a three-tier architec- ture the client code has to be small (possibly only the pre- sentation code of an application should be installed in order to run in as many devices as possible), midtier embeds ap- plication logic possibly without containing any part of the application state which should be completely managed by independent servers which should be accessed by means of standard interfaces.
Replication is a technique used to increase the fault tol- erance and the availability of a system. First replication schemes were developed over custom hardware. Tandem and Stratus solutions were leaders in such market during the 80s. Afterwards, the diffusion of the off-the-shelf hardware makes a software based replication easier and cost effective [9]. Group toolkits such as ISIS [2], TOTEM [15], HORUS [18], TRANSIS [1] and Phoenix [13] (just to name a few) were the software platforms that provided those services (such as totally and causally ordered communication, state transfer and group membership [2]) needed for a success-
1
fully implementation of software-based replication. Such schemes were typical examples of how to implement repli- cation in two tiers distributed systems. In particular two schemes has emerged [9]: active1and passive (or primary- backup) replication [4]. The active replication paradigm does not impose and exchange of messages among repli- cas, however it requires each replica to be deterministic and relies on the availability of a total order multicast primitive [3] from the communication subsystem. This allows a to- tal order of requests incoming from distinct clients at each replica. To implement this primitive it is necessary a sort of coordination (i.e., synchronization) among the communica- tion subsystem entities local at each object. Passive repli- cation needs a coordination among replicas, at each time of the evolution of the replication protocol. For example when handling a request, to support a primary and to elect a new primary in case of failure of the previous one.
This paper wants to be a first attempt to study replica- tion schemes in the context of three-tier distributed sys- tems. In particular we would like to understand if the new setting brings some new research challenges or it is an its pure engineering extension of the replication schemes used in two tiers architectures. More specifically we focus on the synchronization and communication patterns pro- duced by replication schemes (independently of the basic assumptions used to model the underlying communication subsystem such as synchronous, asynchronous and timed [6]) and we give a general synchonization and communi- cation pattern that encompasses all replication schemes im- plementable in three tiers architectures.
As the three tiers architecture imposes (i) light and in- dependent clients and (ii) a backend tier formed by au- tonomous and independent resources, the replication logic has to be a part of the application logic. Hence it should be moved in the midtier. The replication logic includes the handling of the synchronization and communication pattern due to replication.
The paper is structured as follows. Section 2 presents the model of the distributed systems. Section 3 shows replication schemes in two tiers architectures and Section 4 proposes synchronization and communication patters to be used in three tiers architectures. Section 5 concludes the paper.
2 Distributed System model
This section describes the nature of the computation, the structure of a client and the correctness criterion used by replication.
1This is also called state machine approach [17].
2.1 Objects
The distributed system consists of objects which ex- change messages by means of primitives provided by the communication subsystem. Objects can be of three types:
clients ( ), application servers ( ) and replicas ( -s).
Objects can either behave correctly (i.e., following their specifications) or crash. We do not model the message transfer delay so the distributed system could be asyn- chronous (message transfer delay unpredictable but finite), synchronous (predictable message transfer delay) or timed [6] ( message transfer delay predictable most of the times).
Objects can synchronize themselves by using a wait-free (i.e., non-blocking) scheme [12, 10]. As an example in the context of the asynchronous model, this means that a con- sensus service is provided by the underlying system [5], in the context of timed systems such synchronization can be provided by a leader election function as the one shown in [7].
2.2 Clients
The structure of a client is similar in two and three tiers architectures. A client issues a invocation on behalf of an end-user and waits for a result . More specifically
(resp. ) represents the -th invocation (resp. result) is- sued (resp. received by ) (as shown in the figures). We assume that after an invocation a client eventually receive back a result for that invocation. At this aim the client em- beds a retransmission mechanism triggered by a time-out (the only form of failure detection available at client side) and a message filtering mechanism to remove result dupli- cates. For performance reasons the client can send its invo- cation to any non-empty subset of either application servers or object replicas in three tiers and two tiers architectures respectively. For clarity, this sending is shown in the figures by a thick line labeled with a pair which abstracts a message pattern formed by (with ) point-to-point messages sent by the client to distinct entities. More gen- erally in the figures, a thick line labeled with a pair
abstracts a message pattern formed by distinct mes- sage patterns.
2.3 Correctness Criterion
Requests linearizability (or one-copy equivalence) is the classical adopted correctness criterion for replication [11].
Linearizability means that the ordering of invocations from distinct clients at each replica has to be the same. As a con- sequence the sequence of invocations represents a sort of shared state for the replication logic. Necessary conditions to get linearizability are:
(b) active replication
request ordering diffuse result (a) Passive Replication
compute result
request ordering
compute result
"!
many-to-many synch one-to-many synch many-to-many synch
Figure 1. Replication logic in two tiers architectures
# Order. Two invocations incoming from distinct clients have to be ordered in the same way at each entitity (application server or request object);
# Atomicity. If a non-crashed entity executes a client in- vocation , then all non crashed entities have to execute
.
3 Replication in two-tiers architectures
This section describes the classic replication schemes (active and passive replication) used in two tiers architec- tures. Then it intruduces a generic replication scheme that includes active and passive replication as particular cases.
3.1 Passive Replication
In passive replication (Figure 1.a) a client sends the re- quest to a set of distinct -s, the primary eventually re- ceives the invocation and computes the result, then it dif- fuses the result to the other replicas by means of a one-to- many synchronization that in the simplest form is composed of two update messages sent by the primary and two acks from the replicas to the client.
The request ordering required by linearizability is en- sured by the presence of one primary that actually acts as request serializer. The ”request ordering” many-to-many synchronization is needed to ensure the presence of at most one primary at a time. From an abstract point of view that synchronization ensures that at the time of the receipt of the invocation by the primary , there is a majority of -s that support as primary.
In the context of timed asynchronous model, this means that there exists a service of primary (leader) election which runs concurrently to the replication pattern execution. This service guarantees the presence of at most one leader at a time where a leader is one object that receives a support message, in a timely way, from a majority of objects [7]. In the context of the asynchronous model, the many-to-many
synchronization cen be realized by a service of group mem- bership which provides each object with the same sequence of views [3, 16]. A view contains all non-crashed objects.
Therefore the primary can be selected by any object in the view using the same deterministic rule. Another method has been proposed by Guerraoui and Frolund in [8]. They use the notion of Write-Once-Register [10] which is actually a simple extension of a consensus object [10].
Note that the “request ordering” and the one-to-many synchronization allow to associate a result to each invoca- tion at each replica. This is a necessary condition to ensure atomicity despite a failure of the primary.
Let us finally remark that the client does not know the identifier of the primary. It sends its invocation to a set of objects if nobody of these objects is the primary then repli- cas filter out the invocation and the client will retransmit the request to other objects after its timeout expiration. Even though this mechanism ensures that eventually the invoca- tion gets the primary, it introduces a performance penalty.
On the other hand, it avoids the client to have the knowl- edge of the identifier of the primary which induces a tight coupling between clients and replicas.
3.2 Active Replication
In active replication (Figure 1.b) object replicas are de- terministic. A client sends the request to all -ss, each replica computes independently the result and sends it back to the client which, in turn, passes the first arrived result to the end-user and filters out the others. To ensure request ordering, this replication scheme needs a primitive of total order multicast (examples of such primitives can be found in [3], [14]) provided by the underlying communication sys- tem. This primitive induces a synchronization between all the replicas and it has been shown that, in an asynchronous system, this problem is hard as consensus [5]. As repli- cas are deterministic, the request ordering implies atomic- ity. This makes useless the presence of a synchronization after the “computing result” phase.
invocation result
decide result request ordering
compute result
many-to-many synch many-to-many synch
Figure 2. A general scheme for two tiers repli- cation logic
3.3 Generic Replication Scheme
The generic replication scheme is shown in Figura 2. A client sends the request to replicas, each one of the repli- cas computes independently the result, then a synchroniza- tion among all the replicas is needed to select one of the results, then (with ) replicas sends back the selected result to the client (in Figure 2 this is abstracted by the thick line labeled ) which, in turn relays the first arrived result to the end-user and filters out the others.
Request ordering is then given by the first synchronization while the association between a request and the computed result (which is necessary to get atomicity) is given by the
“decide result” synchronization.
Let us now show how active and passive replications are instances of the generic replication pattern. If we assume deterministic replicas and , all the results com- puted by replica will be the same (so no need to execute the
“decide result” synchronization). Then we get active repli- cation. Let us assume and one primary at a time. As a consequence, only the primary computes the result and the “decide result” synchronization boils down to a simple one-to-many synchronization to diffuse the primary’s result to the other replicas.
4 Replication in Three Tiers Architectures
In two tiers architectures tasks including the manage- ment of the replica state and of the snchronization and com- munication pattern were caried out by one entity (i.e., the object replica). Key constraints of a three tiers architecture are (i) independence between the entity that manages the state of the application and the ones that manages the ap- plication logic and (ii) no coordination among object repli- cas. In terms of replication, this means that application servers manage mechanisms necessary to ensure lineariz-
ability2 (i.e., request ordering and atomicity) while object replicas the state of the application through standard inter- faces.
As a consequence a client issues an invocation to the ap- plication servers tier and the latter forwards the invocation to object replicas which form the backend tier. Both appli- cation servers that object replicas can use an independent replication style. So in the following with the term
replication we mean that the midtier uses the replication style while the backend uses .
In the rest of the section we first define the structure of an application server and of the object replica. Then we study the replication schemes derived directly by the application of active and passive replication style to midtier and back- end respectively. Finally, we present the generic replication scheme of three tiers architectures.
4.1 Application Server
An application server receives invocation from clients, and forwards it to the object replicas according to their replication style. As -s have to implement the replication logic (i.e., mechanisms to ensure linearizability), they needs wait-free primitive to synchronize themselves.
In particular the application server tier has to label each in- vocation with a sequence number agreed by all the -s.
Moreover, has to embed mechanisms: (i) to filter out multiple requests of the same invocation, (ii) to filter out multiple identical results of the same invocation and (iii) to retransmit and invocation after a timeout expiration.
4.2 Object Replica
An object replica exposes three methods: compute() get() and set(). compute() returns the result of the original client invocation to the application server. For simplicity we assume that compute() does not invoke any methods of objects residing on another server. set() stores into the ap- plication state the invocation result selected by the midtier.
get() returns the state of the object.
We assume each object replica embeds mechanisms: (i) to filter out multiple instance of the same invocation (ii) to buffer arrived but not yet executed invocations and (iii) to execute invocations according to the request ordering im- posed by the midtier.
4.3 Passive/Passive Replication
In passive/passive replication (Figure 3.a), a client sends the request to a set of distinct -s, the primary even- tually receives the invocation as in two tiers architectures,
2In other words, this means that wait-free many-to-many synchroniza- tions have to be be confined within the midtier. Inter-tiers interactions should be as light as possible.
invocation result invocation result
request ordering
request ordering
compute result
(a) passive/passive replication (a) passive/active replication
compute result
diffuse result
set decided result
decide result
one-to-many synch
many-to-many synch many-to-many sych one-to-many synch
Figure 3. Examples of replication Schemes in three tiers architectures
then it serializes the invocations (assigning for example a sequence number to each invocation) and forwards it to the
primary. The latter computes the result and sends it back to the primary which, in turn, sends the result to the other
-s using a one-to many sychronizations. The primary sends the result to the other replicas invoking their set() methods including the result and the identifier of the invoca- tion as parameters. Finally a result is returned to the client by the primary.
As in two tiers architectures, request ordering required by linearizability is ensured by the presence of the pri- mary which needs an underlying wait-free many-to-many synchronization mechanism to support its leadership. Also the diffuse results synchronization is used for atomicity.
Note that at the end of the last synchonization all -s store the same sequence of invocations and, for each invocation, its result.
In this scheme the only assumption needed for the con- sistent update of the object replica is the use of an eventu- ally reliable point-to-point communication primitive (if the sender and the receiver are correct, then each message sent from the sender will be eventually delivered by the receiver) when executing the invocation to set the computed result to the object replicas. Upon the crash of the primary, the new one will have to re-send to the replica at least the last invocation carried out by the crashed primary.
Note that a crash of the primary can be transpar- ently handled by the primary by invoking the compute() method on another that would acts as a new primary on the timeout expiration of the previous invocation.
4.4 Passive/Active Replication
In passive/active replication (Figure 3.b), the primary forwards the invocation to all the -s. Under the assump- tion that -s are deterministic, each computes the same results and it will send it back to the primary. The latter upon receiving the first result (the others are filtered out), starts the “diffuse result” synchronization. Finally returns back the result to the client.
4.5 Active/Passive Replication
In active/passive replication (Figure 4.a) -s are deter- ministic, a client sends the request to all -s, the invoca- tion is totally ordered by the “request ordering” synchro- nization and each relays the request to the primary that, on the receipt of the first invocation, computes the re- sults. Once the result is computed, primary sends back the result to all the -s. When an receives the results it invokes the set() method at each (but the primary) and finally sends the result to the client which receives the first and filters out the others.
Note that under this scheme -s have to agree on the identity of the primary, otherwise the invocation is sent to more than one with the consequent inconsistency of results. This makes harder the many-to-many synchoniza- tion that has to finalize request ordering and agreement on the primary. In the context of asynchronous systems, this leads to (i) multiple synchronization handling the same in- vocation if the -s primary fails in order to agree on a new primary and (ii) the usage of a system of failure detector from -s to -s which actually enhances the coupling be- tween the midtier and the backend. If this coupling wants to be avoided there is the need to add a “decide result” syn-
invocation result invocation result
request ordering
request ordering
compute result
(a) active/passive replication
set decided result
compute result
(a) active/active replication
many-to-many synch many-to-many synch
Figure 4. Examples of replication Schemes in three tiers architectures
chronization typical of the active replication handling non- deterministic replicas.
4.6 Active/Active Replication
The active/active replication (Figure 4.b) differs from the previous one as each forwards the invocation to all the deterministic -ss that replies to each invocation with the computed result. Each as soon as it receives the fist reply, send the result to the client and filters the others. The client passes the first result to the end-user and filters the others.
4.7 Generic Replication Scheme
The generic three tiers replication scheme is shown in Figure 5. A client sends the request to -s, the tier se- rializes the request by using a many-to-many sycnhroniza- tion and (i.e., it associated a unique sequence number to the request) each one of the -s replies forwards the request (with the sequence number) to -s. This is abstracted by the thick line labeled shown in Figure 5. Each one of the replica computes the result and sends it back to the invoking . The tier associates the client invocation to a selected result by using a many-to-many “decide result”
synchronization. Finally, the selected result is imposed to the -s tier. This is done in the following way: -s in- voke the method set() at -s. This is abstracted by the thick line labeled .
It is easy to show that all previous replication schemes are particular instances of the generic one when setting ,
, and and assuming deterministic (or not) replicas. The latter choice allows to avoid a many to many sychronization as in two tiers architectures.
invocation result
decide result
compute result set decided result
request ordering
many-to-many synch many-to-many synch
Figure 5. A general scheme for three tiers replication logic
5 Concluding Remarks
This paper has shown which are the differences in han- dling software replication when moving from two to three tiers architectures. In particular, it has been pointed out that the distinction, used in two tiers architectures, between ac- tive and passive replication misses its relevance in this new context. In three tiers architectures the distinction should be on the deterministic (or not) behaviour of a resource of the backend. As an example, when handling deterministic resources (as in Figures 3.b and 4.b) we can simplify the replication message pattern with respect to the generic one described in Figure 5 by avoiding the presence of a wait-free many-to-many synchronization.
The fact that reasoning about passive (or active) repli- cation in three tiers architectures is not the right point is actually also shown by the active/passive replication pattern depicted in Figure 4.a. From an implementation point of view, the active/passive replication scheme is actally much more harder than the other ones as all the application servers have to agree on the primary of the backend. This implies a tight coupling between midtier and backend. The replica- tion scheme has actually to avoid the case in which two ap- plication servers see two distinct primaries when handling the same invocation. This scenario leads to linearizability violation. Note that this problem does not show up in pas- sive/passive replication (see Figure 3.a) as there is only ob- ject (the application server primary) which invokes the pri- mary of the backend. If the application server primary be- lieves erroneously that the primary of the backend is down (due to timeout expiration of its invocation), it can safely switch randomly on another member of the backend. This also confirm the fact that the only correct distinction to do among replicas in on their deterministic behavior and not on their replication style.
Finally our answer to the question proposed by the title is positive. We have actually shown through the paper how the way of reasoning about replication used in two tiers does not apply (completely) in three tiers architectures. So for example there is a lot of work to be done in finding the best replication pattern style, in finding solutions to the recov- ery problem and in finding light tools to execute wait-free many-to-many synchronizations.
References
[1] Y. Amir, D. Dolev, S. Kramer, and D. Malki, Transis: A Communication Sub-System for High Availability, Proc. of the 22nd Annual International Symposium on Fault-Tolerant Computing, July 1992, pp. 76–84.
[2] K. Birman and R. Van Renesse (eds.), Reliable distributed computing with the isis toolkit, IEEE CS Press, 1994.
[3] K. Birman, A. Schiper, and P. Stephenson, Lightweight Causal and Atomic Group Multicast, ACM Transactions on Computer Systems 9 (1991), no. 3, 272–314.
[4] N. Budhiraja, F.B. Schneider, S. Toueg, and K. Marzullo, The Primary-Backup Approach, Distributed Systems (S. Mullen- der, ed.), Addison Wesley, 1993.
[5] T. Chandra and S. Toueg, Unreliable Failure Detectors for Reliable Distributed Systems, Journal of the ACM (1996), 225–267.
[6] F. Cristian and C. Fetzer, The Timed Asynchronous Dis- tributed System, Proc. of the 28nd Annual International Sym- posium on Fault-Tolerant Computing, 1998.
[7] C. Fetzer and F. Cristian, A Highly Available Local Leader Election Service, IEEE Transactions on Software Engineer- ing 25 (1999), no. 5, 603–618.
[8] R. Guerraoui and S. Frølund, Implementing e-transactions with asynchronous replication, IEEE Transactions on Paral- lel and Distributed Systems 12 (2001), no. 2, 133–146.
[9] R. Guerraoui and A. Shiper, Software-based replication for fault tolerance, IEEE Computer - Special Issue on Fault Tol- erance 30 (1997), 68–74.
[10] M. Herlihy, Wait-free Synchronization, ACM Transactions on Programming Languages and Systems 13 (1991), no. 1, 124–149.
[11] M. Herlihy and J. Wing, Linearizability: a Correcteness Condition for Concurrent Objects, ACM Transactions on Programming Languages and Systems 12 (1990), no. 3, 463–
492.
[12] L. Lamport, Concurrent Reading and Writing, Communica- tions of the ACM 20 (1977), no. 11, 806–811.
[13] C. Malloth, P. Felber, A. Schiper, and U. Wilhelm, Phoenix:
A Tollkit for Building Fault-Tolerant Distributed Application in Large Scale, Tech. report, Department d’Informatique, Ecole Polytechnique Federale de Lausanne, July 1995.
[14] L. E. Moser, P. M. Melliar-Smith, and V. Agrawala, Asyn- chronous Fault-Tolerant Total Ordering Algorithm, SIAM Journal of Computing 22 (1993), no. 4, 727–750.
[15] L.E. Moser, P.M. Melliar-Smith, D.A. Agarwal, R.K. Bud- hia, and C.A. Lingley-Papadopoulos, Totem: A Fault- Tolerant Multicast Group Communication System, Commu- nications of the ACM 39 (1996), no. 4, 54–63.
[16] A. Schiper and A. Sandoz, Uniform Reliable Multicast in a Virtually Synchronous Environent, Proc. of the 13th Interna- tional Conference on Distributed Computing Systems, May 1993, pp. 561–568.
[17] Fred B. Schneider, The state machine approach: a tutorial, Tech. Report TR 86-800, Department of Computer Science, Cornell University, December 1986, Revised June 1987.
[18] R. van Renesse, K. Birman, and S. Maffeis, Horus: A flex- ible Group Communication System, Communications of the ACM 39 (1996), no. 4, 76–83.
