The best solution for multi-threaded puzzles?

Question

Here's the task: I need to block based on the file name. There may be up to a million different file names. (This is used for large-scale disk-based caching). I want to use low memory and low search times, which means that I need a GC'd lock dictionary. (Only built-in locks can be present in a dict).

The callback may take several minutes, so global locking is unacceptable. High throughput is critical.

I posted my current solution below, but I'm not happy with the complexity.

EDIT: Please do not submit solutions that are not 100% correct. For example, a solution that allows you to exclude a lock from the dictionary between the “get object lock” phase and the “lock” phase is NOT correct, regardless of whether it is an “accepted” design pattern or not.

Is there a more elegant solution than this?

Thanks!

[EDIT: I updated my code to use a loop or recursion based on RobV's suggestion]

[EDIT: code updated again to allow timeouts and a simpler call pattern. This will probably be the last code I use. All the same basic algorithm as in the original message.]

[EDIT: updated code again to deal with exceptions inside callback without orphaned lock objects]

public delegate void LockCallback(); /// <summary> /// Provides locking based on a string key. /// Locks are local to the LockProvider instance. /// The class handles disposing of unused locks. Generally used for /// coordinating writes to files (of which there can be millions). /// Only keeps key/lock pairs in memory which are in use. /// Thread-safe. /// </summary> public class LockProvider { /// <summary> /// The only objects in this collection should be for open files. /// </summary> protected Dictionary<String, Object> locks = new Dictionary<string, object>(StringComparer.Ordinal); /// <summary> /// Synchronization object for modifications to the 'locks' dictionary /// </summary> protected object createLock = new object(); /// <summary> /// Attempts to execute the 'success' callback inside a lock based on 'key'. If successful, returns true. /// If the lock cannot be acquired within 'timoutMs', returns false /// In a worst-case scenario, it could take up to twice as long as 'timeoutMs' to return false. /// </summary> /// <param name="key"></param> /// <param name="success"></param> /// <param name="failure"></param> /// <param name="timeoutMs"></param> public bool TryExecute(string key, int timeoutMs, LockCallback success){ //Record when we started. We don't want an infinite loop. DateTime startedAt = DateTime.UtcNow; // Tracks whether the lock acquired is still correct bool validLock = true; // The lock corresponding to 'key' object itemLock = null; try { //We have to loop until we get a valid lock and it stays valid until we lock it. do { // 1) Creation/aquire phase lock (createLock) { // We have to lock on dictionary writes, since otherwise // two locks for the same file could be created and assigned // at the same time. (ie, between TryGetValue and the assignment) if (!locks.TryGetValue(key, out itemLock)) locks[key] = itemLock = new Object(); //make a new lock! } // Loophole (part 1): // Right here - this is where another thread (executing part 2) could remove 'itemLock' // from the dictionary, and potentially, yet another thread could // insert a new value for 'itemLock' into the dictionary... etc, etc.. // 2) Execute phase if (System.Threading.Monitor.TryEnter(itemLock, timeoutMs)) { try { // May take minutes to acquire this lock. // Trying to detect an occurence of loophole above // Check that itemLock still exists and matches the dictionary lock (createLock) { object newLock = null; validLock = locks.TryGetValue(key, out newLock); validLock = validLock && newLock == itemLock; } // Only run the callback if the lock is valid if (validLock) { success(); // Extremely long-running callback, perhaps throwing exceptions return true; } } finally { System.Threading.Monitor.Exit(itemLock);//release lock } } else { validLock = false; //So the finally clause doesn't try to clean up the lock, someone else will do that. return false; //Someone else had the lock, they can clean it up. } //Are we out of time, still having an invalid lock? if (!validLock && Math.Abs(DateTime.UtcNow.Subtract(startedAt).TotalMilliseconds) > timeoutMs) { //We failed to get a valid lock in time. return false; } // If we had an invalid lock, we have to try everything over again. } while (!validLock); } finally { if (validLock) { // Loophole (part 2). When loophole part 1 and 2 cross paths, // An lock object may be removed before being used, and be orphaned // 3) Cleanup phase - Attempt cleanup of lock objects so we don't // have a *very* large and slow dictionary. lock (createLock) { // TryEnter() fails instead of waiting. // A normal lock would cause a deadlock with phase 2. // Specifying a timeout would add great and pointless overhead. // Whoever has the lock will clean it up also. if (System.Threading.Monitor.TryEnter(itemLock)) { try { // It succeeds, so no-one else is working on it // (but may be preparing to, see loophole) // Only remove the lock object if it // still exists in the dictionary as-is object existingLock = null; if (locks.TryGetValue(key, out existingLock) && existingLock == itemLock) locks.Remove(key); } finally { // Remove the lock System.Threading.Monitor.Exit(itemLock); } } } } } // Ideally the only objects in 'locks' will be open operations now. return true; } } 

Usage example

 LockProvider p = new LockProvider(); bool success = p.TryExecute("filename",1000,delegate(){ //This code executes within the lock }); 

Answer 1

There is no ideal way to do this in .NET, although I improved the algorithm thanks to the @RobV loop suggestion. Here is the final decision I settled on.

It is immune to the "orphaned link" error, which seems typical of a standard template, followed by @Steven's answer.

 using System; using System.Collections.Generic; using System.Text; using System.Threading; namespace ImageResizer.Plugins.DiskCache { public delegate void LockCallback(); /// <summary> /// Provides locking based on a string key. /// Locks are local to the LockProvider instance. /// The class handles disposing of unused locks. Generally used for /// coordinating writes to files (of which there can be millions). /// Only keeps key/lock pairs in memory which are in use. /// Thread-safe. /// </summary> public class LockProvider { /// <summary> /// The only objects in this collection should be for open files. /// </summary> protected Dictionary<String, Object> locks = new Dictionary<string, object>(StringComparer.Ordinal); /// <summary> /// Synchronization object for modifications to the 'locks' dictionary /// </summary> protected object createLock = new object(); /// <summary> /// Attempts to execute the 'success' callback inside a lock based on 'key'. If successful, returns true. /// If the lock cannot be acquired within 'timoutMs', returns false /// In a worst-case scenario, it could take up to twice as long as 'timeoutMs' to return false. /// </summary> /// <param name="key"></param> /// <param name="success"></param> /// <param name="failure"></param> /// <param name="timeoutMs"></param> public bool TryExecute(string key, int timeoutMs, LockCallback success){ //Record when we started. We don't want an infinite loop. DateTime startedAt = DateTime.UtcNow; // Tracks whether the lock acquired is still correct bool validLock = true; // The lock corresponding to 'key' object itemLock = null; try { //We have to loop until we get a valid lock and it stays valid until we lock it. do { // 1) Creation/aquire phase lock (createLock) { // We have to lock on dictionary writes, since otherwise // two locks for the same file could be created and assigned // at the same time. (ie, between TryGetValue and the assignment) if (!locks.TryGetValue(key, out itemLock)) locks[key] = itemLock = new Object(); //make a new lock! } // Loophole (part 1): // Right here - this is where another thread (executing part 2) could remove 'itemLock' // from the dictionary, and potentially, yet another thread could // insert a new value for 'itemLock' into the dictionary... etc, etc.. // 2) Execute phase if (System.Threading.Monitor.TryEnter(itemLock, timeoutMs)) { try { // May take minutes to acquire this lock. // Trying to detect an occurence of loophole above // Check that itemLock still exists and matches the dictionary lock (createLock) { object newLock = null; validLock = locks.TryGetValue(key, out newLock); validLock = validLock && newLock == itemLock; } // Only run the callback if the lock is valid if (validLock) { success(); // Extremely long-running callback, perhaps throwing exceptions return true; } } finally { System.Threading.Monitor.Exit(itemLock);//release lock } } else { validLock = false; //So the finally clause doesn't try to clean up the lock, someone else will do that. return false; //Someone else had the lock, they can clean it up. } //Are we out of time, still having an invalid lock? if (!validLock && Math.Abs(DateTime.UtcNow.Subtract(startedAt).TotalMilliseconds) > timeoutMs) { //We failed to get a valid lock in time. return false; } // If we had an invalid lock, we have to try everything over again. } while (!validLock); } finally { if (validLock) { // Loophole (part 2). When loophole part 1 and 2 cross paths, // An lock object may be removed before being used, and be orphaned // 3) Cleanup phase - Attempt cleanup of lock objects so we don't // have a *very* large and slow dictionary. lock (createLock) { // TryEnter() fails instead of waiting. // A normal lock would cause a deadlock with phase 2. // Specifying a timeout would add great and pointless overhead. // Whoever has the lock will clean it up also. if (System.Threading.Monitor.TryEnter(itemLock)) { try { // It succeeds, so no-one else is working on it // (but may be preparing to, see loophole) // Only remove the lock object if it // still exists in the dictionary as-is object existingLock = null; if (locks.TryGetValue(key, out existingLock) && existingLock == itemLock) locks.Remove(key); } finally { // Remove the lock System.Threading.Monitor.Exit(itemLock); } } } } } // Ideally the only objects in 'locks' will be open operations now. return true; } } } 

Using this code is very simple:

 LockProvider p = new LockProvider(); bool success = p.TryExecute("filename",1000,delegate(){ //This code executes within the lock }); 

Answer 2

Depending on what you do with the files (say, disk-based caching, so I assume reading as well as writing), then I would suggest trying something based on ReaderWriterLock , if you can upgrade to .Net 3.5, try ReaderWriterLockSlim as it works much better.

As a general step to reduce the potential infinite recursive case in your example, change the first bit of code to the following:

 do { // 1) Creation/aquire phase lock (createLock){ // We have to lock on dictionary writes, since otherwise // two locks for the same file could be created and assigned // at the same time. (ie, between TryGetValue and the assignment) if (!locks.TryGetValue(key, out itemLock)) locks[key] = itemLock = new Object(); //make a new lock! } // Loophole (part 1): // Right here - this is where another thread could remove 'itemLock' // from the dictionary, and potentially, yet another thread could // insert a new value for 'itemLock' into the dictionary... etc, etc.. // 2) Execute phase lock(itemLock){ // May take minutes to acquire this lock. // Real version would specify a timeout and a failure callback. // Trying to detect an occurence of loophole above // Check that itemLock still exists and matches the dictionary lock(createLock){ object newLock = null; validLock = locks.TryGetValue(key, out newLock); validLock = validLock && newLock == itemLock; } // Only run the callback if the lock is valid if (validLock) callback(); // Extremely long-running callback. } // If we had an invalid lock, we have to try everything over again. } while (!validLock); 

This replaces your recursion with a loop, which avoids the randomness of StackOverflow with infinite recursion.

Answer 3

This decision certainly looks fragile and complex. Having publicly accessible callbacks inside locks is bad practice. Why don't you let LockProvider return some kind of "lock" objects so that consumers themselves block. This separates the lock of the locks dictionary from execution. It might look like this:

 public class LockProvider { private readonly object globalLock = new object(); private readonly Dictionary<String, Locker> locks = new Dictionary<string, Locker>(StringComparer.Ordinal); public IDisposable Enter(string key) { Locker locker; lock (this.globalLock) { if (!this.locks.TryGetValue(key, out locker)) { this.locks[key] = locker = new Locker(this, key); } // Increase wait count ínside the global lock locker.WaitCount++; } // Call Enter and decrease wait count óutside the // global lock (to prevent deadlocks). locker.Enter(); // Only one thread will be here at a time for a given locker. locker.WaitCount--; return locker; } private sealed class Locker : IDisposable { private readonly LockProvider provider; private readonly string key; private object keyLock = new object(); public int WaitCount; public Locker(LockProvider provider, string key) { this.provider = provider; this.key = key; } public void Enter() { Monitor.Enter(this.keyLock); } public void Dispose() { if (this.keyLock != null) { this.Exit(); this.keyLock = null; } } private void Exit() { lock (this.provider.globalLock) { try { // Remove the key before releasing the lock, but // only when no threads are waiting (because they // will have a reference to this locker). if (this.WaitCount == 0) { this.provider.locks.Remove(this.key); } } finally { // Release the keyLock inside the globalLock. Monitor.Exit(this.keyLock); } } } } } 

And LockProvider can be used as follows:

 public class Consumer { private LockProvider provider; public void DoStufOnFile(string fileName) { using (this.provider.Enter(fileName)) { // Long running operation on file here. } } } 

Note that Monitor.Enter is called before we introduce the try (using), which means that in some host environments (such as ASP.NET and SQL Server) we have the ability to never be issued when an asynchronous exception is thrown . Hosts such as ASP.NET and SQL Server aggressively kill threads when timeouts occur. Overwriting this with Enter outside of Monitor.Enter inside try bit complicated.

Hope this helps.

Answer 4

Could you just use a named Mutex with a name derived from your file name?

Although this is not a simple synchronization primitive, it is easier than managing your own synchronized dictionary.

However, if you really want to do this, I would think that the next implementation looks simpler. You need a synchronized dictionary - either the .NET 4 ConcurrentDictionary , or your own implementation if you are on .NET 3.5 or lower.

 try { object myLock = new object(); lock(myLock) { object otherLock = null; while(otherLock != myLock) { otherLock = lockDictionary.GetOrAdd(key, myLock); if (otherLock != myLock) { // Another thread has a lock in the dictionary if (Monitor.TryEnter(otherLock, timeoutMs)) { // Another thread still has a lock after a timeout failure(); return; } else { Monitor.Exit(otherLock); } } } // We've successfully added myLock to the dictionary try { // Do our stuff success(); } finally { lockDictionary.Remove(key); } } }