Persistent-memory allocators spend up to 87% of their time flushing heap metadata, and the flushes are pathological — 40–99.7% re-flush the SAME cache line (at 7.5× the cost of a write), extent headers scatter random small writes across the whole heap, and statically size-segregated slabs strand up to 2.8× memory that survives reboots — NVAlloc fixes each with layout, interleaving bitmap bits across cache lines so consecutive allocations never touch the same line, appending 8-byte bookkeeping entries to a sequential log instead of updating headers in place, and morphing under-used slabs between size classes — up to 6.4×/57× faster small/large allocations and 57.8% less memory.
The argument in one glance
-
Problem
On persistent memory, the allocator itself must survive crashes
Persistent memory (Intel Optane DIMMs) puts byte-addressable, durable storage on the memory bus — and in-memory databases, indexes, and transactional systems allocate from it directly. A persistent allocator must therefore make its own bookkeeping crash-safe: every bitmap bit, slab header, extent header, and write-ahead-log entry must be explicitly FLUSHED from CPU caches to the DIMM at the moment it changes. Heap metadata management, an afterthought in DRAM allocators, becomes the dominant cost — up to 87% of execution time in the paper's breakdown.
-
What people did
Port the classic allocator playbook and add flushes
The ecosystem's allocators — Intel's PMDK, nvm_malloc, PAllocator, Makalu, Ralloc — did exactly that: size-segregated slabs with bitmaps or embedded free lists for small objects, chunked heaps with header-space bookkeeping for large ones, and either write-ahead logs (strong consistency) or post-crash garbage collection (weak) for recovery.
-
Why it fell short
Three metadata pathologies, all layout-induced
Measured on real Optane: (1) REFLUSHES — consecutive allocations from a slab update adjacent bitmap bits living in one 64-byte cache line, so the same line is flushed again and again; a reflush costs 7.5× a write, and reflushes are 40.4–99.7% of all allocator flushes across four benchmarks. (2) RANDOM SMALL WRITES — chunk headers are scattered across the heap by design (separation from data), so best-fit allocation lands in-place metadata updates at random addresses, the access pattern persistent memory handles worst. (3) PERMANENT FRAGMENTATION — slabs are locked to the size class chosen at initialization; when request sizes shift, near-empty slabs of the old class cannot serve the new one, inflating 1 GB of live data to 2.8 GB — and since the heap is a DAX file, a reboot clears nothing.
-
This paper's idea
Fix the layout, not the algorithm
NVAlloc attacks each pathology with a placement decision. INTERLEAVED MAPPING stripes bitmap bits across cache lines so consecutive block allocations touch different lines (with a striped, cursor-rotated thread cache to keep it true under LIFO reuse) — reflushes eliminated. LOG-STRUCTURED BOOKKEEPING appends 8-byte extent-metadata entries to a sequential persistent log (tombstones + two-tier GC) instead of updating scattered headers in place — random writes become sequential ones. SLAB MORPHING transforms under-20%-occupied slabs to whichever size class is starving, safely holding two size classes during a flag-stepped, crash-consistent transition — fragmentation down 41.9–57.8% for 4.5% overhead. Results: up to 6.4× (small) and 57× (large) faster than state-of-the-art allocators, validated in both WAL-based and GC-based consistency variants.
Why this problem is worth solving
byte-addressable memory that
survives power loss — Intel’s Optane DIMMs being the flagship —
sitting on the memory bus at near-DRAM latency. Programs map a
heap file (via a DAX filesystem) and load/store into it
directly; durability requires explicitly flushing dirtied cache
lines (clwb instructions) so they reach the protected domain
before a crash
the guarantee that after any crash,
the allocator’s metadata is recoverable to a consistent state
with no leaked or double-allocated memory. Achieved either with
write-ahead logs (append intent, flush, then act — strong
consistency, recovery by replay) or by post-crash garbage
collection that rebuilds state by scanning the heap (weak
consistency, faster runtime, slower recovery)
The paper’s contribution begins as measurement: on real Optane, the ported-from-DRAM designs spend the overwhelming majority of their time not searching or splitting but flushing — and flushing badly, since their layouts concentrate consecutive updates into single cache lines (the 7.5×-cost reflush pattern) and scatter header updates randomly (the pattern Optane’s internal write buffering handles worst). Fragmentation, the third pathology, gains teeth in persistence: a DRAM allocator’s waste dies with the process, but a persistent heap’s stranded slabs are stranded in a file, forever. All three are layout problems, and NVAlloc’s thesis is that layout — not smarter algorithms — is where persistent allocation performance lives.
What people did before, and where it broke
- PMDK, nvm_malloc, PAllocator (strongly consistent). Slab-and-bitmap or slab-and-WAL designs where every allocation persists a bitmap bit and/or a WAL entry. Adjacent allocations → adjacent bits → same cache line: reflushes reach 99.7% (PMDK), 94.4% (nvm_malloc), 98.8% (PAllocator) of flush operations on the classic allocator benchmarks.
- Makalu, Ralloc (GC-based). Skip most runtime flushing and rebuild metadata by conservative GC after a crash. Their free lists are embedded in the blocks themselves — pointer chains through persistent memory with poor locality (and headers adjacent to data, a corruption hazard) — costing them up to 70× against NVAlloc’s bitmap-plus-volatile-copy design.
- Chunked heaps with header bookkeeping. PMDK, Makalu, and PAllocator subdivide the heap into fixed regions (e.g., 4 MB) whose headers hold extent metadata, deliberately separated from data. After enough allocate/free cycles, best-fit picks extents anywhere — so header updates are small random writes sprayed across the whole heap, profiled directly in the paper’s address traces.
- Static slab segregation, universally. Every allocator — volatile and persistent alike — fixes a slab’s size class at creation and can only reassign a completely empty slab. Fragbench (RAMCloud-style shifting size distributions): 2.8 GB peak for 1 GB live.
How NVAlloc works
Three pathologies, three layout fixes
-
Standard skeleton, carefully split
Per-core arenas and per-thread caches (tcaches) for contention-free small allocation (<16 KB) from 64 KB slabs; large allocations (16 KB–2 MB) from extents managed by virtual extent headers (VEHs) in DRAM across activated/reclaimed/retained lists, with an R-tree for split/coalesce neighbor lookup. Volatile copies (vslab, VEH, R-tree) live in DRAM for speed and are rebuilt on recovery; only what recovery truly needs is persisted.
-
Interleaved mapping (kills reflushes) new
The slab bitmap is divided into BIT STRIPES, each stripe resident in a different cache line; consecutive data blocks map to bits in DIFFERENT stripes. Allocating B0, B1, B2 in sequence now dirties lines #0, #1, #2 instead of hammering one line. The same interleaving is applied to WAL entries and the bookkeeping log. Six stripes empirically balance reflush elimination against exhausting Optane's internal write buffer.
-
Interleaved tcache (keeps it true under reuse) new
LIFO tcaches could still hand out blocks whose bits share a line, so the tcache splits into sub-tcaches — one per bit stripe — with a rotating cursor: consecutive allocations draw from different sub-tcaches, hence different cache lines, by construction.
-
Log-structured bookkeeping (kills random writes) new
Extent-header updates never happen in place. Each VEH change appends one 8-BYTE entry (26-bit size, 36-bit address — 4 KB-aligned within 48-bit space — 2-bit type) to a persistent log of 1 KB chunks; frees append tombstones. DRAM-side vchunk bitmaps (in an RB-tree) track liveness; FAST GC frees fully-dead chunks by bitmap scan alone (no PM access), SLOW GC compacts live entries into a fresh chain — swapped atomically via an alternate-pointer bit — only when the log exceeds its threshold. Metadata-only entries make the space-for-locality trade nearly free (3–8% GC overhead).
-
Slab morphing (kills permanent fragmentation) new
Slabs sit in an LRU list; when a size class starves, NVAlloc picks a least-recently-used slab under 20% occupancy and TRANSFORMS it. During transition the slab legitimately holds two size classes: old_size_class/old_data_offset plus a 2-bytes-per-survivor index_table track the old blocks; volatile counters (cnt_slab, per-block cnt_block) decide when the slab becomes a regular member of its new class. A flag field incremented atomically after each transformation step makes the whole morph crash-consistent (undo on recovery if interrupted).
-
Two consistency variants + recovery
NVAlloc-LOG persists WALs for strong consistency (recovery replays them); NVAlloc-GC skips runtime metadata flushing for small objects and rebuilds via conservative post-crash GC (Makalu-style). Both share the large-allocator path. Recovery scans the bookkeeping log, rebuilds vslabs/VEHs, treats gaps between active extents as free, and checks morph flags to undo interrupted transformations.
The idea
On persistent memory, WHERE metadata lives matters more than what it is. The reflush pathology is pure geometry: allocation order is sequential, bitmap layout is sequential, so time-adjacent persist points collide in one cache line — and Optane punishes exactly that collision (a reflush at distance 0 costs ~800 ns against ~500 ns at distance 3, 7.5× a plain write). NVAlloc’s fix changes no algorithm and no semantics: the bitmap still has one bit per block, but the mapping permutation between blocks and bits is chosen so sequential allocations stride across cache lines. The sub-tcache cursor extends the same guarantee through the reuse path. The eADR evaluation is the elegant proof that this is hardware-conscious design and not a universal truth: on platforms whose caches are themselves persistent (no flushes needed), interleaving buys nothing and NVAlloc auto-disables it.
When in-place updates are the enemy, append. The random small writes of extent bookkeeping are structural — best-fit will pick extents anywhere — so NVAlloc stops writing where the extents are and starts writing where the log is. The move is the LSM/journal playbook, but the allocator setting makes it unusually cheap: entries are fixed 8-byte metadata (bit-packed by exploiting 48-bit addresses and 4 KB alignment), not data, so a 100 MB log absorbs enormous churn, and liveness tracking lives entirely in DRAM bitmaps so the common-case GC never touches persistent memory at all. Sequentiality is exactly what Optane’s limited internal write buffering wants.
Fragmentation in a persistent heap deserves a persistent fix. Slab morphing accepts a heresy — one slab briefly holding blocks of two size classes — because static segregation’s alternative is permanent, file-resident waste. The design keeps the heresy cheap and safe: only cold (LRU-selected), nearly-empty (under 20%) slabs morph, so the dual-class bookkeeping (a small index table plus counters) covers few blocks; and the multi-step metadata rewrite is made atomic-in-effect by a step counter that recovery can read to undo a half-finished morph. The measured trade — 4.5% runtime for 41.9–57.8% memory — is the kind that persistent heaps, where waste never expires on its own, should take every time.
An allocation’s journey, small and large
Through NVAlloc-LOG on real Optane
Stripe = the set of bitmap bits sharing one cache line. Sub-tcache = per-stripe free-block cache with rotating cursor. VEH = volatile extent header (DRAM). SU = slab-occupancy threshold for morphing (20%). Numbers from the paper's Optane evaluation.
Step 1 of 7
malloc(64 B): the tcache rotates
The thread's tcache serves the request from the sub-tcache under its cursor, then advances the cursor. The previous allocation came from a different sub-tcache — so this block's bitmap bit lives in a different cache line than the last one, by construction.
LIFO reuse can no longer re-collide persist points sub-tcaches = one per bit stripe (6 stripes)
Why it works
- Reflush cost is a function of temporal-spatial collision (same line, close in time) → permuting the block-to-bit mapping and rotating sub-tcaches makes consecutive persist points land on different lines → the 40–99.7% reflush share collapses, worth 35–48% of execution time, with zero algorithmic change.
- Optane favors sequential small writes and punishes random ones → appending fixed 8-byte entries to a log converts best-fit’s inherently random header updates into sequential I/O → and because entries are metadata (bit-packed, uniform), the log stays small, GC stays mostly in DRAM, and the classic log-structuring tax nearly vanishes.
- Persistent fragmentation compounds forever (the heap is a file) → morphing recycles cold, nearly-empty slabs across size classes, with dual-class bookkeeping bounded by the 20% occupancy gate and crash safety by a stepped flag → 2.8× waste becomes the smallest footprint measured, for 4.5% runtime.
- Volatile copies (vslab, VEH, R-tree, vchunk bitmaps) do the fast work in DRAM; persistent memory holds only what recovery needs → the persist-point count itself shrinks — the same division of labor that lets NVAlloc-GC skip small-object flushing entirely.
- The optimizations are orthogonal to the consistency model → applied under both WAL and GC regimes, and auto-adapted to eADR hardware (interleaving disabled when flushes are free) → the design degrades gracefully as hardware assumptions shift.
What it costs
- Complexity in the smallest allocator. Stripes, sub-tcaches, morph flags, index tables, a logging subsystem with two GCs — a substantial machine where DRAM allocators have a bitmap; each piece is individually simple but the correctness surface (especially morphing under crashes) grows.
- Recovery time. NVAlloc-LOG scans both WALs and the bookkeeping log — slower recovery than PMDK/nvm_malloc; the runtime-versus-recovery trade is explicit and measured.
- Log space and slow-GC pauses. 100 MB of persistent log is traded for locality; slow GC copies live entries when the threshold trips (kept to 3–8% throughput impact at the evaluated settings).
- Morphing is bounded, not free. 4.5% average runtime overhead, and the SU=20% and 6-stripe parameters are empirically tuned — the authors themselves flag dynamic tuning as future work.
- Hardware specificity. The reflush economics, XPBuffer stripe ceiling, and random-write penalties are Optane measurements; eADR already voids one technique (gracefully), and the platform landscape shifted dramatically after publication.
The evaluation
Real hardware throughout: dual 20-core Xeons with two 128 GB Optane DIMMs in App Direct mode. Five allocator baselines split by consistency model (fair within-class comparisons), five allocation benchmarks plus DBMStest, Fragbench for memory, FPTree as a real application, and sensitivity/overhead studies for every new mechanism — plus an emulated-eADR study testing the design’s future-proofing.
Persistent allocators, by how they persist metadata
| Property | PMDK / nvm_malloc / PAllocator (WAL-based) | Makalu / Ralloc (post-crash GC) | NVAlloc (LOG and GC variants) |
|---|---|---|---|
| Cache-line behavior of metadata persists | |||
| Large-object bookkeeping | Same chunked-header layouts | ||
| Fragmentation under shifting sizes | Same static segregation | ||
| Performance (real Optane) | Baselines | Baselines (weak class) | |
| Consistency & recovery | Strong (WAL replay); fast recovery | Weak (conservative GC); fast runtime, recovery scans the heap |
Check yourself
Check your understanding
1. Persistent allocators spend up to 87% of their time flushing, and most flushes are REflushes of the same cache line. Predict the mechanism that makes this pathology near-universal in ported-from-DRAM designs.
2. For large allocations, NVAlloc never updates an extent's persistent header in place — it appends an 8-byte entry to a log instead. Why is this trade unusually cheap here compared to classic log-structured systems?
3. Slab morphing briefly lets one slab hold blocks of TWO size classes — heresy in allocator design. What makes this both worthwhile and safe in the persistent setting?
4. NVAlloc ships two variants — NVAlloc-LOG (write-ahead logging) and NVAlloc-GC (post-crash garbage collection) — and applies its optimizations to both. What does this dual offering reveal about where the paper locates its contribution?