This chapter is from the book
This chapter is from the book
This chapter is from the book
3.6 Transactions
In the context of concurrent OO programming, a transaction is an operation performed by an arbitrary client that invokes an arbitrary set of methods on an arbitrary set of participant objects, all without interference from other activities.
The arbitrariness of both the participants and the action sequences requires extensions of the joint action control strategies discussed in 3.5. Transaction techniques extend delegation-based synchronization and control to situations in which each participant may be unaware of the atomicity constraints placed on its actions, and cannot rely on more efficient structural solutions. In transaction frameworks, each participant (and each client) gives up its local autonomy in deciding how to perform concurrency control. Participants must instead reach consensus deciding how and when to perform actions and/or to commit to their effects.
Transaction frameworks are among the most famous examples of how providing components that implement valuable general-purpose functionality sometimes has the price of introducing a large number of programmer obligations. Classes supporting transaction protocols can be highly usable and reusable. Transaction frameworks can be used to tackle most of the concurrency problems discussed in this book. But they rely on designs in which each class, at each layer of functionality, supports a standardized transaction protocol that propagates control down through successive layers. The heaviness of transaction frameworks usually restricts their use to contexts in which you really need to set up objects so as to guarantee atomicity of arbitrary code sequences.
For example, you may be able to bypass transactional control if you know all the call-sequences that will ever be encountered in a component or application. In this case, you can specifically design support for each one (using whatever techniques happen to apply) without having to address the general case. This is a perhaps extreme extension of the idea (see 2.2.2) of padding reusable synchronized objects with atomic versions of frequently needed convenience methods. This is sometimes a plausible alternative, in the spirit of doing the simplest and surest thing that could possibly work. Similarly, you may be able to rely entirely on client-side locking (see 2.2.3) in cases where clients somehow know to obtain all locks required for a given action and how to avoid any potential deadlocks.
This section provides a brief overview of transaction-based techniques applicable in general-purpose concurrent programming contexts. The designs presented here deal only with internal concurrency, and not explicitly with databases or distribution. Because even lightweight (at least in a relative sense) internal transaction frameworks are normally tied to other application-specific constraints and features, you are unlikely to use the exact interfaces and classes described here (although most are simplified variants of those in the net.jini package). And if you instead rely on a standardized transaction framework such as JDBC or JTS, you will encounter additional issues tied to persistence support and related services that fall outside the scope of this book. However, the final example in this section (3.6.4) illustrates how the ideas behind transactions can help structure more ordinary concurrent OO designs. Thus, the main goals of this section are to give a brief synopsis of how transaction systems extend other approaches to concurrency control, and to present techniques that may be scaled down as needed to apply to other concurrency problems.
As a running example, consider again writing a transfer operation for the BankAccount class in 3.5.1. From a transactional point of view, a stand-alone transfer operation (without any provisions for automatic transfers) looks like:
pseudoclass AccountUser {
// Pseudocode
TransactionLogger log; // any kind of logging facility
// ...
// Attempt transfer; return true if successful
public boolean transfer(long amount,
BankAccount source,
BankAccount destination) {
TRANSACTIONALLY {
if (source.balance() >= amount) {
log.logTransfer(amount, source, destination);
source.withdraw(amount);
destination.deposit(amount);
return true;
}
else
return false;
}
}
}
The TRANSACTIONALLY pseudo-qualifier indicates that we'd like this code to be executed in an all-or-none fashion without any possibility of interference from other activities. Once implemented, this operation could be used in an automated transfer scheme of the sort described in 3.5.1. Additionally, the transactional approach permits greater flexibility than seen in our specific solution, although with significantly greater overhead. Once classes are fitted with transactional apparatus, it becomes possible to associate transactionality with any sequence of operations involving bank accounts.
3.6.1 Transaction Protocols
Transaction frameworks rely on extended forms of the before/after tactics characteristic of most concurrency control strategies. Here, the before-action is typically called join (or sometimes, begin) and the after-action is called commit. The main differences between join/commit and operations such as lock acquire/release stem from the fact that join/commit require consensus among the set of participating objects: All participants must agree to begin and end transactions. This leads to two-phase protocols surrounding join and/or commit — first to obtain consensus and then to act. If any participant disagrees about joining or committing, the attempted transaction is aborted. The most straightforward version of the basic protocol is:
For each participant p, if p cannot join, abort.
For each participant p, tentatively execute p's action.
For each participant p, if p cannot commit, abort.
For each participant p, commit p's effects of the transaction.
As in most concurrency control contexts, two complementary sets of policies can be applied to this protocol. In the purest form of optimistic transactions, participants can always join, but cannot always commit. In the purest form of conservative transactions, participants cannot always join, but if they do, they can always commit. Optimistic approaches apply best when the likelihood of contention is low enough to outweigh rollback costs. Conservative approaches apply best when it is difficult or impossible to undo actions performed during transactions. However, it is rare to find pure forms of each, and it is not hard to create frameworks that permit mixtures.
The most classic forms of conservative transactions can be implemented only if the identities of all participants can be known before any actions are taken. This is not always possible. In an OO system, the participants are just those objects whose methods are invoked during some call sequence that is wrapped as a transaction. Because of polymorphism, dynamic loading, etc., it is generally impossible to identify them all beforehand; instead, their identities become known only as the action unfolds. Still, in many cases, at least some participants are known beforehand and they can be probed before starting to engage in any unrecoverable action.
However, in most approaches to conservative OO transactions, participants join only tentatively. They can still later refuse to commit, using approximately the same strategy seen in optimistic transactions. Conversely, full rollback is not always necessary in optimistic approaches. Some roll-forward operations may be allowed if they do not impact overall functionality.
3.6.2 Transaction Participants
In addition to supporting methods for joining, committing, aborting, and (when necessary) creating transactions, each class in a structured transaction framework must declare all of its public methods to add a transaction control argument to its set of normal arguments.
A method invocation supplying a given transaction argument serves as a request to perform the associated action on behalf of the given transaction, but without committing to its effects until requested to do so. Methods take the form:
ReturnType aMethod(Transaction t, ArgType args) throws...
For example, BankAccount.deposit would be declared as:
void deposit(Transaction t, long amount) throws ...
Transaction is any type that supplies the necessary control information. This transaction information must be propagated throughout all methods invoked in the course of a particular transaction, including nested calls to helper objects. The simplest kind of transaction argument is a transaction key that uniquely identifies each transaction. Each method in each participating object is then responsible for using this key to manage and isolate actions in accord with the given transaction policy. Alternatively, a transaction argument may refer to a special control or coordinator object possessing methods that help participants perform their roles in transactions.
It is, however, possible to cheat here, and many transaction frameworks do. For example, transaction identifiers can be hidden as thread-specific data (see 2.3.2). Before/after control can be restricted to intercepted entry points into sessions performing services provided by components. Participants can be determined via reflection or scanning bytecodes. And rollback obligations can be semi-automated by serializing the entire state of a component and/or acquiring locks on entry into a service session. These kinds of tactics can help hide the details of transactional control from application writers. This comes at the expense overhead and usage restrictions that are not generally worthwhile in lightweight transaction frameworks performing internal concurrency control.
3.6.2.1 Interfaces
Participant classes must implement interfaces defining the methods used in transaction control. Here is a simple but representative interface:
class Failure extends Exception {}
interface Transactor {
// Enter a new transaction and return true, if possible
public boolean join(Transaction t);
// Return true if this transaction can be committed
public boolean canCommit(Transaction t);
// Update state to reflect current transaction
public void commit(Transaction t) throws Failure;
// Roll back state (No exception; ignore if inapplicable)
public void abort(Transaction t);
}
Among many other variants, it is possible to split the join phase similarly to the commit phase — a preliminary canJoin followed by a required join. The canCommit method is most often named prepare in transaction frameworks.
For simplicity of illustration, a single Failure exception type is associated with these operations, as well as all others in this series of examples. Participant objects are allowed to raise exceptions when they encounter actual or potential conflicts and when they are requested to participate in transactions they do not know about. Of course in practice, you'd want to subclass these exception types and use them to provide additional information to clients in cases of failure.
A second interface or class is needed to describe Transaction objects themselves. In discussing basic operations, we can use a no-op version:
class Transaction {
// add anything you want here
}
Again, it is not even necessary to associate an object with a transaction. A simple unique long transactionKey argument may suffice in place of all uses of Transaction. At the other extreme, you may need a TransactionFactory for creating all Transactions. This allows different kinds of Transaction objects to be associated with different styles of transactions.
3.6.2.2 Implementations
Participants in transactions must support both a transaction participant interface and an interface describing their basic actions. For example:
interface TransBankAccount extends Transactor {
public long balance(Transaction t) throws Failure;
public void deposit(Transaction t, long amount)
throws InsufficientFunds, Failure;
public void withdraw(Transaction t, long amount)
throws InsufficientFunds, Failure;
}
However, it is not always necessary to provide transactional signatures for pure accessor methods such as balance here. Instead (or in addition to transactional versions), such methods can return the most recently committed value when called from clients that are not participating in transactions. Alternatively, a special null-transaction type (or just passing null for the Transaction argument) can be used to denote one-shot invocations of transactional methods.
The most common approach to implementing transactional classes entails first splitting out underlying state representations into separate helper classes using either a provisional action or checkpointing approach (see 2.4.4 and 3.1.1.3). This makes it easier to perform virtual state changes that are updated only after commit operations and/or reverted from during abort operations. This approach is especially appropriate in transaction frameworks supporting persistence, which often require representations to be isolated anyway in order to be efficiently read from and written to disks and other media.
While this is by far the most tractable option, it leads to a sometimes-uncomfortable coding style in which objects must pretend to be in the states maintained by representations associated with particular transactions. Each normal public method performs operations only on the state representation associated with the given transaction, and invokes methods on other objects that are doing likewise.
Implementations of transactional methods (both control methods and base actions) can span the range from optimistic to conservative tactics. The following table sketches some highlights of the end-points for methods invoked with Transaction argument tx:
| Method | Optimistic | Conservative |
| join |
|
|
| action methods |
|
|
| abort |
|
|
| commit |
|
|
| canCommit |
|
|
When applied to the BankAccount class, taking the simplest possible option at each step leads to a mixed-strategy version that is probably not fit for serious use. Among other scale-downs, it maintains only a single backup copy of state (as a single field), so can be used only for non-overlapping transactions. But this version suffices to illustrate the general structure of transactional classes and also, implicitly, how much more code would be required to build a more useful version:
class SimpleTransBankAccount implements TransBankAccount {
protected long balance = 0;
protected long workingBalance = 0; // single shadow copy
protected Transaction currentTx = null; // single transaction
public synchronized long balance(Transaction t) throws Failure {
if (t != currentTx) throw new Failure();
return workingBalance;
}
public synchronized void deposit(Transaction t, long amount)
throws InsufficientFunds, Failure {
if (t != currentTx) throw new Failure();
if (workingBalance < -amount)
throw new InsufficientFunds();
workingBalance += amount;
}
public synchronized void withdraw(Transaction t, long amount)
throws InsufficientFunds, Failure {
deposit(t, -amount);
}
public synchronized boolean join(Transaction t) {
if (currentTx != null) return false;
currentTx = t;
workingBalance = balance;
return true;
}
public synchronized boolean canCommit(Transaction t) {
return (t == currentTx);
}
public synchronized void abort(Transaction t) {
if (t == currentTx)
currentTx = null;
}
public synchronized void commit(Transaction t) throws Failure{
if (t != currentTx) throw new Failure();
balance = workingBalance;
currentTx = null;
}
}
Classes obeying the Transactor interface can also employ arbitrary sharing of references among participants. For example, you can construct a Proxy account that forwards messages to another unrelated and otherwise uncontrolled account.
class ProxyAccount implements TransBankAccount {
private TransBankAccount delegate;
public boolean join(Transaction t) {
return delegate.join(t);
}
public long balance(Transaction t) throws Failure {
return delegate.balance(t);
}
// and so on...
}
3.6.3 Creating Transactions
Transactions that employ participants obeying the Transactor interface take a standard form, performing the following steps:
-
Create a new Transaction.
-
Invoke join on all (initially known) participants, failing immediately if any cannot join.
-
Try the entire action, aborting all participants on any failure and also rolling back any other auxiliary actions.
-
Upon completion, collect votes using canCommit and then commit or abort.
In most applications, it simplifies matters if the classes initiating transactions also support the Transactor interface. They may also support other methods that set up logging and related bookkeeping matters.
It is possible to automate many aspects of this protocol, redistribute or centralize functionality, and incorporate additional features. For example, an arbitrary amount of effort can be expended computing whether a transaction can be joined and/or committed in order to minimize the probability and expense of aborts. The actions and participant structure of potentially conflicting transactions can be analyzed and manipulated (for example, via use of conflict sets — see 3.3.2) to allow overlaps in cases when you can determine that no conflicts are possible.
Similarly, locking strategies can be refined to use read and write locks, or even further refined to support lock upgrades and intention locks (see 3.3.3.1).
3.6.3.1 Example
The following version of the transfer operation deals with several kinds of potential failures:
Semantic failure. There may not be sufficient funds in the accounts, in which case the method returns false. In this example, there is not even a pre-check that the source holds a sufficient balance. Even if it reported true, the withdraw attempt may fail anyway. Similarly, since the amount is allowed to be negative, destination.deposit may fail even if source.withdraw succeeds. (For a negative amount, a deposit acts like a withdraw and vice versa.) Additional exceptions could be caught here to deal with other errors encountered within these methods.
Interference. If either account cannot join or cannot commit to this transaction due to interference by another concurrent transaction, an exception is thrown indicating that the action is retryable.
Transaction error. Unrecoverable, catastrophic operation failure can occur if objects fail to commit after they say they can. Of course, these methods should do everything within their power to avoid commitment failure, since there is nothing to be done about this internal error. Here, the exception is propagated back to clients. In a more realistic version, this might in turn trigger a recovery from the last recorded persistent record of the object's state.
The recovery action for each of these cases happens to be identical in this example (and is factored into a helper method). The abort clauses perform the state rollbacks. But the log must be cancelled independently.
class FailedTransferException extends Exception {}
class RetryableTransferException extends Exception {}
class AccountUser {
TransactionLogger log; // a made-up class
// helper method called on any failure
void rollback(Transaction t, long amount,
TransBankAccount src, TransBankAccount dst) {
log.cancelLogEntry(t, amount, src, dst);
src.abort(t);
dst.abort(t);
}
public boolean transfer(long amount,
TransBankAccount src,
TransBankAccount dst)
throws FailedTransferException, RetryableTransferException {
if (src == null || dst == null) // screen arguments
throw new IllegalArgumentException();
if (src == dst) return true; // avoid aliasing
Transaction t = new Transaction();
log.logTransfer(t, amount, src, dst); // record
if (!src.join(t) || !dst.join(t)) { // cannot join
rollback(t, amount, src, dst);
throw new RetryableTransferException();
}
try {
src.withdraw(t, amount);
dst.deposit(t, amount);
}
catch (InsufficientFunds ex) { // semantic failure
rollback(t, amount, src, dst);
return false;
}
catch (Failure k) { // transaction error
rollback(t, amount, src, dst);
throw new RetryableTransferException();
}
if (!src.canCommit(t) || !dst.canCommit(t)) { // interference
rollback(t, amount, src, dst);
throw new RetryableTransferException();
}
try {
src.commit(t);
dst.commit(t);
log.logCompletedTransfer(t, amount, src, dst);
return true;
}
catch(Failure k) { // commitment failure
rollback(t, amount, src, dst);
throw new FailedTransferException();
}
}
}
3.6.4 Vetoable Changes
The fact that transaction frameworks can become almost arbitrarily heavy sometimes makes developers neglect simpler transactional solutions in smaller-scale concurrent design efforts. We conclude this section with a more ordinary-sounding design problem that is readily solved in a transactional fashion.
In the JavaBeansTM framework, component objects have sets of properties — fields that support get and set methods. Constrained properties may support vetoable set methods. A host component may have a list of listeners to which it sends vetoable change events in the course of a vetoable set method. If any listener responds to an event with a PropertyVetoException, then an attempted set of the property must be cancelled.
Some components express many of their operations as vetoable property changes. For example, an attempt to exit an editor application may be implemented as a set method, vetoable by any documents that have not yet been saved, as well as by confirmation dialogs.
Vetoable changes employ a slimmed-down transaction protocol that has only one active participant, but possibly several passive participants that must be polled for consensus. This can be done in either a conservative (i.e., before performing the update) or optimistic (i.e., after tentatively performing the update) fashion.
Here are some background notes about java.beans support needed to construct any solution:
Listeners are normally structured identically to the Observers discussed in 3.5.2 except that they are triggered via events that contain information about changes. In the normal case discussed here, the event-based method vetoableChange(PropertyChangeEvent evt) is invoked directly for each listener rather than being held in queues described in 4.1.
The VetoableChangeSupport and PropertyChangeSupport classes in the java.beans package can be used to manage multicasts to listeners. But, as usual, we'll adopt copy-on-write versions that allow lock-free multicasting. The version below uses VetoableChangeMulticaster and PropertyChangeMulticaster from util.concurrent, both of which support the same interfaces as java.beans versions. They provide methods to attach and detach listeners similar to those described in 2.4.4.
The VetoableChangeMulticaster.fireVetoableChange method constructs and multicasts a PropertyChangeEvent with event fields indicating the name of the property, its old value, and its proposed new value.
As a bland example illustrating basic techniques, consider a ColoredThing component with a vetoable color property. Each ColoredThing may have several vetoers, as well as several ordinary listeners that are notified upon every update. We'll use a simple conservative-style solution.
When a ColoredThing receives a request to setColor(Color newColor), it performs the following steps:
-
Check to see if another attempted setColor operation is already in progress, if so throwing a PropertyVetoException. To manage this, the class maintains a boolean execution state variable indicating whether a change is pending. A fancier (but probably less desirable) version could instead wait out other transactions using a wait/notifyAll construction based on changePending.
-
Check to see if the argument is null, in which case also refuse to change the property. This illustrates how a component can, in a sense, veto its own changes.
-
Invoke fireVetoableChange, which multicasts to vetoers.
-
If a PropertyVetoException results from the change event, abort and rethrow the exception. Otherwise, update the color field, clear the pending flag, and send a change event to all property listeners. As an extra safeguard here, the method maintains a completed variable used for detecting run-time exceptions. The finally clause makes sure that the changePending flag is reset properly if the method encounters such an exception.
class ColoredThing {
protected Color myColor = Color.red; // the sample property
protected boolean changePending;
// vetoable listeners:
protected final VetoableChangeMulticaster vetoers =
new VetoableChangeMulticaster(this);
// also some ordinary listeners:
protected final PropertyChangeMulticaster listeners =
new PropertyChangeMulticaster(this);
// registration methods, including:
void addVetoer(VetoableChangeListener l) {
vetoers.addVetoableChangeListener(l);
}
public synchronized Color getColor() { // property accessor
return myColor;
}
// internal helper methods
protected synchronized void commitColor(Color newColor) {
myColor = newColor;
changePending = false;
}
protected synchronized void abortSetColor() {
changePending = false;
}
public void setColor(Color newColor)
throws PropertyVetoException {
Color oldColor = null;
boolean completed = false;
synchronized (this) {
if (changePending) { // allow only one transaction at a time
throw new PropertyVetoException(
"Concurrent modification", null);
}
else if (newColor == null) { // Argument screening
throw new PropertyVetoException(
"Cannot change color to Null", null);
}
else {
changePending = true;
oldColor = myColor;
}
}
try {
vetoers.fireVetoableChange("color", oldColor, newColor);
// fall through if no exception:
commitColor(newColor);
completed = true;
// notify other listeners that change is committed
listeners.firePropertyChange("color", oldColor, newColor);
}
catch(PropertyVetoException ex) { // abort on veto
abortSetColor();
completed = true;
throw ex;
}
finally { // trap any unchecked exception
if (!completed) abortSetColor();
}
}
}
3.6.5 Further Readings
More thorough accounts of transactions in database systems may be found in:
Bacon, Jean. Concurrent Systems, Addison-Wesley, 1993.
Cellary, Wojciech, E. Gelenbe, and Tadeusz Morzy, Concurrency Control in Distributed Database Systems, North-Holland, 1988.
Gray, Jim, and Andreas Reuter. Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993.
Khoshafian, Setrag. Object-Oriented Databases, Wiley, 1993.
Lynch, Nancy, Michael Merritt, William Weihl, and Alan Fekete. Atomic Transactions, Morgan Kaufmann, 1994.
The following covers database programming using JDBC:
White, Seth, Maydene Fisher, Rick Cattell, Graham Hamilton, and Mark Hapner. JDBC™ API Tutorial and Reference, Second Edition, Addison-Wesley, 1999.