Moin, ich bin Marcel. Mein Thema ist Short History of Linux File Systems. Meine Motivation dahinter war immer, bevor ich mir File Systemen angeguckt habe,

waren die immer ein bisschen mysteriös für mich. Was machen die eigentlich? Also ja klar, Dateien speichern. Aber wie? Wie liegen die Sachen am Ende auf der Festplatte, sodass ich sie schnell wiederfinden kann. Deswegen habe ich irgendwann vor Monaten mal angefangen, mir so irgendwie alle paar Wochen, wenn ich Zeit hatte, mal ein paar Dateisysteme anzugucken,

wie sie funktionieren. Und auf das History-Ding bin ich gekommen, weil ich irgendwann versucht habe, mal ein bisschen zu gucken, wo kommt das alles her? Warum sieht das eigentlich so aus? Warum gibt es eigentlich I-Notes? Wo kommt das alles her?

So, kurz zu mir. Wer bin ich? Ich bin wissenschaftlicher Mitarbeiter am Zentrum für Datenverarbeitung der Uni Mainz. Das ist das Hochschulrechenzentrum. Da arbeiten auch ein paar Wissenschaftler, die unter anderem sich beschäftigen mit High-Performance-Computing und Speichersystemen. Ich gehöre zu den Speichersystemen, Leute. Meine Aufgabe ist da mehr oder weniger nicht Dateisysteme,

sondern ich bin so ein bisschen mit CEF unterwegs. Ich gucke mir an, was man da so an experimentellen Dingen tun kann. Grob gesagt war das in der letzten Zeit, wie kann man Archive daraus machen? Wie kann man D-Duplizierung einbauen? Ich mag Dateisysteme. Vor vielen Jahren habe ich irgendwann mal eine Java-Implementierung von EXT-2 gemacht.

Das war Teil meiner Bachelorarbeit. Die Idee dahinter war grob, wie viel langsamer wäre es denn? Es stellt sich heraus, es ist langsamer. Den Faktor habe ich vor langer Zeit vergessen. Es war für mich auf jeden Fall eine sehr interessante Erfahrung, ein Dateisystem zu implementieren.

Das Ganze hat immer sehr viele Kleinigkeiten, auf die man achten muss. Mir geht es heute hauptsächlich darum, so ein Big Picture zu kriegen. Wie sehen die Datenstrukturen eigentlich aus? Grobe Outline ist, ich fange an mit Grundlagen. Was sind eigentlich I-Notes? Was ist der Superblock? Was sind Directories? Wie sehen Directory Entries und Entries aus?

Dann gehe ich weiter zu den Anfängen, die ich gefunden habe. Wie sieht eigentlich das Minix-Filesystem grob aus? Wie sieht das Unix-Version 6-Filesystem aus? Danach werde ich noch kurz mal auf die Microsoft-Seite eingehen, auf FAT. Warum mache ich FAT? Weil es ist halt allgegenwärtig.

Irgendein embedded Device hat, das hat häufig einen FAT, um einen Kernel drauf zu speichern. Oder EFI hat sowas wie FAT. Die haben lustigerweise einen eigenen Speck dafür. Aber in Wirklichkeit ist es so eine Art FAT-Filesystem. Dann gehe ich weiter zu der Linux-Seite und werde mit XC2 anfangen.

Danach kommt mal kurz so ein Einschub, was eigentlich ein B-Tree ist. B-Trees sind so die Datenstruktur, die man überall findet in allen aktuellen Dateisystemen in irgendeiner Form. Danach geht es weiter mit XC3 und XC4. Was kam dazu? Was kam dazu? Dann noch kurz was zu einem der sehr beliebten Importe von anderen kommerziellen Unix-Systemen.

Und zwar XFS. Und abschließend noch so ein kleiner Outlook. Wo stehen wir gerade? Welche Dateisysteme sind so ein bisschen im Kommen? Was für neue Challenges kamen dazu? Warum müssen sich Sachen ändern?

Ich habe aus meinem Notizheft ein kleines Foto gemacht. Und zwar ist es so eine Art Timeline zu den Dateisystemen. Was sind die interessanten Stellen? Das sind so ein bisschen die interessanten Stellen. Also hier links geht es Richtung 70er. In der Mitte sind 90er. Das hier sind die 00er. Und weiter da sind irgendwo, wo wir gerade sind.

Die interessanten Stellen sind, FAT kommt irgendwo aus den 70ern. Mit FAT 16, so Mitte der 80er. Das Unix-Fallsystem kommt auch aus den 70ern und hat eine ganz andere Struktur als zum Beispiel FAT. Es gibt dann ungefähr hier das Unix-Fast-Fallsystem.

Das ist so ein bisschen der Grundstein aller Dateisysteme, die Unix-Systeme danach haben. Abstammungen sind zum Beispiel, EXT2 stammt so ein bisschen von den Ideen ab. Und das, was man in BSD unter UFS versteht, stammt davon auch ab.

Und was man noch so ein bisschen sehen kann, es gab irgendwann unter Linux so ein bisschen die Ära der Journaling-Fallsysteme. Und die ist so ungefähr Anfang der 00er gewesen. So, kurz, was sind Quellen, um Dateisystem-Strukturen nachzugucken?

Eine der besseren Quellen, also die genauesten Quellen, sind der Code. Ich kann jedem, der mal ein bisschen Dateisystem-Code lesen möchte, total gut Grub empfehlen. Weil die haben Read-Only-Treiber, die alle so in der Hausnummer 1000 Zeilen sind. Für fast alles an Dateisystemen, was man sich vorstellen kann. Sehr nett zu lesen. Relativ neuer Code auch, denke ich.

Der Linux-Könel, klar, der hat Read-Write-Treiber. Die sind meistens in der Komplexität weitaus mehr. Also zwischen Read-Only-Treibern und Read-Write-Treibern, da liegt meistens so Faktor 5 bis Faktor 10 in Aufwendigkeit zwischen. Ansonsten stütze ich mich häufig auf Specs oder auf Paper. Viele Dateisysteme, gerade neuere und auch ältere, gibt es wissenschaftliche Paper zu.

Ich starte jetzt mit den Grundlagen. Zwar mit Blöcken. Blöcke sind so die Ebene, mit der man Sachen adressiert. Ein Fallsystem. Da gibt es mehr oder weniger zwei Unterschiede.

Erstmal eine Disk hat irgendwelche Blöcke. Früher waren es mal 512 Byte, heute sind es häufig 4K. Häufig nennt man die auch Sektoren. Das verschwimmt gerne mal so ein bisschen. Manchmal sind es auch einfach Blöcke, meistens Sektoren. In Dateisystemen gibt es auch Blöcke. Man kann also nicht wirklich aus der Dateisystemebene aus einzelne Bytes adressieren. Man hat immer so ein Ding in der Hand.

Unter Linux sind 4K sehr üblich. Das lag wohl früher daran, dass das gerade die Page Size war. Es gibt aber auch durchaus andere Block Sizes. ZFS geht bis 128K, allerdings haben die Variable Block Sizes. Je nachdem, welches Dateisystem man sieht, heißen die Dinge auch manchmal Cluster.

Aber ich werde die Dinge Blöcke nennen. Zu Blöcke gibt es immer noch einen Block, der alle Blöcke beschreibt. Das ist der Superblock. Üblicherweise liegt der irgendwo am Anfang. Meistens noch mit Kopien irgendwo anders auf der Platte, falls der mal kaputt geht. In der Block beschreibt all die wichtigen Dinge, die man braucht, um das Dateisystem mounten zu können.

Üblicherweise eine Liste mit Pointer auf Datenstrukturen, wie zum Beispiel die Inode Tables. Irgendwo steht dort auch, was die Block Size eigentlich ist. Meistens auch noch eine Menge von Statistiken. Wie viele Daten sind frei? Wie viele Inodes sind noch frei? Und ganz wichtig, üblicherweise eine Magic. Das ist einfach eine Zahl, womit die Implementierung weiß, es ist wirklich ein Superblock.

Und nicht irgendwelche Daten, die ich gerade zufällig lade. Ganz kurz noch, was gibt es für Dateitypen? Das ist die Liste der Dateitypen, die ich aus dem X2-Code habe. Lustigerweise in der Reihenfolge scheinbar kam FIFO sehr früh. Die wichtigsten Typen davon sind reguläre Files, symbolische Links und Directories.

Directories sind auch Dateien. Interessanterweise Hardlinks tauchen zum Beispiel nicht auf. Warum das so ist, erkläre ich auch gleich. Was ist eigentlich ein Directory? Ein Directory ist aus der Words Eye View nichts anderes als ein Mapping von irgendwelchen Namen zu Pointers auf Inodes.

Diese Namen sind, es hat sich irgendwie 255 Characters durchgesetzt auf den meisten Unix-Filesystemen. Falls mir nachher einer sagen kann, warum es so viele sind. Ich weiß es leider nicht, warum es 255 sind, aber das steht überall so definiert.

Dann dieser Pointer auf eine Inode. Eine Inode ist so ein Zwischenschritt, der zwischen dem Filenamen und den Daten steht. In der Inode steht, das i kommt, by the way, von Index. Da stehen Dinge drin wie die Mode, also dieses Unix-Permission-Ding mit User Group und Others. UIDs, GIDs, heutzutage häufig auch Links auf External Attributes.

Verschiedene Times stehen da drin, wie C-Time, A-Times. Und ganz wichtig, dort findet man auch die Pointer auf die Daten. Was steht in den Daten? Bei Files stehen die Daten der Files da drin.

Bei Directories findet man genau diese Tabelle mit dem Mapping von Name zu Inodes an der Stelle. Was passiert, wenn ich zwei Directory Entries habe, die auf die gleiche Inode zeigen? Ja, ich habe einen Hardlink, so heißt es am Ende. Zusätzlich habe ich da noch einen Eintrag mit Links gleich zwei, was sagt, es gibt zwei Leute, die pointen auf mich.

Das heißt, irgendwann muss eine Inode auch mal gelöscht werden und man löscht, wenn das Ding auf Null geht. Was ist der Unterschied zu einem Swim Link? Ein Swim Link ist nichts anderes als ein String, der in dem Datenteil einer Inode steht. Das kann wirklich alles sein, das muss nicht mal existieren, was in diesem String steht.

So, die Anfänge, die ich gefunden habe von Dateisystemen. Ich starte mit der Unix Version 6. So ungefähr sieht ein Unix Version 6 Fallsystem aus. Das fängt an mit einem Superblock, danach kommt eine Inode-Liste und danach kommen auch schon die Daten.

Das ist wirklich die komplette Inode, das sind wirklich alle Einträge davon. Spätere Superblocks werde ich halt nur noch die interessanten Teile zeigen. Was hier interessant ist, die Art und Weise, wie freie Sachen gehandelt werden. Das ist eins der größten Kritikpunkte gewesen und sorgt auch dafür,

