Implementing per-key or striped locking in a Map - best approach?

Question

I came across this dilemma at work and wanted to see if there is a better solution... it feels like there should be an easier, cleaner answer.

Goal: Concurrently access a map with locks at the key level, not at the entire map level, to ensure atomicity while impacting performance as little as possible.

I have a Map which needs to be concurrent. *(Added) The map will be filled with an unknown amount of entries over time. I have multiple readers and a single writer. The writer does a "check-then-put" and the reader does a simple get(). I need these to be atomic... but only at the key level. So for example, if the reader is checking for Key X, and the writer is writing to Key Y, I don't care if I miss the write to Key Y. If the reader/writer is working on the same key however I need that to be atomic.

The easiest solution is to lock the whole map. But this seems like it would impact performance, since there are about 10,000 keys that will end up in the map. (If that doesn't seem like it would hurt performance because the size of the Map is relatively small, let's pretend the Map has many more keys, for arguments sake.)

As far as I know, ConcurrentHashMap will not guarantee the "per-key" atomic behavior I need.

The next solution that came to mind was to have an array of lock objects. You would index into that array of lock Object()'s based on a hash of the original key. This would still have some contention since you have less locks than you have keys into the original map. I'm aware that ConcurrentHashMap does a similar thing under the hood (striping) to provide concurrency (but not atomicity).

Is there an easier way to perform this type of per-key or striped locking?

Thanks.

Are all possible keys known ahead of time? If so, you could allocate one lock object for every key before spawning the readers and writers. — Adam Bliss, Jan 13 '14 at 02:15
@AdamBliss We don't know all the keys ahead of time. Also, if I could avoid maintaining my own Map of lock objects, that would be an ideal solution. — Bryan, Jan 13 '14 at 02:23
_Exactly_ which operations do you need to be atomic per-key? `ConcurrentHashMap` should do the right thing here. e.g. `ConcurrentHashMap.put` is atomic. — Louis Wasserman, Jan 13 '14 at 02:35
@LouisWasserman The putting and the getting are all I am focusing on. For the put, I am doing a check-then-put, so it's not solely a call to put(). Perhaps ConcurrentHashMap can do this for me with putIfAbsent()? — Bryan, Jan 13 '14 at 02:44

score 1 · Answer 1 · answered Jan 13 '14 at 02:38

This concern can come up when value generation is a time-consuming process. You don't want to lock the whole map and find a missing value, and keep the map locked while you generate the value. You could release the map during generation, but then you could have two simultaneous misses and generations.

Instead of directly storing the value with the key, store it inside a reference object:

public class Ref<T>
{
    private T value;

    public T getValue()
    {
        return value;
    }

    public void setValue(T value)
    {
        this.value = value;
    }
}

So if you originally had a map of Map<String, MyThing>, you instead use Map<String, Ref<MyThing>>. Don't bother with a concurrent implementation, just use HashMap or LinkedHashMap or whatever.

Now you can lock the map to find or create a reference holder, and then release the map. Following that, you can lock the reference to find or create the value object:

String key; // key you're looking up
Map<String, Ref<MyThing>> map; // the map

// Find the reference container, create it if necessary
Ref<MyThing> ref;
synchronized(map)
{
    ref = map.get(key);
    if (ref == null)
    {
        ref = new Ref<MyThing>();
        map.put(key, ref);
    }
}

// Map is released at this point

// Now get the value, creating if necessary
MyThing result;
synchronized(ref)
{
    result = ref.getValue();
    if (result == null)
    {
        result = generateMyThing();
        ref.setValue(result);
    }
}

// result == your existing or new object

Implementing per-key or striped locking in a Map - best approach?

1 Answers1