Sunday, June 26, 2011

STM Arjuna

I'd forgotten how long ago I'd promised to talk about some of the STM work we've been doing. Well I haven't been able to do much more on it for a while, but I do have time to at least outline what's possible at the moment. So let's just remember a bit about the current way in which you can use JBossTS to build transactional POJOs without the need for a database; we'll use an example to illustrate:
  public class AtomicObject extends LockManager
{
public AtomicObject()
{
super();

state = 0;

AtomicAction A = new AtomicAction();

A.begin();

if (setlock(new Lock(LockMode.WRITE), 0) == LockResult.GRANTED)
{
if (A.commit() == ActionStatus.COMMITTED)
System.out.println("Created persistent object " + get_uid());
else
System.out.println("Action.commit error.");
}
else
{
A.abort();

System.out.println("setlock error.");
}
}

public void incr (int value) throws Exception
{
AtomicAction A = new AtomicAction();

A.begin();

if (setlock(new Lock(LockMode.WRITE), 0) == LockResult.GRANTED)
{
state += value;

if (A.commit() != ActionStatus.COMMITTED)
throw new Exception("Action commit error.");
else
return;
}

A.abort();

throw new Exception("Write lock error.");
}

public void set (int value) throws Exception
{
AtomicAction A = new AtomicAction();

A.begin();

if (setlock(new Lock(LockMode.WRITE), 0) == LockResult.GRANTED)
{
state = value;

if (A.commit() != ActionStatus.COMMITTED)
throw new Exception("Action commit error.");
else
return;
}

A.abort();

throw new Exception("Write lock error.");
}

public int get () throws Exception
{
AtomicAction A = new AtomicAction();
int value = -1;

A.begin();

if (setlock(new Lock(LockMode.READ), 0) == LockResult.GRANTED)
{
value = state;

if (A.commit() == ActionStatus.COMMITTED)
return value;
else
throw new Exception("Action commit error.");
}

A.abort();

throw new Exception("Read lock error.");
}

public boolean save_state (OutputObjectState os, int ot)
{
boolean result = super.save_state(os, ot);

if (!result)
return false;

try
{
os.packInt(state);
}
catch (IOException e)
{
result = false;
}

return result;
}

public boolean restore_state (InputObjectState os, int ot)
{
boolean result = super.restore_state(os, ot);

if (!result)
return false;

try
{
state = os.unpackInt();
}
catch (IOException e)
{
result = false;
}

return result;
}

public String type ()
{
return "/StateManager/LockManager/AtomicObject";
}

private int state;
}
Yes, quite a bit of code for a transactional integer. But if you consider what's going on here and why, such as setting locks and creating potentially nested transactions within each method, it starts to make sense. So how would we use this class? We'll let's just take a look at a unit test to see:
     AtomicObject obj = new AtomicObject();
AtomicAction a = new AtomicAction();

a.begin();

obj.set(1234);

a.commit();

assertEquals(obj.get(), 1234);

a = new AtomicAction();

a.begin();

obj.incr(1);

a.abort();

assertEquals(obj.get(), 1234);
But we can do a lot better in terms of ease of use, especially if you consider what's behind STM: where objects are volatile (don't survive machine crashes). And this is where our approach comes in. Let's look at the example above and create an interface for the AtomicObject:
public interface Atomic
{
public void incr (int value) throws Exception;

public void set (int value) throws Exception;

public int get () throws Exception;
}
And now we can create an implementation of this:
@Transactional
public class ExampleSTM implements Atomic
{
@ReadLock
public int get () throws Exception
{
return state;
}

@WriteLock
public void set (int value) throws Exception
{
state = value;
}

@WriteLock
public void incr (int value) throws Exception
{
state += value;
}

@TransactionalState
private int state;
}
Here we now simply use annotations to specify what we want. The @Transactional is needed to indicate that this will be a transactional object. Then we use @ReadLock or @WriteLock to indicate the types of locks that we need on a per method basis. (If you don't define these then the default is to assume @WriteLock). And we use @TransactionalState to indicate to the STM implementation which state we want to operate on and have the isolation and atomicity properties (remember, with STM there's no requirement for the D in ACID). If there's more state in the implementation than we want to recover (e.g., it can be recomputed on each method invocation) then we don't have to annotate it.

But that's it: the AtomicObject and ExampleSTM classes are identical. So let's take a look at another unit test:
      RecoverableContainer theContainer = new RecoverableContainer();
ExampleSTM basic = new ExampleSTM();
Atomic obj = obj = theContainer.enlist(basic);
AtomicAction a = new AtomicAction();

a.begin();

obj.set(1234);

a.commit();

assertEquals(obj.get(), 1234);

a = new AtomicAction();

a.begin();

obj.incr(1);

a.abort();

assertEquals(obj.get(), 1234);
Think of the RecoverableContainer as the unit of software transactional memory, within which we can place objects that it will manage. In this case ExampleSTM. Once placed, we get back a reference to the instance within the unit of memory, and as long as we use this reference from that point forward we will have the A, C and I properties that we want.

