Functional way to implement a thread safe shared counter

Question

I'm relatively new to Scala and functional programming, and I like the idea that using immutable objects I can avoid many thread safety pitfalls. One thing still haunts me, and it's the classical example used to teach thread safety - the shared counter.

I was wondering if it would be possible to implement a thread-safe counter (a request counter in this example), using immutable objects, and functional concepts, and avoid synchronization completely.

So for reference here are first the classical mutable versions of the counter (excuse me for the public member variable, just for brevity of the examples)

Mutable, Non thread safe version:

public class Servlet extends HttpServlet {

  public int requestCount = 0; 

  @Override
  public void service(ServletRequest req, ServletResponse res) throws ... {
    requestCount++; //thread unsafe
    super.service(req, res);  
  }
}

Mutable, Classic thread safe version: (or so I hope...)

public class Servlet extends HttpServlet {

  public volatile int requestCount = 0;

  @Override
  public void service(ServletRequest req, ServletResponse res) throws ... {
    synchronized (this) {
      requestCount++;
    }
    super.service(req, res);  
  }
}

I was wondering if there is a way using immutable objects, and volatile variables to achieve thread safety without synchronization.

So here was my naive attempt. The idea is to have an immutable object for the counter, and just replace the reference to it, using a volatile variable. Feels fishy, but worth a shot.

Holder:

public class Incrementer {
  private final int value;
  public Incrementer(final int oldValue) {
    this.value = oldValue + 1;
  }

  public Incrementer() {
    this.value = 0;
  }

  public int getValue() {
    return value;
  }
}

Modified servlet:

public class Servlet extends HttpServlet {

  public volatile Incrementer incrementer = new Incrementer();

  @Override
  public void service(ServletRequest req, ServletResponse res) throws ... {
    incrementer = new Incrementer(incrementer.getValue());
    super.service(req, res);
  }
}

I have a strong feeling this is also not thread safe, as I'm reading from incrementer, and might get a stale value (e.g. if the reference was already replaced by another thread). In case it's indeed not thread safe, then I wonder if there is at all any "functional" way to handle such a counter scenario without locking / synchronization.

So my question(s) are

1. Is this thread safe by any chance?
2. If yes, why?
3. If not, is there at all any way to implement such a counter without synchronizing?

Although the example code above is in Java, replies in Scala are of course also welcome

Answer 1

Is this thread safe by any chance?

No, unless you have already created the immutable object in a synchronized block, this is not thread-safe. There are chances of creating a corrupt immutable object under thread race condition.

And to achieve the same functionality you can use AtomicInteger which avoids explicit synchronization.

public class Servlet extends HttpServlet {

  public AtomicInteger incrementer = new AtomicInteger (0);

  @Override
  public void service(ServletRequest req, ServletResponse res) throws ... {
    int newValue = incrementer.incrementAndGet();
    super.service(req, res);
  }
}

Answer 2

Thread safety from immutables looks much more like this.

val x = AtomicReference(Vector("salmon", "cod"))

// Thread 1
val y = x.get
println(y(y.length-1))

// Thread 2
x.getAndSet(x.get.tail)

If you were working mutably, you would be sorely tempted to have Thread 2 alter a mutable list, which could then make Thread 1's index fail. Or you'd have to copy the data, which might be very expensive if you didn't have collections meant to reuse as much as practical (and if the vector was longer). Or you'd have to synchronize large blocks in both threads instead of just atomically getting and/or get-setting your data.

You still have to synchronize somehow, and you may have to deal with out-of-date copies of data. But you don't have to keep track of who has a copy of which data structure and synchronize everyone like mad because that data might change out from under you and throw exceptions all over the place.