Thread Safe Multitons in Java

Thread safe multitons in Java

This will provide you a threadsafe storage mechanism for your Multitons. The only downside is that it is possible to create a Multiton that will not be used in the putIfAbsent() call. The possibility is small but it does exist. Of course on the remote chance it does happen, it still causes no harm.

On the plus side, there is no preallocation or initialization required and no predefined size restrictions.

private static ConcurrentHashMap<Integer, Multiton> instances = new ConcurrentHashMap<Integer, Multiton>();

public static Multiton getInstance(int which) 
{
    Multiton result = instances.get(which);

    if (result == null) 
    {
        Multiton m = new Multiton(...);
        result = instances.putIfAbsent(which, m);

        if (result == null)
            result = m;
    }

    return result;
}

Thread-safe multiton pattern

It is absolutely not thread-safe. Here is a simple example of the many, many things that could go wrong.

Thread A is trying to put at key id1. Thread B is resizing the buckets table due to a put at id2. Because these have different synchronization monitors, they're off to the races in parallel.

Thread A                      Thread B
--------                      --------
b = key.hash % map.buckets.size   

                             copy map.buckets reference to local var
                             set map.buckets = new Bucket[newSize]
                             insert keys from old buckets into new buckets

insert into map.buckets[b]

In this example, let's say Thread A saw the map.buckets = new Bucket[newSize] modification. It's not guaranteed to (since there's no happens-before edge), but it may. In that case, it'll be inserting the (key, value) pair into the wrong bucket. Nobody will ever find it.

As a slight variant, if Thread A copied the map.buckets reference to a local var and did all its work on that, then it'd be inserting into the right bucket, but the wrong buckets table; it wouldn't be inserting into the new one that Thread B is about to install as the table for everyone to see. If the next operation on key 1 happens to see the new table (again, not guaranteed to but it may), then it won't see Thread A's actions because they were done on a long-forgotten buckets array.

Thread Safe Singletons in Java

Answer 1: static synchronized methods use the class object as the lock - ie in this case Singleton.class.

Answer 2: The java language, among other things:

• loads classes when they are first accessed/used
• guarantees that before access to a class is allowed, all static initializers have completed

These two facts mean that the inner static class SingletonHolder is not loaded until the getInstance() method is called. At that moment, and before the thread making the call is given access to it, the static instance of that class is instantiated as part of class loading.

This all means we have safe lazy loading, and without any need for synchronization/locks!

This pattern is the pattern to use for singletons. It beats other patterns because MyClass.getInstance() is the defacto industry standard for singletons - everyone who uses it automatically knows that they are dealing with a singleton (with code, it's always good to be obvious), so this pattern has the right API and the right implementation under the hood.

btw Bill Pugh's article is worth reading for completeness when understanding singleton patterns.

Thread-safe Map in Java

For tasks of this nature, I highly recommend Guava caching support.

If you can't use that library, here is a compact implementation of a Multiton. Use of the FutureTask was a tip from assylias, here, via OldCurmudgeon.

public abstract class Cache<K, V>
{

  private final ConcurrentMap<K, Future<V>> cache = new ConcurrentHashMap<>();

  public final V get(K key)
    throws InterruptedException, ExecutionException
  {
    Future<V> ref = cache.get(key);
    if (ref == null) {
      FutureTask<V> task = new FutureTask<>(new Factory(key));
      ref = cache.putIfAbsent(key, task);
      if (ref == null) {
        task.run();
        ref = task;
      }
    }
    return ref.get();
  }

  protected abstract V create(K key)
    throws Exception;

  private final class Factory
    implements Callable<V>
  {

    private final K key;

    Factory(K key)
    {
      this.key = key;
    }

    @Override
    public V call()
      throws Exception
    {
      return create(key);
    }

  }

}

Proving the following code not thread safe

Well... The result of this code will be false, where you expect for a true.

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

public class LazyInitRace {

    public class ExpensiveObject {
        public ExpensiveObject() {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            }
        }
    }

    private ExpensiveObject instance = null;

    public ExpensiveObject getInstance() {
        if (instance == null)
            instance = new ExpensiveObject();
        return instance;
    }

    public static void main(String[] args) {
        final LazyInitRace lazyInitRace = new LazyInitRace();

        FutureTask<ExpensiveObject> target1 = new FutureTask<ExpensiveObject>(
                new Callable<ExpensiveObject>() {

                    @Override
                    public ExpensiveObject call() throws Exception {
                        return lazyInitRace.getInstance();
                    }
                });
        new Thread(target1).start();

        FutureTask<ExpensiveObject> target2 = new FutureTask<ExpensiveObject>(
                new Callable<ExpensiveObject>() {

                    @Override
                    public ExpensiveObject call() throws Exception {
                        return lazyInitRace.getInstance();
                    }
                });
        new Thread(target2).start();

        try {
            System.out.println(target1.get() == target2.get());
        } catch (InterruptedException e) {
        } catch (ExecutionException e) {
        }
    }
}

Is this a lazy thread safe Generic multiton?

Dictionary class is not thread-safe, you can use ConcurrentDictionary to atomically check if element is in dictionary and add/get value from dictionary:

public sealed class Multiton<T> where T : class, new() {
    private static readonly ConcurrentDictionary<object, Lazy<T>> _instances = new ConcurrentDictionary<object, Lazy<T>>();

    public static T GetInstance(object key) {
        Lazy<T> instance = _instances.GetOrAdd(key, k => new Lazy<T>(() => new T()));
        return instance.Value;
    }

    private Multiton() {
    }
}

Java Concurrency

Java 8:

private final Map<String, AtomicInteger> cnts =
        new ConcurrentHashMap<>();

private void accumulate(String name) {
    cnts.computeIfAbsent(name, k -> new AtomicInteger()).incrementAndGet();
}

The ConcurrentHashMap can be freely accessed from multiple threads. The computeIfAbsent method takes a lambda to evaluate to get a value for the key if the key is not present in the map, and adds it if and only if there is no such mapping, and then returns that value. It's effectively putIfAbsent followed by get. The value is a new AtomicInteger with the value 0. Whether there was an existing value, or whether a new one with value 0 was just added, in either case increment it.

Java 7:

private final ConcurrentMap<String, AtomicInteger> cnts =
        new ConcurrentHashMap<>();

private void accumulate(String name) {
    cnts.putIfAbsent(name, new AtomicInteger());
    cnts.get(name).incrementAndGet();
}

For Java 7, there is no computeIfAbsent method, but that effectively just does a putIfAbsent followed by a get, so the same effect is achieved by calling those methods. There is no concern that the value already existed in the map; a new, zero AtomicInteger is added if and only if the map had no value for that key. Even if another thread got in there before us and added a zero, both threads would then see and increment that same AtomicInteger instance.

When to use proper version of singleton thread-safe implementation?

If your class is entirely stateless - make it a util class with only static functions.

If you have state and want a semi-singleton I would say that what you have done is misleading since there is no way for the reader to know if you were aware of the fact that you can get multiple instances or not. If you decide to stick with your posted code - rename it multiton or document the behaviour carefully. But don't do it just to reduce boilerplate though - you are in fact creating more problems for the reader than you are removing.

In my opinion the "Initialization on Demand Holder" idiom is the nicest singleton pattern. But I would recommend against Singletons in general. You would be better off passing a reference to a shared instance to your thread when you start it.

---

Related Topics