Reducing Fragmentation in Data Deduplication Systems via Partial Repetition and Coding

Yun-Han Li, Jin Sima, Ilan Shomorony, Olgica MilenkovicIEEE Trans. Information Theory 2025 · DOI

Abstract

Data deduplication is a critical technique for modern storage efficiency, yet it inherently introduces data fragmentation and reduces system robustness. This paper, authored by researchers at the University of Illinois Urbana-Champaign, presents the first rigorous theoretical analysis of the trade-off between storage redundancy and fragmentation. By modeling file structures through graph theory and applying linear coding techniques, the authors demonstrate that even minimal coded redundancy can significantly improve read performance and system reliability.

Introduction

Modern storage providers like Dropbox and NetApp rely on data deduplication to eliminate redundant chunks of data, thereby maximizing storage capacity. However, this efficiency comes at a cost. When identical chunks are shared across multiple files, the physical layout of those files becomes fragmented. This fragmentation forces the storage system's read head to jump between distant sectors, severely degrading read performance. Furthermore, deduplication creates single points of failure: if a heavily shared chunk is corrupted, every file referencing it becomes unrecoverable.

While engineers have historically addressed these issues using ad-hoc methods—such as keeping selective duplicates or using specialized caching—there has been a lack of mathematical framework to optimize these trade-offs. This research fills that gap by providing a formal model to determine the exact amount of redundancy required to achieve specific performance targets.

Theoretical Framework and Metrics

The authors utilize a combination of Graph Theory and Coding Theory to model the deduplication landscape. Chunks are represented as nodes in a graph, and a "file" is modeled as a self-avoiding path (a walk that does not revisit nodes) through this graph. To test their theorems, the researchers utilized several synthetic graph-based models:

  • Sparse Hamiltonian Graphs: Simulating files that are largely linear but contain internal jumps (e.g., edited video files).
  • Caterpillar and Hierarchical Trees: Representing complex, hierarchical file systems and data structures.

To quantify performance, the paper introduces two primary metrics:

  1. Stretch Metric: Measures the maximum physical distance between any two chunks that are logically adjacent in a file.
  2. Jump Metric: Measures the total number of times a storage system must "jump" to a new location to complete a file read.

Coded Deduplication and Graph Folding

The core innovation of this work is the shift from simple repetition to Coded Deduplication. Instead of merely deciding whether to store a duplicate chunk, the authors propose using linear codes (such as XORing chunks). This allows a single redundant "parity" chunk to assist in the reconstruction of multiple different files.

To optimize the physical layout of these chunks on a disk, the authors employ a technique called Graph Folding. By minimizing the "thickness" of the graph layout, they can directly reduce the fragmentation metrics associated with the file paths.

Key Insights

The Bandwidth Connection

The researchers discovered that the Stretch Metric is a variation of the Graph Bandwidth Problem. Because finding the optimal bandwidth is a known NP-hard problem, the authors were able to establish that finding the absolute optimal coded chunk store for a general file system is also NP-hard. This allowed them to adapt existing approximation algorithms to the storage domain.

The Power of Minimal Redundancy

A significant finding is the "Power of One." The authors proved that if no extra space is allowed ($m=n$), coding provides no benefit over standard deduplication. However, as soon as even a single extra chunk of redundancy is permitted ($m=n+1$), coded deduplication becomes significantly more effective than simple repetition. Specifically, coded stores can reduce fragmentation by a factor of 2 compared to uncoded methods with the same overhead.

Centrality and Coding Gains

The research highlights that "popular" chunks—those appearing in the highest number of files—are the most effective candidates for coded redundancy. By focusing redundancy on these central nodes, systems can maximize both read speed and robustness. For specific graph structures, the authors demonstrated a coding gain of approximately 1.5x; for example, a coded store achieved a stretch of $(2N+2)/2$ where an uncoded store required $(3N+2)/2$.

Results and Algorithms

Beyond theoretical proofs, the paper contributes practical algorithmic improvements:

  • Jump Metric Approximation: The authors developed a new 4-approximation algorithm with $O(n)$ complexity for calculating the jump number on hierarchical tree structures.
  • The 2x Bound: The paper proves a fundamental limit: for any file model, coded deduplication can, at most, halve the stretch metric compared to an uncoded system with equivalent redundancy.

Limitations and Future Directions

While this work establishes a foundational theory, it focuses primarily on worst-case metrics. In practice, average-case performance is often more relevant to user experience, and the authors identify average-case analysis as a priority for future research. Additionally, the current models assume an "offline" setting where all files are known in advance. Developing an "online" model—where the system must deduplicate and code files as they arrive in real-time—remains an open challenge. Finally, the authors suggest that exploring "high-redundancy" regimes (10-20% extra data) may reveal even more substantial benefits for coded deduplication.

Summary updated

BibTeX
@article{li2025reducing,
  author = {Yun-Han Li and Jin Sima and Ilan Shomorony and Olgica Milenkovic},
  title = {{Reducing Fragmentation in Data Deduplication Systems via Partial Repetition and Coding}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2025.3613455},
}

Loading related content...

Figure