Transactions in Pipeline Server

Transaction Design and Management Options

                                                  Igor Pavlin
                                                 May 2nd, 2006

This paper proposes handling of transactions in web-based applications with a particular relevance to the new pipeline server. Since we are not using J2EE application servers we are pretty much forced to handle transaction management in the pipeline server (an application) and are forced to deal with database integrity in the pipeline server itself. I propose the use of Timestamp-based Protocol found elsewhere in the literature. A short outline of the protocol is given, and links to more detailed explanations are given at the end of the paper.

A transaction is an indivisible unit of work that changes application state - whether on disk, in memory or in a database - that, once started, is completed entirely, or not at all.

Transactions can be demarcated - started, and ended with a commit or rollback - by an EJB container (like JBoss, Glassfish, etc), by an enterprise bean, or by a client. An application using Tomcat server, which is a Servlet and JSP server and is not an EJB container, can be also designed to use transactions, but they need to be controlled by JDBC or JTA transactions on the client side.

Statement of the problem

Pipeline server needs to submit several tasks at the same time (for concurrent processing). The tasks can have its own set of subtasks and processes attached to them. Each task is associated with several database tables that it reads and writes to in order to complete. The reads and writes to database are performed using SQL transactions through JDBC connections.

There are two different types of transactions to be considered:

  • One that can be done usually within a single method, but involves several accesses to database that all have to succeed or fail collectively. We will call these single, or single-thread transactions.
  • The other that involves several methods, usually running in separate threads, accessing the same or different database tables or even several databases. We will call these concurrent, or multiple-thread transactions.

The pipeline server will be dealing with both types of transactions and we will address issues in both cases.

  • Requirement 1. Pipeline server needs to manage task and subtask creation as a single transaction. This is an application level transaction.
  • Requirement 2. We require that the JDBC connection does not perform the autocommit for each of the connection's statement execution, because we assume that one task transaction will require several database updates as a logical group (see Requirement 1). This implies that the client is taking over the proccess of transaction management.
  • Requirement 3. A protocol needs to be designed that will prevent deadlocks in the case of multi-thread transactions.

The pipeline server scheduler will initiate several threads of execution for these tasks at any given time. Each of the tasks is accessing database and modifying database tables at the application level and the task submission can fail at any level before a final commit to database table is called. In this case the pipeline server needs to perform the rollback on the threads' initiated set of changes and leave the database in consistent state.

One of the basic questions is what happens if one thread initiates updates, and than performs the rollback at the application level, while the other thread performs a successful commit at the application level. Is there a potential for a deadlock and in what state is the database left?

  • Requirement 4. The thread to succeed first in the application level commit will promote a new state of the database and the thread that failed needs to perform the rollback at the application level, and can not change the state of the database until it completes a new sucessful transaction.
  • Requirement 5. All the methods dealing with database statements of the thread need to either all succeed or they all fail collectively.

Container-Managed Transactions

Demarcating transactions at the EJB container level is the most efficient. However, that implies that Pipeline Server needs to use an application server, which is a major architectural decision, we do not seem to support at this moment. If we plan to use the Tomcat web application server, than we need to use JDBC and JTA transactions, i.e., use client managed transaction handling.

For the completness, I briefly state what would be involved if we were to use an EJB Container (i.e., an J2EE application server).

Transactions are costly application resources, especially database transactions, because they reserve a network connection for the duration of the transaction. In a multi-tiered architecture with database, application server, and web layers you optimize performance by reducing the network traffic "round trip." The best approach is to start and stop transactions at the application server level, i.e., in the EJB container.

Container-Managed Transactions (CMT)s are simpler to develop and perform well. Container-managed transactions are supported by all bean types: session, entity, and message-driven. They provide good performance, and simplify development because the enterprise bean code does not include statements that begin and end the transaction. In the case of system failure all the transactions are rolled back by the container, and do not have to be handled by beans or client.

However, each method in a CMT bean can only be associated with a single database transaction (which can include several SQL queries or updates). In a container-managed transaction, the EJB container manages the transaction, including start, stop, commit, and rollback. Usually, the container starts a transaction just before a bean method starts, and commits it just before the method exits. However, a finer control, like calling another transaction within a transaction (nested transaction) can not be achieved by CMT.

If a system exception is thrown during a transaction, the container will automatically roll back the transaction. For user defined exceptions, however, you need to explicitly program rollbacks in your bean.

Bean-Level Transaction Management

In a bean-managed transaction, the EJB bean manages the transaction, including start, stop, commit, and rollback. Bean-managed transactions are supported by all session and message-driven beans; you cannot use bean-managed transactions with entity beans (which use CMT).

When to Use Bean-Managed Transactions

