Partitioned Garbage Collection of Large Object Store.

@inproceedings{DBLP:conf/sigmod/MaheshwariL97,
  author    = {Umesh Maheshwari and
               Barbara Liskov},
  editor    = {Joan Peckham},
  title     = {Partitioned Garbage Collection of Large Object Store},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {313-323},
  ee        = {http://doi.acm.org/10.1145/253260.253338, db/conf/sigmod/MaheshwariL97.html},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present new techniques for efficient garbage collection in a large persistent object store. The store is divided into partitions that are collected independently using information about inter-partition references. This information is maintained on disk so that it can be recovered after a crash. We use new techniques to organize and update this information while avoiding disk accesses. We also present a new global marking scheme to collect cyclic garbage across partitions. Global marking is piggybacked on partitioned collection; the result is an efficient scheme that preserves the localized nature of partitioned collection, yet is able to collect all garbage.

We have implemented the part of garbage collection responsible for maintaining information about inter-partition references. We present a performance study to evaluate this work; the results show that our techniques result in substantial savings in the usage of disk and memory.

Copyright © 1997 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

[AFFS95]

...

[AGF95]

Laurent Amsaleg, Michael J. Franklin, Olivier Gruber: Efficient Incremental Garbage Collection for Client-Server Object Database Systems. VLDB 1995: 42-53 BibTeX

[Bak78]

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

[Bak93]

Henry G. Baker: 'Infant Mortality' and Generational Garbage Collection. SIGPLAN Notices 28(4): 55-57(1993) BibTeX

[Bis77]

...

[CKWZ96]

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 BibTeX

[CWZ94]

Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994: 371-382 BibTeX

[FS96]

Paulo Ferreira, Marc Shapiro: Larchant: Persistence by Reachability in Distributed Shared Memory Through Garbage Collection. ICDCS 1996: 394-401 BibTeX

[Ghe95]

...

[HM92]

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

[Hug85]

...

[JJ92]

Niels Christian Juul, Eric Jul: Comprehensive and Robust Garbage Collection in a Distributed System. IWMM 1992: 103-115 BibTeX

[KW93]

Elliot K. Kolodner, William E. Weihl: Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. SIGMOD Conference 1993: 177-186 BibTeX

[LAC+96]

Barbara Liskov, Atul Adya, Miguel Castro, Mark Day, Sanjay Ghemawat, Robert Gruber, Umesh Maheshwari, Andrew C. Myers, Liuba Shrira: Safe and Efficient Sharing of Persistent Objects in Thor. SIGMOD Conference 1996: 318-329 BibTeX

[LGG+91]

Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, Michael Williams: Replication in the Harp File System. SOSP 1991: 226-238 BibTeX

[LL92]

...

[LMN96]

...

[LQP92]

Bernard Lang, Christian Queinnec, José M. Piquer: Garbage Collecting the World. POPL 1992: 39-50 BibTeX

[ML94]

Umesh Maheshwari, Barbara Liskov: Fault-Tolerant Distributed Garbage Collection in a Client-Server Object-Oriented Database. PDIS 1994: 239-248 BibTeX

[ML95]

Umesh Maheshwari, Barbara Liskov: Collecting Cyclic Distributed Garbage Using Heuristics to Control Migration. PODC 1995: 57-63 BibTeX

[MMH96]

J. Eliot B. Moss, David S. Munro, Richard L. Hudson: PMOS: A Complete and Coarse-Grained Incremental Garbage Collector for Persistent Object Stores. POS 1996: 140-150 BibTeX

[Ng96]

...

[ONG93]

James O'Toole, Scott Nettles, David K. Gifford: Concurrent Compacting Garbage Collection of a Persistent Heap. SOSP 1993: 161-174 BibTeX

[SGP90]

...

[Sob88]

...

[Ung84]

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

[YNY94]

Voon-Fee Yong, Jeffrey F. Naughton, Jie-Bing Yu: Storage Reclamation and Reorganization in Client-Server Persistent Object Stores. ICDE 1994: 120-131 BibTeX

Referenced by

1. Marcin Skubiszewski, Patrick Valduriez: Concurrent Garbage Collection in O2. VLDB 1997: 356-365