Nemo: A Low-Write-Amplification Cache for Tiny Objects on Log-Structured Flash Devices

Xufeng Yang, Tingting Tan, Jingxin Hu, Congming Gao, Mingyang Liu, Tianyang Jiang and 4 others

Datacenters cache billions of tiny key-value objects on flash SSDs to save money, but flash wears out from "write amplification" — writing far more than the actual data — and for tiny objects the cache software itself is the culprit, flushing mostly-empty blocks to flash; this paper (Xiamen University and Tsinghua — Xufeng Yang, Jiwu Shu, and colleagues) presents Nemo, which counterintuitively shrinks the hash space to force objects to collide and pack blocks nearly full before writing, cutting the software's write amplification close to the theoretical minimum.

The argument in one glance

Problem

Caching tiny objects on flash wears the flash out through write amplification

Datacenters use key-value caches to speed up services — key-value stores, social media, content delivery — and these services handle massive volumes of tiny objects, each only a few hundred bytes or less. As the scale grows, so does the demand for cache capacity, and because DRAM is expensive and limited, systems increasingly put the cache on flash SSDs, which are far cheaper per byte. But flash behaves differently from memory. You cannot overwrite a flash location in place; updates go to a new location and the old one must later be erased, and flash can only be written a limited number of times before it wears out. So a flash cache has to worry about something a memory cache never did: write amplification, which means writing more data to the flash than the actual data you wanted to store. Every extra byte written eats into the flash's limited lifetime. For tiny objects this is acute, in two ways. First, the number of index entries needed to track where each tiny object lives on flash grows sharply, straining memory. Second, and worse, there is a mismatch between a tiny object and flash's coarse write granularity — flash is written in relatively large chunks, so writing a handful of tiny objects can force writing a whole chunk, hugely amplifying the writes. A flash cache for tiny objects must therefore juggle three things at once: a low miss ratio, small memory overhead, and low write amplification.
What people did

Use log-structured SSDs to make device-level write amplification near-ideal

The hardware industry has attacked write amplification with advanced log-structured SSDs — Zoned Namespace (ZNS) and Flexible Data Placement (FDP) drives from vendors like Western Digital and Samsung. These let the application manage where data is placed on the flash in a way that matches how flash prefers to be written (sequentially, in large batches), which minimizes the write amplification caused by the SSD's own internal garbage collection — the device-level write amplification. On such drives, the device's contribution to wasted writes can be driven down almost to the ideal.
Why it fell short

The cache software still writes half-empty blocks, so its own amplification dominates

Making the device near-ideal is not enough, because there are two sources of write amplification, and log-structured SSDs only fix one. Device-level write amplification comes from the SSD's internal housekeeping; application-level write amplification comes from how the cache software itself packs and flushes data. Even when the device level is near-ideal, the application level still dominates — and its root cause is the cache's structure. Flash caches are set-associative: objects are hashed into fixed-size "sets," and a set is the unit that gets flushed to flash. To avoid wasted writes, you want each set to be nearly full before it is flushed, because flushing a half-empty set wastes the empty space. But with a large hash space, incoming objects scatter thinly across an enormous number of sets, so at flush time most sets are nearly empty. Prior designs suffer exactly this: the paper reports an average set fill rate of only 7 percent, meaning the cache is writing mostly padding. That low fill rate is the application-level write amplification, and no amount of device cleverness removes it. What was missing was a cache structure that keeps its sets full so it writes almost nothing but real data — while still keeping the per-object index metadata small.
This paper's idea

Shrink the hash space to force collisions and pack sets full

