John Heidemann / Research / John Heidemann's Graduate Work

From 1989 to 1995 I was a graduate student at UCLA under Gerald Popek. At UCLA I was a member of the Ficus project, where I worked on stackable filing and Ficus replication.

Stackable Filing

An image of a stackable sandwich appears here. Filing services have experienced a number of innovations in recent years, but many of these promising ideas have failed to enter into broad use. One reason is that current filing environments present several barriers to new development. For example, file systems today typically stand alone instead of building on the work of others, and support of new filing services often requires changes which invalidate existing work.

Stackable file system design addresses these issues in several ways. Complex filing services are constructed from layer ``building blocks’’, each of which may be provided by independent parties. There are no syntactic constraints to layer order, and layers can occupy different address spaces, allowing very flexible layer configuration. Independent layer evolution and development is supported by an extensible interface bounding each layer.

This summary is derived from the abstract of Heidemann94a; see that paper for more details. A list of frequently asked questions about UCLA stacking is also available.

UCLA stacking is currently in daily use for file replication and user-id mapping (see the umap layer in the Ficus documentation or the BSD 4.4 manual pages). UCLA stacking has also been used to prototype several layers in a graduate class at UCLA; see Heidemann91a, Section 6.2.2 for details.

Additional Dimensions of Stacking

My basic work in stacking was done as part of my master’s thesis. For my doctoral work I expanded in several directions.

First, I’ve replaced the SunRPC specific transport layer in the initial implementation with an more modular (but somewhat slower) implementation. This development should enable transport layers to be portable to kernels without Sun’s XDR implementation. (This work is actually not presented in the dissertation.)

Second, I’ve implement cache coherence. In a multi-layer system, data may be cached at different layers, especially if data has different representations (crypt-text and clear-text, for example), or when doing distributed filing. When data is cached in different places, a cache coherence protocol should be used to insure that updates are consistently reflected in all caches. I have designed and implemented a cache coherence system for layered filing. This work is described in a paper appearing at the 15th ACM Symposium on Operating Systems Principles Heidemann95c.

The final part of my doctoral work examines a different approach to permit very light-weight layers. Although general stacking is well suited to many applications (encryption, compression, etc.), a lighter-weight mechanism is better suited to many small services common to filing. The featherweight-layer model allows a light-weight layer to piggy-back on general-purpose layer, trading some restrictions on functionality for improved performance. Featherweight layering is well suited to provided light-weight services such as name-lookup caching, user-level locking, and VM-cache assistance. This work is described in my Ph.D. dissertation.

Ficus Replication

An image of the Ficus mascot tree appears here. Ficus is a replicated file system developed at UCLA. Distinguishing features of Ficus are:

Optimistic replication: Updates are always accepted; concurrent updates are detected after-the-fact.

Conflict resolution:

When conflicting concurrent updates are detected automatic conflict resolution attempts to resolve any differences. Concurrent updates to many file types (such a directories) can be completely or nearly resolved.

Peer-to-peer architecture: All replicas are peers in Ficus; replicas can exchange information directly without the presence of a ``server’’.

Modular construction: Ficus is built from stackable layers (described above).

These features make Ficus ideal for use in a number environments where peer-to-peer replication is important, such as:

Home Use: Imagine having a machine at home which replicates most of the environment you use in the office. While you commute, your machine at home dials into the office, pulling down any changes made that day. By the time you get home, the machine there is up to date and you can work in the evening. When you are done for the night your machine dials in to the office and reconciles changes again, uploading all of your changes. While primarily disconnected, the machine at home is functioning almost as if it were constantly connected.

Portable Notebook Computers: You are about to take a trip, so you create replicas on your laptop of all files you are likely to need. While traveling on an airplane or sitting in your hotel room, you revise your next journal paper. If you get a chance during your trip, you connect your laptop to the Internet, either by modem or a direct network connection. Once connected, your changes are automatically reflected in the office replicas while the laptop also receives changes that occurred while you were gone.

Long Distance Networking: As is the case on the Ficus project, one of the members resides on Guam where the only network connection is by long-distance telephone. However, a machine there stores replicas of key file systems. Once a week, when phone tariffs are minimum, that machine connects to UCLA to exchange modifications.

I have been involved in Ficus research and development throughout my career at UCLA. My contributions include:

Additional aspects of Ficus can be found in the Ficus web page. Important aspects of Ficus not mentioned above include:

Copyright © 1995-2016 by John Heidemann