Building a High-performance Fine-grained Deduplication Framework for Backup Storage with High Deduplication Ratio

Xiangyu Zou, Wen Xia, Philip Shilane, Haijun Zhang, Xuan WangUSENIX ATC 2022 · OpenReview

TL;DR

This paper introduces MeGA, a novel fine-grained deduplication framework for backup storage that significantly boosts backup and restore speeds while maintaining high deduplication ratios. By addressing the inherent locality issues of fine-grained deduplication with innovative data layout and traversal techniques, MeGA offers a compelling solution for efficient and performant data backup.

What Problem Does This Paper Address?

Traditional chunk-level deduplication is effective at reducing storage costs but struggles to fully exploit data compressibility. Fine-grained deduplication (also known as delta compression) goes a step further by identifying and eliminating redundancies not just between identical chunks, but also between similar, non-identical chunks. This leads to much higher deduplication ratios, saving even more space. However, this enhanced compression comes at a steep price: significantly degraded backup and restore performance. The core problem is that fine-grained deduplication exacerbates data locality issues. When similar chunks are shared, it breaks the spatial and temporal locality of data, leading to increased I/O overheads and slower operations. This paper aims to bridge this gap by developing a fine-grained deduplication system that achieves performance comparable to chunk-level methods while retaining the superior deduplication capabilities.

Methods

MeGA tackles the performance bottleneck of fine-grained deduplication through three key techniques:

  • Backup-Workflow-Oriented Delta Selector: This technique addresses the "Reading Base Issue" during backups. It observes that base chunks (used for delta encoding) are often clustered in a small number of containers. The delta selector intelligently skips delta compression for chunks whose base counterparts reside in these "base-sparse containers," thereby avoiding costly I/O operations to read these inefficient containers.
  • Delta-Friendly Data Layout: To combat the "Fragmentation Issue" and improve spatial locality during restores, MeGA introduces a new data layout. This layout considers both the traditional chunk-workload relationships and the new delta-base relationships introduced by fine-grained deduplication. By organizing data based on chunk lifecycles across backups, it ensures that related chunks are stored together, minimizing fragmentation.
  • "Always-Forward-Reference" Traversing and Delta Prewriting: These techniques address the "Repeatedly Accessing Issue" during restores. "Always-Forward-Reference" traversing ensures that delta chunks are always accessed before their corresponding base chunks. Delta prewriting leverages this by writing delta chunks to their final destination in user space before their base chunks are read. This allows for efficient decoding when the base chunk is eventually accessed, significantly reducing I/O overhead and improving restore speed.

Datasets

The authors evaluated MeGA using four real-world backup datasets:

  • WEB: Backups of a news website (news.sina.com).
  • CHM: Source code of the Chromium project.
  • SYN: Synthetic backups generated by simulating file operations.
  • VMS: Backups of an Ubuntu 12.04 virtual machine.

These datasets are standard in deduplication research and represent diverse workload characteristics.

Key Insights and Ideas

  • Locality is the Achilles' Heel: The paper powerfully demonstrates that while fine-grained deduplication offers superior compression, its benefits are severely hampered by the resulting poor data locality. This is a fundamental trade-off that needs careful management.
  • Backup vs. Restore Workflow Optimization: MeGA's success stems from tailoring optimizations to the specific needs of both backup and restore workflows. The delta selector focuses on backup efficiency, while the data layout and traversal methods are geared towards fast restores.
  • Smart Skipping is Key: The delta selector's ability to intelligently skip delta compression for certain chunks is crucial. It's not about compressing everything, but about compressing smartly to achieve the best overall performance.
  • Data Layout Matters for Restore: The delta-friendly data layout is a significant contribution, directly addressing the fragmentation problem that plagues fine-grained deduplication during restores.
  • Exploiting Asymmetry: Delta prewriting cleverly uses the performance differences between storage media (e.g., faster SSDs for user space, slower HDDs for backup space) to optimize restore operations.

Key Results

MeGA demonstrates impressive performance improvements:

  • Backup Speed: Achieves a 4.47–34.45× higher backup performance compared to the traditional greedy approach.
  • Restore Speed: Achieves a 30–105× higher restore performance compared to the greedy approach.
  • Deduplication Ratio: Maintains a very high deduplication ratio, comparable to other fine-grained methods and significantly better than chunk-level approaches (1.18–8.73× higher).
  • I/O Reduction: Significantly reduces I/O overheads in both backup and restore workflows, particularly by addressing the fragmentation and repeated access issues.

Limitations and Future Work

  • Dataset Specificity: While MeGA performs well across various datasets, its advantage is smaller on SYN and VMS datasets. This is attributed to the random nature of SYN's modifications and the limited similarity between chunks in VMS, which reduces the effectiveness of the delta selector.
  • Incremental Backups: The paper outlines a plan to support incremental backups by generating "virtual" full backups, but this is presented as future work.
  • Delta Prewriting Overhead: Delta prewriting introduces some additional I/O overhead on user space (5-10%), which could potentially be mitigated by a delta cache.
  • Memory Overhead: While MeGA manages memory efficiently by only keeping indexes for the last two backups, further reductions could be explored with stream-informed indexes.

The authors suggest future work could explore optimizing delta prewriting with a delta cache and further investigating incremental backup support.

Summary updated

BibTeX
@inproceedings{zou2022building,
  author = {Xiangyu Zou and Wen Xia and Philip Shilane and Haijun Zhang and Xuan Wang},
  title = {{Building a High-performance Fine-grained Deduplication Framework for Backup Storage with High Deduplication Ratio}},
  booktitle = {USENIX ATC},
  year = {2022},
  url = {https://openreview.net/forum?id=edSN1zLKHz},
}
Figure