The Fragmentation Penalty in Deduplicated Storage Systems

28 concepts13 papers

Storage systems are locked in a fundamental tug-of-war between space efficiency and read performance. To minimize costs, modern storage architectures rely heavily on data deduplication—a technique that identifies identical blocks of data across files and stores only a single physical copy, replacing duplicates with pointers.

While deduplication achieves massive storage savings, it introduces a severe performance tax: physical data fragmentation. When multiple files or backups share the same physical block, that block can only be stored contiguously with one of them. For every other file referencing it, the natural sequential layout of the data is broken. Consequently, reading a file sequentially requires jumping across disparate physical locations, turning high-throughput sequential access into slow, fragmented random I/O.

The Mechanics of the Fragmentation Tax

To understand why deduplication degrades read performance, consider how data is reconstructed. In an ideal storage layout, a file's blocks reside side-by-side on the physical medium. A single, continuous read operation can stream the entire file into memory.

Deduplication shatters this continuity. As Ng et al. observe in their work on virtual machine storage, shared blocks become scattered across the disk over time. When a system attempts to boot a virtual machine or read an image layer, it must perform a series of non-contiguous data retrievals.

This problem scales with the aggressiveness of the deduplication strategy:

  • The Granularity Trade-Off: To maximize storage savings, systems often employ fine-grained deduplication, breaking data into smaller chunks. However, Ng demonstrates that smaller block sizes inherently multiply the number of pointers required. This exacerbates fragmentation, forcing the system to execute a massive number of disk seeks to reconstruct a single file.
  • Locality Disruption: Fine-grained deduplication breaks both spatial and temporal locality. As Zou et al. explain, when systems introduce delta-base relationships to share similar but non-identical chunks, related data that belongs together logically becomes physically isolated.

This fragmentation penalty is not confined to traditional backup systems. In decentralized, content-addressed architectures like IPFS, storing data blocks based strictly on their cryptographic hashes naturally scatters related blocks across the disk, increasing I/O overhead and lowering publication throughput (Shi et al.). Similarly, using linked structures to enable incremental updates in full-text search engines introduces a query performance penalty because retrieving a complete record requires traversing a chain of non-contiguous blocks (Brown et al.).

The Modern Hardware Bottleneck

A common historical assumption was that solid-state drives (SSDs) and flash storage would render fragmentation irrelevant due to their lack of moving mechanical parts. However, research shows that fragmentation merely shifts its tax from mechanical heads to the software and hardware translation layers.

On mobile flash storage, fragmented files cause highly dispersed I/O patterns. Ji et al. discovered that this dispersion places immense pressure on the mapping cache within the Flash Translation Layer (FTL). Instead of a clean address translation, the FTL is forced to perform frequent translation page reads and writes, severely increasing I/O latency. Furthermore, Hahn et al. demonstrate that a significant portion of this performance degradation stems from overhead within the software I/O stack itself, which must manage a bloated volume of non-contiguous block requests.

Even in ultra-fast mediums like Persistent Memory (PM) or learned secondary indexes, fragmentation degrades performance by destroying cache locality. When logically sequential keys or file mappings point to physically distant memory locations, the CPU suffers from frequent cache misses and must perform expensive multi-level tree traversals to resolve addresses (Kipf et al.; Neal et al.).

Architectural Solutions: Restoring Locality

To bridge the gap between storage density and read performance, researchers have developed architectures that intelligently manage or shift the fragmentation penalty.

Reverse Deduplication

In backup systems, the most critical performance metric is often the restore speed of the latest backup. Traditional inline deduplication deduplicates new backups against old ones, meaning the newest backup is stored as a fragmented collection of pointers pointing back in time.

To fix this, Ng introduced Reverse Deduplication (RevDedup). The intuition is simple: keep the latest backup perfectly sequential on disk. When a new backup arrives, the system detects duplicates, but instead of fragmenting the new data, it replaces the duplicate blocks in the old backup with pointers to the new one.

Traditional Deduplication (New points to Old):
Old Backup:  [A][B][C][D] (Sequential)
New Backup:  [A']->(Old A) [E] [C']->(Old C) [F] (Fragmented)

Reverse Deduplication (Old points to New):
Old Backup:  [A']->(New A) [B] [C']->(New C) [D] (Fragmented)
New Backup:  [A][E][C][F] (Sequential)

By shifting the fragmentation penalty to older, rarely accessed historical backups, the system guarantees high-speed restores for the most recent data. Li et al. expanded this concept into a hybrid framework, using coarse-grained inline deduplication to maintain ingestion speed, followed by fine-grained out-of-line reverse deduplication to optimize long-term layout.

Selective Rewriting and Defragmentation

Another approach is to accept a minor compromise in storage efficiency to achieve major gains in read throughput. Instead of deduplicating every single redundant block, systems can use "near-exact" or selective rewriting schemes.

For instance, Lai et al. developed a defragmentation scheme that identifies highly fragmented data streams during backup and intentionally rewrites duplicate chunks contiguously if they break a threshold of sequentiality. This slightly reduces the deduplication ratio but prevents the catastrophic WAN and disk bottlenecks that occur when retrieving scattered segments during a cloud restore. Similarly, frameworks like MeGA use optimized data layouts and traversal techniques to balance chunk compression with spatial locality, ensuring that backup and restore operations remain fast even under fine-grained deduplication (Zou et al.).

Key Foundational Work

Live Deduplication Storage of Virtual Machine Images in an Open-Source Cloud (2011) — contributed 3 concept elements to this direction.
Fast Incremental Indexing for Full-Text Information Retrieval (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_deduplication_induced_fragmentation_4265f14d,
  title = {deduplication-induced fragmentation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deduplication-induced-fragmentation/rdr_4265f14d0c5b47eeac2a6f73b9beb656},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_deduplication_induced_fragmentation_4265f14d_v1,
  title = {deduplication-induced fragmentation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deduplication-induced-fragmentation/rdr_4265f14d0c5b47eeac2a6f73b9beb656/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake