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 |