Multiverse: Non Blocking Transactions

If an application is using traditional locks, it it quite hard to use a different model then a thread per operation because once a thread enters a lock (a lock you don’t have any control over), the thread is ‘lost’. With IO there is a special extension (non blocking IO) that makes it possible to bypass this behaviour so you can have one thread serving multiple sockets. But if you use traditional concurrency control then you are on your own.

With Multiverse (a Java based STM implementation) it is not only possible to block on multiple resources (for more information see the retry/orelse primitives in the STM literature), but in the 0.4 release it also is going to be possible to use a single thread to run multiple blocking transactions. For some time the idea was in the back of my mind and I had the gut feeling that it should be possible with STM. But I never gave it any serious thought because there is so much else to do. Last Friday I had a day off and apparently it was a good day because in 30 minutes I had something up and running.

In Multiverse a latch is used to register transactions as ‘being interested’ in changes of transactional objects. A latch is a blocking structure that can be opened, but once it is opened it can’t be closed, and others threads can wait (block) on the opening of the latch. If a retry happens (so a retryerror is thrown) the transactionmanager catches it, creates a latch and registers it at the read objects. Once a change happens on one of the read objects in the transaction, the latch is opened and the transaction can continue (technically it is restarted). But because the transaction/transactionmanager controls which latch implementation is used, there is a lot of design freedom.

How do non blocking transactions work?
Instead of relying on a traditional latch (so based on an intrinsic lock or a java.util.concurrent.locks.Condition), I replaced it with a different implementation:


public class NonBlockingLatch implements Latch {

private final AtomicBoolean open = new AtomicBoolean();
private final Runnable task;

public NonBlockingLatch(Runnable task) {
this.task = task;
}

@Override
public void open() {
if (open.compareAndSet(false, true)) {
tasks.put(task);
}
}

@Override
public boolean isOpen() {
return open.get();
}

@Override
public void awaitUninterruptible() {
throw new UnsupportedOperationException();
}

.....
}

This latch is added to all the transactional objects in the transaction, and it does a callback once it is opened. In this case it does a callback to some taskqueue of an executor and stores the task in the taskqueue so that the transaction can restart. In the 0.4 release of Multiverse an initial version of this functionality will be added.

Why should you want it?
The cool thing about non blocking transactions is that you could create 100.000 transactions for example while using a few hundred threads. You could build a trading system e.g. where transactions wait on some stock price to go under or over some threshold and buy/sell the stocks using a transaction on one or more transactional resources.

But the mechanism isn’t completely perfect; there is a lot of room for fairness/starvation prevention and at the moment the transaction is restarted on every change. And with this implementation it also is possible that the same transaction is run in parallel if multiple transactional resources are notified used in the same transaction. It seems that I don’t need to be bored the coming weeks with my Christmas leave.

Advertisements

2 Responses to Multiverse: Non Blocking Transactions

  1. […] Multiverse: Non Blocking Transactions « Blog of Peter Veentjer […]

  2. RosenK says:

    Hi,

    How your implementation differs from the Clojure’s STM?

    Rosen

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: