Synchronizing on an id with removal

Question

I need to ensure that multiple threads aren't trying to access the same resource at the same time. I have a bunch of these resources, so I want to have a separate lock object for each resource (rather than one global lock) so that threads aren't unnecessarily blocking eachother.

Eddie presents a great solution for this using ConcurrentMap.putIfAbsent() in https://stackoverflow.com/a/659939/82156.

// From https://stackoverflow.com/a/659939/82156
public Page getPage(Integer id) {
  Page p = cache.get(id);
  if (p == null) {
    synchronized (getCacheSyncObject(id)) {
      p = getFromDataBase(id);
      cache.store(p);
    }
  }
}

private ConcurrentMap<Integer, Integer> locks = new ConcurrentHashMap<Integer, Integer>();

private Object getCacheSyncObject(final Integer id) {
  locks.putIfAbsent(id, id);
  return locks.get(id);
}

However, one problem with that implementation is that the hashmap will grow unbounded. Is there a way to remove the hash key when the thread is complete without screwing up the concurrency?

The lock map will be way smaller than the actual cache. Is there a mechanism in place to clean the cache? If so, it should probably clean the lock map too. — flup, Apr 01 '13 at 22:42

Pyrce · Answer 1 · 2013-04-01T23:58:35.620

If you know that a particular thread is the last thread to request a specific lock, then you can just use locks.remove(id, id). Otherwise you need an atomic update on two events which can't be easily synchronized together.

If you release and then remove a lock another thread could grab that lock you released while an additional thread makes a new lock object oblivious to the original lock object. In this situation you could end up with two threads calling getFromDataBase(id) or cache.store(p) simultaneously. If you remove and then release instead you could have had another thread waiting for you to release the old lock while a new thread has already made a new lock. The same collision could occur.

Essentially you can't atomically release a lock and remove it from the HashMap without adding a new lock to the system. In this case you either end up with a global lock -- which defeats the speed-up of hash specific locking -- or you need an additional lock for each page which itself would have the same removal problems. Alternatively if you had access to the HashMap's internals you could try some tricky bucket lock exposure to your higher level logic, though I would not recommend trying to implement such a thing.

One solution to limiting the size of the hashmap is to use a fixed size mapping instead. Mod your Integer id with a large number (10,000) and use the modded number as a unique lock id. The probability of two hashes colliding and requiring the same lock for different pages would be very small and you'd have a hard cap on the memory that is consumed by the locks. In this case you actually don't need a HashMap as you could pre-allocate the Integer lock objects into a static const array and request the mod hash directly from the id objects.

Also you should be careful doing the cache reads outside of a lock unless the cache itself is protected from simultaneous read-writes as a thread could be writing while another reads from the way the code is specified in the question.

+1 for the suggestion to mod the id into a fixed size integer list. You might occasionally mod two distinct resources onto the same lock, but that's okay for my purposes. — emmby, Apr 03 '13 at 18:19

score 1 · Accepted Answer · answered Apr 04 '13 at 01:00

Pyrce made me realize that it wasn't required that every resource have its own lock object. Rather, I could use a pool of, say, 100 lock objects that could be shared between the resources. That way, the set of lock objects wouldn't grow unbounded, but I'd still get most of the concurrency benefits I was hoping to get by removing the single global lock.

This meant that I no longer needed to use a ConcurrentHashMap and could instead just use a simple array that was eagerly initialized.

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

private int MAX_LOCKS = 100;
private Object[] locks = new Object[MAX_LOCKS];

{
    for(int i=0; i<locks.length; ++i)
        locks[i] = new Object();
}


private Object getCacheSyncObject(final Integer id) {  
  return locks[ id % MAX_LOCKS ];
}

Synchronizing on an id with removal

2 Answers2