Journaling Filesysteme unter Linux

Was ist neu an den Journaling Filesystemen?

[ Seminar Linux und Apache ] ... [ Inhaltsübersicht ] ... [ Ablauf beim Journaling ]

Übersicht

Verwaltung der freien Blöcke

Das Problem:
In den meisten Dateisystemen werden die noch freien Blöcke einer Platte in einer Liste verwaltet. Hier wird in einer sogenannten Bitmap für jeden logischen Block ein Bit gespeichert. Ist der Block belegt so ist dieses Bit gesetzt.
Durch die Speicherung in einer Liste verlängert sich der Suchweg zum Auffinden eines freien Blockes bei Vergrößerung des Dateisystems. Bei kleinen Platten mag das noch im Rahmen bleiben, bei größeren fällt dies schon mehr ins Gewicht.

Die Lösung:
Die Dateisysteme der neuen Generation lösen diese Problem dadurch, dass die freien Bereiche der Platte als Extents gespeichert werden. Hierdurch wird nicht mehr für jeden Block ein eigenes Bit benötigt. Die Struktur zur Verwaltung der freien Blöcke ist damit nicht mehr abhängig von der Größe des Dateisystems, sondern von der Anzahl der Extents. Wenn man aber den ungünstigen Fall nimmt, dass jeder Extent nur einen Block enthält, würde die Verwaltung der Extents mehr Speicher benötigen als die Bitmap.

Ein weiterer Punkt, um hier etwas mehr aus dem Dateisystem herauszukitzeln, ist die Verwendung einer Baumstruktur zur Speicherung der freien Extents. Dies ermöglicht dem System eine Indexierung der freien Speicherbereiche nach Größe oder Position der Extents. Danach kann das Dateisystem dann den freien Speicherbereich auswählen in den die zu speichernden Daten am besten (ohne großen Verschnitt) hineinpassen.

Nach oben

Große Dateiverzeichnisse

Das Problem:
Verzeichnisse sind aus Sicht von Dateisystemen eine Menge von Einträgen. Diese Einträge bestehen jeweils aus einem Inode und einem Dateinamen. Da herkömmlicherweise diese Einträge in einer Liste verwaltet werden, muss diese auch durchlaufen werden sobald eine Anwendung auf eine Datei zugreifen will. Man kann sich also vorstellen, dass bei tausenden von Dateien und anderen Verzeichnissen schon eine Weile vergehen kann bis eine Datei gefunden wurde.

Die Lösung:
Auch hier ist die Speicherung der Einträge in eine Baumstruktur mit dem Index auf dem Dateinamen sinnvoll. Die neuen Dateisysteme gehen hier zwei unterschiedliche Wege. Entweder werden die Dateien in einem großen Baum für das gesamte Dateisystem gespeichert, oder aber es wird für jedes Verzeichnis ein eigener Baum erzeugt. Eine Beschreibung der Speicherung in einem Baum folgt etwas weiter unten auf dieser Seite.

Nach oben

Große Dateien

Das Problem:
UFS und Ext2fs wurden zu einer Zeit entwickelt, in der man nicht so große Dateien zu speichern hatte wie heute. Dementsprechend ist auch die Architektur angelegt. Durch die Verwendung von indirekten Zeigern (doppelt- oder sogar dreifach-indirekten Zeigern bei großen Dateien) wächst die Anzahl der Zugriffe auf die Festplatte.


   Zugriff durch Inodes auf Blöcke mit doppelt-indirekten Zugriffen [ 6]

Die Lösung:
Auch hier wird wiederum der Baum als ein wichtiger Lösungsteil genommen.
Um die Anzahl der indirekten Zeiger zu reduzieren könnte man die Größe der Blöcke erhöhen. Dies würde also die Anzahl der Blöcke pro Datei reduzieren, allerdings würde auch der interne Verschnitt größer. Also muss auch hier eine weitere Technik herhalten.
Wie bei der Verwaltung der freien Blöcke werden die Dateien in Extents gespeichert.
Einige der neuen Dateisysteme gehen dort sogar noch einen Schritt weiter. Um die Performance zu erhöhen werden kleine Dateien im Baum mit abgespeichert. D.h. also direkt im Inode. Dies erspart dann auch den letzten noch vorhandenen Zeiger, da beim Laden des Inodes aus dem Baum bereits die komplette Datei geladen wurde. Ein Plattenzugriff wird hierbei gespart.
ReiserFS speichert zusätzlich den jeweils letzten Block einer größeren Datei im Inode. Dies verhindert den internen Verschnitt durch die Dateienden und verringert die übertragene Datenmenge um einen Block.

Nach oben

Sparse files

