OceanStore: an architecture for global-scale persistent storage

ABSTRACT

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.

References

1. 1.M. Abadi. On SDSI's linked local name spaces. In Proc. of IEEE CSFW, 1997.]]
2. 2.S. Acharya and S. B. Zdonik. An efficient scheme for dynamic data replication. Technical Report CS-93-43, Department of Computer Science, Brown University, 1993.]]
3. 3.T. Anderson, M. Dahlin, J. Neefe, D. Patterson, D. Roselli, and R. Wang. Serverless Network File Systems. In Proc. of ACM SOSP, Dec. 1995.]]
4. 4.B. Barak, A. Herzberg, D. Naor, and E. Shai. The proactive security toolkit and applications. In Proc. of ACM CCS Conf., pages 18-27, Nov. 1999.]]
5. 5.M. Blaze. A cryptographic file system for UNIX. In Proc. of ACM CCS Conf., Nov. 1993.]]
6. 6.M. Blaze, J. Feigenbaum, and J. Lacy. Decentralized trust management. In Proc. of IEEE SRSP, May 1996.]]
7. 7.B. Bloom. Space/time trade-offs in hash coding with allowable errors. In Communications of the ACM, volume 13(7), pages 422-426, July 1970.]]
8. 8.W. Bolosky, J. Douceur, D. Ely, and M. Theimer. Feasibility of a serverless distributed file system deployed on an existing set of desktop pcs. In Proc. of Sigmetrics, June 2000.]]
9. 9.W. Bolosky, R. Draves, R. Fitzgerald, C. Fraser, M. Jones, T. Knoblock, and R. Rashid. Operating systems directions for the next millennium. In Proc. of HOTOS Conf., May 1997.]]
10. 10.M. Castro and B. Liskov. Practical Byzantine fault tolerance. In Proc. of USENIX Symp. on OSDI, 1999.]]
11. 11.S. Chaudhuri and V. Narasayya. AutoAdmin "what-if" index analysis utility. In Proc. of ACM SIGMOD Conf., pages 367- 378, June 1998.]]
12. 12.M. Dahlin, T. Anderson, D. Patterson, and R. Wang. Cooperative caching: Using remote client memory to improve file system performance. In Proc. of USENIX Symp. on OSDI,Nov. 1994.]]
13. 13.A. Demers, K. Petersen, M. Spreitzer, D. Terry, M. Theimer, and B. Welch. The Bayou architecture: Support for data sharing among mobile users. In Proc. of IEEE Workshop on Mobile Computing Systems & Applications, Dec. 1994.]]
14. 14.W. Edwards, E. Mynatt, K. Petersen, M. Spreitzer, D. Terry, and M. Theimer. Designing and implementing asynchronous collaborative applications with Bayou. In Proc. of ACMSymp. on User Interface Software & Technology, pages 119-128, 1997.]]
15. 15.C. Ellison, B. Frantz, R. Rivest, B. Thomas, and T. Ylonen. SPKI certificate theory. RFC 2693, 1999.]]
16. 16.L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable wide-area Web cache sharing protocol. In Proc. of ACM SIGCOMM Conf., pages 254-265, Sept. 1998.]]
17. 17.M. Franklin, M. Carey, and M. Livny. Transactional clientserver cache consistency: Alternatives and performance. ACM Transactions on Database Systems, 22(3):315-363, Sept. 1997.]]
18. 18.A. Goldberg and P. Yianilos. Towards an archival intermemory. In Proc. of IEEE ADL, pages 147-156, Apr. 1998.]]
19. 19.J. Gray, P. Helland, P. O'Neil, and D. Shasha. The dangers of replication and a solution. In Proc. of ACM SIGMOD Conf., volume 25, 2, pages 173-182, June 1996.]]
20. 20.J. Griffioen and R. Appleton. Reducing file system latency using a predictive approach. In Proc. of USENIX Summer Technical Conf., June 1994.]]
21. 21.E. Hagersten, A. Landin, and S. Haridi. DDM - A Cacheonly Memory Architecture. IEEE Computer, Sept. 1992.]]
22. 22.J. Hill, R. Szewczyk, A. Woo, D. Culler, S. Hollar, and K. Pister. System architecture directions for networked sensors. In Proc. of ASPLOS, Nov. 2000.]]
23. 23.J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham, and M. West. Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6(1):51-81, Feb. 1988.]]
24. 24.J. Hughes, C. Feist, H. S, M. O'Keefe, and D. Corcoran. A universal access, smart-card-based secure file system. In Proc. of the Atlanta Linux Showcase, Oct. 1999.]]
25. 25.L. Kawell, S. Beckhardt, T. Halvorsen, R. Ozzie, and I. Greif. Replicated document management in a group communication system. In Proc. of ACM CSCW Conf., Sept. 1988.]]
26. 26.J. Kistler and M. Satyanarayanan. Disconnected operation in the Coda file system. ACM Transactions on Computer Sys-tems, 10(1):3-25, Feb. 1992.]]
27. 27.T. Kroeger and D. Long. Predicting file-system actions from prior events. In Proc. of USENIX Winter Technical Conf., pages 319-328, Jan. 1996.]]
28. 28.G. Kuenning. The design of the seer predictive caching system. In Proc. of IEEE Workshop on Mobile Computing Systems & Applications, Dec. 1994.]]
29. 29.H. Kung and J. Robinson. On optimistic methods for concurrency control. ACM Transactions on Database Systems, 6(2):213-226, June 1981.]]
30. 30.L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM TOPLAS, 4(3):382-401, 1982.]]
31. 31.E. Levy and A. Silberschatz. Distributed file systems: Concepts and examples. ACM Computing Surveys, 22(4):321- 375, Dec. 1990.]]
32. 32.M. Luby, M. Mitzenmacher, M. Shokrollahi, D. Spielman, and V. Stemann. Analysis of low density codes and improved designs using irregular graphs. In Proc. of ACM STOC, May 1998.]]
33. 33.L. Mackert and G. Lohman. R* optimizer validation and performance for distributed queries. In Proc. of Intl. Conf. on VLDB, Aug. 1986.]]
34. 34.J. Matthews, D. Roselli, A. Costello, R. Wang, and T. Anderson. Improving the performance of log-structured file systems with adaptive methods. In Proc. of ACM SOSP, Oct. 1997.]]
35. 35.D. Mazieres, M. Kaminsky, F. Kaashoek, and E. Witchel. Separating key management from file system security. In Proc. of ACM SOSP, 1999.]]
36. 36.M. Nelson, B. Welch, and J. Ousterhout. Caching in the sprite network file system. IEEE/ACM Transactions on Networking, 6(1):134-154, Feb. 1988.]]
37. 37.NIST. FIPS 186 digital signature standard. May 1994.]]
38. 38.D. Norman. The Invisible Computer, pages 62-63. MIT Press, Cambridge, MA, 1999.]]
39. 39.J. Plank. A tutorial on reed-solomon coding for faulttolerance in raid-like systems. Software Practice and Experience, 27(9):995-1012, Sept. 1997.]]
40. 40.C. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. of ACM SPAA, pages 311-320, Newport, Rhode Island, June 1997.]]
41. 41.M. Rabinovich, I. Rabinovich, R. Rajaraman, and A. Aggarwal. A dynamic object replication and migration protocol for an internet hosting service. In Proc. of IEEE ICDCS, pages 101-113, June 1999.]]
42. 42.R. Rivest and B. Lampson. SDSI-A simple distributed security infrastructure. Manuscript, 1996.]]
43. 43.R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and implementation of the Sun Network Filesystem. In Proc. of USENIX Summer Technical Conf., June 1985.]]
44. 44.D. Santry, M. Feeley, N. Hutchinson, A. Veitch, R. Carton, and J. Ofir. Deciding when to forget in the Elephant file system. In Proc. of ACM SOSP, Dec. 1999.]]
45. 45.M. Seltzer and C. Small. Self-monitoring and self-adapting operating systems. In Proc. of HOTOS Conf., pages 124-129, May 1997.]]
46. 46.J. Sidell, P. Aoki, S. Barr, A. Sah, C. Staelin, M. Stonebraker, and A. Yu. Data replication in Mariposa. In Proc. of IEEE ICDE, pages 485-495, Feb. 1996.]]
47. 47.D. Song, D. Wagner, and A. Perrig. Search on encrypted data. To be published in Proc. of IEEE SRSP, May 2000.]]
48. 48.M. Spreitzer, M. Theimer, K. Petersen, A. Demers, and D. Terry. Dealing with server corruption in weakly consistent, replicated data systems. In Proc. of ACM/IEEE Mobi- Com Conf., pages 234-240, Sept. 1997.]]
49. 49.M. Stonebraker. The design of the Postgres storage system. In Proc. of Intl. Conf. on VLDB, Sept. 1987.]]
50. 50.M. Weiser. The computer for the twenty-first centry. Scientific American, Sept. 1991.]]
51. 51.J. Wilkes, R. Golding, C. Staelin, and T. Sullivan. The HP AutoRAID hierarchical storage system. ACMTransactions on Computer Systems, pages 108-136, Feb. 1996.]]
52. 52.E. Wobber, M. Abadi, M. Burrows, and B. Lampson. Authentication in the Taos operating system. In Proc. of ACM SOSP, pages 256-269, Dec. 1993.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

      • Client-server architectures

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Metrics

    • Performance

• Hardware

  • Communication hardware, interfaces and storage

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data encryption

    • Middleware for databases

      • Application servers

      • Database web servers

  • Information storage systems

    • Storage management

• Networks

  • Network performance evaluation

• Security and privacy

  • Cryptography

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Project and people management

        • Systems analysis and design

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

• Theory of computation

  • Computational complexity and cryptography

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems