Transaction Processing Cheat Sheet

Introduction

Transaction processing (or OLTP for online transaction processing) is a class of information system in which the goal is to handle requests for updates to shared data from multiple clients. A crucial requirement is that the processing be completed while the client waits and an immediate response given. The automated teller machine (ATM) network is a typical example.

Transaction processing applications typically have some or all of these requirements:

• data is shared among multiple clients
• requests are processed while a user is waiting
• multiple requests may be in progress at once
• scalability to large volumes of requests
• high reliability (few errors)
• high availability (minimal down-time)

So, what exactly is a transaction? A transaction is a series of operations on shared data taken together as a logical unit of work. It must succeed or fail as a unit and must proceed independently from other transactions that may be running at the same time. In other words, a transaction is a short program that accesses shared data and that must be executed in a way that obeys the ACID properties.

The standard example of a transaction is a transfer of funds from one account to another. The transaction has two parts. Crediting one account and debiting another. Clearly, it would be bad if one of these parts were to happen without the other.

Transaction processing is a key piece of computing infrastructure that enables applications in e-commerce, airline reservations, banking, and securities trading. When buzzwords like "enterprise" and "middleware" are thrown about, the meaning often boils down to transactional capabilities.

This cheat sheet is an attempt to quickly define the basic concepts needed to understand transactional technologies and apply them to software development and systems architecture.

History and Context

Transaction processing developed as business applications outgrew the limitations of batch mode data processing. In a batch mode system, requests are stored to be executed later, probably at some wee hour of the morning. The accumulated tasks are executed sequentially, so interference between transactions was not an issue. While simple, batch processing is clearly unsuitable for applications that require immediate response and continuously up-to-date data.

Early transaction processing software products include CICS and IMS both from IBM. Tuxedo originated at AT&T and was later acquired by BEA. Not coincidentally, both IBM and BEA are now vendors of application servers. Modern application servers evolved out of components called transaction processing monitors, as additional functionality was merged in over time (web server, persistence, security, etc.). The architecture of Enterprise Java Beans is a little less baffling when viewed as a descendant of transaction processing software like CICS, especially given IBM's heavy involvement in the creation of the J2EE specification.

Among data-centric applications, transaction processing is distinguished by an emphasis on rapid update over searching or summarizing. This is in contrast to decision support, data mining, or OLAP (online analytical processing) applications in which the goal is to allow complex queries against a relatively static database.

In a large part, transactions are a means of concurrency control. Transaction processing is not the only perspective on concurrency. Other branches of computer science, notably operating systems and parallel programming, have also encountered and addressed concurrency. These efforts, at times, proceeded in isolation but are now better integrated. The formal theory developed in the context of transaction processing has made important contributions to the study of concurrency and remains an active area of research in computer science.

Although transaction processing was conceived in the context of databases, the theory and principles are widely applicable to other situations involving concurrency. Examples include message queuing, caching, file systems, source code control, and document management.

Architecture

The chunk of software that implements transactional capabilities is called either a "transaction processing monitor" or a "transaction manager". It can be packaged as a stand-alone component or integrated into a database engine, application server, or operating system. One advantage of keeping the transaction manager separate from the database is the ability to coordinate distributed transactions -- transactions over multiple databases or other transactional resources.

Database engines incorporating transactional capabilities gave rise to client-server (or two-tier) architecture. Here, the client -- usually a desktop application written in Visual Basic, PowerBuilder, or another 4GL language -- interacts directly with the database through SQL statements.

[SEI]

The advent of the web popularized three-tier and n-tier architectures. There's a lot of variation in what is meant by these terms. The most basic type of three-tier architecture has a middle layer consisting of a transaction processing monitor. More common these days, especially in the Java world, is to deploy "business logic" in an application server as the layer between the clients and the database.

The term middleware denotes an emphasis on connecting distributed systems across a network. Often middleware incorporates transaction management. Middleware is something of a nebulous buzzword, but usually involves integrating systems from disparate vendors running on heterogeneous platforms. It has been used to describe CORBA, Microsoft's COM, transaction processing monitors, message queues, and application servers.

The ACID Properties

To be considered transactional a system must execute transactions in a way that maintains the ACID properties.

