Lazy modular upgrades in persistent object stores

ABSTRACT

Persistent object stores require a way to automatically upgrade persistent objects, to change their code and storage representation. Automatic upgrades are a challenge for such systems. Upgrades must be performed in a way that is efficient both in space and time, and that does not stop application access to the store. In addition, however, the approach must be modular: it must allow programmers to reason locally about the correctness of their upgrades similar to the way they would reason about regular code. This paper provides solutions to both problems.The paper first defines upgrade modularity conditions that any upgrade system must satisfy to support local reasoning about upgrades. The paper then describes a new approach for executing upgrades efficiently while satisfying the upgrade modularity conditions. The approach exploits object encapsulation properties in a novel way. The paper also describes a prototype implementation and shows that our upgrade system imposes only a small overhead on application performance.

REFERENCES

• 1: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.23-34, May 22-25, 1995, San Jose, California, United States
• 2: Ole Agesen , Stephen N. Freund , John C. Mitchell, Adding type parameterization to the Java language, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.49-65, October 05-09, 1997, Atlanta, Georgia, United States
• 3: Jonathan Aldrich , Valentin Kostadinov , Craig Chambers, Alias annotations for program understanding, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 4: M. P. Atkinson, F. Bancilhon, D. J. DeWitt, K. R. Dittrich, D. Maier, and S. B. Zdonik. The object-oriented database system manifesto. In SIGMOD Conference, May 1990.
• 5: Malcolm P. Atkinson , Misha Dmitriev , Craig Hamilton , Tony Printezis, Scalable and Recoverable Implementation of Object Evolution for the PJama1 Platform, Revised Papers from the 9th International Workshop on Persistent Object Systems, p.292-314, September 06-08, 2000
• 6: M. P. Atkinson, M. J. Jordan, L. Daynes, and S. Spence. Design issues for persistent Java: A type-safe, object-oriented, orthogonally persistent system. In Persistent Object Systems (POS), May 1996.
• 7: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• 8: E. Bertino, G. Guerrini, and L. Rusca. Object evolution in object databases. In B. Franhoefer and R. Pareschi, editors, Dynamic Worlds, Kluwer Academic Publishers, 1999.
• 9: C. Boyapati. JPS: A distributed persistent Java system. SM thesis, Massachusetts Institute of Technology, September 1998.
• 10: C. Boyapati, R. Lee, and M. Rinard. Safe runtime downcasts with ownership types. In ECOOP International Workshop on Aliasing, Confinement and Ownership in Object-Oriented Programming (IWACO), July 2003.
• 11: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 12: Chandrasekhar Boyapati , Barbara Liskov , Liuba Shrira, Ownership types for object encapsulation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-223, January 15-17, 2003, New Orleans, Louisiana, USA
• 13: C. Boyapati, B. Liskov, and L. Shrira. Ownership types and safe lazy upgrades in object-oriented databases. Technical Report TR-858, MIT Laboratory for Computer Science, July 2002.
• 14: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 15: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 16: Gilad Bracha , Martin Odersky , David Stoutamire , Philip Wadler, Making the future safe for the past: adding genericity to the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.183-200, October 18-22, 1998, Vancouver, British Columbia, Canada
• 17: Robert Bretl , David Maier , Allen Otis , Jason Penney , Bruce Schuchardt , Jacob Stein , E. Harold Williams , Monty Williams, The Gem–Stone data management system, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989 [doi>10.1145/63320.66507]
• 18: Michael J. Carey , David J. DeWitt , Chander Kant , Jeffrey F. Naughton, A status report on the OO7 OODBMS benchmarking effort, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.414-426, October 23-28, 1994, Portland, Oregon, United States
• 19: Miguel Castro , Atul Adya , Barbara Liskov , Andrew C. Meyers, HAC: hybrid adaptive caching for distributed storage systems, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.102-115, October 05-08, 1997, Saint Malo, France
• 20: Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: Y. Cheung. Lazy schema evolution in object-oriented databases. SM thesis, Massachusetts Institute of Technology, September 2001.
• 22: Stewart M. Clamen, Type Evolution and Instance Adaptation, Carnegie Mellon University, Pittsburgh, PA, 1992
• 23: David Gerard Clarke, Object ownership and containment, 2003
• 24: Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 25: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 26: Viviane M. Crestana-Jensen , Amy J. Lee , Elke A. Rundensteiner, Consistent Schema Version Removal: An Optimization Technique for Object-Oriented Views, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.261-280, March 2000 [doi>10.1109/69.842266]
• 27: Mark Day , Robert Gruber , Barbara Liskov , Andrew C. Myers, Subtypes vs. where clauses: constraining parametric polymorphism, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.156-168, October 15-19, 1995, Austin, Texas, United States
• 28: Christine Delcourt , Roberto Zicari, The Design of an Integrity Consistency Checker (ICC) for an Object-Oriented Database System, Proceedings of the European Conference on Object-Oriented Programming, p.97-117, July 15-19, 1991
• 29: O. Deux et al., The Story of O2, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.91-108, March 1990 [doi>10.1109/69.50908]
• 30: Mikhail Dmitriev, Safe Class and Data Evolution in Large and Long-Lived Java[tm] Applications, Sun Microsystems, Inc., Mountain View, CA, 2001
• 31: Sophia Drossopoulou , Ferruccio Damiani , Mariangiola Dezani-Ciancaglini , Paola Giannini, Fickle: Dynamic Object Re-classification, Proceedings of the 15th European Conference on Object-Oriented Programming, p.130-149, June 18-22, 2001
• 32: D. Duggan. Type-based hot swapping of running modules. Technical Report SIT CS 2001-7, Stevens Institute of Technology, Hoboken, NJ 07030, October 2001.
• 33: Fabrizio Ferrandina , Thorsten Meyer , Roberto Zicari , Guy Ferran , Joëlle Madec, Schema and Database Evolution in the O2 Object Database System, Proceedings of the 21th International Conference on Very Large Data Bases, p.170-181, September 11-15, 1995
• 34: F. Ferrandina, T. Meyer, and R. Zicari. Measuring the Performance of Immediate and Deferred Updates in Object Database Systems. In Proceedings of the OOPSLA Workshop on Object Database Behavior, Benchmarks and Performance, 1995.
• 35: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 36: Michael Hicks , Jonathan T. Moore , Scott Nettles, Dynamic software updating, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.13-23, June 2001, Snowbird, Utah, United States
• 37: G. Hjalmtysson and R. Gray. Dynamic C++ classes - a lightweight mechanism to update code in running program. In USENIX Annual Technical Conference, June 1998.
• 38: K. R. M. Leino and G. Nelson. Data abstraction and information hiding. Research Report 160, Compaq Systems Research Center, November 2000.
• 39: K. Rustan M. Leino , Arnd Poetzsch-Heffter , Yunhong Zhou, Using data groups to specify and check side effects, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 40: Barbara Staudt Lerner , A. Nico Habermann, Beyond schema evolution to database reorganization, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.67-76, September 1990, Ottawa, Canada
• 41: Barbara Liskov , Miguel Castro , Liuba Shrira , Atul Adya, Providing Persistent Objects in Distributed Systems, Proceedings of the 13th European Conference on Object-Oriented Programming, p.230-257, June 14-18, 1999
• 42: B. Liskov, C. Moh, S. Richman, L. Shrira, Y. Cheung, and C. Boyapati. Safe lazy software upgrades in object-oriented databases. Technical Report TR-851, MIT Laboratory for Computer Science, June 2002.
• 43: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 44: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• 45: Joseph A. Bank , Andrew C. Myers , Barbara Liskov, Parameterized types for Java, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.132-145, January 15-17, 1997, Paris, France [doi>10.1145/263699.263714]
• 46: Object Design Inc. ObjectStore Advanced C++ API User Guide Release 5.1, 1997.
• 47: Objectivity Inc. Objectivity Technical Overview, Version 6.0, 2001.
• 48: D. Jason Penney , Jacob Stein, Class modification in the GemStone object-oriented DBMS, Conference proceedings on Object-oriented programming systems, languages and applications, p.111-117, October 04-08, 1987, Orlando, Florida, United States
• 49: Andrea H. Skarra , Stanley B. Zdonik, The management of changing types in an object-oriented database, Conference proceedings on Object-oriented programming systems, languages and applications, p.483-495, September 29-October 02, 1986, Portland, Oregon, United States
• 50: Versant Object Technology. Versant User Manual, 1992.
• 51: Mirko Viroli , Antonio Natali, Parametric polymorphism in Java: an approach to translation based on reflective features, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.146-165, October 2000, Minneapolis, Minnesota, United States
• 52: Roberto Zicari, A Framework for Schema Updates In An Object-Oriented Database System, Proceedings of the Seventh International Conference on Data Engineering, p.2-13, April 08-12, 1991

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages, Verification

Keywords:
ownership types, presistent objects, software upgrades