Named Locks and Lock Striping

Suppose there is a function to which a reference to some arbitrary resource is passed (a file name, for example). The function needs exclusive access to that referenced resource, but should allow concurrent access to other resources. On the one hand, a single lock object would synchronize all calls to the function, which would ruin concurrency. On the other hand, the references are arbitrary, so the number of lock objects required is non-deterministic.

Framework support for named locks is kind of thin. The .NET framework offers named mutexes. For .NET developers this seems like an obvious choice, but since they are system-level they are very tricky to implement properly and can get out of sync very easily.

One more broadly applicable approach I've seen involves locking on the interned string representation of the resource reference. Any two references that are the same will convert to the same interned string instance, so the lock will prevent concurrent access. Meanwhile references that are not the same will convert to different interned string references, so the locks should permit concurrent access. However, if there are a lot of different possible values (names of temporary files, for example) then this approach is not sustainable--the number of interned strings would grow without bound until some kind of limit is reached, and there is usually no way to un-intern a string.

Another approach would be to set up a concurrent dictionary. When the function needs exclusive access, a GetOrAdd is attempted on the dictionary using the resource reference as a key. Atomically, the concurrent dictionary will add the key-value pair if it does not exist or return the existing value for the key. Other threads needing access to the same reference will therefore receive the same lock instance, which should prevent concurrent access to the same resource while permitting concurrent operations on different resources.

However, there is no good heuristic for determining when (or even if) a lock should be removed from the concurrent dictionary. If the lock is removed as a thread exits the critical section, then new threads attempting to access the resource will get a new lock object for that key as a result of the GetOrAdd call. This would permit concurrent access to the same resource if there are already threads waiting for access to the previous lock object. Or perhaps a cleanup thread could run in the background and periodically block all threads while old keys are cleaned up, but that increases the potential for deadlocks and race conditions that would be difficult to track down.

So the trick is to somehow map an arbitrary set of inputs to a reasonable number of lock objects. One possibility is to compute a hash code for each resource reference, which reduces a potentially infinite set of inputs to the range of an int. But that still leaves millions of possibilities, so the next step is to mod the hash code by some reasonable number of lock objects. Say, for example, 64. An array of 64 objects doesn't take up too much space, and more importantly, its size will never grow. The final algorithm looks something like this:

class LockExample
{
    private const int MaxLocks = 64;
    private static object[] Locks = new object[MaxLocks];

    static LockExample()
    {
        for (var i = 0; i < MaxLocks; i++)
        {
            Locks[i] = new object();
        }
    }

    public void Critical(string resourceName)
    {
        EnterLock(resourceName);
        try
        {
            // Critical section
        }
        finally
        {
            ExitLock(resourceName);
        }
    }

    private void EnterLock(string resourceName)
    {
        Monitor.Enter(GetLock(resourceName));
    }

    private void ExitLock(string resourceName)
    {
        Monitor.Exit(GetLock(resourceName));
    }

    private object GetLock(string resourceName)
    {
        if (resourceName == null) throw new ArgumentNullException();
        var lockIndex = ((uint)resourceName.GetHashCode()) % MaxLocks;
        return Locks[lockIndex];
    }
}

This technique (which I gather is called lock striping) offers much more concurrency than a single lock object while avoiding the out-of-control memory growth of dictionaries and interned strings. I decided to write about it after spending an entire afternoon searching for things like "named lock" and coming up empty. It wasn't until I finally thought to look at the details of sp_getAppLock procedure in SQL server function that I found myself on the right track.

Despite being widely used (Google's Guava library has a reusable implementation), there does't seem to be much discussion about it. In fact, I didn't even know the name of it until I stumbled across a mention of the jkeylockmanager project in a Stack Overflow discussion and browsed the source. (Which, happily, has a file named StripedKeyLockManager.)

Granted, this isn't something that comes up every day, and generally speaking locks are something to be avoided if at all possible. But every once in a while a situation like this does come up, and knowing what to look for makes all the difference.