Atomic incremental garbage collection and recovery for a large stable heap

ABSTRACT

A stable heap is storage that is managed automatically using garbage collection, manipulated using atomic transactions, and accessed using a uniform storage model. These features enhance reliability and simplify programming by preventing errors due to explicit deallocation, by masking failures and concurrency using transactions, and by eliminating the distinction between accessing temporary storage and permanent storage. Stable heap management is useful for programming languages for reliable distributed computing, programming languages with persistent storage, and object-oriented database systems. Many applications that could benefit from a stable heap (e.g., computer-aided design, computer-aided software engineering, and office information systems) require large amounts of storage, timely responses for transactions, and high availability. We present garbage collection and recovery algorithms for a stable heap implementation that meet these goals and are appropriate for stock hardware. The collector is incremental: it does not attempt to collect the whole heap at once. The collector is also atomic: it is coordinated with the recovery system to prevent problems when it moves and modifies objects. The time for recovery is independent of heap size, even if a failure occurs during garbage collection.

REFERENCES

• 1: Antonio Albano , Luca Cardelli , Renzo Orsini, GALILEO: a strongly-typed, interactive conceptual language, ACM Transactions on Database Systems (TODS), v.10 n.2, p.230-260, June 1985 [doi>10.1145/3857.3859]
• 2: M.P. Atkinson, P. J. Bailey, K. J. Chisholm, P. W. Cockshott, and R. Motrison. An Approach to Persistent Programming. The Computer Journal, 26(4):360--365, 1983.
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: P. B. Bishop. Computer Systems with a Very Large Address Space and Garbage Collection. Technical Report MIT/LCS#-178, Laboratory for Computer Science, M1T, Cambridge, Ma., May 1977.
• 6: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
• 7: A. Brown and J. Rosenberg. Persistent Object Stores: An Implementation Technique. In A. Dearie, G. M. Shaw, and S. B. Zdonik, editors, Implementing Persistent Object Bases: Principles and Practice. Proceedings of the Fourth International Workshop on Persistent Object Systems, pages 199--212. Morgan Kaufmann Publishers, San Mateo, Ca., 1990.
• 8: Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
• 9: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 10: David L. Detlefs , Maurice P. Herlihy , Jeannette M. Wing, Inheritance of Synchronization and Recovery Properties in Avalon/C++, Computer, v.21 n.12, p.57-69, December 1988 [doi>10.1109/2.16189]
• 11: D. L. Detlefs. Concurrent, Atomic Garbage Collection. Technical Report CMU-CS-90-177, Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pa., October 1990.
• 12: J. R, Ellis, K. Li, and A. W. Appel. Real-time Concurrent Collection on Stock Multiprocessors. Technical Report 25, Systems Research Center, Digital Equipment Corporation, Palo Alto, Ca., February 1988.
• 13: D. Gawlick and D. Kinkade. Varieties of Concurrency Control in IMS/VS Fast Path. Database Engineering, 8(2):63--70, June 1985.
• 14: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 15: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 16: M. P. Herlihy and J. M. Wing. Avalon: Language Support for Reliable Distributed Systems. In Proceedings of the Seventeenth International Symposium on Fault-Tolerant Computing, July 1987.
• 17: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 18: Scott E. Hudson , Roger King, Cactis: a self-adaptive, concurrent implementation of an object-oriented database management system, ACM Transactions on Database Systems (TODS), v.14 n.3, p.291-321, Sept. 1989 [doi>10.1145/68012.68013]
• 19: E. Kolodner. Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. In A. Dearie, G. M. Shaw, and S. B. Zdonik, editors, Implementing Persistent Object Bases: Principles and Practice. Proceedings of the Fourth International Workshop on Persistent Object Systems, pages 185--198. Morgan Kaufmann Publishers, San Mateo, Ca., 1990.
• 20: Elliot Kolodner , Barbara Liskov , William Weihl, Atomic garbage collection: managing a stable heap, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.15-25, June 1989, Portland, Oregon, United States
• 21: E. K. Kolodner, RECOVERY USING VIRTUAL MEMORY, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 22: E. K. Kolodner. Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. Technical Report MIT/LCS/TR-534, Laboratory for Computer Science, MIT, Cambridge, Ma., February 1992.
• 23: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 24: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 25: B. G. Lindsay, P. G. Selinger, C. Galtieri, J. N. Gray, R. A. Lode, T. G. Price, F. Putzolu, I. L. Traiger, and B. W. Wade. Notes on Distributed Databases. Technical Report RJ2571, IBM Research Laboratory, San Jose, Ca., July 1979.
• 26: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 27: B. Liskov , D. Curtis , P. Johnson , R. Scheifer, Implementation of Argus, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.111-122, November 08-11, 1987, Austin, Texas, United States
• 28: David Maier , Jacob Stein , Allen Otis , Alan Purdy, Development of an object-oriented DBMS, Conference proceedings on Object-oriented programming systems, languages and applications, p.472-482, September 29-October 02, 1986, Portland, Oregon, United States
• 29: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 30: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 31: Brian M. Oki , Barbara H. Liskov , Robert W. Scheifler, Reliable object storage to support atomic actions, Proceedings of the tenth ACM symposium on Operating systems principles, p.147-159, December 1985, Orcas Island, Washington, United States
• 32: R. F. Rashid. Threads of a New System. Unix Review, 4(8):37--49, August 1986.
• 33: M. Reinhold. Personal communication.
• 34: Satish M. Thatte, Persistent memory: a storage architecture for object-oriented database systems, Proceedings on the 1986 international workshop on Object-oriented database systems, p.148-159, September 23-26, 1986, Pacific Grove, California, United States
• 35: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 36: William Weihl , Barbara Liskov, Implementation of resilient, atomic data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.244-269, April 1985 [doi>10.1145/3318.3319]
• 37: Gerhard Weikum, A theoretical foundation of multi-level concurrency control, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.31-43, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15401]
• 38: Gerhard Weikum, Principles and realization strategies of multilevel transaction management, ACM Transactions on Database Systems (TODS), v.16 n.1, p.132-180, March 1991 [doi>10.1145/103140.103145]
• 39: Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.177-191, June 24-28, 1991, Toronto, Ontario, Canada
• 40: S. Zdonik and P. Wegner. Language and Methodology for Object-Oriented Database Environments. In Proceedings of the 19th Annual Hawaiian Conference on Systems Science, January 1986.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Logging and recovery

General Terms:
Algorithms, Design, Languages, Reliability