Dateisysteme

Eine Datei ist eine dauerhaft gespeicherte Folge von Bytes. Das Dateisystem speichert diese Bytes, ohne zu entscheiden, ob sie Text, ein Bild oder Maschinencode bedeuten. Ein Verzeichnis gibt der Datei einen lesbaren Namen; ihre Inode-Nummer identifiziert sie innerhalb des Dateisystems.

Öffne eine Datei und prüfe das Ergebnis

open(path, flags, mode) gibt einen Dateideskriptor zurück, eine nicht negative Ganzzahl, die in späteren Aufrufen verwendet wird. Bei einem Fehler wird -1 zurückgegeben und errno gesetzt. Wähle für den Zugriff O_RDONLY, O_WRONLY oder O_RDWR. O_CREAT erzeugt eine fehlende Datei, O_TRUNC leert eine vorhandene Datei und O_APPEND platziert jeden Schreibvorgang am aktuellen Ende.

Für eine neue Datei fordert mode Berechtigungen an und die umask des Prozesses entfernt Bits. Ohne eine Standard-Zugriffskontrollliste (ACL) für das Verzeichnis ergibt sich mode & ~umask. Die Anforderung 0666 mit umask 0022 ergibt 0644 oder rw-r--r--. Dieses Argument ändert die Berechtigungen einer bereits vorhandenen Datei nicht.

Deskriptoren gehören zu einem Prozess. Normalerweise stehen 0, 1 und 2 für Standardeingabe, Standardausgabe und Standardfehlerausgabe. open wählt den kleinsten ungenutzten Deskriptor, häufig 3. Unter Linux zeigt strace cat notes.txt die Aufrufe: das Öffnen der Eingabe, ihr Lesen, das Schreiben auf Deskriptor 1 und anschließend das Schließen der Eingabe.

Verfolge den Offset, nicht die angeforderte Anzahl

read(fd, buf, n) gibt die tatsächlich gelesene Bytezahl zurück, höchstens n. Bei einer von null verschiedenen Anforderung an eine reguläre Datei bedeutet null, dass am oder hinter dem Dateiende keine Bytes mehr vorhanden sind; -1 bedeutet einen Fehler. Auch write gibt eine tatsächliche Anzahl zurück, die kleiner als angefordert sein kann. Prüfe diese Anzahl, bevor du einen Pufferzeiger weitersetzt oder die Operation für abgeschlossen erklärst.

Angenommen, log.txt enthält 300 Byte. Vier Anforderungen von je 100 Byte geben 100, 100, 100 und 0 zurück. Der Offset, die Position der nächsten Operation, steht danach bei 100, 200, 300 und 300. Das Dateiende wird durch eine zurückgegebene Anzahl angezeigt, nicht durch ein spezielles Byte in der Datei.

lseek(fd, 200, SEEK_SET) setzt den Offset auf 200. Das anschließende Lesen von 50 Byte gibt die Bytes 200 bis 249 zurück und hinterlässt den Offset bei 250. SEEK_CUR zählt vom aktuellen Offset aus; SEEK_END zählt vom Dateiende aus. Das Verschieben ändert eine Zahl im Speicher. Es bewegt keinen Festplattenkopf und liest selbst keine Daten. pread und pwrite nutzen eine ausdrücklich angegebene Position, ohne diesen Offset zu ändern.

Bestimme, welche Deskriptoren einen Offset gemeinsam nutzen

Die Deskriptortabelle des Prozesses zeigt auf Einträge in der Tabelle geöffneter Dateien des Kernels. Jeder Eintrag für eine offene Datei enthält den Zugriffsmodus, den Offset, eine Inode-Referenz und einen Referenzzähler.

Setzt ein Kindprozess den Offset eines gemeinsam genutzten Deskriptors auf Byte 10, beginnt auch der nächste Lesevorgang des Elternprozesses über diesen Eintrag bei 10. Der Inode identifiziert die Datei, aber der Eintrag für die offene Datei enthält den Offset: Zwei lesende Prozesse können eine Datei gemeinsam nutzen, ohne ihre Position zu teilen. Die Shell-Umleitung nutzt dup2, damit die Standardausgabe auf einen anderen Eintrag für eine offene Datei verweist. close gibt einen Deskriptor frei; der Eintrag verschwindet, nachdem seine letzte Referenz freigegeben wurde. Das Schließen allein erzwingt nicht das Schreiben gepufferter Daten auf dauerhaften Speicher.

Ein erfolgreicher Schreibvorgang und eine absturzsichere Aktualisierung beantworten unterschiedliche Fragen. Ein Schreibvorgang meldet, dass Bytes angenommen wurden. Dauerhaftigkeit betrifft die Frage, ob sie einen Absturz überstehen; Atomarität betrifft die Frage, ob eine Aktualisierung nur als Ganzes beobachtet werden kann.

Erzwinge das Schreiben auf dauerhaften Speicher

Betriebssysteme puffern Schreibvorgänge meist im Speicher und senden veränderte Blöcke später an das Speichergerät, häufig innerhalb von ungefähr 5 bis 30 Sekunden. Das bündelt kleine Schreibvorgänge und lässt das Programm schnell weiterlaufen. Ein Absturz kann Daten löschen, die noch in diesen Puffern warten.

fsync(fd) erzwingt das Schreiben der veränderten Daten und Metadaten der Datei auf das Speichergerät und wartet, bis das Gerät den Abschluss meldet. Ein Programm muss das Ergebnis prüfen, bevor es eine dauerhafte Speicherung meldet. close gibt den Deskriptor frei und ersetzt dieses Warten nicht.

Eine Datei braucht auch einen dauerhaft gespeicherten Namen. Der Eintrag, der den Namen auf den Inode abbildet, gehört zu den Daten ihres Verzeichnisses, nicht zu denen der Datei. Wird nach dem Erzeugen einer Datei nur diese synchronisiert, können ihre Bytes dauerhaft gespeichert sein, ohne dass ihr neuer Name garantiert erhalten bleibt. Öffne das enthaltende Verzeichnis und synchronisiere es, wenn der Name dauerhaft erhalten bleiben muss.

Ersetze eine Datei, ohne eine unvollständige Version sichtbar zu machen

Beim direkten Überschreiben eines Dokuments entsteht ein Zeitraum, in dem lesende Prozesse auf unvollständige Inhalte stoßen können. O_TRUNC setzt seine Länge zunächst auf null. Unterbricht ein Absturz die späteren Schreibvorgänge, ist die alte vollständige Kopie bereits verschwunden.

Schreibe den Ersatz stattdessen unter einem temporären Namen in dasselbe Verzeichnis. Nutze dann rename, um das Ziel zu ersetzen. Für ein vorhandenes Ziel auf demselben Dateisystem macht POSIX diese Ersetzung atomar: Der Zielname verweist auf die alte Datei oder den Ersatz, ohne dass der Name dazwischen fehlt. Lesende Prozesse sehen unter diesem Namen keine Mischung ihrer Inhalte.

Für settings.json lautet die Folge für eine dauerhafte Ersetzung:

1. Schreibe den gesamten neuen Inhalt nach settings.json.tmp und prüfe auf partielle Schreibvorgänge und Fehler.
2. Rufe fsync für die temporäre Datei auf und prüfe, ob der Aufruf erfolgreich war.
3. Rufe rename("settings.json.tmp", "settings.json") auf und prüfe, ob der Aufruf erfolgreich war.
4. Rufe fsync für das enthaltende Verzeichnis auf und prüfe, ob der Aufruf erfolgreich war.

Die temporäre Datei ist vollständig und dauerhaft gespeichert, bevor sich der Name ändert. Die abschließende Synchronisierung des Verzeichnisses macht diese Namensänderung dauerhaft. Ein Absturz während der Folge hinterlässt am Ziel eine vollständige alte oder eine vollständige neue Version; nach der letzten erfolgreichen Synchronisierung ist die neue Version dauerhaft gespeichert. Die atomare Ersetzung des Namens allein verspricht nicht, dass ein nicht synchronisiertes Umbenennen einen Stromausfall übersteht.

rename über Dateisystemgrenzen hinweg schlägt mit EXDEV fehl. Ein Befehl, der darauf mit Kopieren und Löschen reagiert, führt mehrere Operationen aus, sodass diese Ausweichlösung keine atomare Ersetzung garantiert.

Ändere die Länge, ohne jedes Byte zu schreiben

truncate(path, length) und ftruncate(fd, length) setzen die Länge der Datei. Beim Verkleinern werden Bytes jenseits des neuen Endes verworfen. Beim Verlängern wird der neue Bereich als Nullen gelesen. Auch das Positionieren hinter dem Ende und anschließende Schreiben erzeugt eine Lücke, die als Nullen gelesen wird.

Eine dünn besetzte Datei kann eine solche Lücke darstellen, ohne dafür Datenblöcke zuzuweisen. Schreibst du ausgehend von einer leeren Datei ein Byte an Offset 8192, entsteht eine Datei der Länge 8193 Byte; der vorangehende ungeschriebene Bereich wird als Nullen gelesen. Ihre logische Größe kann den physisch zugewiesenen Speicherplatz übersteigen.

Verzeichnisse trennen die Namen, die Menschen verwenden, von den Objekten, die das Dateisystem speichert. Jedes Verzeichnis hat einen eigenen Inode und eigene Datenblöcke; seine Einträge bilden Namen auf Inode-Nummern ab.

Folge Pfaden durch den Baum

Ein absoluter Pfad beginnt bei /. Ein relativer Pfad beginnt beim aktuellen Arbeitsverzeichnis des Prozesses. Der Eintrag . bezeichnet das Verzeichnis selbst und .. sein übergeordnetes Verzeichnis; das übergeordnete Verzeichnis der Wurzel ist die Wurzel selbst. Von /home/lee aus führt der relative Pfad ../shared nach /home/shared.

Eine Endung wie .txt ist Teil eines Namens. Programme können anhand der Endung entscheiden, wie sie die Bytes interpretieren, aber das Dateisystem verlangt nicht, dass eine .txt-Datei Text enthält.

mkdir erzeugt ein Verzeichnis mit . und ... Um Einträge aufzulisten, nutzt ein Programm opendir, ruft readdir auf, bis keine Einträge mehr vorhanden sind, und ruft closedir auf. Ein Ergebnis von readdir enthält einen Namen und eine Inode-Nummer. Programme ändern Verzeichnisinhalte durch Aufrufe wie link, unlink und rename, nicht durch gewöhnliche write-Aufrufe. rmdir entfernt ein leeres Verzeichnis.

Gib einer Datei zwei gleichwertige Namen

link(old, new) erzeugt einen harten Link: einen weiteren Verzeichniseintrag, der auf denselben Inode zeigt. Keiner der Namen ist als Original bevorzugt. Der Linkzähler des Inodes hält fest, wie viele Namen auf ihn verweisen.

Betrachte diese Befehle, wenn kein Prozess die Datei geöffnet hat:

echo hi > a
ln a b
rm a
cat b
rm b

Das Erzeugen von b erhöht den Linkzähler von 1 auf 2. Das Entfernen von a senkt ihn auf 1; b erreicht weiterhin dieselben Bytes, sodass cat b „hi“ ausgibt. Das Entfernen von b senkt den Zähler auf 0, sodass der Inode und seine Blöcke zurückgewonnen werden können.

Ein offener Deskriptor ergänzt eine zweite Regel für die Lebensdauer. Wird der letzte Name entfernt, während ein Prozess die Datei noch geöffnet hat, kann dieser Prozess weiterhin darauf zugreifen. Die Freigabe wartet sowohl auf null Links als auch darauf, dass keine offenen Referenzen mehr bestehen. Das erklärt, warum das Löschen einer großen geöffneten Protokolldatei ihren Speicherplatz möglicherweise nicht sofort freigibt.

Ein harter Link kann Dateisystemgrenzen nicht überschreiten: Die Inode-Nummer des Ziels hätte in der anderen Inode-Tabelle keine Bedeutung. Die meisten Unix-Systeme verbieten auch harte Links auf Verzeichnisse, um einen Baum ohne Zyklen zu erhalten. Nach der klassischen Unix-Zählweise hat ein leeres Verzeichnis zwei Links, aus seinem Eintrag im übergeordneten Verzeichnis und seinem eigenen .. Jedes Unterverzeichnis trägt durch .. einen weiteren bei; drei Unterverzeichnisse ergeben den Zählerstand 5.

Speichere einen Pfad in einem symbolischen Link

Ein symbolischer Link oder Softlink ist eine eigenständige Datei, deren Inhalt ein Zielpfad ist. ln -s /home/ana/report.txt r erzeugt r mit dem 20 Byte langen Zielpfad als Inhalt. Beim Folgen des Links wird dieser Pfad aufgelöst. Symbolische Links können Dateisystemgrenzen überschreiten und auf Verzeichnisse zeigen.

Ein symbolischer Link erhöht den Linkzähler seines Ziels nicht. Das Behalten des Linkobjekts erhält daher das Ziel nicht.

Der Inhalt einer Datei ist nur ein Teil ihres Zustands. Metadaten halten fest, wer sie nutzen darf, welche Größe und welchen Typ sie hat und wann sie geändert wurde. Durch das Einhängen werden Objekte mehrerer Dateisysteme über einen einzigen Namensbaum erreichbar.

Lies die Metadaten richtig

stat(path, &buf) liest Metadaten über einen Pfad; fstat(fd, &buf) liest sie über einen offenen Deskriptor. Zu den Ergebnissen gehören Inode-Nummer, Typ, Berechtigungen, Eigentümer- und Gruppenkennung, Größe, zugewiesene Blöcke und Linkzähler. Die Dateigröße zählt die logischen Bytes; die zugewiesenen Blöcke messen den tatsächlich genutzten Speicherplatz, der bei einer dünn besetzten Datei kleiner sein kann.

Drei Zeitstempel beschreiben unterschiedliche Ereignisse:

ctime ist nicht die Erstellungszeit. Eine Aktualisierung von atime allein ändert ctime nicht. Das klassische Unix-stat hat kein Feld für die Erstellungszeit; Linux-statx kann eine gespeicherte Erstellungszeit ausgeben, wenn das Dateisystem sie unterstützt.

Entschlüssele Berechtigungsbits

Lese-, Schreib- und Ausführungsrechte werden für Eigentümer, Gruppe und andere getrennt gespeichert. Jede Klasse entspricht einer Oktalziffer: Lesen zählt 4, Schreiben 2 und Ausführen 1. Bei rw-r----- erhält der Eigentümer 4 + 2 = 6, die Gruppe 4 und andere erhalten 0. chmod 640 report.txt setzt diese Bits.

Verzeichnisberechtigungen gelten für Namen und die Pfadauflösung. Lesen erlaubt das Auflisten von Namen. Ausführen erlaubt das Durchsuchen, also die Verwendung des Verzeichnisses in einem Pfad. Schreiben zusammen mit Ausführen erlaubt das Erzeugen, Löschen und Umbenennen von Einträgen. Wer den Namen kennt, kann eine Datei in einem Verzeichnis mit Ausführungs-, aber ohne Leseberechtigung möglicherweise öffnen, sofern die Berechtigungen der Datei den Zugriff erlauben. Das Auflisten dieses Verzeichnisses schlägt dennoch fehl.

Dieser Unterschied ist beim Löschen wichtig: Das Entfernen eines Eintrags ändert das enthaltende Verzeichnis. Das Schreibbit einer Datei steuert die Änderung ihrer Bytes; es ist nicht die Berechtigung des Verzeichnisses, ihren Namen zu entfernen. Root umgeht die meisten gewöhnlichen Berechtigungsprüfungen. Zugriffskontrolllisten (ACLs) können benannten Benutzern und Gruppen über die drei grundlegenden Klassen hinaus Rechte gewähren.

Hänge ein weiteres Dateisystem ein

mkfs initialisiert ein Dateisystem auf einer Partition oder einem anderen Gerät, einschließlich seines eigenen Wurzelverzeichnisses und seiner Metadaten. Dabei wird der bisherige Dateisysteminhalt des Geräts zerstört. Führe den Befehl daher nur auf einem für die Initialisierung vorgesehenen Gerät aus.

mount hängt diese Wurzel an ein vorhandenes Verzeichnis, den Einhängepunkt. Ein unter /media/usb eingehängtes Laufwerk macht den Inhalt seiner Wurzel dort zugänglich. Der bisherige Inhalt von /media/usb ist verborgen, solange das Dateisystem eingehängt ist; beim Einhängen wird er nicht mit dem eingehängten Baum zusammengeführt. Ein Aufruf von mount ohne Argumente listet die aktuellen Einhängungen auf.

Die Schicht des virtuellen Dateisystems (VFS) im Kernel stellt ext4, XFS, FAT sowie speicherbasierten und Netzwerkdateisystemen eine gemeinsame Schnittstelle bereit. Programme können bei jedem dieser Systeme open und read aufrufen. Der vereinte Namensraum führt ihre Inode-Tabellen nicht zusammen: Gleiche Inode-Nummern auf verschiedenen Dateisystemen können voneinander unabhängige Dateien bezeichnen. Harte Links und atomares Umbenennen bleiben daher auf das jeweilige Dateisystem beschränkt.

Ein Dateisystem muss sich merken, wo Bytes liegen und welcher Speicherplatz verfügbar ist. Eine einfache Unix-artige Aufteilung macht diese Aufgaben sichtbar, indem sie Belegungsinformationen, Inodes und Inhalte trennt.

Teile die Partition in Bereiche ein

Ein Block ist die grundlegende Zuweisungseinheit des Dateisystems. Ein 4-KiB-Block enthält 4.096 Byte oder acht herkömmliche Sektoren zu je 512 Byte. Binäre Größen verwenden KiB, MiB und GiB; Übertragungsraten wie MB/s verwenden dezimale Millionen Byte pro Sekunde.

Der Lehrentwurf vsfs, das sehr einfache Dateisystem, enthält diese Strukturen:

Ein Bitmap-Bit mit dem Wert 1 bedeutet belegt; 0 bedeutet frei. Der Superblock gibt dem Betriebssystem beim Einhängen vor, wie es den Rest der Partition interpretieren muss. Die beiden Bitmaps beschreiben unterschiedliche Ressourcen: Einer Datei kann bereits ein Inode zugewiesen sein, bevor sie Datenblöcke hat.

