Lock-Free Concurrency in MongoDB: Hazard Pointers and Skip Lists Inside WiredTiger

By Vivek Kumar 10 min read

Lock-Free Concurrency in MongoDB: Hazard Pointers and Skip Lists Inside WiredTiger

Most engineers assume that databases rely heavily on locks to coordinate concurrent access.

But locks don’t scale well.

As CPU core counts increase, lock contention becomes one of the biggest bottlenecks in modern database systems. Threads block, CPUs idle, and throughput collapses under high concurrency.

MongoDB’s default storage engine WiredTiger takes a different approach.

Instead of relying primarily on locks, it uses lock-free algorithms for both reads and writes.

Two key mechanisms make this possible:

  • Hazard Pointers → Lock-free reads
  • Skip Lists + CAS → Lock-free writes

Together, these techniques allow WiredTiger to handle massive concurrency while fully utilizing modern multi-core hardware.

The Problem

Modern databases must support:

  • thousands of concurrent client connections
  • millions of reads and writes per second
  • efficient use of multi-core CPUs

Traditional storage engines rely on locking to maintain consistency.

Example:

lock(page)
read(page)
unlock(page)

Even shared locks introduce coordination overhead:

  • threads must synchronize
  • cache lines bounce between CPU cores
  • lock queues form under contention

As concurrency increases, lock-based systems often hit scalability limits.

To avoid this, WiredTiger uses lock-free data structures.

The Role of the Storage Engine

In MongoDB, the storage engine is responsible for:

  • persisting documents on disk
  • managing the in-memory cache
  • coordinating concurrent reads and writes
  • ensuring durability and crash recovery

MongoDB’s default storage engine is WiredTiger.

On disk, WiredTiger stores data using a B+Tree.

B+Trees are ideal for databases because they support:

  • fast point lookups
  • efficient range scans
  • balanced performance for reads and writes
  • disk-friendly page layouts

But the in-memory representation is very different from the on-disk structure.

This separation enables powerful concurrency optimizations.

Disk vs Memory Representation

WiredTiger maintains two different representations of data.

LayerStructurePurpose
DiskB+Tree pagesDurable storage
MemoryCached pages + update structuresConcurrent access

Disk structures prioritize:

  • compression
  • sequential I/O
  • storage efficiency

Memory structures prioritize:

  • concurrency
  • fast pointer manipulation
  • lock-free algorithms

This design allows WiredTiger to use in-memory structures that would be impractical for disk storage.

Lock-Free Reads Using Hazard Pointers

When a thread reads a document, it typically accesses a page cached in memory.

However, the cache manager may evict pages to free memory.

If a page were evicted while a thread was reading it, the thread might dereference a dangling pointer, causing crashes or memory corruption.

Traditional databases solve this using read locks.

But WiredTiger uses hazard pointers instead.

What Is a Hazard Pointer?

A hazard pointer allows a thread to announce which memory object it is currently accessing.

Before accessing a page, the thread publishes the pointer in a hazard slot.

thread.hazard_pointer = page
memory_barrier()

After the read completes:

thread.hazard_pointer = NULL

This simple mechanism tells the system:

“This thread is currently using this memory object.”

How Eviction Works

When the cache manager wants to evict a page:

  1. It scans hazard pointers from all threads.
  2. If any thread references the page → eviction is skipped.
  3. If no hazard pointer references it → the page can be safely evicted.

This guarantees:

  • no dangling pointers
  • no read locks
  • minimal synchronization overhead

Lock-Free Writes Using Skip Lists

Reads are only half the story.

Databases must also support highly concurrent writes.

Traditional systems use page-level write locks:

lock(page)
modify data
unlock(page)

This serializes updates and limits scalability.

Instead, WiredTiger stores in-memory updates using a lock-free skip list.

Why Skip Lists?

A skip list is a probabilistic data structure similar to a balanced tree.

Conceptually it looks like multiple linked lists stacked on top of each other.

Level 3:       30 -------- 70
Level 2:       30 ---- 50 ---- 70
Level 1: 10-20-30-40-50-60-70

Higher levels act as express lanes, allowing faster traversal.

Skip lists provide:

  • O(log n) search time
  • simple pointer manipulation
  • natural support for lock-free algorithms

Atomic Compare-And-Swap (CAS)

Updates in the skip list rely on an atomic CPU instruction called Compare-And-Swap (CAS).

CAS works like this:

if (*pointer == expected_value)
    *pointer = new_value

The update succeeds only if the pointer hasn’t changed.

If another thread modified it first, the operation fails and the thread retries.

Example pattern:

while(true) {
    old = pointer
    new = build_update(old)

    if CAS(pointer, old, new)
        break
}

This technique is called optimistic concurrency.

Instead of locking, threads simply retry if conflicts occur.

Why Not Doubly Linked Lists?

Lock-free algorithms depend on atomic pointer updates.

A singly linked list insertion requires only one pointer change:

CAS(A.next, B, X)

But a doubly linked list requires two updates:

A.next = X
B.prev = X

These operations cannot be performed atomically with a single CAS instruction.

If a thread crashes or gets interrupted between updates, the structure becomes inconsistent.

Skip lists avoid this problem because they rely on singly linked forward pointers, which can be safely updated using CAS.

How Reads Combine Disk Data and Updates

Another important design choice:

WiredTiger does not modify disk pages directly during writes.

Instead, updates are stored in memory.

A read operation merges:

disk page
+
in-memory updates

Example:

Disk page:

key: 20 → value A

Update chain:

key:20 → value B
key:20 → value C

The reader applies the newest update to return the correct value.

This allows updates to occur without modifying the base page immediately.

Example Write Scenario

A simplified write path looks like this:

  1. Locate the leaf page in the B+Tree.
  2. Create an update node.
  3. Insert the update into the skip list using CAS.
  4. Commit the transaction.

No disk write occurs at this stage.

Later, WiredTiger performs page reconciliation, merging updates into a new B+Tree page and writing it to disk.

Internal Architecture

The interaction between memory structures and disk storage looks like this:

flowchart TD

Client --> Read
Client --> Write

Read --> CachedPage
Write --> UpdateNode

UpdateNode --> SkipList
SkipList --> CachedPage

CachedPage --> HazardPointer

CachedPage --> Reconciliation
Reconciliation --> DiskPage

DiskPage --> BPlusTree

Example Concurrency Scenario

The following sequence shows how concurrent reads and writes operate safely.

sequenceDiagram

participant Reader
participant Cache
participant SkipList
participant Eviction

Reader->>Cache: Access page
Reader->>Cache: Publish hazard pointer

SkipList->>Cache: Insert update using CAS

Eviction->>Cache: Attempt page eviction
Cache->>Eviction: Page protected by hazard pointer
Eviction->>Cache: Skip eviction

Reader->>Cache: Read merged result
Reader->>Cache: Clear hazard pointer

Readers never block writers, and writers never block readers.

Why This Architecture Works

This hybrid architecture gives WiredTiger several advantages.

Lock-Free Reads

Hazard pointers eliminate read locks and prevent unsafe memory reclamation.

Lock-Free Writes

CAS-based skip list updates allow concurrent writes without page locks.

CPU Scalability

Threads rarely block each other, allowing efficient multi-core scaling.

Efficient Disk Writes

Updates accumulate in memory and are later merged during reconciliation.

Key Takeaways

Modern database engines must scale across dozens of CPU cores.

Traditional lock-heavy designs struggle under high contention.

WiredTiger solves this using lock-free techniques:

  • Hazard pointers protect in-memory pages during reads
  • Skip lists + CAS enable concurrent lock-free updates
  • Separate memory and disk structures optimize both performance and durability
  • Deferred page reconciliation reduces disk write amplification

These design choices allow MongoDB to achieve high throughput and excellent concurrency on modern hardware.

Final Thoughts

Lock-free algorithms are notoriously difficult to implement correctly.

They require careful reasoning about:

  • memory ordering
  • atomic operations
  • pointer safety
  • race conditions

But when done right, the payoff is enormous.

WiredTiger demonstrates how combining hazard pointers, CAS-based structures, and careful separation of memory and disk layers can unlock massive concurrency in modern database systems.

For engineers exploring database internals, these techniques offer a fascinating glimpse into how high-performance storage engines are built.