One of the most important criteria in evaluating

Asynchronous Nested Transactions for

Mult-tier Applications

Authors:

Ramzi Karoui, Malik Saheb.

Institut National de Recherche en Informatique Domaine de Voluceau 78150 Le Chesnay, France

Email : Ramzi.Karoui@inria.fr , Malik.Saheb@inria.fr.

Abstract:

This abstract paper aims at covering the problem of distributed multi-tier transactional applications which is addressed neither by any messaging product on the market nor by the ongoing specification in the Object Management Group. The Queueing Transaction model and the Open Nested Transaction model are combined to guarantee the multi-tier transactional Work Unit Atomicity. Our implementation of the Open Nested Transaction models is such that the maximum of capabilities which are necessary to maintain Atomicity are covered by the OMG Transaction Service and transparent to the application.

Introduction
Nowadays, the scale of applications distribution has been increasing. The trend is the use of asynchronous communications. Asynchrony extols Time Independent Processing, which in turn favors the parallelism. One way to support asynchrony between applications is to use messaging systems. Some of them support transactions.

Asynchrony leads to uncertain duration of the tasks execution on the servers. Moreover, it, generally, results in long transaction with two specific problems, First, the long transaction becomes concurrency bottlenecks because updated resources are retained for the duration of the transaction. Second, the work done in the long transaction is vulnerable since the abort of one task for any reason (unavailable resource, or transient network failure) will, automatically, lead to the rollback of the hall work.

The solution adopted by the major messaging products vendors consist in the use of the queueing transaction model (also called offline transaction model [GRAY93]). In this model, the message producer sends its message in one transaction; the messaging mechanism delivers the message in an other transaction only if the first one commits.

IBM MQSeries, BEA Tuxedo/Q are product leaders in the messaging. More recently, OMG has adopted a new specification called CORBA messaging [COR98]. This specification aims at an asynchronous operation invocation, using message passing. The OMG approach is to place the required changes at the Object Request Broker level, which implies a revision and changes to several parts of its architecture, mainly to the GIOP protocol.

The actual products as well as the ongoing CORBA messaging specification do not address the issue of a unit of work involving several servers. Consequently, if a client sends several message requests to different remote servers, each server will execute the message request in a separate transaction. Therefore, each server transaction may have an independent outcome. By doing so, the

atomicity as it may be wished by the client in its initial transaction will be lost.

The goal of this abstract paper is to prove how we can guarantee the Atomicity of a distributed work unit by integrating the queueing transaction model with an other advanced transaction model called Open Nested Transaction.
Related Work

Moss Nested Transactions model [MOS85] is a tree of transactions. The root transaction is the top-level transaction, the other transactions are called subtransactions. A top-level as well as a subtransaction can recursively create a transaction (a child) that is embedded in a existing transaction (a parent). In addition, the model obeys two rules:

First, a subtransaction commit can not take effect unless its parent commits.

Second, a parent rollback causes the rollback of all its children.

The Moss nested model requires that the database be notified of the subtransaction completion in order to surrender its locks to its parent. Consequently, the locks are maintained for the whole duration of the top-level transaction. The subtransaction completion is not a two-phase commit protocol but only a relevant notification to the database.

Open Nested Model

G.Weikum and H.J.Sheik [WEI 92] defined the Open Nested Transactions Model.

Open Nested Transactions (ONT) relax the isolation property by allowing the effects of the committed subtransaction to be visible to concurrent transactions, thus waiving the locks transfer rule of Moss nested transactions.

This feature improves greatly transaction parallelism by releasing the nested transaction locks at the nested transaction commit time. This is not adapted to a transaction whose nested transactions conflict, but there are many applications, specially distributed applications, where the global transaction nested transactions do not conflict (travel agency application…).

The open nested transaction model is different from the Moss nested transaction model in the following aspects:

First, the open nested transaction completion is a two-phase commit.

Second, Once a subtransaction has committed and if either a top-level or an ancestor in the tree rolls back, a compensating operation is assumed to undo the committed subtransaction effects due to its lock release at completion time.

The term "Open Nested Transaction Model" was some time employed to denote an anarchic transaction model [GRAY93], in which every transaction is able to start another transaction having an independent outcome from the one that created it. Thus, the rollback of the originating transaction does not affect the commitment of the created transactions. Clearly, there is no transactional dependency rule between the originating transaction and the created ones.

In this paper, we adopt the Weikum’s Open Nested Transaction definition.

The transaction queueing principles

Taking in account the characteristics of the existing products and the ancomming standards, we propose to define the transaction queueing principles as follows:

