per-key lock other than whole map lock in HashMap

Question

I have a large map=ConcurrentHashMap() in Java while Key, Value are some kind of Object structure. Suppose the key's set of this map is keySet.

Now I have a calculation procedure below. My question is how can I get a better performance by not using whole map lock. Are there any options like using per-key lock or using some other kind of data structures?

Considering this is a large map, using a every-key lock may not be an acceptable approach.

multiThread():
    for(0 to N):
        K = subset(keySet, m) where m is much smaller than keySet.size
        lock(map)
        for(key in K):
            result = func1(map.get(key), result)
        for(key in K):
            map.put(key, func2(map.get(key), result))
        releaseLock(map)

radai radai · Accepted Answer · 2015-02-12T03:56:14

in java 8+ ConcurrentHashMap as a compute() function that allows you to do atomic read-modify-write operation on a single key, so you could do something like:

map.compute(key, () -> {
    //call func2 to compute new value and return it
});

if, however, you want atomic read-modify-write for the entire set of keys (so 1st you iterate over your set of keys to compute result and then change all those keys using that pre-computed result) then there's no facility in ConcurrentHashMap to provide that locking.

you could, however, use guava's Striped lock, like so:

Striped<Lock> arrayOfLocks = Striped.lock(20);
// ...later on...
K = subset(keySet, m);
Iterable<Lock> toObtain = arrayOfLocks.bulkGet(K);
for (Lock l : toObtain) { lock it }
try {
   //do your modifications - your holding the stripe locks for all the keys
} finally {
   for (Lock l : toObtain) { unlock it }
}

lock striping is the concept of assigning locks to different "area"s of a data structure - here its done by the hashCode of your keys.

you need to pick the size of the lock array very carefully to balance between too-few stripes (where you'll lock the whole map and do it slower than a single global lock) and too-many stripes (where you'll be grabbing a lot of locks, depending onthe size of K).

Striped takes care of returning the locks in the same order for the same set of keys to lock so that you avoid the dining philosophers problem.

per-key lock other than whole map lock in HashMap

1 Answers