Atomicity	An atomic transaction must be all-or-nothing. Partial completion is not allowed.
Consistency	A transaction transforms a system from one consistent state to another, maintaining invariants and integrity constraints. Along the way the system may pass through inconsistent states, but at the end of a transaction, whether committed or aborted, the system is in a consistent state. The definition of consistent may be application specific.
Isolation	Each transaction has the illusion that there are no concurrent transactions. The system prevents any transaction from observing or acting upon any inconsistent intermediate state generated while another transaction is in progress.
Durability	The results of committed transactions must be persisted to stable storage even in cases of hardware failure or system crash.

The system must maintain the ACID properties not only during normal operation, but also in the presence of failures. Computers crash. Power fails. Communications get lost. A transaction processing system such as the ATM network needs to cope. The art of failing gracefully, without losing data or allowing inconsistencies to be left behind, is a major source of complexity for transaction processing applications.

Among the ACID properties, consistency is something of an odd man out. The definition of consistency is application dependent. Therefore, consistency must be maintained within the transactions in application code and with constraints in the data model.

The two fundamental techniques for maintaining the ACID properties are logging and locking. Write-ahead logging handles atomicity and durability, while locking takes care of isolation.

Commit and Abort

Transaction demarcation refers to the means of establishing the beginning and end of a transaction. This can be achieved directly in program code or declaratively as in EJB entity beans. Also, by default many databases use an "autocommit" feature which automatically issues a commit after every SQL statement.

A transaction can be completed in one of two ways -- it can commit or abort (otherwise known as rollback). A successful commit makes the transaction's updates permanent. The system transitions from one consistent state to another. An abort undoes all the transaction's updates, returning the system to its original state. Either way, the system remains in a consistent state. If a transaction needs to be undone after it has been committed, a compensating transaction can be performed.

Serializability

The concurrent execution of transactions must have the same effect as executing the transactions serially in some order without overlap. The classic example to illustrate nonserializability is a transaction (T1) that reads record X and writes record Y executing at the same time as another transaction (T2) that reads Y and writes X:

T1: r1[x], w1[y]
T2: r2[y], w2[x]

The operations may be interleaved in different ways:

H1: r1[x], r2[y], w1[y], w2[x]
H2: r1[x], w1[y], r2[y], w2[x]
H3: r2[y], w2[x], r1[x], w1[y]

H1, H2, and H3 are histories, also called schedules. A history is just a sequence of operations. Two operations are said to conflict if they access the same data and at least one of them is a write. Two histories are equivalent if they have the same operations and the conflicting operations are in the same order. This type of equivalence is called Conflict Equivalence. A history is serializable if and only if there exists an equivalent serial history.

H2 and H3 are the two possible serial histories of T1 and T2. H1 is equivalent to neither, therefore, history H1 is not serializable. Generally, in a serializable history either transaction A can see transaction B's updates or B can see A's updates but not both.

T3: r1[x] w1[x]
T4: r2[x] w2[y]

H4: r1[x] r2[x] w1[x] w2[y]
H5: r2[x] w2[y] r1[x] w1[x]

Here, H5 is a serial history and H4 is equivalent to H5. So, H4 is serializable.

Serializability Graphs

A serializability graph can be constructed that describes the conflicts between operations in a given history. Take the history H6.

H6: r1[x], r2[x], r3[y], w2[x], r1[y], w1[y], r3[x], w3[z]

The transactions form the vertices of the graph. For each conflicting pair of operations we draw a directed edge. Because r1[x] conflicts with w2[x] and r1[x] precedes w2[x] we draw an edge from T1 to T2. Likewise, r3[y] conflicts with w1[y], and w2[x] conflicts with r3[x].

According to the Serializability Theorem, a history is serializable if and only if there are no cycles in its serialization graph. The graph of H6 contains a cycle, so H6 is not serializable.

Now consider the serializability graph of the slightly different history H7...

H7: r1[x], r2[x], r3[y], w2[x], r1[y], w1[z], r3[x], w3[y]

No cycles, no problem. H7 is serializable.

Enforcing Serializability

The tools available to the transaction manager to enforce serializability are few. A transaction manager has only three options when requested to perform an operation by a client: perform it, block making the client wait, or refuse to perform the operation, in which case the transaction is aborted.

Blocking allows the transaction manager to execute the operations in a different order from which it receives them. By reordering operations, the transaction manager seeks a serializable order. If this cannot be achieved, which is possible because the transaction manager can't predict the future any better than you or I can, the transaction manager must resort to aborting one of the transactions. The client then has the option of retrying or giving up.

