Skip list architecture — probabilistic levels, concurrency, iterators

Why architecture matters here

Skip lists fail on wrong probability tuning (memory blows up) or naive concurrency (lock contention). Architecture matters because the structure's simplicity is what makes concurrent implementations tractable.

The architecture: every piece explained

The top strip is the structure. Bottom level is a sorted linked list. Higher levels are express lanes with fewer nodes. Level selection uses coin flips (p=0.5 typical). Search starts at top, descends when it overshoots.

The middle row is operations + parallelism. Insert / delete update pointers at all held levels. Concurrency lock-free variants exist (CAS on next pointers + hazard pointers). Range iterators are cheap forward scans on the bottom level. Memory expected O(n) but constants matter.

The lower rows are use. Use cases: memtables, secondary indexes, order books. vs trees: simpler code, similar performance, easier concurrent. Ops: tuning + persistence.

End-to-end flow

End-to-end: RocksDB memtable uses skip list. Writes append + insert. Reads probe top level, descend. Range scans iterate bottom. Snapshots are cheap via versioned nodes. When memtable fills, it's flushed to an SSTable.

The invariant that lives at level zero

A skip list is a sorted singly linked list with a stack of progressively sparser lists layered on top of it. Level 0 holds every element in key order. Level 1 holds a random subset of those, level 2 a random subset of level 1, and so on, each level acting as an express lane over the one below. A search enters at the top-left sentinel, runs right until the next key would overshoot, drops a level, and repeats. The whole structure is a linked list that has been given shortcuts.

One structural fact drives everything else in this article, and it is worth stating before any analysis: the correctness invariant lives entirely at level 0. The bottom list is the sorted source of truth. Every level above it is a hint that affects only speed. A node that has been spliced into level 0 but not yet into levels 1 through 4 is still present, still returned by a lookup, still visited in order by a range scan - it is merely found more slowly, because the express lanes do not know about it yet. There is no reachable state of a partially built skip list that is wrong; there are only states that are slower than they could be.

Contrast that with a height-balanced tree. A rotation reassigns several parent and child pointers, and the configurations it passes through in the middle are not valid search trees: a reader who observes one can walk into a subtree that no longer contains the key it is looking for. The tree has no notion of a link that is merely an optimisation. That single asymmetry is why skip lists are the structure people reach for when readers and writers have to run at the same time, and it is the thread that ties together the concurrency, deletion and reclamation sections below.

Why the coin flip works: the backward analysis

When a node is inserted, its height is drawn by flipping a biased coin: keep flipping while the coin comes up heads with probability p, and the height is the number of flips. The node gets height 1 with probability 1 - p, height 2 with probability p(1 - p), height k with probability p^(k-1)(1 - p) - a geometric distribution.

The critical property is what the height does not depend on. It does not depend on the key, on the insertion order, on the current shape of the structure, or on anything an adversary can see. A binary search tree fed keys in sorted order degenerates into a linked list; a skip list fed keys in sorted order is shaped exactly as well as one fed keys at random, because the shape is a function of your random number generator and nothing else. There is no bad input, only a bad RNG. This is what buys you logarithmic behaviour with no rebalancing step at all.

Pugh's analysis of the search cost is short enough to reproduce, and it is worth doing properly rather than gesturing at "it is like a binary search". Walk the search path backwards, starting from the node you landed on at level 0 and retracing toward the top-left sentinel. At each node on that reverse path you either climb up one level or step one node to the left. You climb when the node you are standing on has a height greater than the level you arrived at - which, since you have not examined that node's coin flips above the current level, is an untouched fair-with-bias-p event. So each backward step climbs with probability p and moves left with probability 1 - p, independently.

The reverse walk is therefore a sequence of Bernoulli trials, and the expected number of steps needed to accumulate one climb is 1/p. You need to climb about log_(1/p) n levels to reach the top of the structure. Multiplying gives the expected search cost:

expected steps  =  (1/p) * log_(1/p) n
                =  ln n / ( p * ln(1/p) )

Nothing in that derivation refers to the data. The expectation is over the coin flips only, which is exactly why the bound holds for every key sequence.

p = 1/2 or p = 1/4: identical search cost, different space

Now minimise the expression above. The cost is ln n divided by p * ln(1/p), so the best p is the one that maximises p * ln(1/p). Differentiate: ln(1/p) - 1 = 0, giving p = 1/e, roughly 0.368, where the denominator reaches 1/e and the cost bottoms out at about e * ln n, or 2.718 ln n.

Evaluate the two probabilities people actually use. At p = 1/2 the denominator is 0.5 * 0.693 = 0.347. At p = 1/4 it is 0.25 * 1.386 = 0.347. They are the same number. Both give an expected cost of 2.885 ln n, which is 2 log2 n comparisons either way - p = 1/2 spends 2 steps per level over 20 levels at a million keys, p = 1/4 spends 4 steps per level over 10 levels. One half and one quarter straddle 1/e symmetrically on the logarithmic axis, and the true optimum at 1/e is only about six percent better than either, which is not worth giving up a coin flip that is a single bit test.

The tie is broken on space. The expected number of forward pointers a node carries is the sum of p^(k-1) over all levels k, which is 1/(1 - p).

Dropping from p = 1/2 to p = 1/4 buys a third fewer forward pointers at zero expected search cost. That is a genuinely free win on memory, and it is why Pugh recommended a quarter and why both Redis and LevelDB use it.

Two things the table does not show. First, variance: with fewer nodes promoted, there is less averaging, so the spread of individual search costs around the mean is wider at p = 1/4 than at p = 1/2. Tail latency degrades slightly even though the mean does not. Second, the model counts comparisons, and a machine does not. A horizontal step is a pointer dereference into a different node - very likely a cache miss - plus a key comparison. A vertical descent, in the usual layout where a node holds its forward pointers in one contiguous array, is a move within a cache line you already have. So p = 1/4 does four expensive steps per cheap descent while p = 1/2 does two. If your comparator is expensive (long string keys, collation rules) or your nodes are scattered, the abstract equality stops being an equality on real hardware and p = 1/2 can measure faster. Benchmark with your key type before assuming the paper's advice transfers.

Expected height and the tail bound that makes it reliable

An expectation on its own is a weak promise. What makes a skip list safe to deploy is that the distribution has a very thin tail, and the argument is a one-line union bound.

The probability that any given node reaches height at least k is p^(k-1) - it needed k - 1 consecutive heads. With n nodes, the probability that some node reaches height at least 1 + c * log_(1/p) n is at most

n * p^( c * log_(1/p) n )  =  n * n^(-c)  =  n^(1 - c)

Set c = 3 and the probability that the structure is more than three times its expected height is at most 1/n^2. At a million keys that is one in a trillion. The failure probability does not merely stay small as the structure grows - it shrinks polynomially. Bigger skip lists are more reliable than small ones, which is the opposite of the intuition people carry over from hash tables.

Two practical consequences follow. The first is that you can hard-cap the level count. Implementations pick MaxLevel = log_(1/p) N for the largest N they expect and clamp any draw above it. Redis uses ZSKIPLIST_MAXLEVEL = 32 with p = 0.25, which covers 4^32 = 2^64 elements; LevelDB's memtable skip list uses a height cap of 12 with a branching factor of 4, covering about 16 million entries, which is well past any memtable size worth flushing. Clamping costs nothing measurable because the probability mass above the cap is where the tail bound already says nothing lives.

The second is that a skip list needs a real random source only in the weakest sense. A cheap xorshift or a counter-based hash of the key is fine, and many implementations derive the level from bits of the key's hash so that the same key always lands at the same height - convenient for reproducible tests. The one thing to avoid is a generator whose output an adversary can predict when the keys are attacker-supplied, since predicting the RNG is the only way back to a degenerate shape.

Search, insert and delete: the update vector

Search starts at the head sentinel at the highest currently occupied level. At each level, advance while the next node's key is strictly less than the target; when the next key would meet or overshoot the target, drop one level. At level 0 the node to the right is either the target or its successor - which is also exactly what a lower-bound or range-start query wants, so the same code path serves point lookups and range scans.

