PERFORMANCE EVALUATION OF OPTIMISTIC REPLICATED FILE SYSTEMS

Thomas W. Page, Jr.
Department of Computer and Information Science
The Ohio State University

Contact Information

2015 Neil Avenue
Department of Computer and Information Science
The Ohio State University
Columbus, OH 43210
Phone: (614) 292-5835
Fax : (614) 292-2911
Email: page@cis.ohio-state.edu

WWW PAGE

Project URL

Keywords

replicated, file system, optimistic replication, concurrency control, distributed file system

Project Award Information

Award Number: IRI-9501812
Duration: 3rd year
Title: PERFORMANCE EVALUATION OF OPTIMISTIC REPLICATED FILE SYSTEMS

Project Summary

Replication is key to achieving performance and fault tolerance in widely distributed systems. Conservative replica management schemes do not scale well, yet optimistic approaches depend in complex ways on workload, architecture, topology, and failure modes of the system. This research captures the design space for optimistically replicated systems in a flexible, object-oriented, simulation model, allowing alternative architectures to be evaluated on a "level playing field." The object-oriented nature allows specialization of model components, permitting experimentation with alternative designs, communications bandwidths, failure distributions, workload models, etc. A flexible workload generation tool which can be tuned to produce synthetic traces matching the statistical properties of various anticipated environments is also produced. The simulation and synthetic trace generator are validated by comparison with analytical models and measurements of real systems.

This research will enable designers of a broad range of distributed database and filing systems to assess the impact of an optimistic approach to achieving high performance and availability in large scale systems.

The educational plan seeks to add a "hands-on", experimental component to the operating systems curriculum. Synchronization, scheduling, and concurrency control simulation labs are constructed and piloted using the same object-oriented simulation methodology as in the research plan. This provides a balance to the current theoretical approach to teaching operating systems to both undergraduate and graduate students.

Goals, Objectives, and Targeted Activities

A simple model of a replicated file system has been completed. We have derived an analytical solution to this model which allows us to predict the mean time between conflicting updates to a replicated object, assuming that updates result from an exponential arrival process. As the occurrence of arrivals is significantly more bursty than an exponential process will generate, we have also developed a simulation of the model which can be driven by various workloads, including a results of a synthetic trace generator that we developed and actual trace data. This model has allowed us to run a variety of experiments to determine how the occurrence of conflicts is affected by varying the update traffic, update propagation strategy, and number of replicas. However, this model is too simplistic in that it ignores node and network failures and the effects of realistic replica selection policies.

Consequently, we have devolved a new model, with sufficient detail to handle network partitions and realistic replica selection policies. With this new model, we are in the process of conducting experiments which, among other things compares the replica selection strategies of Ficus and Coda.

Indication of Success

We have carried out measurements of the Ficus Optimistically Replicated File System and published the results in the Software Practice and Experience paper referenced below.
We have built a synthetic file system trace generator and validated it against actual trace data. This work is published in the ACM TOMACS paper referenced below.
We have built a simple simulation model of an optimistically replicated file system. This model is described in the TOMACS paper and is used to evaluate the synthetic workload generator. It is, however, too simplistic to be used to draw meaningful conclusions about optimistic replication.
A more sophisticated replicated file system model has been developed and is currently being simulated. Results from this model will be available shortly.

Project Impact

This project has supported one graduate student, Peter Ware, who will likely graduate with a PhD in 1998. He has developed the object oriented simulation package and participated in developing the synthetic workload generator and its evaluation. Five other grad students have participated in aspects of the project.
We have integrated hands on simulation into the undergraduate operating systems curriculum as proposed. The use of simulation to teach synchronization concepts including semaphores has been very successful and is now in use by all OS instructors at OSU.
We have developed and twice piloted a course on distributed system security.
We have developed and twice taught a new course on distributed file systems. Students did hands on development, benchmarking, and simulation projects.
An indication of the impact of our work on Ficus in industry can be found in the following quote. In the article ``Inside Microsoft Research'' in Jan. '98 IEEE Computer a paragraph towards the end reads: "Instead of having programmers pass hints to the operating system, asks Richard Draves, a researcher on the Millennium project, can the OS monitor applications and hardware? The OS could then reconfigure the system as needed into tightly coupled object clusters, intelligently moving objects within the system to enhance performance and efficiency. Although this may seem a tall order, the MSR group takes heart in the success of the Ficus and Seer projects at UCLA, which are developing a distributed file system with networked transparent file naming and automated, predictive file caching, as well as other recent work on self-tuning file systems."

Project References

"Perspectives on Optimistic Peer-to-Peer Distributed Filing," Page, Guy, Popek, Heidemann, Kuenning, Journal of Software Practice and Experience, 1998, in press.

"Modeling a Two-level Arrival Process, With Applications to Computer Performance Simulation," P. Ware, T. Page, B. Nelson, ACM Transactions on Modeling and Computer Simulation, 1998, accepted pending final editor review.

"Modeling File-System Input Traces Via a Two-level Arrival Process," P. Ware, T. Page, B. Nelson, Proceedings of the 1996 Winter Simulation Conference, Dec. 1996

"Consistency Algorithms for Optimistic Replication," R. Guy, G. Popek, T. Page, Proceedings of the 1st IEEE International Conference on Network Protocols Oct. 1993.

Area Background

When a replicated object is updated, that update must first be applied to one of the replicas, and then knowledge of that update propagated to all other replicas to restore mutual consistency. If a second update occurs before the first has completed propagating to all replicas, that second update may be applied to a replica which knows of the first, or to one that does not. In the former case, all is well; there are then as many as three different versions of the object in the system, but the versions are totally ordered, and propagation of the "dominant" copy will restore the system to consistency. However, the latter case results in an only partially ordered set of replicas and a situation in which the system cannot converge to consistency without intervention. This is known as a conflict.

Traditional methods prevent conflicts by restricting updates to only up-to-date replicas. However, determining which replica is up-to-date requires expensive communications and locking, and often results in unacceptable loss of update availability. Therefore, optimistic approaches have been developed which detect rather than prevent conflicting updates. Optimism is based on the premise, "Why take expensive measures to prevent an outcome which is very unlikely, and from which the system could recover, albeit with some cost." This research is aimed at evaluating just how frequent or infrequent conflicts truly are, and hence the applicability of optimistic replica management.

Area References

"Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types," Maurice Herlihy ACM Transactions on Database Systems, 15(1), March 1990, pp. 96-124.

"Implementation of the {Ficus} Replicated File System," Richard G. Guy, John S. Heidemann, Wai Mak, Thomas W. Page, Jr., Gerald J. Popek, Dieter Rothmeier. Proceedings of the Usenix Conference, June, 1990, pp. 63-71.

"Coda: A Highly Available File System for a Distributed Workstation Environment," Mahadev Satyanarayanan, James J. Kistler, Puneet Kuma, Maria E. Okasaki, Ellen H. Siegel, David C. Steere, IEEE Transactions on Computers, 39(4), April 1990, pp. 447-459.