Sprite Reterospective (original) (raw)

A Brief Retrospective on the Sprite Network Operating System

John Ousterhout Computer Science Division Department of EECS University of California at Berkeley

Sprite is a research operating system whose development I have had the pleasure of leading over the last eight years. Four graduate students and I started the project in the Fall of 1984 because we felt that current operating systems were paying insufficient attention to local-area networks. It seemed to us that networking support had been added in a quick and dirty fashion to systems that were designed to run stand-alone. As a result, networked workstations didn't work well together. At the time we started Sprite there were no good network file systems (even NFS didn't exist yet) and administering a network of workstations was a nightmare.

Our goal for Sprite was to "do networking right" by building a new operating system kernel from scratch and designing the network support into the system from the start. We hoped to create a system where a collection of networked workstations would behave like a single system with both storage and processing power shared uniformly among the workstations. We hoped that users would be able to tap the power of the entire network while preserving the simple behavior and administrative ease of a traditional time-shared system.

I think that we achieved these goals. Four technical accomplishments stand out in my mind. First and foremost is Sprite's network file system, which demonstrated that network file systems can provide a convenient user model without sacrificing performance. Sprite's file system allows file sharing while completely hiding the network. It provides the same behavior among workstations that users would see if they all ran on a traditional time-sharing system. Even I/O devices can be accessed unformly across the network, and user processes can extend the file system by implementing its I/O and naming protocols using pseudo devices and pseudo file systems. At the same time, Sprite uses aggressive file caching to achieve high performance. Five years after its construction, Sprite still has the fastest network file system in existence.

Sprite's second key accomplishment is its process migration mechanism, which allows processes to be moved transparently between workstations at any time. With process migration a single user can harness the power of many workstations simultaneously, achieving speedups of four or more on common system tasks such as recompilation. The migration mechanism keeps track of idle machines, uses them for migration, and evicts migrated processes when a workstation's owner returns, so that migration doesn't impact the response time of active users. Evicted processes are remigrated to a different idle machine or executed on their home machine. Sprite is one of only a few systems where process migration has been used on a day-to-day basis by a large user community.

Sprite's third key accomplishment is its single system image. The file system and process migration provide the most obvious evidence of the single system image, since they make storage and processing power sharable among workstations. But in many other ways Sprite looks and feels just like a single system. There is one root partition, one password file, one swap area (in the network file system), one login database, and so on. The "finger" command tells about all users on all workstations in the Sprite cluster, not just those on the workstation where the command was invoked. System administration is no harder with fifty machines in the network than it is with ten, and adding a new machine is no more difficult than adding a new user account.

Sprite's single system image also supports different machine architectures in the same cluster. We developed a framework for separating architecture- independent information from architecture-specific information. All the information for all architectures is visible at all times, which simplifies cross-development, yet each machine uses the appropriate architecture- dependent information when it is needed.

Sprite's fourth key accomplishment is its log-structured file system (LFS), which demonstrates a radical new approach to file system design. LFS treats the disk more like a tape, writing information sequentially in large runs that permit great efficiency. We developed a new garbage collection mechanism that continually opens up large extents of free space on the disk. The result is a system that writes small files to disk an order of magnitude faster than any other existing file system. At the same time it handles other operations, such as reads and large writes, at least as well as other systems. Log-structured file systems have many other advantages as well, such as fast crash recovery, the ability to store information on disk in compressed form, and the ability to vary the block size from file to file.

In addition to the above results, which have already been achieved, there are several promising projects still underway, such as recovery enhancements, a new file system called Zebra that stripes files across multiple servers, and high-bandwidth file service using disk arrays. Before the Sprite project ends I expect to see major results from each of these projects too.

Throughout the Sprite project we have tried to characterize the behavior of the system and to use this information to guide future developments. Some of our most important results are the measurements we have made. The founding of the project was based in part on file system measurements made on time-shared systems in 1984 and 1985. We made additional measurements of Sprite usage in 1991 to see how patterns had changed and to analyze the potential application of non-volatile memory in networked systems.

Perhaps the most significant accomplishment of all is that we were able to make the system work, not just for ourselves but for a community of users that numbered as high as 80 or more at the peak of the project. Many of these users depended on Sprite for all of their day-to-day computing needs, such as mail and printing. For a period of several years it was common to see 25-35 simultaneous logins of which only a half-dozen were Sprite developers. I know of only one other university project that developed a new operating system kernel from scratch and used it to support a user community this large for this long; that project was Multics, which was carried out at MIT in the late 1960's.

