Umesh Maheshwari
Barbara Liskov
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.
- AFFS95 L. Amsaleg, R Ferreira, M. Franklin, and M. Shapiro. Evaluating garbage collection for large persistent stores. In Addendum to Proc. 1995 OOPSLA Workshop on Object Database Behavior. ACM Press, 1995.Google Scholar
- AGF95 L. Amsaleg, O. Gruber, and M. Franklin. Efficient incremental garbage collection for workstation-server database systems. In Proc. 21st VLDB. ACM Press, 1995. Google ScholarDigital Library
- Bak78 H.G. Baker. List processing in real-time on a serial computer. CACM, 21(4):280-94, 1978. Google ScholarDigital Library
- Bak93 H. G. Baker. 'Infant mortality' and generational garbage collection. ACM SIGPLAN Notices, 28(4), 1993. Google ScholarDigital Library
- Bis77 P. B. Bishop. Computer systems with a very large address space and garbage collection. Technical Report MIT/LCS/TR- 178, MIT, 1977.Google Scholar
- CKWZ96 J. E. Cook, A. W. Klauser, A. L. Wolf, and B. G. Zorn. Semi-automatic, self-adaptive control of garbage collection rates in object databases. In Proc. 1996 SIGMOD. ACM Press, 1996. Google ScholarDigital Library
- CWZ94 J.E. Cook, A. L. Wolf, and B. G. Zorn. Partition selection policies in object databases garbage collection. In Proc. 1994 SIGMOD. ACM Press, 1994. Google ScholarDigital Library
- FS96 P. Ferreira and M. Shapiro. Larchant: Persistence by reachability in distributed shared memory through garbage collection. In Proc. 16th ICDCS, 1996. Google ScholarDigital Library
- Ghe95 S. Ghemawat. The Modified Object Buffer: A Storage Management Technique for Object-Oriented Databases. PhD thesis, Massachusetts Institute of Technology, 1995. Google ScholarDigital Library
- HM92 R. L. Hudson and J. E. B. Moss. Incremental garbage collection for mature objects. In Proc. IWMM, volume 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992. Google ScholarDigital Library
- Hug85 R. J. M. Hughes. A distributed garbage collection algorithm. In Proc. 1985 FPCA, volume 201 of Lecture Notes in Computer Science, pages 256-272. Springer-Verlag, 1985. Google Scholar
- JJ92 N.-C. Juul and E. Jul. Comprehensive and robust garbage collection in a distributed system. In Proc. IWMM, volume 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992. Google ScholarDigital Library
- KW93 E. K. Kolodner and W. E. Weihl. Atomic incremental garbage collection and recovery for large stable heap. In Proc. 1993 SIGMOD, pages 177-186, 1993. Google ScholarDigital Library
- LAC+96 B. Liskov, A. Adya, M. Castro, M. Day, S. Ghemawat, R. Gruber, U. Maheshwari, A. Myers, and L. Shrira. Safe and efficient sharing of persistent objects in Thor. In Proc. 1996 SIGMOD, pages 318--329. ACM Press, 1996. Google ScholarDigital Library
- LGG+91 B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams. Replication in the Harp file system. In Proc. SOSP, pages 226-238. ACM Press, 1991. Google ScholarDigital Library
- LL92 R. Ladin and B. Liskov. Garbage collection of a distributed heap. In Proc. International Conference on Distributed Computing Systems. IEEE Press, 1992.Google ScholarCross Ref
- LMN96 B. Liskov, U. Maheshwari, and T. Ng. Partitioned garbage collection of a large stable heap. In Proc. IWO00S, 1996. Google ScholarDigital Library
- LQP92 B. Lang, C. Queinniec, and J. Piquer. Garbage collecting the world. In Proc. POPL '92, pages 39-50. ACM Press, 1992. Google ScholarDigital Library
- ML94 U. Maheshwari and B. Liskov. Fault-tolerant distributed garbage collection in a client-server object-oriented database. In Proc. 3rd Parallel and Distributed Information Systems. IEEE Press, 1994. Google ScholarDigital Library
- ML95 U. Maheshwari and B. Liskov. Collecting cyclic distributed garbage by controlled migration. In Proceedings of PODC'95 Principles of Distributed Computing, pages 57-63, 1995. Google ScholarDigital Library
- MMH96 J. E. B. Moss, D. S. Munro, and R. L. Hudson. Pmos: A complete and coarse-grained incremental garbage collector for persistent object stores. In Proc. 7th Workshop on Persistent Object Systems, 1996.Google Scholar
- Ng96 T. Ng. Efficient garbage collection for large object-oriented databases. Technical Report MIT/LCS/TR-692, MIT LCS, 1996. Google ScholarDigital Library
- ONG93 J.W. O'Toole, S. M. Nettles, and D. Gifford. Concurrent compacting garbage collection of a persistent heap. In Proc. 14th SOSP, pages 161-174, 1993. Google ScholarDigital Library
- SGP90 M. Shapiro, O. Gruber, and D. Piainfoss6. A garbage detection protocol for a realistic distributed object-support system. Rapports de Recherche 1320, iNRIA-Rocquencourt, 1990.Google Scholar
- Sob88 R Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Technical Report AITR- 1417, MIT, AI Lab, 1988. Google ScholarDigital Library
- Ung84 D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIG- PLAN Notices, 19(5):157-167, 1984. Google ScholarDigital Library
- YNY94 V. Yong, J. Naughton, and J. Yu. Storage reclamation and reorganization in clinet-server persistent object stores. In Proc. Data Engineering, pages 120-133. IEEE Press, 1994. Google Scholar
Index Terms
- Partitioned garbage collection of a large object store
Recommendations
Partitioned garbage collection of a large object store
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of dataWe 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 ...
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 applicationsModern 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