Simple Java Name Based Locks

Simple Java name based locks?

maybe this is useful for you: jkeylockmanager

Edit:

My initial response was probably a bit short. I am the author and was faced with this problem several times and could not find an existing solution. That's why I made this small library on Google Code.

How to acquire a lock by a key

Guava has something like this being released in 13.0; you can get it out of HEAD if you like.

Striped<Lock> more or less allocates a specific number of locks, and then assigns strings to locks based on their hash code. The API looks more or less like

Striped<Lock> locks = Striped.lock(stripes);
Lock l = locks.get(string);
l.lock();
try {
  // do stuff 
} finally {
  l.unlock();
}

More or less, the controllable number of stripes lets you trade concurrency against memory usage, because allocating a full lock for each string key can get expensive; essentially, you only get lock contention when you get hash collisions, which are (predictably) rare.

(Disclosure: I contribute to Guava.)

Java synchronizing based on a parameter (named mutex/lock)

Use a map to associate strings with lock objects:

Map<String, Object> locks = new HashMap<String, Object>();
locks.put("a", new Object());
locks.put("b", new Object());
// etc.

then:

public void doSomething(String name){
    synchronized(locks.get(name)) {
        // ...
    }
}

Synchronized lock by particular ID

It seems like a bad idea because:

String#intern() is a native method and it uses native Hash Table which apparently is much slower than a typical ConcurrentHashMap.
You probably don't want the pool of strings to grow indefinitely. How would you invalidate entries from there?

I think using your own map of strings will be the preferred way. Maybe Guava's cache could be leveraged because you need to evict items from that map eventually. But this needs further research.

Leasing a lock

Another option is to have a set of predefined lock objects. E.g. a HashMap of size 513. Then to acquire a lock use bid.hashCode() mod 513:

int hash = Math.abs(bid.hashCode() % 513);
Object lock = locks.get(hash);
synchronized(lock) {...}

This will occasionally lock unrelated transactions, but at least you don't have to bother with eviction.

PS: there was some method to calculate a true mod in Math class.

Name based Reentrant Lock in Java

Simply put, ReentrantLock is not for you. The subject acquring the lock is a thread, so when you attempt to release it in another thread, that thread is actually trying to release a lock it doesn't own. Meanwhile the thread that did acquire it, keeps holding on to it.

What you probably need instead is a Semaphore—more specifically, a collection of semaphores, one for each color group.

User level Locking Approach With synchronizedMap & ReentrantLock

The deadlock spawns from the interaction of your map, and the locks.

More precisely : you use a Collections.syncrhonized map, which in effect, puts a mutual exclusion on every (or so) method of the orignal map instance.

That means, for example, that as long as someone is inside a computeIfAbsent (or computeIfPresent) call, then no other method can be called on the map instance.

Up to this point no problem.

Except that, inside the computeIfxx calls, you do another locking operation, by acquiring lock instances.

Having two different locks AND not maintaining a strict lock acquisition order is the perfect recipe to deadlock, which you demonstrate here.

A sample chronology :

Thread T1 enters the Map (acquires the lock M), creates a Lock L1 and acquires it. T1 holds M and L1.
Thread T1 exists the map.computeXX, releasing M. T1 holds L1 (only).
Thread T2 enters the map (acquires M). T1 holds L1, T2 holds M.
Thread T2 tries to acquire L1 (the same one as T1), is blocked by T1. T1 holds L1, T2 holds M and waits for L1. Do you see it coming ?
Thread T1 is done. It wants to release L1, so tries to enter the map, which means trying to acquire M, which is held by T2. T1 holds L1, waits for M. T2 holds M, waits for L1. Game over.

The solution : it is tempting to not try to create the lock and take it at the same time, e.g. do not acquire the lock when inside a locked method. Let's try (just to make a point, you'll see how hard it gets).

If you break this embedded lock pattern, you'll never have lock/unlock calls when your threads already have another lock, preventing any deadlock pattern (deadlocks can not occur with a single reentrant lock).

Which means : change your AccountLock class from a locking instance to a lock factory instance. Or if you want to integrate stuff, do it differently.

lock(String user) {
    LOCKS.computeIfAbsent(user, u -> new ReentrantLock()).lock();
}

by moving the lock acquisition outside the map's method call, i've removed it from the map's mutex, and I eliminated the deadlock possibility.

With that corrected, I created another bug.

On the unlock side, you use computeIfPresent which returns null. That means that once done with a lock, you intend to remove it from the map. This is all well, but it creates a race condition in the unlock case.

