Revisiting Log-Structured Merging for KV Stores in Hybrid Memory Systems

Key-value stores built on LSM-trees (RocksDB and kin) batch random writes into big sequential files and merge-sort them level by level — a design that made sense for slow spinning disks but wastes effort on byte-addressable persistent memory, where MioDB (Huazhong University of Science and Technology) shows two costs dominate — serializing in-memory skiplists into disk-format files (and deserializing them back, up to 59% of read time) and stalling writes while slow compaction drains a full level (up to 62% of write time); MioDB throws out the disk file format and keeps the skiplist itself persisted on NVM, so flushing is a single memcpy plus a background pointer fix-up, compaction merges levels by rewiring pointers without moving any data, and unlimited-capacity levels compact in parallel so fast writes never wait on slow merges — cutting write amplification from about 6x to 2.9x and 99.9th-percentile latency from roughly 1 millisecond to 45 microseconds.

The argument in one glance

Problem

A database design built for slow disks, now running on fast memory

LSM-tree key-value stores — the engine inside RocksDB, LevelDB, Cassandra — are everywhere, and their whole design is shaped by one assumption: the storage underneath is a slow block device where random writes are catastrophic and only sequential writes are fast. So they buffer writes in an in-memory sorted skiplist, and when it fills, SERIALIZE it into a block-formatted file (an SSTable) written sequentially to disk, then repeatedly MERGE-SORT those files across exponentially larger levels to keep data sorted. It is a beautiful fit for hard drives and SSDs. But when the storage becomes byte-addressable persistent memory (Intel Optane) — as fast and fine-grained as DRAM, yet durable — that founding assumption quietly stops being true, and much of the machinery becomes wasted motion.
What people did

Port the LSM-tree onto NVM and tune the worst parts

The prior NVM key-value stores kept the LSM-tree and patched its hot spots. NoveLSM put a large mutable MemTable in NVM to absorb more writes before flushing. MatrixKV replaced the troublesome L0 level with a matrix container and did fine-grained column compaction to cut the L0-to-L1 cost. SLM-DB used a single NVM level with a B+-tree index. Each keeps the SSTable-and-compaction framework and optimizes the step that hurts most, hoping to carry the LSM-tree onto the new hardware with surgical fixes.
Why it fell short

The serialization and the stalls are the whole cost, and they remain

Measuring the patched systems reveals that the two dominant costs are exactly the ones the block-device design imposes, and the patches do not remove them. SERIALIZATION: flushing still serializes an in-memory skiplist into a block-based SSTable, and reading still deserializes it back — deserialization alone is 50.7% to 58.6% of read time. That work exists only to fit a block file format that byte-addressable NVM does not need. STALLS: level-to-level compaction is slower than DRAM-to-NVM flushing, so writes stall waiting for a full level to drain — cumulative stalls are 62.5% of total write time — and data is rewritten 5.6 to 6.6 times across levels (write amplification). Patching L0 or enlarging a MemTable trims the symptoms; the block-format serialization and the flush-versus-compaction imbalance survive because they are baked into the LSM-tree itself.
This paper's idea

Keep the skiplist on NVM, and move pointers instead of data

MioDB (Huazhong University of Science and Technology) stops porting the disk design and rebuilds around what NVM actually is: byte-addressable and persistent. So it keeps the SAME skiplist across the DRAM-NVM boundary — persisting skiplists directly on NVM (PMTables) instead of serializing to SSTables. Four moves follow. ONE-PIECE FLUSHING copies a full MemTable to NVM with a single memcpy, then fixes up the internal pointers in the background. ZERO-COPY COMPACTION merges levels by rewiring skiplist pointers, never moving a data node. ELASTIC LEVELS give each level unlimited capacity, so a fast flush never blocks on a slow compaction. PARALLEL COMPACTION runs one independent thread per level to balance flushing against merging. Together they cut serialization to zero, write stalls by 96-97%, write amplification from about 6x to 2.9x, and 99.9th-percentile latency from around a millisecond to 45 microseconds.

Why this problem is worth solving

LSM-tree stores power a huge fraction of the world’s write-heavy databases, and their entire structure is a careful accommodation of one hardware fact that is now changing. The accommodation is the

