Spriteネットワークオペレーティングシステムの簡単な回顧録

Spriteネットワークオペレーティングシステムに関する簡単な回顧

John Ousterhout
コンピュータサイエンス部門
EECS学科
カリフォルニア大学バークレー校

Spriteは、私が過去8年間にわたり開発を率いる機会に恵まれた研究用オペレーティングシステムです。4人の大学院生と私は、当時のオペレーティングシステムがローカルエリアネットワークに十分な注意を払っていないと感じたため、1984年秋にこのプロジェクトを開始しました。私たちにとって、ネットワーキングサポートは、スタンドアロンで動作するように設計されたシステムに、場当たり的に追加されたもののように見えました。その結果、ネットワーク化されたワークステーションはうまく連携しませんでした。Spriteの開発を開始した当時、優れたネットワークファイルシステムは存在せず（NFSさえまだ存在していませんでした）、ワークステーションのネットワークを管理するのは悪夢でした。

Spriteの目標は、オペレーティングシステムカーネルを一から構築し、システム設計の初期段階からネットワークサポートを組み込むことで、「ネットワーキングを正しく行う」ことでした。私たちは、ネットワーク化されたワークステーションの集合が、ストレージと処理能力の両方がワークステーション間で均一に共有される単一システムのように動作することを期待しました。ユーザーは、従来のタイムシェアシステムのような単純な動作と管理の容易さを維持しながら、ネットワーク全体のパワーを活用できるようになることを望んでいました。

これらの目標は達成できたと私は考えています。私の心に残る4つの技術的成果があります。まず最も重要なのは、Spriteのネットワークファイルシステムです。これは、ネットワークファイルシステムがパフォーマンスを犠牲にすることなく、便利なユーザーモデルを提供できることを実証しました。Spriteのファイルシステムは、ネットワークを完全に隠蔽しながらファイル共有を可能にします。これは、ユーザーが従来のタイムシェアリングシステムで経験するのと同じ動作をワークステーション間で提供します。I/Oデバイスでさえネットワーク全体で均一にアクセスでき、ユーザープロセスは擬似デバイスと擬似ファイルシステムを使用してI/Oおよび命名プロトコルを実装することで、ファイルシステムを拡張できます。同時に、Spriteは積極的なファイルキャッシングを使用して高いパフォーマンスを実現しています。構築から5年後、Spriteは依然として現存する中で最も高速なネットワークファイルシステムを持っています。

Spriteの2番目の主要な成果は、プロセス移行メカニズムです。これにより、プロセスはいつでもワークステーション間で透過的に移動できます。プロセス移行により、単一のユーザーは複数のワークステーションのパワーを同時に活用し、再コンパイルなどの一般的なシステムタスクで4倍以上の高速化を達成できます。移行メカニズムは、アイドル状態のマシンを追跡し、それらを移行に使用し、ワークステーションの所有者が戻ってきたときに移行されたプロセスを追い出します。これにより、移行はアクティブなユーザーの応答時間に影響を与えません。追い出されたプロセスは、別のアイドルマシンに再移行されるか、ホームマシンで実行されます。Spriteは、大規模なユーザーコミュニティによって日常的にプロセス移行が使用されている数少ないシステムの一つです。

Spriteの3番目の主要な成果は、シングルシステムイメージです。ファイルシステムとプロセス移行は、ストレージと処理能力がワークステーション間で共有可能になるため、シングルシステムイメージの最も明白な証拠となります。しかし、Spriteは他の多くの方法でも単一システムのように見え、感じられます。ルートパーティションは1つ、パスワードファイルは1つ、スワップ領域（ネットワークファイルシステム内）は1つ、ログインデータベースは1つ、といった具合です。「finger」コマンドは、コマンドが実行されたワークステーションだけでなく、Spriteクラスタ内のすべてのワークステーションの全ユーザーに関する情報を提供します。50台のマシンがあるネットワークでも、10台のマシンがある場合よりもシステム管理は難しくなく、新しいマシンを追加することは新しいユーザーアカウントを追加するよりも難しくありません。

Spriteのシングルシステムイメージは、同じクラスタ内で異なるマシンアーキテクチャをサポートすることも可能にします。アーキテクチャに依存しない情報とアーキテクチャ固有の情報を分離するためのフレームワークを開発しました。すべてのアーキテクチャに関するすべての情報は常に表示されるため、クロス開発が簡素化されますが、各マシンは必要に応じて適切なアーキテクチャ固有の情報を使用します。