Das Problem:
In einem UFS oder Ext2fs werden für die gesamte Größe des Files Inodes belegt.
Ein Beispiel:
Wir erstellen eine neue Datei und schreiben ein paar Bytes an den Anfang. Nun werden mit einer Lücke (Offset) von 10.000 Byte ein paar zusätzliche Bytes hineinschreiben. Damit haben wir eine Datei erzeugt, die am Anfang und am Ende jeweils ein paar Bytes belegt. Dazwischen liegt dann praktisch eine Menge von "Nichts". In den herkömmlichen Dateisystemen werden aber auch für dieses "Nichts" Inodes belegt. Zwar wird der Platz für die Daten auf der Platte nicht reserviert, allerdings verschwendet man hiermit eine gewisse Anzahl von Inodes.

Die Lösung:
Durch die Verwaltung der Dateien in Extents kann hier eine weitaus günstigere Lösung erzielt werden. Die Datei wird durch zwei Extents repräsentiert. In unserem Beispiel werden dann nicht zehn sondern lediglich zwei Blöcke belegt.



Bsp. für Verwendung von Extents bei sparse-files [ 3]

Nach oben

Dynamische Inode-Vergabe

Das Problem:
Ein Hauptproblem der UFS-ähnlichen Dateisysteme ist die fest vorgegebene Anzahl von Inodes. Bei der Formatierung der Partition wird bestimmt wieviele Inodes vorhanden sein sollen. Sind alle diese Inodes belegt, so müssen die Daten gesichert werden und die Partition mit einer höheren Anzahl neu formatiert werden.
Man sollte allerdings nicht von Haus aus die höchst mögliche Anzahl vorsehen, weil dadurch natürlich eine Menge an Platz für die Speicherung der Bitmaps für die (vermutlich dann nicht benutzten) Inodes verloren geht.

Die Lösung:
Auch zur Verwaltung der Inodes wird eine Baumstruktur verwendet. Dies ist zwar etwas zeitaufwendig, allerdings entbindet es den Administrator von der unangenehmen Aufgabe die maximale Anzahl der Objekte im Dateisystem im Voraus zu raten.

Nach oben

Allgemeines zur Architektur

Block-based vs. extent-based allocation
Block-based:
Traditionelle Dateisysteme unter UNIX-Systemen wie z.B. Ext2fs oder UFS benutzen zur Reservierung von Speicher auf der Platte eine block-orientierte (block-based) Vorgehensweise. Wird eine Datei auf die Platte geschrieben, so wird vom Dateisystem eine bestimmte Anzahl von Blöcken reserviert.
Im allgemeinen ist die Reihenfolge der Blöcke zufällig. Dies bedeutet, dass beim Einlesen der Datei dann zum Teil kräftige "Sprünge" des Lesekopfes auf der Platte notwendig sind. Im optimalen Fall liegen die Blöcke direkt hintereinander auf der Platte. Aber spätest dann wenn die Datei mal in der Größe verändert wird ergeben sich wieder andere Konstellationen. Daraus resultiert dann eine Verteilung der Datei-Blöcke auf der Platte (External fragmentation). Was dann zu tun ist, ist hinreichend bekannt: Die Defragmentierung! Für jeden dieser Blöcke wird im Inode der Datei eine Adresse gespeichert. Daraus resultiert ein nicht geringer Overhead an Daten.

Ein weiteres Problem beim block-orientierten Dateisystem ist, dass jede Datei in Blöcke gleicher Länge gespeichert wird. Ist eine Datei also kleiner als ein Block (hierzu zählen auch alle Dateienden, die nicht einen ganzen Block ausfüllen) wird Platz verschwendet. Statistisch betrachtet ist der letzte Datenblock jeder Datei zu mehr als 50% Brachland. Bei einer Blockgröße von 1 KB und 100.000 Dateien kommen so schon runde 50 MB zusammen.(Internal fragmentation)
Durch die heutigen Festplattenpreise fällt dies nicht so sehr ins Gewicht wie die Tatsache, dass das Betriebssystem in jedem Fall den ganzen Datenblock von der Platte übertragen muss, selbst wenn die Datei nur wenige Bytes belegt.

Extent-based:
Dateisysteme wie das ReiserFS oder das JFS benutzen nicht eine block-based allocation sondern eine extent-based allocation. Das bedeutet, dass nicht eine Reihe von Blöcken von der block map reserviert werden, sondern es wird ein zusammenhängender Speicherbereich in Größe der Datei reserviert. In den Meta-Daten der Datei wird allerdings nur eine Adresse gespeichert, und zwar die Startadresse dieses Speicherbereiches.


   block-allocation vs. extent-allocation [17]

