Garbage Collection in Distributed Value-Oriented Storage System

Abstract

The XML Store is a distributed and mobile storage system for storing XML documents, based on the value-oriented programming model. In the value-oriented programming model there is a distinction between immutable data (values) and mutable data (cells). Once stored, values (but not cells) can be freely shared, cached, replicated, distributed and migrated in XML Store. To make this transparent to clients value can only be stored, but not deleted from an XML Store by clients. Eventually, this will lead to flooding of the underlying storage media for many types of applications unless a distributed garbage collector that automatically deletes unused values is available. Therefore, incorporation of garbage collection into the XML Store is essential if it is to be of any practical use for many applications.

This master's thesis investigates the feasibility of incorporating distributed garbage collection into the XML Store. Garbage collection with emphasis on the distributed case is surveyed. A theoretical model for garbage collecting the XML Store is presented. Existing garbage collection algorithms are projected onto the XML Store and their feasibility is analyzed.

The challenge with distributed and incremental garbage collectors is that synchronization between the collectors and the user programs (also referred to as the mutators) is needed because they share data that they all are capable of updating. Even though mutators in the XML Store cannot update data, it is not of any apparent advantage to the garbage collection techniques applied to the XML Store in this thesis. Synchronization is still needed.

Design proposals for three distributed garbage collectors are presented. A collector based on a local copying collector and reference listing is implemented and evaluated. Evaluation shows that distributed garbage collection is feasible for the XML Store.

Download

Links

Plan-X project

Last updated: August 28th, 2003
Mads Pultz