GoKawiilWill Wilson CEO What are skiplists good for? Antithesis
A while back, I joined Phil Eaton’s book club on The Art of Multiprocessor Programming, and the topic of skiplists came up.
For most of my career, skiplists had always seemed like a niche data structure, with a rabid cult following but not a whole ton of applicability to my life. Then six or so years ago, we encountered a problem at Antithesis that seemed intractable until it turned out that a generalization of skiplists was exactly what we needed.
Before I tell you about that, though, let me explain what skiplists are (feel free to skip ahead if you already know them well).
A skiplist is a randomized data structure that’s basically a drop-in replacement for a binary search tree with the same interface and the same asymptotic complexity on each of its operations. Some people like them because you can produce relatively simple and understandable lock-free concurrent implementations, and others like them as a matter of taste, or because they enjoy listening to bands that you’ve totally never heard of.
In implementation terms, you can think of them roughly as linked lists plus “express lanes”:
You start with a basic linked list, and then add a hierarchy of linked lists with progressively fewer nodes in them. In the example above, the nodes in the higher-level lists are chosen probabilistically, with each node having a 50% chance of being promoted to the next level.1 This helps with search, because you can use the higher-level lists to skip more quickly to the node you want: For (much) more on skiplists, see The Ubiquitous Skiplist.
Here we’ve found the node with an ID of 38 by starting at the top level and working downwards. At each level we advance until the next node would have an ID that’s too high, then jump down a level.
In a regular linked list of n nodes, finding a node would take O(n) time, because you’re walking through the nodes one by one. Skiplists let you jump levels, with each level halving the number of nodes you need to check, so you end up finding the node in O(log n) time.
This is all very nice, but after reading about this data structure I literally never thought about it again, until one day we encountered the following problem at Antithesis…
... continue reading