Pastiche: making backup cheap and easy

ABSTRACT

Backup is cumbersome and expensive. Individual users almost never back up their data, and backup is a significant cost in large organizations. This paper presents Pastiche, a simple and inexpensive backup system. Pastiche exploits excess disk capacity to perform peer-to-peer backup with no administrative costs. Each node minimizes storage overhead by selecting peers that share a significant amount of data. It is easy for common installations to find suitable peers, and peers with high overlap can be identified with only hundreds of bytes. Pastiche provides mechanisms for confidentiality, integrity, and detection of failed or malicious peers. A Pastiche prototype suffers only 7.4% overhead for a modified Andrew Benchmark, and restore performance is comparable to cross-machine copy.

REFERENCES

• 1: Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002 [doi>10.1145/567112.567116]
• 2: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 3: C. Batten, K. Barr, A. Saraf, and S. Trepetin. pStore: A secure peer-to-peer backup system. Unpublished report, MIT Laboratory for Computer Science, December 2001.
• 4: Matt Blaze , John Ioannidis , Angelos D. Keromytis, Offline Micropayments without Trusted Hardware, Proceedings of the 5th International Conference on Financial Cryptography, p.21-40, February 19-22, 2002
• 5: W. J. Bolosky, S. Corbin, D. Goebel, and J. R. Douceur. Single instance storage in Windows 2000. In Proceedings of the 4th USENIX Windows Systems Symposium, pages 13--24, Seattle, WA, August 2000.
• 6: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 7: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 8: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 9: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, 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.1060317]
• 10: M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Submitted for publication.
• 11: Fay W. Chang , Minwen Ji , Shun-Tak A. Leung , John MacCormick , Sharon E. Perl , Li Zhang, Myriad: Cost-Effective Disaster Tolerance, Proceedings of the Conference on File and Storage Technologies, p.103-116, January 28-30, 2002
• 12: D. Chaum. Blind signatures for untraceable payments. In Advances in Cryptology: Proceedings of Crypto '82, pages 199--203, August 1982.
• 13: A. L. Chervenak, V. Vellanki, and Z. Kurmas. Protecting file systems: A survey of backup techniques. In Proceedings of the Joint NASA and IEEE Mass Storage Conference, March 1998.
• 14: Ian Clarke , Scott G. Miller , Theodore W. Hong , Oskar Sandberg , Brandon Wiley, Protecting Free Expression Online with Freenet, IEEE Internet Computing, v.6 n.1, p.40-49, January 2002 [doi>10.1109/4236.978368]
• 15: Connected Corporation. The 60% you're missing: Preventing data loss through PC management. White paper, Farmingham, MA, 2002.
• 16: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 17: J. Daemen and V. Rijmen. AES proposal: Rijndael. Advanced Encryption Standard Submission, 2nd version, March 1999.
• 18: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 19: John R. Douceur , William J. Bolosky, A large-scale study of file-system contents, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.59-70, May 01-04, 1999, Atlanta, Georgia, United States
• 20: John R. Douceur , William J. Bolosky, Progress-based regulation of low-importance processes, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.247-260, December 12-15, 1999, Charleston, South Carolina, United States
• 21: S. Elnikety, M. Lillibridge, M. Burrows, and W. Zwaenepoel. Cooperative backup system. In The USENIX Conference on File and Storage Technologies, Monterey, CA, January 2002. Work-in-progress report.
• 22: D. Hitz, J. Lau, and M. A. Malcom. File system design for an NFS file server appliance. In Proceedings USENIX Winter Technical Conference, pages 235--246, San Francisco, CA, January 1994.
• 23: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 24: A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the Network and Distributed System Security Symposium, pages 151--165, San Diego, CA, February 1999.
• 25: M. Frans Kaashoek , Dawson R. Engler , Gregory R. Ganger , Hector M. Briceño , Russell Hunt , David Mazières , Thomas Pinckney , Robert Grimm , John Jannotti , Kenneth Mackenzie, Application performance and flexibility on exokernel systems, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.52-65, October 05-08, 1997, Saint Malo, France
• 26: S. R. Kleiman. Vnodes: An architecture for multiple file system types in Sun UNIX. In USENIX Association Summer Conference Proceedings, pages 238--247, Atlanta, GA, June 1986.
• 27: U. Manber. Finding similar files in a large file system. In Proceedings of the USENIX Winter 1994 Conference, pages 1--10, San Francisco, CA, January 1994.
• 28: Eric Melski, Burt: The Backup and Recovery Tool, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 29: Microsoft Corporation. SimPastry. http://www.research.microsoft.com/~ antr/Pastry/ download.htm.
• 30: 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
• 31: National Institute of Standards and Technology. Computer data authentication. FIPS Publication #113, May 1985.
• 32: National Institute of Standards and Technology. Secure hash standard. FIPS Publication #180-1, April 1997.
• 33: Network Appliance. NetApp unveils first nearstore release. Computer Reseller News, page 33, March 25, 2002.
• 34: R. Hugo Patterson , Stephen Manley , Mike Federwisch , Dave Hitz , Steven Kleiman , Shane Owara, SnapMirror: File-System-Based Asynchronous Mirroring for Disaster Recovery, Proceedings of the Conference on File and Storage Technologies, p.117-129, January 28-30, 2002
• 35: W. W. Peterson and E. J. Weldon. Error-correcting Codes. The MIT Press, 1972.
• 36: W. Curtis Preston, Using Gigabit Ethernet to Backup Six Terabytes, Proceedings of the 12th Conference on Systems Administration, p.87-96, December 06-11, 1998
• 37: Sean Quinlan, A cached WORM file system, Software—Practice & Experience, v.21 n.12, p.1289-1299, Dec. 1991 [doi>10.1002/spe.4380211203]
• 38: 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
• 39: M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 40: Sean Rhea , Chris Wells , Patrick Eaton , Dennis Geels , Ben Zhao , Hakim Weatherspoon , John Kubiatowicz, Maintenance-Free Global Data Storage, IEEE Internet Computing, v.5 n.5, p.40-49, September 2001 [doi>10.1109/4236.957894]
• 41: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 42: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 43: Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
• 44: M. Satyanarayanan. RPC2 User Guide and Reference Manual. School of Computer Science, Carnegie Mellon University, October 1991.
• 45: Mirjana Spasojevic , M. Satyanarayanan, An empirical study of a wide-area distributed file system, ACM Transactions on Computer Systems (TOCS), v.14 n.2, p.200-222, May 1996 [doi>10.1145/227695.227698]
• 46: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 47: J. D. Strunk, G. R. Goodson, M. L. Scheinholtz, C. A. N. Soules, and G. R. Ganger. Self-securing storage: Protecting data in compromised systems. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, pages 165--179, San Diego, CA, October 2000.
• 48: A. Tridgell. Efficient algorithms for sorting and synchronization. PhD thesis, The Austrailian National University, 1999.
• 49: J. D. Tygar, Atomicity versus Anonymity: Distributed Transactions for Electronic Commerce, Proceedings of the 24rd International Conference on Very Large Data Bases, p.1-12, August 24-27, 1998
• 50: Werner Vogels, File system usage in Windows NT 4.0, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.93-109, December 12-15, 1999, Charleston, South Carolina, United States
• 51: A. Westerlund and J. Danielsson. Arla--afree afs client. In Proceedings of 1998 USENIX, Freenix track, New Orleans, LA, June 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Backup procedures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
      D.4.8 Performance
          Subjects: Operational analysis

General Terms:
Performance, Reliability, Security