Synchronizing on an Integer value [duplicate]

Question

Possible Duplicate:
What is the best way to increase number of locks in java

Suppose I want to lock based on an integer id value. In this case, there's a function that pulls a value from a cache and does a fairly expensive retrieve/store into the cache if the value isn't there.

The existing code isn't synchronized and could potentially trigger multiple retrieve/store operations:

//psuedocode
public Page getPage (Integer id){
   Page p = cache.get(id);
   if (p==null)
   {
      p=getFromDataBase(id);
      cache.store(p);
   }
}

What I'd like to do is synchronize the retrieve on the id, e.g.

   if (p==null)
   {
       synchronized (id)
       {
        ..retrieve, store
       }
   }

Unfortunately this won't work because 2 separate calls can have the same Integer id value but a different Integer object, so they won't share the lock, and no synchronization will happen.

Is there a simple way of insuring that you have the same Integer instance? For example, will this work:

 syncrhonized (Integer.valueOf(id.intValue())){

The javadoc for Integer.valueOf() seems to imply that you're likely to get the same instance, but that doesn't look like a guarantee:

Returns a Integer instance representing the specified int value. If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values.

So, any suggestions on how to get an Integer instance that's guaranteed to be the same, other than the more elaborate solutions like keeping a WeakHashMap of Lock objects keyed to the int? (nothing wrong with that, it just seems like there must be an obvious one-liner than I'm missing).

Answer 1

Integer.valueOf() only returns cached instances for a limited range. You haven't specified your range, but in general, this won't work.

However, I would strongly recommend you not take this approach, even if your values are in the correct range. Since these cached Integer instances are available to any code, you can't fully control the synchronization, which could lead to a deadlock. This is the same problem people have trying to lock on the result of String.intern().

The best lock is a private variable. Since only your code can reference it, you can guarantee that no deadlocks will occur.

By the way, using a WeakHashMap won't work either. If the instance serving as the key is unreferenced, it will be garbage collected. And if it is strongly referenced, you could use it directly.

Answer 2

Use a thread-safe map, such as ConcurrentHashMap. This will allow you to manipulate a map safely, but use a different lock to do the real computation. In this way you can have multiple computations running simultaneous with a single map.

Use ConcurrentMap.putIfAbsent, but instead of placing the actual value, use a Future with computationally-light construction instead. Possibly the FutureTask implementation. Run the computation and then get the result, which will thread-safely block until done.

Answer 3

You could have a look at this code for creating a mutex from an ID. The code was written for String IDs, but could easily be edited for Integer objects.

Answer 4

See section 5.6 in Java Concurrency in Practice: "Building an efficient, scalable, result cache". It deals with the exact issue you are trying to solve. In particular, check out the memoizer pattern.

alt text http://www.cs.umd.edu/class/fall2008/cmsc433/jcipMed.jpg

Answer 5

Steve,

your proposed code has a bunch of problems with synchronization. (Antonio's does as well).

To summarize:

1. You need to cache an expensive object.
2. You need to make sure that while one thread is doing the retrieval, another thread does not also attempt to retrieve the same object.
3. That for n-threads all attempting to get the object only 1 object is ever retrieved and returned.
4. That for threads requesting different objects that they do not contend with each other.

pseudo code to make this happen (using a ConcurrentHashMap as the cache):

ConcurrentMap<Integer, java.util.concurrent.Future<Page>> cache = new ConcurrentHashMap<Integer, java.util.concurrent.Future<Page>>;

public Page getPage(Integer id) {
    Future<Page> myFuture = new Future<Page>();
    cache.putIfAbsent(id, myFuture);
    Future<Page> actualFuture = cache.get(id);
    if ( actualFuture == myFuture ) {
        // I am the first w00t!
        Page page = getFromDataBase(id);
        myFuture.set(page);
    }
    return actualFuture.get();
}

Note:

1. java.util.concurrent.Future is an interface
2. java.util.concurrent.Future does not actually have a set() but look at the existing classes that implement Future to understand how to implement your own Future (Or use FutureTask)
3. Pushing the actual retrieval to a worker thread will almost certainly be a good idea.

Answer 6

As you can see from the variety of answers, there are various ways to skin this cat:

• Goetz et al's approach of keeping a cache of FutureTasks works quite well in situations like this where you're "caching something anyway" so don't mind building up a map of FutureTask objects (and if you did mind the map growing, at least it's easy to make pruning it concurrent)
• As a general answer to "how to lock on ID", the approach outlined by Antonio has the advantage that it's obvious when the map of locks is added to/removed from.

You may need to watch out for a potential issue with Antonio's implementation, namely that the notifyAll() will wake up threads waiting on all IDs when one of them becomes available, which may not scale very well under high contention. In principle, I think you can fix that by having a Condition object for each currently locked ID, which is then the thing that you await/signal. Of course, if in practice there's rarely more than one ID being waited on at any given time, then this isn't an issue.