Seite 2: Extents

Große Dateien

Die wichtigste interne Verbesserung in Ext4 ist die Verwendung von Extents anstelle der in Ext3 verwendeten indirekten Blockadressierung. Bei letzterer speichert ein Inode die Nummern von maximal zwölf 4-KByte-Blöcken. Ist eine Datei größer als 48 KByte, kommen zunächst indirekt adressierte Blöcke (bis 4 MByte), dann doppelt (bis 4 GByte) und schließlich dreifach indirekt adressierte Blöcke zum Einsatz, bei denen eine Blocknummer im Inode auf einen Block mit Blocknummern verweist, die auf Blöcke mit Blocknummern verweisen, die auf Blöcke mit den Blocknummern der Daten verweisen (Details zu Ext3 finden Sie hier). Dieses klassische Adressierungsschema der Unix-Welt bewährt sich bei kleinen oder sehr stark fragmentierten Dateien sowie bei sparse files, bringt aber bei großen Dateien einen zunehmenden Verwaltungs-Overhead mit sich.

struct ext3_extent {
  __u32   ee_block;
/* first logical block 
   extent covers */
  __u16   ee_len;
/* number of blocks
   covered by extent */
  __u16   ee_start_hi;
/* high 16 bits of
   physical block */
  __u32   ee_start;
/* low 32 bits of
   physical block */
};

Extents adressieren keine einzelnen Blöcke, sondern mappen stattdessen einen (möglichst großen) Bereich einer Datei auf einen Bereich zusammenhängender Blöcke auf der Platte. Dazu braucht man statt vieler einzelner Blocknummern nur noch drei Werte: Der Start und die Größe des Bereichs in der Datei (jeweils in Dateisystemblöcken) sowie die Nummer des ersten Datenblocks auf der Platte. Die Datenstruktur eines Extents in Ext4 sieht so aus wie in dem Kasten rechts.

Dabei zählt Ext4 die Blöcke innerhalb einer Datei 32-bittig, was die maximale Größe einer Datei im Ext4-Dateisystem auf 2³² 4-KByte-Blöcke, also 16 TByte begrenzt. Dieses Limit könnte fallen, wenn das Extent-Format überarbeitet wird: Es gibt bereits Überlegungen, für sparse files und sehr stark fragmentierte Dateien, die sich mit Extents nicht effizient verwalten lassen, ein anderes Format zu verwenden, das wieder mit einzelnen Blocknummern arbeitet. Außerdem denken die Entwickler darüber nach, beschädigte Extents durch zusätzliche Informationen und eine Checksumme erkennen zu können.

Das ist zwar alles noch Zukunftsmusik, aber eine Grundlage dafür ist zumindest schon gelegt: Vor den Extents steht eine Header-Struktur auf der Platte, die auch eine magic number zur Identifizierung und falls nötig Unterscheidung von Extents je nach Typ erlaubt.

Für die Größe eines Extents stehen 15 Bit zur Verfügung, sodass ein Extent nicht größer als 2¹⁵ 4-KByte-Blöcke, also 128 MByte werden kann. Für dieses Limit gibt es einen einfachen Grund: Wie Ext3 unterteilt auch Ext4 die Platte in Blockgruppen von 128 MByte Größe. Da jeder Blockgruppe ein Blockgruppen-Deskriptor und ein Ausschnitt aus der Inode-Bitmap, der Block-Bitmap und der Inode-Tabelle vorangehen, lassen sich nicht mehr als 128 MByte am Stück speichern.

Das übrig gebliebene sechzehnte Bit bei der Extent-Größe speichert, ob der Extent bereits mit Daten beschrieben ist – wenn nein, gibt das Dateisystem beim Lesen der Daten Nullen zurück („unitialized extent flag“). Das ermöglicht es Anwendungen, Plattenplatz vorzubelegen („persistent preallocation“, dazu gleich mehr), eine von mehreren Maßnahmen zur Performance-Steigerung in Ext4, ohne dass dadurch ein Zugriff auf früher in diesem Bereich gespeicherte Daten möglich wird.

Extents bringen vor allem bei großen Dateien und dort speziell bei solchen Operationen Vorteile, die in erster Linie Metadaten-Operationen erfordern, also beim Löschen und Verkürzen von großen Dateien. Das sieht man bereits, wenn man mit dd ein paar große Dateien anlegt und sie dann wieder löscht (siehe Tabelle) – vor allem das Löschen benötigt bei Ext4 nur einen Bruchteil der Zeit.

Extent-Bäume

Ext4 benutzt die 60 Byte im Inode, die Ext3 zum Speichern von 15 32-bittigen Blocknummern verwendet, um dort vier Extents und einen Header-Extent von jeweils 12 Byte Länge abzulegen. Damit lassen sich Dateien bis zu 512 MByte direkt aus dem Inode heraus verwalten. Dabei zeigt sich ein weiterer, ganz praktischer Vorteil der 48-bittigen Blocknummern: Würden sowohl für die Position des Extents in der Datei als auch für den Start-Block auf der Platte 64-Bit-Werte verwendet werden, stiege die Größe eines Extents auf 18 Byte. Da der Extent-Header bereits 12 Byte belegt, könnte man nur noch zwei statt vier Extents im Inode speichern.

Ist eine Datei größer als 512 MByte, baut Ext4 einen Baum aus Extents auf. Dabei kommt eine weitere Datenstruktur zum Einsatz, der Extent-Index, der lediglich die Startposition des Extents in der Datei und eine Blocknummer auf der Festplatte enthält. In diesem Datenblock können dann entweder Extents stehen, die auf die Daten verweisen, oder erneut Extent-Indexe, wobei jeder Block mit einem Extent-Header beginnt. Der Extent-Baum startet mit einem Extent-Index im Inode.

Extents packen zwei Probleme von Ext3 an: Sie verringern den Verwaltungs-Overhead bei großen Dateien – eine 500-MByte-Datei lässt sich mit vier Extents à 12 Byte im Inode effizienter verwalten als mit einem halben Megabyte über die Platte verstreuter 32-bittiger Blocknummern – und können die Fragmentierung des Dateisystems verhindern. Dazu haben die Entwickler einige neue Mechanismen implementiert.

Einer davon ist die bereits angesprochene „persistent preallocation“. Mit dem Systemaufruf fallocate() kann eine Anwendung für eine Datei eine bestimmte Menge Speicher reservieren und das Dateisystem so darüber informieren, wie groß die Datei werden wird. Hilfreich ist das vor allem, wenn eine Datei langsam wächst oder wenn sie nicht sequenziell geschrieben wird, wie es beispielsweise Tauschbörsen-Clients machen.

Dank der „persistent preallocation“ kann Ext4 gleich ausreichend Platz in möglichst zusammenhängenden Bereichen auf der Platte reservieren. Erfreulicher Nebeneffekt für die Anwendung: Das tatsächliche Schreiben der Daten kann nicht mehr wegen Speicherplatzmangel fehlschlagen. Die Glibc stellt fallocate() derzeit noch nicht zur Verfügung; Anwendungen müssen die Funktion entweder per syscall() aufrufen oder posix_fallocate() verwenden. Das bereits erwähnte sechzehnte Bit in der Größenangabe eines Extents speichert, ob ein Extent voralloziert, aber noch nicht mit Daten beschrieben ist.