Nemo is a flash cache for tiny objects whose central move is counterintuitive: rather than spreading objects thinly to avoid hash collisions, it deliberately increases the collision probability by using a small hash space, so objects pile into the same few sets and fill them up before they are flushed. Concretely, Nemo hashes incoming objects into a small in-memory Set-Group (SG) containing a few fixed-size sets; the small hash range means many objects collide into the same sets, driving the set fill rate way up. The one wrinkle is that although hashed keys are uniform over the long run, they are skewed during the brief window when a Set-Group is filling from empty, which would leave some sets lagging. Nemo smooths out this transient skew with three mechanisms, raising the average set fill rate from 7 percent to over 89 percent. Full Set-Groups are then flushed to the SSD and organized into a FIFO-managed on-flash pool; when space runs low, Nemo evicts a whole Set-Group at a time. This batched write-and-invalidate pattern is exactly what log-structured flash likes, so it works hand in hand with the device. The result is an application-level write amplification of about 1.56 — close to the theoretical optimum of 1 — with device-level write amplification as low as 1 on ZNS, FDP, and even conventional SSDs. To keep memory small even for tiny objects, Nemo approximates the object index with a Parallel Bloom Filter Group (space-efficient probabilistic filters queried in parallel to locate an object) instead of exact per-object maps, offloads stable metadata like the index to flash while keeping frequently-updated metadata in memory, and tracks each object's hotness with just one bit. Together, Nemo achieves all three flash-cache goals at once: low write amplification, high memory efficiency, and low miss ratio.

Why this problem is worth solving

Flash KV caches are becoming the backbone of large-scale caching, and write amplification is what limits their lifetime and cost, especially for the tiny objects these systems are full of.

Caching at datacenter scale is shifting from DRAM to flash because flash is far cheaper per byte and lets caches grow to the capacities modern services need. But flash has a finite write budget: every write brings it closer to wearing out, so the effective cost and lifetime of a flash cache are governed by how much it writes. Write amplification — writing more than the real data — directly shortens that lifetime and raises cost, so minimizing it is not a marginal optimization but the thing that determines whether flash caching is economical. Tiny objects, which these caching workloads are dominated by, make it worse on both fronts: they need more index entries per unit of flash (straining memory), and their size mismatch with flash’s write granularity inflates the writes. So a flash cache that could write almost nothing but real data, while keeping its index small, would substantially extend flash lifetime and cut cost across a huge and growing class of caching deployments. Because the same tiny-object caching pattern recurs across key-value stores, social platforms, and content delivery, the payoff is broad.

The key realization inverts a basic instinct: for this problem, hash collisions are a feature, not a bug.

Hashing is normally designed to avoid collisions — you want keys spread evenly so no bucket is overloaded. But in a set-associative flash cache, the unit of writing is a set, and the enemy is not an overloaded set, it is an underfull one: flushing a half-empty set to flash writes wasted padding, which is precisely the application-level write amplification. Spreading objects thinly across a large hash space, the collision-avoiding instinct, guarantees that sets are nearly empty when flushed — a 7 percent fill rate. Nemo’s insight is to do the opposite: shrink the hash space so objects collide into the same small group of sets and fill them up before flushing. Collisions, here, are what pack the sets, and packed sets are what eliminate wasted writes. The subtlety is that this only works if the sets fill evenly; during the short transient when a Set-Group is filling from empty, the hashing is momentarily skewed and some sets lag, which is why Nemo needs the three smoothing mechanisms to push the fill rate from that already-improved level up past 89 percent. Once the sets are full, flushing and evicting whole Set-Groups in FIFO order produces exactly the large, sequential, batched writes that log-structured flash is built for, so the application and the device finally pull in the same direction. The whole design follows from turning the usual view of collisions upside down.

What people did before, and where it broke

Cache tiny objects in DRAM. Keep the key-value cache entirely in memory. Where it broke. DRAM is expensive and capacity-limited, so it does not scale to the cache sizes modern services need.
Move the cache to flash SSDs. Use cheaper, larger flash as the cache medium. Where it broke. Flash has limited write endurance and out-of-place updates, so write amplification wears it out, especially for tiny objects.
Adopt log-structured SSDs (ZNS, FDP). Let the application place data to match flash-friendly write patterns, minimizing device-level write amplification. Where it broke. It only fixes the device level; the application-level write amplification from the cache software still dominates.
Use a large hash space in a set-associative cache. Spread objects to avoid collisions. Where it broke. Objects scatter thinly, so sets are only about 7 percent full when flushed, and the cache writes mostly padding.
The gap. No design kept the cache’s sets nearly full — so it wrote almost only real data — while also keeping the per-object index metadata small enough in memory for tiny objects.

