Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility

Abstract

This paper presents and evaluates the storage management and caching in PAST, a large-scale peer-to-peer persistent storage utility. PAST is based on a self-organizing, Internet-based overlay network of storage nodes that cooperatively route file queries, store multiple replicas of files, and cache additional copies of popular files.In the PAST system, storage nodes and files are each assigned uniformly distributed identifiers, and replicas of a file are stored at nodes whose identifier matches most closely the file's identifier. This statistical assignment of files to storage nodes approximately balances the number of files stored on each node. However, non-uniform storage node capacities and file sizes require more explicit storage load balancing to permit graceful behavior under high global storage utilization; likewise, non-uniform popularity of files requires caching to minimize fetch distance and to balance the query load.We present and evaluate PAST, with an emphasis on its storage management and caching system. Extensive trace-driven experiments show that the system minimizes fetch distance, that it balances the query load for popular files, and that it displays graceful degradation of performance as the global storage utilization increases beyond 95%.

References

1. 1 Napster. http://www.napster.com/.]]
2. 2 The Gnutella protocol specification, 2000. http: / / dss.clip2.com/GnuteUaProtocolO4.pdf.]]
3. 3 W. Adjie-Winoto, E. Schwartz, H. Baiakrishnan, and J. Lilley. The design and implementation of an intentional naming system. In Proc. SOSP'99, Kiawah Island, SC, Dec. 1999.]]
4. 4 Y. Amir, A. Peterson, and D. Shaw. Seamlessly selecting the best copy from Internet-wide replicated web servers. In Proc. 12th Symposium on Distributed Computing, Andros, Greece, Sept. 1998.]]
5. 5 R. Anderson. The Eternity service. In Proc. PRAGOCRYPT'96, pages 242-252. CTU Publishing House, 1996. Prague, Czech Republic.]]
6. 6 T. Anderson, M. Dahlin, J. Neefe, D. Patterson, D. RoseUi, and R. Wang. Serverless network file systems. In Proe. 15th A CM SOSP, Copper Mountain, CO, Dec. 1995.]]
7. 7 F. Bennett, D. Clarke, J. B. Evans, A. Hopper, A. Jones, and D. Leask. Piconet - embedded mobile networking. IBEE Personal Communications, 4(5):8-15, October 1997.]]
8. 8 W. J. Bolosky, J. R. Douceur, D. Ely, and M. Theimer. Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs. In Proc. SIGMBTRICS'2000, Santa Clara, CA, 2000.]]
9. 9 M. Bowman, L. L. Peterson, and A. Yeatts. Univers: An attribute-based name server. Software -- Practice and Experience, 20(4):403-424, Apr. 1990.]]
10. 10 L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In Proc. IEEE Infoeom'g9, New York, NY, Mar. 1999.]]
11. 11 P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. In Proc. USENIX Symposium on Internet Technologies and Systems (USITS), Monterey, CA, Dec. 1997.]]
12. 12 D. R. Cheriton and T. P. Mann. Decentralizing a global naming service for improved performance and fault tolerance. ACM Trans. Comput. Syst., 7(2):147-183, May 1989.]]
13. 13 I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Workshop on Design Issues in Anonymity and Unobservability, pages 311-320, July 2000. ICSI, Berkeley, CA, USA.]]
14. 14 F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. ACM SOSP'01, Banff, Canada, Oct. 2001.]]
15. 15 It. Dingledine, M. J. Freedman, and D. Molnar. The Free Haven project: Distributed anonymous storage service. In Proc. Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, July 2000.]]
16. 16 P. Druschel and A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS VIII, Schloss Elman, Germany, May 2001.]]
17. 17 J. Jannotti, D. K. Gifford, K. L. Johnson, M. F. Kaashoek, and J. W. O'Toole. Overcast: Reliable multicasting with an overlay network. In Proc. OSDI 2000, San Diego, CA, October 2000.]]
18. 18 J. Kangasharju, J. W. Roberts, and K. W. Ross. Performance evaluation of redirection schemes in content distribution networks. In Proc. 4th Web Caching Workshop, San Diego, CA, Mar. 1999.]]
19. 19 J. Kangasharju and K. W. Ross. A replicated architecture for the domain name system. In Proc. IEEE Infocom 2000, Tel Aviv, Israel, Max. 2000.]]
20. 20 J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for global-scale persistent store. In Proc. ASPLOS'2000, Cambridge, MA, November 2000.]]
21. 21 B. Lampson. Designing a global name service. In Proc. Fifth Symposium on the Principles of Distributed Computing, pages 1-10, Minaki, Canada, Aug. 1986.]]
22. 22 J. Li, J. 3annotti, D. S. J. D. Couto, D. R. Karger, and R. Morris. A scalable location service for geographical ad hoc routing. In Proc. of A CM MOBICOM 2000, Boston, MA, August 2000.]]
23. 23 J. S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software -- Practice and Experience, 27(9):995-1012, Sept. 1997.]]
24. 24 C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241-280, 1999.]]
25. 25 S. Ratnasamy, P. Francis, M. Handiey, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM'01, San Diego, CA, Aug. 2001.]]
26. 26 J. Reynolds. RFC 1309: Technical overview of directory services using the X.500 protocol, Mar. 1992.]]
27. 27 A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. IFIP/A CM Middleware 2001, Heidelberg, Germany, Nov. 2001.]]
28. 28 S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. Technical Roport UW-CSE-01-06-02, University of Washington, July 2001.]]
29. 29 M. A. Sheldon, A. Duda, R. Weiss, and D. K. Gifford. Discover: A resource discovery system based on content routing. In Proe. 3rd International World Wide Web Conference, Darmstadt, Germany, 1995.]]
30. 30 I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. A CM SIGCOMM'01, San Diego, CA, Aug. 2001.]]
31. 31 B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-resilient wide-area location and routing. Technical Report UCB//CSD-01-1141, U. C. Berkeley, April 2001.]]

Index Terms

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

    • Software system structures

      • Distributed systems organizing principles