Finde einen Inode anhand seiner Nummer

Nimm eine Partition mit 64 Blöcken zu je 4 KiB. Lege den Superblock in Block 0, die Inode-Bitmap in Block 1, die Datenbitmap in Block 2 und die Inode-Tabelle in den Blöcken 3 bis 7 ab. Die Daten belegen die Blöcke 8 bis 63. Fünf Blöcke der Inode-Tabelle mit Inodes zu je 256 Byte fassen 80 Inodes, weil jeder Block 16 fasst. Es gibt 56 Datenblöcke. Eine 4 KiB große Bitmap kann 32.768 Objekte beschreiben, sodass in dieser kleinen Aufteilung ein großer Teil jeder Bitmap ungenutzt bleibt.

Werden die Inode-Plätze ab null nummeriert, beginnt Inode 37 genau 37 × 256 = 9.472 Byte nach Beginn der Tabelle. Die Tabelle beginnt bei Byte 12.288, was die absolute Byteadresse 21.760 ergibt. Die Division durch 4.096 ergibt Festplattenblock 5 mit Rest 1.280. Die Division durch 512 ergibt dagegen Sektor 42 mit Rest 256. Lies den Block oder Sektor, der den Inode enthält, und wähle darin die Bytes des Inodes aus.

Die allgemeine Methode lautet: Tabellenanfang in Byte plus Inode-Nummer mal Inode-Größe. Halte die Anfangsadresse der Tabelle vom Offset des Inodes innerhalb der Tabelle getrennt. Lässt du diese Basisadresse weg, erhältst du den falschen Festplattenblock.

Trenne Namen, Metadaten und Inhalte

Ein Inode oder Indexknoten speichert Typ, Berechtigungen, Eigentumsverhältnisse, Größe, Zeiten, Linkzähler, zugewiesene Blöcke und Datenpositionen. Er enthält nicht den Dateinamen. Der Name gehört in einen Verzeichniseintrag, sodass mehrere Namen einen Inode gemeinsam nutzen können.

Ein Verzeichnis hat einen Inode vom Typ Verzeichnis und Datenblöcke mit Einträgen. Ein einfacher Eintrag speichert eine Inode-Nummer, die Datensatzlänge, die Namenslänge und den Namen. Anhand der Datensatzlänge kann bei der Suche der ganze Eintrag übersprungen werden, einschließlich des durch Löschen entstandenen wiederverwendbaren Platzes. Große Verzeichnisse profitieren von Indizes: XFS nutzt B-Bäume und ext4 hashbasierte Baumindizes.

Beim Erzeugen einer Datei wird ein freies Bit in der Inode-Bitmap gesucht und gesetzt. Die Zuweisung von Daten ändert entsprechend die Datenbitmap. Ein Allokator kann eine Folge von Blöcken reservieren, damit die Datei zusammenhängend wachsen kann. Die Bitmap gibt an, ob ein Block frei ist; der Inode gibt an, zu welcher Datei er gehört. Diese Strukturen müssen übereinstimmen.

Ein Programm sieht aufeinanderfolgende Byteoffsets, aber die zugehörigen Datenblöcke können über die Festplatte verstreut sein. Das Dateisystem benötigt eine Zuordnung von jedem logischen Dateiblock zu seiner physischen Position.

Folge direkten und indirekten Zeigern

Ein direkter Zeiger in einem Inode bezeichnet einen Datenblock. Bei 4-KiB-Blöcken liegt Byteoffset 10.000 im logischen Block 2, weil zwei vollständige Blöcke 8.192 Byte umfassen. Der Offset innerhalb dieses Blocks beträgt 1.808. Logische Blöcke beginnen bei 0, sodass Block 2 den dritten direkten Zeiger nutzt.

Ein indirekter Zeiger bezeichnet einen Block, der Datenblockadressen enthält. Ein Block von 4.096 Byte mit 4 Byte großen Adressen fasst 1.024 Zeiger. Ein doppelt indirekter Zeiger bezeichnet einen Block, dessen Zeiger zu 1.024 indirekten Blöcken führen. Dreifache Indirektion fügt eine weitere Ebene hinzu. Dieser mehrstufige Index ist bewusst unausgeglichen: Kleine Dateien nutzen direkte Zeiger ohne zusätzliche Lesezugriffe auf Zeigerblöcke, während bei großen Dateien Aufwand für zusätzliche Ebenen anfällt.

Für einen Inode mit 12 direkten Zeigern und einem Zeiger jeder indirekten Ebene gilt:

Dies sind Kapazitäten dieser Zeigerstruktur. Zeigerblöcke belegen ebenfalls Speicherplatz, aber ihre Bytes gehören nicht zum Dateiinhalt.

Zähle die Zeigerblöcke einer Datei

Eine 5 MiB große Datei belegt 1.280 Datenblöcke zu je 4 KiB. Weise die ersten 12 direkten Zeigern zu. Weise die nächsten 1.024 dem einfach indirekten Block zu. Es bleiben 244 Datenblöcke.

Diese 244 benötigen einen doppelt indirekten Wurzelblock und einen indirekten Block darunter. Insgesamt braucht die Datei drei Zeigerblöcke: den einfach indirekten Block, den doppelt indirekten Wurzelblock und dessen einen Kindblock. Wer nur den doppelt indirekten Wurzelblock zählt, übersieht den Kindblock, der die Datenadressen tatsächlich enthält. Alle 1.024 möglichen Kindblöcke zu zählen verschwendet Platz: Nur der benötigte Kindblock wird zugewiesen.

Vergleiche Extents und Ketten

Ein Extent speichert einen Startblock auf der Festplatte und die Länge einer Folge. Eine zusammenhängende Folge von 1.000 Blöcken kann einen Extent statt 1.000 einzelner Zeiger nutzen. Ext4, XFS und NTFS verwenden Extents. Ext4 kann bis zu vier Extents in seinem Inode halten und nutzt für weitere einen Baum. Fragmentierung teilt Folgen auf und erhöht die Anzahl benötigter Extent-Einträge.

Die verkettete Zuweisung folgt einer Kette von Blöcken. Die Dateizuordnungstabelle (FAT) speichert die Verweise auf den jeweils nächsten Block in einer separaten Tabelle, die meist im Speicher zwischengespeichert wird. Ein Verzeichniseintrag bezeichnet den ersten Block, und um einen späteren Block zu erreichen, muss man den vorherigen Verweisen folgen. FAT nutzt keine Unix-Inodes und unterstützt keine zwei harten Links auf eine Datei.

Aufeinanderfolgende Offsets beweisen nie, dass die Daten physisch zusammenhängen. Der Allokator wählt Positionen, und die Zuordnung hält diese Wahl fest.

Ein Systemaufruf kann mehrere Festplattenoperationen benötigen oder gar keine. Um die Arbeit zu verfolgen, gehst du die Strukturen durch, die das Dateisystem heranziehen muss, und gibst an, welche davon bereits im Cache liegen.

Löse einen Pfad auf, bevor du Inhalte liest

Im einfachen Modell ohne Cache liest das Öffnen von /docs/plan.txt fünf Blöcke:

1. Den Wurzel-Inode, dessen Nummer bekannt ist.
2. Die Daten des Wurzelverzeichnisses, um docs zu finden.
3. Den Inode von docs.
4. Die Verzeichnisdaten von docs, um plan.txt zu finden.
5. Den Inode der Datei.

Jedes Verzeichnis passt in einen Block, und zunächst liegt kein benötigter Block im Speicher. Das Dateisystem prüft die Berechtigungen und erzeugt einen Eintrag für die offene Datei. Das Öffnen hat die Metadaten der Datei gefunden; ihren Inhalt hat es noch nicht gelesen. ext2 und ext4 verwenden die Wurzel-Inode-Nummer 2.

In einem bewusst ohne Cache gehaltenen Lesemodell liest jeder anschließende Blocklesevorgang den Inode der Datei und die Daten und schreibt die Zugriffszeit des Inodes. Zwei Blöcke ergeben sechs zusätzliche Ein-/Ausgaben, einschließlich des Öffnens also elf. Das Schließen benötigt in diesem Modell keinen Festplattenzugriff. Diese Zahlen beschreiben die ausdrücklichen Regeln des Modells für erneutes Lesen und Zeitstempel; ein realer Cache verändert sie.

Berücksichtige die Zuweisung beim Erzeugen

Das Erzeugen von /docs/log.txt erfordert mehr als das Finden eines vorhandenen Inodes. Im selben einfachen Modell erfolgen vier Lesezugriffe für die Inodes und Verzeichnisdaten der Wurzel und von docs. Das Lesen und Schreiben der Inode-Bitmap ergänzt zwei Ein-/Ausgaben. Die Aktualisierung der Daten von docs ergänzt einen Schreibvorgang. Das Lesen und Schreiben des neuen Inodes ergänzt zwei und die Aktualisierung des Inodes von docs eine Ein-/Ausgabe. Insgesamt sind es zehn.

Jeder neu zugewiesene Datenblock ergänzt fünf Ein-/Ausgaben: die Datenbitmap lesen und schreiben, den Inode der Datei lesen und schreiben und den Datenblock schreiben. Zwei Blöcke ergeben daher einschließlich des Erzeugens zwanzig Ein-/Ausgaben. Diese Nachverfolgung zählt die einfachen Datenstrukturen, bevor Journalingzugriffe oder das Verhalten eines realen Caches hinzukommen.

Eine Aufstellung hilft: Liste die Struktur auf, ob sie gelesen oder geschrieben wird und warum. Ein Datenschreibvorgang benötigt auch eine Belegungsinformation und eine Zeigeraktualisierung. Eine Verzeichnisänderung ändert auch die Metadaten dieses Verzeichnisses.

Berücksichtige den Einfluss des Caches

Ein Cache-Treffer nutzt einen Block, der bereits im Speicher liegt. Linux nutzt einen einheitlichen Seitencache gemeinsam mit dem virtuellen Speicher, keinen dauerhaft getrennten Dateicache fester Größe. Ein erneutes Öffnen kann die Verzeichnis- und Inode-Blöcke der vorherigen Pfadauflösung wiederverwenden. Das Lesen zwischengespeicherter Inhalte benötigt keinen Gerätezugriff. Die übliche Linux-Strategie relatime sorgt zudem dafür, dass atime nicht bei jedem Lesen geschrieben wird.

Schreibpufferung verzögert das Senden veränderter Blöcke an die Festplatte. Zwei kurz aufeinanderfolgende Dateierzeugungen können dieselbe Inode-Bitmap im Speicher aktualisieren und sie später einmal schreiben. Das Dateisystem kann die Arbeit für einen besseren Durchsatz umordnen. Eine kurzlebige temporäre Datei kann erzeugt und entfernt werden, bevor ihr Inhalt überhaupt das Speichergerät erreicht.

Pufferung verbessert die Leistung, schafft aber ein Zeitfenster ohne Dauerhaftigkeit. fsync schließt dieses Fenster für eine Datei, indem es auf die erforderlichen Schreibvorgänge wartet. Linux-O_DIRECT erlaubt geeigneten Programmen, den Seitencache zu umgehen, wenn sie ihre eigenen Puffer verwalten; das Umgehen eines Caches ist für sich genommen nicht dasselbe wie das Synchronisieren auf dauerhaften Speicher.

Eine Festplatte kann eine lange Folge von Bytes schnell übertragen, sobald ihr Kopf sie erreicht. Kleine verstreute Anfragen verschwenden Zeit durch Positionierung und Warten auf die Rotation. Das Fast File System ändert die Platzierung so, dass gewöhnliche Dateioperationen mehr von der Übertragungsbandbreite der Festplatte nutzen.

Untersuche die alte Unix-Aufteilung

Die frühe Unix-Aufteilung platzierte alle Inodes nahe dem Anfang und alle Dateidaten dahinter. Das Lesen einer Datei konnte daher eine lange Positionierung von den Metadaten zu den Inhalten erfordern. Eine Freispeicherliste verstreute die Zuweisungen nach und nach, während Dateien erzeugt und gelöscht wurden. Selbst eine sequenzielle Datei konnte viele voneinander unabhängige Festplattenzugriffe verursachen.

Kleine 512-Byte-Blöcke verschlimmerten dies. Für jede Positionierungsverzögerung erhielt man nur eine kurze Übertragung, bevor die nächste Anfrage eine weitere Positionierung oder Rotation benötigte. Historische Messungen ergaben, dass der alte Entwurf teilweise nur 2 % der Festplattenbandbreite erreichte. Diese Zahl beschreibt den gemessenen frühen Entwurf, keine feste Schranke von Unix-Schnittstellen.

Das Anfang der 1980er-Jahre in Berkeley entwickelte Fast File System (FFS) behielt vertraute Aufrufe wie open, read und write bei und änderte zugleich die Aufteilung und die Zuweisungsstrategie. Größere Blöcke, typischerweise 4 KiB, erhöhten die pro Anfrage übertragene Bytezahl. Die nahe Platzierung von Metadaten und Inhalten verringerte die Entfernung zwischen zusammengehörigen Anfragen.

Bilde Gruppen mit eigenen Ressourcen

Ein Zylinder umfasst die Spuren auf den Plattenoberflächen einer Festplatte, die denselben Radius haben. FFS bildet Zylindergruppen aus benachbarten Zylindern. Inode und Daten einer Datei können in derselben Gruppe liegen, sodass die Positionierung von den Metadaten zu den Daten kurz bleibt.

Jede Gruppe enthält eine Superblockkopie, eigene Inode- und Datenbelegungsbitmaps, einen Teil der Inode-Tabelle und Datenblöcke. Die Gruppe ähnelt einem kleinen Dateisystem, aber alle Gruppen gehören zu einem Dateisystem. Eine Superblockkopie hilft auch bei der Wiederherstellung, wenn eine Kopie beschädigt ist. Ext4 hält Kopien nur in ausgewählten Gruppen vor, nicht in jeder Gruppe.

Moderne Laufwerke verbergen ihre physische Geometrie. Ext2, ext3 und ext4 nutzen daher Blockgruppen, Folgen aufeinanderfolgender logischer Blockadressen, um dasselbe Lokalitätsziel zu verfolgen, ohne auf genaue Zylinder angewiesen zu sein.

Verfolge das Erzeugen einer kleinen Datei

Das Erzeugen von /docs/a.txt benötigt einen freien Inode, einen Datenblock, Änderungen an den Belegungsbitmaps und einen neuen Verzeichniseintrag. FFS versucht, die Datei in der Gruppe ihres übergeordneten Verzeichnisses zu platzieren. Der neue Inode, die Dateidaten, Bitmaps und Verzeichnisaktualisierungen können dann nahe beieinanderliegen.

Die Operation benötigt weiterhin mehrere getrennte Aktualisierungen. Die Gruppierung spart Positionierungszeit; sie fasst nicht alle Metadaten und Daten in einem Block zusammen. Eine Anordnung, die die Festplatte berücksichtigt, verringert den Aufwand für den Zugriff auf diese Strukturen, ohne die Dateioperationen des Programms zu ändern.

FFS nutzt Namen als Hinweise darauf, auf welche Dateien ein Programm gemeinsam zugreifen wird. Es begrenzt auch, wie viel Platz eine große Datei in einer Gruppe belegen kann, und stimmt so Lokalität und Platz für spätere Zuweisungen aufeinander ab.

Platziere Verzeichnisse und Dateien

Ein neues Verzeichnis kommt in eine Gruppe mit relativ wenigen Verzeichnissen und vielen freien Inodes. Das verteilt unterschiedliche Verzeichnisse und lässt zugleich Platz für ihre späteren Dateien. Der Inode einer regulären Datei kommt in die Gruppe ihres übergeordneten Verzeichnisses und ihre Daten nahe an ihren Inode.

Für /a/b, /a/c und /a/d werden die drei Dateien nahe dem Verzeichnis /a platziert. Eine Datei /b/f folgt ihrem eigenen übergeordneten Verzeichnis /b, meist in eine andere Gruppe. Das nutzt Namensraumlokalität: Ein Compiler, der an einem Projekt arbeitet, öffnet häufig mehrere Dateien im selben Verzeichnis. Die Verzeichnisbeziehung lässt Zugriffsmuster erwarten; sie ist keine Garantie für jedes Programm.

Mache eine Ausnahme für eine große Datei

Eine große Datei könnte die freien Blöcke ihrer Gruppe verbrauchen und alle späteren Nachbarn an andere Stellen verdrängen. FFS hält den ersten Teil, der über 12 direkte Zeiger erreicht wird, in der Gruppe des Inodes. Bei 4-KiB-Blöcken sind das 48 KiB. Spätere Teilstücke, die jeweils über einen indirekten Block mit 1.024 Zeigern erreicht werden, umfassen 4 MiB Daten und kommen in andere schwach belegte Gruppen.

Dies opfert etwas Lokalität innerhalb der großen Datei, um die Lokalität für die anderen Dateien des Verzeichnisses zu erhalten. Bei der großen Datei fällt zwischen Teilstücken eine Positionierungsverzögerung an. Daher muss jedes Teilstück groß genug sein, damit sich dieser Aufwand lohnt.

Leite die Teilstückgröße her

Die Positionierung dauere T Sekunden und die Übertragungsrate betrage R Byte pro Sekunde. Die Übertragung eines Teilstücks C dauert C/R Sekunden. Der Anteil der gesamten Zeit, der auf die Übertragung entfällt, ist:

Auflösen ergibt:

Bei 100 MB/s und 10 ms Positionierung beträgt R mal T gleich 1 MB. Ein Teilstück von 1 MB benötigt 10 ms Übertragung plus 10 ms Positionierung und erreicht damit 50 % der maximalen Bandbreite. Für 90 % multiplizierst du 1 MB mit 0,9/0,1 und erhältst 9 MB. Für 99 % beträgt der Faktor 99, was 99 MB ergibt. Wandle Millisekunden in Sekunden um, bevor du mit MB/s multiplizierst. Der Nenner enthält sowohl Übertragungs- als auch Positionierungszeit; würdest du nur durch die Übertragungszeit dividieren, bliebe der Verwaltungsaufwand verborgen.