T1 creates lock L1 for user 1, puts it in the map and locks it.
T2 wants the same L1, gets it from the map, and waits for its availability
T1 finishes, releases L1 (T2 does not yet know about it), and removes it from the map
T3 comes in and wants a lock for user 1, but L1 is gone from the map, so it creates L2 and acquires it.
T2 sees that L1 is free, acquires it and works
At this point, both T2 and T3 have concurrent access to user 1, which is bad
T2 finished first, goes to the map instance and frees the lock for user 1 which is L2, a lock it never acquired in the first place. IllegalMonitorStateException.

There is no easy way out of this one. You have to make sure that concurrent threads wanting to access a user have a consistant lock instance (here the problem is that T1 releases a lock while T2 has a hold on it, but has not locked it yet). This could not happen with your original code - because of the map's mutex, but that mutex created deadlocks.

So what to do ?
You could never remove keys from the map.

public void unlock(String user) {
    LOCK_MAP.computeIfPresent(user, (s, lock) -> {
        lock.unlock();
        return lock;
});

But then nobody ever releases keys from the map, which grows indefinitely - one could add a thread-safe counter to check that locks are not "being acquired" before releasing them. Will that create in turn another bug ?

So that being said, there are still a few things to strengthen here :

Lock release should be performed in finally blocks
The number of lock instances you create is unbounded. You might want to avoid that (this is the real difficult part)
Having a mutex at the map's level is kind of a waste. A ConcurrentHashMap would provide much finer grained lock mechanism
Who knows what bug is left here.

Conclusion

Try and see if any solution provided in this other question helps you achieve your goal. It might be safer to use a respected library's implementation.

Concurrent programming is hard. Others have done it for you.

Locking database edit by key name

There may be a simple way to let your database take care of this for you. I am admittedly weak in knowledge when it comes to databases. In lieu of that, here is an approach that involves creating an individual lock for each key name. There is a single repository that manages the creation/destruction of the individual locks that requires a one-for-the-entire-application lock, but it only holds that lock while the individual key-name lock is being found, created, or destroyed. The lock that is held for the actual database operation is exclusive to the key name being used in that operation.

The KeyLock class is used to prevent simultaneous database operations on a single key name.

package KeyLocks;

import java.util.concurrent.locks.Lock;

public class KeyLock
{
    private final KeyLockManager keyLockManager;
    private final String keyName;
    private final Lock lock;

    KeyLock(KeyLockManager keyLockManager, String keyName, Lock lock)
    {
        this.keyLockManager = keyLockManager;
        this.keyName = keyName;
        this.lock = lock;
    }

    @Override
    protected void finalize()
    {
        release();
    }

    public void release()
    {
        keyLockManager.releaseLock(keyName);
    }

    public void lock()
    {
        lock.lock();
    }

    public void unlock()
    {
        lock.unlock();
    }
}

The KeyLockManager class is the repository that is responsible for the lifetimes of the key locks.

package KeyLocks;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class KeyLockManager
{
    private class LockEntry
    {
        int acquisitionCount = 0;
        final Lock lock = new ReentrantLock();
    }

    private final Map<String, LockEntry> locks = new HashMap<String, LockEntry>();
    private final Object mutex = new Object();

    public KeyLock getLock(String keyName)
    {
        synchronized (mutex)
        {
            LockEntry lockEntry = locks.get(keyName);
            if (lockEntry == null)
            {
                lockEntry = new LockEntry();
                locks.put(keyName, lockEntry);
            }
            lockEntry.acquisitionCount++;
            return new KeyLock(this, keyName, lockEntry.lock);
        }
    }

    void releaseLock(String keyName)
    {
        synchronized (mutex)
        {
            LockEntry lockEntry = locks.get(keyName);
            lockEntry.acquisitionCount--;
            if (lockEntry.acquisitionCount == 0)
            {
                locks.remove(keyName);
            }
        }
    }
}

Here is a sample of how you would use a key lock.

package test;

import KeyLocks.KeyLock;
import KeyLocks.KeyLockManager;

public class Main
{
    private static final String KEY_NAME = "TEST_KEY";

    public static void main(String[] args)
    {
        final KeyLockManager keyLockManager = new KeyLockManager();
        KeyLock keyLock = null;
        try
        {
            keyLock = keyLockManager.getLock(KEY_NAME);
            keyLock.lock();
            try
            {
                // Do database operation on the data with the specified key name
            }
            finally
            {
                keyLock.unlock();
            }
        }
        finally
        {
            if (keyLock != null)
            {
                keyLock.release();
            }
        }
    }
}

Simple Java Name Based Locks