Eliminating Storage Management Overhead of Deduplication over SSD Arrays Through a Hardware/Software Co-Design

Yuhong Wen, Xiaogang Zhao, You Zhou, Tong Zhang, Shangjun Yang, Changsheng Xie and 1 other

Deduplication saves space and extends SSD life by storing each unique block once, but the bookkeeping it needs — a giant table mapping every logical address to where its one copy lives — is so large and so constantly rewritten that it can multiply the actual disk traffic more than eightyfold and freeze the system during cleanup; this paper from Huazhong University notices that the SSD already keeps an almost identical table inside itself, and re-architects both the software and the SSD firmware so that one shared table does the job, offloading the bookkeeping into an array of enhanced SSDs and raising throughput by up to 272 percent.

The argument in one glance

Problem

Deduplication saves space, but its bookkeeping wrecks performance

Storing each unique block only once cuts storage cost and, on an SSD, extends its life by avoiding redundant writes. But to do it, the system must remember, for every logical address a user can write, where the single shared copy of its data actually lives — a mapping table proportional to capacity that sits on the path of every read and write and must be persisted constantly for crash safety. That table, its reference counts, and the garbage collector that reclaims freed space together burn gigabytes of memory, multiply disk traffic more than eightyfold, and periodically freeze the system during cleanup.
What people did

Accelerate the pieces, or push dedup entirely inside the SSD

One line of work speeds up the compute — hashing and indexing — with FPGAs or faster metadata memory. Another moves deduplication entirely into the SSD firmware, so the drive itself detects and collapses duplicates, folding the two mapping layers into the one the drive already keeps.
Why it fell short

The compute was never the real problem, and one drive sees too little

Accelerating hashing leaves the storage-management overhead — the mapping table and garbage collection — completely untouched, and that is what actually amplifies I/O and stalls the system. Pushing dedup inside a single SSD fixes the redundant mapping but only within that one drive: in an array, most duplicate blocks live on different drives (over 70 percent in an eight-SSD array), so a drive that can only look at itself misses most of the savings, and it lacks the compute to run a full dedup engine anyway.
This paper's idea

Share one mapping table, and make it span the whole array

The host-side deduplication table and the SSD internal table both translate addresses — they are redundant. ARM-Dedup collapses them into a single table managed by the SSDs, but enhances the SSD firmware so that table is array-aware: a duplicate can be remapped to the copy on any drive, near or far. The heavy hashing stays on the host where the compute is; only the bookkeeping moves into the drives, and a versioning trick lets its cleanup run in the background without ever freezing the system.

Why this problem is worth solving

The feature at issue is one storage systems genuinely want, which is why its cost is worth attacking rather than avoiding.

Deduplication is the technique of storing identical blocks of data only once: the system hashes each incoming block into a short fingerprint, keeps an index of fingerprints it has seen, and when a new block’s fingerprint matches an existing one, it stores no new copy and instead points the new logical address at the existing data. On an SSD array this is doubly attractive — it cuts storage cost like on any medium, but it also extends the flash’s limited write endurance and speeds up writes by avoiding redundant programming of the memory. The catch is that pointing many addresses at one copy requires a translation table from every user-visible logical address to the actual storage location, plus reference counts to know when a copy is no longer needed, plus a garbage collector to reclaim it. That storage-management machinery, not the hashing, is where deduplication’s practical pain lives.

The insight that unlocks the paper is that the drive underneath is already doing almost the same job.

A flash translation layer, or FTL, is the firmware inside every SSD that hides flash memory’s quirks behind an ordinary block interface. Because flash cannot be overwritten in place, the FTL writes updates to fresh locations and maintains its own mapping table, from the logical addresses the host uses to the physical flash pages where data currently sits, moving data and rewriting the map during its own garbage collection, all protected against power loss. So an SSD array running host-side deduplication has two mapping layers stacked on top of each other: the dedup engine maps user addresses to storage addresses, and the FTL maps those storage addresses to physical pages. Both are address-translation tables with reference counting and garbage collection; the redundancy between them is exactly the slack this paper reclaims by making one table, inside the drives, do both jobs.

