Lock-Free Sorted Range Queries: ConcurrentSkipListMap & SkipLists in Java

Suppose you are building a distributed time-series database for a cloud metrics platform.

64 worker threads constantly write timestamped performance metrics into a shared in-memory map. Simultaneously, 64 HTTP reader threads query metric ranges (fetch all readings between 10:00:00 AM and 10:05:00 AM).

You need a data structure that keeps entries sorted by timestamp while handling concurrent multi-threaded reads and writes.

TreeMap keeps keys sorted, but Red-Black tree rotations alter ancestor and parent pointers across large portions of the tree. Synchronizing a TreeMap requires acquiring a global mutual exclusion lock, forcing 63 CPU cores to stall whenever a thread inserts a timestamp.

ConcurrentHashMap handles lock-free multi-threaded writes, but hash buckets destroy timestamp ordering. Range queries become impossible without scanning every bucket.

To solve multi-threaded sorted range queries without global locks, Java provides ConcurrentSkipListMap.

Why You Need This in Real Life

ConcurrentSkipListMap and ConcurrentSkipListSet power concurrent ordered architectures:

Concurrent Range Queries: Executing subMap(fromKey, toKey) concurrently across dozens of threads without blocking writes.
In-Memory Indexes: Databases like RocksDB and Cassandra use SkipLists (MemTables) to handle lock-free concurrent writes before flushing sorted data to disk.
Lock-Free Sorting: Achieving $O(\log N)$ expected search, insertion, and deletion speeds using atomic CAS (Compare-And-Swap) pointer updates.

Why Red-Black Trees Fail Under Concurrency

Why can’t we build a lock-free ConcurrentTreeMap using Red-Black trees?

Because a single insertion into a Red-Black tree can trigger tree rotations that modify root pointers, parent links, and child nodes across multiple levels of the tree simultaneously.

Updating multiple non-adjacent object pointers atomically across threads requires complex multi-word locks.

SkipLists solve this by replacing rigid tree balances with probabilistic multi-level linked lists.

How a SkipList Works

A SkipList is a sorted linked list augmented with parallel express lane pointer levels.

Level 3:  [ 10 ] -----------------------------------------> [ 50 ] -----------------> null
            |                                                 |
Level 2:  [ 10 ] ---------------------> [ 30 ] -------------> [ 50 ] --------> [ 70 ] -> null
            |                             |                   |                 |
Level 1:  [ 10 ] ---------> [ 20 ] ----> [ 30 ] ----> [ 40 ] -> [ 50 ] -> [ 60 ] -> [ 70 ] -> null

Searching in $O(\log N)$ Time

To search for key 60:

Start at top express level (Level 3) at 10. Move right to 50. Since $60 > 50$ , stay on 50. Next express node is null. Drop down to Level 2.
At Level 2 node 50, move right to 70. Since $60 < 70$ , do not jump to 70. Drop down to Level 1.
At Level 1 node 50, move right to 60. Found match!

Instead of inspecting every node sequentially, search jumps over large sections of the list along high-level express lanes.

Probabilistic Tower Heights

How does a SkipList decide how many express levels a new node receives during insertion?

Through a random coin flip algorithm.

When a new node is inserted:

It is always added to the base list (Level 1).
Flip a coin (50% probability). If heads, promote the node to Level 2.
Flip again. If heads, promote to Level 3.
Continue until a tails result occurs.

$\text{Probability of height } h = \left(\frac{1}{2}\right)^{h-1}$

Statistically, 50% of nodes exist at Level 1, 25% at Level 2, 12.5% at Level 3, and so on. This probabilistic balance mimics a balanced binary search tree without requiring tree rotations.

Lock-Free Pointer Updates via CAS

Inserting a node into a SkipList only alters horizontal .next pointers at each level.

Level 1 Insert: Node 25 between Node 20 and Node 30

Step 1: Set newNode.next = node20.next (points to 30)
Step 2: CAS update node20.next from 30 to newNode (25)

Because node insertions only modify adjacent horizontal pointers, ConcurrentSkipListMap uses atomic CAS instructions (VarHandle.compareAndSet) to insert nodes without acquiring thread locks.

If two threads attempt to insert nodes at the exact same location simultaneously, one CAS succeeds immediately and the other retries without corrupting list structure.

Performance Comparison: `TreeMap` vs `ConcurrentSkipListMap`

Metric	`TreeMap` (Synchronized)	`ConcurrentSkipListMap`
Data Structure	Red-Black Self-Balancing Tree	Probabilistic Multi-Level SkipList
Thread Locking	Global Mutual Exclusion Lock	Lock-Free CAS Pointer Updates
Concurrent Reads	Blocked during write operations	Zero-lock parallel traversal
Search Time	Exact $O(\log N)$	Probabilistic Expected $O(\log N)$
Range Queries	Fast $O(\log N)$ (single-threaded)	Fast $O(\log N)$ (multi-threaded concurrent)

Quick Summary

Red-Black tree rotations make fine-grained locking difficult, causing TreeMap to bottleneck multi-threaded applications.
SkipLists build parallel express lane linked lists using random coin-flip level promotion.
ConcurrentSkipListMap uses CAS atomic updates on horizontal node pointers, delivering lock-free sorted range queries across 64+ CPU cores.

References & Further Reading

OpenJDK. JEP 431: Sequenced Collections (Java 21 Specification). OpenJDK JEP Standard.
Oracle Corporation. Java SE 21 API Documentation: java.util.SequencedCollection. Oracle Docs.
Oracle Corporation. Java Platform, Standard Edition 21 Release Notes. Oracle Docs.