7
\$\begingroup\$

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<Tuple<int, string>, object>
    _locks = new ConcurrentDictionary<Tuple<int, string>, 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 avoid unnecessary memory consumption, I have created a wrapper class to manage the item locks. This class implements IDisposable to ensure that the lock objects are deallocated when no longer needed.

The wrapper class looks like this:

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

    private readonly Tuple<int, string> _name;

    public object Lock { get; private set; }

    public ItemLock(int repoId, string itemKey)
    {
        lock (_listLock)
        {
            _name = Tuple.Create(repoId, itemKey);
            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);
        }
    }

    public void Dispose()
    {
        lock (_listLock)
        {
            _locks.Remove(this);
        }
    }
}

The code that uses it looks like this:

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

The way this works is that a new instance of the wrapper is created for each update operation. Internally, the wrapper maintains a list of all wrappers that are currently in use. When a new wrapper instance is created, it checks this list to see if there is an existing item for the same document (as identified by the _name tuple). If there is, it uses the existing lock object instance; if not, it creates a new lock object instance. When the wrapper is disposed, it is removed from the list. When all wrappers that refer to a particular lock object instance are disposed, the lock object instance itself can be garbage collected.

This approach seems to satisfy all of my requirements. My main concerns are:

  • Are there any memory leaks?
  • Are there any scenarios where the required locking will not be applied (i.e., simultaneous access to the same document)?
  • Is there a significantly better way to do this?

Thanks!

Update 1
I performed some memory use tests on the two approaches and the results were pretty much what I expected. The test was to process 1,000,000 documents (simple stubs, each with a unique key).

The disposable wrapper approach had stable memory use throughout the test while the memory used by the ConcurrentDictionary approach grew constantly. At the end of the test, the ConcurrentDictionary approach used 164 MB more.

The disposable wrapper also completed the test about 10% faster.

\$\endgroup\$
  • \$\begingroup\$ I'm slightly confused by your updated version. Don't you really just want a disposable wrapper which does the same thing as the first version, but removes the item from the concurrent dictionary at the end? \$\endgroup\$ – Ben Aaronson Sep 25 '15 at 9:41
  • \$\begingroup\$ Thanks for you comment. The problem with a dictionary keyed on the document identifier is that I would have to add something like a reference count to know when a lock is no longer in use. With the disposable wrapper, it uses a list to allow multiple instances of the identifier, each with a reference to the same lock instance. As wrappers are disposed, the references to the lock instance go away and garbage collection automatically frees the lock instance once all references are gone. \$\endgroup\$ – Jack A. Sep 25 '15 at 11:55
  • \$\begingroup\$ Why not use a NoSQL (or even SQL) database for this and have it take care of concurrency for you? There is the added benefit of making it easier to scale across multiple machines later - and you have the database software absorb the complexity for you which is a big win. It will likely also perform a lot better since databases are optimized for this - it can index, sort, cluster and all that very easily. \$\endgroup\$ – Benjamin Gruenbaum Oct 2 '15 at 13:21
  • \$\begingroup\$ @BenjaminGruenbaum we have a separate initiative working on a multi-machine architecture. This is an interim solution to improve the performance of the single process architecture. \$\endgroup\$ – Jack A. Oct 2 '15 at 13:28
6
\$\begingroup\$

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<ItemLock> _locks = new List<ItemLock>();

    private readonly Tuple<int, string> _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<ItemLock> _locks = new List<ItemLock>();

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

    private class ItemLock : IDisposable
    {
        private readonly Tuple<int, string> _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
}
\$\endgroup\$
  • \$\begingroup\$ I like this idea. \$\endgroup\$ – Jack A. Oct 2 '15 at 13:30
  • \$\begingroup\$ I guess the one thing I would want to think about with this approach is the naming. In the usage code, it isn't necessarily clear that you're entering a critical section when you instantiate ItemLock. \$\endgroup\$ – Jack A. Oct 2 '15 at 13:39
  • \$\begingroup\$ See update to my answer \$\endgroup\$ – almaz Oct 2 '15 at 16:15
1
\$\begingroup\$

I'd suggest keeping a list of locks per repository:

public class ItemLock : IDisposable
{
    private static object _listLock = new object();
    private static IDictionary<int, List<ItemLock>> _locks = new Dictionary<int, List<ItemLock>>();

    private readonly string _itemKey;

    private object _lock;

    public ItemLock(int repoId, string itemKey)
    {
        lock (_listLock)
        {
            _itemKey = itemKey;
            List<ItemLock> itemLocks;
            if (!_locks.TryGetValue(repoId, out itemLocks)
            {
                _locks[repoId] = itemLocks = new List<ItemLock>();
            }
            var existing = itemLocks.Find(l => l._itemKey.Equals(itemKey));
            _lock = existing == null ? new object() : existing._lock;
            _locks.Add(this);
        }
        Monitor.Enter(_lock); // from almaz's answer
    }

    public void Dispose()
    {
        // from almaz's answer
        if (Monitor.IsEntered(_lock)) 
            Monitor.Exit(_lock);

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

The reason I'd do that is because you're otherwise forced to loop through the other repositories' locks which will never match - i.e. it's a waste of CPU. With the above (very rough, possibly not working) approach you only loop through the locks which are taken out within the current repository.

I also removed the Lock property as I don't see why you would need that :)

// blocks until the lock is acquired.
using (new ItemLock(1, "some-item-id"))
{
    // do work 
}

Edit:

Some other things for you to consider:

\$\endgroup\$
  • \$\begingroup\$ Thanks for the reply. The total number of wrapper instances in the collection will never be more than the number of processing threads. This is a small number (typically around 10), so I don't think the extra complexity of subdividing by repository is worthwhile in this case. I'll take a look at the IDisposable article. \$\endgroup\$ – Jack A. Oct 2 '15 at 13:36
  • \$\begingroup\$ @JackA. Ah yes, definitely not worth it! \$\endgroup\$ – RobH Oct 2 '15 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.