How Nemo works

Packing sets full by embracing collisions, then flushing flash-friendly

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Reduce write amplification by matching the cache’s writes to log-structured flash. Nemo flushes and evicts whole Set-Groups in FIFO order, producing large, sequential, batched writes that log-structured SSDs handle with minimal amplification. Cutting write amplification by restructuring how a storage system writes so its pattern aligns with the log-structured, batch-friendly nature of flash is the same objective the work on efficient compactions between storage tiers (PrismDB) covered elsewhere on this site pursues, organizing writes to keep flash write costs low. Nemo applies it to a tiny-object cache, where the batched unit is a packed Set-Group.

Shrink the index with a compact, probabilistic hash structure. Nemo replaces exact per-object maps with a Parallel Bloom Filter Group, accepting a small false-positive rate in exchange for far less memory to locate objects. Using a compact hash-based structure to index data in a fraction of the memory an exact mapping would need is the same approach the work on nested elastic cuckoo page tables for virtualized memory translation covered elsewhere on this site takes, packing an index into much less space than the naive form. Nemo does this for tiny-object indexing, where per-object exact maps would otherwise dominate memory.

Design the write pattern for what flash actually wants. Nemo’s whole flushing and eviction scheme is built around flash’s preference for large batched writes and invalidations rather than small in-place updates. Restructuring the I/O pattern of a storage stack to fit the flash-friendly, barrier-and-batch behavior of the device, instead of fighting it, is the same principle the work on reconstructing the Android I/O stack for barrier-enabled flash (LazyBarrier) covered elsewhere on this site is built on, shaping writes to the medium. Nemo shapes its cache writes into full-Set-Group flushes that flash can absorb cheaply.

Following an object through Nemo

Inserting and locating a tiny object with minimal writes and memory

A trace, drawn from the paper, of how Nemo caches a tiny object without amplifying writes or bloating memory.

Step 1 of 5

A tiny object is hashed into a small Set-Group

A new key-value object arrives and is hashed into a small in-memory Set-Group of a few fixed-size sets. Because the hash space is small, many objects collide into these same sets rather than scattering across a huge range.

Deliberate collisions are what will pack the sets full.

Why it works

Full sets write real data, not padding. A large hash space leaves sets about 7 percent full, so flushes are mostly wasted space → but collisions from a small hash space pack sets nearly full → so the cache writes almost only real objects and application-level amplification collapses.
Skew-smoothing makes the collisions pay off. A filling Set-Group is transiently skewed, leaving some sets underfull → but three mechanisms even out the fill during that window → so the average fill rate reaches over 89 percent rather than stalling.
Batched group flushes suit log-structured flash. Small scattered updates cause device garbage-collection amplification → but flushing and evicting whole Set-Groups in FIFO order → so the writes are large and sequential and device-level amplification drops as low as 1.
Bloom filters index in a fraction of the memory. Exact per-object maps would dominate memory for tiny objects → but a Parallel Bloom Filter Group locates objects probabilistically and compactly → so indexing memory shrinks while lookups stay fast via parallel queries.
One-bit hotness keeps the miss ratio low cheaply. Fine-grained hotness counters cost too much memory per tiny object → but tracking hotness with a single bit drawn from the in-memory index → so Nemo evicts wisely and keeps misses low without bloating memory.

What it costs (trade-offs and scope)

Bloom-filter indexing is approximate. A Parallel Bloom Filter Group can return false positives, so Nemo trades a small chance of an unnecessary lookup for large memory savings; the design keeps this rate low, but it is an approximation an exact index would not have.
The collision strategy needs the skew-smoothing to work. Simply shrinking the hash space would leave sets unevenly filled during the transient; Nemo’s benefit depends on its three smoothing mechanisms doing their job, which is added machinery a naive small-hash design lacks.
Whole-Set-Group eviction is coarse. Evicting an entire group at once keeps writes flash-friendly but is a blunt granularity; guided by one-bit hotness it keeps misses low, but a workload whose hot and cold objects are thoroughly mixed within groups gives it less to work with.
It targets tiny-object flash caches specifically. Nemo’s gains come from the tiny-object regime, where index pressure and the size-versus-granularity mismatch are worst; larger objects or non-cache flash workloads would not see the same benefit.
Reported figures are workload- and device-specific. The 7-to-89-percent fill rate, 1.56 application-level and as-low-as-1 device-level amplification come from the paper’s workloads and SSDs (ZNS, FDP, conventional); the exact numbers depend on the object distribution and the drive.