These are examples of requirements that may dictate the use of bean-managed transactions:

  • You need to define multiple database transactions with a single method call. With container - managed transactions, a method can only be associated with a single transaction. You can use a bean-managed transaction to define multiple transactions with a single method. However, it is worth avoiding the need for a bean-managed transaction by breaking the method in to multiple methods, each with its own container-managed transaction.
  • We need to define a single transaction that spans multiple EJB method calls. For example, a stateful session EJB that uses one method to begin a transaction, and another method to commit or roll back a transaction. It is best to avoid this practice, because it requires detailed information about the workings of the EJB object. However, if this scenario is required, we must use bean-managed transaction coordination, and we must coordinate client calls to the respective methods.

Client-Level Transaction Management

Client applications are subject to interruptions or unexpected terminations. If you start and stop a transaction at the client level, you risk:

  • Consumption of network resources during waits for user actions, interruptions, until resumption of client activity or timeout.
  • Consumption of processing resources and network resources to rollback the transaction after timeout or termination of the transaction.

In conclusion: it is better not to manage transactions in client applications unless there are overriding reasons to do so. However, if we use Tomcat server, we need to do client managed transactions for both single-thread and multiple-thread transactions.

Client single-thread transactions

If the requirements above need to be implemented, the proposed design is to use the 'Transaction' design pattern.

The purpose of the transaction pattern is to group a collection of methods so that they either all succeed or they all fail collectively.

One recalls a famous example of transferring funds from one bank account to another. They either need both to succeed or both need to fail in order that the total sum of moneys in both accounts does not change after the transaction. Thus we expect several methods to be fully synchronized and a recovery option should be available.

The main players in the pattern are: 

  // 
  //The interface that defines all the methods to control every participant 
  //
 interface TransactionParticipant {
    boolean join(long transactionID);
    void commit(long transactionID);
    void cancel(long transactionID);
 }

 // 
 // interface that defines the business methods. Methods can throw Exceptions
 // as a signal of failure.
 //
  
  interface SpecificParticipant extends TransactionParticipant {
     boolean operation1(long transactionID);
     boolean operation2(long transactionID);
     ...
  }
 //
 // implements all the interface methods and defines what happens if the
 // transaction manager decides to cancel() or commit(). It has to keep a
 // reference to the original state, to be able to restore when the cancel
 // is invoked (Memento pattern is recommended).
 //
  public class ConcreteParticipant implements SpecificParticipant {
    void cancel();
    void commit();
    ...
 }
 //
 // Call the join method on the participants and ultimately calls either cancel or commit on the participants.
 //
 public class TransactionManager {
   ...
 }

We use the transaction as follows:

  • Create a transactionID (either as a long or as an object)
  • Invoke join on all participants and abort transaction if the joining fails for any of the participants.
  • Try the action, invoke the business methods and call cancel as soon as any participant fails.
  • If the action is completed, call commit on all participants.

Concurrent (multi-threaded) transactions

Multiple transactions are allowed to run concurrently in the system. Advantages are:

  • increased processor and disk utilization, leading to better transaction throughput: one transaction can be using the CPU while another is reading from or writing to the disk. Or we can utilize multi-processor machines better.
  • average response time for transactions is shorter: short transactions need not wait behind long ones.

ACID properites of transaction

ACID stands for four properties transactions must satisfy to insure database consistency.

  • Atomicity. Either all operations of the transaction are properly reflected in the database or none are.
  • Consistency. Execution of a transaction in isolation preserves the consistency of the database.
  • Isolation. Although multiple transactions may execute concurrently, each transaction must be unaware of other concurrently executing transactions. Intermediate transaction results must be hidden from other concurrently executed transactions. That is, for every pair of transactions Ti and Tj, it appears to Ti that either Tj, finished execution before Ti started, or Tj started execution after Ti finished.
  • Durability. After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.

For concurrent transactions we try to resolve a problem of isolation, where there are at least two transactions T0 and T1 (possibly in different threads), accessing with R(ead) and W(rite) methods two data objects A and B. It is the isolation property from all the above ACID properties that is most difficult to achieve.

For better understanding of the following text a more detailed explanations aree given in references bellow. They contain examples of some of the points presented here.

Transaction States

It is useful to have a state diagram of transaction. Here it is:

Definition of transaction states:

  • Active, the initial state; the transaction stays in this state while it is executing.
  • Partially committed, after the final statement has been executed.
  • Failed, after the discovery that normal execution can no longer proceed.
  • Aborted, after the transaction has been rolled back and the database restored to its state prior to the start of the transaction. Two options after it has been aborted:
    • restart the transaction - only if no internal logical error
    • kill the transaction
  • Committed, after successful completion.

