We are the IEnumerable, resistance is futile

In my last blog: cache-synchronization-problem I talked about the genesis of our cache problems. This type of problems is inherent to using IEnumerable in multithreaded scenarios.

Nevertheless we had the multithreaded constrain and our MPT (MasterPlayerTable) had to expose its internal MPR (MasterPlayerRecord) collection to all consumers in a concurrency friendly and thread safe manner. My first thoughts where heading in a lock-free implementation. While this sounds great (although "lock-free" is becoming more and more a buzzword) there are some undeniable drawbacks:

1. It is extraordinary hard to implement a really working lock-free algorithm
2. It is even harder to debug problems coupled with lock-free implementations
3. I was not aware of any existing lock-free implementation of a data structure with an IEnumerable notion
   

A bit research on that topic didn't bring any results. The best of lock-free structures I was aware of is a single writer multiple reader stack/queue implementation and that was not nearly good enough. Well even if it was I honestly doubt that I would  use it for something as complex as the Borg Server.

It was time for good old paper & pen problem analysis. The analysis confirmed it was absolutely mandatory to let one thread add and multiple threads remove items from the MPT - most of the others needed  a read only access just iterating the records.

I thought about implementing the synchronization inside Add() and Remove() with a ReaderWriterLockSlim lock which would fit nicely in the single writer/multiple readers scenario. This would be a fairly easy change except that it did nothing to eliminate the biggest problem of most other threads which where iterating the MPT records.

To summarize if you lock the collection during add or remove you have to lock it during enumeration as well. Failing to do so causes exceptions in threads enumerating the collection while it is changed. Locking the collection during enumeration causes to high thread contention. This was a lose lose situation.

A man's got to do, what a man's got to do. The IEnumerable had to go! It had to be replaced with something organized into a collection of records, that could be iterated over without locks and wouldn't throw exception if individual records are removed or added.

And before I forget to mention, a custom IEnumerable implementation which would provide separate copies of the underlying enumerator would work. The threads iterating the collection wouldn't lock on it but producing constant copies of the collection (enumerator) would be an overkill in such a heavy threaded environment.

The solution was a linked list. Organizing all the records in a linked list provided similar capabilities as a collection has. Of course the consumers couldn't use the foreach anymore but using something like:

                LinkedNode node = context.Mpt.First;
                while (node != null)
                {

                    Character c = (Character)node.Value.pCharacter;

                    // do something

                    node = node.Next;
                }

 

So how did that produce thread safety, if a new element was added that would leave any thread iterating through the list in a inconsistent state? Well yes and no. First this solution is not protecting against iterating over an removed node not even against missing a newly added node. But ... it is thread safe: a thread adding a new node couldn't leave the other thread with an inconsistent pointer. That means even if the thread fetching the next node in the list is preempted and another thread changes the next pointer due to adding a new node it can not be preempted back in the middle of a reference assignment leaving the 1st thread with a garbage pointer. Reference assignments are atomic in nature.

The most dangerous place is the Add() inside the LinkedList implementation. And before you ask, yes it was necessary to implement a custom list since the .NET LinkedNodeList would reset the nodes previous and next pointers after removing the node form the list. So if a node in the middle was removed any threads currently using the very same node would lose the connection to the next node in the list.

The LinkedList.Add() looks like:

        ///

        /// Adds a new node to the list.
        ///
        ///
        public LinkedNode Add(T item)
        {
            LinkedNode previous = null;
            LinkedNode node = new LinkedNode(item, null);
            lock (locker)
            {
                if (nodes.Count > 0)
                {
                    previous = nodes[nodes.Count - 1]; //  this is the last node in the list
                    previous.Next = node;
                }
                node.Previous = previous;
                nodes.Add(node);
            }
            return node;
        }

The hot spot is the line containing previous.Next = node; and nodes.Add(node); where one could argue that the whole solution would fail if thread 1 assigns the new node to previous.next, thread 2  fetches the next node before thread 1 updates the new node previous and next properties.

While the reasoning is 100% correct the solution still works:

1. No one is iterating backwards - this  functionality is not exposed. So obtaining a node with invalid previous pointer during iteration is not hurting anyone.

2. Multiple threads adding new nodes (which is not happening) are protected by the lock, the same is true for simultaneously adding and removing nodes

3. The most dangerous situation is that one thread obtains a new node (the line previous.next = node; is executed) before the node is added to the list. We are on the safe side here as well. Our implementation is only adding new nodes at the end of the list, so all threads obtaining the reference to the new node having null in the Next field work as expected since the Next field simply must be null as it is the last element in the list.

Note that the above solution works only due to insights in other other Borg parts consuming those features. It is no way generic and works only due the fact that the list is a) unsorted, b) iterated forward only and c) new nodes are added to the end.

After the implementation was finished testing showed that all the thread concurrency issues where solved and our MPT was lean and mean as one could only hope for.