Thread-safe multiton pattern

Question

Inspired by a comment to an given answer I tried to create a thread-safe implementation of the multiton pattern, which relies on unique keys and performs locks on them (I have the idea from JB Nizet's answer on this question).

Question

Is the implementation I provided viable?

I'm not interested in whether Multiton (or Singleton) are in general good patterns, it would result in a discussion. I just want a clean and working implementation.

Contras:

• You have to know how many instances you want to create at compile time .

Pros

• No lock on whole class, or whole map. Concurrent calls to getInstanceare possible.
• Getting instances via key object, and not just unbounded int or String, so you can be sure to get an non-null instance after the method call.
• Thread-safe (at least that's my impression).

---

public class Multiton
{
  private static final Map<Enum<?>, Multiton> instances = new HashMap<Enum<?>, Multiton>();

  private Multiton() {System.out.println("Created instance."); }

  /* Can be called concurrently, since it only synchronizes on id */
  public static <KEY extends Enum<?> & MultitionKey> Multiton getInstance(KEY id)
  {
    synchronized (id)
    {
      if (instances.get(id) == null)
        instances.put(id, new Multiton());
    }
    System.out.println("Retrieved instance.");
    return instances.get(id);
  }

  public interface MultitionKey { /* */ }

  public static void main(String[] args) throws InterruptedException
  {
    //getInstance(Keys.KEY_1);
    getInstance(OtherKeys.KEY_A);

    Runnable r = new Runnable() {
      @Override
      public void run() { getInstance(Keys.KEY_1); }
    };

    int size = 100;
    List<Thread> threads = new ArrayList<Thread>();
    for (int i = 0; i < size; i++)
      threads.add(new Thread(r));

    for (Thread t : threads)
      t.start();

    for (Thread t : threads)
      t.join();
  }

  enum Keys implements MultitionKey
  {
    KEY_1;

    /* define more keys */
  }

  enum OtherKeys implements MultitionKey
  {
    KEY_A;

    /* define more keys */
  }
}

---

I tried to prevent the resizing of the map and the misuse of the enums I sychronize on. It's more of a proof of concept, before I can get it over with! :)

public class Multiton
{
  private static final Map<MultitionKey, Multiton> instances = new HashMap<MultitionKey, Multiton>((int) (Key.values().length/0.75f) + 1);
  private static final Map<Key, MultitionKey> keyMap;

  static
  {
    Map<Key, MultitionKey> map = new HashMap<Key, MultitionKey>();
    map.put(Key.KEY_1, Keys.KEY_1);
    map.put(Key.KEY_2, OtherKeys.KEY_A);
    keyMap = Collections.unmodifiableMap(map);
  }

  public enum Key {
    KEY_1, KEY_2;
  }

  private Multiton() {System.out.println("Created instance."); }

  /* Can be called concurrently, since it only synchronizes on KEY */
  public static <KEY extends Enum<?> & MultitionKey> Multiton getInstance(Key id)
  {
    @SuppressWarnings ("unchecked")
    KEY key = (KEY) keyMap.get(id);
    synchronized (keyMap.get(id))
    {
      if (instances.get(key) == null)
        instances.put(key, new Multiton());
    }
    System.out.println("Retrieved instance.");
    return instances.get(key);
  }

  private interface MultitionKey { /* */ }

  private enum Keys implements MultitionKey
  {
    KEY_1;

    /* define more keys */
  }

  private enum OtherKeys implements MultitionKey
  {
    KEY_A;

    /* define more keys */
  }
}

Answer 1

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.

Answer 2

I'd say not viable.

Synchronizing on the id parameter is fraught with dangers - what if they use this enum for another synchronization mechanism? And of course HashMap is not concurrent as the comments have pointed out.

To demonstrate - try this:

Runnable r = new Runnable() {
  @Override
  public void run() { 
    // Added to demonstrate the problem.
    synchronized(Keys.KEY_1) {
      getInstance(Keys.KEY_1);
    } 
  }
};

Here's an implementation that uses atomics instead of synchronization and therefore should be more efficient. It is much more complicated than yours but handling all of the edge cases in a Miltiton IS complicated.

public class Multiton {
  // The static instances.
  private static final AtomicReferenceArray<Multiton> instances = new AtomicReferenceArray<>(1000);

  // Ready for use - set to false while initialising.
  private final AtomicBoolean ready = new AtomicBoolean();
  // Everyone who is waiting for me to initialise.
  private final Queue<Thread> waiters = new ConcurrentLinkedQueue<>();
  // For logging (and a bit of linguistic fun).
  private final int forInstance;

  // We need a simple constructor.
  private Multiton(int forInstance) {
    this.forInstance = forInstance;
    log(forInstance, "New");
  }

  // The expensive initialiser.
  public void init() throws InterruptedException {
    log(forInstance, "Init");
    // ... presumably heavy stuff.
    Thread.sleep(1000);

    // We are now ready.
    ready();
  }

  private void ready() {
    log(forInstance, "Ready");
    // I am now ready.
    ready.getAndSet(true);
    // Unpark everyone waiting for me.
    for (Thread t : waiters) {
      LockSupport.unpark(t);
    }
  }

  // Get the instance for that one.
  public static Multiton getInstance(int which) throws InterruptedException {
    // One there already?
    Multiton it = instances.get(which);
    if (it == null) {
      // Lazy make.
      Multiton newIt = new Multiton(which);
      // Successful put?
      if (instances.compareAndSet(which, null, newIt)) {
        // Yes!
        it = newIt;
        // Initialise it.
        it.init();
      } else {
        // One appeared as if by magic (another thread got there first).
        it = instances.get(which);
        // Wait for it to finish initialisation.
        // Put me in its queue of waiters.
        it.waiters.add(Thread.currentThread());
        log(which, "Parking");
        while (!it.ready.get()) {
          // Park me.
          LockSupport.park();
        }
        // I'm not waiting any more.
        it.waiters.remove(Thread.currentThread());
        log(which, "Unparked");
      }
    }

    return it;
  }

  // Some simple logging.
  static void log(int which, String s) {
    log(new Date(), "Thread " + Thread.currentThread().getId() + " for Multiton " + which + " " + s);
  }
  static final DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
  // synchronized so I don't need to make the DateFormat ThreadLocal.

  static synchronized void log(Date d, String s) {
    System.out.println(dateFormat.format(d) + " " + s);
  }

  // The tester class.
  static class MultitonTester implements Runnable {
    int which;

    private MultitonTester(int which) {
      this.which = which;
    }

    @Override
    public void run() {
      try {
        Multiton.log(which, "Waiting");
        Multiton m = Multiton.getInstance(which);
        Multiton.log(which, "Got");
      } catch (InterruptedException ex) {
        Multiton.log(which, "Interrupted");
      }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    int testers = 50;
    int multitons = 50;
    // Do a number of them. Makes n testers for each Multiton.
    for (int i = 1; i < testers * multitons; i++) {
      // Which one to create.
      int which = i / testers;
      //System.out.println("Requesting Multiton " + i);
      new Thread(new MultitonTester(which+1)).start();
    }

  }
}

Answer 3

I'm not a Java programmer, but: HashMap is not safe for concurrent access. Might I recommend ConcurrentHashMap.

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

  public static <TYPE extends Object, KEY extends Enum<Keys> & MultitionKey<TYPE>> Multiton getInstance(KEY id)
  {
    Multiton result;
    synchronized (id)
    {
      result = instances.get(id);
      if(result == null)
      {
        result = new Multiton();
        instances.put(id, result);
      }
    }
    System.out.println("Retrieved instance.");
    return result;
  }