Asynchronous Nested Transactions for
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.
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.
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.
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:
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.
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:
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.
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.
In the both cases, the server processes the message and enters a reply message in the client-input queue. When T2 commits, the message is removed from the serverís queue.
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 T1, T2 or T3 involve other recoverable resources such as database. Thus, the recoverable queueing system must be under the control of a Transaction Monitor coordinator.
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.
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
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 QT1 and QT3 are leaf subtransactions, whereas QT2 is the Asynchronous Nested Transaction.
QT2 > QT3.
Figure 1: The ANT topological overview
Figure1 generalized the definition given above. The Top-Level transaction can contain:
EachQT21i, can be structured in its turn as the top-level transaction and contains one QT12 (in the level 2) , several QT22 and several QT32.
The ANT model relies on two main ideas:
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.
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.
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, calleddefinite_commit is defined as follow:
void definite_commit(in boolean report_heuristic,in Compensator c, in Any data);
By calling thedefinite_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 thedefinit_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:
void compensate(in Any data);};
Thecompensate 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.
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 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.
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.
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 thecredit1 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 thecredit1(100$) and the debit2(100$) operations.
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: QT21 and QT22.
QT21 involves the bank1 server and QT22 involves the bank2 server.
To be part of the clientís top-level transaction the connector objects use the coordinator reference to create QT21 and QT22. This remark is key to tie-up the top-level transaction with the subtransactions.
When the serversí connectors commit QT21 and QT22 , they use thedefine_commit() operation with two conpensator objects C1 and C2 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 QT21 and QT22 effects.
The Reply-Handlerís Connector behaves like the serversí Connector when it has to return a reply message. It starts the QT31 and QT32 subtransaction to return the two reply messages of thecredit1 and debit2 operations. QT31 and QT32 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
We suppose an unrecoverable failure occurs on bank1, obliging the QT21 to definitively rollback. On the other hand, if QT22 commits normally. The Reply-Handler receives in the QT31 subtransaction the QT21í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 QT22 effects by calling thecompensate(100$) operation belonging to C2 object. The compensate() operation executes internally the credit2(100$) operation.
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
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.
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.
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.
To summarize, when the top-level rolls back
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.
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.
[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].