Übertragungsraten haben sich schneller verbessert als Positionierungsverzögerungen. Um denselben Anteil der maximalen Bandbreite zu erreichen, sind daher größere Teilstücke nötig, wenn der Abstand wächst.

Berücksichtige kleine Dateien und erhalte die Kompatibilität

FFS nutzte außerdem Teilblöcke von 512 Byte, damit kleine Dateien keinen ganzen 4-KiB-Block verschwendeten. Wachsende Dateien wurden in vollständige Blöcke kopiert; die C-Bibliothek pufferte Schreibvorgänge in Stücken von 4 KiB, um wiederholtes Verschieben zu verringern. Die historische Parametrisierung ließ Rotationsabstände zwischen aufeinanderfolgenden Blöcken, damit ein angeforderter nächster Block den Kopf noch nicht passiert hatte. Moderne Spurpuffer machen diese Technik überflüssig, indem sie eine Spur intern einlesen.

Lange Namen, symbolische Links und atomares rename waren zusätzliche Fähigkeiten von FFS. Die Beschleunigung durch die Anordnung selbst erforderte keine Änderung vorhandener Programme.

Für ein Programm sieht ein Anhängen wie eine Handlung aus. Auf der Festplatte ändert es mehrere Strukturen, und ein Absturz kann dazu führen, dass nur einige davon aktualisiert werden. Bei der Absturzkonsistenz geht es darum, wie sich diese Teilergebnisse verhindern oder reparieren lassen.

Verfolge drei unabhängige Schreibvorgänge

Das Anhängen eines 4-KiB-Blocks an eine vorhandene Datei ändert:

• Db, den neuen Datenblock mit den angehängten Bytes.
• I, den Inode mit einer größeren Dateigröße und einem Zeiger auf diesen Block.
• B, die Datenbitmap, die den Block als belegt markiert.

Erreichen alle drei das Speichergerät, ergibt sich die beabsichtigte konsistente Aktualisierung. Erreicht keiner das Speichergerät, bleibt der alte konsistente Zustand erhalten. Die Gefahr liegt in den sechs teilweisen Kombinationen. Das Gerät kann Anfragen umordnen; sie ohne Warten in einer bestimmten Reihenfolge auszugeben, legt daher die Abschlussreihenfolge nicht fest.

Ordne jedes Teilergebnis ein

Eine Inkonsistenz entsteht, wenn Metadaten nicht übereinstimmen, etwa wenn ein Inode einen Block beansprucht, dessen Belegungsbit frei anzeigt. Der Allokator könnte denselben Block dann einer anderen Datei zuweisen. Ein Speicherplatzleck belegt Speicherplatz, den keine Datei erreichen kann. Datenmüll kann schwerer zu erkennen sein: I und B stimmen vollständig überein, obwohl Db nie angekommen ist.

Db allein verursacht kein Speicherplatzleck, weil die Bitmap die Wiederverwendung dieses Blocks weiterhin erlaubt. Bytes an eine freie Stelle zu schreiben ist nicht dasselbe, wie sie zuzuweisen. B allein verursacht ein Speicherplatzleck, weil die Belegung ohne zugehörigen Zeiger erhalten blieb.

Trenne Struktur und Bedeutung

Ein Prüfprogramm kann Zeiger mit Bitmaps vergleichen. Es kann im Allgemeinen nicht feststellen, ob plausible Bytes diejenigen sind, die ein Programm speichern wollte. Das Ergebnis mit I und B zeigt diese Grenze: Eine strukturell gültige Datei kann falsche Inhalte haben.

Der gewünschte Übergang ist über die Aktualisierung hinweg atomar: Die Wiederherstellung führt zum vollständigen alten oder zum vollständigen neuen Zustand. Ein einfaches Speichermodell bietet atomare Schreibvorgänge nur für einen Sektor, traditionell 512 Byte. Mehrere Dateisystemblöcke überschreiten diese Einheit, sodass das Dateisystem ein stärkeres Protokoll aufbauen muss. Die tatsächlichen Garantien für atomare Schreibvorgänge hängen vom Gerät und der Schnittstelle ab; der Commit-Datensatz des Journalprotokolls muss in die unterstützte atomare Einheit passen.

Pufferung erhöht die Anzahl der Änderungen, die verloren gehen können, ist aber nicht die Grundursache. Selbst wenn jeder Schreibvorgang sofort ausgegeben wird, bleibt zwischen den getrennten Abschlüssen eine mögliche Absturzstelle. Auch das Erzeugen, Umbenennen und Löschen von Dateien ändert mehrere Strukturen. Um ihre Fehlerzustände zu verstehen, beginnst du mit derselben Übung: Bestimme jeden geänderten Block und frag dich, was geschieht, wenn nur ein Teil erhalten bleibt.

Ein Dateisystemprüfprogramm repariert Beziehungen zwischen gespeicherten Strukturen, nachdem ein Schaden eingetreten ist. Seine Stärke ist der umfassende Blick auf Metadaten; seine Schwächen sind der Aufwand des Durchsuchens und die fehlende Kenntnis der beabsichtigten Dateiinhalte.

Rekonstruiere die Belegung

fsck, die Abkürzung für die Dateisystemprüfung, untersucht ein nicht sauber geschlossenes Dateisystem vor dem normalen Einhängen. Es prüft, ob die Größe und die Zähler des Superblocks plausibel sind, und kann einen Sicherungs-Superblock verwenden, wenn die Hauptkopie beschädigt ist.

Anschließend durchsucht es Inodes und indirekte Blöcke, um festzustellen, auf welche Datenblöcke Dateien tatsächlich verweisen. Aus diesen Informationen über die Zuordnung stellt es die Belegungsbitmaps wieder her. Zeigt ein ansonsten gültiger Inode auf Block 74, während die Bitmap 74 als frei bezeichnet, muss die Bitmap auf belegt geändert werden. Würde man lediglich der Bitmap vertrauen, könnte eine spätere Zuweisung die Daten der Datei überschreiben.

Die umgekehrte Abweichung ist ein in der Bitmap als belegt markiertes Bit ohne zugehörigen Inode-Zeiger. Das Wiederherstellen der Bitmap kann diesen Speicherplatz zurückgewinnen. Die Reparatur stellt eine konsistente Beziehung her; beliebige fehlende Anwendungsbytes kann sie nicht rekonstruieren.

Prüfe Objekte, Namen und Links

Jeder zugewiesene Inode braucht einen gültigen Typ, etwa reguläre Datei, Verzeichnis oder symbolischer Link. Ein Inode, der nicht repariert werden kann, wird zurückgesetzt und die Belegungsinformationen werden angepasst.

Durch das Durchlaufen des Baums von der Wurzel aus kann fsck die Verzeichnisverweise auf jeden Inode zählen. Es vergleicht diese beobachteten Verweise mit den gespeicherten Linkzählern und korrigiert Fehler. Ein zugewiesener Inode, den kein Verzeichnis erreicht, kann nach lost+found verschoben werden. So erhält der wiederhergestellte Inhalt einen erreichbaren Namen, ohne dass sein ursprünglicher Pfad bekannt sein muss.

Weitere Prüfungen umfassen:

• Doppelte Zuordnung: Zwei Inodes beanspruchen einen Datenblock. Eine Reparatur kann einen Inode zurücksetzen oder jeder Datei eine eigene Kopie geben.
• Ungültige Adressen: Zeiger außerhalb des gültigen Bereichs des Dateisystems müssen zurückgesetzt werden.
• Verzeichnisstruktur: . und .. müssen gültig sein und in der einfachen Verzeichnisstruktur die ersten Einträge belegen, Einträge müssen auf zugewiesene Inodes verweisen und Verzeichnisse dürfen nicht mehrere übergeordnete Verzeichnisse haben.

Diese Prüfungen wirken zusammen. Das Zurücksetzen eines ungültigen Inodes ändert auch, welche Blöcke belegt sein sollten und welche Verzeichniseinträge gültig bleiben. Eine Reparatur braucht daher einen zusammenhängenden Blick auf die Metadaten und nicht nur eine Liste einzelner verdächtiger Bits.

Verstehe, was ein fehlerfreies Ergebnis aussagt

Angenommen, Inode und Bitmap eines Anhängevorgangs haben die Festplatte erreicht, die Daten aber nicht. Der Zeiger liegt im gültigen Bereich, das Belegungsbit ist gesetzt und die Linkstruktur ist gültig. fsck findet keine Abweichung in den Metadaten, die es reparieren könnte. Die Datei kann die Prüfung bestehen und dennoch in ihrem neu hinzugefügten Bereich alte Bytes enthalten.

Die Laufzeit hängt außerdem hauptsächlich von der Größe des Dateisystems ab, nicht vom Umfang der Änderungen vor einem Absturz. Ein Absturz während einer Aktualisierung von drei Blöcken kann dennoch das Durchsuchen aller Metadaten erfordern. Bei einem großen Dateisystem kann das Minuten bis Stunden dauern; währenddessen ist der normale Zugriff nicht verfügbar.

Journaling verringert den üblichen Wiederherstellungsaufwand nach einem Absturz, indem es kürzlich erfolgte Aktualisierungen aufzeichnet. Es macht ein Prüfprogramm nicht überflüssig: Softwarefehler oder ausfallende Hardware können Strukturen auf eine Weise beschädigen, die das erneute Einspielen des Journals nicht reparieren kann. fsck bleibt für diese Fälle ein Reparaturwerkzeug.