B-Baum vs. Liste
Verkettete Liste (Ext2fs):
Beim Ext2fs werden Verzeichniseinträge in einer verketteten Liste gespeichert. Es werden auf der Platte in regelmäßigen Abständen Datenblöcke für die Inodes und die Inode-Bitmaps (die anzeigen welche der Inodes bereits belegt sind) reserviert. Sind alle Inodes belegt meldet der Kernel beim Versuch eine Datei zu erzeugen das Dateisystem sei voll. Dies passiert auch, wenn für den Inhalt der Datei eigentlich noch genug Platz auf dem Dateisystem wäre.
Die Verzeichnisse von Ext2fs können zwar wachsen, aber niemals schrumpfen. D.h. ein einmal für ein Verzeichnis angeforderter Plattenblock wird nicht wieder freigegeben, es sei denn das Verzeichnis wird gelöscht. Das Dateisystem opfert so etwa 3% der Plattenkapazität für Inodes, die der Anwender vielleicht niemals benutzt. Die Reihenfolge der Verzeichniseinträge ist zufällig, ohne jede Ordnung, was die Suche nach einer Datei besonders in großen Verzeichnissen unnötig verlangsamt.


   Verkettete Liste (unten) vs. Binärbaum (oben) [ 1]


B-Baum (ReiserFS):
Beim ReiserFS werden die Verzeichniseinträge in einem B-Baum gespeichert. Der Zugriff auf Informationen in B-Bäumen ist bekanntlich sehr schnell.
Hat ein Verzeichnis z.B. 1.000 Einträge, so werden bei einer Liste im Schnitt 500 Suchschritte benötigt, um einen Eintrag zu finden. Beim ausbalancierten Binärbaum ist das Ziel nach zehn Schritten (ld 1.000) bereits erreicht.


B+Baum [ 3]



   Die Struktur des ReiserFS (vereinfacht) in UML-Notation [ 1]


Dieser Performancegewinn wird allerdings durch den komplexeren Programmcode erkauft. Insbesondere das ausbalancieren des Baumes nachdem ein Eintrag hinzugefügt bzw. entfernt wurde nimmt Rechenzeit in Anspruch.
Ein Problem ist auch das Prüfen ob ein anderer Prozess den Ast des Baumes abgesägt hat, auf dem gerade gearbeitet wird. Beim ReiserFS werden die nicht mehr benötigten Einträge gleich gelöscht, so dass kein unnötiger Platz auf der Platte belegt bleibt.

Nach oben

Übersicht über die verwendeten Techniken

Die benutzen Techniken der Dateisysteme [ 3]
Dateisystem Verwaltung freier Blöcke Extents für freien Speicher B-Bäume für Verzeichnisse B-Bäume für Datei- Verwaltung Extents für Datei-Verwaltung Datei-Inhalt in Inodes
(kleine Dateien)		 Symbolische- Links in Inodes Verzeichnis- Inhalt in Inodes
(kleine Verzeichnisse)
XFS B+Bäume, Index nach Offset ind Größe Ja Ja Ja Ja Ja Ja Ja
JFS Baum und Binary Buddy*1 Nein Ja Ja Ja Nein Ja Bis zu 8
ReiserFS*2 Bitmap Noch nicht unterstützt Teilbaum des FS-Baumes Im FS-Baum Ab release 4 *3 *3 *3
Ext3FS Ext3fs unterstützt keine dieser Techniken. Ext3fs basiert vollkommen auf dem ext2fs.
*1 JFS benutzt ein anderes Verfahren zum Organisieren von freien Blöcken. Die Sruktur ist ein Baum, dessen Blätter keine Extents enthalten, sondern eine Art Bitmap. Allerdings wird nicht für jeden Block ein Bit benötigt, sondern Blöcke werden zusammengefasst (Binary Buddy) und die Belegung wird dann in Hex-Zahlen gespeichert. Eine Angabe von "FFFFFFFF" bedeutet dann, dass alle Blöcke in diesem Bereich belegt sind.

*2 Dieses Dateisystem basiert auf einem B*-Baum. Der Hauptunterschied ist, dass alle Objekte des Dateisystems in einem einzigen Baum gespeichert werden. D.h. dass nicht jedes Verzeichnis in einem eingenen Baum gespeichert wird. Momentan benutzt Reiser FS noch keine Extents, dies ist für spätere Versionen geplant.

*3 ReiserFS speichert alles Objekte (Verzeichnisse, Dateiblöcke, Datei-Attribute, Links, usw.) in einem Baum. Hash-Verfahren werden benutzt, um die Elemente zu organisieren. ReiserFS bietet die Möglichkeit diese Hash-Verfahren zu wechseln, so dass je nach Wahl die Suche nach bestimmten Objekten optimiert werden kann.



Weitere Techniken[ 3]
Dateisystem Dynamische Inode Reservierung Dynamische Inode-Verwaltung Unterstützung von Sparse-files
XFS Ja B+Baum Ja
JFS Ja B+Baum mit Inode-Extents Ja
ReiserFS Ja im FS-Baum Ja*4
Ext3FS Nein Nein Nein
*4 Momentan ist die Unterstützung noch nicht so schnell wie geplant. Dieses Problem soll mit der Version 4 behoben werden.

Nach oben
[ Seminar Linux und Apache ] ... [ Inhaltsübersicht ] ... [ Ablauf beim Journaling ]