Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

atomic addorupdate (trying to write named locker using concurrent dictionary)

ConcurrentDictionary Pitfall - Are delegates factories from GetOrAdd and AddOrUpdate synchronized? notes that AddOrUpdate is not atomic (and can't guarantee delegates won't be run more than once).

I'm trying to implement a name locking implementation using a concurrent dictionary a la here, but where the dictionary should not grow forever, like this:

public class ConcurrentDictionaryNamedLocker : INamedLocker
{
    // the IntObject values serve as the locks and the counter for how many RunWithLock jobs 
    // are about to enter or have entered the critical section.
    private readonly ConcurrentDictionary<string, IntObject> _lockDict = new ConcurrentDictionary<string, IntObject>();
    private static readonly IntObject One = new IntObject(1);
    private readonly Func<string, IntObject, IntObject> _decrementFunc = (s, o) => o - 1;
    private readonly Func<string, IntObject, IntObject> _incrementFunc = (s, o) => o + 1;
    private readonly Func<string, IntObject> _oneFunc = s => new IntObject(1);
    private readonly Func<string, IntObject> _zeroFunc = s => new IntObject(0);

    public TResult RunWithLock<TResult>(string name, Func<TResult> body)
    {
        name = name.ToLower();
        TResult toReturn;
        lock (_lockDict.AddOrUpdate(name, _oneFunc, _incrementFunc))
        {
            toReturn = body();
            if (!_lockDict.TryRemove(name, One))
                _lockDict.AddOrUpdate(name, _zeroFunc, _decrementFunc);
        }
        return toReturn;
    }

    public void RunWithLock(string name, Action body)
    {
        name = name.ToLower();
        lock (_lockDict.AddOrUpdate(name, _oneFunc, _incrementFunc))
        {
            body();
            if (!_lockDict.TryRemove(name, One))
                _lockDict.AddOrUpdate(name, _zeroFunc, _decrementFunc);
        }
    }
}

But the problem is the AddOrUpdate is not atomic, so I'm seeing that often the entries are not being removed when there is contention. I'm fairly sure though that if AddOrUpdate were atomic the above code would do its job and entries would be removed appropriately.

Notice the use of the conditional removal by key+val extension method TryRemove(key,val) mentioned here. Also, IntObject is a simple mutable object wrapper of an int.

What are my options? Are there any concurrent dictionary implementations that have 1. atomic conditional (on key and value) removals and 2. AddOrUpdate is atomic and ensures delegates do not get run more than once?

Have any other ideas? I'd like the named locker to be fast but not have memory pressure problems given an unlimited lock namespace but with not much contention on a given name. As far as I know, string interning locking by name grows forever and never gets cleaned up and has other side effects. And mutexes are semi-slow and have various annoyances (260 char limit).

like image 414
TravisK Avatar asked Jun 25 '13 00:06

TravisK


1 Answers

It would help to see the exact code for IntValue as that is the code being run in the AddOrUpdate delegate.

I think the problem is that the code expects IntValue instances to be both:

  • Mutable in order to lock a single IntValue instance associated to each string (despite the reference count incrementing later)
  • Immutable so that comparing IntValues to a static One works as the removal criteria

If I change the code so that IntValue supports an immutable zero this seems to work:

private readonly Func<string, IntObject> _zeroFunc = s => IntObject.Zero;

...

public void RunWithLock(string name, Action body)
{
    name = name.ToLower();
    lock (_lockDict.AddOrUpdate(name, _oneFunc, _incrementFunc))
    {
        body();
        _lockDict.AddOrUpdate(name, _zeroFunc, _decrementFunc);
        _lockDict.TryRemove(name, IntObject.Zero);
    }
}

But I chose to implement the IntValue methods like this and as non-operators:

    internal IntObject Dec(int p)
    {
        var newVal = Interlocked.Decrement(ref value);
        if (newVal == 0) return Zero;
        return this;
    }
like image 118
Peter Wishart Avatar answered Sep 22 '22 02:09

Peter Wishart