Definition of Schedule

Schedules are sequences that indicate the chronological order in which operations of concurrent transactions are executed. A schedule for a set of transactions must consist of all operations of those transactions and must preserve the order in which the operations appear in each individual transaction. The purpose of the schedule is to arrange the transaction operations in such a way to eliminate deadlocks and insure isolation. A schedule is labeled with S(.., Oi, Oj, ...) where Oi and Oj are transaction operations, which assumes that Oi will happen before Oj.

Schedules must be serializable, and recoverable, for the sake of database consistency, and preferably cascadeless (meaning that one rollback does not trigger a sequence of rollbacks). A policy in which only one transaction can execute at a time generates serial schedules, but provides a poor degree of concurrency. Concurrency-control schemes tradeoff between the amount of concurrency they allow and the amount of overhead that they incur. The bellow outlined timestamp-based concurrency control is quite an optimal solution.

Serial schedule of transactions

This is the case were atomically executed transactions are ordered serially, first one transaction does all the work on A and B, and than the other does all the work. For N transactions, they can be ordered in N! ways. So, a serial schedule would be:

    T0 does sequence R(A),W(A),R(B),W(B)
    and than 
    T1 does sequence R(A),W(A),R(B),W(B)

The problem with this approach is that if T0 fails or takes enormous amount of time to complete, we get a bottleneck.

An example of the schedule that leaves the database in an inconsistent state would be (i.e., this is not a serial schedule)

        T0      T1
        R(A)
                R(A)
                W(A)
                R(B)
        W(A)
        R(B)
        W(B)
                W(B)

where time flows from top to bottom. Although the sequence of operations from each individual transaction is the same as in previous case, one can see by example from reference 2 that the results will leave database in an inconsistent state, even if all goes well with R and W. Bellow we show that this schedule would not have be an equivalent serial schedule.

If we can make a schedule equivalent to a serial schedule, than we have also preserved database consistency.

Non-Serial schedule of transactions

Often we have situations where Ti and Tj can overlap in execution time. There is a potential of deadlock if the operations within transactions are not ordered in the same manner as in original transactions. We use notation Ti(...,Oi, Oj, ...) where Oi < Oj timewise to define a sequence of operations within a transaction.

Notion of Conflict

We define here a notion of conflict. Instructions Oi and Oj of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both Oi and Oj, and at least one of these instructions writes Q. The resolution of conflicts is the essence of the problem solution. Bellow we define one of these algorithms called the Timestamp-based protocol. Intuitively, if there is no conflict, we can exchange the order of Oi and Oj, arriving at different schedule which will not lead to the deadlock or leave the state of database inconsistent.

If a schedule S can be transformed into a schedule S' by a series of swaps of non-conflicting operations, we say that S and S' are conflict equivalent.

We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

Example of a schedule that is not conflict serializable:

    T0	              T1	
    read(Q)			
                     write(Q)	
    write(Q)

We are unable to swap instructions in the above schedule to obtain either the serial schedule < T0, T1 >, or the serial schedule < T1, T0 >.

One example of sequence that is conflict serializable:

    T0              T1
    read(A)
    write(A)
                    read(A)
                    write(A)
    read(B)
    write(B)
                    read(B)
                    write(B)

where time flows from top to bottom. < T0,T1 > is an equivalent serial sequence, while we can not reduce the above sequence by swaping non-conflicting operations to < T1, T0 >

Locking protocol

This is type of transaction handling that requires a transaction T to obtain a lock on an object Q before it can proceed with operations on the Q. If the lock is not available the request might have to wait. The locking protocol is simpler to implement than timestamp-based protocol and relies on the assumption that collisions on an object between competing transactions will be relatively rare. However, the price to pay is a need to have a support for deadlock detection and removal. The protocol is similar to readers/writer algorithm.

Locks can be:

  • Shared - Ti has shared-mode lock (S) on item Q, Ti can read Q but not write Q
  • Exclusive - Ti has exclusive-mode lock (X) on Q, Ti can read and write Q

Berkeley DB Java edition

Berkeley DB Java edition is an embedeed database that provides a framework for transactional processing which uses a locking protocol. In essence it requires only one jar file to be added to an application that uses transactional processing.

See the references bellow for a in depth explanation of how this database works. This is the environment in which the attached example source code is working. The source code represents a transactional application and the principles and APIs that are required to have deadlock free and secure transations on a database. The next step in our design is really to find out how to either use the embeded database (BerkeleyDB Java Edition features in memory processing that is persisted on disk files) together with Oracle database, or how to add essentially the same support as this database does for transactional processing. BerkeleyDB Java edition uses JTA, JMX and JCA to support transactional processing and can be added to an application server and I believe to Tomcat server as well.

