[concurrency-interest] Problem with using an unbounded map of Mutex lock objects

Brian Goetz brian at quiotix.com
Fri Jun 2 18:31:32 EDT 2006


> That sounds good. I don't have a copy of JCiP so I bought one :) from 
> Amazon. 

Guess all that "Jedi mind trick" practice is paying off :)

> It will arrive between June 21 and July 3. I would appreciate 
> any online or email stuff on lock striping in the meantime. 

Hashtable / synchronizedMap uses the "one big fat lock" approach to 
guard the mutable state of the map.  That works, but is a big 
concurrency bottleneck, as you've observed.  You went to the opposite 
extreme, one lock per key.  That works (as long as you've got sufficient 
synchronization in the cache itself to protect its own data structures.)

Lock striping is a middle ground, partitioning keys into a fixed number 
of subsets, like the trick used at large theaters for will-call ticket 
pickup -- there are separate lines for "A-F, G-M, N-R, and S-Z".  This 
way, there are a fixed number of locks, each guarding (hopefully) 1/Nth 
of the keys.

You could use striping in your example:

   Lock[] locks = new Lock[N];
   /* intializer block */ {
     for (i=0; i<N; i++)
         locks[i] = new ReentrantLock();
   }

and

private synchronized Mutex getLockForKey(final Serializable key) {
     int h = key.hashCode() % N;
     if (h < 0)
         h += N;
     return locks[h];
}

This way, 1/Nth of the keys are guarded by locks[0], 1/Nth by locks[1], 
etc.  Concurrency can be tuned by choosing N; we found 16 works well on 
systems with fewer than a few dozen processors.


More information about the Concurrency-interest mailing list