dass es danach das Fast File System for Unix, das ist auch der Name von einem Paper, der ja beschreibt, dass dieses Dateisystem irgendwie 4% Throughput auf den damaligen Maschinen kriegt. Die damaligen Maschinen waren schon nicht die schnellsten, verglichen mit heute. Also, wie funktioniert da das Free Space Management?

Man hat hier eine Liste zum Beispiel von Free Blocks und Free Inodes. Bei den Free Blocks stehen die ersten 100 Free Blocks im Superblock. Und der hundertste Eintrag pointet auf einen Block, der eine Tabelle ist mit den nächsten Blöcken. Das heißt, es geht dann immer so weiter, braucht man mehr.

Der letzte Eintrag dieses Blocks pointet auf den nächsten Block, der wieder sagt, was ist eigentlich frei. Bei Inodes ist das noch mal anders. Ich habe 100 freie Inodes in dieser Liste, die zeigen alle auf diese Inode-Liste vorne.

Und wird das alle, muss ich da einmal durchscannen, durch die ganze Inode-Liste. Wie sieht eine Inode aus? Eine Inode hat, hier auf der Seite mit diesen Tabelleneinträgen, zeigt eins der weit verbreitesten Art und Weisen,

wie man Datenblöcke beschreibt in Inodes. Bis EXT3 war das zum Beispiel noch standard, das so zu tun. Das nennt man häufig Blockmaps oder Indirect Addressing. Das heißt, in diesem Fall sind die ersten sechs Blöcke von Daten direkt adressiert über die Inode.

Danach kommt sogar ein Indirect Block. Das ist sozusagen, man zeigt auf einen Block, und dieser Block ist eine Tabelle mit Blöcken. Das Ganze kann man dann noch mal weitertreiben, mit Double Indirection. Das heißt, man zeigt auf einen Block, dieser Block zeigt auf einen Block mit Zeigern auf Blöcken. Das Ganze geht heute bis Triple Indirection hoch.

Das heißt, je größer die Datei, desto mehr Lookup-Overhead habe ich. So, ein kurzer Ausflug in das Minix-Filesystem, das gar nicht so viel anders aussieht. Die Geschichte von dem Minix-Filesystem ist relativ nah an der von Linux dran,

da die Entwicklungsgeschichte dort so ein bisschen gestartet ist. Interessanterweise zu dem Minix-Filesystem findet man in der Wikipedia-Seite noch den Eintrag, es ist immer noch beliebt auf Disketten. Kann sein, ich habe noch nie eine Diskette mit Minix-Filesystem in der Hand gehabt allerdings. Was man hier sieht ist, es gibt sogenannte Bitmaps.

Und wie die genau funktionieren, erkläre ich später. Aber man hat nicht mehr eine Liste mit, dieser Block ist frei, sondern man hat Bitmaps, um freien Platz zu beschreiben. Auch ist diese Struktur sehr nah an dem, wie die X-Filesysteme später aussahen.

Aber bevor ich die X-Filesysteme erkläre, einmal ein kurzer Ausflug in FAT. Wahrscheinlich dem einzigen Dateisystem, was man aus einer Wikipedia-Seite implementieren kann. Es gibt diese Wikipedia-Seite, die heißt Design of the FAT-Filesystem. Die hat wirklich jedes Bitfeld in jedem Header.

Und was es unter dieser DOS-Version bedeutet, ist sehr erstaunlich. Aber ich werde nur ein paar Konzepte erklären. Wie funktioniert eigentlich so ein FAT, ein File Allocation Table? An einem wohl definierten Ort auf dem Dateisystem hat man eine Tabelle, die beschreibt den Rest des Dateisystems.

Das heißt, wenn ich weiß, wo die Tabelle ist und in welchem Index ich bin, kann ich sagen, dieser Block gehört zu folgendem. Wenn ich jetzt eine Datei beschreiben will, wo die lang geht, habe ich da sogenannte File Chains drin. Das heißt, aus meinem Directory-Entry habe ich einen Eintrag in den FAT.

Und in jedem FAT-Entry steht, wo ist das nächste Entry. Das heißt, hier zum Beispiel die File Chain 234 nach oben sagt, der erste Block ist in zwei, der zweite Block ist in drei, der dritte Block ist in vier. Und jedem Block steht einfach die Zahl des nächsten Blockes. Das Ganze kann so schön linear aneinanderhängen, aber es kann auch so unordentlich sein.

Wie zum Beispiel hier die File Chain 6A78B. Dazwischen ist auch noch ein Bad Block. Man kann auch Blöcke markieren, als benutzt den mal nicht, denn der ist kaputt auf der Festplatte. Es gibt auch einen Special Marker, der EOC heißt, End of Chain.

Und wo kommt jetzt dieses 1632, manchmal liest man noch von 12 her? Das kommt einfach daher, das ist die Breite dieser Einträge. Allerdings muss ich dazu sagen, mit FAT32 kamen noch ein paar andere Änderungen dazu. Aber im Großen und Ganzen heißt es, wie breit sind diese Einträge da drin?

Denn je breiter die sind, desto mehr Blöcke kann ich auf der Festplatte adressieren. So, noch ein interessantes Teil davon ist, wie sehen Verzeichnisse aus? Verzeichnisse sind fest breiten Einträge. Das Erste, das Gelbe da oben ist der Name, genau 11 Characters. Da kommt auch dieses 8 plus 3 Filename-Ding her.

Und da stehen alle Sachen drin. Es gibt keine iNodes in diesem Dateisystem. Dort ist auch direkt der Link auf die FAT drin. So, irgendwann dachte man sich, ja, irgendwie 8 plus 3, der Teilname ist ein bisschen doof, ist ein bisschen kurz und hat dort Long Filename Support drüber gestülpt.

