Efficient locking on a resource, identified by a string [duplicate]

Question

I'm attempting to figure out an issue that has been raised with my ImageProcessor library here where I am getting intermittent file access errors when adding items to the cache.

System.IO.IOException: The process cannot access the file 'D:\home\site\wwwroot\app_data\cache\0\6\5\f\2\7\065f27fc2c8e843443d210a1e84d1ea28bbab6c4.webp' because it is being used by another process.

I wrote a class designed to perform an asynchronous lock based upon a key generated by a hashed url but it seems I have missed something in the implementation.

My locking class

public sealed class AsyncDuplicateLock
{
    /// <summary>
    /// The collection of semaphore slims.
    /// </summary>
    private static readonly ConcurrentDictionary<object, SemaphoreSlim> SemaphoreSlims
                            = new ConcurrentDictionary<object, SemaphoreSlim>();

    /// <summary>
    /// Locks against the given key.
    /// </summary>
    /// <param name="key">
    /// The key that identifies the current object.
    /// </param>
    /// <returns>
    /// The disposable <see cref="Task"/>.
    /// </returns>
    public IDisposable Lock(object key)
    {
        DisposableScope releaser = new DisposableScope(
        key,
        s =>
        {
            SemaphoreSlim locker;
            if (SemaphoreSlims.TryRemove(s, out locker))
            {
                locker.Release();
                locker.Dispose();
            }
        });

        SemaphoreSlim semaphore = SemaphoreSlims.GetOrAdd(key, new SemaphoreSlim(1, 1));
        semaphore.Wait();
        return releaser;
    }

    /// <summary>
    /// Asynchronously locks against the given key.
    /// </summary>
    /// <param name="key">
    /// The key that identifies the current object.
    /// </param>
    /// <returns>
    /// The disposable <see cref="Task"/>.
    /// </returns>
    public Task<IDisposable> LockAsync(object key)
    {
        DisposableScope releaser = new DisposableScope(
        key,
        s =>
        {
            SemaphoreSlim locker;
            if (SemaphoreSlims.TryRemove(s, out locker))
            {
                locker.Release();
                locker.Dispose();
            }
        });

        Task<IDisposable> releaserTask = Task.FromResult(releaser as IDisposable);
        SemaphoreSlim semaphore = SemaphoreSlims.GetOrAdd(key, new SemaphoreSlim(1, 1));

        Task waitTask = semaphore.WaitAsync();

        return waitTask.IsCompleted
                   ? releaserTask
                   : waitTask.ContinueWith(
                       (_, r) => (IDisposable)r,
                       releaser,
                       CancellationToken.None,
                       TaskContinuationOptions.ExecuteSynchronously,
                       TaskScheduler.Default);
    }

    /// <summary>
    /// The disposable scope.
    /// </summary>
    private sealed class DisposableScope : IDisposable
    {
        /// <summary>
        /// The key
        /// </summary>
        private readonly object key;

        /// <summary>
        /// The close scope action.
        /// </summary>
        private readonly Action<object> closeScopeAction;

        /// <summary>
        /// Initializes a new instance of the <see cref="DisposableScope"/> class.
        /// </summary>
        /// <param name="key">
        /// The key.
        /// </param>
        /// <param name="closeScopeAction">
        /// The close scope action.
        /// </param>
        public DisposableScope(object key, Action<object> closeScopeAction)
        {
            this.key = key;
            this.closeScopeAction = closeScopeAction;
        }

        /// <summary>
        /// Disposes the scope.
        /// </summary>
        public void Dispose()
        {
            this.closeScopeAction(this.key);
        }
    }
}

Usage - within a HttpModule

private readonly AsyncDuplicateLock locker = new AsyncDuplicateLock();

using (await this.locker.LockAsync(cachedPath))
{
    // Process and save a cached image.
}

Can anyone spot where I have gone wrong? I'm worried that I am misunderstanding something fundamental.

The full source for the library is stored on Github here

Answer 1

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();
    }
  }
}

Answer 2

The problems in your implementation arise from your desire to remove unused lockers from the dictionary. It would be much simpler if you could just let each SemaphoreSlim stay in the dictionary forever (until the process terminates). Assuming that this is not a viable option, you have two obstacles to overcome:

1. How to keep track of how many workers are using each semaphore, so that you know when it's safe to remove it.
2. How to do the above using the performant but tricky ConcurrentDictionary<K,V> collection.