Insert runs the identical search, but records along the way an array update[0..maxLevel] holding, for each level, the last node visited at that level - that is, the node whose forward pointer at that level will have to change. That array is the entire bookkeeping. There is no rebalancing pass afterwards, no parent pointers, no colour bits, no height fields to recompute up the spine. Draw a random level, then splice.

Delete reuses the same update vector: at each level where update[i].forward[i] is the victim, point it past the victim. Then lower the list level while the top levels are empty.

MAXLEVEL, P = 32, 0.25

def random_level():
    lvl = 1
    while random() < P and lvl < MAXLEVEL:
        lvl += 1
    return lvl

def _descend(sl, key):
    # search; returns (node before target at level 0, update vector)
    update = [None] * MAXLEVEL
    x = sl.head
    for i in range(sl.level - 1, -1, -1):
        while x.forward[i] and x.forward[i].key < key:
            x = x.forward[i]          # horizontal: a dependent load
        update[i] = x                 # vertical: stays in this node
    return x, update

def insert(sl, key, val):
    x, update = _descend(sl, key)
    nxt = x.forward[0]
    if nxt and nxt.key == key:
        nxt.val = val                 # plain update, no structural change
        return
    lvl = random_level()
    if lvl > sl.level:                # new levels start at the sentinel
        for i in range(sl.level, lvl):
            update[i] = sl.head
        sl.level = lvl
    node = Node(key, val, lvl)
    for i in range(lvl):              # bottom-up: level 0 first
        node.forward[i] = update[i].forward[i]
        update[i].forward[i] = node   # each line is one pointer store

def delete(sl, key):
    x, update = _descend(sl, key)
    victim = x.forward[0]
    if not victim or victim.key != key:
        return False
    for i in range(sl.level):
        if update[i].forward[i] is victim:
            update[i].forward[i] = victim.forward[i]
    while sl.level > 1 and sl.head.forward[sl.level - 1] is None:
        sl.level -= 1
    return True

That is the whole data structure in about forty lines, with no case analysis. A red-black tree's delete-fixup alone is longer and has six cases that are famously easy to get subtly wrong. The brevity is not a cosmetic virtue - it is the reason a concurrent version is writable by a mortal, and the reason Redis chose one over a balanced tree.

Note also what iteration costs. A forward range scan is a walk along level 0: no traversal stack, no successor computation, no parent pointers. A balanced tree gets the same only by threading its leaves, which is an extra invariant to maintain through every rotation. This is why ZRANGE is cheap in Redis and why flushing a memtable to a sorted file is a single linear pass.

No rotations, so insertion becomes independent CAS operations

Look again at the insert loop above. The structural mutation is update[i].forward[i] = node, repeated once per level, bottom-up. Each iteration touches exactly one pointer in one node. Replace each assignment with a compare-and-swap and you have the skeleton of a lock-free insert:

level 0:  node.next = succ0 ; CAS(pred0.next, succ0, node)   <-- the linearization point
level 1:  node.next = succ1 ; CAS(pred1.next, succ1, node)   <-- pure optimization
level 2:  node.next = succ2 ; CAS(pred2.next, succ2, node)   <-- pure optimization

The moment the level-0 CAS succeeds, the key is in the map. That single instruction is the linearization point of the whole operation: every reader from that instant onward will find the node, because level 0 is the source of truth. Everything after it is speed work. If a higher-level CAS fails because a neighbour changed underneath, you re-search at that level and retry that level only - you never unwind level 0, and there is no undo path to write. If the thread is preempted, migrated, or killed outright between the level-0 CAS and the level-2 CAS, what remains is a perfectly legal skip list in which one node drew a height it did not fully claim. Nothing needs repair. Nobody has to notice.

Now write the same paragraph for an AVL or red-black tree. The insert finds a leaf, links it, and then rebalances. A single rotation reassigns three to six child and parent pointers across several distinct nodes, and it must appear atomic, because the intermediate configurations are not valid search trees - a concurrent reader descending through a half-completed rotation can miss a key that is unambiguously present. There is no such thing as a partial rotation that is merely slower. The known ways out are multi-word CAS (not available on real hardware without software emulation), or a helping protocol in which a reader that stumbles into an in-progress rotation completes it on the writer's behalf, which requires every intermediate state to be encoded in the nodes themselves. Lock-free balanced trees exist in the literature; they are long, delicate, and largely absent from production runtimes. That gap is the entire reason skip lists are the concurrent ordered map of choice.