Das ist etwas, was man häufig findet in der Geschichte von Dateisystemen, dass man, irgendwie müssen wir da jetzt noch was Neues reinkriegen, gerne machen möchte. Im Sinne von FAT hat man das so gemacht, man hat hier in diesen Attributes, in den Attributes hat man eine Kombination gefunden, die so und so benutzt wird

und die Treiber nicht kaputt machen. Deswegen, man hat dann einfach genommen, ich sorge einfach dafür, dass ich solche Pseudo Entries da reinmache. Die werden auch noch mal aneinander gechained. Das heißt, ich kann, ich kenne die Länge gar nicht, man kann lange Filenames bauen.

Zusätzlich gibt es auch einen Eintrag, der so 8 plus 3 Dateinamen beschreibt. Das sind diese Dinger, die man vielleicht von früher kennt mit so einem tilde 1 am Ende. Und dann versteckt man Entries da drin. Noch ein interessantes Ding ist, die Character Entries sind plötzlich breiter geworden.

Das liegt daran, dass man auch gleichzeitig UCS2-Encoding benutzt hat. Das ist, so grob über den Daumen ist das so fest breiten Variante von UTF-16. Aber auch nur grob. So, wie sieht es dann auf der Linux-Seite aus?

Das X2-Filesystem. Die grobe Struktur eines X2-Filesystems ist, es fängt mit einem Bootblock an. Das ist eigentlich nicht Teil des Dateisystems, das was das Dateisystem in Ruhe lässt sozusagen. Da kann der MBR zum Beispiel liegen an der Stelle.

Und dann hat man eine Folge von Block Groups. Und jede Block Group sieht entweder so oder so aus. Es gibt zwei Varianten und die unterscheiden sich damit, ob da ein Superblock mit bei ist, ein Superblock und ein Group Descriptor Table bei ist oder nicht. Ich glaube in ganz frühen Versionen war das überall dran und dann merkte man, dass das ein bisschen Platz verbraucht.

Und jetzt ist das nur, es gibt eine Formel dafür, wo die Dinger am Ende liegen. Ich glaube, das war Potenz 3, 5, 7, irgendwie sowas. Es gibt dort immer noch Kopien von. Ein Superblock ist wieder der Block, der beschreibt das Dateisystem. Und was interessant ist, das hier ist sehr ähnlich zu dem, wie das Minix-Filesystem funktionierte.

Also dass man Bitmaps hat, die danach die Dinge beschreiben. Wie zum Beispiel die Block-Bitmap beschreibt einen Datenblock-Bereich. Und es gibt eine Inode-Bitmap, die beschreibt, was frei und nicht frei ist in einem Inode-Table. So wie sieht eine Inode aus? Die Inode sieht sehr ähnlich aus wie das, was ich eben schon gezeigt habe,

nur dass wir jetzt Triple Indirection dabei haben. Und dass wir mehrere Side Entries haben. Und dass die Inodes mit der Zeit wachsen, die auch. Neue Bedürfnisse, neue Features. So, wir sehen da Verzeichnisse aus. Verzeichnisse sind nicht wie in FAT Fixed Ranks. Sondern die können variabellang sein.

Allerdings können Filenames immer nur 255 Zeichen lang sein. Das heißt, das Gewuppelte am Ende in Name, das meint, das ist variabel. Dann gibt es noch einen interessanten Eintrag, der heißt Filetype. Das ist eine Optimierung, die später dazu kam.

Und zwar, man hat gemerkt, wenn man eine LS macht, möchte man auch gerne vielleicht wissen, ist der Eintrag ein Directory, ist der Eintrag eine File, ohne dass man einen Stat auf jede Inode da drin macht. Und jede Inode damit lädt. Deswegen steht in diesem Filetype einfach noch drin, ist es ein Directory, ist es eine File.

So, wie sieht jetzt ein Verzeichnis aus? Ein Verzeichnis ist eine Hintereinanderreihung von diesen Directory Entry Einträgen. So, wie findet man eine Datei in einem Verzeichnis? Man geht die Liste durch. Das ist auch nicht das Optimale, was man machen kann. Deswegen gibt es da auch später, in X3 kam eine Optimierung dazu, wie man macht, dass man nicht diese Verzeichnisse komplett durchgehen muss.

Denn das hat unter anderem dazu geführt, dass es in X2 ein hartes Limit gibt auf Directory-Größen von 65.000. Danach geht nicht größer, weil sonst sucht man sich halt tot da drin.

Dann habe ich eben noch von den Bitmaps geredet. Wie kann man sich das vorstellen? Na ja, man hat halt ein Stück Platz auf der Festplatte. Und man interpretiert die Nullen und Einsen mit belegt und nicht belegt. Zum Beispiel, für ein Inode-Table wäre das erste frei, das zweite nicht.

Und der Allocator geht da halt durch und sucht sich freie Regionen aus den Bitmaps aus und setzt die auf eins, damit der nächste weiß, da ist belegt. Das ist eine relativ kompakte Darstellung, um zu sehen, was frei ist und was nicht ist.

Mittlerweile gibt es auch Checksum. Ich weiß allerdings nicht, ob die auf Bitmaps gehen. Nein. Ich hatte so etwas mal mit dem Speicherfehler. Ah, okay.

Ach so. Die Frage war, wie merkt man Bitkipper da drin? Gibt es Checksums? Und die Antwort aus dem Publikum war Nö. Ist halt schlecht dann.

