article

Free access

Semi-automatic, self-adaptive control of garbage collection rates in object databases

Authors:

Jonathan E. Cook,

Artur W. Klauser,

Alexander L. Wolf,

Benjamin G. ZornAuthors Info & Claims

ACM SIGMOD Record, Volume 25, Issue 2

Pages 377 - 388

https://doi.org/10.1145/235968.233354

Published: 01 June 1996 Publication History

Abstract

A fundamental problem in automating object database storage reclamation is determining how often to perform garbage collection. We show that the choice of collection rate can have a significant impact on application performance and that the "best" rate depends on the dynamic behavior of the application, tempered by the particular performance goals of the user. We describe two semi-automatic, self-adaptive policies for controlling collection rate that we have developed to address the problem. Using trace-driven simulations, we evaluate the performance of the policies on a test database application that demonstrates two distinct reclustering behaviors. Our results show that the policies are effective at achieving user-specified levels of I/O operations and database garbage percentage. We also investigate the sensitivity of the policies over a range of object connectivities. The evaluation demonstrates that semi-automatic, self-adaptive policies are a practical means for flexibly controlling garbage collection rate.

References

[1]

L. Amsaleg, M. Franklin, and O. Gruber. Efficient incremental garbage collection for clientserver object database systems. In Proceedings of the 21st VLDB Conference, Zurich, Switzerland, September 1995.

Digital Library

[2]

Anders Bjgrnerstedt. Secondary Storage Garbage Collectzon for Decentrahzed Object- Based Systems. PhD thesis, Stockholm University, Dept. of Comp. Sys. Sciences, Royal Inst. of Tech. and Stockholm Univ., Kista, Sweden, 1993. Also appears as Systems Dev. and AI Lab. Report No. 77.

[3]

Margaret H. Butler. Storage reclamation in object-oriented database systems. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 410- 423, San Francisco, CA, 1987.

Digital Library

[4]

Jack Campin and Malcolm Atkinson. A persistent store garbage collector with statistical facilities. Persistent Programming Reserarch Report 29, Department of Computing Science, University of Glasgow, Glasgow, Scotland, 1986.

[5]

R.G.G. Cattell, editor. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1993.

Digital Library

[6]

Michael J. Carey, David J. DeWitt, and Jeffrey F. Naughton. The OO7 benchmark. In Proceedings of the A CM SIGMOD International Conference on the Management of Data~ pages 12-21, Washington, DC, June 1993.

Digital Library

[7]

C.J. Cheney. A nonrecursive list compacting algorithm. Comm. ofthe ACM, 13(11):677-678, November 1970.

Digital Library

[8]

Servio Corporation. Announcing GemStone version 4.0. Product literature, 1994.

[9]

Jonathan Cook, Alexander Wolf, and Benjamin Zorn. The design of a simulation system for persistent object storage management. TechnicM Report CU-CS-647-93, Department of Computer Science, University of Colorado, Boulder, CO, March 1993.

[10]

Jonathan Cook, Alexander Wolf, and Benjamin Zorn. Partition selection policies in object database garbage collection. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 371-382, Minneapolis, MN, March 1994.

Digital Library

[11]

Elliot Kolodner, Barbara Liskov, and William Weihl. Atomic garbage collection: Managing a stable heap. In Proceedings of the ACM SIG- MOD International Conference on the Management of Data, pages 15-25, Portland, OR, June 1989.

Digital Library

[12]

Elliot Kolodner and William Weihl. Atomic incremental garbage collection and recovery for a large stable heap. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 177-186, Washington, DC, June 1993.

Digital Library

[13]

David C. J. Matthews. Poly manual. SIGPLAN Not,ces, 20(9), September 1985.

Digital Library

[14]

Umesh M~heshwari and Barbara Liskov. F~ulttolerant distributed garbage collection in a client-server, object-oriented database. In Proceed,ngs of the Parallel and Distmbuted Information Systems, pages 239-248, Austin, TX, September 1994.

[15]

Paul R. Wilson. Uniprocessor garbage collection techniques. In Proceedings of the Internatzonal Workshop on Memory Management, St. Malo, France, September 1992.

Digital Library

[16]

Jr. William J. McIver and Roger King. Selfadaptive, on-line reclustering of complex object data. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 407-418, Minneapolis, MN, March 1994.

Digital Library

[17]

Voon-Fee Yong, Jeffrey Naughton, and Jie-Bing Yu. Storage reclamation and reorganization in client-server persistent object stores. In Proc. of the l Oth International Conference on Data Eng~neemng, pages 120-131, February 1994.

Digital Library

Cited By

Wang JBalazinska MAfrati FSroka JHidders J(2016)Toward elastic memory management for cloud data analyticsProceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond10.1145/2926534.2926541(1-4)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2926534.2926541
Naeem Irfan MOriat CGroz R(2013)Model Inference and Testing10.1016/B978-0-12-408094-2.00003-5(89-139)Online publication date: 2013
https://doi.org/10.1016/B978-0-12-408094-2.00003-5
Cook JWolf AZorn B(1998)A Highly Effective Partition Selection Policy for Object Database Garbage CollectionIEEE Transactions on Knowledge and Data Engineering10.1109/69.66710010:1(153-172)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.1109/69.667100
Show More Cited By

Index Terms

Semi-automatic, self-adaptive control of garbage collection rates in object databases
1. Information systems
  1. Data management systems
    1. Database management system engines
  2. Information storage systems
    1. Storage management
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        File systems management
        Memory management

Recommendations

Semi-automatic, self-adaptive control of garbage collection rates in object databases
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

A fundamental problem in automating object database storage reclamation is determining how often to perform garbage collection. We show that the choice of collection rate can have a significant impact on application performance and that the "best" rate ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 25, Issue 2

June 1996

557 pages

ISSN:0163-5808

DOI:10.1145/235968

Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick

Issue’s Table of Contents

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data
June 1996
560 pages
ISBN:0897917944
DOI:10.1145/233269
Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1996

Published in SIGMOD Volume 25, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
448
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)16

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang JBalazinska MAfrati FSroka JHidders J(2016)Toward elastic memory management for cloud data analyticsProceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond10.1145/2926534.2926541(1-4)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2926534.2926541
Naeem Irfan MOriat CGroz R(2013)Model Inference and Testing10.1016/B978-0-12-408094-2.00003-5(89-139)Online publication date: 2013
https://doi.org/10.1016/B978-0-12-408094-2.00003-5
Cook JWolf AZorn B(1998)A Highly Effective Partition Selection Policy for Object Database Garbage CollectionIEEE Transactions on Knowledge and Data Engineering10.1109/69.66710010:1(153-172)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.1109/69.667100
Wang JBalazinska MAfrati FSroka JHidders J(2016)Toward elastic memory management for cloud data analyticsProceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond10.1145/2926534.2926541(1-4)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2926534.2926541
Peserico E(2013)Elastic pagingACM SIGMETRICS Performance Evaluation Review10.1145/2494232.247978141:1(349-350)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2479781
Ciucu FPoloczek FSchmitt J(2013)Sharp bounds in stochastic network calculusACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246574641:1(367-368)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465746
Sundaresan SMagharei NFeamster NTeixeira RCrawford S(2013)Web performance bottlenecks in broadband access networksACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246574541:1(383-384)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465745
Paredes-Oliva IBarlet-Ros PDimitropoulos X(2013)FaRNetACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246574341:1(355-356)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465743
Wang YTai DZhang TLu JXu BDai HLiu B(2013)Greedy name lookup for named data networkingACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246574141:1(359-360)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465741
Kwak JLee CEun D(2013)Exploiting the past to reduce delay in CSMA schedulingACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246554241:1(353-354)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465542
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents