A skiplist is an ordered map built from multiple linked-list levels. The bottom level stores every key in sorted order; higher levels contain progressively sparser shortcuts. A search starts at the highest level, moves right while keys remain smaller than the target, then drops down until it reaches the bottom list. This gives expected logarithmic search, insert, and delete behavior while preserving ordered iteration.
Storage engines use skiplists as memtables because they support point lookups, range scans, and cheap incremental insertion without rebalancing a tree. In an LSM engine, writes append to the WAL and then enter an in-memory ordered structure. When the memtable reaches a threshold, it freezes and flushes to an immutable SSTable. The memtable needs high write throughput while still serving reads and scans, so coarse locks quickly become a bottleneck.
A lock-free skiplist replaces global mutexes with atomic pointer updates. Inserts splice a new tower of nodes into predecessor/successor links using compare-and-swap. Readers traverse immutable key/value fields and atomic next pointers without waiting for writers. The hard part is not the search algorithm; it is safely publishing partially linked nodes, retrying when another writer wins a race, and reclaiming removed nodes only after no reader can still observe them.
Each inserted key receives a random height. Level 0 contains every key, level 1 might contain about half, level 2 about a quarter, and so on. This approximates a balanced tree without rotations. The distribution matters: too many tall towers waste memory and cache, while too few turn searches into long bottom-level walks.
Insertions first run a search that records the predecessor and successor at every level of the new node’s height. The algorithm then links level 0, which makes the key discoverable, and proceeds upward. If a compare-and-swap fails because a concurrent insert changed a predecessor’s next pointer, the operation reruns the search and tries again.
Lock-free code relies on a publication protocol. The node’s key, value, height, and internal next pointers must be initialized before the node is reachable from the shared list. After publication, readers may observe the node at any time, so fields that readers depend on should be immutable or protected by their own synchronization.
Lock-free data structures guarantee system-wide progress: if threads keep running, at least one operation completes. A single unlucky thread may still retry many times under contention. For a memtable, this is often acceptable because throughput is more important than strict per-operation latency bounds.
Removing a node from linked lists does not make it safe to free. Readers may have loaded its pointer before the unlink. Epoch-based reclamation, hazard pointers, or read-copy-update style schemes delay destruction until all readers that could have seen the pointer have exited their critical sections.
The search procedure maintains one cursor per level conceptually, but executes as a single top-down walk. At each level it advances while the next key is less than the target. When it cannot advance, it records that node as the predecessor for the level and drops down. The bottom-level successor determines whether the key already exists.
fn find_path<'g>(
head: &'g Node,
key: &Key,
guard: &'g Guard,
) -> (Vec<&'g Node>, Vec<Shared<'g, Node>>) {
let mut preds = Vec::with_capacity(MAX_HEIGHT);
let mut succs = Vec::with_capacity(MAX_HEIGHT);
let mut pred = head;
for level in (0..MAX_HEIGHT).rev() {
loop {
let next = pred.next[level].load(Ordering::Acquire, guard);
let Some(curr) = unsafe { next.as_ref() } else { break };
if curr.key < *key {
pred = curr;
} else {
break;
}
}
preds.push(pred);
succs.push(pred.next[level].load(Ordering::Acquire, guard));
}
preds.reverse();
succs.reverse();
(preds, succs)
}The insert initializes all next pointers to the successors discovered by the search. It then attempts to splice level 0. Once level 0 succeeds, the key is logically present. Higher levels are acceleration structure; if a race occurs while linking them, the operation can rerun search for that level and continue.
fn insert(&self, key: Key, value: Value) -> Result<(), InsertError> {
let guard = &epoch::pin();
let height = random_height();
loop {
let (preds, succs) = find_path(&self.head, &key, guard);
if let Some(curr) = unsafe { succs[0].as_ref() } {
if curr.key == key {
return Err(InsertError::Duplicate);
}
}
let node = Owned::new(Node::new(key.clone(), value.clone(), height));
for level in 0..height {
node.next[level].store(succs[level], Ordering::Relaxed);
}
let shared = node.into_shared(guard);
if preds[0].next[0]
.compare_exchange(succs[0], shared, Ordering::Release, Ordering::Relaxed, guard)
.is_ok()
{
for level in 1..height {
loop {
let (preds, succs) = find_path(&self.head, &key, guard);
unsafe { shared.deref().next[level].store(succs[level], Ordering::Relaxed); }
if preds[level].next[level]
.compare_exchange(succs[level], shared, Ordering::Release, Ordering::Relaxed, guard)
.is_ok()
{
break;
}
}
}
return Ok(());
}
}
}Practical lock-free skiplists usually separate logical deletion from physical unlinking. A deleted flag or marked pointer prevents future readers from treating the node as live, then cleanup removes it from each level. This avoids races where one thread finds a node while another is halfway through unlinking its tower.
Skiplists are a natural memtable for LSM engines because they preserve key order for flushes. A flush can iterate the bottom level and write sorted SSTable blocks directly. Concurrent readers can continue traversing a frozen memtable while a new mutable memtable accepts writes.
Many concurrent maps optimize point lookups but make range scans expensive or impossible. A skiplist keeps ordered traversal cheap, which is useful for time-series windows, prefix scans, schedulers, leaderboard ranges, and secondary indexes that need both updates and sorted iteration.
Search systems often buffer postings, document metadata, or lexicographically sorted terms before segment flush. A skiplist can act as the mutable front buffer when the workload needs predictable ordered drains rather than hash-table iteration.
For most Rust systems, start by isolating a mature ordered concurrent map behind a storage-engine trait. This lets the engine test WAL, flush, range-scan, and snapshot behavior without also debugging memory ordering bugs.
use crossbeam_skiplist::SkipMap;
pub struct MemTable {
rows: SkipMap<Vec<u8>, Vec<u8>>,
}
impl MemTable {
pub fn put(&self, key: Vec<u8>, value: Vec<u8>) {
self.rows.insert(key, value);
}
pub fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
self.rows.get(key).map(|entry| entry.value().clone())
}
pub fn scan(&self, start: Vec<u8>, end: Vec<u8>) -> Vec<(Vec<u8>, Vec<u8>)> {
self.rows
.range(start..end)
.map(|entry| (entry.key().clone(), entry.value().clone()))
.collect()
}
}If implementing the structure directly, make traversal APIs explicit about guard lifetimes. A loaded pointer should not outlive the epoch guard that protects it. Hiding that detail behind safe iterators is possible, but the implementation still needs a clear pin/unpin boundary.
LSM engines can simplify the concurrency model by freezing a memtable when it is ready to flush. New writes move to a fresh skiplist. Readers keep references to the old frozen table until their snapshots finish. This avoids complex in-place compaction of mutable nodes.