Aber Festplatten haben Checksums. Vielleicht reichen die ja. Obwohl dann natürlich noch der Ram dazwischenkommt. Auf irgendwas muss man sich an irgendeiner Stelle leider verlassen. Ich komme zu einem sehr interessanten Feature von den X-Dateisystemen. Denn die sind so ein bisschen auf Wachstum ausgelegt.

Im Superblock werden drei Bitmasken definiert, die beschreiben Features. Und zwar in drei verschiedenen Gruppen. Incompat, RO-Compat und Incompat. Compat steht für kompatibel. Das heißt, aus der Sicht einer Implementierung, wenn ich ein Dateisystem sehe, was dieses Feature angeschaltet habe und kompatibel ist,

dann darf ich das einfach ohne Bedenken mounten und damit rumarbeiten. Wenn es nur RO-Compat ist, darf ich es nur read-only mounten. Weil würde ich schreiben, würde ich irgendwelche Dinge ruinieren auf dem Fallsystem. Und Incompat heißt, nein, ich darf nicht. So, und diese Features werden sehr extensiv benutzt.

Interessanterweise ist nicht jedes von den Feature-Bits auch wirklich ein Feature. Manche davon beschreiben einfach nur Repurposing von Werten in zum Beispiel Inodes. Zum Beispiel Large-File sorgt dafür, wenn man eine File größer als zwei Gigabyte hat, dann wird ein Feld, was eigentlich für etwas anderes reserviert, wird in Inodes für die File-Size mitbenutzt.

Die interessanten Features davon werde ich gleich, wenn ich auf EXT3 und EXT4 eingehe, näher beschreiben. Das kann man auch relativ einfach auslesen. Mit TuneToWeb S-L kann man sich einmal den Superblock ausgeben lassen. Und für ein frisch formatiertes EXT4 sieht es so aus.

Die interessanten Features sind hier Has Journal. Ich habe Journaling an. Frontier-Index ist ein Feature, das ich später beschreibe, was Directories besser macht. File-Type heißt, dass mein Directory-Entry das File-Type-Entry hat. Extent heißt, ich benutze Extents. Das komme ich auch noch zu.

Large-File und Huge-File beschreiben, sind zwei Large-File, größer als zwei Gigabyte. Huge-File beschreibt auch eine andere Messung von Blöcken. Aber die ist nicht so dramatisch interessant. So, als kurzen Einschub.

The Ubiquitous D-Tree. Das ist auch der Titel von einem Paper. Jeder, der mal Details von B-Trees wissen möchte, kann ich das Paper empfehlen. Das ist von Ende der 70er. Beschreibt alles Mögliche. Hat auch interessanterweise eine Section darüber, warum das B-Tree heißt. Das B kommt wohl von Balanced Bushy vielleicht.

Oder von Bayer, so heißt einer der Empfinder. Auf jeden Fall. Wie funktionieren die? So als Vorgreif. Search-Trees. Also Suchbäume sind häufig binär, nicht unbedingt.

Und es sind Bäume, die eine sogenannte Sucheigenschaft haben. Zum Beispiel links kleiner, rechts größer. Das benutzt man, um schnell in einer Menge von Daten das zu finden, was ich möchte. Und das, was in dem Kringle steht, ist immer der Key. Und irgendwo an dem Key hängen normalerweise die Daten.

Wichtige Eigenschaften davon, die man gerne hat, ist, dass das Zeug balanciert ist. Weil dann kann man über die Laufzeit Garantien machen. Zum Beispiel, dass es nicht wirklich gerade balanciert. Was ist jetzt ein B-Tree dagegen? Ein B-Tree hat auch diese Sucheigenschaft. Aber es ist pro Knoten nicht nur ein Key, sondern mehrere.

Und zwar üblicherweise in einer Art Größe von einem Block. Bei den Dateisystemen ist es üblicherweise ein Dateisystem Block, was eine Menge von Keys enthält. Zum Beispiel sind die Keys auch sortiert.

Das heißt, wenn ich mit meiner Anfrage rankomme, zum Beispiel nach einer Blocknummer, kann ich da durchgehen und finde irgendwann, was ich möchte. Die Standard B-Trees speichern die Daten in den Zwischenknoten. Das hat aus verschiedenen Gründen Nachteile. Unter anderem, weil die Daten könnten groß sein.

Und man verschwendet ein bisschen Platz in den Zwischenknoten. Deswegen verwenden fast alle Dateisysteme, die ich gesehen habe, eine Variante davon, die sich B-Plus-Trees nennt, wo die Daten am Ende in den Leaf-Knoten rumliegen. Wie das im Detail aussieht, wie im Detail die Dateisysteme B-Trees verwenden, zeige ich gleich.

Erstmal die nächsten Dateisysteme. So, und zwar, man kann XC3 und XC4, ich meine mittlerweile gibt es im Kern nicht mehr eine XC3-Implementierung,

sondern nur noch XC4, man kann die Unterschiede etwa an den Features ausmachen, die dazukamen. Zum Beispiel in XC3 kam Dear Index und Journaling. XC4 ist eins der wichtigsten Sachen Extents. Das sind nicht die einzigen Sachen, die dazwischen kamen. Das sind die strukturellen interessanten Sachen, die ich jetzt vorstellen werde.

Ich fange an mit Journaling. Die Motivation unter Journaling ist, stellt euch vor, ich mache drei Änderungen an meiner Einhold. Mein Computer stirbt und ich habe eine davon nicht geschrieben. Das ist natürlich Käse, weil würde ich dann das Dateisystem irgendwann wieder mountain, steht an einer Stelle etwas, was nicht konsistent ist mit den anderen Einträgen.

Und die Idee dahinter ist, ich schreibe zusätzlich ein Log. Das ist etwas, was in vielen Datenbanken auch gemacht bin. Das ist ein allgegenwärtiges Konzept beim Abspeichern von Daten. Hier unten habe ich mal so einen Log beschrieben. Das heißt, bevor ich meine Änderung mache, mache ich so eine Art Transaktion.

Ich entkapsel meine Änderungen alle zusammen und schreibe die in ein Log. Und ich schreibe die Sachen in ein Log auf eine Art, sodass sie auch wirklich da ankommen. Und nicht in irgendeinem Cache rumliegen. Und dann mache ich erst mal eine Änderung am Dateisystem. Das heißt, wenn ich den Crash habe, weiß ich, ich replye dann nach meinem Log.

Ich wende dann einfach meine Einträge im Log wieder an nach dem nächsten Mountain. Und weiß, dass ich in einem konsistenten Zustand bin. Weil ich immer eine Menge von Änderungen habe. Dann als nächstes Feature, Directory Indexes.

Wie ich am Anfang gezeigt habe, sind Directories. Ich habe auch nie erklärt, wofür diese Löcher sind. Diese Löcher sind Padding. Also, das wird auf Vielfache von irgendwas gepaddelt, die Einträge.

Wie funktioniert jetzt die Indexing? Also, die Motivation war dafür, dieses lineare Search dadurch dauert lange. Und es ist nicht unbedingt die beste Art und Weise, Dateien zu finden in einem großen Directory. So, und die Idee ist, ich benutze ein B-Tree. Und zwar, wo die Keys Hashes sind von Dateinamen.

Im Moment ist es die Hälfte eines MD4 Hashes. Das heißt, ich habe in meinen Einträgen, ich habe Indexeinträge. Die fangen mit einem Header an. Und danach habe ich jedes Mal so ein Element, wo steht Hash.

Hash ist nichts anderes als eine Zahl. Ich habe die Hashes sortiert. Und von jedem Hash zum nächsten Hash habe ich so einen Bereich, der sagt, dieser Bereich von Hashes liegt in diesem Block. Dieser Bereich von Hashes liegt in diesem Block. Und der nächste Bereich von Hashes liegt im nächsten Block. Sodass ich die Suche eingrenzen kann. In den Leafknoten von dem Tree liegen immer noch,

wie früher, ganz normale Directory-Indexes drin. Das ist auch ein Read-only-compatible-Feature. Das heißt, ich kann auch Read-only dieses Datalsystem immer noch lesen. Später.

Weil die Datenstrukturen sich nicht großartig geändert haben. Jetzt die Frage, wo blende ich denn diesen Hash-Key-Kram unter? Ich kann nicht einfach einen neuen Platz dafür finden. Deswegen, der Trick an der Sache ist, wir stopfen ihn einfach in die Directory-Entries mit rein.

Das heißt, wir produzieren so zwei Fake-Einträge, die einfach sagen, ja, hier ist so ein Entry, den überspringen wir mal. Und dazwischen stopfen wir die H-Tree. Das ist ein anderer Name für diese Directory-Index-Hash-Trees. Für die stopfen wir diesen H-Tree rein.

So, das ist die ganze Magie hinter großen Directorys. Als nächstes das Kernfeature, was mit EXT4 kam. Extents. Was ist grob ein Extents? Also nicht nur grob, was ist ein Extents? Und zwar ist es ein Dreitupel aus logischer Blocknummer,

Länge und physikalischer Blocknummer. Das heißt, ich fange irgendwie bei Byte 5 in der Datei an, habe 10 Gigabyte, fängt auf der Festplatte bei Block 5 Millionen an. Das ist ein Extents. Was mache ich nun? Wo bringe ich das Ganze unter? Na ja, ich habe ja Einträge für meine Blockmap in der Inode.

Und zwar ganze 60 Byte. Das heißt, kann man ja auch für was anderes nehmen. Zu anderem gibt es auch das Feature, mittlerweile in EXT4 Inline-Data zu haben. Ich kann auch einfach direkt die 60 Byte-Daten da rein stopfen. Oder ich stopfe Extents da rein.

Von der Länge her passen maximal vier Extents direkt da rein. Sollte das nicht reichen, baue ich mir einen B-Tree aus Extents. Aber erstmal, ein B-Tree würde dann ungefähr so aussehen. Ich habe in meinen 60 Byte, anstatt dass ich direkte Extents da drin habe,

habe ich so einen Index-Record von einem B-Tree, wo ich erst ein Index habe, das ist sortiert nach den logischen Blocknummern. Das heißt, ich kann dann einfach ein B-Tree traversieren und irgendwann lande ich wieder auf diesmal etwas größeren Extent-Blöcken. Was ist der Unterschied zu der Blockmap?

Und warum sollte ich das überhaupt machen? Das Schöne daran ist, es ist eine viel kompaktere Art und Weise, zusammenhängende Daten zu beschreiben als Blockmaps. Ich habe hier mal für eine Blockmap dran geschrieben, wie weit ich komme, wenn ich 4K-Blöcke habe. Mit den ersten 12 Direct Entries komme ich 48 Kb weit,

mit den Indirects komme ich 4 Megabyte, dann komme ich mit den Double Indirects 8 Gigabyte und dann komme ich irgendwann auf 4 Terabyte weit. Das heißt, durch zum Beispiel mit einem Extent kann ich beschreiben, von 0 bis 10 Gigabyte fängt da an.

