How to create a Lockfree collection of collection

Question

I need to create a collection of collections. The collection is called by multiple threads to add items and lookup items. Once added the items will not be removed. Currently, while adding elements I need to take a lock on the entire collection. Is there a way around it to make it lockfree. Or is there a better datastructure or pattern that I can use? Here is a simplified version of my code:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem(string s, int k, int v)
{
    ConcurrentDictionary<int, int> subDict;
    if (dict.TryGetValue(s, out subDict))
    {
        subDict[k] = v;
    }
    else
    {
        lock (dict)
        {
            if (dict.TryGetValue(s, out subDict))
            {
                subDict[k] = v;
            }
            else
            {
                subDict = new ConcurrentDictionary<int, int>();
                subDict[k] = v;
                dict[s] = subDict;
            }
        }
    }
}

Answer 1

Method ConcurrentDictionary.GetOrAdd is thread safe (although not atomic). It guarantees that the returned object is the same for all threads. Your code could be rewritten as:

void AddUpdateItem(string s, int k, int v)
{
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>());
    subDict[k] = v;
}

Answer 2

You can make a hashtable lock-free, by using immutability, but it isn't likely to be efficient if there's contention. Basically, you need a dictionary-content class that can be atomically swapped. You build a copy of the current-content, with the one change made, then use a compare-and-swap primitive to exchange it with the existing version. If compare-and-swap fails, start over with the copying step.

You might be able to atomically swap just a single hash-bucket, which would make contention much less common, and retry cheaper. (ConcurrentDictionary does already use this optimization, to reduce lock contention) But growing the number of buckets will still require the method outlined above.

Have a look at Eric Lippert's blog, in which he covers immutable data structures. He's got a nice example of a binary tree, which should show you the techniques needed to make a lockless hash-table.

Answer 3

Are you using tasks or threads in your code ? In any case, ConcurrentDictionary is designed to be thread-safe. You don't need to use locks while add or remove elements. Link from MSDN How to: Add and Remove Items from a ConcurrentDictionary explains how to use it.

Answer 4

If you speculatively create the sub-dictionary, there is a simpler solution:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem( string s, int k, int v )
{
    ConcurrentDictionary<int, int> subDict;

    while ( true )
    {
        if ( dict.TryGetValue( s, out subDict ) )
        {
            subDict[ k ] = v;
            break;
        }

        // speculatively create new sub-dictionary
        subDict = new ConcurrentDictionary<int, int>();
        subDict[ k ] = v;

        // this can only succeed for one thread
        if ( dict.TryAdd( s, subDict ) ) break;
    }
}

Answer 5

before you go down the road of implementing a lockless collection have a look at ReadWriteLock which solve your problem. If it doesn't (e.g. because you have heavy write contention) there isn't really a one-size-fits-all approach.

One technique I ave used in the past is to have a thread dedicated thread to managing the collection and use Interlocked.Exchange to marshal new objects to that thread and an immutable collection out. With this approach your writer threads are managed in a separate list that you need to lock whenever a writer is created or destroyed, so this only works if that is a rare event.