What people did before, and where it broke

Accelerate the deduplication compute with special hardware. Offload hashing, chunking, and index lookups to an FPGA, GPU, or data-processing unit, or pipeline them across CPU cores. Where it broke. This targets the computation, but the storage-management overhead — the mapping table, its persistence, and garbage collection — is untouched, and that is what actually amplifies I/O and stalls the system.
Keep the deduplication metadata in faster memory. Put the mapping table and index in non-volatile memory so accessing it is quicker. Where it broke. Faster metadata storage does not shrink the metadata or stop it from being rewritten, so the I/O amplification and memory footprint remain, on top of the availability and cost problems of the special memory.
Shrink the fingerprint index in software. Use bloom filters, compact prefix indexes, or selective deduplication to reduce the memory the fingerprint index needs. Where it broke. These optimize the fingerprint index, a different structure; they leave the address-mapping table and its garbage collection — the dominant cost this paper measures — as an open problem.
Move deduplication entirely inside one SSD. Integrate the dedup engine into the FTL so the drive detects duplicates and collapses the two mapping layers into the one it already keeps, as in CAFTL and Remap-SSD. Where it broke. A single drive can only deduplicate against its own contents, but in an array most duplicate blocks live on other drives — over 70 percent in an eight-SSD array — so device-wide deduplication forfeits most of the opportunity, and a small SSD controller lacks the compute and memory to run a full dedup engine.
The gap. No approach both removed the storage-management overhead and preserved array-wide deduplication. Doing the first meant pushing everything into a drive that then could not see the array; doing the second meant keeping the heavy table on the host. What was missing was a way to offload only the bookkeeping into the drives while keeping the array-wide view — and the compute — where they belonged.

How ARM-Dedup is put together

A write's path through ARM-Dedup, with bookkeeping offloaded to the array

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

The idea

Two stacked tables are translating the same addresses, so let one table do both jobs. The waste at the heart of host-side deduplication on SSDs is structural: the dedup engine keeps a table mapping each user address to a storage address, and directly beneath it the SSD’s own firmware keeps a table mapping that storage address to a physical flash page. Both are address-translation tables, both do out-of-place updates, both reference-count and garbage-collect — and the lower one already comes with power-loss protection the upper one has to reinvent. ARM-Dedup collapses the two into a single layer that the SSDs manage, unifying the address spaces so the drive’s map translates the user’s address straight to a physical page. The single most expensive piece of host metadata — the mapping table that dominated both memory footprint and I/O amplification — simply ceases to exist on the host, cutting its metadata I/O by well over half. Recognizing that two layers of the stack are independently maintaining what is essentially one structure, and dissolving the redundancy by letting the layer already equipped for the job own it, is the same move the paging-replacement work covered elsewhere on this site makes when it removes a whole redundant address-translation mechanism by having the layers of the system cooperate instead of each translating on its own.

Push the bookkeeping down to the device, but keep the thinking up on the host. The obvious way to merge the tables is to move deduplication wholesale into the SSD, and prior work did exactly that — but a drive can only see its own data, and in an array the duplicates are mostly somewhere else, so device-only deduplication throws away most of the benefit. ARM-Dedup splits the labor along the seam that actually matters: the compute-heavy, array-wide part — hashing blocks and deciding what is a duplicate of what across the whole array — stays on the host, which has the CPU and the global view, while only the storage management is offloaded into the drives, through a new array-aware remap primitive the enhanced firmware exposes. Crucially that primitive is cross-device: a duplicate can be remapped to a copy sitting on a different drive, so the array-wide opportunity is preserved even though the mapping now lives in the hardware. The measured dedup ratio rises from the 12 percent a device-only design manages to the 45 percent the array-wide view captures. Dividing a job at the boundary where each side has the advantage — heavy computation and global knowledge on the host, mechanical data management near the storage — is the same co-design discipline the near-data-processing work covered elsewhere on this site follows, placing each part of the work where the hardware is actually suited to it rather than forcing everything to one side.

Tag metadata with versions so its cleanup can wait instead of freezing the system. Decoupling the mapping table from the dedup engine creates a subtle hazard: when a user overwrites an address in place, the old fingerprint pointing at it becomes stale, and a later write of that old data could be wrongly deduplicated to a location that no longer holds it. The heavy-handed fix would be to eagerly hunt down and delete stale fingerprints — but that scan blocks user I/O and is exactly the kind of periodic freeze the paper is trying to eliminate. Instead ARM-Dedup stamps every fingerprint and every address with a version number: when a lookup finds a fingerprint whose version no longer matches the address’s current version, it simply knows the entry is stale and declines to deduplicate, no correctness harm done. Because a stale fingerprint can now be tolerated rather than urgently purged, the cleanup that removes it is demoted to a background task that runs when the system is idle, so garbage collection never again makes the array unresponsive. Turning a piece of consistency work from something that must happen synchronously into something that can be validated lazily and swept up later, off the critical path, is the same manoeuvre the crash-consistency logging work covered elsewhere on this site relies on, moving the expensive guarantee out of the moment of the write and deferring it without ever risking correctness.

Following a few operations through ARM-Dedup

A unique write, a cross-drive duplicate, a stale fingerprint, and a read

A trace through the key mechanisms: how a duplicate becomes a remap, how versioning catches a stale fingerprint, and how a remapped read is served.

Step 1 of 5

Write unique data A to address 0

The block is new, so the host writes it to a local drive and inserts a fingerprint-index entry recording that data A lives at address 0, stamped with that address's current version, say version 1. No separate mapping table or reference count is kept on the host.

The address is unified across the layers: the value the host records is the same logical address the drive's firmware maps to a physical flash page, so there is only one translation, not two.

Why it works

Collapsing the redundant table removes the dominant overhead. The host-side mapping table was proportional to capacity, on every I/O’s critical path, and constantly persisted → so folding it into the SSDs’ existing map deletes the biggest source of both memory use and metadata traffic → cutting host metadata I/O volume by about 59 percent and shrinking the host metadata footprint from 1.7GB to roughly 0.97GB.
Keeping compute on the host lets the drives do only what they are good at. SSD controllers are too weak to hash and index at speed → so leaving that on the capable host and offloading only the mechanical mapping means neither side is overburdened → which is why the drives can manage the tables while the host still deduplicates across the whole array at a 45 percent ratio rather than a device-only 12 percent.
A cross-device remap captures the duplicates that actually exist. In an array most identical blocks sit on different drives → so a remap that can point an address at a copy on any drive reaches those cross-drive duplicates → giving a dedup ratio that holds up as the array grows, exactly where a device-only design collapses.
Versioning turns a blocking cleanup into a background one. Stale fingerprints after in-place overwrites would normally force a synchronous scan that freezes user I/O → but stamping fingerprints and addresses with versions lets a stale entry be detected on lookup and tolerated → so its removal defers to idle time and the periodic unresponsiveness disappears, while write amplification drops from 24.6 to 6.3.
A bounded remote map makes array-wide mapping fit inside a drive. A full table of every other drive’s addresses would not fit in an SSD’s small memory → so treating that space as a fixed-size, direct-mapped cache keeps the remote map tiny enough to hold on-device → making array-wide offloading feasible, at the accepted cost of occasional collisions that forgo a little deduplication.

What it costs (trade-offs and scope)