the sequence an LSM-tree uses to turn random writes into disk-friendly sequential ones. New writes land in an in-memory sorted skiplist called the MemTable. When it fills, it becomes immutable and is SERIALIZED into a block-based Sorted String Table (SSTable) and flushed to storage. SSTables are organized into LEVELS — L0, L1, up to Ln — where each level holds roughly ten times more data than the one above. A background process called COMPACTION continually merge-sorts SSTables from one level into the next, discarding overwritten versions and keeping each level sorted. This converts every logical random write into batched sequential I/O, which is exactly what a hard drive or SSD wants, at the cost of rewriting data many times as it descends the levels

. Every piece of that — the block format, the serialization, the many levels, the compaction — is engineered to avoid random writes to a slow device. It is one of the great designs of storage systems, precisely because it respects the hardware it was built for.

The catch is that persistent memory is not that hardware, and the mismatch turns careful engineering into overhead. On

non-volatile memory such as Intel Optane persistent memory: storage that sits on the memory bus, is addressed byte-by-byte like DRAM (not in fixed blocks like a disk), is nearly as fast as DRAM, and yet retains its contents across power loss. Crucially, random access is as cheap as sequential access, and the CPU can read and write individual bytes in place without any block-transfer step. This overturns the two premises the LSM-tree was built on: there is no penalty for random writes to avoid, and there is no block-transfer boundary that data must be serialized to cross. An in-memory data structure can simply live, persistently, in NVM as-is

, so the serialization that packs a skiplist into an SSTable and the deserialization that unpacks it are pure waste — work performed to satisfy a constraint that no longer exists. And because NVM flushing is so fast, the slow compaction that was hidden behind slow disk I/O is now exposed as the bottleneck, stalling writes. The reason to revisit the design is that these are not small inefficiencies: on NVM they are the majority of read time and write time. The opportunity is to keep the LSM-tree’s genuine benefit (write-optimization, sorted data) while deleting everything it did only to appease a disk.

What people did before, and where it broke

Classic LSM-trees on NVM (RocksDB, LevelDB ported). Treat NVM as a fast disk. This keeps every disk-era cost — block-format serialization on flush, deserialization on read, and heavy cross-level compaction with 10x-plus write amplification — none of which NVM requires, so most of the work is wasted motion.
NoveLSM (bigger NVM MemTable). Puts a large mutable MemTable in NVM to absorb more writes before flushing. But it still serializes when data moves to SSDs and pays costly merging into a big skiplist; flushing a 4GB MemTable is enormously slow, and its write amplification is 6.6x.
MatrixKV (redesigned L0). Replaces L0 with a matrix container and does fine-grained column compaction to reduce the L0-to-L1 cost. It helps the worst level, but still serializes on flush (deserialization is 58.6% of read time) and still suffers cumulative write stalls of 62.5% of write time.
SLM-DB (single NVM level, B+-tree index). Collapses to one level with a B+-tree index. But compaction must maintain B+-tree order with costly candidate selection, and its operations must be serialized, so it cannot compact in parallel.
The gap. Every prior system kept the SSTable-and-compaction framework and optimized a piece of it, so the two costs baked into that framework — block-format serialization and the flush-versus-compaction imbalance — persisted. MioDB removes the framework itself, keeping skiplists on NVM and merging them by pointer, so those costs disappear rather than shrink.

How MioDB works

Persist the skiplist, flush in one piece, compact by pointers, and never block

Keep the skiplist across the DRAM-NVM boundary new

Instead of serializing the MemTable into a block-based SSTable, MioDB persists skiplists directly on NVM as PMTables (persistent MemTables). Because NVM is byte-addressable and durable, the very same pointer-linked structure that lives in DRAM can live, persistently, in NVM — so there is nothing to serialize or deserialize when data crosses the boundary.
↓ →
One-piece flushing (single memcpy + swizzle) new

A full immutable MemTable is flushed to NVM with ONE memcpy into an identically-laid-out region — no per-node insertion, no serialization. The copied skiplist's internal pointers now point at stale DRAM addresses, so a background thread SWIZZLES them by adding the fixed DRAM-to-NVM offset, while the original DRAM copy stays readable until the fix-up finishes. Flushing a 64MB table takes about 11 milliseconds, 37.6x faster than NoveLSM.
↓ →
Zero-copy compaction (merge by rewiring pointers) new

