Partition Selection Policies for Garbage Collection of an OODBMS
Dr Fred Brown
Dept. of Computer Science
University of Adelaide
Overview
Partitioned garbage collectors are designed to incrementally collect partitions
of a large object store or database. With an additional layer of software
global knowledge can be constructed in order to identify and collect
cyclic and cross partition garbage. Selecting the order in which to collect
partitions may be difficult. Cook, Zorn & Wolf have published a number
of papers on this topic which have included an analysis of different selection
policies[CWZ94]. However, their results appear to be dependent on the artificial
nature of their simulations. In collaboration with Dave Munro, also at
Adelaide University, I have attempted to repeat their experiments using
a real programming language system and have found that the selection policy
that performed best in their experiments performed worst in ours[MB00].
This project will investigate new
partition selection policies that will work in real systems and in the
presence of significant cyclic garbage.
Strategy
First we intend to construct a simulation system by tracing real applications
and using these traces to compare garbage collection implementations and
policies. Traces can be collected at different levels, the object store
interface, the object cache interface and at the virtual machine/application
level. The end result should be reproducible experiments where specific
policy effects can be isolated and measured. Access to object traces generated
by real Java and C++ applications would be very helpful, especially if
the applications were long lived and operated on some form of persistent
data.
Experiments
Initial experiments would focus on partition selection policies for use
in the PMOS garbage collector[MMH96]. PMOS is an extension of Mature Object
Space algorithm (the train algorithm)[HM92] which removes restrictions
on the order of partition collection. Dave Munro in conjunction with Eliot
Moss and Ric Hudson was responsible for extending the MOS algorithm for
use in persistent systems. Our latest implementation of PMOS uses explicit
I/O buffering and can be configured to use a number of partition selection
policies and buffer replacement algorithms. Subsequent experiments will
look at variations on the PMOS algorithm and alternative algorithms such
as the one proposed by Maheshwari and Liskov[ML97].
Experience
I have been working on object store technology, initially in the context
of persistent programming systems, since 1983. I jointly designed the Persistent
Programming Language Napier88[M88], its byte-coded virtual machine[CBC89],
and was sole designer/implementor of the underlying generic object store[BM92].
The object store is based on well defined layers and has been successfully
used in a number of other programming languages[BM92] and as a framekwork
for other object store research[M93,S97]. The object store can be easily
adapted to work with other programming languages and systems.
References
[BM92] Brown, A.L. & Morrison, R.
"A Generic Persistent Object Store", Software Engineering Journal,
Special Issue on Object-oriented Systems, Vol.7, No.2, (March 1992), 161-168.
[CBC89] Connor, R.C.H., Brown, A.L., Carrick, R., Dearle, A. & Morrison,
R.
"The Persistent Abstract Machine". 3rd International Workshop on Persistent
Object Systems, Newcastle, N.S.W., (January 1989), 80-95. In Persistent
Object Systems (Eds. J.Rosenberg & D.Koch). Springer-Verlag, 353-366.
[CWZ94] Johnathan E. Cook, Alexander L. Wolf, and Benjamin G. Zorn.
Partition selection policies in object database garbage collection.
In Proceedings of the 1994 ACM SIGMOD International Conference on Management
of Data (SIGMOD '94) (Minneapolis, MN, May 1994), pp. 371-382.
[HM92] Richard L. Hudson and J. Eliot B. Moss.
Incremental garbage collection for mature objects. In Bekkers and Cohen,
editors. In Proceedings of the International Workshop on Memory Management,
St. Malo, France, 1992. Published as number 637, Lecture Notes in Computer
Science, Springer-Verlag, 1992.
[M93] Munro, D.
On the Integration of of Concurrency, Distribution and Persistence.
PhD Thesis, University of St.Andrews, 1993.
[MBC+93] Morrison, R., Brown, A.L., Connor, R.C.H., Cutts, Q.I., Dearle,
A., Kirby, G.N.C. & Munro, D.S.
"The Napier88 Reference Manual (Release 2.0)", University of St Andrews
technical report CS/93/15, 1993.
[MB00] Munro, D.S. & Brown, A.L.
"Evaluating Partition Selection Policies using the PMOS Garbage Collector",
9th International Workshop on Persistent Object Systems, Norway, September
2000.
[ML97] Umesh Maheshwari and Barbara Liskov.
Partitioned garbage collection of a large object store. In Proceedings
of ACM SIGMOD'97, Phoenix, Arizona, 1997.
[MMH96] J. Eliot B. Moss, David S. Munro, and Richard L. Hudson.
PMOS: A complete and coarse-grained incremental garbage collector for
persistent object stores. In Proceedings of the 7th International Workshop
on Persistent Object Systems, pp. 140-150, Morgan Kaufmann, 1996.
[S97] Scheuerl, S J G.
Modelling Recovery in Database Systems. PhD Thesis, University of St.Andrews,
1997.