The SSDs are emulated, not real. The array-aware FTL is prototyped on the FEMU flash emulator, not fabricated silicon, so the results demonstrate the design’s logic rather than measured behavior on production drives, and the firmware changes would need real vendor adoption.
It is not faster on every workload. On the highest-duplicate real trace (Mail-3, about 88.5 percent duplicates), ARM-Dedup is 4 to 12 percent slower on throughput than the host-side baseline, because each duplicate now triggers a remap and a trim rather than a metadata update that mostly hits cache — it still cuts write amplification there, so it wins on flash lifetime, not speed. The headline 272 percent is a best case, a random read-only workload dominated by mapping-table cache misses; gains fall to roughly 22 to 44 percent on sequential and high-locality workloads.
It gives up some deduplication to gain performance. Two effects cost dedup ratio — stale fingerprints that decline to match, and collisions in the direct-mapped remote table — losing up to about 9 percent of the achievable savings at a small remote-table size; the table size is a tuning knob trading memory overhead against dedup ratio.
Parity protection costs extra space. Cross-device remapping can place two blocks of one RAID stripe on the same drive, so the design extends parity to the remote space with additional stripes, adding up to about 10 percent parity overhead for a five-drive array — a real space cost that partly offsets the dedup savings, and worse when the dedup ratio is low.
It requires new SSD hardware. ARM-Dedup depends on drives with an array-aware FTL exposing remap and remote-read primitives, cross-device mapping, and array-wide reverse-mapping logs — none of which commodity SSDs provide, so it is a co-design proposal, not something deployable on existing arrays.
Cross-device reads add coordination and remote latency. Data that was remapped to another drive is fetched by a remote-read redirected through the array manager, so those reads are no longer purely local; the design keeps the coordination structures small, but the cost is real for remap-heavy workloads.
The prototype is small and the rival is self-built. The arrays evaluated are 64GB to 512GB, bounded by the emulator’s use of host memory, not datacenter scale; and the intra-SSD baseline it beats is the authors’ own variant of ARM-Dedup with the remote table switched off, rather than an independent system.
Recovery is more intricate. Because a block can live on a remote drive and remote addresses are direct-mapped with possible collisions, rebuilding after a drive failure involves reconstructing both local and remote stripes and resolving which address a recovered remote page belongs to — workable, but more complex than a conventional array’s recovery.

The evaluation

Three places to put deduplication's bookkeeping

Property	Host-side dedup (Dmdedup)	Intra-SSD dedup (one drive)
Where storage management lives
Deduplication scope
Host metadata cost
Write amplification and responsiveness		Better, limited by scope
Throughput	The baseline

Comparison on a FEMU-emulated SSD array (64GB to 512GB, RAID-0 and RAID-5) under synthetic and real-world traces. DedupSSD is ARM-Dedup with its remote mapping table disabled. Percentages are versus the host-side Dmdedup baseline.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

ARM-Dedup’s core result is real and well-motivated: the host-side mapping table is genuinely the dominant cost — driving metadata I/O amplification up past eighty times and freezing the system during garbage collection — and folding it into the SSDs’ existing map, while keeping deduplication array-wide through a cross-device remap, removes that cost and typically doubles throughput. But read the numbers with care. The drives are emulated on FEMU, not real silicon, so this is a co-design proposal that needs vendor adoption, not a measurement of shipping hardware. It is not uniformly faster: on the highest-duplicate workload it is a few percent slower on throughput (winning only on flash lifetime), and the 272 percent peak is a cache-miss-dominated best case, with typical high-locality gains nearer 22 to 44 percent. It trades away some deduplication — up to about 9 percent — through stale-fingerprint mismatches and collisions in the deliberately-bounded remote table, whose size is a tuning knob; RAID parity over the remote space adds up to roughly 10 percent extra overhead; cross-device reads carry remote-fetch latency; and the arrays tested are small, with the intra-SSD baseline being the authors’ own disabled variant. The versioning mechanism that lets cleanup run in the background is the quiet enabler that keeps the whole thing from trading one stall for another.

Background

The rich hidden layer inside every SSD

It is worth appreciating why offloading work into an SSD is even possible, because it reveals something about modern storage. An SSD presents itself as a simple array of numbered blocks you can read and write, but behind that plain interface sits a small computer running the flash translation layer — remapping addresses, wearing the flash evenly, collecting garbage, correcting errors, and protecting itself against sudden power loss — because raw flash is far too unruly to expose directly. That hidden sophistication is usually invisible, and a great deal of it duplicates functions the layers above also perform, which is exactly the redundancy this paper exploits. A recurring theme in storage research is to stop treating the drive as an opaque block box and instead renegotiate the boundary — exposing a richer interface so the host and the firmware can cooperate rather than each solving the same problem blindly. The same spirit animates the work covered elsewhere on this site that reaches deep into 3D NAND flash to tame the physics of reading charge levels: both recognize that the interesting engineering, and the wasted effort, are increasingly inside a device the block interface pretends is simple. The broader lesson is that as devices grow their own intelligence, the highest-leverage systems work often lies in redrawing the line between what the host does and what the device does.

If you remember only three things

1. Deduplication over an SSD array is dragged down not by its hashing but by its bookkeeping: a mapping table from every logical address to the single stored copy of its data, proportional to capacity, on every I/O's critical path, constantly persisted, and cleaned by a garbage collector that blocks user requests — together consuming gigabytes of memory, amplifying disk traffic more than eightyfold, and periodically freezing the system.
2. The key observation is that this table is redundant with the mapping the SSD's own firmware already keeps, so ARM-Dedup collapses the two into one table managed by the drives, but enhances the firmware to make it array-aware: a duplicate is turned into a cross-device remap that can point at a copy on any drive, the compute-heavy hashing stays on the host where the CPU and the array-wide view are, and a versioning scheme lets the cleanup of stale fingerprints run lazily in the background instead of stalling I/O.
3. On an emulated array this removes the host mapping table (cutting metadata I/O about 59 percent), preserves array-wide deduplication (45 percent ratio versus 12 percent for a single-drive design), drops write amplification from 24.6 to 6.3, and raises throughput by up to 272 percent — though it needs new SSD hardware, is a few percent slower on the most redundant workloads, forgoes up to about 9 percent of deduplication through collisions and stale entries, and adds parity overhead, all evaluated in emulation rather than on real drives.

Check yourself

Check your understanding

1. What is the real source of deduplication's overhead on an SSD array, according to the paper?
2. What redundancy does ARM-Dedup exploit, and how?
3. Why does ARM-Dedup keep the deduplication compute on the host instead of moving everything into the SSD?
4. Which limitation most affects how ARM-Dedup's results should be read?

Sources

The paper is “Eliminating Storage Management Overhead of Deduplication over SSD Arrays Through a Hardware/Software Co-Design” by Yuhong Wen, Xiaogang Zhao, You Zhou, Tong Zhang, Shangjun Yang, Changsheng Xie, and Fei Wu, published at ASPLOS 2024, pages 320-335, DOI 10.1145/3620665.3640368. The authors are at Huazhong University of Science and Technology.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the introduction and background on block-layer deduplication, its fingerprint index and Dedup-MapTable and reference counting, and the redundant dual mapping between the host dedup engine and the SSD flash translation layer, including the Remap-SSD design; the motivation section quantifying metadata I/O amplification (up to 83.6 times) and garbage-collection overhead and system unresponsiveness in Dmdedup and VDO; the design section detailing ARM-Dedup’s three components — the array-wide ReMap-SSDs with their local and direct-mapped remote mapping tables, the array manager with its target-SSD table, and the lightweight dedup engine with its version-based fingerprint verification and merged TgtSSD-DataVer-Table — plus the RAID parity extension over local and remote stripes, the consistency and recovery mechanisms, and the discussion of deduplication loss; and the evaluation section reporting the FEMU-based prototype (with its line counts), the RAID-0 and RAID-5 comparisons against Dmdedup and the device-only DedupSSD variant, the 71-to-272 percent IOPS improvements and write-amplification reductions, the dedup-ratio analysis across remote-table sizes and array widths, the parity-overhead measurements, and the CPU-overhead breakdown.