Ivy: a read/write peer-to-peer file system

ABSTRACT

Ivy is a multi-user read/write peer-to-peer file system. Ivy has no centralized or dedicated components, and it provides useful integrity properties without requiring users to fully trust either the underlying peer-to-peer storage system or the other users of the file system.An Ivy file system consists solely of a set of logs, one log per participant. Ivy stores its logs in the DHash distributed hash table. Each participant finds data by consuiting all logs, but performs modifications by appending only to its own log. This arrangement allows Ivy to maintain meta-data consistency without locking. Ivy users can choose which other logs to trust, an appropriate arrangement in a semi-open peer-to-peer system.Ivy presents applications with a conventional file system interface. When the underlying network is fully connected, Ivy provides NFS-like semantics, such as close-to-open consistency. Ivy detects conflicting modifications made during a partition, and provides relevant version information to application-specific conflict resolvers. Performance measurements on a wide-area network show that Ivy is two to three times slower than NFS.

REFERENCES

• 1: Planet Lab. http://www.planet-lab.org/.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: T. E. Anderson , M. D. Dahlin , J. M. Neefe , D. A. Patterson , D. S. Roselli , R. Y. Wang, Serverless network file systems, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.109-126, December 03-06, 1995, Copper Mountain, Colorado, United States
• 4: B. Berliner. CVS II: Parallelizing software development. In Proc. Winter 1990 USENIX Technical Conference, 1990.
• 5: 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
• 6: B. Callaghan, B. Pawlowski, and P. Staubach. NFS version 3 protocol specification. RFC 1813, Network Working Group, June 1995.
• 7: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 8: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 9: 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
• 10: FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/N.I.S.T., National Technical Information Service, April 1995.
• 11: K. Fu, M. Frans Kaashoek, and D. Mazières. Fast and secure distributed read-only file system. In Proc. of the USENIX Symposium on Operating Systems Design and Implementation, pages 181--196, October 2000.
• 12: John H. Hartman , John K. Ousterhout, The Zebra striped network file system, ACM Transactions on Computer Systems (TOCS), v.13 n.3, p.274-310, Aug. 1995 [doi>10.1145/210126.210131]
• 13: 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]
• 14: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.213-225, October 13-16, 1991, Pacific Grove, California, United States
• 15: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 16: Puneet Kumar , M. Satyanarayanan, Log-Based Directory Resolution in the Coda File System, Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, p.202-213, January 20-23, 1993
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.226-238, October 13-16, 1991, Pacific Grove, California, United States
• 19: Nancy A. Lynch , Dahlia Malkhi , David Ratajczak, Atomic Data Access in Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.295-305, March 07-08, 2002
• 20: U. Maheshwari, R. Vingralek, and W. Shapiro. How to build a trusted database system on untrusted storage. In Proc. of the USENIX Symposium on Operating Systems Design and Implementation, pages 135--150, October 2000.
• 21: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 22: David Mazières, A Toolkit for User-Level File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.261-274, June 25-30, 2001
• 23: David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
• 24: David Mazières , Dennis Shasha, Building secure file systems out of byzantine storage, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571840]
• 25: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 26: T. Page, R. Guy, G. Popek, and J. Heidemann. Architecture of the Ficus scalable replicated file system. Technical Report UCLA-CSD 910005, 1991.
• 27: D. Parker, G. Popek, G. Rudisin, A. Stoughton, B. Walker, E. Walton, J. Chow, D. Edwards, S. Kiser, and C. Kline. Detection of mutual inconsistency in distributed systems. In IEEE Transactions on Software Engineering, volume 9(3), pages 240--247, 1983.
• 28: 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
• 29: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 30: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 31: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• 32: 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
• 33: R. Sandberg, D. Goldberg, D. Kleiman, D. Walsh, and B. Lyon. Design and implementation of the Sun network file system. In Proc. Usenix Summer Conference, pages 119--130, June 1985.
• 34: 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
• 35: Mike J. Spreitzer , Marvin M. Theimer , Karin Petersen , Alan J. Demers , Douglas B. Terry, Dealing with server corruption in weakly consistent, replicated data systems, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.234-240, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262151]
• 36: Christopher A. Stein , John H. Howard , Margo I. Seltzer, Unifying File System Protection, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.79-90, June 25-30, 2001
• 37: 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
• 38: J. Strunk, G. Goodson, M. Scheinholtz, and C. Soules. Self-securing storage: Protecting data in compromised systems. In Proc. of the USENIX Symposium on Operating Systems Design and Implementation, pages 165--179, October 2000.
• 39: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 40: Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France
• 41: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Operational analysis

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

General Terms:
Design, Management, Performance