Designing for Asymmetric Read-Write Costs in Non-Volatile Memory

183 concepts126 papers2 proposals

For decades, computer systems have relied on the uniform memory access assumption: the classic Random Access Memory (RAM) abstraction treats the cost of reading data and writing data as identical. Emerging non-volatile memory (NVM) technologies—such as Phase Change Memory (PCM), Spin-Transfer Torque Magnetic RAM (STT-MRAM), and Flash—shatter this illusion.

At a physical level, altering the state of a non-volatile cell requires significantly more energy, structural modification, or time than simply sensing its current state. For instance, melting a phase-change material or forcing a magnetic domain alignment incurs a steep physical penalty. This creates a fundamental read-write asymmetry, where write operations are often an order of magnitude slower and more energy-intensive than reads, alongside causing gradual physical degradation (limited write endurance).

To prevent these hardware traits from crippling modern software, a major research direction focuses on designing "asymmetry-aware" algorithms and system architectures. The core intuition is simple: intentionally spend cheap read operations to avoid expensive write operations.

The Hidden Cost of Writes in Read-Heavy Workloads

It is tempting to assume that read-heavy applications are naturally immune to NVM write bottlenecks. However, modern data-intensive workloads generate substantial "hidden" writes under the hood to manage intermediate states.

In database systems, for example, Online Analytical Processing (OLAP) queries are overwhelmingly read-oriented. Yet, as Jie Liang Ang et al. demonstrate in Micro-architectural Analysis of OLAP Systems on Persistent Memory, these queries must build temporary, intermediate structures like hash tables or sorted runs. The authors reveal that these intermediate writes cause a 1.4x performance slowdown, with data cache stalls consuming up to 90% of CPU cycles because the processor pipeline chokes on the slower write speeds of persistent memory.

Similarly, parallel graph processing involves massive datasets where vertex and edge properties are continuously traversed. Wei Liu 0004 et al. observe in NGraph: Parallel Graph Processing in Hybrid Memory Systems that random write operations on NVM suffer an especially severe latency penalty compared to sequential writes. When traditional graph algorithms perform update-in-place operations across billions of edges, they trigger frequent random writes that quickly bottleneck the entire system.

Algorithmic Paradigms: Trading Reads for Writes

To bypass the hardware limitations of NVM, researchers have begun rewriting fundamental computer science algorithms using computational models that explicitly penalize writes. As formalized by Guy E. Blelloch et al. in Sorting with Asymmetric Read and Write Costs, assigning a high weight to write operations while maintaining a unit cost for reads allows for the mathematical optimization of sorting, Fast Fourier Transforms (FFTs), and matrix multiplications.

This theoretical shift manifests in highly practical software design patterns:

1. Read-Based Verification

Traditional sorting algorithms blindly move and swap elements in memory. In contrast, write-efficient sorting algorithms introduce an extra read phase to check if data is already ordered before committing a write. For example, the framework proposed in NVMSorting: Efficient Sorting on Non-Volatile Memory leverages "natural runs" to identify pre-existing order via read-only scans. By verifying data alignment beforehand, the algorithm bypasses destructive and slow write cycles, trading a minor increase in read volume for a massive reduction in total latency.

2. Structural Read-Write Trade-offs

In database indexing, Shimin Chen et al. pioneered "PCM-friendly" data structures in Rethinking Database Algorithms for Phase Change Memory. Instead of utilizing standard B+-trees that require frequent node rebalancing and pointer updates (writes), they designed modified tree structures and Hash Joins that tolerate slightly longer read paths in exchange for a drastic reduction in cell modifications.

3. Minimizing State Changes

This paradigm extends to data streams, where memory footprint and update frequency are tightly constrained. Rajesh Jayaram et al. address this in Streaming Algorithms with Few State Changes, proving that fundamental streaming estimations can maintain optimal space complexity while strictly minimizing the number of times the algorithm modifies its internal memory state.

Traditional Paradigm (Symmetric Costs):
[Data Input] ──> [Frequent Read/Write Updates in Place] ──> [Output]
                 (High NVM Write Penalty & Wear)

Asymmetric Paradigm (Write-Efficient):
[Data Input] ──> [Read-Only Scan / Verification] ──> [Selective, Minimal Writes] ──> [Output]
                 (Extra Cheap Reads Spent)           (NVM Lifespan & Speed Preserved)

Architectural and System-Level Mitigations

While algorithms solve the problem for specific applications, operating systems and hardware architectures employ structural mechanisms to mask NVM write asymmetry globally.

Hybrid Memory Tiering

A dominant architectural pattern pairs a small, symmetric, volatile memory tier (like DRAM) with a large, asymmetric, non-volatile tier (NVM). The goal is to isolate mutable state within the symmetric tier.

In Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs, Charles McGuffey et al. implement this by treating the immutable graph topology as a read-only structure mapped directly to high-capacity NVRAM. Meanwhile, all rapidly changing algorithm states (such as vertex frontiers and visited flags) are allocated in DRAM. This topology ensures that the bulk of execution traffic consists of fast NVRAM reads and DRAM writes, completely avoiding direct NVRAM writes during traversal.

Asymmetric Cache Replacement

Standard cache eviction policies like Least Recently Used (LRU) are "write-blind"—they evict pages based solely on access recency. In an asymmetric memory system, evicting a "dirty" (modified) page forces an expensive writeback to NVM, whereas evicting a "clean" page costs nothing because the data can simply be dropped.

To exploit this, Xi Zhang et al. developed the Asymmetric Read-Write (ARW) policy in ARW: Efficient Replacement Policies for Phase Change Memory and NAND Flash. Similarly, Youwei Yuan et al. introduced DPW-LRU: An Efficient Buffer Management Policy Based on Dynamic Page Weight for Flash Memory in Cyber-Physical Systems. These policies assign a higher "weight" or retention priority to dirty pages. By keeping modified pages in the fast cache tier longer, the system aggregates multiple logical writes into a single physical writeback, significantly lowering overall I/O latency.

Decoupling and Buffering

Hardware-level abstractions can also be used to shield the execution pipeline from slow persistence writes. For transactional databases, Fangming Lu et al. designed a mechanism detailed in Reducing Transaction Processing Latency in Hardware Transactional Memory-based Database with Non-volatile Memory. By introducing a specialized parity versioning scheme, they decoupled the fast, volatile execution of hardware transactions from the slower, asynchronous logging writes required by NVM. This allows the processor to complete transactions at CPU speeds without stalling for physical non-volatile persistence.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 112 papers
  2. Version 1 · 2026-10-04 · 124 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_volatile_memory_write_latency_6050751a,
  title = {non-volatile memory write latency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-volatile-memory-write-latency/rdr_6050751afd7b455daf10f1260055b73a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_volatile_memory_write_latency_6050751a_v2,
  title = {non-volatile memory write latency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-volatile-memory-write-latency/rdr_6050751afd7b455daf10f1260055b73a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake