Tuesday 8 April 2008

Java: synchronizing on an ID

If you are a Java programmer, you will be familiar with synchronized blocks.
  Object myObject = //some instance
  synchronized(myObject) {
   //do some thread-sensitive
   //work on myObject
  }
Sometimes, you want to synchronize on a transient object - a resource that isn't going to stay in memory.

For example, there is nothing in the Servlet 2.5 MR6 specification that says a HttpServletSession instance can't be recreated as a facade object every time it is requested. That makes the session instance a poor candidate for a synchronized lock. There is nothing in the specification that prevents the container implementer from always serializing session attributes as soon as they are set either. That makes session attributes poor candidates for synchronization locks. Note: existing implementations may support either of these approaches in practice, but lets say our imaginary servlet container doesn't. However, the session ID will be consistent across requests.

The following code allows you to get an object to synchronize on based on a String ID. This allows a mutual exclusion lock (mutex).

import java.lang.ref.WeakReference;
import java.util.Map;
import java.util.WeakHashMap;

/**@author McDowell*/
public class IdMutexProvider {

  private final Map mutexMap = new WeakHashMap();
  
  /**Get a mutex object for the given (non-null) id.*/
  public Mutex getMutex(String id) {
    if(id==null) {
      throw new NullPointerException();
    }
    
    Mutex key = new MutexImpl(id);
    synchronized(mutexMap) {
      WeakReference ref = (WeakReferencemutexMap.get(key);
      if(ref==null) {
        mutexMap.put(key, new WeakReference(key));
        return key;
      }
      Mutex mutex = (Mutexref.get();
      if(mutex==null) {
        mutexMap.put(key, new WeakReference(key));
        return key;
      }
      return mutex;
    }
  }
  
  /**Get the number of mutex objects being held*/
  public int getMutexCount() {
    synchronized(mutexMap) {
      return mutexMap.size();
    }
  }
  
  public static interface Mutex {}
  
  private static class MutexImpl implements Mutex {
    private final String id;
    protected MutexImpl(String id) {
      this.id = id;
    }
    public boolean equals(Object o) {
      if(o==null) {
        return false;
      }
      if(this.getClass()==o.getClass()) {
        return this.id.equals(o.toString());
      }
      return false;
    }
    public int hashCode() {
      return id.hashCode();
    }
    public String toString() {
      return id;
    }
  }
  
}


This code isn't a panacea. Any code that requests a Mutex object will pass through the global synchronization block within the class. For trivial synchronization blocks, the cost of getting the object will outweigh locking on a global object.

Notes:
  • A WeakHashMap is used to reference the Mutex instances. This avoids the need to release the object - the garbage collector will get rid of it as long as you don't keep a hard reference to it.
  • The WeakHashMap values have hard references, so the Mutex value is wrapped in a WeakReference.


Usage

      String id = sharedObject.getId();
      IdMutexProvider.Mutex mutex = MUTEX_PROVIDER.getMutex(id);
      synchronized(mutex) {
        //do some thread-sensitive
        //work with sharedObject
      }


One IdMutexProvider instance should be created per domain to avoid ID collisions. That is, you shouldn't use the same instance to lock sessions as you would to lock access to files, for example.

JUnit tests

import junit.framework.TestCase;

// JUnit 3
public class IdMutexProviderTest extends TestCase {

  public void testNPE() {
    IdMutexProvider imp = new IdMutexProvider();
    try {
      imp.getMutex(null);
      fail("Did not throw NullPointerException");
    catch (NullPointerException e) {
    }
  }

  public void testSynchObject() {
    IdMutexProvider imp = new IdMutexProvider();
    // an id
    String id1a = "id1";
    // same id value; different key instance
    String id1b = new String(id1a);
    // a different id
    String id2 = "id2";

    // assert inequality of String id reference values
    assertFalse(id1a == id1b);
    assertFalse(id1a == id2);

    IdMutexProvider.Mutex m1a = imp.getMutex(id1a);
    System.out.println(m1a);
    assertNotNull(m1a);
    assertTrue(imp.getMutexCount() == 1);

    IdMutexProvider.Mutex m1b = imp.getMutex(id1b);
    System.out.println(m1b);
    assertNotNull(m1b);
    assertTrue(m1a == m1b);
    assertTrue(imp.getMutexCount() == 1);

    IdMutexProvider.Mutex m2 = imp.getMutex(id2);
    System.out.println(m2);
    assertNotNull(m2);
    assertTrue(imp.getMutexCount() == 2);
    assertFalse(m2 == m1a);
  }

  public void testForMemoryLeak() {
    System.out.println("Testing for memory leaks; wait...");

    IdMutexProvider imp = new IdMutexProvider();

    int creationCount = 0;
    while (true) {
      if (creationCount == Integer.MAX_VALUE) {
        fail("Memory leak");
      }

      creationCount++;
      imp.getMutex("" + creationCount);
      if (imp.getMutexCount() < creationCount) {
        // then some garbage collection has
        // removed entries from the map
        break;
      }

      // encourage the garbage collector
      if (creationCount % 10000 == 0) {
        System.out.println(creationCount);
        System.gc();
        try {
          Thread.sleep(5000);
        catch (InterruptedException e) {
        }
      }
    }
  }

}


Java 1.5 (or Java 5 if you prefer) includes a lot of helper classes to aid concurrency. As you can probably tell by all the casts, this was written using Java(2) 1.4.

6 comments:

  1. This only works because id1a==id1b (Strings are immutable). If you change your implementation from String to StringBuffer (i.e. public Mutex getMutex(String id)), then it will fail.

    ReplyDelete
  2. Are you talking about changing IdMutexProvider.getMutex(String) to IdMutexProvider.getMutex(StringBuffer)? Yes, this would be a bad idea. The implementation is dependent on the argument being a String.

    ReplyDelete
  3. I maybe missed the point of this bit:

    Anonymous wrote: "This only works because id1a==id1b (Strings are immutable)."

    Actually, in the test method testSynchObject() id1a!=id1b because they refer to different instances (though id1a.equals(id1b) returns true). Note the use of the "new" operator when assigning id1b.

    I will update the test with this assertion.

    ReplyDelete
  4. I seem to recall trying to synchronize based on .equals rather than == in java because I wished the scope of the mutext to be based on a "combined key". If I recall correctly, the WeakHashMap was not suitable because the keys had weak references when one needed the soft references to the values to get the desired behavior. Apache collections had a Map implementation that allowed you to specify whether you wanted hard, soft, weak references on both keys and values. Hard keys and Soft values seemed to be the one that passed the unit tests.

    - OneFactory

    ReplyDelete
  5. This post is nearly 5 years old at this point, but I thought I'd chime in with my experiences using the example.

    Under load we found that the "synchronized(mutexMap)" portion of getMutex was too much of a bottle neck. There is likely a way to optimize this code, but we ended up going another direction and placing a single mutex in a context object.

    ReplyDelete

All comments are moderated