Asynchronous Locking Based on a Key

Asynchronous locking based on a key

As the other answerer noted, the original code is removing the SemaphoreSlim from the ConcurrentDictionary before it releases the semaphore. So, you've got too much semaphore churn going on - they're being removed from the dictionary when they could still be in use (not acquired, but already retrieved from the dictionary).

The problem with this kind of "mapping lock" is that it's difficult to know when the semaphore is no longer necessary. One option is to never dispose the semaphores at all; that's the easy solution, but may not be acceptable in your scenario. Another option - if the semaphores are actually related to object instances and not values (like strings) - is to attach them using ephemerons; however, I believe this option would also not be acceptable in your scenario.

So, we do it the hard way. :)

There are a few different approaches that would work. I think it makes sense to approach it from a reference-counting perspective (reference-counting each semaphore in the dictionary). Also, we want to make the decrement-count-and-remove operation atomic, so I just use a single lock (making the concurrent dictionary superfluous):

public sealed class AsyncDuplicateLock
{
  private sealed class RefCounted<T>
  {
    public RefCounted(T value)
    {
      RefCount = 1;
      Value = value;
    }

    public int RefCount { get; set; }
    public T Value { get; private set; }
  }

  private static readonly Dictionary<object, RefCounted<SemaphoreSlim>> SemaphoreSlims
                        = new Dictionary<object, RefCounted<SemaphoreSlim>>();

  private SemaphoreSlim GetOrCreate(object key)
  {
    RefCounted<SemaphoreSlim> item;
    lock (SemaphoreSlims)
    {
      if (SemaphoreSlims.TryGetValue(key, out item))
      {
        ++item.RefCount;
      }
      else
      {
        item = new RefCounted<SemaphoreSlim>(new SemaphoreSlim(1, 1));
        SemaphoreSlims[key] = item;
      }
    }
    return item.Value;
  }

  public IDisposable Lock(object key)
  {
    GetOrCreate(key).Wait();
    return new Releaser { Key = key };
  }

  public async Task<IDisposable> LockAsync(object key)
  {
    await GetOrCreate(key).WaitAsync().ConfigureAwait(false);
    return new Releaser { Key = key };
  }

  private sealed class Releaser : IDisposable
  {
    public object Key { get; set; }

    public void Dispose()
    {
      RefCounted<SemaphoreSlim> item;
      lock (SemaphoreSlims)
      {
        item = SemaphoreSlims[Key];
        --item.RefCount;
        if (item.RefCount == 0)
          SemaphoreSlims.Remove(Key);
      }
      item.Value.Release();
    }
  }
}

An AsyncDuplicateLock that can be locked on all keys

I strongly, strongly advise you to take a step back, think about the actual problem you're trying to solve, explain it to someone else, and ask them how they would solve the concurrency issues.

That said, yes, you can (ab)use a reader/writer lock to do this. Personally, I would separate out the locking:

public IDisposable ReaderLock(object key)
{
  var rwKey = _rwLock.ReaderLock();
  var duplicateKey = _duplicateLock.Lock(key);
  return CollectionDisposable.Create(rwKey, duplicateKey);
}

// (and the same for async)

This makes it more obvious that the code is taking the RWL first (which it must do, in order to be correct).

Keyed Lock in .Net

You correctly recognized that you need to ensure that only one semaphore is being created per key. The standard idiom for that is:

var dict = new ConcurrentDictionary<TKey, Lazy<SemaphoreSlim>>();
...
var sem = dict.GetOrAdd( , _ => new new Lazy<SemaphoreSlim>(() => SemaphoreSlim(1, 1))).Value;

Multiple lazies might be created but only one of them will ever be revealed and materialized.

Besides that it is a questionable practice to rely on in-memory state. What if your queue processing app recycles and all semaphores are lost? You better use a persistent store to track this locking info.

Efficient locking on a resource, identified by a string

You could probably improve upon the first solution by removing a lock from the dictionary when it stops being in use. The removed locks could then be added to a small pool, so that the next time you need a lock you just grab one from the pool instead of creating a new one.

Update: Here is an implementation of this idea. It is based on SemaphoreSlims instead of Stephen Cleary's AsyncLocks, because a custom disposable is required in order to remove unused semaphores from the dictionary.

public class MultiLock<TKey>
{
    private object Locker { get; } = new object();
    private Dictionary<TKey, LockItem> Dictionary { get; }
    private Queue<LockItem> Pool { get; }
    private int PoolSize { get; }

