Synchronize access to given key in a ConcurrentMap

Question

I often enough want to access (and possibly add/remove) elements of a given ConcurrentMap so that only one thread can access any single key at a time. What is the best way to do this? Synchronizing on the key itself doesn't work: other threads might access the same key via an equal instance.

It's good enough if the answer only works with the maps built by guava MapMaker.

Indeed I'm wondering why Maps don't have method `getKey(key)` which returns key instance. — Sergey Aslanov, Jul 20 '11 at 07:54
Are you saying you want to synchronise access within the `ConcurrentMap` during lookups (which doesn't quite make sense to me) or after the fact, once the value has been sourced from the map? — Drew Noakes, Jul 20 '11 at 07:57
@JustYo if you have an equal key instance, why would you need the instance in the map? If that key would be mutable I'd doubt the design choice to use that key here. — Thomas, Jul 20 '11 at 08:01
@Thomas having such method will solve task of synchronizing by key. That won't work with equal but different instance. — Sergey Aslanov, Jul 20 '11 at 08:03
@JustYo So why would one want to synchronize on the key? I can think of 2 situations: 1. prevent concurrent access to the value -> synchronize on the value. 2. the value might be changed/replaced causing a "dirty read" like situation -> add a level of indirection (e.g. a value holder) and synchronize on that. — Thomas, Jul 20 '11 at 08:13
@Thomas Option 2 won't help when you want to remove the value instead of replacing it. Of course, it's possible to add an "empty" state to the value holder... — Alexey Romanov, Jul 20 '11 at 11:21

score 3 · Accepted Answer · edited May 23 '17 at 11:55

3

See a simple solution here Simple Java name based locks?

EDIT: This solution has a clear happens-before relation from unlock to lock. However, the next solution, now withdrawn, doesn't. The ConcurrentMap javadoc is too light to guaranteed that.

(Withdrawn) If you want to reuse your map as a lock pool,

private final V LOCK = ...; // a fake value
// if a key is mapped to LOCK, that means the key is locked
ConcurrentMap<K,V> map = ...;

V lock(key)
    V value;  
    while( (value=map.putIfAbsent(key, LOCK))==LOCK )
        // another thread locked it before me
        wait();
    // now putIfAbsent() returns a real value, or null
    // and I just sucessfully put LOCK in it
    // I am now the lock owner of this key
    return value; // for caller to work on

// only the lock owner of the key should call this method
unlock(key, value)
    // I put a LOCK on the key to stall others
    // now I just need to swap it back with the real value
    if(value!=null) 
        map.put(key, value);
    else // map doesn't accept null value
        map.remove(key)
    notifyAll();

test()
    V value = lock(key);

    // work on value

    // unlock. 
    // we have a chance to specify a new value here for the next worker
    newValue = ...; // null if we want to remove the key from map
    unlock(key, newValue); // in finally{}

This is quite messy because we reuse the map for two difference purposes. It's better to have lock pool as a separate data structure, leave map simply as the k-v storage.

edited May 23 '17 at 11:55

Community

1
1

answered Jul 20 '11 at 12:51

irreputable

44,725
9
65
93

I prefer sjr's answer to the linked question to the accepted one. – Alexey Romanov Jul 20 '11 at 13:56
Why? Of course, values need to be weak, so if nobody needs a lock right now, entries will be evicted from the lock map. – Alexey Romanov Jul 20 '11 at 15:03
you still have the key->weakReference entry in the map – irreputable Jul 20 '11 at 23:29
"it is possible for a key or value present in the the map to be reclaimed by the garbage collector. _If this happens, the entry automatically disappears from the map._" If I don't have a reference to the key any longer, I certainly won't have a reference to the value (which is only accessed through the map) and the corresponding entry will be garbage-collected. – Alexey Romanov Jul 21 '11 at 05:24
I see. I was not familiar with MapMaker. But if the lock object can disappear then get recreated, different threads may `synchronize` on different objects, and happens-before relation may not hold – irreputable Jul 21 '11 at 07:12
`makeComputingMap` ensures that when several threads try to create a value for a key which doesn't exist in the map, only one value is created. And of course, the lock can only disappear while nobody is synchronizing on it. – Alexey Romanov Jul 21 '11 at 08:52
The problem is happens-before relation from unlock action to next lock action. with `synchronized(getLock(key)){...}`, if returned lock changes, we'll have visibility issues. This prompts me to reexamine my solution with ConcurrentMap. Too bad the javadoc of it just doesn't make enough guarantees so that my unlock-lock has happens-before relation. Neither is ConcurrentHashMap. We could dig into the implementation to argue about synchronization behaviors; but just based on public javadoc, my solution cannot guarantee happens-before, so I have to withdraw it too. – irreputable Jul 21 '11 at 09:17

Anton Fil · Answer 2 · 2019-02-14T11:33:58.803

    private static final Set<String> lockedKeys = new HashSet<>();

    private void lock(String key) throws InterruptedException {
        synchronized (lockedKeys) {
            while (!lockedKeys.add(key)) {
                lockedKeys.wait();
            }
        }
    }

    private void unlock(String key) {
        synchronized (lockedKeys) {
            lockedKeys.remove(key);
            lockedKeys.notifyAll();
        }
    }

    public void doSynchronouslyOnlyForEqualKeys(String key) throws InterruptedException {
        try {
            lock(key);

            //Put your code here.
            //For different keys it is executed in parallel.
            //For equal keys it is executed synchronously.

        } finally {
            unlock(key);
        }
    }

key can be not only a 'String' but any class with correctly overridden 'equals' and 'hashCode' methods.
try-finally - is very important - you must guarantee to unlock waiting threads after your operation even if your operation threw exception.
It will not work if your back-end is distributed across multiple servers/JVMs.

score 0 · Answer 3 · answered Jul 20 '11 at 08:20

Can't you just create you own class that extends concurrentmap. Override the get(Object key) method, so it checks if the requested key object is already 'checked out' by another thread ?

You'll also have to make a new method in your concurrentmap that 'returns' the items to the map, so they are available again to another thread.

Synchronize access to given key in a ConcurrentMap

3 Answers3