The Design of a High-Performance Fine-Grained Deduplication Framework for Backup Storage

Xiangyu Zou, Wen Xia, Philip Shilane, Haijun Zhang, Xuan Wang

Abstract

Fine-grained deduplication (also known as delta compression) can achieve a better deduplication ratio compared to chunk-level deduplication. This technique removes not only identical chunks but also reduces redundancies between similar but non-identical chunks. Nevertheless, it introduces considerable I/O overhead in deduplication and restore processes, hindering the performance of these two processes and rendering fine-grained deduplication less popular than chunk-level deduplication to date. In this paper, we explore various issues that lead to additional I/O overhead and tackle them using several techniques. Moreover, we introduce MeGA, which attains fine-grained deduplication/restore speed nearly equivalent to chunk-level deduplication while maintaining the significant deduplication ratio benefit of fine-grained deduplication. Specifically, MeGA employs (1) a backup-workflow-oriented delta selector and cache-centric resemblance detection to mitigate poor spatial/temporal locality in the deduplication process, and (2) a delta-friendly data layout and “Always-Forward-Reference” traversal to address poor spatial/temporal locality in the restore workflow. Evaluations on four datasets show that MeGA achieves a better performance than other fine-grained deduplication approaches. Specifically, MeGA significantly outperforms the traditional greedy approach, providing 10–46 times better backup speed and 30–105 times more efficient restore speed, all while preserving a high deduplication ratio.
BibTeX
@article{zou2025design,
  author = {Xiangyu Zou and Wen Xia and Philip Shilane and Haijun Zhang and Xuan Wang},
  title = {{The Design of a High-Performance Fine-Grained Deduplication Framework for Backup Storage}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2025},
  url = {https://openreview.net/forum?id=q7BMGrLjFl},
}

Loading related content...

Figure