Sunday, February 19, 2012

Optimistic STM

It's been a while since I last posted anything on the Software Transactional Memory work that's been going on in JBossTS (aka Narayana). At that time we had everything in place for you to write transactional applications that have all of the ACID properties or, more common for STM, without the D. Per object concurrency control is done through locks and type specific concurrency control is available. You can define locks on a per object and per method basis, and combined with nested transactions this provides for a flexible way of structuring applications that would typically not block threads unless there is really high contention:

@Transactional

public class SampleLockable implements Sample

{

public SampleLockable (int init)

{

_isState = init;

}

@ReadLock

public int value ()

{

return _isState;

}


@WriteLock

public void increment ()

{

_isState++;

}

@WriteLock

public void decrement ()

{

_isState--;

}


@State

private int _isState;

}


If you recall from previous articles, all but the @Transactional annotation are optional, with sensible defaults taken for everything else including locks and state. And you create and use instances fairly simply:


RecoverableContainer theContainer = new RecoverableContainer();

Sample obj1 = theContainer.enlist(new SampleLockable(10));


However, the locking strategy we had originally was pessimistic. As I mentioned separately:

"Most transaction systems utilize what is commonly referred to as pessimistic concurrency control mechanisms: in essence, whenever a data structure or other transactional resource is accessed, a lock is obtained on it as described earlier. This lock will remain held on that resource for the duration of the transaction and the benefit of this is that other users will not be able to modify (and possibly not even observe) the resource until the holding transaction has terminated. There are a number of disadvantages of this style: (i) the overhead of acquiring and maintaining concurrency control information in an environment where conflict or data sharing is not high, (ii) deadlocks may occur, where one user waits for another to release a lock not realizing that that user is waiting for the release of a lock held by the first."

And the obvious alternative to this approach is optimistic:

"Therefore, optimistic concurrency control assumes that conflicts are not high and tries to ensure locks are held only for brief periods of time: essentially locks are only acquired at the end of the transaction when it is about to terminate. This kind of concurrency control requires a means to detect if an update to a resource does conflict with any updates that may have occurred in the interim and how to recover from such conflicts. Typically detection will happen using timestamps, whereby the system takes a snapshot of the timestamps associated with resources it is about to use or modify and compares them with the timestamps available when the transaction commits."

Therefore, you can probably guess what's just been added to our STM implementation? Yes, that's right ... optimistic concurrency control! In line with the annotation based approach we've used so far, there are now two new annotations: @Optimistic and @Pessimistic, with Pessimistic being the default. These are defined on a per interface basis and define the type of concurrency control implementation that is used whenever locks are needed:

@Transactional

@Optimistic

public class SampleLockable implements Sample

{

public SampleLockable (int init)

{

_isState = init;

}

@ReadLock

public int value ()

{

return _isState;

}


@WriteLock

public void increment ()

{

_isState++;

}

@WriteLock

public void decrement ()

{

_isState--;

}


@State

private int _isState;

}


And that's it. No other changes are needed to the interface or to the implementation. However, at present there is a subtle change in the way in which you create your objects. Recall how that was done previously and then compare it with the style necessary when using optimistic concurrency control:

RecoverableContainer theContainer = new RecoverableContainer();

Sample obj1 = theContainer.enlist(new SampleLockable(10));

Sample obj2 = theContainer.enlist(new SampleLockable(10),

theContainer.getUidForHandle(obj1));


In the original pessimistic approach the instance obj1 can be shared between any number of threads and the STM implementation, along with JBossTS, will ensure that the state is manipulated consistently and safely. However, with optimistic concurrency we need to have one instance of the state per thread. So in the above code we first create the object (obj1) and then we create a copy of it (obj2), passing a reference to the original to the container.

It is likely that the API for this will change soon in order to unify optimistic and pessimistic: the aim is to make it as opaque as possible to the application so you only have to modify an annotation when you want to change the implementation. One other thing that we're considering is changing the implementation dynamically, perhaps based on monitored metrics for contention. But for now that's it and it's all available in the Narayana git repository.