A queueing system is interposed between the clients and the servers. Each server and each client owns an input queue in the queueing system.

Within the scope of a first transaction T₁, a client pushes a message (request) to the server queue. The message becomes available, only and only if T₁ commits.

In a second transaction T₂, the server pulls its queue and gets a message or it waits the queueing system to push the message to it.

In the both cases, the server processes the message and enters a reply message in the client-input queue. When T₂commits, the message is removed from the server’s queue.

In a third transaction T_3,the client takes the reply message by it own or it can delegate a Reply-Handler which picks up the message reply and process it. The Reply-Handler can be co-allocated with the client application or it can be in a separate process.

If T2 rolls back, the message is scheduled for a next trial according to a retrying policy. It is possible that after a retry condition is reached the message is moved to an error queue and deleted from the server’s pending messages. The originating client or the Reply-Handler receives a TRANSANCTION_ROLLBACK message reporting the problem.

With regard to each transaction, the queueing system handles the messages as if it were a database and coordinates the queues manager with the transaction outcome commit/rollback. Such a queueing system is called Recoverable Queueing System.

Note that it is also possible that either of the transactions T₁, T₂ or T₃ involve other recoverable resources such as database. Thus, the recoverable queueing system must be under the control of a Transaction Monitor coordinator.

Products and standardization

MQSeries [IBM93] and Tuxedo/Q [TUX95]are the main products offering transaction queueing. They both comply with the queueing Principe presented above.

Recently, the OMG [COR98] defined the CORBA Messaging specification. This specification introduces the router concept. Routers store and forward request and reply messages. They can be seen as queueing systems which may solve interoperability between heterogeneous systems.
Discussion

The actual messaging products and specifications reach their limits when they are confronted with the problem of guarantying the Atomicity of distributed multi-tier transactional applications. To illustrate this problem, let’s take the example of a simple credit/debit application. Assuming that a client application would like to make a call to credit a count and debit another on two different banks, using the messaging paradigm. It is usually recommended to execute this Work Unit in an Atomic manner. However, using the actual products or future CORBA messaging products can lead to the following:

A client starts a transaction, makes two asynchronous calls: credit() and debit() then commits its transaction. The messaging system will start two different transactions, one to debit the count and the other to credit another count. If one of them, definitively rolls back, the messaging system can not undo the committed transaction.

Because the client (or the Reply-Handler) is "rollback aware", it will be informed by the TRANSACTION_ROLLBACK message.

The client (or reply-handler) is obliged to take the appropriate compensation action. But it is not always able to do this, specially, if the multi-tier servers topology is complex. Even if one of them can easily re-establishes the Atomicity by executing the right compensation action, it is intolerable to bother them with such things.

This problem will be solved by the use of a new transaction model named Asynchronous Nested Transaction Model. Section 3 defines and details this model

The problem of Atomicity in the building of multi-tier transactional application comes from the fact that when the client wants to send several requests involving several remote servers in a single Unit of Work, the messaging systems execute each request in a separate transaction. Further, the messaging systems are not able to coordinate globally, the outcome of these separate transactions.

The independent outcome property destroys the Atomicity property. Thus, what is needed is a high-level transaction control that

Preserves the asynchronous communication style,

Respects the queueing transactional principles and

Minimizes the clients concerns about compensation actions.

Asynchronous Nested Transaction Model

We define the Asynchronous Nested Transaction (ANT) as follow:

The ANT model is a tree of transactions. The root transaction is the top-level transaction, the other transactions are Open Nested Transactions.

The top-level transaction contains:

QT1, the request messages producing subtransaction
QT2, the message processing subtransaction, and
QT3, the reply message subtransaction.

The QT1 and QT3 are leaf subtransactions, whereas QT2 is the Asynchronous Nested Transaction.

The three subtransactions QT1, QT2 and QT3 obey the precedence rule:QT1 > QT2 and

QT2 > QT3.
Messages exchanged during the ANT active phase are hold in a Recoverable Queueing System.
The subtransactions completion are a two-phase commit.
Once a subtransaction has committed and if either a top-level or an ancestor in the tree rolls back, a compensating operation is assumed to undo, if necessary, the committed subtransaction effects, due to its lock release at completion time.

Figure 1: The ANT topological overview

Figure1 generalized the definition given above. The Top-Level transaction can contain:

One QT1 subtransaction producing N request messages.

N message processing subtransactions noted QT2¹_i,iÎ [1,N]. (which should be read QT2 number "i" at the level "1")

N message reply subtransactions noted QT3¹_i iÎ [1,N].

