What Are Skiplists Good For?

A skiplist is a randomized data structure that acts as a substitute for binary search trees, handling search in O(log n).

• It layers multiple levels of express lanes on top of a linked list to search quickly.
• Its implementation is relatively simple, making it well-suited for lock-free concurrent implementations.

Antithesis runs customer software repeatedly to find bugs, and this process—through choices and fault injection—creates a branching tree of timelines.

The problem was that they were putting this data into Google BigQuery at the time.

• BigQuery is strong at large-scale scans and aggregation, but point lookup is slow.
• Storing the tree with parent pointers means queries like ancestor tracing require repeated lookups equal to the depth, which is inefficient.
• Splitting the data between an OLTP DB and BigQuery was also an option, but it introduces 2PC and consistency issues.

The solution was a skiptree.

• A separate SQL table is kept for each level: tree0, tree1, tree2...
• Each row has the current node's next_level_ancestor and ancestors_between, a list of the nodes in between.
• To find a node's ancestors, you climb up through the tables performing only a fixed number of JOINs.

For example, to find the ancestors of node I, you start at tree0, jump to tree1 while collecting the intermediate node G, then climb up to A, ultimately obtaining [G, C, A].

Thanks to this approach:

• Ancestor tracing became possible without recursive queries.
• The number of skip levels was tuned to stay just under BigQuery's planner limit.
• The scan cost of each query didn't grow exponentially either, staying at roughly 2x the level of a normal table scan.

The SQL was long and unwieldy to look at, but it wasn't written by hand—it was generated by a JavaScript compiler.

This structure was used at Antithesis for about 6 years, and was later moved to their own analytics DB, Pangolin, which came to support more efficient tree queries.

The core message is that even an uncommon data structure can save huge amounts of time and cost if it fits the actual problem. Skiplists, skiptrees, and skipgraphs are all connected, and even a simple implementation can be plenty useful.