Merging two levels does not move any data. MioDB splices the newer skiplist into the older by updating predecessor and successor pointers, keeps the newest of any duplicate key and NULLs out old versions, and uses insertion marks so concurrent, lock-free queries always find every node during the rewiring. No data node is copied, so write amplification collapses.
↓ →
Elastic, unlimited-capacity levels new

Unlike a classic LSM-tree where each level has a fixed size ten times the last, a MioDB level can hold any number of PMTables. So a fast one-piece flush into L0 never has to wait for a slow L0-to-L1 compaction to make room — the level just holds more tables, and the costly merging is postponed to the background.
↓ →
Parallel compaction, one thread per level new

Because levels no longer block each other on capacity, MioDB runs an independent compaction thread per level; the moment a level has two PMTables they merge. Compactions across levels run concurrently, so data flows quickly down to the bottom level and fast flushing and slow merging stay balanced — the write stalls nearly vanish.
↓ →
Consolidate reads with depth, Bloom filters, and a huge bottom level new

Many small PMTables per level speed writes but slow reads, so MioDB counters with more levels (PMTables grow larger and fewer to scan), a mergeable Bloom filter per PMTable to skip non-matching tables, and a single huge sorted PMTable at the bottom level (Ln) that a lazy-copy compaction only garbage-collects.

Evaluated on Intel Optane DCPMM with db_bench micro-benchmarks and YCSB (80GB dataset), against NoveLSM, MatrixKV, and NoveLSM-NoSST (a single big skiplist), measuring write/read throughput, tail latency, write stalls, and write amplification.

The idea

When the hardware changes, revisit which parts of the design were only ever compensation. The LSM-tree is a monument to one constraint — random writes to a block device are ruinously slow — and nearly everything distinctive about it (serialize into sequential SSTables, pile them in ten-fold levels, compact endlessly) exists to convert random writes into sequential ones. Byte-addressable NVM removes that constraint entirely, so MioDB’s first move is to ask which machinery was serving the workload and which was only serving the disk, and delete the latter. The serialization, the block format, the deserialization on read — all of it was compensation for a penalty that no longer exists on NVM, so it becomes pure overhead. This is the revisit-the-premise discipline the site prizes: a design is only as valid as the assumption it was built on, and when the hardware moves, the honest response is not to patch the old structure but to strip out what it was compensating for.

Move the reference, not the data. The two most expensive operations both become nearly free the same way — by manipulating pointers instead of bytes. One-piece flushing copies a skiplist to NVM in a single memcpy and then merely fixes up its pointers in the background; zero-copy compaction merges two skiplists purely by rewiring predecessor and successor pointers, moving no data node at all. The data stays where it is; only the names that refer to it change. This is the address-indirection trick the site sees dissolving data movement across every layer — the GPU-microservice page passing an 8-byte memory handle instead of copying a tensor, the GPU-memory-pooling and on-NIC-memory pages remapping addresses rather than moving payloads — and here it is what turns a heavyweight merge-sort into a handful of pointer writes, cutting write amplification from about 6x to 2.9x.

Decouple the fast path from the slow one, and let a buffer absorb the mismatch. Once flushing is fast and compaction is comparatively slow, forcing a flush to wait on a compaction (as fixed-capacity levels do) reintroduces the stall NVM should have killed. MioDB’s elastic, unlimited-capacity levels break that coupling: a flush always has somewhere to land, and the expensive merging is deferred to independent background threads, one per level, that run in parallel. The buffer absorbs write bursts and the slow work is pushed off the critical path — the same decouple-and-defer discipline the site sees when a system balances a producer against a slower consumer by buffering between them, and it is what shrinks write stalls by 96 to 97%.

A write, the old way and the MioDB way

From serialize-and-merge-sort to memcpy-and-rewire

The life of a write in an LSM-tree KV store on persistent memory. Numbers from MioDB's evaluation.

Step 1 of 5

The classic path: serialize, flush, compact

A write lands in the DRAM MemTable (a skiplist). When it fills, the classic LSM-tree serializes that skiplist into a block-formatted SSTable file, flushes it, and later a compaction reads SSTables from one level, merge-sorts them with the next level's, and writes new files down — moving and rewriting the data repeatedly as it descends.