Each QT2¹_i,can be structured in its turn as the top-level transaction and contains one QT1²(in the level 2) , several QT2² and several QT3².

The ANT model relies on two main ideas:

It assumes the existence of a recoverable queueing system that assures the creation of the asynchrony between two consecutive levels.

The ANT commit and rollback rules are the same as in the ONT model. This implies that the ANT commit is a two-phase commit. This is very important for the overall working of the model. In fact, QT2 starts only if QT1 commits and QT3 starts only if QT2 commits. The rollback of an ANT reverberates on the down-tree. The immediate consequence is that if the top-level transaction rolls back all the subtransactions are rolled back.

As in the ONT model, the rollback of a committed subtransaction is performed by a compensation transaction which semantically reverses the effects of the whole ANT sub-tree. Ideally, the compensating transaction creates a new top-level transaction and calls the inverse operations of those executed by the ONT.

The section 4.3 discusses the technological challenge of mounting asynchronously the subtransactions in the transaction tree and explains its completion in more details.

CORBA implementation of the Asynchronous Nested Transactions

This section aim to prove the feasibility of the ANT model. The standard CORBA architecture was selected to build the ANT framework because, currently our prototypes run on this platform.
1. Object Transaction Service Basics
  
  The Object Transaction Service (OTS) [OTS97] is one of the Common Object Services defined by OMG. It supports the flat and the Moss nested transaction models.
  
  The CORBA Transaction Service Figure2 is the transactional service provider. The client (Transaction Originator) begins a top-level transaction which has for effect the creation of a Coordinator Object. The Subtransactions can be started by the client or by the servers. The Coordinator object relies on the SubCoordinator objects to control subtransactions completion.
  
  A Transaction Server is a collection of objects whose behavior is affected by the transaction but which have no recoverable states of their own.
  
  A Recoverable Server implements application objects whose data are affected within the scope of the transaction. Data are represented by the Resource objects. Normally, a recoverable server consists of, at least, one Resource object. Resource interface (RO) supports two-phase commit protocol to complete a transaction on its data resource. The SubTransactionAwareResource interface is a specialisation of the Resource interface that supports subtransaction.
  
  Figure 2: OTS Architecture Overview
  
  When a client invokes an operation on the application object interface (I, cf fig2), it propagates with the call the coordinator object reference.
  
  This reference can be used by the Transaction Server to start a subtransaction, or it is used by the Recoverable Server to register recoverable objects with the coordinator.
  
  If the reference is used to create a subtransaction, the subcoordinator is put under the control of the coordinator.
  An Open Nested Transaction (ONT) is created in the same manner as in the OTS subtransaction option. Its type (open) is only fixed at its end. To distinguish between the end of an open subtransaction and of Moss subtransaction, a new operation, called definite_commit is defined as follow:
  
  void definite_commit(in boolean report_heuristic,in Compensator c, in Any data);
  
  By calling the definite_commit operation, the subtransaction is terminated with open semantics, i.e the two-phase commit is started in the sub-tree of the nested transaction to release all its locks and resources. Since the locks acquired during the execution of the ONT are released at commit, the abort-dependency induced by the ancestor transaction on its open nested transactions cannot be undone by the traditional rollback (restoring the initial state of the data from some logs). A compensating transaction that semantically reverses the effects of the whole ONT sub-tree is needed.
  
  The compensating transaction is encapsulated in the Compensator object, which is passed as a parameter in the definit_commit operation. The define_commit( ) takes also an other input parameter "data", wrapped in the CORBA::Any format. This parameter is application dependent.
  
  The compensator object is automatically called by ONT-OTS-aware if the ONT’s parent rolls back. The Compensator interface is defined as follow:
  
  interface Compensator{
  
  void compensate(in Any data);};
  
  The compensate operation is called by a subcoordinator to ask the compensation of a committed open subtransaction. It is usually provided by the server programmer. The behaviour of this operation is application dependent. ONT-OTS-aware does not impose any constraints on how the compensation should be carried out.
2. Recoverable Queueing System Architecture

Our approach to design a recoverable queueing system consists in considering it as a CORBA service that is plugged over the actual CORBA2.2 Object Request Broker. By the use of the Dynamic Skeleton Interface (DSI), the recoverable queueing system receives the method invocations, then stores them in a persistent storage and finally forwards them on using the Dynamic Invocation Interface (DII).

The recoverable queueing system (cf. figure 3) contains four computing objects:

A Scheduler, Access points, Connectors and a Queue Manager.

Figure 3: Recoverable queueing system Architecture

