Epoch-based reclamation and hazard pointers
When can memory a reader might hold be freed, and why is that the same question as a vacuum retention window?
The problem, stated precisely
This is the hardest thing in lock-free programming and the reason most people never write any.
In a lock-free structure you can unlink a node (make it unreachable from the structure). But you cannot free it (give its memory back), because another thread may be holding a pointer it read a microsecond ago. Removal and reclamation are separate problems, and only the first one is easy. This is exactly Arjun's crash: a writer unlinked a node and freed it while a reader still held a pointer to it. (A pointer to freed memory is called a dangling pointer; using it is a use-after-free bug.)
Garbage collection as a correctness mechanism
This reframes garbage collection entirely. Lock-free structures are common in Java and rare in C++ not because of language culture. It is because the GC is a universal safe-reclamation protocol: it already solves the hard half. In C++ you must build your own. And the price of having one, pause times, is exactly why low-latency systems cannot simply adopt a GC and move on. In a concurrent system, a garbage collector is not a convenience. It is a correctness mechanism.
Three protocols and the trade-off they form
Hazard pointers. Before using a shared pointer, a thread publishes it in its own per-thread slot. A reclaimer scans all slots and frees only the nodes nobody has published.
- Memory is bounded: at most (number of threads × hazards per thread) retired-but-unfreed nodes.
- But readers must write and fence on every access. This violates the principle "a reader that writes does not scale", so the reader path is expensive.
Epoch-based reclamation (EBR). There is a global epoch counter (a number that increases over time). A thread announces the epoch it was in when it entered a critical section (a stretch of code that reads shared pointers). A node retired in epoch e is freed once every thread has advanced past e+2.
- Readers write only to their own cache line, so readers are cheap.
- Memory is unbounded: one thread parked inside a critical section (descheduled by the OS, stopped in a debugger, or stuck in a GC pause) blocks all reclamation indefinitely.
RCU (read-copy-update). In the common case readers do nothing: no writes, and on most architectures no fences. Writers wait for a grace period, during which every CPU has passed a quiescent state (a point where it provably holds no reference to the old data). Free readers are why RCU is the Linux kernel's scaling workhorse. The costs are writer waits on the scale of milliseconds, and the need for a definition of "quiescent" that kernels have naturally and user-space programs do not.
| Protocol | Reader cost | Memory | Implementation |
|---|---|---|---|
| Hazard pointers | high (write and fence per access) | bounded | moderate |
| EBR | low (write own line) | unbounded if a thread stalls | simple |
| RCU | nearly zero | bounded by the grace period | needs a quiescent-state definition |
So: cheap readers, bounded memory, simple implementation. Pick two. This is the shape of the RUM triangle in a completely different domain. That is mild evidence that the triangle is about constrained resources in general and not only about storage.
The same question at every scale
Safe reclamation is a consensus problem in miniature: has every participant confirmed that it no longer references this? The same question, with the same structure, appears at every scale of the stack.
| Scale | Question | Grace period |
|---|---|---|
| Nanoseconds | Can I free this node? | Epoch advance or hazard scan |
| Microseconds | Can the FTL (SSD translation layer) erase this block? | No live pages remain in it |
| Seconds to hours | Can vacuum remove this row version? | The oldest snapshot's xmin horizon |
| Hours to days | Can Iceberg delete this orphan file? | The expire_snapshots retention window |
VACUUM RETAIN 168 HOURS and a hazard-pointer scan are the same mechanism, separated by twelve orders of magnitude. Their failure mode is the same too. A long-running Postgres transaction blocks vacuum and lets the table bloat. That is exactly a stalled thread blocking epoch advance and letting memory grow without bound. The Postgres DBA and the lock-free programmer are debugging the same bug. If a data engineer keeps one thing from this article, it should be this equivalence, because the diagnostic instinct then transfers in both directions.
The Immutability law, final form
This earns the Immutability law its final refinement:
The last clause carries the weight. It is the Variance law (variance costs more than volume) in another costume: reclamation latency is a maximum over all participants, so one slow reader causes unbounded space growth, however fast everyone else is.