Zusammenfassung

  • Mendel Rosenblum und John Ousterhout verwandelten mit Sprite LFS viele kleine, zufällige Writes in große sequentielle Transfers; ungültige Altversionen mussten dennoch später bereinigt werden.
  • Die Kennzahl „write cost“ rechnete das Lesen und erneute Schreiben lebender Blöcke dem neuen Datenvolumen zu und verhinderte so, dass die schnelle Annahme als Gesamturteil galt.
  • Spätere Implementierungen zeigten die Grenze: Bei echter Leerlaufzeit lässt sich die Arbeit im Hintergrund erledigen; bei hoher Belegung, zufälligen Updates und knapper Reserve kehrt sie als Konkurrenz zur Nutzlast zurück.

Die Quittung am Eingang

Eine Anwendung erhält die Bestätigung für ein Update. Auf dieser Ebene ist der Vorgang abgeschlossen. Im Speichersystem kann die alte Version weiterhin Platz belegen, der Vorrat sauberer Segmente kann sinken, und nach einem Absturz muss noch rekonstruiert werden, welche Version aktuell ist. Die Antwortzeit belegt einen Übergang. Sie belegt nicht den vollständigen Kreislauf.

Genau diese Differenz machte die 1992 veröffentlichte Arbeit von Mendel Rosenblum und John K. Ousterhout sichtbar. Das Berkeley-Sprite-Team schlug nicht bloß vor, „wie ein Log“ zu schreiben. Es baute und betrieb ein Dateisystem, das Änderungen an Daten und Metadaten puffert und anschließend in großen sequentiellen Einheiten ausgibt. Viele kleine synchrone Zufallszugriffe wurden zu einem asynchronen Strom.

Für Lesezugriffe musste das Log nicht durchsucht werden. Normale Indizes zeigten weiterhin auf aktuelle Blöcke; eine inode map hielt die jeweilige Position der Inodes fest. Die Logstruktur war eine Platzierungsregel, kein Verzicht auf wahlfreien Zugriff.

Ein Update schrieb eine neue Version, statt die alte an Ort und Stelle zu verändern. Die alte Version wurde ungültig, blieb aber physisch zwischen lebenden Blöcken liegen. Sobald das Log den Datenträger umrundete, hätte das direkte Auffüllen einzelner Lücken die sequentiellen Transfers wieder zerlegt. Sprite LFS teilte den Datenträger deshalb in große Segmente und gewann ganze Segmente zurück.

Der Cleaner beendet, was der Writer begann

Der Segment Cleaner liest Kandidaten, bestimmt die noch lebenden Blöcke, schreibt sie kompakt an anderer Stelle und gibt die alten Segmente frei. Segment summaries verzeichnen Datei und logische Position jedes Blocks. Der Cleaner vergleicht diese Angabe mit dem aktuellen Zustand; dieselben Zusammenfassungen helfen beim Roll-forward nach einem Crash.

Der Anteil lebender Daten bestimmt die Rechnung. Ein fast totes Segment liefert viel freien Raum für wenig Kopierarbeit. Ein überwiegend lebendes Segment erfordert viel Lesen und Schreiben für geringen Gewinn. Freie Kapazität ist damit kein bloßer Leerstand. Sie verschafft dem System die Wahl zwischen günstigeren Kandidaten.

Rosenblum und Ousterhout fassten den Zusammenhang als write cost. Im Nenner stehen neue Nutzdaten, im Zähler der gesamte I/O-Aufwand für ihre Aufnahme – einschließlich Cleaner-Lesezugriffen und erneut geschriebenen lebenden Blöcken. Der Idealwert eins bewegt nur neue Daten. Beim Wert zehn bleibt ungefähr ein Zehntel der Rohbandbreite für neue Inhalte. Die Kennzahl zieht die später fällige Arbeit in das heutige Urteil.

