Using `ConcurrentDictionary` with thousands or even millions of entries to lock only on specific keys

Question

Is it reasonable to use a ConcurrentDictionary<String, SemaphoreSlim> with thousands or even millions of entries to lock only on specific keys? That is, something like

private static readonly ConcurrentDictionary<String, SemaphoreSlim> _Locks = new();
...
var _Lock = _Locks.GetOrAdd(_Key, (_) => new SemaphoreSlim(1, 1));
await _Lock.WaitAsync();
try { ... } finally { _Lock.Release() }

My main concerns would be:

1. the sheer number of SemaphoreSlims that are potentially in play (thousands or even millions)
2. (_) => new SemaphoreSlim(1, 1) potentially being called extra times such that there are SemaphoreSlims that are allocated but ultimately never used.

Update with further context:

I reality, I probably only need to support between 1k - 10k entries.

I am trying to use the SemaphoreSlims to lock on updates to another ConcurrentDictionary that acts as a cache by the same key.

private static readonly ConcurrentDictionary<String, SemaphoreSlim> 
_Locks = new();
private static readonly ConcurrentDictionary<String, ImmutableType> _Cache = new();
...
var _Value;
var _Lock = _Locks.GetOrAdd(_Key, (_) => new SemaphoreSlim(1, 1));
await _Lock.WaitAsync();
try 
{ 
  if(!_Cache.TryGetValue(_Key, out _Value) || _Value.ExpirationTime < DateTime.UtcNow)
  {
    //do expensive operation to construct the _Value
    //possibly return from the method if we can't construct the _Value
    //(we can't use a Lazy Task - we are in the middle of a bi-direction gRPC call on the server side)
    _Cache[_Key] = _Value;
  }  
} finally { _Lock.Release() }

Note that the _Value type is an immutable class, we are just trying to avoid blocking other callers for other keys while refreshing our cache for the key in question.

Also note that I am not worried about evicting stale entries. We refresh them as needed but never remove them.

Answer 1

Having a ConcurrentDictionary<K,V> with millions of idle SemaphoreSlims sitting around is certainly concerning. It might not be a big deal if you have abundant memory available, but if you are aiming at economic use of resources it is possible to evict from the dictionary the SemaphoreSlims that are not actively used at the moment. It's not trivial because you have to track how many workers are using each semaphore, but it's not rocket science either. You can find implementations in this question:

• Asynchronous locking based on a key

If you are worried about SemaphoreSlims being left undisposed, see this question:

• Do I need to Dispose a SemaphoreSlim?

Disposing IDisposable instances is the correct thing to do in principle, but practically the SemaphoreSlim.Dispose method is a no-op, unless you are using the rarely used AvailableWaitHandle property.

Answer 2

This is a solution I have used a long time for protecting my webapi:s from duplicates.

It is based on a single TaskCompletionSource which is only used when the lock is actually contended.

One drawback is that all waiting tasks need to reacquire the lock on release even if they are waiting for a different key. It is a quick cycle for each task but if probability of contention is high a better solution might be to use a separate TCS for each contended key.

(my implementation returns an IDisposable and is using a plain List for the keys but I simplified the code for this example)

public sealed class KeyedSemaphore<TKey>
{
    // A concurrent dictionary locks on mutations and we only do mutations.
    // Use a normal collection inside lock instead
    private readonly HashSet<TKey> _keys;

    // Using the same tcs will cause all waiting tasks, 
    // independent of key, to spin on each release
    private TaskCompletionSource<object> _tcs;

    public KeyedSemaphore(IEqualityComparer<TKey> comparer = null)
    {
        _keys = new HashSet<TKey>(comparer);
    }

    public async Task WaitAsync(TKey key)
    {
        while (true) // this will loop until key is successfully added to _keys
        {
            Task task;

            lock (_keys)
            {
                if (_keys.Add(key))
                    return;

                if (_tcs == null || _tcs.Task.IsCompleted)
                {
                    _tcs = new TaskCompletionSource<object>();
                }

                task = _tcs.Task;
            }

            await task.ConfigureAwait(false);
        }
    }

    public void Release(TKey key)
    {
        lock (_keys)
        {
            if (!_keys.Remove(key))
                return; // maybe an error instead
        }

        _tcs?.TrySetResult(null);
    }
}

Usage:

private static readonly KeyedSemaphore<int> _keyedSemaphore = new();

public async Task CreateOrderAsync(Order order)
{
    // This ensures multiple requests for creating same order
    // will not create multiple orders
    await _keyedSemaphore.WaitAsync(order.Id)
    try 
    {
       if (OrderExists(order.Id)
           return Conflict();
       ... 
    }
    finally {
        _keyedSemaphore.Release(order.Id);
    }
}