Colloquium Speaker

Speaker:Scott Nettles
University of Arizona
Topic:Safe and Efficient Persistent Heaps
Date:Thursday, December 3, 1998
Time:9:30 am
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 9:15 am


Object-oriented databases, persistent programming languages, distributed object servers, and other systems require support for permanence of arbitrary data-types, in contrast to simple, fixed types like files or database records. Persistent heaps support the allocation, deallocation, and transactional management of arbitrary data-types that persist even in the face of machine failures; such heaps are an essential component of these new systems. Since the data they store are valuable and difficult to recreate, it is critical that persistent heaps provide maximum protection of data integrity. Such safety requirements often conflict with the need to provide high throughput, low latency access to persistent data. This conflict may lead to sacrificing safety for performance.

I will discuss some novel implementation techniques that avoid the need to sacrifice safety for performance; this work has been done in the context of Standard ML and the SML/NJ implementation. Protection of data integrity is supported by three features: transactions, which allow groups of updates to permanent data to be done atomically; garbage collection, which provides freedom from storage leaks and memory corruption due to prematurely freeing data; and orthogonal persistence, which frees the programmer from explicitly determining what data should be persistent. A new technique, concurrent replicating collection, allows the use of garbage collection without sacrificing the throughput and latency characteristics of explicit deallocation. The use of replicating collection has resulted in the first implementation of a concurrent collector for a persistent heap. Replicating collection also facilitates the efficient implementation of orthogonal persistence. I will present the results of a series of experiments that characterize the performance of my system and compare it to the performance of other systems that do not provide the same level of support for data integrity or equivalent throughput and latency.

At the end of my talk, I will briefly discuss some other recent garbage collection work, including: Oscar, a GC performance evaluation testbed; a concurrent mark-and-sweep collector for Java; and recent extensions to replicating collection that make it the first dynamic storage allocation technique suitable for multi-threaded hard real-time systems.