Locking

Locking is a basic building block of concurrency control and ensures the property of isolation. As a client of a database server, the implementation of concurrency control is mostly hidden. But, underneath the hood, most database servers use locking. (Multiversion concurrency control is one alternative.)

A lock is a mechanism for reserving access to a resource or piece of data. This prevents conflicting concurrent operations from stepping on each other. A lock can be as simple as a flag indicating that a given item is in use. Accessing a locked resource typically follows the pattern:

1. acquire lock
2. perform operations
3. release lock

The attempt to acquire the lock may succeed immediately or it may block causing the requesting thread to wait. It will block if another client already holds a conflicting lock. This can lead to a situation called lock contention where several clients are competing for the same locks.

For many purposes, multiple read operations can proceed at once with no problem, while write operations need exclusive access. A reader/writer lock (also called shared and exclusive locks) is a type of lock that does the trick in cases like this. This type of lock is consistent with the above definition of conflicting operations in which a read and a write or two writes on the same data conflict.

Locking and performance

Locking can have tremendous implications for performance. Having a good understanding of the locking mechanisms and configuration options of your database engine can be a valuable asset during performance tuning.

Two-Phase Locking

In order to guarantee serializability, locking by itself is insufficient. The two-phase locking (2PL) protocol introduces a restriction on when a transaction may acquire and release locks. A transaction must acquire all necessary locks before releasing any of them. In other words, once a transaction has released a lock it may not acquire any more locks. Locks are acquired during a growing phase, and released during a shrinking phase. 2PL guarantees serializability. Interestingly, serializable histories that violate the two phase locking protocol do exist. Capturing these lost opportunities for concurrency is a topic of ongoing research.

Strict two-phase locking is more restrictive still and is the standard protocol for database implementation. Strictness is the extra requirement that all locks be held until after commit or abort. This allows locking to be handled automatically by the transaction manager, transparently from the point of view of the applications programmer.

Deadlock

Deadlock occurs when two transactions are each waiting on a resource that the other transaction holds. More generally, a set of transactions may form a cycle where each member of the set is waiting for a lock held by another member of the set. None of the transactions in the set can make progress.

Transactions managers must be able to detect and deal with deadlock. Deadlock can be detected by constructing a waits-for graph and looking for cycles or simply by time-out. In either case, a transaction will have to be aborted to break the deadlock.

Granularity

Lock granularity refers to size of the resource being locked. In database engines, it is common to support page level locking or row level locking, where a page is the same size as a single block on disk. Presumably, multiple rows can fit onto one page, so row level locking has a fine granularity while page level locking is coarse. Locking a whole table (or file) is coarser still. Locking at a finer level of granularity allows more concurrency. The trade-off is in higher complexity and more resources spent managing the locks themselves.

In a database, a file contains multiple pages and a page contains multiple rows. Multiple granularity locking uses this hierarchical structure to, in effect, size the lock to fit the purposes. Queries that access large numbers of records will benefit from the lower overhead of coarser grained locking. Queries that update a single row can lock fine-grained units, maximizing concurrency.

Optimistic vs. Pessimistic Locking

Optimistic locking works under the assumption that conflicts are unlikely. The transaction first reads the data it needs, then releases locks. It performs whatever computation is required, and then checks for conflicts with other concurrent transactions. If conflicts are detected the transaction aborts, otherwise it commits.

This has several advantages. Write locks are acquired only at the end of the transaction and held as briefly as possible. Transactions that crash or hang while holding contended resources end up aborting automatically without blocking transactions that are still working properly. If there are few conflicts, a higher degree of concurrency is obtained. The downside is the extra work in handling aborted transactions, usually by retrying.

In a pessimistic locking, transactions request locks as needed and hold them until completion. Since locks are held longer, this increases the potential for blocking and deadlock. The advantage with pessimistic locking is that conflicts are detected earlier and usually handled by blocking rather than aborting.

Degrees of Isolation:

So far, we've been talking about achieving fully serializable transactions. Now, things start to get weird. Full serializability can be expensive in terms of performance, particularly in the presence of queries that acquire lots of locks. So, maybe we don't need to be such sticklers for perfect correctness. Perhaps, we can tolerate some potential for error to gain higher throughput.