BerkeleyDB JE offers the following major features:

  • Large database support. JE databases efficiently scale from one to millions of records.
  • Multiple thread and process support. JE is designed for multiple threads of control. Both read and write operations can be performed by multiple threads. JE uses record-level locking for high concurrency in threaded applications. Further, JE uses timeouts for deadlock detection to help ensure that two threads of control do not deadlock indefinitely. JE allows multiple processes to access the same databases. However, in this configuration JE requires that there be no more than one process allowed to write to the database. Read-only processes are guaranteed a consistent, although potentially out of date, view of the stored data as of the time that the environment is opened.
  • Database records. All database records are organized as simple key/data pairs. Both keys and data can be anything from primitive Java types to the most complex of Java objects (This becomes a problem for complicated objects, as special read/write methods need to be implemented to write to the JE database).
  • Transactions. Transactions allow you to treat one or more operations on one or more databases as a single unit of work. JE transactions offer the application developer recoverability, atomicity, and isolation for database operations. Transactions are described in detail in the JE Transaction Processing guide (see reference bellow).
  • Backup and restore. JE's backup procedure consists of simply copying JE's log files to a safe location for storage. To recover from a catastrophic failure, you copy your archived log files back to your production location on disk and reopen the JE environment. Note that JE always performs normal recovery when it opens a database environment. Normal recovery brings the database to a consistent state based on change information found in the database log files.
  • JTA. JE has implemented Java Transaction Api for transaction management.
  • JCA. JE provides support for the Java Connector Architecture. This helps you integrate your transactional application into an exsiting application server.
  • JMX. JE provides support for Java Management Extensions. A JavaBean can be used to monitor configuration and operation of BerkeleyDB JE database.

Transactional processing with the BerkeleyDB JE

The reference bellow provides a thorough introduction and discussion on transactions as used with Berkeley DB, Java Edition (JE). It begins by offering a general overview to transactions, the guarantees they provide, and the general application infrastructure required to obtain full transactional protection for data.

It also also provides detailed explanation on how to write a transactional application. Both single threaded and multi-threaded are discussed.

The source code included in the attachment shows how to write an transactional application. The source code has extensive comments, and can be used as a self contained explanation of how to handle transactions. An example is given where five threads reading and writing each 500 records in chunks of 10 writes to database (representing one transaction) compete for the resources. The database is allowed to grow, and one can see how the number of deadlocks is increasing as the database gets larger because of a concurrent read in the transaction. The BerkeleyDB JE environment provides for deadlock resolution and transaction isolation.

Timestamp-based protocol

In order to make a serializable schedule and to avoid deadlocks and provide a finer granularity which enables interleaving of operations from multiple transactions (threads), we define Timestamp-based protocol.

In this protocol, each transaction is first ordered in advance by a timestamp (like a system timestamp, or just an integer based counter that is updated when a new transaction appears in the system). Thus, if TS means timestamp

        TS(Ti) < TS(Tj) if Ti entered the system before Tj

implies that Ti is older (has smaller timestamp). The timestamp-based protocol bellow assures that, although the Ti and Tj overlap in time, there operations can be performed in such a manner that we can avoid deadlock. Here is how the protocol works.

Each data item Q (like A or B), gets two timestamps, a W-timestamp and an R-timestamp. W-timestamp denotes the largest write timestamp (the timestamp of the transaction that last executed a successful write on Q). R-timestamp is the largest timestamp of the last successful read on Q. Timestamps are updated whenever a write or read is executed on Q.

The protocol assures that any conflicting read or write (read/write of shared data that can happen simultaneously) is executed in timestamp order.


* Suppose Ti executes Read on Q.

if TS(Ti) < W-timestamp(Q) 
  then Ti is trying to read a value on Q which is already overwritten, 
  =&gt; reject read operation and rollback Ti. Ti gets new timestamp.
  
if TS(Ti) >= W-timestamp(Q)
  then Ti is trying to read a value already written before 
  => allow read to proceed 
  => R-timestamp(Q)=max(R-timestamp(Q), TS(Ti))


* Suppose Ti executes a Write on Q.

if TS(Ti) < R-timestamp(Q)
  then the value of Q that Ti is producing was needed previously, and system assumed that value would never be produced.
  => the write operation is rejected, and Ti is rolled back.
  
if TS(Ti) < W-timestamp(Q)
   some other transaction already changed the value of Q (the Ti tries to write an  obsolete value of Q).
   => the write operation is rejected, and Ti is rolled back.
   
otherwise, the write is commited.


Whenever a rollback is called, a transaction is timestamped anew and ordered to restart.

References

  • No labels