Alternatives to Multi Threading for concurrency in Java. STM and Actors

In the Java world we are used to work with concurrency dealing directly with Threads, Synchronization and Shared Data.

Java introduced a great deal of improvement in version 5 with the new concurrency facilities it provided, and had built on it in subsequent versions of the language.

These facilities are great and powerful, but they still can sometimes be hard to use correctly. I will cover concurrency in the traditional (and concurrency utilities) way in another post. This post is just about introducing a couple of alternatives to these.

In this post I’ll introduce the Software Transactional Memory (STM) model for concurrency. In a later post I’ll introduce the Actors model in Java.

STM: Very much like the transactions we are use to in DBs but working with objects in memory, keeping the ACI properties of transactions.

In this model we separate identity from state. This basically means that we have some entities that hold an inmutable state that can change over time. We’ll understand this better with the example that will follow.

The main advantage of this separation is that there is no need to block or synchronize as the state doesn’t change.

I’ll write a piece of code now and explain how it works. For the example I will use Akka and its support for STM with Multiverse.

Let’s assume we want to create a very simplistic kind of Stack (No validations, no anything) that only supports push, peek and pop and it should be thread safe. The simplistic code would be something like the following (No thread safe).

1.  
2. public class StmStack {
3.  
4.    private static int SIMPLISTIC_BIG_SIZE = 1024;
5.    private Object[] elements = new Object[SIMPLISTIC_BIG_SIZE];
6.    private int top=0;
7.  
8.    public Object pop() {
9.       Object value =  elements[top];
10.       top --;
11.       return value;
12.    }
13.  
14.    public Object peek() {
15.        return  elements[top];
16.    }
17.  
18.  
19.    public void push(Object value) {
20.        elements[top+1] = value;
21.        top++;
22.    }
23. }

It is very simple to see that there exist a thread safety problem with the state variable ‘top’. The problem is simply that this variable is shared mutable state. A variable that can be accessed, read and changed concurrently by mutliple threads. And of course the elements array itself has the same problem.

The common solution to this problem, would be to synchronize the access to the three methods. This approach is not hard to follow here in this very simple example, but even here it has a couple of drawbacks. One of them is that synchronizing and lock acquiring affects performance. Other can be that for example the peek method is not changing state, and in an application that will use peek more than any other method (more reading and moderate writing) no more than one thread will be able to peek. Also we need to remember to synchronize every method that we put in this class that will either read or write. When things start to get a little complicated (more locks, more granularity, more mutable shared state) understanding synchronization and locking logic is not very easy, and debugging synchronization and concurrency problems is hard to say the least.

We’ll see now the code using STM. This will look a bit complex

1. public class StmStack {
2.  
3.     private Ref<Elements> elements = new Ref<Elements>(new Elements());
4.     private Ref<Integer> top = new Ref<Integer>(-1);
5.  
6.     public Object pop() {
7.        final TransactionFactory factory =
8.                new TransactionFactoryBuilder().setBlockingAllowed(true).setTimeout(new DurationInt(6).seconds()).build();
9.  
10.        return new Atomic(factory) {
11.  
12.            @Override
13.            public Object atomically() {
14.                System.out.println("poping ");
15.                if (top.get() < 0) {
16.                    StmUtils.retry();
17.                }
18.                Object value = elements.get().get(top.get());
19.                top.swap(top.get() - 1);
20.                return value;
21.            }
22.        }.execute();
23.     }
24.  
25.     public Object peek() {
26.        final TransactionFactory factory =
27.                new TransactionFactoryBuilder().setBlockingAllowed(true).setTimeout(new DurationInt(6).seconds()).build();
28.  
29.        return new Atomic(factory) {
30.  
31.            @Override
32.            public Object atomically() {
33.                System.out.println("peeking ");
34.                if (top.get() < 0) {
35.                    StmUtils.retry();
36.                }
37.                return elements.get().get(top.get());
38.            }
39.        }.execute();
40.     }
41.  
42.     public void push(final Object value) {
43.        new Atomic() {
44.  
45.            @Override
46.            public Object atomically() {
47.                System.out.println("pushing " + value);
48.                elements.swap(new Elements(elements.get(), value, top.get()));
49.                top.swap(top.get() + 1);
50.                return "";
51.            }
52.        }.execute();
53.     }
54.  
55.     public int elements() {
56.        return top.get()+1;
57.     }
58. }
59.  
60. class Elements {
61.  
62.     private static int SIMPLISTIC_BIG_SIZE = 1024;
63.     private final Object[] elements;
64.  
65.     Elements(Elements elements, Object newElement, int top) {
66.        this.elements = elements.elements;
67.        this.elements[top + 1] = newElement;
68.     }
69.  
70.     Elements() {
71.        elements = new Object[SIMPLISTIC_BIG_SIZE];
72.     }
73.  
74.     Object get(Integer index) {
75.        return elements[index];
76.     }
77.  

The first thing to notice is that we changed the elements array of objects to a Ref object to an object of the new class Elements. We can also see that the Elements objects created are immutable. Noone has direct access to mutate its state. It never changes after created. This is one of the ideas that need to be encouraged. The use of immutable objects.

As we talked before the use of Ref helps to separate the ID of the reference to its state so in this case we have a Ref that will point to a different Elements object in different moments of time, but will not modify the one it has currently directly, it will just replace it. We do the same with the ‘top’ variable, making it a Ref instead of an Integer.

The next thing is the implementation of the different methods. As we can see we are wrapping each method content in an Atomic object, and putting the content inside the atomically method. This will ensure that the operation runs inside in a transaction.

The transaction ensures that all the values in the Ref variables are consistently changed or rolled back in case some other transactions modify them in the meantime, retrying automatically if that is the case. We can also observe the ‘retry’ method call. This method help us retry the transaction in the case a pre-condition is not met to run the transaction in the first place.


I’ll show a couple of running examples now(Just the relevant code):

first we run 7 push operations in different threads:

final StmStack stack = new StmStack();
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
sleep();
System.out.println(stack.elements());

The output:

pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
Number of elements: 7

Event though we called the push on the stack only 7 times, we can see that the push method (actually just the transaction part) was executed more than 20 times. This is because of all the retrying when multiple threads collide in the transaction execution. We can see that maybe for heavily writing applications STM transactions might not be the best solution because of all the retrying.


Now we run just 1 push, and then 6 peeks.


push(stack);
sleep(2000);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
sleep(8000);
System.out.println(stack.elements());

And the output

pushing asdad
pushing asdad
peeking
peeking
peeking
peeking
peeking
peeking
Number of elements: 1

We can see that no retry is needed for the peeking. We can see that STM is better suited for multiple reads, low-to-moderate writes.

So with STM we have a model that avoids the use of explicit locking, offers great concurrency performance, helps encourage the use of immutable types and just mutable References, makes explicit the parts that we expect to be executed atomically.
It also dynamically and automatically handles threads and contention, and can help mitigate or entirely remove deadlocks as we don’t deal with locking or lock orders anymore.

STM is an alternative worth considering if we have requirements for concurrency that adjust to this model.

A lot more information in:


AKKA Documentation

And