Ein Journal zeichnet eine Aktualisierung auf, bevor das Dateisystem ihre gewöhnlichen Speicherpositionen überschreibt. Nach einem Absturz zeigt diese Aufzeichnung der Wiederherstellung, welche vollständigen Änderungen erneut ausgeführt werden können. Das ist Vorausprotokollierung. Ext3, ext4, XFS und NTFS nutzen Journaling, obwohl sich ihre genauen Protokollformate unterscheiden.

Beschreibe eine Aktualisierung als Transaktion

Bei einem Anhängevorgang protokolliert Daten-Journaling Kopien des neuen Inodes I, der Bitmap B und des Datenblocks Db. Ein Transaktionsanfangsdatensatz, TxB, enthält eine Kennung und die endgültigen Zielpositionen der Blöcke. Ein Transaktionsenddatensatz, TxE, enthält die zugehörige Kennung und markiert den Abschluss.

Das Protokollieren vollständiger Ersatzblockabbilder ist physische Protokollierung. Das Protokollieren einer Operationsbeschreibung heißt dagegen logische Protokollierung. Die physische Wiederholung hat eine nützliche Eigenschaft: Wird dasselbe Abbild erneut an dieselbe Adresse geschrieben, hat das dieselbe Wirkung. Die Wiederherstellung kann daher einen Checkpoint wiederholen, der vor dem Absturz teilweise abgeschlossen wurde.

Setze den Abschluss hinter die Nutzdaten

Das grundlegende Protokoll hat vier Phasen:

1. Journal schreiben: TxB sowie I, B und Db ins Journal schreiben und auf den dauerhaften Abschluss warten.
2. Commit: TxE schreiben und warten. Die Transaktion ist nun abgeschlossen.
3. Checkpoint: I, B und Db aus dem Journal an ihre endgültigen Positionen kopieren.
4. Freigeben: Den Journalplatz dieser Transaktion für eine spätere Wiederverwendung freigeben.

TxE darf nicht vor seinen Nutzdaten dauerhaft gespeichert werden. Würden alle fünf Blöcke ohne Garantie für die Reihenfolge ausgegeben, könnte ein Gerät TxB und TxE abschließen und Db ungeschrieben lassen. Die Wiederherstellung würde eine unvollständige Transaktion für gültig halten. Im Grundmodell passt TxE in einen atomaren Sektorschreibvorgang und ist daher als vollständiger Commit-Datensatz entweder vorhanden oder nicht vorhanden.

Auch Schreibcaches von Geräten müssen die Grenze für dauerhafte Speicherung beachten. Das Leeren des Caches oder erzwungene Schreibvorgänge verhindern, dass ein flüchtiger Gerätecache dem Protokoll sichere Nutzdaten vorgaukelt, obwohl ein Stromausfall sie noch löschen könnte.

Stelle den Zustand nach zwei Absturzpunkten wieder her

Ein Absturz nach den Nutzdaten, aber vor TxE, hinterlässt eine nicht abgeschlossene Transaktion. Die Wiederherstellung ignoriert sie und behält den alten Dateizustand bei.

Ein Absturz nach TxE, aber während des Checkpointings, hinterlässt eine abgeschlossene Transaktion. Die Wiederherstellung schreibt alle ihre Abbilder der Reihe nach an ihre endgültigen Positionen. Einige Schreibvorgänge wiederholen möglicherweise bereits erledigte Arbeit, was für diese Blockabbilder harmlos ist. Das ist Wiederherstellung durch erneutes Ausführen. Journalplatz darf erst wiederverwendet werden, wenn die abgeschlossenen Abbilder ihre endgültigen Positionen erreicht haben.

Das Journal ist ein Ringprotokoll. Sein Superblock verfolgt den aktiven Bereich und erlaubt so die Wiederverwendung abgeschlossener Bereiche. Werden mehrere Aktualisierungen zu einer Transaktion gebündelt, kann ein gemeinsam genutzter Verzeichnisblock oder eine Bitmap einmal protokolliert werden. Das standardmäßige Commit-Intervall von ext4 beträgt 5 Sekunden, sodass der Abschluss nicht automatisch unmittelbar nach jedem Anwendungsschreibvorgang erfolgt.

Unterscheide Prüfsummen und Dauerhaftigkeit

Eine Transaktionsprüfsumme kann fehlende oder unvollständig geschriebene Nutzdatenblöcke aufdecken, selbst wenn ein Commit-Datensatz vorhanden ist. Ein prüfsummenbasiertes Protokoll kann Journalschreibvorgänge gemeinsam ausgeben und nur Transaktionen akzeptieren, deren Prüfung erfolgreich ist. Prüfsummen erkennen unvollständige Datensätze; das Leeren von Caches stellt sicher, dass bestätigte Bytes tatsächlich erhalten bleiben.

Ein gepufferter, nicht abgeschlossener Schreibvorgang einer Anwendung kann weiterhin verschwinden. Ein Programm, das einen dauerhaften Abschluss benötigt, nutzt fsync und prüft den Erfolg.

Daten-Journaling schreibt Dateiinhalte ins Journal und dann an ihre endgültigen Positionen. Das Protokollieren allein der Metadaten verringert diese Zugriffe, doch die Reihenfolge von Daten und Metadaten bestimmt weiterhin, was bei der Wiederherstellung sichtbar werden kann.

Schreibe Daten vor dem Abschluss ihrer Zeiger

Beim geordneten Metadaten-Journaling geht Db direkt an seine endgültige Position. TxB, I und B gehen ins Journal. Diese beiden Gruppen von Schreibvorgängen können parallel ablaufen, müssen aber beide abgeschlossen sein, bevor TxE die Metadaten festschreibt. Nach dem Abschluss können I und B per Checkpoint übertragen und der Journalplatz freigegeben werden.

Die Abhängigkeit ist entscheidend: Der Block, den ein Zeiger bezeichnet, muss bereit sein, bevor dieser Zeiger wiederhergestellt werden kann. Wird I zuerst festgeschrieben, kann die Wiederherstellung einen gültigen Zeiger auf Bytes eines früheren Nutzers des Blocks einsetzen. Die Metadaten würden übereinstimmen, ohne die beabsichtigten Daten zu enthalten.

Der geordnete Modus ist der Standard. Metadaten-Journaling allein bedeutet nicht, dass der geordnete Modus verwendet wird: Der Writeback-Modus kann strukturell intakte Dateien mit veralteten Inhalten wiederherstellen. Der Daten-Journalingmodus veranschaulicht das vollständige Protokoll, verursacht aber einen zweiten Schreibvorgang für die Dateidaten.

Verhindere, dass erneutes Einspielen einen wiederverwendeten Block beschädigt

Verzeichnisinhalte zählen als Metadaten. Angenommen, ein Verzeichnisblock an Adresse 1000 wird protokolliert, dann wird das Verzeichnis entfernt und dieselbe Adresse für gewöhnliche Dateidaten verwendet. Diese neuen Benutzerdaten werden im Modus mit reinem Metadaten-Journaling nicht protokolliert. Das erneute Einspielen des alten Verzeichnisabbilds nach einem Absturz würde die Bytes der neuen Datei überschreiben.

Ein abgeschlossener Widerrufsdatensatz weist die Wiederherstellung an, protokollierte Kopien dieses Blocks aus Transaktionen bis einschließlich der widerrufenden Transaktion zu überspringen. Er verbietet nicht jede zukünftige Verwendung der Adresse. Protokolliert eine spätere Transaktion diesen Block erneut, kann das spätere Abbild weiterhin eingespielt werden. Diese zeitliche Grenze unterscheidet den Widerruf von einer dauerhaften Markierung eines Blocks als unbrauchbar.

Vergleiche Alternativen

Soft Updates setzen Abhängigkeiten zwischen gewöhnlichen Schreibvorgängen ohne Journal durch. Das Schreiben initialisierter Daten vor einem Zeiger verhindert erreichbaren Datenmüll, obwohl unterbrochene Operationen Speicherplatzlecks hinterlassen können, die eine spätere Hintergrundprüfung zurückgewinnt. Das FFS von FreeBSD nutzt diesen Ansatz. Die Verfolgung aller Abhängigkeiten erschwert die Implementierung.

Copy-on-Write (COW) schreibt geänderte Blöcke an ungenutzte Positionen und veröffentlicht den neuen Baum durch eine atomare Umstellung des Wurzelzeigers. Der alte Baum bleibt bis zur Umstellung verfügbar. ZFS, Btrfs und WAFL nutzen verwandte Entwürfe; das Erhalten alter Blöcke ermöglicht auch Snapshots.

Forschungsentwürfe mit Rückverweisen speichern die Zuordnung von Daten zurück zu Inodes, sodass unvollständige Aktualisierungen erkennbare Abweichungen hinterlassen. Optimistische Absturzkonsistenz verringert das Warten und nutzt Prüfsummen und andere Prüfungen, um unvollständige Arbeit zu erkennen. Jeder Ansatz wägt Schreibzugriffe, Wiederherstellungsgarantien und Implementierungsaufwand gegeneinander ab. Geordnetes Metadaten-Journaling hält die Wiederherstellung kurz und schreibt gewöhnliche Dateidaten einmal.

