RevDedup: A Reverse Deduplication Storage System Optimized for Reads to Latest Backups

Chun-Ho Ng, Patrick P. C. Lee

Abstract

Scaling up backup storage for an ever-increasing volume of virtual machine (VM) images is a critical issue in virtualization environments. While deduplication effectively eliminates duplicates, it introduces fragmentation that degrades read performance. We propose RevDedup, a deduplication system that optimizes reads to the latest VM image backups using "reverse deduplication." Unlike conventional deduplication that removes duplicates from new data, RevDedup removes duplicates from old data, shifting fragmentation to older versions while keeping the layout of new data sequential. Our evaluation shows that RevDedup achieves approximately 97% storage savings and read throughput on the order of 1GB/s.

Introduction: The Fragmentation Problem

In modern data centers, backing up massive volumes of VM images is a significant challenge. Deduplication is the standard solution for eliminating redundant data blocks across different backups. However, traditional "forward" deduplication has a major performance flaw: fragmentation.

In a standard deduplication system, new data is checked against existing storage. If a match is found, the new backup simply points to the old blocks. Over time, the latest backup—the one most likely to be needed for disaster recovery—becomes a "patchwork quilt" of references scattered across the disk. This results in excessive disk seeks, crippling read throughput. RevDedup addresses this by prioritizing the "hottest" data: the most recent backup.

The RevDedup Approach

RevDedup flips the traditional deduplication logic. Instead of making new data point to old data, it ensures that the latest backup is written sequentially to the disk. It then identifies redundant blocks in the previous version and replaces them with pointers to the new version. This process, called reverse deduplication, effectively shifts the "fragmentation tax" from the latest, most critical backup to older, less frequently accessed versions.

Two-Tier Deduplication Strategy

To achieve both high throughput and high storage efficiency, RevDedup employs a two-tier strategy:

  1. Coarse-Grained Global Deduplication (Inline): The system uses large segments (several MBs) to handle redundancy across different VMs. This minimizes the global index size and ensures that deduplicated data is still read in large, efficient chunks.
  2. Fine-Grained Reverse Deduplication (Out-of-Order): This core innovation compares a new VM version to its immediate predecessor. When a new version is backed up, it is written sequentially. The system then removes shared blocks from the old version, replacing them with "indirect references."

Key Results and Performance

RevDedup was evaluated using real-world VM traces consisting of 12 weekly snapshots from 160 users (14.3TB raw data). The results demonstrate that the system successfully balances storage efficiency with high-speed access:

  • Storage Efficiency: RevDedup achieved a deduplication ratio of approximately 97%, matching the efficiency of state-of-the-art commercial systems.
  • Read Performance: The latest backups were restored at 1.2–1.7 GB/s, nearly the raw speed of the underlying RAID array. In contrast, traditional deduplication read speeds plummeted to ~266 MB/s for newer versions due to fragmentation.
  • Backup Throughput: By offloading fingerprint calculations to the client side, the system maintained a backup throughput of 4–7 GB/s, significantly exceeding raw disk write speeds by discarding redundant data before it reached the server.

Conclusion

RevDedup demonstrates that fragmentation is not an unavoidable consequence of deduplication that must affect all data equally. By applying the "latest is hot" heuristic, RevDedup ensures that disaster recovery—the primary purpose of backups—can occur at near-raw disk speeds. While it introduces fragmentation into older backups, this is a strategic trade-off that optimizes for the most common and critical use case in virtualization environments.

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},
}
Figure