Multi-level comparison of data deduplication in a backup scenario

ABSTRACT

Data deduplication systems detect redundancies between data blocks to either reduce storage needs or to reduce network traffic. A class of deduplication systems splits the data stream into data blocks (chunks) and then finds exact duplicates of these blocks.

This paper compares the influence of different chunking approaches on multiple levels. On a macroscopic level, we compare the chunking approaches based on real-life user data in a weekly full backup scenario, both at a single point in time as well as over several weeks.

In addition, we analyze how small changes affect the deduplication ratio for different file types on a microscopic level for chunking approaches and delta encoding. An intuitive assumption is that small semantic changes on documents cause only small modifications in the binary representation of files, which would imply a high ratio of deduplication. We will show that this assumption is not valid for many important file types and that application-specific chunking can help to further decrease storage capacity demands.

REFERENCES

• 1: H. K. F. Bjerke, D. Shiyachki, A. Unterkircher, and I. Habib. Tools and techniques for managing virtual machine images. In Proceedings of the Workshop on Virtualization in High-Performance Cluster and Grid Computing, August 2008.
• 2: J. Black, Compare-by-hash: a reasoned analysis, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.7-7, May 30-June 03, 2006, Boston, MA
• 3: William J. Bolosky , Scott Corbin , David Goebel , John R. Douceur, Single instance storage in Windows® 2000, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.2-2, August 03-04, 2000, Seattle, Washington
• 4: N. Burch and Y. Kazlov. PIO-HSLF - a guide to the Powerpoint file format. Web, http://poi.apache.org/slideshow/ppt-file-format.html.
• 5: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844155]
• 6: F. Douglis and A. Iyengar. Application-specific deltaencoding via resemblance detection. In Proceedings of the 2003 USENIX Annual Technical Conference, pages 113--126, 2003.
• 7: M. Dutch. Understanding data deduplication ratios. SNIA White Paper, June 2008.
• 8: T. Gibson, E. Miller, and D. Long. Long-term file activity and inter-reference patterns. In Proceedings of the 24th International Conference on Technology Management and Performance Evaluation of Enterprise-Wide Information Systems, 1998.
• 9: Val Henson, An analysis of compare-by-hash, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.3-3, May 18-21, 2003, Lihue, Hawaii
• 10: B. Hong and D. D. E. Long. Duplicate data elimination in a san file system. In Proceedings of the 21st IEEE / 12th NASA Goddard Conference on Mass Storage Systems and Technologies (MSST), pages 301--314, 2004.
• 11: International Standardization Organisation. Iso 32000-1:2008: Portable document format, July 2008.
• 12: Navendu Jain , Mike Dahlin , Renu Tewari, TAPER: tiered approach for eliminating redundancy in replica synchronization, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.21-21, December 13-16, 2005, San Francisco, CA
• 13: Purushottam Kulkarni , Fred Douglis , Jason LaVoie , John M. Tracey, Redundancy elimination within large collections of files, Proceedings of the annual conference on USENIX Annual Technical Conference, p.5-5, June 27-July 02, 2004, Boston, MA
• 14: Chuanyi Liu , Yingping Lu , Chunhui Shi , Guanlin Lu , David H. C. Du , Dong-Sheng Wang, ADMAD: Application-Driven Metadata Aware De-duplication Archival Storage System, Proceedings of the 2008 Fifth IEEE International Workshop on Storage Network Architecture and Parallel I/Os, p.29-35, September 22-22, 2008 [doi>10.1109/SNAPI.2008.11]
• 15: J. P. Macdonald. Abstract file system support for delta compression. Master's thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, 2000.
• 16: Nagapramod Mandagere , Pin Zhou , Mark A Smith , Sandeep Uttamchandani, Demystifying data deduplication, Proceedings of the ACM/IFIP/USENIX Middleware '08 Conference Companion, December 01-05, 2008, Leuven, Belgium [doi>10.1145/1462735.1462739]
• 17: Microsoft Corporation. Knowledge base article 938808. Microsoft Support Knowledge Base, September 2007.
• 18: Microsoft Corporation. Microsoft Office Powerpoint 97--2007 binary file format specification (.ppt). Technical report, Microsoft Corporation, 2007.
• 19: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: Pkware. .zip file format specification. Specification, http://www.pkware.com/documents/casestudies/APPNOTE.TXT, September 2007.
• 21: Calicrates Policroniades , Ian Pratt, Alternatives for detecting redundancy in storage systems data, Proceedings of the annual conference on USENIX Annual Technical Conference, p.6-6, June 27-July 02, 2004, Boston, MA
• 22: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 23: M. O. Rabin. Fingerprinting by random polynomials. Technical report, Center for Research in Computing Technology, 1981.
• 24: Constantine P. Sapuntzakis , Ramesh Chandra , Ben Pfaff , Jim Chow , Monica S. Lam , Mendel Rosenblum, Optimizing the migration of virtual computers, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060324]
• 25: L. L. You and C. Karamanolis. Evaluation of efficient archival storage techniques. In Proceedings of 21st IEEE/NASA Goddard MSS, 2004.
• 26: Lawrence L. You , Kristal T. Pollack , Darrell D. E. Long, Deep Store: An Archival Storage System Architecture, Proceedings of the 21st International Conference on Data Engineering, p.804-8015, April 05-08, 2005 [doi>10.1109/ICDE.2005.47]
• 27: Benjamin Zhu , Kai Li , Hugo Patterson, Avoiding the disk bottleneck in the data domain deduplication file system, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-14, February 26-29, 2008, San Jose, California

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES

Keywords:
backup, compression, deduplication, temporal redundancy