Item-level locks for a large number of items

Background

I'm working on a system that records information about a large number of external documents. These documents are organized by "repository". There can be a modest number of repositories (hundreds). Each repository can contain an essentially unbounded number of documents (tens of millions in some cases). Each document is identified by a key, which is unique per repository. So each document in the system is uniquely identified by the combination of repository ID and document key.

There is one process that is responsible for detecting changes to the documents and updating the system with the changes. The process for updating a document requires reading the document, applying changes, and saving. There are multiple sources of change notifications, and several threads (tens) that process the change notifications. On rare occasions, there can be multiple change notifications for the same document at the same time. For concurrency, two threads must not update the same document at the same time.

The current concurrency implementation has one lock per repository, so only one document in each repository can be updated at a time. This has proven to have unacceptable performance.

Requirements

I want to implement document-level locks to allow multiple documents to be updated in the same repository at the same time. I want to do this without adding unacceptable overhead.

Many of the solutions to similar problems involve the use of ConcurrentDictionary, and my green solution did just this:

private static ConcurrentDictionary, object>
    _locks = new ConcurrentDictionary, object>();

public void UpdateItem(int repoId, string itemKey)
{
    var lockName = Tuple.Create(repoId, itemKey);
    lock (_locks.GetOrAdd(lockName, new object()))
    {
        // read, update, save
    }
}

My concern with this approach is that there can be a huge number of documents, and the lock instances created using this technique are never deallocated.

Proposed Solution

To a

I don't see memory leaks here, as well as cases where lock is not applied.

From design point of view I improve it a little bit. Currently you require customers to get the item lock and then lock on the Lock property. You can simplify it by locking right away, and unlocking in within Dispose method:

public class ItemLock : IDisposable
{
    private static readonly object _listLock = new object();
    private static readonly List _locks = new List();

    private readonly Tuple _name;
    private readonly object _lock;

    public ItemLock(int repoId, string itemKey)
    {
        _name = Tuple.Create(repoId, itemKey);
        lock (_listLock)
        {
            var existing = _locks.Find(l => l._name.Equals(_name));
            // Allow one lock instance per name
            _lock = existing == null ? new object() : existing._lock;
            _locks.Add(this);
        }
        Monitor.Enter(_lock);
    }

    public void Dispose()
    {
        if (Monitor.IsEntered(_lock)) //can be skipped if usages are from your code only
            Monitor.Exit(_lock);

        lock (_listLock)
        {
            _locks.Remove(this);
        }
    }
}

so that the usage looks like

using (var itemLock = new ItemLock(repoId, itemKey))
{
    // read, update, save
}

UPDATE: To hide the details, and express the locking behaviour even further you can wrap the ItemLock like this:

public static class ConcurrencyControl
{
    private static readonly object _listLock = new object();
    private static readonly List _locks = new List();

    public static IDisposable AcquireLock(int repoId, string itemKey)
    {
        return new ItemLock(repoId, itemKey);
    }

    private class ItemLock : IDisposable
    {
        private readonly Tuple _name;
        private readonly object _lock;

        public ItemLock(int repoId, string itemKey)
        {
            _name = Tuple.Create(repoId, itemKey);
            lock (_listLock)
            {
                var existing = _locks.Find(l => l._name.Equals(_name));
                // Allow one lock instance per name
                _lock = existing == null ? new object() : existing._lock;
                _locks.Add(this);
            }
            Monitor.Enter(_lock);
        }

        public void Dispose()
        {
            if (Monitor.IsEntered(_lock)) //can be skipped if usages are from your code only
                Monitor.Exit(_lock);

            lock (_listLock)
            {
                _locks.Remove(this);
            }
        }
    }
}

Usage:

using (ConcurrencyControl.AcquireLock(repoId, itemKey))
{
    // read, update, save
}

StackExchange Code Review Q#105523, answer score: 9