Atomic garbage collection: managing a stable heap

ABSTRACT

Modern database systems use transactions to achieve a high degree of fault-tolerance. Many modern programming languages and systems provide garbage collected heap storage, which frees the programmer from the job of explicitly deallocating storage. In this paper we describe integrated garbage collection and recovery algorithms for managing a stable heap in which accessible objects survive both system crashes and media failures. A garbage collector typically both moves and modifies objects which can lead to problems when the heap is stable because a system crash after the start of collection but before enough of the reorganized heap reaches the disk can leave the disk in an inconsistent state. Furthermore, collection has to be coordinated with the recovery system. We present a collection algorithm and recovery system that solves these problems.

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. Morrison. An Approach to Persistant Programming. The Computer Journal, 26(4):360-365, 1983.
• 3: 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
• 4: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 5: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 6: 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]
• 7: Robert C. Daley , Jack B. Dennis, Virtual memory, processes, and sharing in MULTICS, Communications of the ACM, v.11 n.5, p.306-312, May 1968 [doi>10.1145/363095.363139]
• 8: Jeffrey L. Dawson, Improved effectiveness from a real time LISP garbage collector, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.159-167, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802146]
• 9: Jeffrey L. Eppinger and Alfred Z. Spector. Virtual Memory Management for Recoverable Objects in the TABS Prototype. Technical Report CMU-CS-85-163, Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pa., December 1985.
• 10: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 11: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 12: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 13: 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]
• 14: E. K. Kolodner, RECOVERY USING VIRTUAL MEMORY, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 15: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 16: 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]
• 17: Barbara Liskov. Overview of the Argus Language and System. Programming Methodology Group Memo 40, Laboratory for Computer Science, MIT, Cambridge, Ms., February 1984.
• 18: 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
• 19: 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
• 20: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 21: Nathaniel Mishkin. Managing Permanent Objects. Technical Report YALEU/DCS/RR-338, Department of Computer Science, Yale University, New Haven, Ct., November 1984.
• 22: 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]
• 23: 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
• 24: Richard F. Rashid. Threads of a New System. Unix Review, 4(8):37-49, August 1986.
• 25: Alfred Z. Spector, J. J. Bloch, Dean Daniels, R. P. Draves, Daniel Duchamp, Jeffrey L. Eppinger, S. G. Menees, and D. S. Thompson. The camelot project. Database Engineering, 9(4), December 1986.
• 26: Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, Proceedings of the tenth ACM symposium on Operating systems principles, p.127-146, December 1985, Orcas Island, Washington, United States
• 27: Satish M. Thatte. Persistent Memory: Merging AI- Knowledge and Databases. Texas Instruments Engineering journal, 3(1), January-February 1986.
• 28: 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
• 29: Daniel Weinreb, Neal Feinberg, Dan Gerson, and Charles Lamb. An Object-Oriented Database System to Support an Integrated Programming Environment. 1988. Submitted for publication.
• 30: Stanley Zdonik and Peter 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: Query processing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Design, Languages