Concurrency Pattern: Object Update (part 2)

This is the second part of series on concurrent patterns for object updating/modification, and we are going to show a concurrent pattern for Multiple-Writers-Multiple-Readers that is Lock-Free for Write operations and Wait-Free Population-Oblivious for Read operations.
If you haven't done so, better start in part 1

In the end of the previous post we showed how to make an immutable class that has wait-free progress guarantees for Read operations, but the problem is that it allows only a single Writer thread. This time we are going to show how to implement it such that it allows multiple Writer threads, although they will be serialized.

We start by creating an inner class that encapsulates the data of the original class, and then we have a reference to that instance which we guard with a reader-writer lock:

class MyClass {

    static class InnerMyClass {

        final int a;

        final int b;

        final int c;

       InnerMyClass(int a, int b, int c) {

           this.a = a;

           this.b = b;

           this.c = c;

        }

    }

    InnerMyClass inner;

    ReentrantReadWriteLock rwlock;

    MyClass(int a, int b, int c) {

        InnerMyClass inner = new InnerMyClass(a, b, c);

        rwlock = new ReentrantReadWriteLock();

    }

    void incrementMembers() {

        rwlock.writeLock().lock();

        inner = new InnerMyClass(inner.a+1, inner.b+1, inner.c+1);

        rwlock.writeLock().unlock();

    }

    int sumMembers() {

        rwlock.readLock().unlock();

        InnerMyClass localInner = inner;

        rwlock.readLock().unlock();         

        return (localInner.a + localInner.b + localInner.c);

    }

}

The problem with this approach is that we're again blocking on both Write and Read operations, even if for the Reads it is a very small amount of time. To overcome this, we can replace the lock with an
AtomicReference to the InnerMyClass instance that is changed whenever there is a Write operation. The new code looks like this:

class MyClass {

    static class InnerMyClass {

        final int a;

        final int b;

        final int c;

       InnerMyClass(int a, int b, int c) {

           this.a = a;

           this.b = b;

           this.c = c;

        }

    }

    final AtomicReference<InnerMyClass> innerRef;

    MyClass(int a, int b, int c) {

        AtomicReference<InnerMyClass> innerRef = new AtomicReference<InnerMyClass>(new InnerMyClass(a, b, c));

    }

    void incrementMembers() {

        while (true) {

            InnerMyClass oldInner = innerRef.get();

            InnerMyClass newInner = new InnerMyClass(oldInner.a+1, oldInner.b+1, oldInner.c+1);

            if (innerRef.compareAndSet(oldInner, newInner)) break;

        }

    }

    int sumMembers() {

        InnerMyClass localInner = innerRef.get();

        return (localInner.a + localInner.b + localInner.c);

    }

}

Notice that the variable innerRef is final, but its contents are mutable because the reference to the
InnerMyClass instance can change in the compareAndSet() call.
This code is simpler than the previous version with the reader-writer lock, and it is again Wait-Free Population-Oblivious for Read operations. For Write operations, it gives a progress guarantee of Lock-Free because there is a CAS in a while(true) loop, which may fail indefinitely.

Having Wait-Free Reads and Lock-Free Write operations may seem like a great thing (and it kind of is), but there is a hidden issue that you need to be aware of. Imagine that you have several Write functions and each one takes a different amount of time, for example, imagine a new function to decrement the members that is very slow when compared to incrementMembers() :

    void decrementMembersSlow() {

        while (true) {

            InnerMyClass oldInner = innerRef.get();

            doLengthyCalculation();      // This function takes a really long time

            InnerMyClass newInner = new InnerMyClass(oldInner.a+1, oldInner.b+1, oldInner.c+1);

            if (innerRef.compareAndSet(oldInner, newInner)) break;

        }

    }

on a high contention scenario where one thread is attempting a decrementMembersSlow() and one or more threads are continuously doing incrementMembers(), this will cause the call to decrementMembersSlow() to never complete because, one of the other threads calling incrementMembers() will always "jump in front" between InnerMyClass oldInner = innerRef.get() and call compareAndSet() modifying the innerRef 's contents and causing the compareAndSet() in the decrementMembersSlow() to continuously fail, thus resulting in "starvation".

Yes, this is still Lock-Free, it's just that Lock-Free is not necessarily fair. Bear in mind that it's not a problem with this technique itself, it's just that if fairness is something important in your application then Lock-Free is not a strong enough guarantee for your needs. To add to the pain, every time there is a CAS failure, a new InnerMyClass instance will have to be created and the previous one cleaned up by the Garbage Collector, which causes more churn in the GC.

Advantages:
- Read operations are Wait-Free Population-Oblivious
- Write operations are Lock-Free
- Allows multiple Writers
- Simple to implement once you get the hang of it

Disadvantages:
- Needs a language with a Garbage Collector
- Slow and wasteful for large objects
- Lots of churn on the GC


There are still other techniques that may be better depending on the case. One of them is the Left-Right pattern which we have been working on for some time now, and are in the process of submitting a paper on it. As soon as it gets accepted we'll post the examples and code  ;)

In the meantime, here is a comparison table to help you chose the best technique for your particular problem: