In the LSM-tree series, the MemTable needs two properties that pull in different directions: it should preserve key order for range scans and flushes, but it should also accept concurrent reads and writes without turning one mutex into the hottest point in the process.

That is why the Rust implementation in Part 2 uses crossbeam-skiplist::SkipMap.

A skip list is a good fit because it gives us an ordered structure without tree rotations. A lock-free implementation can publish small pointer changes with atomic operations and let competing threads retry when they lose a race. The difficult part is making traversal, insertion, removal, and memory reclamation all correct at the same time.

This post looks at those mechanics using the current crossbeam-skiplist implementation as the reference.

Skip lists: a sorted list with express lanes

At level 0, a skip list is an ordinary sorted linked list containing every key:

level 0:  1 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34

Some nodes also appear in sparser higher levels:

level 3:  1 -----------------------> 21
      level 2:  1 ----------> 8 ---------> 21
      level 1:  1 -> 3 -----> 8 -> 13 --> 21 -> 34
      level 0:  1 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34

A search starts high, moves forward while the next key is still below the target, then drops down. With randomized tower heights, search, insertion, and deletion are O(log n) in expectation, while expected space remains O(n). The worst case can still degrade toward a linear walk.

The same structure is attractive for concurrency because there is no global rebalance step. Inserting a key mostly means installing a new node between nearby predecessor and successor links.

Lock-free still means synchronization

A lock-free collection does not mean synchronization disappears. It means progress does not depend on obtaining an exclusive lock held by another thread.

The key primitive is compare-and-exchange: update an atomic link only if it still contains the value observed during the preceding search.

match link.compare_exchange(expected, replacement, success, failure) {
          Ok(_) => {
              // The new link was published.
          }
          Err(_) => {
              // Another thread changed it first; search again and retry.
          }
      }

For a linked structure, that conditional update is enough to turn many conflicting writes into retry loops instead of lock waits.

The memory-ordering arguments matter. A simplified implementation that labels every read Acquire and every write Release is not a faithful description of Crossbeam. The real implementation uses different orderings for different invariants, including relaxed operations for hints and counters and stronger operations around structural publication. Memory ordering has to come from the algorithm, not from a generic recipe.

For a deeper treatment, Mara Bos's Rust Atomics and Locks is an excellent reference.

Start with the public SkipMap API

The application-facing code is intentionally simple:

use crossbeam_skiplist::SkipMap;
      
      struct MemTable {
          rows: SkipMap<String, Vec<u8>>,
      }
      
      impl MemTable {
          fn put(&self, key: String, value: Vec<u8>) {
              self.rows.insert(key, value);
          }
      
          fn get(&self, key: &str) -> Option<Vec<u8>> {
              self.rows.get(key).map(|entry| entry.value().clone())
          }
      }

Notice that mutation only needs &self. SkipMap implements concurrent ordered-map operations without requiring callers to place a mutex around the whole structure.

Crossbeam's documentation also makes an important distinction: one operation such as insert is atomic from the caller's perspective, but a sequence of operations is not a transaction. Another thread can interleave a remove between your insert and a later contains_key.

The API deliberately does not return &mut V. If values need in-place mutation, the value itself needs interior synchronization, for example SkipMap<K, RwLock<V>>. In that design, the map structure remains lock-free, while value access may block on the value-level lock.

What Crossbeam actually stores

The recovered draft used a common teaching model with head, tail, prev, a thread-local RNG, and an atomic value inside every node. That model is useful for intuition, but it does not match the current Crossbeam source closely enough to present as the implementation.

At a high level, the current code is closer to this:

SkipMap<K, V>
          |
          v
      base::SkipList<K, V>
          |-- head tower
          |-- epoch collector
          |-- hot metadata
          |     |-- random seed
          |     |-- approximate length
          |     `-- maximum observed tower height
          `-- comparator
      
      Node<K, V>
          |-- value: V
          |-- key: K
          |-- reference-count + height metadata
          `-- variable-height tower of atomic next links

The value is an ordinary V; concurrency is primarily in the tower links and node-lifetime machinery. Normal nodes are allocated with only as many tower slots as their randomized height needs, and the current implementation caps towers at 32 levels.

Random height instead of rotations

Crossbeam generates a pseudo-random tower height for each inserted node. The distribution makes height 1 common and progressively taller towers rarer.

The important consequence is that insertion does not need a global balancing operation. Higher levels are probabilistic acceleration indexes over the authoritative bottom list.

The current source also keeps a maximum-height hint so searches can start near the highest useful level rather than always scanning the full possible tower height.

Search also helps with cleanup

A concurrent traversal cannot assume every linked node is still logically present. Crossbeam marks removed nodes in pointer metadata. If a search encounters such a node, it can try to reconnect the predecessor directly to the successor and continue.

start at highest useful level
              |
              v
      load successor
              |
              +-- live node and key < target --> advance
              |
              +-- live node and key >= target -> drop one level
              |
              `-- removed node ----------------> try to bypass it
                                                   |
                                                   +-- success -> continue
                                                   `-- race lost -> restart search

This helping behavior is an important non-blocking pattern: cleanup is not reserved for the thread that initiated deletion. A thread that discovers stale structure can help finish the structural repair.

Insertion: publish level 0, then build the tower

Insertion first searches for predecessor and successor nodes and allocates a new node with a randomized height.

The essential structural step is the level-0 compare-and-exchange:

before:
      
      pred -----------------> succ
      
      successful publication:
      
      pred ------> new ------> succ

If the compare-and-exchange fails, another thread modified that link first. Crossbeam searches again and retries.

Once level 0 is installed, the node is reachable in the ordered list. The implementation then builds higher levels. The source explicitly treats those upper levels as optional for correctness: level 0 carries the ordered structure; upper levels make later searches faster.

That separation is valuable under concurrency. A removal can begin while higher levels are still being added, and the insertion logic can stop or repair tower construction without losing the bottom-level list.

Removal: logical state first, physical unlink second

A node may appear at several levels, but normal hardware does not give us one atomic operation that rewrites all of those predecessor links together.

Crossbeam therefore separates removal into phases. It first marks the node's tower as removed. It then reconnects predecessor links directly to successors, level by level.

logical removal:
      
      pred ------> [ removed node ] ------> succ
      
      physical unlink:
      
      pred -------------------------------> succ

If a predecessor changed concurrently, the update can fail and the algorithm searches again. Other traversals may also help unlink the marked node.

The key idea is that logical removal and physical unlink are different events, and neither one immediately implies that the node's storage can be reclaimed.

Epoch-based reclamation closes the lifetime gap

Concurrent linked structures have a lifetime problem: a thread can still hold a reference to a node after another thread removes that node from the visible structure.

crossbeam-skiplist uses crossbeam-epoch to manage that gap. Operations pin to an epoch collector while following protected shared pointers. Retired nodes are reclaimed only after the collector can establish that earlier pinned operations can no longer depend on them.

At the SkipMap layer, most of this is hidden. Methods pin internally, and get returns an Entry handle rather than exposing an untracked raw reference. Holding an Entry can delay reclamation of a removed entry until the handle is dropped.

This is more precise than saying "pinning means nothing is freed while this function runs." The actual guarantee comes from the collector, pinned participants, deferred reclamation, and the lifetime of returned entry handles working together.

Why this fits an LSM MemTable

A MemTable needs ordered iteration because flushing to an SSTable is easiest when keys are already sorted. It also needs point lookups and range scans while writes are arriving.

SkipMap provides that combination:

  • ordered keys and range iteration;
  • concurrent get, insert, and remove;
  • no tree rotations or global rebalance step;
  • lock-free structural progress;
  • safe handling of removed nodes whose references are still in use.

But lock-free does not automatically mean faster.

Crossbeam's own documentation warns that skip lists can be substantially slower than B-trees in some scenarios. With infrequent writes, an RwLock<BTreeMap<...>> may be simpler and faster. If ordering is unnecessary, a concurrent hash map may be a better fit.

The engineering rule is therefore: benchmark the workload you actually have. Allocation, cache locality, key distribution, read/write ratio, range scans, contention, and reclamation all matter.

The MemTable still needs a freeze protocol

The concurrent container solves only one layer of the storage-engine problem.

An LSM flush needs a stable MemTable generation. Iterating a live map while writers continue modifying it is not the same as producing an atomic snapshot for an SSTable. A more robust design rotates generations:

active MemTable  ---- accepts new writes
            |
            | threshold reached
            v
      generation swap
            |
            +------> new active MemTable
            |
            `------> frozen MemTable ----> SSTable flush

The skip list handles concurrency inside a generation. The storage engine still needs a protocol defining which writes belong to the frozen generation and how that boundary coordinates with the WAL.

That separation is important: a lock-free map is a building block, not a complete durability or snapshot protocol.

Practical rules

  1. Treat each SkipMap call as an atomic operation, not a multi-call transaction.
  2. Do not treat len() as an exact synchronization point while the map is concurrently changing; Crossbeam documents it as approximate in that case.
  3. Keep Entry handles only as long as needed because they can delay reclamation.
  4. If values require mutation, choose interior synchronization deliberately.
  5. Use a skip list when ordering and concurrent mutation are both useful; do not pay for ordering when a hash map is enough.
  6. Benchmark against a simpler RwLock<BTreeMap<...>> rather than assuming lock-free wins.
  7. In an LSM tree, design MemTable rotation and WAL/flush boundaries separately from the container.

Conclusion

The elegant part of a skip list is the express-lane structure. The difficult part of a concurrent skip list is maintaining those lanes while many threads are traversing and changing them.

Crossbeam combines several techniques to make that work:

  • probabilistic towers avoid global balancing operations;
  • compare-and-exchange publishes structural changes;
  • level 0 carries the essential ordered list while upper levels accelerate search;
  • removed nodes are marked before they are fully unlinked;
  • traversing threads can help finish cleanup;
  • reference tracking and epoch-based reclamation keep node lifetimes valid across concurrent operations.

That combination is why crossbeam-skiplist is an interesting MemTable building block. It preserves ordered access while allowing concurrent structural updates without a global mutex.

The deeper lesson is that eliminating locks does not eliminate coordination. It moves coordination into atomic state transitions, retry loops, helping protocols, and memory-reclamation rules. Those mechanisms are what make the structure correct.

References