The bottom-up ordering is not arbitrary, incidentally. Linking low levels before high ones preserves the invariant that a node present at level i is present at every level below i, so a reader descending from level 3 to level 2 can never land on a node that has vanished from the lane it descended into.

One caveat on contention, because the shape differs from the cache case. Skip list writes spread their CAS traffic across many nodes, and only searches that begin at the very top touch the head sentinel's high-level pointers. This is the opposite of a strict LRU list, where every single hit must store to the one head sentinel - the analysis of that failure mode, along with lock striping, CLOCK approximation and deferred read buffers, belongs to the LRU cache deep-dive and is not repeated here.

Logical deletion, marker nodes, and the lost-insert race

Insertion was the easy half. Deletion is where naive lock-free linked lists break, and the bug is worth seeing in full because it is silent.

The obvious implementation is one CAS: CAS(pred.next, victim, victim.next). Consider two threads. Thread A deletes victim with that CAS. Thread B concurrently inserts X immediately after victim, with CAS(victim.next, succ, X). Both CASes look at different words, both see the values they expect, and both succeed. Afterwards pred points at succ, victim is unlinked, and X hangs off the unlinked victim where nobody will ever look. Thread B's insert returned success. The key is gone. No assertion fires, no counter disagrees, and the loss surfaces days later as a missing record.

Harris's solution, which is what ConcurrentSkipListMap implements, splits deletion into three steps that cannot interleave badly:

1. logical delete   CAS(victim.value, v, null)
                    the node is now absent to readers, still linked
2. append marker    CAS(victim.next, succ, new Marker(succ))
                    poisons the slot: no insert can attach after victim
3. physical unlink  CAS(pred.next, victim, succ)
                    victim and its marker leave together

Step 2 is the fix. A marker is a distinguished node that no insert will ever link behind; a thread attempting CAS(victim.next, ...) now finds a marker instead of the value it expected, fails, and restarts its search from a fresh predecessor. The lost-insert window is closed not by making the two CASes atomic together, but by making the second one impossible.

Step 1 is what makes deletion linearizable at a single instant while the physical work happens later, and it has a second benefit: a stalled deleter cannot wedge the structure, because any thread that traverses a null-valued node helps by attempting steps 2 and 3 itself. That helping is what makes the implementation lock-free in the technical sense - some thread always makes progress, even if the thread that started the deletion has been descheduled indefinitely.

Upper levels are unlinked opportunistically by whichever searching thread notices an index entry pointing at a deleted node. Nothing has to happen promptly. An orphaned level-3 link is a correctness non-event; the search that follows it lands on a dead node, ignores it, and continues at level 0. Once again the asymmetry does the work: the bottom level must be exact, the upper levels merely tidy.

The reclamation problem you inherit

Lock-free removal answers "when is the node unlinked". It does not answer "when may I free the memory". A reader can load a pointer to victim a nanosecond before it is unlinked and be about to dereference it. Free the node and you have a use-after-free; free it into a slab allocator that recycles addresses and you get the ABA problem, where a CAS that ought to have failed succeeds because a different node landed on the same address with the same bit pattern. This is not a corner case - it is the normal outcome under load.

In Java the problem is invisible, and that is the single biggest reason ConcurrentSkipListMap is a readable class while its C++ equivalents run to thousands of lines. The garbage collector is the reclamation scheme: a node stays alive precisely as long as some thread holds a reference to it, which is exactly the condition safe reclamation requires. You get it for free and never think about it.

Outside a managed runtime you must supply the scheme yourself, and there are three families.

Epoch-based reclamation