Um das Gleiche zu beschreiben mit Blockmaps, muss ich bis Triple Indirection durchgehen. Diese Blöcke muss ich auch noch mit einrechnen, die verschwenden zusätzlich Platz. Das ist der große Vorteil von Extents. Der größte Nachteil von Extents ist,

diese Blockmaps, ich kann es berechnen, wo ich nachgucken muss. Ich habe eine logische Adresse, ich kann mir ausrechnen, ja, das ist das Feld in Triple Indirection, weil diese Range ist immer konstant. Ich fange immer vorne an und fülle nach hinten auf.

Ich kann ausrechnen, das ist die Triple Indirection, ich hole mir den Block, ich kann ausrechnen, welchen Eintrag ich nehmen muss, ich kann ausrechnen, welchen Eintrag ich nehmen muss, bis ich am Ende bei den Daten ankomme. Bei Extents muss ich eventuell durch einen B-Tree durchsuchen, um den richtigen Eintrag zu finden.

So, das waren die Extratei-Systeme. Ich habe jetzt noch eine Kleinigkeit zu XFS. Als ich mir XFS angeschaut habe, war ich relativ erstaunt, dass das gar nicht so sehr unterschiedlich mehr von XC4 ist, also von den Strukturen auf der Festplatte.

Allerdings, ein großer Teil von Dateisystemen ist auch, wie werden Sachen allokiert und wie werden Sachen zusammenhängt allokiert und wie macht man das so, dass es parallel gut funktioniert. Das ist etwas, was ich mir nicht angeguckt habe, da kann man Vorlesungen für füllen. Wie man die passenden Logs setzt und wie man es schnell macht.

Zu XFS, es ist ein Import von SGI IRIX. Es benutzt B-Trees für so ziemlich alles, was geht, an Metadaten. Und es ist auch ein Journaling-Fallsystem. Die Struktur von einem XFS sieht ein bisschen anders aus,

also sieht auf den ersten Blick fast aus, wie das mit den Block Groups. Allerdings sind Allocation Groups wesentlich größer. Block Groups sind mit Standard-Einstellungen etwa 128 MB lang. Und diese Allocation Groups sind eher so in Gigabyte-Bereich oder in 100 Gigabyte-Bereich.

Jede Block Group ist mehr oder weniger ein kleines, eigenes Dateisystem. Es beschreibt den freien Platz. Es beschreibt auch, welche Einhauts existieren. Und zwar kann XFS benutze dynamische Einhauts, wo die EXT-Dateisysteme eine feste Tabelle hat. Es gibt mittlerweile auch Extensions, um die zu erweitern.

Aber in den ursprünglichen Versionen gab es eine feste Tabelle. Und waren diese Tabellen alle voll, hatte ich ein Problem. XFS umgeht das, indem man Einhauts später dazu allokieren kann. Auch benutzt es in jeder Allocation Group relative Adressen.

Das heißt, ich spare ein bisschen Platz in meinen Pointeren und kann am Ende mehr Platz adressieren. Interessant beim Free Space Management ist, dass es mit zwei B-Trees verwendet wird. Und zwar einer ist sortiert nach Blocknummer und einer nach Größe. Das heißt, wenn ich mit einem großen Anfrage ankomme,

ich hätte gerne 4 Gigabyte, kann man einfach gucken, ah ja, ich gehe mal einen B-Tree durch, hier sind 4 Gigabyte frei, ich nehme die mal. Das Ganze ist sortiert nach Blocknummer. Zum Beispiel, wenn ich eine Datei habe, die wächst über die Zeit, dass ich sehen kann, dass ich möglichst Lokalität auf meiner Disk erhalte.

Die Einhauts enthalten so einen, die nennen das Data Fork, das beschreibt mehr oder weniger nicht die Blockmap, sondern das ist in der Einhaut der Ort, wo die Extensions liegen. Es kann auch Inline Data, es kann auch Extensions, es kann auch B-Trees, um die Datenblöcke zu adressieren.

Für Directory Entries ist das Ganze noch viel komplizierter. Ich glaube, ich habe sieben verschiedene Arten Directories zu speichern gesehen, die alle je nach Größe eingesetzt werden. Was man sehr gut an XFS erkennen kann, ist, das Ding ist nicht so historisch gewachsen wie die EXT-Datisysteme,

so dass man aus EXT 2 erweitert hat in 3, in 4, sondern dass es mal designt wurde und so umgesetzt wurde mit den Features, die man dachte, dass man sie braucht. Das war alles zu dem Jetzt. Ich habe noch ein bisschen Outlook,

was gerade so ein Programm ist, eine ganze Slide zu geben. Was ist also zum Beispiel das Interessante an XFS? Das Interessante an ZFS ist, es ist so ein schichtenweise organisiertes System.

Unten zum Beispiel Festplatte da drauf, das Dateisystem geht nicht direkt. Das Dateisystem ist mehr oder weniger eine Schicht über der Data Management Unit. Das ist ein Subsystem, was sich darum kümmert, Objekte und Transactions zu ermöglichen. Das Dateisystem ist also auch nur eine Sicht auf einen Layer.

Dieser Data Management Unit benutzt einen Storage Pool Allocator,

basiert auf dem Slab Allocator. Man kann sich das so vorstellen, dass man so einen malloc oder free für Bereiche auf der Festplatte machen kann. Das ist auch der Ort, der diese ganzen RAID-Sachen implementiert. Das sind die interessanten Sachen da dran.

Was sind die strukturell interessanten Sachen an ButterFS? Jedenfalls auf meiner Sicht ist, die benutzen B-Trees für so gut wie alles es geht. Und zwar eine spezielle Variante von B-Trees, die Copy-and-Write-fähig ist. Das sind Standard B-Trees nicht, aus Gründen, dass das Balancieren für Copy-and-Write nicht so optimal ist.

Wer ist interessiert? Ich kann das Paper raussuchen, was diese Copy-and-Write-B-Trees beschreibt. Zum Beispiel gibt es B-Trees, die die Dinos beschreiben und Dateien und Verzeichnisse und die Allocation beschreiben.

Ein paar Worte zu F2FS. Alle Dateisysteme, die ich bis jetzt beschrieben habe, sind für die Festplatte optimiert und versuchen Lokalität herzustellen und haben zum Beispiel so Features wie Logs, die immer an die gleiche Stelle schreiben, was für Dinge wie Flash-Storage ein Problem darstellt.

Zum Beispiel gibt es seit ein paar Jahren F2FS, was nicht für Disks optimiert ist, sondern für Flash-Storage. Der große Unterschied zu den Blog-Storage-Filesystemen ist, dass es log-structured ist.

Man kann sich das vorstellen, wie das Fall ist im Journal, was ich eben beschrieben habe. Man schreibt Dinge einfach immer hintereinander da drauf. Man überschreibt nicht einfach irgendwelche Sachen in Plays, sondern man möchte etwas Neues. Man hängt es hinten an. Das hat den großen Nachteil, dass man hier plötzlich leere Blöcke bekommt

und die irgendwie wieder füllen muss. Man muss vielleicht Sachen umkopieren für Compaction. F2FS löst das auf eine sehr elegante Weise. Es hat auch nicht nur ein Log, sondern es werden sechs für verschiedene Hotness von Daten,

je nachdem, wie oft sie gebraucht werden. Das waren die Dateisysteme. Was habe ich erzählt? Ich habe ein bisschen Grundlagen, Einnotes, Directory Entries erzählt. Danach, wo kam es her? Unix, das Unix Version 6-Filesystem, das Minix-Filesystem.

Dann ein bisschen was zum FAT-Filesystem. Danach die ganzen X-Filesysteme bis heute. Wie ist das Layout? Wie sehen Einnotes aus? Wie sehen Verzeichnisse aus? Was sind die Optimierungen, die zwischendurch zum Beispiel in XT3 kamen? Wie das Journal, wie H3-Verzeichnisse.

Was sind Extends und wie werden sie verwaltet? Wie sieht XFS im Vergleich mit EXT4 aus? Was ist der Startpunkt für die aktuellen Dinge?

Danke für eure Aufmerksamkeit. Fragen? Welches ist dein Lieblings-Filesystem?

Welches ist dein Lieblings-Filesystem, mit dem du am liebsten Ernst-Darf-Sauce-Coat-Raw-Filesystem nicht verlieren möchtest? Kommt drauf an. Die Dateisysteme sind immer sehr anwendungsspezifisch.

Ich bin meistens ein bisschen konservativ neben EXT4, wo es geht. Am Ende des Tages muss man messen. Was am besten funktioniert für die Anwendung? Diese Systeme sind so komplex, dass man nicht wirklich drumherum kommt. Nur vom Verständnis der Datenstrukturen zu sehen,

welches besser performt für irgendeine Anwendung. Excuse me, can you wipe the microphone, please? We're streaming this live. Which one of these detects mutilation in the data blocks? Mutilation in the data blocks? Yes, when your data are corrupted,

instead of when your metadata are corrupted. I know ZFS has checksumming for data blocks. BTRFS, I'm not sure, but it has also that. ZXFS, I think only for metadata.

That doesn't detect corruption, right? Well, if the corruption happens while crashing or something, you can enable data journaling for the EXT file systems, but it doesn't have checksums. There are metadata checksums for it.

But there isn't really silent data corruption detection. For example, in ZFS there is scrubbing you can do when the file system is idle. EXT4 has for some years now metadata checksums, which I think the latest Ubuntu release also supports in New Zealand.

You just said that the data systems are paying attention to locality,

because the old hard drives still had these writing heads. How important is that for the SSD hard drives? Are there data systems that are optimizing for that?

Yes, it's also relevant for SSDs. But in a different way. I'm not a specialist in SSDs. A colleague of mine is. What I know roughly is that in-place updates are a bit bad,

because I end up having problems with the garbage collection on SSDs. F2FS is the only file system I know that is optimized for SSDs. It was developed by Samsung.

It looks at how the SSD is created and tries to optimize data access, so that you get as much lifetime as possible at the end. That's just a reminder. BateraFS does that too. It can recognize whether it is a rotating disk or a solid state.

If it's a solid state disk, it lets all optimizations, which it normally does for the rotating disk, go to waste. But it doesn't have lifetime optimization, does it? Maybe as a side effect, but the special effect is that you can push the latency down.

Also something. I'll go all the way back. You just mentioned F2FS. It looks at how the SSD is structured.

I had the impression that F2FS was built for flash media without a flash translation layer. Something like an SPL Norflash, for example, is that it doesn't have its own intelligence. Was that a misunderstanding on my part? I think someone has the answer.

Oh, that's a lot of running. Hi. F2FS is optimized for disk or block devices that have an FTL in between.

F2FS can be tuned a bit. Depending on what the FTL can do, it can write and manage so and so many streams of data at the same time. Then F2FS is tuned a bit by itself. F2FS is not for NAND or NOR or anything else for embedded devices that don't have an FTL.

There are other data systems like UBFS, JFF2 and a few other things.