The scheduler object is a programmable object that works according to scheduling policies. A scheduling policy defines the condition or the timing under which, the recoverable queueing system forwards a request message to the server or a reply message to the Reply-Handler.

The Access point objects allow clients to send request messages as in the CORBA programming model. They receive invocations for any server’s interface described in the Interface Definition Language (IDL), hence, they hide the queueing to the clients. Access points rely on DSI.

The method invocations and their parameters are stringified, and marshaled in messages in these objects. From a transactional point of view, they assume the role of a Transaction Server.

The Connector objects allow the recoverable queueing system to forward request messages to the servers by invoking their interfaces. Similarly, they forward the reply messages to the Reply-Handlers. In both cases connectors use DII.

Connectors are under the scheduler control, which commands them to either start the QT2 subtransactions when they forward request messages or QT3 subtransactions when they forward reply messages. From this point of view, Connectors are Transaction Originators.

The Queue Manager object organizes messages in queues on a persistent storage in order to secure them. It assumes the Recoverable Server role and offers to the OTS the Resource Object Interface. The Queue Manager supports the two-phase commit protocol, which allows it to participate either in a flat transaction or in an open nested transaction.

Structuring the Asynchronous Nested Transaction Model
1. Application level
  We take back the typical credit/debit application introduced in section 2.5 to illustrate the use of the Asynchronous Nested Transaction model. In this example, we suppose bank1 and bank2: two servers offering respectively two application objects O1 and O2, and two compensator objects C1 and C2. The object O1 possesses the credit1 operation and the object O2 possesses the debit2 operation. The compensator objects C1 and C2 implement, respectively, two compensation operations: debit1 and credit2.
  
  A client starts a top-level transaction in which it creates the QT1 subtransaction. QT1 involves the credit1(100$) and the debit2(100$) operations.
2. Transaction Tree expansion and control
  During the QT1 active phase, the coordinator reference is passed to the recoverable queueing system through the Access point object. When it commits, the recoverable queueing system’s scheduler order the connectors objects to start two ANTs: QT2₁and QT2₂.
  
  QT2₁ involves the bank1 server and QT2₂ involves the bank₂ server.
  
  To be part of the client’s top-level transaction the connector objects use the coordinator reference to create QT2₁andQT2₂. This remark is key to tie-up the top-level transaction with the subtransactions.
  
  When the servers’ connectors commit QT2₁and QT2_{2 ,}they use the define_commit() operation with two conpensator objects C₁ and C₂ and the money amount they received from the client. Thus, the ONT-OTS-aware owns the appropriate object references and data to compensate all the QT2₁and QT2₂ effects.
  
  The Reply-Handler’s Connector behaves like the servers’ Connector when it has to return a reply message. It starts the QT3₁ and QT3₂subtransactionto return the two reply messages of the credit1 and debit2 operations. QT3₁ and QT3₂ are created by using the top-level coordinator object , thus they become part of the top-level transaction.
  
  During the top-level’s sphere of control expansion, a Control Tree made by a top-level coordinator and subcoordinator objects, is build progressively. Its topology is exactly the same as the ANT transaction tree described in figure1.
  
  Note that the coordinator and the subcoordinators are persistent objects with a lifetime equal to the top-level transaction one. This property guarantees that the rollback will be performed even in the crash scenarios
3. Application control and concerns
  We suppose an unrecoverable failure occurs on bank₁, obliging the QT2₁ to definitively rollback. On the other hand, if QT2₂ commits normally. The Reply-Handler receives in the QT3₁ subtransaction the QT2₁’s reply which, is TRANSCTION_ROLLBACK. In this case, all that the Reply-Handler has to do is to roll back the top-level transaction. The ONT-OTS-aware will automatically, compensate the QT2₂ effects by calling the compensate(100$) operation belonging to C2 object. The compensate() operation executes internally the credit2(100$) operation.
4. The Asynchronous Nested Transaction Consistency

In order to prove the consistency of the ANT model we propose to analyze the failure cases in a simple topology containing a top-level transaction with QT1, QT2 and QT3 subtransactions.

Five potential failure points are examined. They are noted A, B, C, D, E in figure 4.

Figure 4: failure cases analyze

(A):If the top-level transaction rollback occurs during the QT1 active phase then QT1 is forced to abort. Thus, no request messages will be sent.
(B): If the top-level transaction rollback take place after the QT1 commit and before the QT2 start, according to the transaction queueing principles, the message will not be immediately removed from the server’s queue.