Isolation levels below serializable trade a weaker set of correctness guarantees in exchange for higher performance. Not only is this kind of "cheating" enabled (usually by default) in all major databases. It is even enshrined in the SQL standard. Shocking, isn't it?

The SQL-92 standard defines isolation levels in terms of particular kinds of transaction anomalies, primarily because that sounds less scary than big flaming hairy errors. Here are the SQL-92 standard anomalies and isolation levels.

SQL Transaction Anomalies
Dirty reads	A transaction reads data that has been written by another transaction that has not yet been committed.
Nonrepeatable (fuzzy) reads	A transaction rereads data it has previously read and finds that another committed transaction has modified or deleted the data.
Phantom reads	A transaction re-executes a query returning a set of rows that satisfies a search condition and finds that another committed transaction has inserted additional rows that satisfy the condition.

SQL Isolation Levels
Isolation level	Dirty read	Nonrepeatable read	Phantom
Read uncommitted	Yes	Yes	Yes
Read committed	No	Yes	Yes
Repeatable read	No	No	Yes
Serializable	No	No	No

Read committed isolation allows release of read locks before the end of a transaction. Imagine a query that scans through a whole table and updates only a few records matching some specific criteria to see the performance benefit of releasing the read locks early.

Cursor Stability is another type of isolation which is commonly referred to although not part of the standard. It is a variant of read committed that makes special provision for efficiently iterating through rows with a cursor.

Read uncommitted isolation lowers the bar further. Transactions don't bother setting read locks. A transaction may read uncommitted data, which may be inconsistent or may be wiped out later by an abort.

The most common default isolation level is read committed, which is the default of Oracle, SQL Server, and PostgreSQL. DB2's default is cursor stability. MySQL's InnoDB defaults to repeatable read.

Logging and Recovery

The properties of atomicity and durability require that at the moment of commit, the updates of a transaction become a permanent part of the database. But, updating the complicated data structures of the database is a rather involved process. How is this contradiction resolved?

Logging

The term write-ahead logging means that before any updates are applied to the database, they are first recorded in the log. Once all updates for a transaction are logged, the transaction can safely commit in full confidence that, if anything goes wrong, recovery is possible. If a failure occurs while the database is being updated, the log can be replayed and any incomplete changes reapplied to the database, which is what happens during recovery.

The log is a simply a sequential file with a record describing each update and each commit or abort. Because a sequential log file is simple in structure, writing to the log is fast. This is crucial because the overall limiting factor on TP throughput is usually the speed of writing to the log.

Recovery

The recovery process uses the log to bring the database back up to a current and consistent state. Any transactions that were uncommitted at the time of failure are aborted. By the end of recovery, the database reflects the updates of all transactions committed before the failure. Any traces of uncommitted transactions have been rolled back. The system is then ready to begin accepting new transactions.

Checkpoints

A checkpoint is a point of synchronization between the database and the transaction log. It is a special log record which allows the recovery process to figure out what work needs to be undone or redone. Without checkpoints, the recovery process would have to scan through the entire log starting at the beginning.

Distributed Transactions

Imagine a business that has an accounting system running on an old mainframe, an order entry system on SQL-Server, and manages inventory on an Oracle database. If the company has the audacity to actually sell something, it's likely they'll want to check inventory, record an order invoice, and credit accounts receivable all in a single transaction.

Two-phase Commit

Two-phase commit is a protocol used to coordinate transactions across multiple transactional resources. 2PC involves two rounds of messages between a transaction manager, called the coordinator, and the participants. Each participant is a transactional resource which can commit or abort independently. The trick is to ensure that either they all commit or they all abort.

In the first round of messages, the coordinator sends a prepare message to each participant. If all participants respond with a prepared message, the transaction commits. Any participant may unilaterally abort by responding with a not-prepared message. If any participant responds with not-prepared or does not respond, the transaction aborts. In the second round, the coordinator notifies the participants of the outcome, whether commit or abort.

After replying with a prepared message, a participant is in a uncertainty period until it receives a commit or abort message from the coordinator. The participant cannot unilaterally commit or abort during the uncertainty period.

The 2PC protocol is subject to blocking. The participants wait for the order to commit or abort from the coordinator while still holding locks. If the coordinator fails, participants will not be able to resolve their transactions and will have to continue holding locks until the coordinator recovers.

X/Open

X/Open XA is a specification that standardizes the interaction between the coordinator and the participants, allowing products from different vendors to interoperate in distributed transactions.