Spriteの4番目の主要な成果は、ログ構造ファイルシステム（LFS）です。これは、ファイルシステム設計に対する根本的に新しいアプローチを示しています。LFSは、ディスクをテープのように扱い、効率を大幅に向上させる大きな連続ブロックに情報を書き込みます。ディスク上の大きな空き領域を継続的に解放する新しいガベージコレクションメカニズムを開発しました。その結果、他の既存のファイルシステムよりも1桁高速に小さなファイルをディスクに書き込むシステムが生まれました。同時に、読み取りや大きな書き込みなどの他の操作も、他のシステムと同等以上に処理します。ログ構造ファイルシステムには、高速なクラッシュリカバリ、ディスク上の情報を圧縮形式で保存できること、ファイルごとにブロックサイズを変更できることなど、他の多くの利点もあります。

上記の結果に加えて、回復機能の強化、複数のサーバーにファイルをストライピングする新しいファイルシステムであるZebra、ディスクアレイを使用した高帯域幅ファイルサービスなど、いくつかの有望なプロジェクトが現在進行中です。Spriteプロジェクトが終了する前に、これらの各プロジェクトから主要な結果が得られると予想しています。

Spriteプロジェクト全体を通して、システムの動作を特徴づけ、その情報を使用して将来の開発を導くように努めてきました。私たちの最も重要な成果の一部は、私たちが収集した測定データです。プロジェクトの設立は、1984年と1985年に行われたタイムシェアシステムでのファイルシステム測定に部分的に基づいています。1991年にはSpriteの使用状況に関する追加測定を行い、パターンがどのように変化したかを確認し、ネットワークシステムにおける不揮発性メモリの応用可能性を分析しました。おそらく最も重要な成果は、システムを機能させることができたことです。私たち自身のためだけでなく、プロジェクトのピーク時には80人以上に達したユーザーコミュニティのためにも機能しました。これらのユーザーの多くは、メールや印刷など、日常のコンピューティングニーズすべてをSpriteに依存していました。数年間にわたり、Sprite開発者はわずか半ダース程度でしたが、同時に25〜35のログインが見られるのは一般的でした。私が知る限り、新しいオペレーティングシステムカーネルを一から開発し、それをこの規模のユーザーコミュニティにこれほど長くサポートした大学プロジェクトは、1960年代後半にMITで行われたMulticsプロジェクト以外にはありません。

さらに、Sprite（合計20万行以上の新しいコード）を、平均して約4人の大学院生と1〜2人のスタッフまたは学部アシスタントからなる小規模なチームで構築しました。プロジェクト会議が私のオフィスで行えなくなるほど大きくなることはありませんでしたが、オフィスにあった6つの椅子に加えて、2つの追加の椅子を借りなければならない時期もありました。

Spriteの歴史は、大まかに3つのフェーズに分けられます。初期開発、統合とLFS開発、そして新しい取り組みと終結です。

Spriteの最初のフェーズである初期開発は、1984年秋のプロジェクト開始から1987年末頃まで続きました。1985年初頭にSun-2ワークステーションでコーディングを開始し、1986年春にはシェルコマンドを実行できるシステムが完成しました。1986年夏には、「実際の」Spriteファイルシステムの開発を開始しました（それまではBNFSという古いネットワークファイルシステムを使用していました）。同時期に、プロセス移行とXウィンドウシステムの移植も開始しました。1987年秋までには、これらのすべてがインターネットプロトコルサーバーとともに機能していました。また、SpriteをSun-3にも移植しました。この時点でカーネルソースをSpriteにコピーし、カーネル開発のすべてをSprite自体で行うようになりました。

Spriteの歴史における2番目のフェーズは、1987年末から1990年末まで続きました。このフェーズは主に統合から成りました。1988年初頭にファイルシステムの大幅な改訂を行いました。リモートデバイスサポートが改善され、擬似デバイスの実装が書き直され、サーバークラッシュから正常に回復するための簡単な回復プロトコルが導入されました。プロセス移行も大幅に改善され、1988年末までにはシステム開発で日常的に使用できるほど安定しました。1988年にはSpriteをSPURリサーチマルチプロセッサ（SPURプロジェクトはSpriteの初期資金の多くを提供しました）に移植し、1989年にはDECstation-3100およびSun-4プラットフォームに移植しました。Sequent Symmetryマシンへの移植は、1989年末から1990年初頭にかけてSequentで行われました。

