Efficient ordered single-writer multi-reader list with "add" and "bring to front" operations

Question

I'm looking to implement a collection that needs to support only two operations:

1. AddOrUpdate: Insert item into collection if it doesn't exist; otherwise, move it from whatever the current position is to the head of the list
2. Enumerate: Enumerate items in the order they were inserted/updated in

Any type of delete operation is not quired for now.

There will be a single writer thread. Writing must be O(1) and wait-free - optimising for write speed is key here.

There will be multiple reader threads.

• Read efficiency is slightly less crucial, so having overhead here is more tolerable.
• Once a reader acquires an enumerator, it must be able to enumerate the items in the collection in the same order as it was at the exact time the enumerator was acquired. Subsequent changes to the collection must not impact the enumerator's items or their order
  • Example: Say an int collection is currently [1,2,3], and an enumerator is acquired
  • Shortly thereafter, a writer thread pushes 3 to the front, so the collection in its latest state is now [3,1,2]
  • The previously acquired enumerator must still enumerate items in the same order as it was at the time it was acquired, i.e. [1,2,3]
• Assume that these enumerators can and will be deterministically disposed of when done

I'm specifically looking to implement this in C#, so general efficiency must take GC into account.

Is there any known data structure that would seem to fit this bill very well? Does anyone have any thoughts on an efficient implementation, otherwise?

---

My general thought so far has been a structure roughly:

1. Maintain a Map<T, Node>, simply for O(1) retrieval of existing items
2. Maintain the data as a relatively plain either single or double linked list with a node structure roughly as follows:

class Node<T>
{
   public readonly T Item;
   public readonly ulong Version;
   public Node<T>? Next;
   public ulong LastIncludedVersion
}

Inserting a new value should be trivial - just replace the head node, and set the new head's version to the prior head's version + 1.

Moving an existing value of the front could then be done by

1. Finding the node-to-be-moved, then setting its LastIncludedVersion to current head + 1
2. Cloning and re-inserting the node as the new head

Enumerators could then grab a hold of the head node, and start enumerating; if they encounter any node whose LastIncludedVersion is < the version of the head node they got, they can omit it.

I believe this should work, but it leaves the big issue of: Who, what or when do we remove nodes who've been marked for deletion (i.e. have LastIncludedVersion set)?

Generally, my hunch would be to leave it up to readers; when an enumerator is created, it inserts its head version into some shared ordered set. When it's done enumerating, it removes itself again from this yet, and then enumerates the entire list again, removing any node for good whose LastIncludedVersion is smaller than the minimum head version of all active readers.

The problem of course is.. that would be horribly inefficient. If there are no pending removals, an enumerator would still need to enumerate the entire list again for no good reason.

Maybe I can tweak this part to be more efficient - but I'm curious to hear if there are any more elegant approaches.

Answer 1

There is a trivial way to achieve $O(1)$, wait-free writes: use an append-only, log-structured data structure. Specifically, have an append-only linked list of AddOrUpdate log records.

Each time the caller invokes AddOrUpdate, you just append a log record containing the parameter to AddOrUpdate (the item that was added/updated).

Each time the caller invokes Enumerate, you stash a pointer to the current log head, then walk the entire list to build up the answer to the Enumerate operation (e.g., maintaining a list and moving items to the front as you read each log record), stopping when you reach the stashed pointer.

This will achieve $O(1)$ time writes and $O(N)$ time reads.

Of course, this is a rather trivial and silly solution. But it could be the foundation for an optimized version of this data structure. For instance, each time an Enumerate operation finishes, you can replace the entire log up to the stashed pointer with the collection built up by the Enumerate operation, and do an atomic compare-and-swap to change the head of the log to point to this collection followed by log entries starting at the stashed pointer. This can all be implemented in a way that supports multi-threading and ensures writes remain wait-free.

See also log-structured filesystems.