this converts random writes to sequential I/O — a win on disks, where random writes are catastrophic
data is rewritten 5.6 to 6.6 times across levels (write amplification) in NoveLSM and MatrixKV

Why it works

The LSM-tree serializes to a block format only to cross a slow disk boundary → NVM is byte-addressable, so the skiplist can persist in place → serialization and deserialization drop to zero, reclaiming up to 58.6% of read time.
Flushing an identically-laid-out skiplist needs no reformatting → a single memcpy plus a background pointer swizzle replaces per-node insertion → flush latency falls 37.6x, and the swizzle is off the write path.
Merging sorted skiplists can be done by relinking pointers rather than copying nodes → zero-copy compaction moves no data → write amplification collapses from about 6x to 2.9x.
Fixed-capacity levels force a fast flush to wait on a slow compaction → unlimited-capacity levels give a flush somewhere to land and defer merging to the background → write stalls fall 96 to 97%.
Independent levels can no longer block one another → one parallel compaction thread per level balances flushing against merging → data reaches the bottom level fast and the pipeline stays balanced.

What it costs

Scans suffer from many small tables. MioDB’s fast writes create many small PMTables per level, and Bloom filters help point lookups but not range scans — so on scan-heavy workloads (YCSB-E, 95% scans) it can underperform a single-big-skiplist design until compaction consolidates the data into the bottom level.
A real write-speed-versus-read-speed tension. The elastic buffer that makes writes fast leaves data spread across many redundant small tables, and read tail latency in the worst case grows roughly linearly with the number of PMTables a query must check; the design trades read consolidation for write speed.
Bloom filters degrade at scale. During heavy write bursts, large PMTables accumulate and their merged Bloom filters develop high false-positive rates, weakening the main read optimization exactly when there are the most tables to skip.
Crash consistency is intricate. Zero-copy compaction needs atomic pointer writes, and the insertion marks and state during a merge create several corner cases that recovery must handle correctly — more subtle than flushing self-contained files.
NVM-specific, with swizzling overhead. The whole design exploits byte-addressability and persistence, so it does not transfer to plain DRAM-and-SSD systems; and pointer swizzling, though asynchronous, still costs background work and holds the DRAM copy until it completes (the authors rejected offset-based pointers as making compaction costlier).

The evaluation

Intel Optane DCPMM hybrid memory, db_bench micro-benchmarks and YCSB over an 80GB dataset, against NoveLSM, MatrixKV, and NoveLSM-NoSST (a single large NVM skiplist), measuring throughput, tail latency, write stalls, and write amplification.

Running an LSM key-value store on persistent memory

Property	Classic LSM ported to NVM	MatrixKV (NVM-tuned L0)	MioDB (skiplists on NVM)
Flush method
Compaction
Serialize / deserialize cost
Write stalls
99.9th-percentile latency (4KB)

MioDB's gains are largest on write- and tail-latency-sensitive workloads: 2.5-3.1x random write throughput and 21.7x lower 99.9th-percentile latency versus MatrixKV, with write amplification cut about 5x. The cost lands on scan-heavy reads, where many small PMTables and Bloom-filter limits erode the advantage until data consolidates into the bottom level.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

MioDB buys its write speed with a real read-side tension. The elastic buffer that lets flushes never block also spreads data across many small, partly-redundant PMTables, and because Bloom filters accelerate point lookups but not range scans, scan-heavy workloads (YCSB-E) can trail a single-big-skiplist design until compaction consolidates the data into the huge bottom level; read tail latency in the worst case grows roughly with the number of tables a query must check, and merged Bloom filters lose accuracy at large sizes just when they are needed most. The zero-copy and one-piece machinery also raises the stakes on crash consistency — atomic pointer updates and insertion-mark state create corner cases recovery must get exactly right — and pointer swizzling, though asynchronous, is not free and pins the DRAM copy until it completes. And the whole approach is intrinsically tied to byte-addressable persistent memory; it does not carry over to plain DRAM-and-SSD systems. None of this weakens the core lesson — that the LSM-tree’s serialization and heavy compaction were compensation for a slow block device, so on byte-addressable NVM the right move is to persist the skiplist in place and merge it by moving pointers instead of data, which turns the two biggest costs into nearly nothing.

Background

Revisit the premise when the hardware moves, and move references not data

MioDB sits in the site’s storage-and-memory-systems cluster and rhymes with several ideas covered elsewhere on this site. Its governing move is to revisit a design once its founding hardware assumption has changed: the LSM-tree exists to convert random writes into sequential ones because block devices punish random writes, and byte-addressable NVM erases that penalty, so MioDB strips out the serialization and heavy compaction that were only ever compensation for the disk — the same design-is-only-as-valid- as-its-assumption discipline the site applies when it asks whether a mechanism is serving the workload or only serving a constraint that has since disappeared. Its two central mechanisms are the address-indirection trick the site meets again and again: one-piece flushing and zero-copy compaction both move the REFERENCE, not the data — a single memcpy plus a pointer swizzle to flush, and pointer rewiring to merge — exactly the pass-the-name-not-the-payload move the GPU-microservice scheduling page uses to hand over an 8-byte memory handle instead of copying a tensor, and that the GPU-memory- pooling and on-NIC-memory pages use to dissolve data movement by remapping addresses. And its elastic, unlimited-capacity levels with parallel per-level compaction are a decouple-the-fast-path- from-the-slow-path move: let a buffer absorb the write burst and push the expensive merging off the critical path into background threads, the same producer-faster-than-consumer balancing the datacenter-scheduling and pipeline pages rely on. Even its honest write-fast-read-slower trade-off is the recurring reminder that a buffer which smooths one side of a pipeline usually owes a cost to the other.

If you remember only three things

1. LSM-tree key-value stores (RocksDB and kin) are built to convert random writes into sequential ones — buffering writes in an in-memory skiplist, serializing it into block-based SSTable files, and merge-sorting those files across exponentially larger levels — a design tuned for slow block devices; but on byte-addressable persistent memory that premise no longer holds, and the two costs it imposes become the whole bottleneck: serializing skiplists into SSTables and deserializing them back (up to 58.6% of read time), and write stalls while slow compaction lags fast flushing (62.5% of write time), plus 5.6-6.6x write amplification.
2. MioDB rebuilds the store around what NVM actually is: it persists skiplists directly on NVM (PMTables) instead of serializing to SSTables, flushes a full MemTable with a single memcpy plus a background pointer swizzle (one-piece flushing), merges levels by rewiring skiplist pointers without moving any data node (zero-copy compaction, with insertion marks for lock-free concurrent reads), gives each level unlimited capacity so a fast flush never blocks on a slow compaction, and runs one parallel compaction thread per level to balance flushing against merging.
3. The result cuts serialization to zero, write stalls by 96-97%, write amplification from about 6x to 2.9x, and 99.9th-percentile latency from roughly a millisecond to 45 microseconds (21.7x lower than MatrixKV), with 2.5-3.1x higher write throughput — at the honest cost of a write-fast-read-slower tension (many small tables hurt scans until they consolidate) and intricate crash consistency, all specific to persistent memory. The durable lessons: when the hardware assumption changes, delete the machinery that was only compensating for the old device, and dissolve data movement by moving references instead of data.

Check yourself

Check your understanding

1. LSM-trees serialize in-memory skiplists into block-based SSTable files, and prior NVM systems kept doing so. Predict why this serialization is pure overhead on byte-addressable persistent memory.
2. MioDB flushes a MemTable with a single memcpy and merges levels by rewiring pointers, in both cases avoiding moving the actual data. Predict the general principle these two mechanisms share and why it is so effective.
3. On fast NVM, MioDB finds that slow compaction stalls writes for a large fraction of the time, and it responds with unlimited-capacity levels plus one parallel compaction thread per level. Predict why fixed-capacity levels caused the stalls and why the elastic design removes them.
4. MioDB delivers huge write and tail-latency wins but can underperform a simple single-big-skiplist design on scan-heavy workloads. Predict what this reveals about the design's central trade-off.

Sources

ACM DL: Revisiting Log-Structured Merging for KV Stores in Hybrid Memory Systems — ASPLOS 2023 (the MioDB system; full text read via the ACM PDF; no arXiv preprint).