Ein logstrukturiertes Dateisystem wandelt verstreute kleine Aktualisierungen in große sequenzielle Schreibvorgänge um. Das hilft bei einer Festplatte mit hoher Übertragungsrate, deren Positionierungs- und Rotationsverzögerungen weiterhin aufwendig sind.

Sammle Aktualisierungen in einem Segment

Das von Rosenblum und Ousterhout entwickelte und 1991 veröffentlichte LFS aus Berkeley ging von veränderten Arbeitslasten aus. Größere Arbeitsspeicher bedienten mehr Lesezugriffe aus dem Cache, sodass Schreibvorgänge einen größeren Anteil der Festplattenzugriffe ausmachten. Die sequenzielle Bandbreite wuchs schneller als die Positionierungsgeschwindigkeit. FFS benötigte beim Erzeugen einer kleinen Datei weiterhin mehrere kurze Schreibvorgänge für Metadaten und Daten, und auch bei Paritäts-RAID waren kleine Schreibvorgänge ungünstig.

LFS puffert geänderte Daten, Inodes und Zuordnungsinformationen gemeinsam im Speicher. Es schreibt sie als ein großes Segment in einen ungenutzten Festplattenbereich. Die Aktualisierung eines Blocks erzeugt eine neue Version an einer neuen Adresse; die vorherige Version bleibt physisch vorhanden, bis die Bereinigung ihr Segment zurückgewinnt.

Segmente amortisieren die Positionierung ebenso wie große FFS-Teilstücke. Bei einer Rate R, einer Positionierungszeit T und einem gewünschten Übertragungszeitanteil F beträgt die gepufferte Größe:

Bei 200 MB/s und 5 ms erfordern 95 % genau 19 MB. Die Übertragung dauert 95 ms, die Positionierung 5 ms und die effektive Rate beträgt 19 MB pro 0,1 s = 190 MB/s. Ein hoher angestrebter Anteil kann ein Segment erfordern, das größer als die üblichen Hunderte Kilobyte bis mehrere Megabyte ist. Die erforderliche Größe ergibt sich aus dem Gerät und dem Ziel, nicht aus dem Wort „Segment“.

Finde einen Inode, der seinen Ort immer wieder ändert

Die Formel für eine feste Inode-Tabelle funktioniert nicht mehr: Jede Inode-Aktualisierung wird an eine neue Adresse geschrieben. LFS ergänzt eine Inode-Zuordnungstabelle, kurz imap, die jede Inode-Nummer auf ihre neueste Festplattenadresse abbildet. Aktualisierte imap-Stücke werden neben die Inodes, die sie beschreiben, in das Protokoll geschrieben.

Ein fester Checkpoint-Bereich (CR) hält fest, wo sich die neuesten imap-Stücke befinden. Er wird periodisch aktualisiert, zum Beispiel alle 30 Sekunden, sodass der gelegentliche Schreibvorgang an einer festen Position die Zugriffe nicht dominiert.

Die Suchfolge lautet:

1. Lies beim Einhängen den CR, um die aktuellen imap-Stücke zu finden.
2. Lade die imap in den Speicher.
3. Suche die angeforderte Inode-Nummer in der imap.
4. Lies diesen neuesten Inode und folge seinen Datenzeigern.

Sobald die imap im Cache liegt, folgen gewöhnliche Dateilesezugriffe weitgehend demselben Weg vom Inode zu den Daten wie in FFS. Die zusätzliche Zuordnung macht das Verschieben mit vertretbarem Aufwand möglich, ohne die stabile Identität der Datei zu ändern.

Halte Verzeichniseinträge stabil

Ein Verzeichnis speichert Namen und Inode-Nummern. Wird /docs/report.txt aktualisiert, wechselt sein Inode den Ort, behält aber seine Nummer. Die imap ändert sich; der Verzeichniseintrag muss sich allein wegen dieser Verschiebung nicht ändern.

Ohne diese zusätzliche Zuordnung müsste ein Verzeichnis mit physischen Inode-Adressen jedes Mal neu geschrieben werden, wenn sich ein untergeordneter Inode verschiebt. Sein eigener Inode würde sich dann ebenfalls verschieben und eine Änderung im übergeordneten Verzeichnis erzwingen, und so weiter bis zur Wurzel. Die imap unterbricht dieses rekursive Aktualisierungsproblem.

LFS macht Schreibvorgänge sequenziell, nicht alle Lesezugriffe. Unveränderte Blöcke einer Datei können in älteren Segmenten bleiben, während spätere Versionen anderer Blöcke an andere Stellen wandern. Beim Lesen dieser Datei können weiterhin Positionierungen zwischen Segmenten nötig sein; große Speichercaches gehören zur Motivation des Entwurfs.

Das Schreiben neuer Versionen an ungenutzte Stellen lässt alte Bytes physisch zurück. LFS muss alte, nicht erreichbare Versionen von gültigen Blöcken unterscheiden, große freie Bereiche zurückgewinnen und nach einem Absturz eine nutzbare Zuordnung wiederherstellen.

Bereinige ganze Segmente

Der Cleaner liest teilweise belegte Segmente, kopiert ihre gültigen Blöcke in weniger neue Segmente und gibt die alten Segmente frei. Enthalten vier gleich große Segmente jeweils ein Viertel gültige Daten, füllen ihre gültigen Daten zusammen ein neues Segment. Die Freigabe der vier alten Segmente nach dem Kopieren gewinnt drei Segmente nutzbarer Kapazität.

Das Bereinigen ganzer Segmente erhält große zusammenhängende Bereiche für spätere sequenzielle Schreibvorgänge. Das Kopieren verursacht Aufwand: Gültige Blöcke werden erneut gelesen und geschrieben, obwohl keine Anwendung sie geändert hat. Bei einer fast vollen Festplatte mit überwiegend gültigen Daten in den Segmenten muss möglicherweise viel kopiert werden, um wenig freien Platz zurückzugewinnen.

Entscheide, ob ein Block gültig ist

Eine Segmentzusammenfassung bezeichnet den zu jedem Block gehörenden Inode und den logischen Dateiblockoffset. Um einen Block an Adresse A zu prüfen, suchst du mithilfe der imap den neuesten zugehörigen Inode. Folge seinem Zeiger für den gespeicherten logischen Block. Ist der Zeiger weiterhin gleich A, ist dies die gültige Version. Zeigt er anderswohin, ist A veraltet.

Eine Zusammenfassung ordnet beispielsweise Adresse 600 dem Inode 14 und dem logischen Block 2 zu. Der aktuelle Inode 14 verweist für den logischen Block 2 auf Adresse 920. Block 600 ist ungültig, selbst wenn seine Bytes wie gültige Daten aussehen. Die Gültigkeit hängt von der aktuellen Erreichbarkeit ab, nicht davon, wie kürzlich ein Block geschrieben wurde oder ob sein Inhalt nützlich aussieht.

Versionsnummern beschleunigen das Aussortieren. Wird eine Datei gelöscht oder auf null gekürzt, steigt ihre Version in der imap. Ein Segmentblock mit einer älteren Version kann als ungültig eingestuft werden, ohne den Inode zu lesen.

Die Bereinigungsstrategie berücksichtigt auch erwartete Änderungen. Heiße Segmente enthalten häufig überschriebene Blöcke; durch Warten können weitere ihrer Blöcke ungültig werden, ohne sie zu kopieren. Kalte Segmente ändern sich wenig, sodass die ursprüngliche LFS-Strategie sie früher bereinigt. Die Strategie muss den Anteil gültiger Daten, das Alter und den verfügbaren Platz gegeneinander abwägen; die Temperatur eines Segments allein misst nicht den unmittelbaren Kopieraufwand.

Stelle die Zuordnung und kürzliche Änderungen wieder her

LFS hält zwei Checkpoint-Bereiche an gegenüberliegenden Enden der Festplatte vor und aktualisiert sie abwechselnd. Jede Aktualisierung schreibt einen Kopf mit Zeitstempel, den Hauptteil und einen abschließenden passenden Zeitstempel. Die Wiederherstellung wählt den neuesten Bereich, dessen Anfang und Ende übereinstimmen. Eine unterbrochene neuere Aktualisierung verdrängt keinen älteren vollständigen Checkpoint.

Der Checkpoint enthält möglicherweise nicht die zuletzt abgeschlossenen Segmente. Die Wiederherstellung führt daher vom darin gespeicherten Protokollende aus eine Vorwärtswiederherstellung durch: Sie findet gültige spätere Aktualisierungen und wendet sie an, um die aktuelle Zuordnung wiederherzustellen. Daten, die nie eine gültige wiederherstellbare Aktualisierung bildeten, können nach einem Stromausfall nicht aus dem Speicher rekonstruiert werden.

Verwandte Copy-on-Write-Systeme bewahren alte Blöcke auf, um Snapshots zu unterstützen; ZFS, Btrfs und WAFL teilen diese Grundidee. SSD-Controller nutzen häufig logstrukturierte Flash Translation Layers, während F2FS logstrukturierte Ideen auf Dateisystemebene für Flash-Speicher anwendet. Alle benötigen weiterhin eine Möglichkeit, den von veralteten Versionen hinterlassenen Platz zurückzugewinnen.

