Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap.

@inproceedings{DBLP:conf/sigmod/KolodnerW93,
  author    = {Elliot K. Kolodner and
               William E. Weihl},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Atomic Incremental Garbage Collection and Recovery for a Large
               Stable Heap},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {177-186},
  ee        = {http://doi.acm.org/10.1145/170035.170068, db/conf/sigmod/KolodnerW93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 featnres 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.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Antonio Albano, Luca Cardelli, Renzo Orsini: Galileo: A Strongly-Typed, Interactive Conceptual Language. ACM Trans. Database Syst. 10(2): 230-260(1985)

[2]

Malcolm P. Atkinson, Peter J. Bailey, Kenneth Chisholm, W. Paul Cockshott, Ronald Morrison: An Approach to Persistent Programming. Comput. J. 26(4): 360-365(1983)

[3]

Henry G. Baker Jr.: List Processing in Real Time on a Serial Computer. Commun. ACM 21(4): 280-294(1978)

[4]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents

[5]

...

[6]

Hans-Juergen Boehm, Alan J. Demers, Scott Shenker: Mostly Parallel Garbage Collection. PLDI 1991: 157-164

[7]

Alfred L. Brown, John Rosenberg: Persistent Object Stores: An Implementation Technique. POS 1990: 199-212

[8]

Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100

[9]

Robert Courts: Improving Locality of Reference in a Garbage-Collecting Memory Management System. Commun. ACM 31(9): 1128-1138(1988)

[10]

David Detlefs, Maurice Herlihy, Jeannette M. Wing: Inheritance of Synchronization and Recovery Properties in Avalon/C++. IEEE Computer 21(12): 57-69(1988)

[11]

...

[12]

...

[13]

Dieter Gawlick, David Kinkade: Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Database Eng. Bull. 8(2): 3-10(1985)

[14]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents

[15]

Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983)

[16]

...

[17]

Richard L. Hudson, J. Eliot B. Moss: Incremental Collection of Mature Objects. IWMM 1992: 388-403

[18]

Scott E. Hudson, Roger King: Cactis: A Self-Adaptive, Concurrent Implementation of an Object-Oriented Database Management System. ACM Trans. Database Syst. 14(3): 291-321(1989)

[19]

Elliot K. Kolodner: Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. POS 1990: 185-198

[20]

Elliot K. Kolodner, Barbara Liskov, William E. Weihl: Atomic Garbage Collection: Managing a Stable Heap. SIGMOD Conference 1989: 15-25

[21]

...

[22]

...

[23]

Butler W. Lampson: Atomic Transactions. Advanced Course: Distributed Systems 1980: 246-265

[24]

Henry Lieberman, Carl Hewitt: A Real-Time Garbage Collector Based on the Lifetimes of Objects. Commun. ACM 26(6): 419-429(1983)

[25]

...

[26]

Barbara Liskov: Distributed Programming in Argus. Commun. ACM 31(3): 300-312(1988)

[27]

Barbara Liskov, Dorothy Curtis, Paul Johnson, Robert Scheifler: Implementation of Argus. SOSP 1987: 111-122

[28]

David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482

[29]

C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992)

[30]

...

[31]

Brian M. Oki, Barbara Liskov, Robert Scheifler: Reliable Object Storage to Support Atomic Actions. SOSP 1985: 147-159

[32]

...

[33]

...

[34]

Satish M. Thatte: Persistent Memory: A Storage Architecture for Object-Oriented Database Systems. OODBS 1986: 148-159

[35]

David Ungar: Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm. Software Development Environments (SDE) 1984: 157-167

[36]

William E. Weihl, Barbara Liskov: Implementation of Resilient, Atomic Data Types. ACM Trans. Program. Lang. Syst. 7(2): 244-269(1985)

[37]

Gerhard Weikum: A Theoretical Foundation of Multi-Level Concurrency Control. PODS 1986: 31-43

[38]

Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991)

[39]

Paul R. Wilson, Michael S. Lam, Thomas G. Moher: Effective ``Static-Graph'' Reorganization to Improve Locality in Garbage-Collected Systems. PLDI 1991: 177-191

[40]

...

Referenced by

1. Mohana Krishna Lakhamraju, Rajeev Rastogi, S. Seshadri, S. Sudarshan: On-line Reorganization in Object Databases. SIGMOD Conference 2000: 58-69
2. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: A Highly Effective Partition Selection Policy for Object Database Garbage Collection. IEEE Trans. Knowl. Data Eng. 10(1): 153-172(1998)
3. Umesh Maheshwari, Barbara Liskov: Partitioned Garbage Collection of Large Object Store. SIGMOD Conference 1997: 313-323
4. Jonathan E. Cook, Artur Klauser, Alexander L. Wolf, Benjamin G. Zorn: Semi-automatic, Self-adaptive Control of Garbage Collection Rates in Object Databases. SIGMOD Conference 1996: 377-388
5. Laurent Amsaleg, Michael J. Franklin, Olivier Gruber: Efficient Incremental Garbage Collection for Client-Server Object Database Systems. VLDB 1995: 42-53
6. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994: 371-382
7. Voon-Fee Yong, Jeffrey F. Naughton, Jie-Bing Yu: Storage Reclamation and Reorganization in Client-Server Persistent Object Stores. ICDE 1994: 120-131
8. Patricia G. Selinger: Predictions and Challenges for Database Systems in the Year 2000. VLDB 1993: 667-675

Last update Fri May 25 08:38:37 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page