The effectiveness of deduplication on virtual machine disk images

ABSTRACT

Virtualization is becoming widely deployed in servers to efficiently provide many logically separate execution environments while reducing the need for physical servers. While this approach saves physical CPU resources, it still consumes large amounts of storage because each virtual machine (VM) instance requires its own multi-gigabyte disk image. Moreover, existing systems do not support ad hoc block sharing between disk images, instead relying on techniques such as overlays to build multiple VMs from a single "base" image.

Instead, we propose the use of deduplication to both reduce the total storage required for VM disk images and increase the ability of VMs to share disk blocks. To test the effectiveness of deduplication, we conducted extensive evaluations on different sets of virtual machine disk images with different chunking strategies. Our experiments found that the amount of stored data grows very slowly after the first few virtual disk images if only the locale or software configuration is changed, with the rate of compression suffering when different versions of an operating system or different operating systems are included. We also show that fixed-length chunks work well, achieving nearly the same compression rate as variable-length chunks. Finally, we show that simply identifying zero-filled blocks, even in ready-to-use virtual machine disk images available online, can provide significant savings in storage.

REFERENCES

• 1: Siddhartha Annapureddy , Michael J. Freedman , David Mazières, Shark: scaling file servers via cooperative caching, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.129-142, May 02-04, 2005
• 2: Anonymous. Secure hash standard. FIPS 180--1, National Institute of Standards and Technology, Apr. 1995.
• 3: http://bagside.com/bagvapp/.
• 4: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 5: Fabrice Bellard, QEMU, a fast and portable dynamic translator, Proceedings of the annual conference on USENIX Annual Technical Conference, p.41-41, April 10-15, 2005, Anaheim, CA
• 6: Deepavali Bhagwat , Kave Eshghi , Pankaj Mehra, Content-based document routing and index partitioning for scalable similarity-based searches in a large corpus, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281207]
• 7: Collin, L. A quick benchmark: Gzip vs. Bzip2 vs. LZMA, 2005.
• 8: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, 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.1060316]
• 9: Daum, M., and Lucks, S. Hash Collisions (The Poisoned Message Attack) "The Story of Alice and her Boss". Presentation at Rump Sessions of Eurocrypt 2005 5 (2005).
• 10: Deutsch, P. Deflate compressed data format specification version 1.3.
• 11: John R. Douceur , Atul Adya , William J. Bolosky , Dan Simon , Marvin Theimer, Reclaiming Space from Duplicate Files in a Serverless Distributed File System, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.617, July 02-05, 2002
• 12: Gupta, D., Lee, S., Vrable, M., Savage, S., Snoeren, A. C., Varghese, G., Voelker, G. M., and Vahdat, A. Difference Engine: Harnessing memory redundancy in virtual machines. In Proceedings of the 8th Symposium on Operating Systems Design and Implementation (OSDI) (Dec. 2008), pp. 309--322.
• 13: 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
• 14: Jeffrey K. Hollingsworth , Ethan L. Miller, Using content-derived names for configuration management, Proceedings of the 1997 symposium on Software reusability, p.104-109, May 17-20, 1997, Boston, Massachusetts, United States
• 15: Kingsley G. Morse, Jr., Compression tools compared, Linux Journal, v.2005 n.137, p.3, September 2005
• 16: Liguori, A., and Van Hensbergen, E. Experiences with content addressable storage and virtual disks. In Proceedings of the First Workshop on I/O Virtualization (Dec. 2008).
• 17: 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
• 18: Partho Nath , Michael A. Kozuch , David R. O'Hallaron , Jan Harkes , M. Satyanarayanan , Niraj Tolia , Matt Toups, Design tradeoffs in applying content addressable storage to enterprise-scale systems based on virtual machines, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.6-6, May 30-June 03, 2006, Boston, MA
• 19: 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
• 20: 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
• 21: Rabin, M. O. Fingerprinting by random polynomials. Tech. Rep. TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 22: Mark W. Storer , Kevin Greenan , Darrell D.E. Long , Ethan L. Miller, Secure data deduplication, Proceedings of the 4th ACM international workshop on Storage security and survivability, October 31-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1456469.1456471]
• 23: http://www.thoughtpolice.co.uk/vmware/.
• 24: http://www.vmware.com/appliances/.
• 25: VMware Inc. Virtual disk format. VMware web site, http://www.vmware.com/interfaces/vmdk.html, 11 2007.
• 26: Wang, X., Yin, Y. L., and Yu, H. Finding collisions in the full SHA-1. Lecture Notes in Computer Science 3621 (2005), 17--36.
• 27: Lawrence L. You , Darrell D. Long, Efficient archival data storage, University of California at Santa Cruz, Santa Cruz, CA, 2006
• 28: 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]
• 29: 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
• 30: Ziv, J., and Lempel, A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23, 3 (May 1977), 337--343.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Measurement, Performance