    public MultiLock(int poolSize = 10)
    {
        Dictionary = new Dictionary<TKey, LockItem>();
        Pool = new Queue<LockItem>(poolSize);
        PoolSize = poolSize;
    }

    public WaitResult Wait(TKey key,
        int millisecondsTimeout = Timeout.Infinite,
        CancellationToken cancellationToken = default)
    {
        var lockItem = GetLockItem(key);
        bool acquired;
        try
        {
            acquired = lockItem.Semaphore.Wait(millisecondsTimeout,
                cancellationToken);
        }
        catch
        {
            ReleaseLockItem(lockItem, key);
            throw;
        }
        return new WaitResult(this, lockItem, key, acquired);
    }

    public async Task<WaitResult> WaitAsync(TKey key,
        int millisecondsTimeout = Timeout.Infinite,
        CancellationToken cancellationToken = default)
    {
        var lockItem = GetLockItem(key);
        bool acquired;
        try
        {
            acquired = await lockItem.Semaphore.WaitAsync(millisecondsTimeout,
                cancellationToken).ConfigureAwait(false);
        }
        catch
        {
            ReleaseLockItem(lockItem, key);
            throw;
        }
        return new WaitResult(this, lockItem, key, acquired);
    }

    private LockItem GetLockItem(TKey key)
    {
        LockItem lockItem;
        lock (Locker)
        {
            if (!Dictionary.TryGetValue(key, out lockItem))
            {
                if (Pool.Count > 0)
                {
                    lockItem = Pool.Dequeue();
                }
                else
                {
                    lockItem = new LockItem();
                }
                Dictionary.Add(key, lockItem);
            }
            lockItem.UsedCount += 1;
        }
        return lockItem;
    }

    private void ReleaseLockItem(LockItem lockItem, TKey key)
    {
        lock (Locker)
        {
            lockItem.UsedCount -= 1;
            if (lockItem.UsedCount == 0)
            {
                if (Dictionary.TryGetValue(key, out var stored))
                {
                    if (stored == lockItem) // Sanity check
                    {
                        Dictionary.Remove(key);
                        if (Pool.Count < PoolSize)
                        {
                            Pool.Enqueue(lockItem);
                        }
                    }
                }
            }
        }
    }

    internal class LockItem
    {
        public SemaphoreSlim Semaphore { get; } = new SemaphoreSlim(1);
        public int UsedCount { get; set; }
    }

    public struct WaitResult : IDisposable
    {
        private MultiLock<TKey> MultiLock { get; }
        private LockItem LockItem { get; }
        private TKey Key { get; }

        public bool LockAcquired { get; }

        internal WaitResult(MultiLock<TKey> multiLock, LockItem lockItem, TKey key,
            bool acquired)
        {
            MultiLock = multiLock;
            LockItem = lockItem;
            Key = key;
            LockAcquired = acquired;
        }

        void IDisposable.Dispose()
        {
            MultiLock.ReleaseLockItem(LockItem, Key);
            LockItem.Semaphore.Release();
        }
    }
}

Usage example:

var multiLock = new MultiLock<string>();
using (await multiLock.WaitAsync("SomeKey"))
{
    //...
}

The default pool size for unused semaphores is 10. The optimal value should be the number of the concurrent workers that are using the MultiLock instance.

I did a performance test in my PC, and 10 workers were able to acquire the lock asynchronously 500,000 times in total per second (20 different string identifiers were used).

What is the Correct Usage of SempahoreSlim as a Lock in Async Code?

Yes, it is true that in theory something could happen between the await semaphoreSlim.WaitAsync(); and the try, but in reality: in that scenario your app is already toast, as it is in the process of imploding call-stacks. In reality, while this is a theoretical concern, there isn't much that you can usefully do anyway, and your process is about to be put down ungracefully like the sickly thing that it is.

So my advice: don't worry too much about it :)

(in reality, the much bigger risk is a thread-pool spiral of death, usually caused by sync-over-async on thread-pool threads, meaning that even though you have acquired the semaphore semantically, there is no pool thread to give to you to actually do the thing, allowing you to get back to releasing it)

locking object in async operation

How about changing the delegate to look like this:

var cacheValue = operation();
lock (this.Cache)
            {
                if (!this.Cache.Contains(key))
                {
                    // Perform the operation to get value for cache here

                    this.Cache.Add(key, cacheValue);
                }
            }

This kind of coding locks the dictionary for a very short time. You can also try using ConcurrentDictionary that mostly doesn't to any locking at all.

Alex.

Asynchronous Locking Based on a Key