Design and Evaluation of Algorithms for Storage Reclamation in Object Databases

点击翻译按钮获取中文摘要

A problem for an object database management system (ODBMS) is the reclamation of storage for persistent, secondary-memory objects that are no longer accessible. Although excellent reclamation algorithms have been developed for transient, primary-memory objects, these algorithms have been shown to be inappropriate for use on secondary-memory objects in object databases. This project investigates new algorithms for ODBMS storage reclamation. The critical aspects of secondary-memory reclamation are teased apart into a set of distinct policy areas. Rigorous trace-driven simulations of the algorithms are performed to gain an understanding of the relative performance of alternative policies within each area as well as an understanding of the interplay of policies across areas. Prototype implementations of the most promising algorithms are integrated into an existing ODBMS. This project makes three primary contributions to the ODBMS research, development, and user communities. First, a set of new reclamation algorithms appropriate for object databases is defined. Second, performance evaluations of the algorithms are used to reveal the circumstances under which the algorithms should be considered for adoption within a particular ODBMS or application. Third, a catalog of benchmark and live-application traces is created to establish an empirically founded characterization of application behavior that can be used far beyond evaluation of reclamation algorithms.