Lock-free data structures promise scalability by letting threads make progress without blocking each other. But they introduce a deceptively hard problem: when is it safe to free memory that other threads might still be reading?

In a conventional mutex-protected data structure, the answer is straightforward. Once you hold the lock and remove a node, you know no other thread can access it. You can free it immediately. Lock-free algorithms sacrifice that certainty. A thread might read a pointer, get preempted for milliseconds, then dereference that pointer after another thread has already unlinked and freed the memory. The result is a use-after-free bug and likely a crash.

Reference counting seems like an obvious solution, but atomic reference count operations on every access kill the performance benefits of going lock-free in the first place. You need a mechanism that tracks what memory is in use without constant synchronization overhead. Hazard pointers provide exactly that.

The Core Mechanism

A hazard pointer is a thread-local announcement: “I’m currently accessing this memory address.” Before dereferencing any pointer obtained from shared memory, a thread writes that pointer value into one of its hazard pointer slots. These slots are visible to all threads but each thread only writes to its own.

When a thread wants to free memory, it doesn’t call free() immediately. Instead, it adds the pointer to a thread-local retire list. Periodically, it scans all hazard pointers published by all threads. Any retired pointer that appears in a hazard pointer slot is still in use and must wait. Anything else can be safely reclaimed.

The pattern looks like this: acquire a pointer from shared memory, publish it as a hazard, verify the pointer is still valid (it might have been unlinked between reading and publishing), then safely dereference. When done, clear the hazard pointer. The verification step is critical because another thread might have removed the node in the window between your read and your hazard pointer write.

Trade-offs and Performance Characteristics

Hazard pointers separate the hot path from the reclamation overhead. Reading threads do two operations: a write to a thread-local hazard pointer and a validation check. Both are cheap and non-contending. The expensive work happens on the thread doing deletion, which must scan all active hazard pointers before reclaiming memory.

This means hazard pointers scale well for read-heavy workloads. Each reader pays a fixed small cost regardless of how many other threads exist. The deleting thread pays linear cost in the number of threads, but deletions are typically rarer than reads in most data structures.

Memory reclamation isn’t instantaneous. Retired nodes accumulate until a thread decides to scan hazard pointers and reclaim what’s safe. This creates a tuneable trade-off: scan frequently for lower memory overhead but higher CPU cost, or scan rarely and tolerate more memory lingering in retired lists. Most implementations trigger scans when the retired list reaches a threshold proportional to the number of threads times the number of hazard pointers per thread.

Alternative Approaches

Epoch-based reclamation (EBR) is the main alternative. Threads announce they’re in an active epoch rather than announcing specific pointers. Memory is retired to a specific epoch and reclaimed only after all threads have advanced past that epoch. EBR has lower per-operation overhead but can’t reclaim memory as quickly if a single thread stalls while in an active epoch.

Some implementations combine approaches. Folly’s hazard pointer implementation in C++ provides both mechanisms, letting developers choose based on their access patterns. Long-running operations that might block favor hazard pointers because they don’t prevent other threads from reclaiming memory. Short critical sections favor EBR for its lower overhead.

For languages with automatic memory management, the problem largely disappears. The garbage collector already solves safe reclamation. But in systems languages like C, C++, or Rust, hazard pointers are often the most practical solution for building scalable lock-free structures without leaking memory or requiring intrusive reference counting on every access.

Implementation Complexity

Hazard pointers shift complexity from correctness to performance. The safety property is straightforward: don’t free anything that appears in a hazard pointer. But the engineering details matter. How many hazard pointer slots does each thread need? How do you handle thread termination and ensure its hazard pointers are eventually released? How do you batch reclamation work efficiently?

Most production implementations provide a library that handles these details. Developers mark pointer loads as hazardous and the library manages the underlying machinery. But unlike garbage collection, the performance characteristics remain explicit and predictable. You know exactly when scans happen and what they cost.

The result is a technique that makes lock-free data structures practical in environments where automatic memory management isn’t available or acceptable. It’s not simple, but it solves a problem that has no simple solution.