dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Partitioned Garbage Collection of Large Object Store.

Umesh Maheshwari, Barbara Liskov: Partitioned Garbage Collection of Large Object Store. SIGMOD Conference 1997: 313-323
@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},
  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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Joan Peckham (Ed.): SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press 1997 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 26(2), June 1997
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1333 KB]

References

[AFFS95]
...
[AGF95]
Laurent Amsaleg, Michael J. Franklin, Olivier Gruber: Efficient Incremental Garbage Collection for Client-Server Object Database Systems. VLDB 1995: 42-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bak78]
Henry G. Baker Jr.: List Processing in Real Time on a Serial Computer. Commun. ACM 21(4): 280-294(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bak93]
Henry G. Baker: 'Infant Mortality' and Generational Garbage Collection. SIGPLAN Notices 28(4): 55-57(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CWZ94]
Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994: 371-382 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FS96]
Paulo Ferreira, Marc Shapiro: Larchant: Persistence by Reachability in Distributed Shared Memory Through Garbage Collection. ICDCS 1996: 394-401 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ghe95]
...
[HM92]
Richard L. Hudson, J. Eliot B. Moss: Incremental Collection of Mature Objects. IWMM 1992: 388-403 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hug85]
...
[JJ92]
Niels Christian Juul, Eric Jul: Comprehensive and Robust Garbage Collection in a Distributed System. IWMM 1992: 103-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KW93]
Elliot K. Kolodner, William E. Weihl: Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. SIGMOD Conference 1993: 177-186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LGG+91]
Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, Michael Williams: Replication in the Harp File System. SOSP 1991: 226-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LL92]
...
[LMN96]
...
[LQP92]
Bernard Lang, Christian Queinnec, José M. Piquer: Garbage Collecting the World. POPL 1992: 39-50 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ML94]
Umesh Maheshwari, Barbara Liskov: Fault-Tolerant Distributed Garbage Collection in a Client-Server Object-Oriented Database. PDIS 1994: 239-248 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ML95]
Umesh Maheshwari, Barbara Liskov: Collecting Cyclic Distributed Garbage Using Heuristics to Control Migration. PODC 1995: 57-63 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ng96]
...
[ONG93]
James O'Toole, Scott Nettles, David K. Gifford: Concurrent Compacting Garbage Collection of a Persistent Heap. SOSP 1993: 161-174 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SGP90]
...
[Sob88]
...
[Ung84]
David Ungar: Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm. Software Development Environments (SDE) 1984: 157-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YNY94]
Voon-Fee Yong, Jeffrey F. Naughton, Jie-Bing Yu: Storage Reclamation and Reorganization in Client-Server Persistent Object Stores. ICDE 1994: 120-131 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:15 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page