Tuesday, June 14, 2011

Ever wondered about transactions and threads?

No? Well you really should! When transaction systems were first developed they were single-threaded (where a thread is defined to be an entity which performs work, e.g., a lightweight process, or an operating-system process.) Executing multiple threads within a single process was a novelty! In such an environment the thread terminating the transaction is, by definition, the thread that performed the work. Therefore, the termination of a transaction is implicitly synchronized with the completion of the transactional work: there can be no outstanding work still going on when the transaction starts to finish.

With the increased availability of both software and hardware multi-threading, transaction services are now being required to allow multiple threads to be active within a transaction (though it’s still not mandated anywhere, so if this is something you want then you may still have to look around the various implementations). In such systems it is important to guarantee that all of these threads have completed when a transaction is terminated, otherwise some work may not be performed transactionally.

Although protocols exist for enforcing thread and transaction synchronization in local and distributed environments (commonly referred to as checked transactions), they assume that communication between threads is synchronous (e.g., via remote procedure call). A thread making a synchronous call will block until the call returns, signifying that any threads created have terminated. However, a range of distributed applications exists (and yours may be one of them) which require extensive use of concurrency in order to meet real-time performance requirements and utilize asynchronous message passing for communication. In such environments it is difficult to guarantee synchronization between threads, since the application may not communicate the completion of work to a sender, as is done implicitly with synchronous invocations.

As we’ve just seen, applications that do not create new threads and only use synchronous invocations within transactions implicitly exhibit checked behavior. That is, it is guaranteed that whenever the transaction ends there can be no thread active within the transaction which has not completed its processing. This is illustrated below, in which vertical lines indicate the execution of object methods, horizontal lines message exchange, and the boxes represent objects.



The figure illustrates a client who starts a transaction by invoking a synchronous ‘begin’ upon a transaction manager. The client later performs a synchronous invocation upon object a that in turn invokes object b. Each of these objects is registered as being involved in the transaction with the manager. Whenever the client invokes the transaction ‘end’ upon the manager, the manager is then able to enter into the commit protocol (of which only the final phase is shown here) with the registered objects before returning control to the client.

However, when asynchronous invocation is allowed, explicit synchronization is required between threads and transactions in order to guarantee checked (safe) behavior. The next figure illustrates the possible consequences of using asynchronous invocation without such synchronization. In this example a client starts a transaction and then invokes an asynchronous operation upon object a that registers itself within the transaction as before. a then invokes an asynchronous operation upon object b. Now, depending upon the order in which the threads are scheduled, it’s possible that the client might call for the transaction to terminate. At this point the transaction coordinator knows only of a’s involvement within the transaction so enters into the commit protocol, with a committing as a consequence. Then b attempts to register itself within the transaction, and is unable to do so. If the application intended the work performed by the invocations upon a and b to be performed within the same transaction, this may result in application-level inconsistencies. This is what checked transactions are supposed to prevent.

Some transaction service implementations will enforce checked behavior for the transactions they support, to provide an extra level of transaction integrity. The purpose of the checks is to ensure that all transactional requests made by the application have completed their processing before the transaction is committed. A checked transaction service guarantees that commit will not succeed unless all transactional objects involved in the transaction have completed the processing of their transactional requests. If the transaction is rolled back then a check is not required, since all outstanding transactional activities will eventually rollback if they are not told to commit.

As a result, most (though not all) modern transaction systems provide automatic mechanisms for imposing checked transactions on both synchronous and asynchronous invocations. In essence, transactions must keep track of the threads and invocations (both synchronous and asynchronous) that are executing within them and whenever a transaction is terminated, the system must ensure that all active invocations return before the termination can occur and that all active threads are informed of the termination. This may sound simple, but believe us when we say that it isn’t!

Unfortunately this is another aspect of transaction processing that many implementations ignore. As with things like interposition (for performance) and failure recovery, it is an essential aspect that you really cannot do without. Not providing checked transactions is different from allowing checking to be disabled, which most commercial implementations support. In this case you typically have the ability to turn checked transactions off when you know it is safe, to help improve performance. If you think there is the slightest possibility you’ll be using multiple threads within the scope of a single transaction or may make asynchronous transactional requests, then you’d better find out whether your transaction implementation it up to the job. I'm not even going to bother about the almost obligatory plug for JBossTS here ;-)

Thursday, June 2, 2011

WTF is Interposition?

Consider the situation depicted below, where there is a transaction coordinator and three participants. For this sake of this example, let us assume that each of these participants is on a different machine to the transaction coordinator and each other. Therefore, each of the lines not only represents participation within the transaction, but also remote invocations from the transaction coordinator to the participants and vice versa.


In a distributed system there’s always an overhead incurred when making remote invocations compared to making a purely local (within the same VM) invocation. Now the overhead involved in making these distributed invocations will depend upon a number of factors, including how congested the network is, the load on the respective machines, the number of transactions being executed etc. Some applications may be able to tolerate this overhead, whereas others may not. As the number of participants increase, so does the overhead for fairly obvious reasons.

