Concurrent set based on sorted singly linked list
Set is an abstract data structure that can store certain values, without any particular order, and no repeated values. Static sets that do not change with time, and allow only query operations while mutable setsallow also the insertion and/or deletion of elements from the set.
Wikipedia
Though set definition says it doesn’t imply particular of values it is referred to how consuming code treats set. One legitimate way (though not the most efficient one) to implement set is to use sorted singly linked list that will allow us to eliminate duplicate values. Other ways include but not limited to self-balancing binary search tree, skip lists or hash table.
As the title says we are about to explore algorithm for concurrent set. Taking this into account we can use ConcurrentDictionary<TKey, TValue> to implement concurrent set. Assuming it is done =) let’s take a look at other options. At this point .NET Framework has to support for concurrent self-balancing binary search tree or skip lists and building those is quite tricky. On the other hand concurrent sorted singly linked list is still feasible solution. This well known algorithm contains useful techniques.
For mutable sets at least the following operations must be supported: add, remove, contains. The simplest way to do this is to wrap any list modifications with lock leading to coarse-grained synchronization. However under high contention this single lock will become a bottleneck taking into account that all operations has O(n) time complexity and thus serializing them will lead to significant performance hit.
Consider list with the following contents: 1->3->4->6->7. Operations Add(2) and Add(5) even when run concurrently do not interfere as they modify distinct areas of the list 1->(2)->3->4->(5)->6->7. Add operation affects two consequent nodes where new node must be added in between. The same is true for remove operation (it affects two consequent nodes: the node to be removed and its predecessor).These nodes will be used as sync roots to make thread safe modifications of the list. In order to prevent deadlocks nodes are locked always in the same order (predecessor first and than its successor).
What if we need to add new node either at the beginning or at the end? In that case we do not have a pair nodes. To work around this the list will contain two sentinel nodes (head and tail sentinels that remain in the list forever and any value is more than value in the head and less than value in the tail). Basically any list looks like h->x0->x1->…->xn->t assuming h contains negative infinity and t contains positive infinity values.
Let’s assume we have a list: h->1->2->5->6->t. Two threads (A and B) execute operations Add(3) and Add(4) respectively concurrently. Both of them need to add new node between nodes that contain 2 and 5 (h->1->2->(x)->5->6->t). One of them will be first who will succeed in locking both nodes. After nodes are successfully locked it will proceed with adding new node (let’s assume thread A succeeded). Once thread A finished with list modifications the list will be h->1->[2]->4->[5]->6->t yet thread B is trying to lock nodes in brackets. Thread B eventually will succeed in locking but his expectations may not be true anymore as it happens in this case (node that holds value 2 no longer points to node that holds 5).
Because between the moment a thread starts his attempt to lock pair of nodes and the moment it eventually succeeds in doing so the list can be modified by other thread as it tries to lock two nodes which is not atomic. Thus after a thread succeeds in locking it must do validation that its expectations are still true.
However dealing with node removal is even more tricky. Assume we have a list h->1->2->5->6->t and thread A attempts to Add(3) concurrently with thread B trying to Remove(2) or Remove(5) and thread B succeeds to be first. In that case once thread A will lock nodes that contain 2 and 5 it may observe list that is now h->1->5->6->t or h->1->2->6->t meaning of the locked nodes is no longer in the list and adding new value in between will lead to lost value (if predecessor was removed) or resurrected value (if successor was removed and now new nodes points to it).
Thus once a thread succeeds in locking both nodes it must check that locked nodes are still not removed from the list and predecessor still points to its observed previously successor. If the validation fails the operation must fallback and start again.
Well if the node is removed from the list how do we know that? One way to make removed node’s next reference null. However this is a bad idea because in that case other thread traverses list without locks (and this is deliberate behavior) may observe unexpected null reference. For example, assume we have a list h->1->2->3->6->t. Thread A tries to Add(4) while thread B tries to Remove(2). Assume that thread A while searching for 3->6 pair of nodes (to add 4 in between) moved its current reference to the node that contains 2 and it was preempted. Then thread B succeeds in Remove(2). If thread B set removed node next reference to null once thread B will wake up it will miserably fail though there are still sought nodes in the list. Thus list node’s next reference must always be non-null.
So how do we remove nodes. We must preserve next pointers even if the node is removed. Thus the node is simply marked as removed and then its predecessor’s next is updated. Thus a node to remove is no longer reachable but still points other list nodes. Thus any traverses in-progress won’t break. From memory perspective we rely on garbage collector to reclaim memory occupied by non reachable nodes.
Because of the mechanism chosen for nodes remove we can safely traverse the list with no locks. And this is true for all three operations. Contains operation just need to validate found nodes.
Now let’s code the thing.
public class ConcurrentSet<T>
{
private readonly IComparer<T> m_comparer;
// Sentinel nodes
private readonly Node m_head;
private readonly Node m_tail;
public ConcurrentSet(IComparer<T> comparer)
{
m_comparer = comparer;
// Sentinel nodes cannot be removed from the
// list and logically contain negative and
// positive infinity values from T
m_tail = new Node(default(T));
m_head = new Node(default(T), m_tail);
}
// Adds item to the set if no such item
// exists
public bool Add(T item)
{
// Continue attempting until succeeded
// or failed
while (true)
{
Node pred, curr;
// Find where new node must be added
Find(item, out pred, out curr);
// Locks nodes starting from predecessor
// to synchronize concurrent access
lock (pred)
{
lock (curr)
{
// Check if found nodes still
// meet expectations
if (!Validate(pred, curr))
continue;
// If the value is already in the
// set we are done
if (Equal(curr, item))
return false;
// Otherwise add new node
var node = new Node(item, curr);
// At this point new node becomes
// reachable
pred.m_next = node;
return true;
}
}
}
}
// Removes item from the list if such item
// exists
public bool Remove(T item)
{
// Continue attempting until succeeded
// or failed
while (true)
{
Node pred, curr;
// Find node that must be removed and
// its predecessor
Find(item, out pred, out curr);
// Locks nodes starting from predecessor
// to synchronize concurrent access
lock (pred)
{
lock (curr)
{
// Check if found nodes still
// meet expectations
if (!Validate(pred, curr))
continue;
// If the value is not in the set
// we are done
if (!Equal(curr, item))
return false;
// Otherwise mark node as removed
curr.m_removed = true;
// And make it unreachable
pred.m_next = curr.m_next;
return true;
}
}
}
}
// Checks if given item exists in the list
public bool Contains(T item)
{
Node pred, curr;
Find(item, out pred, out curr);
return !curr.m_removed && Equal(curr, item);
}
// Searches for pair consequent nodes such that
// curr node contains a value equal or greater
// than given item
void Find(T item, out Node pred, out Node curr)
{
// Traverse the list without locks as removed
// nodes still point to other nodes
pred = m_head;
curr = m_head.m_next;
while (Less(curr, item))
{
pred = curr;
curr = curr.m_next;
}
}
static bool Validate(Node pred, Node curr)
{
// Validate that pair of nodes previously
// found still meets the expectations
// which essentially is checking whether
// nodes still point to each other and no one
// was removed from the list
return !pred.m_removed &&
!curr.m_removed &&
pred.m_next == curr;
}
bool Less(Node node, T item)
{
return node != m_tail &&
m_comparer.Compare(node.m_value, item) < 0;
}
bool Equal(Node node, T item)
{
return node != m_tail &&
m_comparer.Compare(node.m_value, item) == 0;
}
class Node
{
internal readonly T m_value;
internal volatile Node m_next;
internal volatile bool m_removed;
internal Node(T value, Node next = null)
{
m_value = value;
m_next = next;
}
}
}
This algorithm uses fine grained synchronization that improves concurrency and with lazy nodes removal allows us to traverse list with no locks at all. This is quite important as usually Contains operation is used more frequent than Add and Remove.
Hope this pile of bits makes sense to you =).