RevDedup: a reverse deduplication storage system optimized for reads to latest backups

Chun-Ho Ng, Patrick P. C. Lee

TL;DR

RevDedup is a deduplication system designed specifically for Virtual Machine (VM) backups that prioritizes the read performance of the most recent data. By "reversing" the deduplication process—removing duplicates from old backups rather than new ones—it ensures the latest backup remains sequential on disk, enabling restore speeds of up to 1.7 GB/s while maintaining 97% storage savings.

What Problem Does This Paper Address?

In modern data centers, backing up thousands of VM images is a massive storage challenge. While deduplication (removing redundant data blocks) effectively shrinks the storage footprint, it introduces a "fragmentation tax."

In conventional deduplication, when a new backup is saved, the system checks if its blocks already exist in older backups. If they do, the new backup simply stores a pointer to the old block. Over time, the latest backup—the one most likely to be needed for a fast disaster recovery—becomes a "patchwork" of pointers scattered across months of physical disk locations. This leads to excessive disk seeks, crippling read performance exactly when you need it most. RevDedup aims to provide the storage efficiency of deduplication without sacrificing the restore speed of the latest backup.

Methods

The authors introduce a two-tier hybrid approach:

  1. Coarse-Grained Global Deduplication (Inline): To handle similarities across different VMs (e.g., multiple users running the same OS), the system deduplicates large "segments" (several MBs) as data is written. This minimizes disk seeks by keeping large chunks of data together.
  2. Fine-Grained Reverse Deduplication (Out-of-Order): This is the core innovation. When a new version of a VM arrives, the system compares it to the previous version at a 4KB block level. If a block is identical, RevDedup removes the block from the old version and replaces it with a pointer to the new version.
  3. Threshold-Based Space Reclamation: To reclaim the space from deleted blocks in old versions, the system chooses between two methods:
  4. Hole-punching: Using Linux's fallocate to tell the file system a block is empty (fast, but causes disk fragmentation).
  5. Segment Compaction: Rewriting the segment to remove gaps (slower, but keeps the disk clean). The system uses a "rebuild threshold" to decide which method is more efficient based on how much data is being removed.

Datasets

The authors evaluated RevDedup using three primary sources:

  • Microbenchmarks: 128GB of unique data to establish baseline performance.
  • Real-World Student VMs: A 12-week dataset of weekly snapshots from 160 university students (14.3TB total raw data). This captures realistic user behavior and OS updates.
  • Long-Chained VM: 96 daily versions of a Fedora VM running automated yum update tasks to test how the system handles long version histories.

Key Insights and Ideas

  • The "Hot Data" Priority: The authors realized that in backup systems, the value of data is inversely proportional to its age. By shifting the fragmentation "tax" to older, "cold" backups, they optimize for the 99% use case: restoring the most recent state.
  • Reference Counting is Essential: Because segments can be shared across different VMs (global dedup) and different versions (reverse dedup), the system uses reference counts to ensure a block is only deleted when no version—old or new—needs it anymore.
  • Amortizing Seeks: By using large segments for global deduplication, they ensure that even if a restore has to jump between different physical locations, it does so infrequently, keeping throughput high.

Key Results

  • Storage Efficiency: RevDedup achieved a 97% reduction in storage for the real-world VM dataset, which is comparable to state-of-the-art commercial systems.
  • Restore Speed: The read throughput for the latest backup reached 1.2–1.7 GB/s, nearly matching raw disk performance.
  • Comparison to Conventional Dedup: While conventional deduplication saw read speeds drop significantly as more versions were added (due to fragmentation), RevDedup’s read performance remained high and stable for the latest version.
  • Backup Throughput: Despite the overhead of reverse deduplication, the system maintained backup speeds of 4–7 GB/s by offloading fingerprinting tasks to the clients.

Limitations and Future Work

  • Comparison Scope: Currently, RevDedup only compares the new version with the immediately preceding version. While their tests showed this only missed about 0.6% of potential duplicates, a more exhaustive search could improve efficiency at the cost of complexity.
  • Garbage Collection: The paper assumes data is never deleted. Implementing a system to safely remove old versions while maintaining the integrity of the pointer chains is noted as future work.
  • Memory Scaling: The memory required for the block-level index grows with the size of the VM image. While manageable for current VMs (approx. 121MB for a 7.6GB VM), very large multi-terabyte images might require more advanced indexing structures like Bloom filters.

Summary updated

BibTeX
@inproceedings{ng2013revdedup,
  author = {Chun-Ho Ng and Patrick P. C. Lee},
  title = {{RevDedup: a reverse deduplication storage system optimized for reads to latest backups}},
  booktitle = {Apsys},
  year = {2013},
  doi = {10.1145/2500727.2500731},
}

Loading related content...

Figure