A global epoch counter advances periodically. On entering a critical section a thread publishes the epoch it observed; on leaving, it publishes that it is quiescent. Retired nodes are filed under the epoch in which they were retired and freed only once every thread has been seen past that epoch. The read side is close to free - one relaxed store on entry, one on exit, no per-pointer work - which is why EBR is the default in high-throughput C++ structures. The failure mode is memory, not correctness: a single thread that stalls inside a critical section, whether blocked on a syscall, descheduled by the OS, or paused at a debugger breakpoint, pins the epoch and the retire lists grow without bound. Memory usage becomes hostage to the slowest participant. This is what people mean when they say EBR is not lock-free with respect to space.

Hazard pointers

Each thread publishes the specific pointers it is currently dereferencing into per-thread slots. A retiring thread scans all published slots and frees only what nobody has claimed. Outstanding garbage is bounded by threads times slots per thread, so memory is genuinely bounded regardless of stalls. The price lands on the read path: every hop must store a hazard pointer, issue a store-load fence, then re-validate that the pointer is still linked before dereferencing it. Skip list search is nothing but hops - twenty of them at a million keys - so hazard pointers tax exactly the operation you were optimising. On x86 that fence is the dominant cost.

RCU and the arena escape hatch

RCU is the quiescent-state cousin of EBR, with a nearly free read side and a writer that waits for a grace period; it is the reason kernel data structures look the way they do. But the cheapest answer of all is to arrange never to free an individual node. RocksDB's memtable skip list does exactly this: it allocates nodes from an arena, never deletes anything (a delete is a tombstone insert), and drops the entire arena in one call once the memtable has been flushed. Append-mostly plus bulk-free removes the reclamation problem instead of solving it. If your workload allows that shape, take it - it is worth more than any reclamation scheme.

The deterministic 1-2-3 skip list

Munro, Papadakis and Sedgewick showed you can drop the randomness entirely and impose a structural invariant instead: between any two consecutive nodes of height at least i+1, there must be exactly 1, 2 or 3 nodes of height exactly i. Gaps are never empty and never longer than three.

Maintaining it is a local repair. On insert, if a gap grows to 4, promote the middle node one level, which restores the invariant at level i and may cascade upward if the promotion overfills the gap above. On delete, if a gap shrinks to 0, borrow a node from a neighbouring gap or merge two gaps. The result is a skip list with a worst-case logarithmic height rather than an expected one, and no random number generator anywhere. Structurally it is a 2-3-4 tree - equivalently a B-tree of order 4 - flattened into linked-list form, which is a useful way to hold it in your head.

Use it where a probabilistic guarantee is not acceptable: hard real-time systems that must bound the worst case per operation, or adversarial settings where the attacker may be able to observe or influence your entropy source.

And notice the symmetry with everything above. The promotion step changes several nodes' heights and neighbour relationships together, and it must appear atomic, because a reader observing a half-finished promotion can descend into a gap that no longer means what it meant a moment ago. Determinism reintroduces precisely the multi-node restructure that rotations imposed on balanced trees. You buy a worst-case bound and you pay with the property that made skip lists interesting in the first place - which is why there is essentially no lock-free deterministic skip list in production anywhere.

Cache behaviour versus B-trees

Skip lists lose single-threaded lookups to B-trees, and it is important to understand why rather than to argue about it, because the reason also tells you when the loss does not matter.

A skip list search is a chain of dependent loads. Each hop reads a node's key, compares it, and follows a pointer whose address was unknown until the previous load retired. The processor's out-of-order engine cannot start the next load early and the hardware prefetcher has nothing to predict, so the misses cannot overlap. At a million keys with p = 1/2 a search performs roughly 40 comparisons across about 20 distinct nodes. If those nodes are scattered across a heap - and after a few hours of insert and delete traffic they will be - most of those accesses are L3 or DRAM. At around 80 nanoseconds per DRAM miss, twenty serialised misses is about 1.6 microseconds of pure latency that no amount of instruction-level parallelism removes.

Now do the B-tree arithmetic. A 4 KB node holding 16-byte entries (an 8-byte key plus an 8-byte pointer or value) holds about 256 of them, so the fanout is 256. At a million keys, log_256(10^6) is about 2.5: a root, one internal level, and a leaf. Three node accesses instead of twenty. Better still, each node is contiguous, so the search inside a node runs over 64 sequential cache lines that the prefetcher streams happily, and the comparisons vectorise. The dependent-miss chain is three deep, not twenty.