Furthermore, we built Sprite (more than 200,000 lines of new code in all) with a small team that averaged only about four graduate students and one or two staff or undergraduate assistants. We never got too large to have project meetings in my office, although there were times when we had to borrow two additional chairs to supplement the six already in my office.

The history of Sprite divides into roughly three phases: initial development, consolidation and LFS development, and new ventures and closeout.

The first phase of Sprite, initial development, lasted from the founding of the project in the fall of 1984 until about the end of 1987. We began coding on Sun-2 workstations in early 1985 and had a system that could execute shell commands by the spring of 1986. In the summer of 1986 we started developing the "real" Sprite file system (we'd used an older network file system called BNFS up until that point). About that time we also started on process migration and porting the X window system. By the fall of 1987 all of these things were working, along with an internet protocol sever. We had also ported Sprite to Sun-3's. At this point we copied the kernel sources over to Sprite and began doing all of our kernel development on Sprite itself.

The second phase in Sprite's history lasted from late 1987 to late 1990. This phase consisted mostly of consolidation. In early 1988 we made a major revision of the file system. Remote device support was improved, the pseudo device implementation was rewritten, and a simple recovery protocol was introduced so the system could recover gracefully from server crashes. Process migration underwent major improvements also, and by late 1988 it became stable enough for us to use it daily in system development. In 1988 we ported Sprite to the SPUR research multiprocessor (the SPUR project provided much of the early funding for Sprite), and in 1989 we ported it to DECstation-3100 and Sun-4 platforms. A port to the Sequent Symmetry machine was carred out at Sequent in late 1989 and early 1990.

In late 1988 we began to support users other than Sprite developers. The user community gradually grew in size, peaking at around 80 in 1990 and 1991. We also prepared a distribution tape so that we could make Sprite available to people outside Berkeley. The first tapes were sent out in late 1989; over the life of the project Sprite has run at about ten different sites.

The most significant new development during Sprite's second phase was the LFS implementation. We made preliminary designs and studies in 1988 but didn't solidify the prototype design until 1989 (as part of the newly started RAID project). Coding started in late 1989. By the spring of 1990 LFS was showing signs of life, and it entered production use in the fall of 1990. By late 1991 virtually all of Sprite's dozen disks were using LFS.

The final phase of the project started in late 1990 and will continue until Sprite shuts down in late 1993 or early 1994. In this phase we initiated several new projects, most of which reflected the increasing focus of the project on issues related to storage management. In the winter of 1990 we began to analyze the behavior of recovery after file server crashes; this led to a series of experiments with better recovery techniques, such as server-driven recovery and the use of non-volatile storage. In 1991 we began a project to see if Sprite could be re-implemented as a user-level server process running under the Mach 3.0 kernel; this project completed in the summer of 1992 with substantial functionality but disappointing performance. In 1991 and 1992 we also developed the Jaquith tape library system, which made robotically-controlled tape systems available for both Sprite and other UNIX systems. During the same period we started projects to experiment with striping files across multiple file servers (Zebra) and to improve the bandwidth of remote accesses to disk arrays. Both of these projects are still underway.

Like most software, the Sprite kernel became harder and harder to maintain as it aged. Frequent revisions and changes in project personnel led to increases in system complexity, in spite of our best efforts to keep things clean and simple. In addition, we found it harder and harder to keep up with developments in commercial operating systems. By 1990 there were several commercial versions of UNIX with massive support teams, such as System V, Solaris, and OSF. These systems were adding features at a rapid pace and our users wanted access to these features under Sprite. We added new features such as shared libraries and binary compatibility with SunOS and Ultrix, but we found ourselves spending more and more time on tasks that were not research oriented.

At the end of 1991 we decided to bring the Sprite project to a gradual close. Since then we have not started any major new developments and no new graduate students have joined the project. We plan to complete the projects that are currently underway and then shut down the system in late 1993 or early 1994. We no longer encourage new users to work on Sprite, and our user community is slowly shrinking back to just the Sprite team. Sprite has served us long and well as a research vehicle; now it is time to move on to other things.

Many people have contributed to Sprite over the years. I can't possibly hope to list every significant contribution, but I'll try anyway. The list below summarizes the work of the principal project members (my research students and the staff who reported directly to me). The people are listed in chronological order by the date when they started working on Sprite-related things, and the projects are listed with the most important ones (in my opinion) first.

Bob Beck (Sequent port), Ann Chervenak (device drivers), Doug Johnson (SPUR debugging), Ed Lee (RAID striping driver), Dean Long (kernel bug fixing, bootstrapping, SPARCstation port), Ethan Miller (RAID controller support) , Srinivasan Seshan (Ultranet support), Thorsten Von Eicken (X11R4 port), Jay Vosburgh (Sequent port).