Source-linked AI summary
RevDedup: A Reverse Deduplication Storage System Optimized for Reads to Latest Backups
Chun-Ho Ng, Patrick P. C. Lee
TL;DR
VM-image backup storage must scale, while deduplication can fragment data and degrade reads. RevDedup shifts duplicate removal to older backups to keep newer layouts more sequential. On a 12-week dataset from 160 users, its prototype reported around 97% storage saving alongside high backup and latest-backup read throughput.
Problem
VM-image deduplication saves storage but can fragment data and degrade reads, while storing many large VM images and versions remains a scaling challenge.
Source: §1 · p. 1Method
RevDedup combines global deduplication across VMs with reverse deduplication that removes duplicates from older versions and refers them to newer data.
Source: §1 · p. 2Results
Around 97% storage saving, 4–7GB/s write throughput, and 1.2–1.7GB/s latest-backup read throughput were reported on a 12-week dataset from 160 users.
Source: §1 · p. 2Takeaways & Limitations
RevDedup shifts fragmentation toward older backups while keeping newer layouts as sequential as possible, and reports small metadata overhead in backup and read operations.
Source: §1 · p. 2RevDedup assumes stored data will never be deleted; garbage collection for deleted versions is future work.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Scaling up the backup storage for an ever-increasing volume of virtual machine (VM) images is a critical issue in virtualization environments. While deduplication is known to effectively eliminate duplicates for VM image storage, it also introduces fragmentation that will degrade read performance. We propose RevDedup, a deduplication system that optimizes reads to latest VM image backups using an idea called reverse deduplication. In contrast with conventional deduplication that removes duplicates from new data, RevDedup removes duplicates from old data, thereby shifting fragmentation to old data while keeping the layout of new data as sequential as possible. We evaluate our RevDedup prototype using microbenchmark and real-world workloads. For a 12-week span of real-world VM images from 160 users, RevDedup achieves high deduplication efficiency with around 97% of saving, and high backup and read throughput on the order of 1GB/s. RevDedup also incurs small metadata overhead in backup/read operations.
1 Introduction
RevDedup addresses the storage and read-performance challenges of VM-image backups by shifting deduplication from new data to old data. Its design aims to preserve efficient storage and backup performance while keeping recent backups more sequential for reading.
1 Introduction
- Scaling storage for VM images remains a deployment issue because many VMs may each have large images and multiple retained versions.VM backups preserve user data and operating-system updates for disaster recovery and recovery checkpoints.Source: §1 · p. 1
- Deduplication saves space by storing one copy of identical blocks, but references to blocks elsewhere fragment files and degrade read performance.Additional disk seeks make reads nonsequential, while fast restores can reduce disaster-recovery downtime.Source: §1 · pp. 1–2
- Reverse deduplication checks whether already-stored blocks can be represented by new blocks, shifting fragmentation to older backups and preserving newer layouts as sequential as possible.This targets recent backups, which users are more likely to access.Source: §1 · p. 2
- RevDedup combines coarse-grained inline global deduplication across VMs with fine-grained out-of-order reverse deduplication across versions of each VM.A configurable threshold-based mechanism uses hole-punching and segment compaction to remove old duplicates and reclaim contiguous space.Source: §1 · p. 2
- Around 97% storage saving, 4–7GB/s write throughput, and 1.2–1.7GB/s latest-backup read throughput were reported on a 12-week dataset from 160 users.The prototype also incurred small metadata overhead in backup and read operations.Source: §1 · p. 2
2 Background and Motivation
Deduplication reduces redundant backup storage, but conventional deduplication can scatter blocks of a recent snapshot and hurt reads. RevDedup’s design prioritizes newer backups, while related systems address read performance or storage efficiency differently.
2 Background and Motivation
- Deduplication identifies identical blocks using fingerprints and stores one copy, reducing redundant storage in VM images with content similarities.The section introduces Figure 1 as an example of how conventional deduplication and RevDedup place data on disk.Source: §2 · p. 2, Figure 1 · p. 3
2.1 Fragmentation
- Conventional deduplication can scatter the latest VM image across earlier backups; RevDedup instead keeps newer backups less fragmented than older ones.The paper estimates that 60 seeks per second can reduce read throughput by at least 50% versus sequential reads on a 7200 RPM SATA disk.Source: §2.1 · p. 3
2.2 Related Work
- Related systems target indexing, selective rewriting, on-demand deduplication, or restore performance; RevDedup removes duplicates from old data and implements a prototype for actual I/O evaluation.The related-work discussion distinguishes global deduplication across multiple VMs from approaches limited to one backup’s versions, primary-storage workloads, or whole-file deduplication.Source: §2.2 · pp. 3–4
3 RevDedup
RevDedup stores and restores snapshots of multiple VMs through a client-server system. Its design combines deduplication approaches to target storage efficiency, limited indexing memory, backup throughput, and latest-version restore performance.
3 RevDedup
- Multiple clients snapshot VM disk images, compute fingerprints, and upload snapshots and fingerprints to a server that stores images and deduplication metadata.Both client and server processes run in user space on Linux, with the backend mounted on a Linux native file system.Source: §3 · pp. 4–5
- A backup is one snapshot of a VM disk image, and multiple snapshots from the same VM are called versions.The system stores and retrieves versions belonging to different VMs.Source: §3 · p. 4
- The system’s goals are high storage efficiency, limited indexing memory, high backup throughput, and near-raw-disk throughput when restoring latest VM versions.These are design goals, not quantified results in this section.Source: §3 · pp. 4–5
- RevDedup combines coarse-grained global deduplication with fine-grained reverse deduplication to reduce fragmentation in latest-version reads while retaining storage efficiency.It also offloads part of the deduplication workload to clients and supports concurrent submissions.Source: §3 · p. 5
- The design assumes fixed-size chunks, each identified by a fingerprint, for determining whether data can be deduplicated.The passage cites VM-image storage savings and lower chunking overhead than variable-size chunking as reasons for the assumption.Source: §3 · p. 5
- RevDedup assumes stored data will never be deleted; garbage collection for deleted versions is future work.Source: §3 · p. 5
3.1 Coarse-Grained Global Deduplication
RevDedup uses large segments for global deduplication to amortize seek costs and keep its index small. On the real-world dataset, large-segment deduplication still achieved substantial space savings, though not the same efficiency as fine-grained approaches.
3.1 Coarse-Grained Global Deduplication
- Global deduplication compares large fixed-size segments across versions and VMs, eliminating duplicates within a version, across versions of one VM, or across different VMs.A segment is identified by a fingerprint generated from a cryptographic hash of its contents.Source: §3.1 · p. 5
- The authors use large-size global deduplication segments because they expect sequential writes, so seek time is only a small part of reading all VM-image segment contents; nevertheless, this cannot maintain fine-grained deduplication efficiency.Source: §3.1 · pp. 5–6
- At least 80% space saving was achieved with large-size segments in evaluations on the real-world dataset.The paper suggests clustered VM-image changes leave a substantial portion of segments unchanged.Source: §3.1 · p. 5
3.1.1 Indexing
- An 8MB segment size requires 128 million index entries per petabyte; at 32 bytes per entry, the index is 4GB.The example estimates that such an index can fit in commodity-hardware memory.Source: §3.1.1 · p. 6
3.2 Fine-Grained Reverse Deduplication
RevDedup adds block-level deduplication to segment-level deduplication and removes duplicate blocks from older VM versions, leaving newer versions with direct references while older versions may link forward.
3.2 Fine-Grained Reverse Deduplication
- RevDedup applies fine-grained block deduplication within a VM’s versions, removing duplicate blocks from older versions and redirecting them to matching blocks in newer versions.This shifts fragmentation toward older versions while preserving direct references in the latest version.Source: §3.2 · p. 6, §3.2.2 · p. 7
3.2.1 Indexing
- For each version, RevDedup loads segment metadata to build a temporary in-memory block index; memory use grows proportionally with VM image size.For a 7.6GB image with 4KB blocks and 32-byte index entries, the cited estimate is up to 121.6MB.Source: §3.2.1 · p. 6
3.2.2 Reverse Deduplication on Unique Segments
- When writing a new version, RevDedup compares it with the immediately previous version and redirects duplicate blocks in that older version to the new one.Comparing only the most recent version can miss earlier duplicates; the real-world analysis reports 0.6% additional space usage from such misses.Source: §3.2.2 · pp. 7–8
3.2.3 Reverse Deduplication on Shared Segments
- For shared segments, reference counts track direct block references across versions, allowing blocks with a count of zero to be safely removed.The server increments counts for shared segments and decrements them when older blocks are redirected to newer ones.Source: §3.2.3 · p. 8
3.2.4 Removal of Duplicate Blocks
- A rebuild threshold selects block punching for a small removed fraction and segment compaction otherwise, trading disk fragmentation against copying overhead.Punching can fragment free disk space; compaction copies retained blocks sequentially but incurs I/O to copy them.Source: §3.2.4 · pp. 8–9
3.3 Implementation
RevDedup divides VM snapshots into segments, computes fingerprints on clients, and has the server perform reverse deduplication and store the resulting data and metadata.
3.3 Implementation
- Clients divide snapshots into segments, compute segment- and block-level fingerprints, query the server, and upload unique segments with image metadata.Client-side fingerprinting avoids overloading the server when many clients connect.Source: §3.3 · pp. 9–10
- The server writes received data, links versions to stored segments, and performs reverse deduplication by updating references and removing duplicate blocks.Removal uses block punching or segment compaction.Source: §3.3 · p. 10
- The prototype is implemented in C, uses SHA-1 fingerprints, and requires a filesystem that supports hole-punching; the experiments use Ext4.Source: §3.3 · p. 10
- The server skips disk writes for null blocks and generates their contents when read; it also uses multithreading and read predeclaration to improve read performance.For old versions, separate threads trace indirect references and read block contents concurrently.Source: §3.3 · pp. 10–11
3.4 Discussion
RevDedup contrasts conventional inline deduplication with its approach, which removes duplicates from older versions to favor reads of newer data.
3.4 Discussion
- Conventional inline deduplication removes duplicates from new data and generally achieves higher backup throughput than RevDedup through finer-grained client-side elimination.Source: §3.4 · p. 11
- Conventional deduplication can see decaying read performance for newer data because of fragmentation, whereas RevDedup targets reads to latest backups.Source: §3.4 · p. 11
- RevDedup can still achieve high backup throughput when coarse-grained global deduplication lets clients discard enough duplicate segments.Source: §3.4 · p. 11
4 Evaluation
The evaluation uses testbed experiments with unique data and VM workloads, including real-world traces and a long version chain. The reported results include high deduplication efficiency and throughput, alongside small metadata and reference-tracing overheads.
4 Evaluation
- RevDedup maintains high baseline throughput on unique data.Source: §4 · p. 11
- Real-world VM traces show high deduplication efficiency, high backup throughput given system resources, and high read throughput for restoring latest VM versions.Source: §4 · p. 11
- A long-version-chain backup shows small metadata and old-version reference-tracing overheads, with block punching and compaction configurable during backup.Source: §4 · p. 11
- Experiments use a RAID-0 array and precomputed fingerprints, so the reported throughput focuses on read/write performance without fingerprint calculation.The eight client processes and server run on one machine over loopback to eliminate the network bottleneck.Source: §4 · pp. 11–12
4.1 Evaluation with Unique Data
Unique-data tests compare RevDedup with native filesystem throughput. RevDedup reads near raw speed, while its write throughput is 13–19% below raw write throughput.
4.1 Evaluation with Unique Data
- The baseline submits 128GB of globally unique data to an initially empty server, then retrieves it with wget.Raw disk throughput is measured by reading and writing through the testbed's native filesystem.Source: §4.1 · p. 12
- 13–19% below raw write throughput, RevDedup's unique-data write performance is reduced mainly by fingerprint and reference-count metadata.Larger segments involve fewer segments and yield higher unique write throughput.Source: §4.1 · p. 12, Table 1 · p. 12
- RevDedup's read throughput is very close to raw read throughput for unique data.The test retrieves 128GB of unique data and compares RevDedup with native filesystem throughput.Source: §4.1 · p. 12, Table 1 · p. 12
4.2 Evaluation with Real-World VM Usage
The evaluation follows 12 weekly snapshots from 160 student VMs and measures storage efficiency and backup/read throughput. Reverse deduplication raises storage savings, while read performance is strongest for latest backups.
4.2.1 Dataset
- The dataset covers 160 student VMs over 12 weeks; most weekly changes are under 100MB, with a Week 4 spike and a 6GB Week 12 outlier.The un-deduplicated versions total 14.3TB, or 6.67TB excluding null blocks.Source: §4.2.1 · p. 12, Figure 5 · p. 13
4.2.2 Storage Efficiency
- 96.8–97.3%: adding reverse deduplication raises storage savings beyond the 80.5–93.6% achieved with coarse-grained global deduplication alone.The deduplication ratio is space saved relative to total VM-image size excluding null blocks.Source: Figure 6 · p. 13, §4.2.2 · p. 13
- Week 12 uses more additional space than Week 11 despite similar change distributions because of outliers; space rises only marginally as segments grow from 4MB to 32MB.The Week 12 outlier generates 6GB of new data.Source: §4.2.1 · p. 12, §4.2.2 · p. 13
4.2.3 Throughput
- For conventional deduplication, earlier-version reads fall from 606MB/s in Week 1 to 266MB/s in Week 12; RevDedup's Week 1 read throughput is up to 40% below Week 12.The authors attribute the conventional decline to fragmentation becoming more severe for newer versions.Source: Figure 7 · p. 14, §4.2.3 · p. 15
- 4–7GB/s: RevDedup's backup throughput; conventional deduplication averages 30% higher than RevDedup with 4MB segments.RevDedup's backup throughput is around 3–5× raw write throughput, with client-side duplicate discards accounting for the difference.Source: Figure 7 · p. 14, §4.2.3 · p. 14
- 1.2–1.7GB/s: RevDedup's overall read throughput for latest versions; later weeks see a small decline as segment-level fragmentation increases.Larger segments give higher read throughput by better amortizing fragmentation.Source: Figure 7 · p. 14, §4.2.3 · p. 15
4.2.2 Storage Efficiency
- RevDedup configurations have storage efficiency similar to conventional deduplication using 32KB–128KB data units.The authors describe the efficiency as comparable to some state-of-the-art deduplication file systems.Source: §4.2.2 · p. 14
4.2.3 Throughput
- The conventional baseline uses 128KB global-deduplication segments with reverse deduplication disabled, retaining other implementation features for a fair comparison.The 128KB setting has comparable deduplication efficiency to RevDedup and is a default in some state-of-the-art systems.Source: §4.2.3 · p. 14
4.3 Evaluation with a Long-Chained VM
The long-chain evaluation measures backup, block-removal, and read-tracing overhead as VM backup versions accumulate.
4.3.1 Dataset
- The test uses 96 daily versions of a 5GB Fedora 14 VM, with 50–100MB of changes per day.The VM ran daily system updates and background maintenance jobs, but generated no user data.Source: §4.3.1 · p. 15
4.3.3 Block Removal Overhead
- Below an 80% rebuild threshold, block removal takes at most 0.26s; its time first decreases, then increases as the threshold rises.More frequent block punching reduces segment-compaction I/O, but raises file-system metadata overhead; Figure 9(a) shows block-removal time.Source: §4.3.3 · p. 16, Figure 9 · p. 17
- At thresholds of 40% or higher, free extents indicate significant disk fragmentation; with block punching only, small free extents exceed stored-data size.Figure 9(b) plots cumulative free-extent percentages; extents smaller than the 32MB segment size count as small.Source: §4.3.3 · p. 16, Figure 9 · p. 17
4.3.4 Read Overhead
- Indirect-reference tracing accounts for at most 15% of the time to read a 5GB version after all 96 versions are submitted.Figure 10 reports total read time and tracing time per version, with 32MB segments.Source: §4.3.4 · pp. 16–17, Figure 10 · p. 17
5 Conclusions
RevDedup targets storage efficiency, low memory use, and backup and latest-backup restore performance through reverse deduplication. The authors report evaluating the prototype against these goals.
5 Conclusions
- RevDedup removes duplicates from old backups to mitigate fragmentation in the latest backup.The system is designed for VM disk-image backup in virtualization environments.Source: §5 · p. 17
- The design targets high storage efficiency, low memory usage, and high backup and latest-backup restore performance.The authors say their prototype was extensively evaluated using different workloads to validate these goals.Source: §5 · p. 17
- The RevDedup prototype source code is available for download.The paper provides a download address.Source: §5 · p. 17