Double checked locking 101

Question

I've found a peace of code I've wrote not long ago. It is used to fetch some dictinary from DB table only once and then return it to requestors. Seems like I tryed to implement double-checked locking here. Is it correct? If not, what are the mistakes?

package a.b.c.service.orders;

import java.util.List;
import java.util.Map;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Component;
import org.springframework.transaction.annotation.Transactional;

import a.b.c.dao.OrderStatusesDao;
import a.b.c.model.OrderStatuses;

@Component
public class OrderStatusesService {
  @Autowired
  private OrderStatusesDao orderStatusesDao;

  private volatile Map<String, String> cached;

  @Transactional(rollbackFor = Exception.class, readOnly = true)
  public Map<String, String> getAllOrderStatuses() {
    if (null == cached) {
      synchronized (OrderStatusesService) {
        if (null == cached) {
          final List<OrderStatuses> orderStatuses = orderStatusesDao.getAll();

          cached = new HashMap<String, String>();
          for (OrderStatuses orderStatus : orderStatuses) {
            cached.put(orderStatus.getCode(), orderStatus.getName());
          }
        }
      }
    }

    return cached;
  }
}

Answer 1

This is not thread-safe, but it's close. The problem is that you add elements to the map after storing its reference in cached, making the incomplete map available to other callers until initialization is complete. The first step is to move the map building into a separate method.

private Map<String, String> loadAllOrderStatuses() {
  final List<OrderStatuses> orderStatuses = orderStatusesDao.getAll();
  final HashMap<String, String> result = new HashMap<String, String>();

  for (OrderStatuses orderStatus : orderStatuses) {
    result.put(orderStatus.getCode(), orderStatus.getName());
  }
  return result;
}

Returning the raw map to clients can also be dangerous since any caller is free to add elements to it which may or may not be seen by other threads or even corrupt the map's internal structure as viewed by other threads. If you do not control all callers of this method, you may wrap the result in an unmodifiable version at the end of the above method.

return Collections.unmodifiableMap(result);

With this, as long as you're running on Java 1.5+ where volatile is well-defined, it should be thread-safe. However, it can still be improved slightly. Volatile fields force a memory barrier on every access so it's better to write the computed value only once and minimize reads in the already-initialized code path. This can be done using a local variable as seen in the Effective Java Reloaded presentation linked by Banthar.

@Transactional(rollbackFor = Exception.class, readOnly = true)
public Map<String, String> getAllOrderStatuses() {
  Map<String, String> result = cached;
  if (null == result) {
    synchronized (this) {
      result = cached;
      if (null == result) {
        cached = result = loadAllOrderStatuses();
      }
    }
  }

  return result;
}

Finally, you're invoking the transaction advice on every call even though it's only needed on the first for initialization. You can avoid this by moving loadAllOrderStatuses along with @Transactional to a separate bean. There are other workarounds if this seems too much like overkill.

Answer 2

There are a few reasons why double-checked locking does not always work in Java. There are a number of blogs with more detail, but I quite like this one and this one.

Now, your code contains a volatile declaration for cached which, in certain conditions can mitigate the problem, but it is not a complete solution. You can still have cases where the cached variable is set in one thread, but another thread reads it before it is completely initialized. Since the values in the cached are not volatile, you will have problems still. Also, they depend on orderStatusesDao which is not volatile either...

With Java5's changes to the memory model, you can probably use a 'helper' variable to initialize the data... something like:

      Map<String,String> helper = new HashMap<String, String>();
      for (OrderStatuses orderStatus : orderStatuses) {
        helper.put(orderStatus.getCode(), orderStatus.getName());
      }
      cached = helper;

Using the helper ensures that the cached instance is fully assigned before it gets set.

This all seems very complicated.... and all to save a micro-synchronization.

With the advent of Java6 and enums, there are a few really good ways to create thread-safe lazy-initialized values, but your case is somewhat more complicated by the orderStatusesDao.getAll(); required for initialization.

As an 'aside' comment, I am concerned by this line:

synchronized (OrderStatusesService) { ...

The line suggests you have a variable called OrderStatusesService which is the exact same name as the class OrderStatusesService.... or is the synchronization supposed to be on OrderStatusesService.class?

In your case above, I would probably be satisfied with a simple/standard synchronization block and no volatile declaration. The lock-wait time will be very minimal.

Alternatively, I would consider an optimistic system using AtomicReferences, for example:

Map<String, String> cached = atomicref.get();
if (cached != null) {
    return cached;
}
cached = new HashMap....;
// populate cached.....
if (atomicref.compareAndSet(null, cached)) {
    // we were the first thread to populate, great:
    return cached;
}
// return the value that the winning thread created.
return atomicref.get();

in the above system, the first thread to 'set' the cached value will have it's instance used by every other thread. It is possible that multiple threads may be initializing their values at the same time, but they will all defer back to the winning-thread instance if they don't win. Once the instance is set, all threads will use that instance and there will be only fast atomic locking.