Wie funktionieren Linux-Dateisysteme

Speicher-Tricks

Linux unterstützt eine Vielzahl eigener Dateisysteme. Dieser Artikel erklärt, worin sie sich unterscheiden und gibt einige Tipps für den praktischen Einsatz.
Auch wenn auf der Packung "Cloud Computing" steht, steckt dahinter eigentlich Virtualisierungstechnologie mit cleveren Management-Funktionen. ADMIN 05/2010 ... (mehr)

Freie Auswahl ist eine tolle Sache und der Linux-Kernel bietet dem Anwender fürwahr eine große Auswahl an unterstützten Dateisystemen. Dieser Artikel bespricht, welche Anforderungen an Dateisysteme es gibt und wie die einzelnen Implementierungen sie angehen. Diese Entwicklerperspektive soll Aufschluss darüber liefern, welches Linux-Dateisystem am besten für welchen Zweck geeignet ist.

Probleme, Probleme

Eigentlich kann es ja nicht so schwer sein, ein Dateisystem zu schreiben, denn schließlich geht es ja nur darum, ein paar Daten auf einer Festplatte abzuspeichern und sie irgendwann wieder zu lesen. Bleibt also nicht viel mehr zu tun, als den Überblick über die Metadaten wie Datei- und Verzeichnisnamen und ihr Verhältnis zueinander zu behalten und die Daten selbst byteweise zu speichern. Zum Beispiel könnte es die Metadaten einfach in einer Tabelle ablegen, die den Dateinamen, die Größe, die Änderungszeit und so weiter festhält, und natürlich, wo die Inhalte der Datei liegen.

In diesem Stadium erscheint das Dateisystem noch einigermaßen einfach. Man wird durch Locks oder Ähnliches sicherstellen müssen, dass die Metadaten konsistent bleiben, wenn verschiedene Prozesse sie verändern wollen, aber das ist schließlich auch keine Geheimwissenschaft. Eventuell wäre noch ein Index für die Metadaten-Tabelle praktisch, um Verzeichnisse und Dateien schneller zu finden.

Was aber, wenn einmal der Strom ausfällt? Es wäre schon nicht schlecht, wenn man nach dem Wiedereinschalten alle Daten vorfinden würde, die vorher da waren. Das sollte auch der Fall sein, wenn der Stromausfall während des Schreibens passiert. Vielleicht fehlt ein Teil der gerade geschrieben Daten, aber sonst sollte alles ok sein. Außerdem möchte man beim Hochfahren vermutlich nicht einige Stunden lang auf den Dateisystem-Check der neuen Terabyte-Platten warten. Das arme Dateisystem sollte nur ein paar Sekunden lang dafür brauchen, sich daran zu erinnern, welche Dinge es in den kritischen Sekunden vor dem Crash gemacht hat.

Jetzt wird es allerdings etwas schwieriger. Wie kann der Filesystem-Check wissen, ob ein bestimmter Block in den Metadaten auf dem neuesten Stand ist oder nicht? Oder ob er gar nur halb geschrieben wurde, als der Strom ausfiel? Und was ist dann mit dem Index auf die Metadaten? Es könnte ja sein, dass die eine Hälfte des Index schon geschrieben wurde, während sich die andere Hälfte gerade noch im Hauptspeicher befand. Gerade die wichtigen Metadaten will man auf gar keinen Fall verlieren, egal was passiert. Auch der Index sollte in Ordnung sein, denn wenn sich das Dateisystem darauf nicht verlassen kann. Selbst wenn das Dateisystem merkt, dass der Index kaputt ist, und ihn daraufhin neu anlegt, kann das eine ziemlich lange Zeit dauern – und man findet sich genau in dem Dateisystem-Check-Marathon wieder, den man eigentlich vermeiden wollte.

Stattdessen könnte das Dateisystem protokollieren, wann es welche Metadaten geändert hat und regelmäßig zu festgelegten Zeitpunkten erst eine neue Metadaten-Tabelle aufbauen und dann von der alten zur neuen umschalten. So aht das System immer eine gültige Metadaten-Tabelle mit Index. Im Fall eines Crashs kann es die aktuelle Version verwenden und das Journal soweit wie möglich aktualisieren. Auch wenn das wohl funktioniert, ist es immer noch recht langsam, den Index bei jeder Änderung neu aufzubauen. Schließlich soll ein Dateisystem ja nicht nur sicher sein, sondern auch schnell.