However, when the server’s connector object tries to create the QT2 subtransaction, it will not be able to do it because the coordinator object reference becomes invalid, since the top-level transaction rolls back. At that moment the server’s connector discard the request message from the server’s queue. This can be viewed as the QT1 compensation, which is performed by the recoverable queueing system it self.

(C ): If the rollback of the top-level occurs during the QT2 active phase, QT2 is forced to abort.

As in the (B) case, the request message is kept in the server’s queue and the server connector’s trial to create QT2 will be unsuccessful, at that time it discards request message.

(D): If the rollback of the top-level occurs after the commit of QT2 and before the starting of QT3, QT2 will be compensated by executing the compensator operation.

Later, the Reply-Handler’s connector will not be able to start QT3 because the coordinator object reference is invalid. Consequently, it discards the reply message.

(E): If the rollback occurs during the QT3 active phase, the QT3 is forced to abort, and the reply message is discarded exactly as in the (D) case.

To summarize, when the top-level rolls back

All the active subtransactions are forced to roll back,

All the committed subtransactions are compensated,
All the coming subtransactions that would like to tie-up therolled back top-level transaction are prohibited to start.

Since the top-level transaction is a high-level transaction of control, it commits well not impact the servers recoverable resources, but simply release the Control Tree.

The result is that the Atomicity and the exactly-once execution semantic are achieved.

The final result is that the announced requirements made in section 2.5 (The preservation of the asynchronous communication style, the respect of the transaction queueing principles and the minimization of the client concerns about compensation actions) are fulfilled.

Conclusion
The Atomicity of a Work Unit in a distributed environment remains crucial for multi-tier applications and do not have to be abandoned even if the communication paradigm is asynchrone .

In this abstract paper, we illustrate the limits of the actual messaging products and specifications when they are confronted with the problem of guarantying the Atomicity of distributed multi-tier transactional applications.

A new transaction model named Asynchronous Nested Transaction (ANT) was defined to overcome the problem of Atomicity in an Asynchronous environment. The ANT model is an integration of the Open Nested Transaction model and the queueing transaction principles.

We have also proved the feasibility of the ANT model, by building a framework integrating MaaoOts [LIAN98] our ONT-OTS-aware prototype and ATCS (Asynchronous Transactions Coupling System) our recoverable queueing system.

As a future work we think that the Asynchronous Nested Transaction model seems to be appropriate to the work flow management in which a set of autonomous nodes cooperate to execute a common task. Each node function independently, which means that the asynchrony is desirable. Further, the need to control the overall work flow process proves that there is a need of Atomicity.

Due to the lack of time we have not explored this topic yet.
Bibliography

[BEAU98] Beaudree Frédéric, Cyrille Devaux, Bruno Traverson. PENTE: un prototype d’Echange Neutre eT Extensible. NOTER 98.

[BER97] Bernstein Philip. Principals of Transaction Processing, For the systems Professional. 1997.

[COR98] CORBA Messaging Specification. OMG TC Documentation orbos/98-05-05.

[CSC99] C.Schmidt Douglas, Steve Vinoski. Programming Asynchronous Method Invocation with CORBA Messaging. SIGS C++ Report magazine, Feb 1999.

[ELM92] Elmagarmid A.K.. Database Transaction Models for Advanced Applications. Morgan Kaufmann Publishers, 1992.

[GRAY93] GRAY.J REUTER.A. transaction Processing: Concepts and Techniques. p. cm, The Morgan Kaufmann series in data management systems. 1993.

[IBM93] IBM MQSeries: Message Queue Interface, Technical References. IBM corporation 1993.

[LIAN98] LIANG Jian, Saheb Malik, MaaoOTS White Paper. 1998. http://www.actrans.org/Publications.html

[LIS88] Liskov Barbara. Distributed Programming in ARGUS, Communication of the ACM. March 1988.

[LIS95] Liskov Barbara, Mark Day, Maurice Herlihy, Paul Johnson, Gary Leavens, Robert Scheifler, William Weihl Argus Reference Manual,. Cambridge, Massachusetts Laboratry for Compuer Science. April 1995.

[MOH94] Mohan.C, Dievendroff.D, Recent Work on Distributed Commit Protocols and Recoverable Messaging and Queueing. Data Engineering, Vol 17. 1994.

[MOS85] Moss.E. "Nested Transactions". MIT Press, 1985.

[OTS97] CORBA services : Common Object Services Specification. Object Transaction Service: V1.1, November 1997.

[TUX95] Tuxedo/Q Guide, Release 5.0 1995

[WEI92] G.Weikum, H.J.Schek. "Concepts and Applications of Multilevel Transactions and Open Nested Transactions"; in [ELM92].