Stephen Cleary's answer shows how to solve the first problem, using a normal Dictionary<K,V>. A reference counter is stored along with each SemaphoreSlim, and everything is synchronized with the lock statement on a single locker object. In this answer I'll show how to solve the second problem.

The problem with the ConcurrentDictionary<K,V> collection is that it protects from corruption only its internal state, not the values it contains. So if you use a mutable class as TValue, you are opening the door for class">subtle race conditions, especially if you intend to cache these values in a pool and reuse them. The trick that eliminates the race conditions is to make the TValue an immutable struct. This way it essentially becomes part of the internal state of the dictionary, and it is protected by it. In the AsyncDuplicateLock implementation below, the TValue is a readonly struct, declared also as a record for performance¹ and convenience:

public class AsyncDuplicateLock
{
    private readonly ConcurrentDictionary<object, Entry> _semaphores = new();

    private readonly record struct Entry(SemaphoreSlim Semaphore, int RefCount);

    public readonly struct Releaser : IDisposable
    {
        private readonly AsyncDuplicateLock _parent;
        private readonly object _key;
        public Releaser(AsyncDuplicateLock parent, object key)
        {
            _parent = parent; _key = key;
        }
        public void Dispose() => _parent.Release(_key);
    }

    public async ValueTask<Releaser> LockAsync(object key)
    {
        Entry entry = _semaphores.AddOrUpdate(key,
            static _ => new Entry(new SemaphoreSlim(1, 1), 1),
            static (_, entry) => entry with { RefCount = entry.RefCount + 1 });

        await entry.Semaphore.WaitAsync().ConfigureAwait(false);
        return new Releaser(this, key);
    }

    private void Release(object key)
    {
        Entry entry;
        while (true)
        {
            bool exists = _semaphores.TryGetValue(key, out entry);
            if (!exists)
                throw new InvalidOperationException("Key not found.");
            if (entry.RefCount > 1)
            {
                Entry newEntry = entry with { RefCount = entry.RefCount - 1 };
                if (_semaphores.TryUpdate(key, newEntry, entry))
                    break;
            }
            else
            {
                if (_semaphores.TryRemove(KeyValuePair.Create(key, entry)))
                    break;
            }
        }
        entry.Semaphore.Release();
    }
}

Notice that increasing and decreasing the RefCount involves spinning in a while loop. That's because the current thread might lose the optimistic race with other threads for updating the dictionary, in which case it tries again until it succeeds. The spinning is obvious in the Release method, but also happens internally in the LockAsync method. The AddOrUpdate method employs internally a similar logic around the invocation of the updateValueFactory delegate.

Performance: the above implementation is about 80% faster than a simpler Dictionary<K,V>-based implementation, under conditions of heavy contention. That's because the ConcurrentDictionary<K,V> utilizes multiple locker objects internally, so a thread that wants to lock on the key "A" doesn't have to wait until another thread completes acquiring or releasing the key "B". It is considerably more allocatey though. If you have some reason to keep the garbage collector relaxed, a Dictionary<K,V>-based implementation will you serve you better. If you desire both ultimate speed and ultimate memory-efficiency, you could take a look at the 6th revision of this answer, for an implementation based on multiple Dictionary<K,V>s.

Exceptions: When the SemaphoreSlim class is misused, it throws a SemaphoreFullException. This happens when the semaphore is released more times than it has been acquired. The AsyncDuplicateLock implementation of this answer behaves differently in case of misuse: it throws an InvalidOperationException("Key not found."). This happens because when a key is released as many times as it has been acquired, the associated semaphore is removed from the dictionary. If this implementation ever throws a SemaphoreFullException, it would be an indication of a bug.

Note: Personally I am not a fan of (mis)using the using statement for purposes other than releasing unmanaged resources.

¹ _{The ConcurrentDictionary<K,V> compares the TValues in many operations (AddOrUpdate, TryUpdate and TryRemove among others), using the EqualityComparer<TValue>.Default. Structs by default are not compared efficiently, unless they implement the IEquatable<T> interface. Record structs do implement this interface, in a similar way to the value-tuples, so they can be compared for equality efficiently. Actually using a value-tuple as TValue ((SemaphoreSlim, int)) might be slightly more efficient, because the members of value-tuples are fields, while the members of record structs are properties. Record structs are more convenient though.}