The evaluation

Caching tiny objects on flash SSDs

Property	Large-hash set-associative (prior)	Log-structured SSD alone	Nemo
Set fill rate
Application-level write amplification
Device-level write amplification
Index memory for tiny objects
Miss ratio

A comparison of ways to cache tiny objects on flash. By shrinking the hash space to force collisions that pack sets nearly full (fill rate 7 to over 89 percent), flushing and evicting whole Set-Groups FIFO to suit log-structured flash, and indexing compactly with bloom filters plus one-bit hotness, Nemo reaches an application-level write amplification of about 1.56 (near the optimum of 1) and device-level as low as 1, while keeping memory low and the miss ratio low. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ arXiv copy, 2603.09605, of the ASPLOS 2026 paper). The described system is the paper’s: Nemo is a flash-based key-value cache for tiny objects that reduces application-level write amplification (ALWA) by enhancing set-associative cache design to increase hash collision probability and thereby raise the set fill rate. It hashes objects into a small in-memory Set-Group (SG) of fixed-size sets; because hashed keys are skewed while an SG transitions from empty to filled, Nemo uses three mechanisms to smooth the skew, raising the average set fill rate from 7.0 percent to over 89 percent. Full SGs are flushed to a FIFO-managed on-flash SG pool, and SG-level eviction is used when space is insufficient, aligning with log-structured SSDs via batched writes and invalidation; the paper reports an ALWA of about 1.56 (near the theoretical optimum) and device-level write amplification (DLWA) as low as 1 on log-structured SSDs such as ZNS, FDP, and conventional namespace SSDs. For low memory overhead, Nemo introduces a Parallel Bloom Filter Group (PBFG) that approximates object indexing with multiple bloom filters queried in parallel, selectively offloads stable metadata (such as the index) to flash while keeping frequently-updated metadata (such as hotness) in memory, and uses a coarse-grained, one-bit-per-object hybrid hotness tracking. The paper states Nemo simultaneously achieves low write amplification, high memory efficiency, and low miss ratio. The background above on flash out-of-place updates, write endurance, set-associative caching, and bloom filters is standard storage context. The step-by-step walkthrough is an illustration of the described mechanism. Exact algorithms for the skew-smoothing mechanisms, the PBFG, and the full evaluation should be read from the paper.

Background

Why storing data on flash keeps coming down to how, and how much, you write

It helps to see Nemo within a broad pattern: flash storage rewards writing in the shape the medium prefers and punishes everything else, so a huge amount of storage-systems work is really about controlling the volume and pattern of writes. Flash cannot be overwritten in place and wears out with use, which means the naive way of updating small pieces of data — scatter little writes wherever they land — is exactly what flash handles worst, both because the device must do heavy internal cleanup and because the software ends up writing far more than the real data. The recurring answer is to batch: accumulate changes and write them in large, sequential, log-structured chunks that the device can absorb cheaply and reclaim in bulk. What makes tiny-object caching a sharp version of this is that the objects are so small that any wasted space in a write dominates, and any per-object bookkeeping dominates memory, so the design must be ruthless about both. Nemo’s twist — welcoming hash collisions to pack its write units full — is a neat inversion that turns the usual enemy of hashing into the tool that keeps its writes dense. This concern for rethinking the caching layer itself to fit the properties of modern fast storage, rather than reusing designs built for slower media, is the same terrain the work on re-architecting I/O caches for emerging fast storage devices covered elsewhere on this site occupies, redesigning the cache around what the hardware now is. Nemo’s contribution is to show that, for tiny-object flash caches, deliberately increasing collisions to fill write units, batching whole groups to and from flash, and indexing with compact bloom filters together deliver low write amplification, low memory, and low miss ratio at the same time.

If you remember only three things

1. Datacenters cache huge volumes of tiny key-value objects (a few hundred bytes) on flash SSDs to get cheap capacity, but flash wears out with writes, so write amplification — writing more than the real data — governs a flash cache's lifetime and cost. There are two sources: device-level write amplification (from the SSD's internal garbage collection) and application-level write amplification (from how the cache software packs and flushes data). Advanced log-structured SSDs (ZNS, FDP) drive the device level near-ideal, but the application level still dominates. Its cause is that set-associative flash caches flush fixed-size sets of objects, and with a large hash space objects scatter thinly, so sets are only about 7 percent full at flush time — the cache writes mostly padding — while tiny objects also strain memory with per-object index entries.
2. Nemo's central, counterintuitive move is to increase hash collisions rather than avoid them: it uses a small hash space (a small in-memory Set-Group of fixed-size sets) so objects pile into the same sets and pack them nearly full before flushing. Because hashed keys are transiently skewed while a Set-Group fills from empty, three smoothing mechanisms even out the fill, raising the average set fill rate from 7 percent to over 89 percent. Full Set-Groups are flushed to a FIFO-managed on-flash pool, and whole Set-Groups are evicted when space runs low, giving the large batched writes and invalidations log-structured flash prefers — an application-level write amplification of about 1.56 (near the optimum of 1) and device-level as low as 1. To keep memory small, Nemo indexes objects approximately with a Parallel Bloom Filter Group, offloads stable metadata to flash while keeping hot metadata in memory, and tracks hotness with one bit per object.
3. The paper reports Nemo simultaneously achieves all three flash-cache goals: low write amplification, high memory efficiency, and low miss ratio. The trade-offs: bloom-filter indexing is approximate (small false-positive rate for large memory savings), the collision strategy depends on the skew-smoothing mechanisms, whole-Set-Group eviction is a coarse granularity (mitigated by one-bit hotness), and the gains are specific to the tiny-object flash-cache regime. The reported figures — 7 to 89 percent fill rate, 1.56 application-level and as-low-as-1 device-level write amplification — depend on the workloads and the SSDs (ZNS, FDP, conventional) evaluated.

Check yourself

Check your understanding

1. Why is write amplification such a problem for flash caches of tiny objects, and what are its two sources?
2. Why is using advanced log-structured SSDs (ZNS, FDP) not enough to solve write amplification?
3. What is Nemo's central, counterintuitive idea for cutting application-level write amplification?
4. How does Nemo keep both device-level write amplification and memory overhead low, and what does it achieve?

Sources

The paper is “Nemo: A Low-Write-Amplification Cache for Tiny Objects on Log-Structured Flash Devices” by Xufeng Yang, Tingting Tan, Jingxin Hu, Congming Gao, Mingyang Liu, Tianyang Jiang, Jian Chen, Linbo Long, Yina Lv, and Jiwu Shu (Xiamen University, Chongqing University of Posts and Telecommunications, and Tsinghua University), published at ASPLOS 2026, DOI 10.1145/3779212.3790191. It is available on arXiv as 2603.09605.

This explainer is written from the paper’s full text (the authors’ arXiv copy). Nemo is a flash-based key-value cache for tiny objects that reduces application-level write amplification by enhancing set-associative cache design to increase hash collision probability, raising the set fill rate. It hashes objects into a small in-memory Set-Group of fixed-size sets and uses three mechanisms to smooth the transient hash skew as a Set-Group fills, raising the average set fill rate from 7.0 percent to over 89 percent; full Set-Groups are flushed to a FIFO-managed on-flash pool and evicted at Set-Group granularity, aligning with log-structured SSDs, for an application-level write amplification of about 1.56 (near optimal) and device-level as low as 1 on ZNS, FDP, and conventional SSDs. For low memory, it approximates object indexing with a Parallel Bloom Filter Group, offloads stable metadata to flash while keeping frequently-updated metadata in memory, and tracks hotness with one bit per object. The paper reports Nemo simultaneously achieves low write amplification, high memory efficiency, and low miss ratio. Numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.