Sudden power outages remain one of the biggest threats to losing data, disrupting systems and causing financial damages. Whole system persistence (WSP) has previously been proposed as a solution to mitigate such threats through the use of non-volatile main memory (NVRAM). However, it missed out on external device state persistence and the NVRAM technology used at the time was expensive and limited with regard to their scalability. Today's NVRAM technologies are both more affordable and offer much higher storage capacities, but are typically slower than DRAM.

In this article we present an algorithm for a high performance, unbounded, portable, multi-producer/multi-consumer, lock-free FIFO (first-in first-out) queue. Aside from its competitive performance on current hardware, it is further characterized by its integrated memory reclamation mechanism, which is able to reliably and deterministically de-allocate nodes as soon as the final operation with a reference has concluded, similar to reference counting. This differentiates our approach from most other lock-free data structures, which usually require external (generic) memory reclamation or garbage collection mechanisms such as hazard pointers. Our deterministic memory reclamation mechanism completely prevents the build up of memory awaiting reclamation and is hence very memory efficient, yet it does not introduce any substantial performance overhead. By utilizing concrete knowledge about the internal structure and access patterns of our queue, we are able to construct and constrain the reclamation mechanism in such a way that keeps the overhead for memory management almost entirely out of the common fast path. The presented algorithm is portable to all modern 64-bit processor architectures, as it only relies on the commonly available and lock-free atomic synchronization primitives compare-and-swap and fetch-and-add.