The storage hierarchy quietly stopped being a hierarchy — a PCIe Gen4 flash SSD now delivers MORE bandwidth than byte-addressable Optane memory at 27× lower cost, while the Optane answers 100× faster and endures 500× more writes — so the old recipe of putting hot data on the fast device no longer has a fast device to point at; Prism instead decomposes the key-value store by what each COMPONENT needs (index and write buffer on low-latency NVM, bulk values log-structured on high-bandwidth SSDs, a scan-aware cache in DRAM) and stitches them together with an indirection table whose mutually-pointing entries give lock-free concurrency and logging-free crash consistency — beating state-of-the-art stores by up to 13.1× with 8.7× lower tail latency, at matched hardware cost.
The argument in one glance
-
Problem
The storage hierarchy is not a hierarchy anymore
For decades, storage design rested on a clean split: performance devices (fast at everything, expensive) above capacity devices (slow, cheap, big) — SSD over HDD. Every classic technique (caching, tiering, layered log-structured merge trees) is a strategy for keeping hot data on the fast layer. But measure today's devices and the split dissolves: a PCIe Gen4 flash SSD moves 7 GB/s of reads — MORE than Intel Optane persistent memory's 6.8 — at 27× lower cost per terabyte; meanwhile the Optane answers in 0.3 microseconds against the SSD's 50, and endures roughly 500× the lifetime writes. Neither device dominates. There IS no performance layer.
-
What people did
Bolt NVM onto the old hierarchies
The ecosystem retrofitted: NoveLSM puts the LSM-tree's memtable on NVM; SLM-DB moves the global index to NVM over single-level SSTables; MatrixKV does fine-grained compaction through an NVM level; SpanDB tiers two classes of SSD; the Ziggurat and Strata file systems write to NVM first and digest to SSD later. All keep the hierarchical shape: data enters the fast layer and migrates down.
-
Why it fell short
Hot-data promotion optimizes for a fast device that no longer exists
Place hot data on NVM and you enjoy its latency — while starving on its bandwidth, which a modern SSD array exceeds several times over. LSM designs still pay compaction and level-by-level traversal, burning CPU cycles that a recent line of work (KVell) showed are now the actual bottleneck — the devices got fast; the software stack did not. KVell's own answer — shared-nothing sharding over DRAM and SSD — trades that for load imbalance under skewed access, page-granularity caching, and batching queues that push 99th-percentile latency past a millisecond. And nobody addresses the new systems problem underneath: when one store's data lives simultaneously in DRAM, NVM, and SSD, how do you get concurrency control, crash consistency, and recovery ACROSS the media without one slow device serializing everything?
-
This paper's idea
Place components, not data — and let an indirection table hold it together
Prism (Sungkyunkwan, Konkuk, and Virginia Tech) reframes the question: not "which data goes on the fast device" but "which COMPONENT of a key-value store needs which physics." The key index — small random accesses — lives on low-latency NVM (persistent, so no write-ahead log). Bulk values — big and bandwidth-hungry — go log-structured onto flash SSDs in 512 KB chunks. Fresh writes land in per-thread append-only Persistent Write Buffers on NVM (instant durability, no write conflicts, and NVM's endurance absorbs the churn that would wear the SSD). A scan-aware DRAM cache absorbs read-hot values. The glue is the Heterogeneous Storage Index Table (HSIT): an NVM-resident indirection layer where forward pointers (table to value) and backward pointers (value to table) must mutually agree — one atomic pointer update is simultaneously the linearization point for concurrency, the commit point for crash consistency, and the validity test for recovery. Reads from SSD self-tune their batch size by drafting concurrent threads behind a leader. Result: up to 13.1× the throughput of state-of-the-art stores at matched hardware cost, tail latency up to 8.7× lower, and 100 GB recovered in 6.9 seconds with no log to replay.
Why this problem is worth solving
Key-value stores sit under databases, caches, file systems,
analytics, and serverless platforms — the storage
infrastructure’s common denominator — and their economics are
set by how well software exploits the devices underneath.
non-volatile memory in a DIMM
slot — Intel’s Optane DCPMM being the shipped example —
accessed by ordinary load and store instructions with
near-DRAM latency (0.3 microseconds), no storage stack in
the path, persistence across power loss, and effectively
unlimited endurance (about 292 petabytes written, versus a
flash SSD’s 0.6). Its weaknesses mirror its strengths:
bandwidth BELOW a modern flash SSD, capacity capped by
memory channels, and a price per terabyte 27–40× that of
flash
The paper’s second observation compounds the first: the
CPU, not the device, is now the scarce resource. Techniques
that made sense against 10-millisecond disks — compaction,
sorting, multi-level traversal, Bloom filters — are pure
overhead against microsecond media, and
the append-only discipline:
never overwrite in place; write new versions sequentially
and garbage-collect stale ones later. It converts random
writes into the large sequential writes flash performs best
and avoids read-modify-write cycles — at two recurring
costs this paper must pay back: stale versions accumulate
until collected, and values for adjacent keys scatter
across the log, destroying the spatial locality that range
scans depend on
What people did before, and where it broke
- Hierarchical LSM retrofits (NoveLSM, MatrixKV, SLM-DB, SpanDB, RocksDB-on-NVM). NVM becomes a faster top layer — but compaction and level traversal survive, and with them the CPU burn and write amplification; MatrixKV still trails Prism by up to 13.1× at equal hardware cost.
- NVM-first file systems (Strata, Ziggurat). Write to NVM, digest downward — still layer-by-layer data traversal, and system performance can pin to the slowest device in the chain.
- Shared-nothing sharding (KVell). Kill the CPU overhead by partitioning everything per core, batch aggressively into SSD queues. It works — until skew concentrates load on a few shards, page-granularity caching wastes DRAM on cold neighbors, and fixed-depth batching queues push write tails to 1,262 microseconds where Prism holds 145.
- The unaddressed layer. All of the above treat cross-media coordination as an afterthought: consistency via write-ahead logs on the slow device, recovery via full scans, concurrency throttled by whichever medium holds the lock state.
How Prism works
Five components, each on the medium its physics wants
-
Persistent Key Index — on NVM new
A central (not sharded) NVM-native range index (PACTree, swappable) maps each key to an HSIT slot. Index lookups are small random accesses — precisely what byte-addressable low latency serves — and NVM's persistence deletes the write-ahead log and the full-storage recovery scan. Centrality avoids shared-nothing's skew imbalance; modern lock-free index designs keep it from becoming the bottleneck.
-
Persistent Write Buffer (PWB) — on NVM new
Every write appends to the calling thread's own PWB: durable at NVM latency, on the critical path, with zero write/write conflicts by construction. Append-only means old versions are never overwritten — crash safety comes free. At a 50% watermark, a background thread collects only the LATEST version of each value and ships it to SSD — so write churn (hot keys updated repeatedly) is absorbed by NVM's near-infinite endurance and never amplifies SSD wear.
-
Value Storage — log-structured on flash SSDs new
Values (the bulk of the bytes) append in 512 KB chunks — the large sequential writes flash loves — via io_uring asynchronous IO, one Value Storage per SSD, chunks written concurrently with allocation as the only critical section. A DRAM validity bitmap marks stale values; greedy garbage collection merges the emptiest chunks in the background, non-blocking because readers go through the indirection table, never through the log's geography.
-
Scan-aware Value Cache (SVC) — on DRAM new
Read-hot values cache at VALUE granularity (not pages), admitted only on SSD reads, managed entirely off the critical path by a background thread with a two-queue LRU. Its second job repairs log-structuring's scan damage: values touched by the same range scan are chained together, and when one evicts, the whole chain is sorted and rewritten into a single SSD chunk — restoring the spatial locality the log destroyed, so the next scan of that range costs a fraction of the IO.
-
HSIT — the indirection spine, on NVM new
The Heterogeneous Storage Index Table is an array of 16-byte entries holding forward pointers to a value's current home (PWB, SSD, or DRAM cache). Values embed BACKWARD pointers to their entry. A value is valid exactly when the pointers mutually agree — "well-coupled." Because the key index maps to HSIT slots rather than locations, garbage collection, reclamation, and caching move values freely without ever touching (or locking) the index.
-
Opportunistic thread combining — for SSD reads new
Batch size for asynchronous reads is a dial between bandwidth (big batches) and latency (small ones). Prism lets CONCURRENCY set it: threads needing SSD reads enqueue on a combining queue; the first becomes leader and coalesces every waiting follower's request (up to depth 64) into one io_uring submission. Many concurrent readers yield big batches and full bandwidth; a lone reader gets a tiny batch and minimal latency — self-tuning, with no parameter. Worth 11.7× on read-only workloads.
The idea
Decompose by requirement, not by temperature. The hierarchical instinct asks “is this data hot?” and promotes accordingly — a one-dimensional answer for a multi-dimensional device landscape. Prism asks what each STRUCTURAL piece of a key-value store actually needs: the index does small random reads (latency — NVM); values are big and streamed (bandwidth and cost — SSD); the write path needs instant durability under churn (latency and endurance — NVM again); the read-hot set wants the fastest possible medium (DRAM). Each component lands where its physics is served and its weaknesses are irrelevant — NVM’s bandwidth ceiling never matters for index lookups; SSD’s latency never matters for background chunk appends. The same placement-by-appetite logic this site has watched govern coolant loops, model variants, and PIM dosage here organizes a storage engine — and the 13.1× at matched cost is the gap between exploiting the jungle and retrofitting the ladder.
One pointer update is the whole protocol. Scattering a store across three media threatens to multiply its coordination machinery — logs here, locks there, epochs everywhere. Prism compresses nearly all of it into the HSIT entry: the atomic forward-pointer update is the linearization point (no partial write is ever visible), the durability commit (dirty-bit plus flush-on-read makes the update durably linearizable), and the recovery oracle (a crash leaves either mutually-agreeing pointers — value valid — or a dangling half — value unreachable, predecessor intact). Write-ahead logging disappears; recovery becomes a pointer-agreement check that finishes 100 GB in 6.9 seconds. The append-only PWB supplies the enabling invariant: old versions are never destroyed, so there is always a consistent state to fall back to.
Let load set the batch size. Asynchronous IO forces a choice — batch big for bandwidth and CPU efficiency, or small for latency — and fixed choices (KVell’s constant queue depth) buy throughput with millisecond tails. Thread combining makes the batch size EQUAL the instantaneous concurrency: the leader submits exactly the requests that exist right now. Under load, batches are naturally large (and the followers’ CPU is freed the moment their request is drafted); under light load, batches are naturally small and latency-optimal. It is the second self-tuning batching design in this site’s recent pages — the serving page derives batch size from deadlines, Prism from concurrency — both replacing a static tuning knob with a signal the system already has.
One update, one read, one scan, one crash
Following requests through the three memories
Configuration from the evaluation: 40 threads, index and PWB on Optane NVM, eight SSDs of log-structured Value Storage, DRAM cache. Costs matched to competitors at $170 of storage hardware.
Step 1 of 5
Update: durable before the SSD even hears about it
A thread updates key k2. The new value appends to that thread's own Persistent Write Buffer on NVM — with its backward pointer embedded — then one compare-and-swap flips k2's HSIT forward pointer (dirty bit set, flushed, cleared). Total critical path: two NVM writes and an atomic. Durable, visible, linearized — average write latency 44 microseconds under YCSB-A versus 231 for KVell, with the 99th percentile at 145 versus 1,262.
per-thread PWBs make write/write conflicts structurally impossible the old version remains in the log until garbage collection — crash safety needs no undo
Why it works
- No modern device dominates, but every component’s needs are narrow → placing each component on the medium that serves its access pattern lets every device run in its sweet spot simultaneously → the store’s aggregate performance approaches the sum of the devices’ strengths rather than the minimum.
- Writes land append-only in per-thread NVM buffers → durability costs sub-microsecond latency, conflicts vanish structurally, and churn is absorbed by the medium with 500× the endurance → the SSD sees only coalesced, deduplicated, chunk-sized sequential writes.
- The key index maps to indirection slots, not locations → garbage collection, buffer reclamation, and caching move values without touching the index → background machinery runs concurrently and invisibly, and the index never serializes on the slowest medium.
- Forward and backward pointers must mutually agree → one atomic update is at once visibility, durability commit, and recoverability marker → cross-media consistency without write-ahead logging, and recovery as a pointer check instead of a log replay.
- Read-batch size equals instantaneous concurrency → bandwidth and CPU efficiency arrive exactly when concurrency does, latency when it does not → the latency-bandwidth dial tunes itself, and tail latency stays an order of magnitude below fixed-depth batching.
What it costs
- The hardware it celebrates died. Intel discontinued Optane months before publication; the paper’s own discussion pivots to CXL-attached persistent memory and memory-semantic SSDs as successors. The design’s latency/bandwidth/endurance reasoning transfers; the specific price-performance points do not.
- NVM overhead and configuration. Index plus HSIT consume ~5.4 GB of NVM per 100 million pairs, and PWB and cache sizes are watermark-tuned knobs (write throughput tracks PWB size directly).
- Indirection’s tax. Every access adds an HSIT hop — cheap on NVM, but real; and 16-byte entries for every key live forever in the table.
- Background debt. Garbage collection, cache management, and scan reorganization all consume background CPU and SSD bandwidth; the evaluation shows them well-hidden, but they are paid, and pathological churn narrows the margin.
- Evaluation scope. YCSB with Zipfian skew dominates the evidence (one Nutanix production trace aside), on a single two-socket node; distributed operation, replication, and multi-tenant isolation are out of frame.
The evaluation
Cost-normalized comparisons ($170 of storage per configuration) against MatrixKV, RocksDB-on-NVM, SLM-DB, and KVell, on a two-socket Xeon with six 128 GB Optane DIMMs and eight PCIe Gen4 SSDs, under YCSB (100 million to 1 billion 1 KB pairs, Zipfian 0.99) and a Nutanix production workload.
Three architectures for the post-hierarchy landscape
| Property | Hierarchical LSM retrofits (MatrixKV, RocksDB-NVM, SLM-DB) | Shared-nothing DRAM+SSD (KVell) | Prism |
|---|---|---|---|
| Organizing principle | |||
| Write path (YCSB-A) | Up to 13.1× slower; compaction burns CPU and amplifies writes, worse with skew | ||
| Reads and scans | 4.8–5.5× slower on read-heavy; scans traverse every LSM level | 1.2–1.7× slower; page-granular cache wastes DRAM; cached reads still queue behind IO workers | |
| Cross-media consistency & recovery | Write-ahead logs and level invariants; recovery scans | Full-SSD scan on recovery: 10.4 s per 100 GB; commit batches lose recent writes on crash | |
| Behavior under skew and scale | Compaction worsens with skew (write amplification grows) |
Check yourself
Check your understanding
1. Hierarchical stores put hot data on the fast device. Prism's authors argue this recipe is now incoherent. Predict the failure mode — and what Prism replaces the question with.
2. Every Prism value embeds a backward pointer to its HSIT entry, and the entry's forward pointer must agree ("well-coupled") for the value to count as valid. This one invariant replaces write-ahead logging entirely. Trace why.
3. KVell batches SSD reads at a fixed queue depth of 64 and pays millisecond tails; Prism's thread combining also reaches depth 64 but holds its 99th percentile an order of magnitude lower. What is different?
4. Log-structured value storage is what lets Prism write at SSD bandwidth — and it scatters adjacent keys across the log, which should make range scans terrible. Prism's scans instead beat every competitor. Predict the repair mechanism.
Sources
- ACM DL: Prism: Optimizing Key-Value Store for Modern Heterogeneous Storage Devices — ASPLOS 2023 (open access)