Skip List Design

So, let's start with the skip list.

The skip list has only one use case – invocation of find_or_insert() function for a game state, expected ratio of find-to-insert is above 1 (i.e. there will be a fair amount of attempts to insert already present state). An attempt to insert an already present item is a logically read-only operation, while an attempt to insert an absent item is a logically mutating operation.

No items are removed during concurrent phase. This greatly simplifies our task, especially in a non garbage-collected environment.

Total number of items is large and unknown in advance, so the data structure must be dynamic and adaptive.

Move on to Lockfree Reader Pattern