Ein verteiltes Dateisystem hält Dateien auf einem Server vor, während Programme auf Client-Rechnern vertraute Dateiaufrufe nutzen. Der Client übersetzt diese Aufrufe in Netzwerkanfragen. Verzögerungen und Ausfälle werfen eine Frage auf, die bei lokalen Aufrufen meist verborgen bleibt: Was soll ein Client tun, wenn er nicht erkennen kann, ob eine Anfrage abgeschlossen wurde?

Halte den Zustand offener Dateien auf dem Client

Das Network File System (NFS) von Sun entstand in den 1980er-Jahren. NFSv2 machte seinen Server hinsichtlich offener Dateien zustandslos. Der Server speichert Dateien, merkt sich aber nicht die Deskriptoren oder aktuellen Offsets jedes Clients. Jede Anfrage enthält genug Informationen zur Ausführung ohne eine vorherige Öffnungsanfrage.

Ein Dateihandle bezeichnet das Server-Volume, die Inode-Nummer und die Inode-Generation. Die Generation ändert sich, wenn eine Inode-Nummer wiederverwendet wird. Dadurch kann ein altes Handle nicht versehentlich eine andere Datei am wiederverwendeten Platz bezeichnen.

Um /home/ana/notes.txt zu öffnen, beginnt der Client mit einem Wurzel-Handle und sendet LOOKUP für home, ana und notes.txt. Das resultierende Handle behält er in seinem eigenen Zustand für offene Dateien. Das Lesen der ersten 4 KiB wird zu einer READ-Anfrage mit diesem Handle, Offset 0 und Anzahl 4.096. Das Schließen des lokalen Deskriptors benötigt keine NFSv2-CLOSE-Anfrage, weil der Server keinen offenen Eintrag freizugeben hat.

Wiederhole eine Anfrage ohne erneute Wirkung

Trifft keine Antwort ein, kann der Client nicht zwischen einer verlorenen Anfrage, einem nicht verfügbaren Server und einer verlorenen Antwort unterscheiden. Nach einer Zeitüberschreitung sendet er die Anfrage erneut.

Eine Operation ist idempotent, wenn ihre Wiederholung dieselbe Wirkung wie ihre einmalige Ausführung hat. READ, LOOKUP und GETATTR ändern gespeicherte Inhalte nicht. Ein WRITE mit ausdrücklich angegebenem Offset schreibt in diesem Modell bei einer Wiederholung ebenfalls sicher dieselben Bytes an dieselbe Stelle. Die Wiederholung einer Anfrage mit der Anweisung „Hänge diese Bytes am aktuellen Ende an“ würde dagegen eine zweite Kopie hinzufügen; der Offset in einem NFS-WRITE vermeidet diese Mehrdeutigkeit.

Einige Anfragen erfordern besondere Sorgfalt. Wird ein erfolgreiches MKDIR nach dem Verlust seiner Antwort wiederholt, kann „existiert bereits“ zurückgegeben werden. Das Verzeichnis ist vorhanden, aber die wiederholte Antwort unterscheidet sich von der ursprünglichen Erfolgsmeldung. Zustandslose Wiederherstellung macht nicht jede Operation zu einer einfach wiederholbaren Anfrage.

Mache Bestätigungen verlässlich

NFSv2 muss ein WRITE dauerhaft speichern, bevor es den Erfolg bestätigt. Andernfalls könnte der Server einen Block bestätigen, ihn bei einem Absturz aus dem Speicher verlieren und dann spätere Blöcke annehmen. Der Client würde glauben, dass alle Schreibvorgänge erfolgreich waren, während der Datei eine Aktualisierung in der Mitte fehlt.

Bestätigungen nach dauerhafter Speicherung vermeiden diesen Fehler auf Kosten der Leistung. NFSv3 führte nicht dauerhaft bestätigte Schreibvorgänge ein, gefolgt von COMMIT, sodass mehrere Schreibvorgänge gemeinsam dauerhaft werden können. Der Client muss eine nicht dauerhafte Bestätigung von einem dauerhaften Abschluss unterscheiden.

Unterscheide die Protokollversionen

Ein zustandsbehaftetes Protokoll braucht Mechanismen, um den Zustand offener Dateien und Sperren nach einem Serverneustart wiederherzustellen und den Zustand abgestürzter Clients freizugeben. NFSv4 nimmt diese Komplexität bewusst in Kauf: Es hat OPEN, CLOSE, Sperren und zeitlich begrenzte Leases, die Clients erneuern. Der Linux-Client versucht normalerweise zuerst Version 4.2 und greift bei Bedarf auf ältere Versionen zurück. Die Bezeichnung von NFSv2 als zustandslos beschreibt daher nicht jede NFS-Version.

Clientseitiges Caching spart Netzwerkübertragungen, erzeugt aber mehrere Kopien gemeinsam genutzter Dateien. Die Konsistenzregel bestimmt, wann ein anderer Rechner eine alte Kopie nicht mehr verwenden darf und die Änderungen des schreibenden Clients holen muss.

Prüfe NFS-Caches an Grenzen der gemeinsamen Nutzung

Bei Close-to-Open-Konsistenz von NFS sendet das Schließen einer geänderten Datei gepufferte Schreibvorgänge an den Server. Ein späteres Öffnen auf einem anderen Client prüft die Aktualität und sieht diese Änderungen. GETATTR oder eine entsprechende Prüfung vergleicht Serverattribute mit zwischengespeicherten Attributen und verwirft veraltete zwischengespeicherte Daten, wenn eine Änderung erkannt wird.

Eine Prüfung bei jedem Zugriff würde den Server belasten. Linux speichert Attribute regulärer Dateien standardmäßig für Zeiträume zwischen 3 und 60 Sekunden zwischen. Ein Prozess, der eine Datei geöffnet hält, kann daher zwischen den Prüfungen veraltete zwischengespeicherte Daten lesen. Das Öffnen ist eine stärkere Grenze für die gemeinsame Nutzung als ein beliebiger Lesezugriff über einen bereits offenen Deskriptor. Das Close-to-Open-Verhalten verspricht keine sofortige Sichtbarkeit jedes einzelnen Schreibvorgangs.

Nutze ganze Dateien mit AFS-Callbacks erneut

Das Andrew File System (AFS) wurde in den 1980er-Jahren an der Carnegie Mellon University entworfen, um viele Clients pro Server zu unterstützen. Existiert keine gültige lokale Kopie, holt das Öffnen die gesamte Datei auf die lokale Festplatte. Lese- und Schreibvorgänge nutzen dann diese Kopie, und das Schließen einer geänderten Datei sendet die gesamte neue Version an den Server. Eine gültige zwischengespeicherte Kopie kann erneut geöffnet werden, ohne sie nochmals herunterzuladen.

AFSv1 prüfte die Gültigkeit bei jedem Öffnen und überließ die Pfadauflösung dem Server. AFSv2 verlagerte die Pfadauflösung auf Clients, die Verzeichnisse zwischenspeichern, und führte Callbacks ein. Der Server verspricht, einen Client zu benachrichtigen, wenn sich ein zwischengespeichertes Objekt ändert. Bis dieses Versprechen aufgehoben wird, nutzt der Client seine Kopie ohne wiederholte Prüfungen. Seine Dateikennung enthält ein Volume, eine Dateikennung und einen Eindeutigkeitswert.

Verfolge zwei überlappende Sitzungen

Angenommen, die Clients A und B öffnen beide eine Datei. A ändert seine lokale Kopie und schließt die Datei, wodurch die neue Version an den Server gesendet wird. Der Server hebt die Callbacks der anderen Clients auf. Ein späteres Öffnen auf B holt die neue Version, aber die bereits offene Sitzung von B behält ihre vorhandene Kopie bis zum Schließen und erneuten Öffnen.

Ändern beide Rechner ihre Kopien, ersetzt der zuletzt schließende die gesamte Datei auf dem Server. Blöcke aus den beiden Kopien werden nicht zusammengeführt. Auch zwei Änderungen an unterschiedlichen Offsets können zum Verlust der Änderungen eines Clients führen, weil nach dem Prinzip der zuletzt Schließende gewinnt eine vollständige Version ausgewählt wird. Prozesse auf einem Client-Rechner sehen die Schreibvorgänge der jeweils anderen sofort.

Callbacks sind Serverzustand. Nach einem Clientneustart sind zwischengespeicherte Dateien verdächtig, weil Benachrichtigungen verpasst worden sein können. Nach einem Serverneustart müssen Clients die verlorenen Callback-Zusagen durch Lebenszeichen oder eine Servermitteilung erkennen und die Gültigkeit erneut prüfen.

Stimme das Caching auf die Arbeitslast ab

AFS bot außerdem einen globalen Namensraum, Zugriffskontrolllisten und von Administratoren verwaltete Volumes. AFSv2 erhöhte die Anzahl der Clients pro Server historisch auf etwa 50 gegenüber rund 20 bei AFSv1. Keine der beiden Cache-Regeln ersetzt ausdrückliche Koordination, etwa Dateisperren, wenn Programme sichere gemeinsame Aktualisierungen benötigen.