Wenn man sich überlegt, wie Verzeichnisse funktionieren, erkennt man schnell die Bedeutung eines guten Index. Normalerweise bekommt jede Datei eine eindeutige Nummer zugewiesen, die so genannte I-Node-Nummer. Die Implementierung eines Verzeichnisses enthält dann vermutlich die I-Nodes aller Dateien, die es enthält. Um zum Beispiel den Eigentümer und die Rechte für eine Datei herauszufinden, wird ein Dateisystem über die I-Node-Nummer in der Metadaten-Tabelle nachsehen. Deshalb ist der Lookup von Metadaten mit dem I-Node als Schlüssel ein der häufigsten Operationen.

Wenn ein Dateisystem die Zahl der verfügbaren I-Nodes von vornherein beschränkt und für sie beim Anlegen des Dateisystem eine zusammenhängende Tabelle anlegt, kann es die I-Node direkt verwenden, um die Metadaten zu finden. Wenn zum Beispiel 128 I-Nodes in eine Seite passen, dann befindet sich I-Node 600 in der fünften Seite der Metadaten-Tabelle. Der Nachteil dieses Ansatzes ist, dass die Tabelle zusammenhängen und beim Anlegen des Dateisystems erzeugt werden muss.

Eine Alternative hierzu stellt die Verwendung von B-Trees dar, um Metadaten und den Index zu speichern. Die B-Tree-Datenstruktur wurde schon in den 70er Jahren erfunden und erlaubt es, Werte mit sehr wenigen Operationen aufzufinden. Im Fall von Dateisystemen bedeutet das sehr wenige Disk-Seek-Operationen, die Festplatte und Leseköpfe physisch in Bewegung versetzen. B-Trees verlieren ihre guten Eigenschaften beim Hinzufügen oder Löschen von Werten nicht, denn ihre Verwaltungssoftware sorgt dafür, dass sie stets ausbalanciert sind, was wiederum die gute Performance sicherstellt.

Auch die B-Trees sind durch Pages strukturiert, speicher also beispielsweise eine ganze Reihe von Keys einer Ebene in einer einzigen Page. Wenn zum Beispiel die Nummern und die Schlüssel jeweils 8 Bytes einnehmen, kann die Root-Page mit 4 KBytes 256 andere Seiten referenzieren, von denen jede einzelne wieder 256 weitere Seiten referenzieren kann. Man braucht also nicht viele Seiten, um Millionen von Schlüsseln und Werten zu verwalten. Somit kann man beispielsweise über den Zugriff auf nur drei Seiten einen von den Millionen Werten eines B-Trees finden.

Weil jeder Seitenzugriff eine Disk-Seek-Operation bedeutet, liegt der Schlüssel zum schnellen Dateisystem in der Minimierung der nötigen Seitenzugriffe. Das mag sich vielleicht in Zukunft mit der immer größeren Verbreitung von Solid-State-Disks ändern, aber ein paar Jahre lang hat diese Regel sicher noch Gültigkeit.

Die unterste Ebene (die Wurzel ist üblicherweise oben) speichert die zu einem Schlüssel gehörigen Daten, die entweder ein Zeiger auf den Speicherort sind oder die Daten selbst, wenn sie klein genug sind. Bei Dateisystemen sind Änderungszeit, Eigentümer, Berechtigungen und so weiter klein genug, dass sie direkt in den B-Tree passen. Das XFS-Dateisystem verwendet zum Beispiel einen I-Node-B-Tree, um immer Gruppen von jeweils 64 I-Nodes zu referenzieren.

Die Tatsache, dass B-Trees geordnet sind, lässt sich von Dateisystemen zum Vorteil verwenden. Legt man zum Beispiel in einem Verzeichnis 50 Dateien an, sind sie im B-Tree auch nahe beieinander einsortiert. Um sie aufzufinden, genügt also vielleicht schon eine einzige Speicherseite. Weil die Nummer im B-Tree beieinander liegen, sind auch die Seiten, die man beim Durchlaufen des Baums lesen muss, die gleichen. So genügen vielleicht schon drei oder vier Seek-Operationen, um alle 50 Dateien zu finden.