Message Queuing

A message queue provides transactional asynchronous communications between one process or application and another. Message queues bring the same kinds of guarantees to communications that transactional databases provide for storage. Because they are asynchronous, the sender does not wait for a response yielding faster (perceived) response time.

Message queues offer features and service guarantees that make them much more powerful than simple socket connections. Message queues have the ability to "store and forward" messages guaranteeing delivery even when the intended recipient is down or unreachable. Queues can be configured to guarantee delivery once and only once. Load balancing can be achieved by feeding tasks to multiple servers through the same queue. Queues are also capable of guaranteeing in-order delivery or reordering requests by priority.

Message queuing is prominent in the (highly buzzwordy) field of EAI (Enterprise Application Integration) and is a core component in implementations of the Enterprise Service Bus. If your application fits the publish-subscribe model or can benefit from asynchronous communication, a message queue might be a good choice.

Web Services and SOA

While we're descending into a quagmire of buzzwords, we may as well mention Service Oriented Architecture. SOA involves assembling business applications out of loosely coupled independent "services", usually web services speaking XML. There's little doubt that transactions will continue to be important in the SOA world. There may be a need for transactions that span multiple web services or for web services to participate in transactions along with other transactional resources like databases or message queues.

Transaction processing in the web services world is hindered by a few issues. SOA applications are being used to automate complicated business activities involving highly distributed parties. SOA is usually implemented over a protocol (HTTP) that does not maintain an open connection increasing network latency and contributing to longer running transactions. Also, there is a lesser degree of trust between participants. These factors tend not to be handled well by traditional TP techniques.

Under some circumstances, the ACID properties may be impractical and applications may have to make due with looser sets of guarantees. It seems (from what I was able to Google up) that current practice is to keep service granularity larger than that of the transaction. The web service wraps a transactional resource rather than the transaction spanning multiple web services. This approach avoids the costly overhead of coordinated widely distributed transactions. Nonetheless, standards for transactional web services are struggling to mature.[IBM]

Software Architecture with Transactions

Transaction management facilities come packaged with application servers, database engines, and as a completely separate component. Using the transaction management built into a database is a common choice, based on simplicity of programming and the performance advantage of coordinating transactions close to the data. Other options certainly exist.

For certain problems, message queuing can offer a superior alternative to distributed transactions. The advantage is that messaging removes the need for one program to wait on the other as happens during two-phase commit. Message queuing between two applications might be thought of as a looser form of coupling than participating in a distributed transaction.

At times, language or OS level concurrency techniques like semaphores, pthreads, or Java's synchronized keyword can be substituted for transactions. These techniques can enforce isolation for transient in-memory objects, which, though short of the ACID properties, is often enough.

Two outliers of the transaction processing world are distributed objects (CORBA) and tuple spaces (ex. Linda or JavaSpaces). CORBA seems to have fallen off the map since its heyday in the late 90's, while JavaSpaces suffers from its single-platform orientation. While a niche player, JavaSpaces and its underlying technology, Jini, embody ideas that may well be ahead of their time.

TP techniques are not without limitations. Long running transactions are problematic due to lock holding. Cooperative protocols, like 2PC, require a certain degree of trust among participants in a transaction. ACID transactions work best for short-lived activities involving resources under local control. For longer running workflow-like scenarios, other options are currently being mapped out: (BPEL, J2EE Activity Service).

Tips for writing efficient transactions

• reduce time spent holding locks
• reduce transaction execution time
• set locks later in the transaction
• split up long running transactions into series of short lived transactions
• turn off autocommit and do explicit commits
• avoid performing slow operations like user input in a transaction
• be aware of the effects of lock granularity
• be aware of the effects of "hot" (frequently updated) data items

Conclusion

Transaction processing is a powerful and well established model. As application developers, a little insight into the mechanisms involved will allow us to develop efficient software on transactional platforms. As architects, we will be better able to design systems that leverage transactional capabilities offered by "enterprise" infrastructure software.

Concurrency is becoming a more important tool for application developers.[Sutter] Effective use of concurrency is a key to scalability and performance. One of the easiest and safest ways to exploit concurrency is to use the transaction processing capabilities built into database engines and application servers.

Transaction processing has been the context for the discovery of some deep theoretical results in concurrency. The theory and principles of transactions are being increasingly applied in new ways and in areas outside of their traditional uses.