Die Segmentwahl verlangt zudem eine Temperaturannahme. Eine greedy policy nahm stets das Segment mit der niedrigsten Belegung. Bei lokalem Zugriff konnte sie dennoch schlecht abschneiden: Kalte Daten blieben in halbleeren Segmenten gefangen, während heiße Daten kurz vor der nächsten Änderung kopiert wurden. Die cost-benefit policy kombinierte Belegung und Alter des jüngsten Blocks, annähernd als (1-u) × age / (1+u).

Alter war kein Wissen über die Zukunft, sondern ein Stabilitätsindikator. Kalte Segmente konnten trotz eines höheren lebenden Anteils einmal sauber geschrieben werden; heiße Segmente warteten, bis mehr Inhalt veraltet war. In den beschriebenen Simulationen sank der write cost gegenüber greedy cleaning um bis zu die Hälfte. Ein Lastwechsel konnte die gestrige Kälte jedoch in heutige Kopierarbeit verwandeln.

Der Rand des Benchmarks

Die Mikrobenchmarks der ursprünglichen Arbeit enthielten keine Reinigung. Sie zeigten den Bestfall des Vordergrundpfads, nicht den Dauerzustand. Aussagekräftiger waren vier Monate Produktivbetrieb. In der untersuchten Sprite-Umgebung lagen die Schreibkosten ungefähr zwischen 1,2 und 1,6; die langfristige Schreibleistung erreichte etwa 70 Prozent der maximalen sequentiellen Bandbreite.

Das ist ein belastbarer Beleg aus laufendem Code, aber keine Naturkonstante für jede Hardware, Füllhöhe und Last. Die Autoren bezeichneten ihre Erfahrung selbst als begrenzt. Auch Recovery hatte eine eigene Bilanz: Ein Checkpoint setzte einen bekannten Stand der inode map; Segmentinformationen ermöglichten das Vorwärtsrollen. Kurze Intervalle erhöhen den Normalaufwand, lange Intervalle vergrößern die Arbeit nach dem Absturz.

Schnelle Annahme, abgeschlossener Checkpoint und begrenzte Wiederherstellung sind drei verbundene, aber eigenständige Nachweise.

BSD lieferte die Gegenprobe

Margo Seltzer, Keith Bostic, Marshall Kirk McKusick und Carl Staelin implementierten LFS für BSD. Das Ergebnis war kein allgemeiner Sieg. Besseres Clustering ließ ein herkömmliches Dateisystem einen Teil des Vorteils aufholen. LFS zeigte seine klarste Stärke bei Metadaten und vielen sehr kleinen Dateien; bei großen Dateien waren die Leistungen vergleichbar.

In einem Vergleich von 1995 senkte der Cleaner die Transaktionsleistung bei einem halb gefüllten Testdatenträger um mehr als 33 Prozent; die Arbeit verwies außerdem auf frühere Verluste bis 40 Prozent. Eine weitere Untersuchung erreichte dagegen, dass auf dem am stärksten belasteten System 97 Prozent der Reinigung im Hintergrund stattfanden.

Beide Befunde passen zusammen. „Hintergrund“ beschreibt den Zahlungszeitpunkt, nicht die Abwesenheit der Schuld. Echte Leerlaufzeit erlaubt, die Arbeit vor der Konkurrenz durch Nutzer zu erledigen. Bei anhaltendem Zufluss, sinkender Reserve und fehlender Ruhephase beansprucht dieselbe Arbeit sichtbare Bandbreite.

Adaptive LFS-Forschung grenzte den günstigen Bereich weiter ein: häufige kleine Writes, vom Cache absorbierte Reads und ausreichend Leerlauf. Zufällige Updates auf einem vollen Datenträger ohne Ruhephase waren ungünstig. Segmentgröße, Cleaner-Politik und Leseanordnung konnten die Grenze verschieben, aber nicht beseitigen.

Ousterhouts Beitrag lässt sich daher nicht auf „sequentiell ist schnell“ reduzieren. Zusammen mit Rosenblum und dem Sprite-Team schuf er einen schlanken Eingangsmechanismus und eine Rechnung für dessen Folgekosten. Der Logeintrag belegt die Aufnahme einer Version. Reserve, Reinigung und Recovery belegen die Fähigkeit, damit fortzufahren.

Quellen