COW

Auch wenn B-Trees also Suchvorgänge sehr beschleunigen können, ist Problem des Stromausfalls ist natürlich auch bei ihnen weiterhin latent. Es gibt zwei Strategien damit umzugehen: Wie beschrieben ein Journal zu verwenden, um alle Änderungen zu protokollieren oder ein Copy-on-Write-B-Tree (COW). Die Journaling-Methode wird von den Datensysteme XFS, Ext3 und Ext4 verwendet (Abbildungen 1 und 2), das neue Btrfs hingegegen basiert auf COW (Abbildung 3). Die Ext-Dateisysteme speichern Metadaten in vorab zugewiesenen I-Node-Tabellen, XFS dagegen einen B-Tree mit I-Nodes.

Abbildung 1: Das Extended Filesystem (Ext) hat sich von Version 2 bis 4 ziemlich gewandelt.
Abbildung 2: Ursprünglich von Silicon Graphics entwickelt, ist das XFS-Dateisystem heute ein eigenständiges Projekt.
Abbildung 3: Das B-Tree-Filesystem (Btrfs) hat in Linux-Kreisen mit seinen Raid- und Snapshot-Fähigkeiten schon für Begeisterung gesorgt, befindet sich aber noch in Entwicklung.

Normalerweise wird beim Ändern einens B-Tree die Seite gelesen, die den entsprechenden Key enthält, dort geändert und dann wieder zurückgeschrieben. Wenn das Hinzufügen eines neuen Schlüssels dazu führt, dass die Daten nicht mehr in eine Seite passen, teilt das Dateisystem sie in zwei Seiten auf und fügt die neue Seite unterhalb des Elternknotens ein. Bei der COW-Strategie bleibt der alte Tree unangetastet, stattdessen entsteht eine neue Kopie des Elternbaums. Durch die B-Tree-Struktur sind es ja nur etwa drei bis fünf Elternknoten, sodass das Kopieren keinen großen Aufwand verursacht. Nun hat man einen neuen Baum mit drei bis fünf neuen Seiten, der die anderen Seiten mit dem alten Baum teilt. Weil der Einfügevorgang alle Elternknoten kopiert, bekommt man für jede Operation einen neuen Wurzelknoten, was effektiv auf einen immer neuen Snapshot des Dateisystems hinausläuft. Aus Performance-Gründen nehmen COW-Dateisysteme die soviele Änderungen wie möglich im Hauptspeicher vor und synchronisieren in einem periodischen Intervall die Änderungen mit der Disk.

Snapshots ermöglichen es, das Dateisystem in einem früheren Zustand zu mounten, zum Beispiel das Home-Directory so wie es vorigen Monat ausgesehen hat. All das Kopieren mag nach einer Verschwendung von Speicherplatz klingen, aber schließlich handelt es sich immer nur um Blöcke von 4 KBytes, also nehmen selbst Millionen von Pages relativ wenige Speicherplatz in Anspruch. Wenn die alten Seiten nicht mehr gebraucht werden, kann das Dateisystem sie wiederverwenden, um nicht den kompletten Speicherplatz der Platte zu verbrauchen. Btrfs verwendet COW für alles, sodass sich jederzeit komplette Snapshots des Dateisystems anlegen lassen.

comments powered by Disqus

Artikel der Woche

Eigene Registry für Docker-Images

Wer selber Docker-Images herstellt, braucht auch eine eigene Registry. Diese gibt es ebenfalls als Docker-Image, aber nur mit eingeschränkter Funktionalität. Mit einem Auth-Server wird daraus ein brauchbares Repository für Images. (mehr)
Einmal pro Woche aktuelle News, kostenlose Artikel und nützliche ADMIN-Tipps.
Ich habe die Datenschutzerklärung gelesen und bin einverstanden.

Konfigurationsmanagement

Ich konfiguriere meine Server

  • von Hand
  • mit eigenen Skripts
  • mit Puppet
  • mit Ansible
  • mit Saltstack
  • mit Chef
  • mit CFengine
  • mit dem Nix-System
  • mit Containern
  • mit anderer Konfigurationsmanagement-Software

Ausgabe /2020