That ratio is why B-trees own on-disk indexing, where the comparison is three I/Os against twenty, and it is why they usually still win in memory: the structure matches how memory is actually delivered, in blocks rather than words. Cache-conscious variants push it further by sizing nodes to a cache line or a page and eliminating pointers within a node.

The skip list's counter-argument is never raw lookup throughput. It is that (a) an insert never splits or merges a node, so a writer never has to lock a subtree against readers; (b) range iteration is a bare pointer walk with no stack; and (c) the code is short enough that a correct concurrent version is achievable. If your workload is read-mostly and single-threaded, use a sorted array with binary search, or a B+tree. Skip lists earn their place when writes run concurrently with reads. For the storage-engine framing of the same comparison - write, read and space amplification, compaction strategy, workload fit - see LSM trees vs B-trees rather than the cache-level argument here.

A closing note on lineage: HNSW is a skip list generalised from one dimension to a metric space. It draws each node's level from the same geometric distribution, uses the sparse upper layers as express lanes for routing, and keeps all real answers at layer 0. The section above about the bottom level being the truth and the upper levels being hints transfers directly.

Where skip lists actually run

Redis sorted sets

A Redis sorted set is two structures kept in lockstep: a hash table mapping member to score, which serves ZSCORE in constant time, and a skip list ordered by score then member, which serves everything ordered. Small sets skip both and use a flat listpack until they cross a configured entry or value threshold, at which point Redis promotes them to the pair.

The reasons Redis chose a skip list over a balanced tree are on record and none of them is concurrency - Redis executes commands on a single thread, so lock contention was never a consideration. The reasons were: range operations dominate the workload and a bottom-level walk serves them directly; the implementation is dramatically simpler to write, review and debug than a red-black or AVL tree, which has real value in a codebase people audit; and memory can be tuned down by lowering p, which Redis does, running p = 0.25 with a level cap of 32.

The detail worth stealing is the span field. Each forward pointer stores how many level-0 nodes it jumps over. Summing spans along a search path yields the element's rank in logarithmic time, which is what makes ZRANK, index-based ZRANGE and ZREVRANGE cheap instead of linear. A balanced tree achieves the same with subtree-size counters, but those must be repaired after every rotation; skip list spans only change where pointers change, which is a strictly local fix during the same splice loop shown above.

LSM memtables in LevelDB and RocksDB

Both engines use a skip list as the default memtable, and the requirements line up exactly with what the structure provides. Writers must append while readers concurrently serve gets from the same memtable, so no writer may block a reader. The memtable must yield a sorted iterator when it is flushed into an SSTable, so the structure has to be ordered and cheap to scan linearly. And no rebalancing operation may ever run while an iterator is mid-walk, because that iterator is producing a file. A skip list satisfies all three; a balanced tree fails the third by construction.

RocksDB's inline variant stores the key bytes in the node itself inside arena memory, which removes one dereference per comparison, and its concurrent memtable admits many writers using one CAS per level as described above. Deletions never occur - a delete is a tombstone record inserted like any other - so the deletion protocol and reclamation machinery above are simply not needed. For the architecture around the memtable, see the LSM-tree storage engine deep-dive and LSM compaction.

java.util.concurrent.ConcurrentSkipListMap

The JDK's only concurrent sorted map, and it is a skip list for exactly the reason this article has been building toward: no practical lock-free balanced tree was known when it was written. Its internal layout separates a base list of data nodes from index nodes above them, so the hot bottom list stays compact and an entire index level can be dropped without touching data.

Three behaviours follow from the design and surprise people. Iterators are weakly consistent: they never throw ConcurrentModificationException and reflect the map at some point at or after creation, which is a direct consequence of level 0 always being a valid list. size() is O(n) and only an estimate under concurrent modification, because maintaining a counter would create the one contended cache line the whole structure exists to avoid - if you need a live count, keep a LongAdder beside the map. And get, put and remove are expected logarithmic, not constant: if you do not need ordering, ConcurrentHashMap is the faster choice and a separate article covers it. ConcurrentSkipListSet is a thin wrapper over the same map.