  Backup storage systems often remove redundancy across backups via inline
deduplication, which works by referring duplicate chunks of the latest backup
to those of existing backups. However, inline deduplication degrades restore
performance of the latest backup due to fragmentation, and complicates deletion
of ex- pired backups due to the sharing of data chunks. While out-of-line
deduplication addresses the problems by forward-pointing existing duplicate
chunks to those of the latest backup, it introduces additional I/Os of writing
and removing duplicate chunks. We design and implement RevDedup, an efficient
hybrid inline and out-of-line deduplication system for backup storage. It
applies coarse-grained inline deduplication to remove duplicates of the latest
backup, and then fine-grained out-of-line reverse deduplication to remove
duplicates from older backups. Our reverse deduplication design limits the I/O
overhead and prepares for efficient deletion of expired backups. Through
extensive testbed experiments using synthetic and real-world datasets, we show
that RevDedup can bring high performance to the backup, restore, and deletion
operations, while maintaining high storage efficiency comparable to
conventional inline deduplication.
