Filsystemer, journaling og crash consistency

Filer, kataloger og inoder

Et filsystem må mappe to ting: brukerens navnerom (filstier, kataloger, åpne handles) og diskens råstoff (blokker og metadata-strukturer). I midten står inode, datastrukturen som lagrer alt om én fil: størrelse, eier, rettigheter, timestamps og pekere til datablokker. Filnavnet er ikke i inoden — det ligger i en katalog sammen med inode-nummeret.

En path (filsti) som /usr/test.txt er bare en menneskelesbar nøkkel. For å finne data må filsystemet traversere fra rot: slå opp usr i rotkatalogen, så slå opp test.txt i usr-katalogen, og lese inoden den peker på. Hardlenker er mulig nettopp fordi flere navn kan peke på samme inode — det er navnene som telles, ikke filen. En inode har en nlink-teller, og fil-data slettes først når både nlink = 0 og ingen prosess har filen åpen.

Inoden selv bruker en blanding av direkte og indirekte pekere for å adressere data. De første pekerne (typisk 12 i ext-familien) peker rett på datablokker — billig oppslag for små filer. For større filer brukes én eller flere indirekte pekere som peker på en blokk full av flere pekere. Doble og triple indirekte pekere gir plass til filer i terabyte-klassen uten å gjøre selve inoden stor.

Hele organiseringen kommer fra superblock: en liten metadata-blokk øverst på filsystemet som forteller størrelse, antall inoder, antall datablokker, og hvor inode-tabellen starter. Det er det første som leses ved mount, og det første som må være konsistent etter et krasj.

Allokering — bitmaps og frie blokker

Filsystemet trenger raskt å finne en ledig inode eller datablokk. To bit-arrayer holder oversikten: inode bitmap og data bitmap. Hver bit er én ressurs — 0 betyr ledig, 1 betyr i bruk. free-space management er navnet på hele denne mekanismen, og det kan også implementeres som lenkede lister eller B-trær, men bitmaps er konseptuelt enklest og rask å skanne.

Når en ny fil opprettes, må filsystemet finne ledig bit i hver bitmap, sette dem til 1, skrive inoden, oppdatere katalogen, og oppdatere katalogens egen inode (siden mtime endres). ƒblock-sekvens for create(/test.txt) viser hvor mange skrivinger som faktisk skjer for én create. Det er derfor filopprettelse er dyrt sammenlignet med en enkel append til en eksisterende fil.

Hva skjer i en read eller open?

For å åpne en fil må filsystemet traversere katalogtreet. ƒblock-sekvens for open(/foo/test.txt) skisserer rekkefølgen: les rot-inoden, les rot-data for å finne neste mappe, les neste inode, og så videre. Selve filinnholdet leses ikke før første read()-kall. Hver lookup koster minst én I/O hvis cachen er kald.

På prosess-siden returnerer open() en file descriptor (fd) — et lite heltall som er indeks i prosessens private fil-tabell. Verdiene 0, 1 og 2 er reservert som stdin/stdout/stderr (stdin, stdout, stderr). Derfor returnerer første egen-fil typisk fd=3. Konvensjonen lar oss regne baklengs: ƒfd-konvensjon sier at hvis open() returnerer 5, var det 2 egen-filer åpne fra før.

Tabellen heter ofile[]-tabell (i xv6 og lignende kjerner). Indeksen er fd, verdien er en peker til en delt struct file som inneholder offset, modus og inode-peker. Det er derfor dup() og fork() kan dele samme offset mellom flere fd-er — de peker på samme bakomliggende rad. To uavhengige open()-kall på samme fil gir derimot ulike struct file-rader med egen offset, så de leser fra hver sin posisjon.

Buffer-cache — bytt I/O mot minne

Disken er treg, minnet er raskt. buffer cache holder nylig brukte blokker i RAM så de slipper å leses på nytt. Den dekker både metadata (inoder, kataloger, bitmaps) og data. Skriveoperasjoner havner først i cachen og flushes asynkront — det gir batching og mye bedre gjennomstrømning.

Ulempen er at en skriving ikke er trygg før den faktisk er på disk. Hvis strømmen forsvinner mellom cache-skriving og flush, kan filsystemet bli inkonsistent. fsync() finnes nettopp for å tvinge frem en disk-skriving når applikasjonen trenger en hard garanti. Det er også broen til neste tema: crash consistency.

Crash consistency — det vanskelige problemet

Tenk på en enkel filappend: filsystemet må skrive ny datablokk, oppdatere inoden med ny størrelse og peker, og oppdatere data-bitmap-en. ƒfilsystemoperasjon som blokksekvens oppsummerer at hver operasjon er flere ting som må skje sammen. Disken garanterer ingen rekkefølge utenom den filsystemet eksplisitt ber om — og selv da kan en strømsvikt komme mellom hver enkelt skriving.

crash consistency er egenskapen at filsystemet etter et krasj fortsatt er i en gyldig tilstand: alle inoder peker på data som er allokert, alle ledige blokker er virkelig ledige, og ingen referanser er dinglende. Naive filsystemer kan ende opp med en allokert blokk som ingen fil eier (lekkasje), eller en katalog som peker på en inode som ble overskrevet av en annen fil — langt verre enn lekkasje.

Fsck — rydde opp etterpå

Den gamle løsningen er fsck: etter krasj går et eget verktøy gjennom alle metadata-strukturer og leter etter inkonsistens. Marker blokker som er pekt på men ikke allokert; deallokér foreldreløse inoder; rydd opp i kataloger som peker ingensteder.

Fsck virker, men skalerer dårlig. På en 10 TB-disk kan en full sjekk ta timer, og hele tida er filsystemet utilgjengelig. Moderne systemer aksepterer ikke det oppetidstapet, så filsystemene designes for å sjelden trenge fsck etter normale krasj.

Journaling — write-ahead logging

journaling / wal løser problemet ved å skrive en plan før selve oppdateringene. ƒskriveorden i journaling sier rekkefølgen: først logges hva som er tenkt å skje (alle bitmap-endringer, inode-oppdateringer, dirent-tillegg) til en separat logg på disk. Når loggposten er stabil, skrives en commit-rekord. Først etter commit får oppdateringene gå til sine «hjemmebaser» i filsystemet.

Etter krasj sjekker filsystemet loggen: alle transaksjoner som har commit-rekord spilles av på nytt (redo); de uten droppes. Etter at alle transaksjoner er ferdig spilt, kan loggen rotlegges. Recovery tar typisk sekunder, ikke timer.

ext3/ext4 og NTFS bruker varianter av dette. Ofte logges bare metadata (data ordering er løsere) for å spare skrive-arbeid — kalt ordered mode i ext-familien. Det handler om én balanse: full data-journaling er tryggest, men dobler I/O fordi alt skrives to ganger; metadata-journaling er raskere, men beskytter ikke hver byte av filinnhold mot delvise skrivinger.

En ofte oversett detalj er at selve commit-rekorden må skrives atomisk. Disker garanterer atomisk skriving for én sektor (typisk 512 bytes eller 4 KB), så commit-rekorden lages liten nok til å passe i én sektor. Hadde den vært større, kunne en strømsvikt midt i selve commiten ført til et halv-committet — og derfor uleselig — loggsteg.

Log-strukturerte filsystemer

En radikalere variant er log-strukturert filsystem. I stedet for å oppdatere blokker på sine gamle plasseringer, skrives alt sekvensielt til en stadig voksende logg. Inoder, data, alt sammen. Gamle versjoner av blokker blir foreldreløse og samles inn av en garbage collector senere.

Fordelen er at alle skrivinger er sekvensielle — perfekt for både roterende disker (ingen seek) og SSD-er (færre erase-sykluser, vennligere mot wear-leveling). Ulempen er kompleksiteten i GC og hyppige reorganiseringer. Moderne SSD-er gjør internt noe lignende uavhengig av filsystem-laget, og systemer som NILFS, F2FS og deler av ZFS bygger eksplisitt på log-strukturerte ideer.

Endelig setter ƒusable space en grense: en filsystemstørrelse er aldri lik diskens råstoff. Metadata, journal-områder og reserverte blokker spiser sitt — derfor viser df alltid mindre enn produsenten lover. På en typisk ext4-formattering går rundt 1–2 % til inode-tabellen alene, og noen prosent ekstra reserveres for root så systemet kan logge inn selv når brukerprosessene fyller opp disken.

Den røde tråden gjennom hele kapittelet er at filsystemet sjonglerer mange små skrivinger som hver må komme i riktig rekkefølge for at metadata, data og rydding skal stemme overens. Disker og SSD-er gir få garantier av seg selv — det er filsystemets ansvar å bygge dem oppå primitivene som fsync og barrier. Når journaling, log-strukturering og smart cache-håndtering er på plass, kan man miste strømmen midt i en write() og likevel mounte igjen i en konsistent tilstand. Det er denne illusjonen av atomisitet, bygd på flokete I/O-rekkefølger, som gjør at brukere kan stole på filsystemet i det hele tatt.