1988年末に、Sprite開発者以外のユーザーをサポートし始めました。ユーザーコミュニティは徐々に規模を拡大し、1990年と1991年には約80人に達しました。また、Berkeley外の人々がSpriteを利用できるように配布テープを準備しました。最初のテープは1989年末に発送されました。プロジェクトの全期間を通じて、Spriteは約10の異なるサイトで実行されました。

Spriteの第2フェーズにおける最も重要な新しい開発は、LFSの実装でした。1988年に予備的な設計と調査を行いましたが、プロトタイプの設計が固まったのは1989年（新しく開始されたRAIDプロジェクトの一部として）でした。コーディングは1989年末に開始されました。1990年春までにはLFSは稼働の兆しを見せ、1990年秋に本番運用に入りました。1991年末までには、Spriteのディスクのほぼすべて（12台以上）がLFSを使用していました。

プロジェクトの最終フェーズは1990年末に始まり、Spriteが1993年末または1994年初頭にシャットダウンされるまで続きます。このフェーズでは、ストレージ管理に関連する問題へのプロジェクトの関心の高まりを反映したいくつかの新しいプロジェクトを開始しました。1990年冬には、ファイルサーバークラッシュ後の回復動作の分析を開始しました。これは、サーバー主導の回復や不揮発性ストレージの使用など、より良い回復技術に関する一連の実験につながりました。1991年には、SpriteをMach 3.0カーネル上で動作するユーザーレベルのサーバープロセスとして再実装できるかどうかを調べるプロジェクトを開始しました。このプロジェクトは、実質的な機能はあったものの、パフォーマンスは期待外れで、1992年夏に完了しました。1991年と1992年には、Spriteおよび他のUNIXシステムでロボット制御のテープシステムを利用可能にするJaquithテープライブラリシステムも開発しました。同時期に、複数のファイルサーバーにファイルをストライピングする（Zebra）実験プロジェクトや、ディスクアレイへのリモートアクセス帯域幅を改善するプロジェクトも開始しました。これらのプロジェクトはどちらも現在進行中です。

ほとんどのソフトウェアと同様に、Spriteカーネルは年を経るにつれて保守が困難になりました。頻繁な改訂とプロジェクト担当者の変更は、物事をクリーンでシンプルに保つための最善の努力にもかかわらず、システムの複雑さを増大させました。さらに、商用オペレーティングシステムの開発に追いつくのがますます困難になりました。1990年までには、System V、Solaris、OSFなど、大規模なサポートチームを持つ商用UNIXバージョンがいくつかありました。これらのシステムは急速に機能を追加しており、ユーザーはSpriteの下でこれらの機能にアクセスしたいと考えていました。共有ライブラリやSunOSおよびUltrixとのバイナリ互換性などの新機能を追加しましたが、研究指向ではないタスクに費やす時間が増加していることに気づきました。

1991年末、Spriteプロジェクトを段階的に終了することを決定しました。それ以来、主要な新規開発は開始しておらず、新しい大学院生もプロジェクトに参加していません。現在進行中のプロジェクトを完了し、1993年末または1994年初頭にシステムをシャットダウンする予定です。もはや新しいユーザーにSpriteでの作業を推奨しておらず、ユーザーコミュニティはゆっくりとSpriteチームのみに戻りつつあります。Spriteは研究用車両として長く、そしてうまく機能しました。今こそ、他のことに移る時です。

長年にわたり、多くの人々がSpriteに貢献してきました。すべての重要な貢献をリストアップすることは不可能かもしれませんが、それでも試みます。以下のリストは、主要なプロジェクトメンバー（私の研究学生と私に直接報告していたスタッフ）の作業をまとめたものです。人々は、Sprite関連の作業を開始した日付順にリストされ、プロジェクトは（私の意見では）最も重要なものから順にリストされています。

Brent Welch（1984年夏 - 1990年春）：
RPC（リモートプロシージャコール）、ファイルシステム（ストレージマネージャー、ファイルシステムスイッチ、プレフィックス、名前解決、リモートデバイス、クラッシュリカバリプロトコル、ディスクフォーマット、ダンプとリストア、移行サポート）、擬似デバイス、擬似ファイルシステム、BNFSファイルシステム、NFSサポート、デバイスドライバ、カーネルプロファイリング、ブートストラップ。

Andrew Cherenson（1984年秋 - 1987年秋）：
インターネットプロトコルサーバー、ウィンドウシステム設計とX10ポート、タイマー、シリアルインターフェース、ユーザーレベルデバッグ、擬似デバイス、initプロセス、コマンドポート（ネットワークコマンド、ログイン）、プロセス関連システムコール、UNIX互換性、マニュアルエントリフォーマット、Cライブラリ。

