这是任务:我需要根据文件名进行锁定。可能有多达一百万个不同的文件名。(这用于大规模基于磁盘的缓存)。
我希望内存使用率低,查找时间短,这意味着我需要一个GC'd锁字典。(只有正在使用的锁可以存在于字典中)。
回调操作可能需要几分钟才能完成,因此全局锁是不可接受的。高吞吐量至关重要。
我在下面发布了我的当前解决方案,但我对复杂性感到不满意。
编辑:请不要发布不正确的解决方案。例如,允许在“获取锁对象”阶段和“锁定”阶段之间从字典中删除锁的解决方案是不正确的,无论它是否是“接受”的设计模式。
还有比这更优雅的解决方案吗?
谢谢!
[编辑:我更新了我的代码,根据RobV的建议使用循环而不是递归]
[编辑:再次更新代码以允许“超时”和更简单的调用模式。这可能是我使用的最终代码。仍然与原始帖子中的基本算法相同。]
[编辑:再次更新代码以处理回调内部异常而不使锁对象变为孤立状态]
我希望内存使用率低,查找时间短,这意味着我需要一个GC'd锁字典。(只有正在使用的锁可以存在于字典中)。
回调操作可能需要几分钟才能完成,因此全局锁是不可接受的。高吞吐量至关重要。
我在下面发布了我的当前解决方案,但我对复杂性感到不满意。
编辑:请不要发布不正确的解决方案。例如,允许在“获取锁对象”阶段和“锁定”阶段之间从字典中删除锁的解决方案是不正确的,无论它是否是“接受”的设计模式。
还有比这更优雅的解决方案吗?
谢谢!
[编辑:我更新了我的代码,根据RobV的建议使用循环而不是递归]
[编辑:再次更新代码以允许“超时”和更简单的调用模式。这可能是我使用的最终代码。仍然与原始帖子中的基本算法相同。]
[编辑:再次更新代码以处理回调内部异常而不使锁对象变为孤立状态]
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. (i.e, 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;
}
}
使用示例
LockProvider p = new LockProvider();
bool success = p.TryExecute("filename",1000,delegate(){
//This code executes within the lock
});