A common approach to reduce this overhead is to realize that as far as a coordinator is concerned, it does not matter what the participant implementation does. For example, although one participant may interact with a database to commit the transaction, another may just as readily be responsible for interacting with a number of databases: essentially acting as a coordinator itself, as shown below:


In this case, the participant is acting like a proxy for the transaction coordinator (the root coordinator): it is responsible for interacting with the two participants when it receives an invocation from the coordinator and collating their responses (and it’s own) for the coordinator. As far as the participants are concerned, a coordinator is invoking them, whereas as far as the root coordinator is concerned it only sees participants.

This technique of using proxy coordinators (or subordinate coordinators) is known as interposition. Each domain (machine) that imports a transaction context may create a subordinate coordinator that enrolls with the imported coordinator as though it were a participant. Any participants that are required to enroll in the transaction within this domain actually enroll with the subordinate coordinator. In a large distributed application, a tree of coordinators and participants may be created.

A subordinate coordinator must obviously execute the two-phase commit protocol on its enlisted participants. Thus, it must have its own transaction log and corresponding failure recovery subsystem. It must record sufficient recovery information for any work it may do as a participant and additional recovery information for its role as a coordinator. Therefore, it is impossible for a normal participant to simply be a sub-coordinator because the roles are distinctly different; sub-coordinators are tightly coupled with the transaction system.

So the question then becomes when and why does interposition occur?

  • Performance: if a number of participants reside on the same node, or are located physically close to one another (e.g., reside in the same LAN domain) then it can improve performance for a remote coordinator to send a single message to a sub-coordinator that is co-located with those participants and for that sub-coordinator to disseminate the message locally, rather than for it to send each participant the same message.
  • Security and trust: a coordinator may not trust indirect participants and neither may indirect participants trust a remote coordinator. This makes direct registration impossible. Concentrating security and trust at coordinators can make it easier to reason about such issues in a large scale, loosely coupled environment.
  • Connectivity: some participants may not have direct connectivity with a specific coordinator, requiring a level of indirection.
  • Separation of concerns: many domains and services may simply not want to export (possibly sensitive) information about their implementations to the outside world.
You'll find interposition used in a number of transaction systems. Within JBossTS it's used by the JTS and XTS components.

When is a transaction not a transaction?

Most of the time when we talk about transactions we really mean database transactions (local transactions), or ACID transactions. These may also share the common name of Top-level (Flat) Transaction, or maybe Traditional Transactions. Several enhancements to the traditional flat-transaction model have been proposed and in this article I want to give an overview of some of them:

  • Of course the first has to be nested transactions. But I've mentioned these before several times, so won't go over them again here. But I will remind everyone that you can use them in JBossTS!
  • Next up are Independent Top-Level transactions which can be used to relax strict serializability. With this mechanism it is possible to invoke a top-level transaction from within another transaction. An independent top-level transaction can be executed from anywhere within another transaction and behaves exactly like a normal top-level transaction, that is, its results are made permanent when it commits and will not be undone if any of the transactions within which it was originally nested roll back. If the invoking transaction rolls back, this does not lead to the automatic rollback of the invoked transaction, which can commit or rollback independently of its invoker, and hence release resources it acquires. Such transactions could be invoked either synchronously or asynchronously. In the event that the invoking transaction rolls back compensation may be required. Guess what? Yup, we support these too!
  • Now we move on to Concurrent Transactions: just as application programs can execute concurrently, so too can transactions (top-level or nested), i.e., they need not execute sequentially. So, a given application may be running many different transactions concurrently, some of which may be related by parent transactions. Whether transactions are executed concurrently or serially does not affect the isolation rules: the overall affect of executing concurrent transactions must be the same as executing them in some serial order.
  • Glued Transactions are next in our line up: top-level transactions can be structured as many independent, short-duration top-level transactions, to form a “logical” long-running transaction; the duration between the end of one transaction and the beginning of another is not perceivable and selective resources (e.g., locks on database tables) can be atomically passed from one transaction to the next. This structuring allows an activity to acquire and use resources for only the required duration of this long-running transactional activity. In the event of failures, to obtain transactional semantics for the entire long-running transaction may require compensation transactions that can perform forward or backward recovery. As you might imagine, implementing and supporting glued transactions is not straightforward. In previous work we did around the CORBA Activity Service, we used JBossTS as the core coordinator and supported glued transactions. Although some of that code still exists today, it would definitely need a dusting off before being used again.
  • Last but by no means least ... distributed transactions. Need I say more?
So there's an outline of some, but not all, of the more exotic extended transaction models out there. The interesting thing is that with the basic transaction engine in JBossTS we can support many of them. Some of the ones I haven't outlined can also be implemented using a technique that another of the original Arjuna developers came up with: Multi-coloured Actions. Well worth a read, and perhaps something we may look at again someday.