Fred Douglis（1984年秋 - 1990年秋）：
プロセス移行とpmakeプログラム、UNIX互換性とコマンドポート、システムコールインターフェース、同期、スケジューリング、プロセスサポート、emacsやtexなどの主要プログラムのポートとサポート、SPURのトラップ処理とUARTサポート、ログ構造ファイルシステムの初期設計作業、光ディスクの実験。

Mike Nelson（1984年秋 - 1988年秋）：
仮想メモリ、ファイルシステム（キャッシング、ディスクチェッカー、VM連携、移行サポート、クラッシュリカバリ、select）、カーネルデバッグ、Sun-3およびDECstation-3100ポート、デバイスおよびネットワークドライバ、シグナル処理、SPURポート（仮想メモリ、トラップハンドラなど）、コマンドポート。

John Ousterhout（1984年秋 - ??）：
メモリ割り当て、Cライブラリ、端末ドライバ、コンテキストスイッチ、gccポート、mkmfプログラム。

Adam de Boor（1986年秋 - 1988年夏）：
Pmakeプログラム、X11ポート（例：デバイスドライバと領域コード）、xmanおよびmkmfプログラム、swatデバッガ。

Mendel Rosenblum（1988年冬 - 1992年秋）：
ログ構造ファイルシステム、SPURポート、デバッグツール、ディスクドライバ、Sun-4ポート、X11R4ポート。

Mary Baker（1988年冬 - ??）：
回復分析と再設計、RPCの輻輳制御、リカバリボックス、Sun-4、SPARCstation、SPARCstation-2ポート、ファイルシステム測定、NVRAM使用分析、RPCバイトスワッピング、SCSIデバイスドライバ、マルチプロセッサ変換。

Bob Bruce（1988年秋 - 1990年秋、1991年秋 - 1992年冬）：
スプーラーデーモン、ダンプおよびリストアユーティリティ、Sprite配布テープ、コンパイルおよびデバッグツールのサポート、ユーザーレベルプロファイリング、浮動小数点サポート、DECstation-3100およびSequentポート、UNIX互換性、Operation Desert Stormサポート、X11R5ポート。

John Hartman（1988年秋 - ??）：
Zebraストライプファイルシステム、ファイルシステム測定、SPURマルチプロセッサへのポート、SPURマルチプロセッサで動作するSpriteの測定、デバイスおよびネットワークドライバ（FDDIおよびUltranet）、同期分析、ディスクチェッカー、ダンプ、その他のディスクユーティリティ、マルチプロセッササポート、ブートストラップ、デバッガサポート、LFSサポート、スケジューラ。

Don Reeves（1989年春）：
ARPおよびリバースARP。

Ken Shirriff（1989年夏 - ??）：
RAIDを使用した高速ファイル転送、ファイルシステムトレース、名前キャッシングの分析、共有仮想メモリ、マップファイル、System-V同期、セキュリティ強制、メールサポート、UNIX互換性、動的リンク、ネットワークデーモン、DECstation-3100コマンドポート、ダンプ/リストアユーティリティ。

Mike Kupfer（1990年夏 - 1992年夏）：
MachサーバープロセスとしてのSprite、Sprite分析ペーパーの測定、カーネル内の内部エラーチェック、pmake、X、ダンプ/リストアユーティリティ、その他の管理ツールのサポート。

Jim Mott-Smith（1991年冬 - 1992年秋）：
Jaquithテープアーカイブシステム、SCSIドライバ、NFSサポート、インターネットプロトコルサーバーサポート、ダンプ/リストアユーティリティ、sendmailサポート。

Geoff Voelker（1991年秋 - 1992年夏）：
ディスクユーティリティ、FDDIネットワークドライバ、ネットワークユーティリティ。

Matt Secor（1992年夏）：
デバッガサポート。

上記にリストされた人々に加えて、私に直接報告していなかったにもかかわらず、Spriteに重要な貢献をした多くの人々がいました。以下に「外部の協力者」をいくつか挙げます。見落とした方がいたら申し訳ありません。

Bob Beck（Sequentポート）、Ann Chervenak（デバイスドライバ）、Doug Johnson（SPURデバッグ）、Ed Lee（RAIDストライピングドライバ）、Dean Long（カーネルバグ修正、ブートストラップ、SPARCstationポート）、Ethan Miller（RAIDコントローラーサポート）、Srinivasan Seshan（Ultranetサポート）、Thorsten Von Eicken（X11R4ポート）、Jay Vosburgh（Sequentポート）。