Bestandssystemen

Een bestand is een persistente reeks bytes. Het bestandssysteem slaat die bytes op zonder te bepalen of ze tekst, een afbeelding of machinecode voorstellen. Een directory geeft het bestand een leesbare naam; het inodenummer identificeert het binnen het bestandssysteem.

Open een bestand en controleer het resultaat

open(path, flags, mode) geeft een bestandsdescriptor terug, een niet-negatief geheel getal dat in latere aanroepen wordt gebruikt. Bij een fout geeft de aanroep -1 terug en stelt errno in. Kies O_RDONLY, O_WRONLY of O_RDWR voor de toegang. O_CREAT maakt een ontbrekend bestand aan, O_TRUNC maakt een bestaand bestand leeg en O_APPEND plaatst elke schrijfbewerking aan het huidige einde.

Voor een nieuw bestand vraagt mode toegangsrechten aan en verwijdert de umask van het proces bits. Zonder standaardtoegangscontrolelijst (ACL) op de directory is het resultaat mode & ~umask. Als je 0666 aanvraagt met umask 0022, krijg je 0644, oftewel rw-r--r--. Dit argument verandert de toegangsrechten van een al bestaand bestand niet.

Descriptoren horen bij een proces. Normaal zijn 0, 1 en 2 de standaardinvoer, standaarduitvoer en standaardfoutuitvoer. open kiest de laagste ongebruikte descriptor, vaak 3. Op Linux laat strace cat notes.txt de aanroepen zien: de invoer openen, die lezen, naar descriptor 1 schrijven en de invoer sluiten.

Volg de bestandspositie, niet het gevraagde aantal

read(fd, buf, n) geeft het daadwerkelijk gelezen aantal bytes terug, maximaal n. Bij een verzoek om een aantal groter dan nul voor een gewoon bestand betekent nul dat op of voorbij het bestandseinde geen bytes over zijn; -1 betekent een fout. write geeft ook een werkelijk aantal terug, dat lager kan zijn dan gevraagd. Controleer dat aantal voordat je verdergaat in een buffer of besluit dat de bewerking voltooid is.

Stel dat log.txt 300 bytes bevat. Vier verzoeken om 100 bytes geven 100, 100, 100 en 0 terug. De bestandspositie, de positie van de volgende bewerking, wordt 100, 200, 300 en 300. Het bestandseinde is een teruggegeven aantal, geen speciale byte die in het bestand is opgeslagen.

lseek(fd, 200, SEEK_SET) stelt de positie in op 200. Een daaropvolgende leesbewerking van 50 bytes geeft bytes 200–249 terug en laat de positie op 250 staan. SEEK_CUR meet vanaf de huidige positie; SEEK_END meet vanaf het bestandseinde. De positie verplaatsen verandert een getal in het geheugen. Het verplaatst geen schijfkop en leest zelf geen gegevens. pread en pwrite gebruiken een expliciete positie zonder deze bestandspositie te veranderen.

Bepaal welke descriptoren een bestandspositie delen

De descriptortabel van het proces verwijst naar vermeldingen in de tabel met geopende bestanden van de kernel. Elke vermelding bevat de toegangsmodus, bestandspositie, inodeverwijzing en verwijzingsteller.

Als een kindproces een gedeelde descriptor naar byte 10 verplaatst, begint de volgende leesbewerking van het ouderproces via die vermelding ook op 10. De inode identificeert het bestand, maar de vermelding bevat de bestandspositie: twee lezers kunnen een bestand delen zonder hun positie te delen. De shell gebruikt dup2 bij omleiding om de standaarduitvoer naar een andere vermelding te laten verwijzen. close geeft één descriptor vrij; de vermelding verdwijnt nadat de laatste verwijzing is vrijgegeven. Sluiten alleen dwingt gebufferde gegevens niet naar stabiele opslag.

Een geslaagde schrijfbewerking en een wijziging die een crash overleeft, beantwoorden verschillende vragen. Een schrijfbewerking meldt dat bytes zijn geaccepteerd. Duurzaamheid gaat over de vraag of ze een crash overleven; atomiciteit gaat over de vraag of een wijziging alleen als geheel zichtbaar kan zijn.

Dwing de bytes naar stabiele opslag

Besturingssystemen bufferen schrijfbewerkingen meestal in het geheugen en sturen gewijzigde blokken later naar opslag, vaak binnen ongeveer 5–30 seconden. Dit combineert kleine schrijfbewerkingen en laat het programma snel doorgaan. Een crash kan gegevens wissen die nog in die buffers wachten.

fsync(fd) dwingt de gewijzigde gegevens en metadata van het bestand naar opslag en wacht tot het apparaat voltooiing meldt. Een programma moet het resultaat controleren voordat het meldt dat gegevens duurzaam zijn opgeslagen. close geeft de descriptor vrij en vervangt dit wachten niet.

Een bestand heeft ook een duurzaam opgeslagen naam nodig. De vermelding die de naam aan de inode koppelt, is onderdeel van de gegevens van de directory, niet van het bestand. Als je na het aanmaken van een bestand alleen het bestand synchroniseert, kunnen de bytes duurzaam zijn opgeslagen zonder de garantie dat de nieuwe naam behouden blijft. Open de bovenliggende directory en synchroniseer die wanneer de naam behouden moet blijven.

Vervang een bestand zonder een gedeeltelijke versie te tonen

Een document op de bestaande plaats overschrijven creëert een periode waarin lezers onvolledige inhoud kunnen aantreffen. O_TRUNC stelt de lengte eerst in op nul. Als een crash de latere schrijfbewerkingen onderbreekt, is de oude volledige kopie al verdwenen.

Schrijf de vervanging daarom onder een tijdelijke naam in dezelfde directory. Gebruik daarna rename om het doel te vervangen. Voor een bestaand doel op hetzelfde bestandssysteem maakt POSIX die vervanging atomair: de doelnaam verwijst naar het oude bestand of naar de vervanging, zonder dat de naam tussendoor ontbreekt. Lezers zien via die naam geen mengsel van de inhoud van beide bestanden.

Voor settings.json is de volgorde voor duurzame vervanging:

1. Schrijf de volledige nieuwe inhoud naar settings.json.tmp en controleer op schrijfbewerkingen met minder geschreven bytes dan aangevraagd en op fouten.
2. Roep fsync aan op het tijdelijke bestand en controleer of dat lukt.
3. Roep rename("settings.json.tmp", "settings.json") aan en controleer of dat lukt.
4. Roep fsync aan op de bovenliggende directory en controleer of dat lukt.

Het tijdelijke bestand is volledig en duurzaam opgeslagen voordat de naam verandert. De laatste synchronisatie van de directory maakt die naamswijziging duurzaam. Een crash tijdens de reeks laat het doel achter met een volledige oude of volledige nieuwe versie; na de laatste geslaagde synchronisatie is de nieuwe versie duurzaam opgeslagen. Alleen atomaire vervanging van de naam garandeert niet dat een niet-gesynchroniseerde hernoeming stroomuitval overleeft.

rename tussen bestandssystemen mislukt met EXDEV. Een commando dat daarop reageert door te kopiëren en te verwijderen, voert meerdere bewerkingen uit, zodat die terugvaloptie geen atomaire vervanging garandeert.

Verander de lengte zonder elke byte te schrijven

truncate(path, length) en ftruncate(fd, length) stellen de lengte van het bestand in. Inkorten verwijdert bytes voorbij het nieuwe einde. Bij verlengen wordt het nieuwe gebied als nullen gelezen. Ook als je de positie voorbij het einde verplaatst en daarna schrijft, ontstaat een tussenruimte die als nullen wordt gelezen.

Een dunbezet bestand kan zo'n tussenruimte voorstellen zonder er gegevensblokken voor toe te wijzen. Als je met een leeg bestand begint en één byte op positie 8192 schrijft, ontstaat een bestand van 8193 bytes; het voorafgaande ongeschreven gebied wordt als nullen gelezen. De logische grootte kan groter zijn dan de fysiek toegewezen ruimte.

Directory's scheiden de namen die mensen gebruiken van de objecten die het bestandssysteem opslaat. Elke directory heeft een eigen inode en gegevensblokken; de vermeldingen koppelen namen aan inodenummers.

Volg paden door de boom

Een absoluut pad begint bij /. Een relatief pad begint bij de huidige werkdirectory van het proces. De vermelding . duidt de directory zelf aan en .. de bovenliggende directory; de bovenliggende directory van de hoofddirectory is de hoofddirectory zelf. Vanuit /home/lee bereik je met het relatieve pad ../shared de directory /home/shared.

Een extensie zoals .txt maakt deel uit van een naam. Programma's kunnen die gebruiken om te kiezen hoe ze de bytes interpreteren, maar het bestandssysteem vereist niet dat een .txt-bestand tekst bevat.

mkdir maakt een directory aan met . en ... Om vermeldingen weer te geven, gebruikt een programma opendir, roept het readdir aan totdat er geen vermeldingen meer zijn en roept het closedir aan. Een resultaat van readdir bevat een naam en inodenummer. Programma's wijzigen directory-inhoud via aanroepen zoals link, unlink en rename, niet via gewone write-aanroepen. rmdir verwijdert een lege directory.

Geef één bestand twee gelijkwaardige namen

link(old, new) maakt een harde koppeling: een extra directoryvermelding die naar dezelfde inode verwijst. Geen van beide namen heeft een bevoorrechte positie als origineel. Het aantal harde koppelingen van de inode geeft aan hoeveel namen ernaar verwijzen.

Bekijk deze commando's wanneer geen proces het bestand open heeft:

echo hi > a
ln a b
rm a
cat b
rm b

Door b aan te maken stijgt het aantal harde koppelingen van 1 naar 2. Door a te verwijderen daalt het tot 1; via b zijn dezelfde bytes nog bereikbaar, dus drukt cat b “hi” af. Door b te verwijderen daalt het aantal tot 0, zodat de inode en de blokken ervan kunnen worden vrijgemaakt.

Een open descriptor voegt een tweede regel voor de levensduur toe. Als de laatste naam wordt verwijderd terwijl een proces het bestand nog open heeft, kan dat proces het blijven gebruiken. Vrijmaken wacht totdat zowel het aantal koppelingen nul is als er geen open verwijzingen meer zijn. Dit verklaart waarom het verwijderen van een groot geopend logboek de ruimte mogelijk niet onmiddellijk vrijgeeft.

Een harde koppeling kan niet over bestandssystemen heen verwijzen: het inodenummer van het doel zou geen betekenis hebben in de andere inodetabel. De meeste Unix-systemen verbieden ook harde koppelingen naar directory's om een boom zonder cycli te behouden. Bij de klassieke Unix-telling van directorykoppelingen heeft een lege directory twee koppelingen, vanuit de vermelding in de bovenliggende directory en vanuit de eigen .. Elke subdirectory voegt er via .. één toe; drie subdirectory's geven een aantal van 5.

Sla een pad op in een symbolische koppeling

Een symbolische koppeling is een afzonderlijk bestand waarvan de inhoud een doelpad is. ln -s /home/ana/report.txt r maakt r aan met het doelpad van 20 bytes als inhoud. Als je de koppeling volgt, wordt dat pad gevolgd. Symbolische koppelingen kunnen over bestandssystemen heen verwijzen en naar directory's wijzen.

Een symbolische koppeling verhoogt het aantal harde koppelingen van het doel niet. Het koppelingsobject bewaren houdt het doel dus niet in stand.

De inhoud van een bestand is slechts een deel van de toestand ervan. Metadata legt vast wie het bestand mag gebruiken, wat de grootte en het type zijn en wanneer het is gewijzigd. Door aankoppeling worden objecten uit meerdere bestandssystemen bereikbaar via één namenboom.

Lees de metadata correct

stat(path, &buf) leest metadata via een pad; fstat(fd, &buf) leest die via een open descriptor. De resultaten omvatten het inodenummer, type, de toegangsrechten, ID's van eigenaar en groep, grootte, toegewezen blokken en het aantal harde koppelingen. De bestandsgrootte telt logische bytes; toegewezen blokken meten de werkelijk gebruikte opslagruimte, die bij een dunbezet bestand kleiner kan zijn dan de logische grootte.

Drie tijdstempels beschrijven verschillende gebeurtenissen:

ctime is niet de aanmaaktijd. Alleen atime bijwerken verandert ctime niet. De klassieke Unix-aanroep stat heeft geen veld voor de aanmaaktijd; Linux statx kan een geregistreerde geboortetijd tonen wanneer het bestandssysteem die ondersteunt.

Ontcijfer toegangsrechtenbits

Lees-, schrijf- en uitvoerrechten worden afzonderlijk vastgelegd voor eigenaar, groep en anderen. Elke klasse vormt één octaal cijfer: lezen is 4, schrijven 2 en uitvoeren 1. Bij rw-r----- krijgt de eigenaar 4 + 2 = 6, de groep 4 en de anderen 0. chmod 640 report.txt stelt die bits in.

Toegangsrechten voor een directory gelden voor namen en het doorlopen van paden. Leesrecht staat toe namen weer te geven. Uitvoerrecht staat doorzoeken toe, wat betekent dat je de directory in een pad mag gebruiken. Schrijfrecht samen met uitvoerrecht staat toe vermeldingen aan te maken, te verwijderen en te hernoemen. De naam kennen kan voldoende zijn om een bestand te openen in een directory met uitvoerrecht maar zonder leesrecht, mits de eigen toegangsrechten van het bestand toegang toestaan. De inhoud van die directory weergeven mislukt nog steeds.

Dit verschil is van belang bij verwijderen: een vermelding verwijderen wijzigt de bovenliggende directory. Het schrijfbit van een bestand bepaalt of je de bytes ervan mag wijzigen; het geeft niet het recht om de naam uit de directory te verwijderen. Root omzeilt de meeste gewone toegangscontroles. Toegangscontrolelijsten (ACL's) kunnen rechten geven aan bij naam genoemde gebruikers en groepen buiten de drie basisklassen.

Koppel een ander bestandssysteem aan

mkfs initialiseert een bestandssysteem op een partitie of ander apparaat, inclusief een eigen hoofddirectory en metadata. Het vernietigt de eerdere bestandssysteeminhoud van het apparaat, dus voer het alleen uit op een apparaat dat voor initialisatie is bedoeld.

mount koppelt die hoofddirectory aan een bestaande directory die het koppelpunt heet. Een schijf die op /media/usb is aangekoppeld, maakt de inhoud van de hoofddirectory daar bereikbaar. De eerdere inhoud van /media/usb is verborgen zolang de koppeling actief is; aankoppelen voegt die inhoud niet samen met de aangekoppelde boom. Als je mount zonder argumenten uitvoert, zie je de huidige koppelingen.

De laag van het virtuele bestandssysteem (VFS) in de kernel geeft ext4, XFS, FAT, geheugenbestandssystemen en netwerkbestandssystemen een gemeenschappelijke interface. Programma's kunnen via elk daarvan open en read aanroepen. De samengevoegde naamruimte voegt de inodetabellen niet samen: gelijke inodenummers op verschillende bestandssystemen kunnen niet-gerelateerde bestanden identificeren. Harde koppelingen en atomaire hernoemingen blijven daarom binnen hun eigen bestandssysteem.

Een bestandssysteem moet zowel onthouden waar bytes staan als welke ruimte beschikbaar is. Een eenvoudige Unix-achtige indeling maakt deze taken zichtbaar door toewijzingsgegevens, inodes en inhoud te scheiden.

Verdeel de partitie in gebieden

Een blok is de basiseenheid voor toewijzing van het bestandssysteem. Een blok van 4 KiB bevat 4.096 bytes, oftewel acht traditionele sectoren van 512 bytes. Binaire groottes gebruiken KiB, MiB en GiB; overdrachtssnelheden zoals MB/s gebruiken decimale miljoenen bytes per seconde.

Het onderwijsontwerp vsfs, het zeer eenvoudige bestandssysteem, bevat deze structuren:

Een bitmapbit van 1 betekent toegewezen; 0 betekent vrij. Het superblok vertelt het besturingssysteem bij het aankoppelen hoe het de rest van de partitie moet interpreteren. De twee bitmaps beschrijven verschillende bronnen: een bestand kan een toegewezen inode hebben voordat het gegevensblokken heeft.

Zoek een inode op nummer

Neem een partitie van 64 blokken met blokken van 4 KiB. Plaats het superblok op blok 0, de inodebitmap op 1, de gegevensbitmap op 2 en de inodetabel in blokken 3–7. Gegevens bezetten blokken 8–63. Vijf inodetabelblokken met inodes van 256 bytes bevatten 80 inodes, omdat elk blok er 16 bevat. Er zijn 56 gegevensblokken. Eén bitmap van 4 KiB kan 32.768 objecten beschrijven, dus blijft in deze zeer kleine indeling een groot deel van elke bitmap ongebruikt.

Als je inodeplaatsen vanaf nul nummert, begint inode 37 op 37 × 256 = 9.472 bytes na het begin van de tabel. De tabel begint op byte 12.288, wat een absoluut byteadres van 21.760 geeft. Deling door 4.096 geeft schijfblok 5 met rest 1.280. Deling door 512 geeft sector 42 met rest 256. Lees het blok of de sector waarin de inode staat en selecteer daarbinnen de bytes van de inode.

De algemene methode is: het begin van de tabel in bytes plus het inodenummer maal de inodegrootte. Houd het beginadres van de tabel apart van de positie van de inode binnen de tabel. Als je dat basisadres weglaat, vind je het verkeerde schijfblok.

Scheid namen, metadata en inhoud

Een inode, of indexknoop, registreert type, toegangsrechten, eigenaar, grootte, tijdstempels, het aantal harde koppelingen, toegewezen blokken en gegevenslocaties. De inode bevat niet de bestandsnaam. De naam hoort in een directoryvermelding, waardoor meerdere namen één inode kunnen delen.

Een directory heeft een inode van het type directory en gegevensblokken met vermeldingen. Een eenvoudige vermelding bevat een inodenummer, recordlengte, naamlengte en naam. Dankzij de recordlengte kan het systeem bij het doorlopen de hele vermelding overslaan, inclusief herbruikbare ruimte die na verwijderen is achtergelaten. Grote directory's hebben baat bij indexen: XFS gebruikt B-bomen en ext4 gebruikt gehashte boomindexen.

Bij het aanmaken van een bestand zoekt het systeem een vrij bit in de inodebitmap en zet het dat bit. Bij het toewijzen van gegevens verandert op dezelfde manier de gegevensbitmap. Een allocator kan een reeks blokken reserveren zodat het bestand aaneengesloten kan groeien. De bitmap geeft aan of een blok vrij is; de inode geeft aan bij welk bestand het hoort. Deze structuren moeten overeenkomen.

Een programma ziet opeenvolgende byteposities, maar de bijbehorende gegevensblokken kunnen over de schijf verspreid liggen. Het bestandssysteem heeft voor elk logisch bestandsblok een koppeling naar de fysieke locatie nodig.

Volg directe en indirecte pointers

Een directe pointer in een inode duidt één gegevensblok aan. Bij blokken van 4 KiB ligt bytepositie 10.000 in logisch blok 2, omdat twee volledige blokken 8.192 bytes gebruiken. De positie binnen dat blok is 1.808. Logische blokken beginnen bij 0, dus gebruikt blok 2 de derde directe pointer.

Een indirecte pointer duidt een blok aan dat gegevensblokadressen bevat. Een blok van 4.096 bytes met adressen van 4 bytes bevat 1.024 pointers. Een dubbelindirecte pointer duidt een blok aan waarvan de pointers naar 1.024 indirecte blokken leiden. Driedubbele indirectie voegt nog een niveau toe. Deze index met meerdere niveaus is bewust onevenwichtig: kleine bestanden gebruiken directe pointers zonder extra pointerblokken te lezen, terwijl grote bestanden de kosten van extra niveaus dragen.

Voor een inode met 12 directe pointers en één pointer voor elk indirect niveau:

Dit zijn capaciteiten van deze pointerindeling. Pointerblokken nemen ook opslagruimte in, maar hun bytes zijn geen bestandsinhoud.

Tel pointerblokken voor een bestand

Een bestand van 5 MiB bezet 1.280 gegevensblokken van elk 4 KiB. Wijs de eerste 12 toe aan directe pointers. Wijs de volgende 1.024 toe aan het enkelvoudig indirecte blok. Dan blijven 244 gegevensblokken over.

Die 244 hebben een dubbelindirect wortelblok en één indirect blok daaronder nodig. In totaal heeft het bestand drie pointerblokken nodig: het enkelvoudig indirecte blok, het dubbelindirecte wortelblok en het ene kindblok daarvan. Als je alleen het dubbelindirecte wortelblok telt, mis je het kindblok dat de gegevensadressen daadwerkelijk bevat. Alle 1.024 mogelijke kindblokken tellen verspilt ruimte: alleen het benodigde kindblok wordt toegewezen.

Vergelijk extents en ketens

Een extent legt een eerste schijfblok en een reekslengte vast. Een aaneengesloten reeks van 1.000 blokken kan één extent gebruiken in plaats van 1.000 afzonderlijke pointers. Ext4, XFS en NTFS gebruiken extents. Ext4 kan maximaal vier extents in de inode bevatten en gebruikt voor meer een boom. Fragmentatie splitst reeksen en vergroot het aantal benodigde extentrecords.

Gekoppelde toewijzing volgt een keten van blokken. De bestandstoewijzingstabel (FAT) bewaart de koppelingen naar volgende blokken in een afzonderlijke tabel, die meestal in het geheugen wordt gecachet. Een directoryvermelding identificeert het eerste blok en om een later blok te bereiken moet je de eerdere koppelingen volgen. FAT gebruikt geen Unix-inodes en ondersteunt geen twee harde koppelingen naar één bestand.

Opeenvolgende posities bewijzen nooit dat blokken fysiek aaneengesloten zijn. De allocator kiest locaties en de koppeling legt die keuzes vast.

Eén systeemaanroep kan meerdere schijfbewerkingen vereisen, of geen enkele. Om het werk te volgen, ga je na welke structuren het bestandssysteem moet raadplegen en geef je aan welke daarvan al in de cache staan.

Doorloop een pad voordat je de inhoud leest

In het eenvoudige model zonder cache leest het openen van /docs/plan.txt vijf blokken:

1. De inode van de hoofddirectory, waarvan het nummer bekend is.
2. De gegevens van de hoofddirectory, om docs te vinden.
3. De inode van docs.
4. De directorygegevens van docs, om plan.txt te vinden.
5. De inode van het bestand.

Elke directory past in één blok en geen benodigd blok staat vooraf in het geheugen. Het bestandssysteem controleert de toegangsrechten en maakt een vermelding voor het geopende bestand aan. Door het openen zijn de metadata van het bestand gevonden; de inhoud is nog niet gelezen. In ext2 en ext4 wordt inodenummer 2 voor de hoofddirectory gebruikt.

In een bewust cacheloos leesmodel leest elke blokleesbewerking daarna de inode van het bestand, leest de gegevens en schrijft de toegangstijd van de inode. Twee blokken voegen zes I/O-bewerkingen toe, dus elf inclusief het openen. Sluiten vereist in dit model geen schijf-I/O. Deze aantallen beschrijven de expliciete regels van het model voor opnieuw lezen en tijdstempels; een echte cache verandert ze.

Houd bij het aanmaken rekening met toewijzing

Het aanmaken van /docs/log.txt vereist meer dan een bestaande inode vinden. In hetzelfde eenvoudige model voert het systeem vier leesbewerkingen uit voor de inodes en directorygegevens van de hoofddirectory en docs. Het lezen en schrijven van de inodebitmap voegt twee I/O-bewerkingen toe. Het bijwerken van de gegevens van docs voegt één schrijfbewerking toe. Het lezen en schrijven van de nieuwe inode voegt er twee toe en het bijwerken van de inode van docs één. Totaal: tien.

Elk nieuw toegewezen gegevensblok voegt vijf I/O-bewerkingen toe: lees en schrijf de gegevensbitmap, lees en schrijf de inode van het bestand en schrijf het gegevensblok. Twee blokken geven dus twintig I/O-bewerkingen inclusief het aanmaken. Deze telling gebruikt de eenvoudige gegevensstructuren voordat journaalverkeer of echt cachegedrag wordt meegenomen.

Een overzicht bijhouden helpt: noteer de structuur, of die wordt gelezen of geschreven en waarom. Een gegevensschrijfbewerking heeft ook een toewijzingsregistratie en een pointerwijziging nodig. Een directorywijziging verandert ook de metadata van die directory.

Laat de cache het verloop veranderen

Een cachetreffer gebruikt een blok dat al in het geheugen staat. Linux gebruikt een gezamenlijke paginacache die met virtueel geheugen wordt gedeeld, geen blijvend afzonderlijke bestandscache met een vaste grootte. Bij opnieuw openen kunnen de directory- en inodeblokken van het eerdere doorlopen opnieuw worden gebruikt. Voor het lezen van gecachete inhoud is geen leesbewerking op het apparaat nodig. Het gebruikelijke relatime-beleid van Linux voorkomt ook dat atime bij elke leesbewerking wordt geschreven.

Schrijfbuffering stelt het versturen van gewijzigde blokken naar schijf uit. Twee kort na elkaar aangemaakte bestanden kunnen dezelfde inodebitmap in het geheugen bijwerken, waarna die later één keer wordt geschreven. Het bestandssysteem kan het werk anders ordenen voor een betere doorvoer. Een kort bestaand tijdelijk bestand kan worden aangemaakt en verwijderd voordat de inhoud ooit de opslag bereikt.

Buffering verbetert de prestaties, maar laat een periode waarin gegevens nog niet duurzaam zijn opgeslagen. fsync sluit die periode voor een bestand af door op de benodigde schrijfbewerkingen te wachten. Linux O_DIRECT laat geschikte programma's de paginacache omzeilen wanneer ze hun eigen buffers beheren; een cache omzeilen is op zichzelf niet dezelfde bewerking als synchroniseren naar duurzame opslag.

Een harde schijf kan een lange reeks bytes snel overdragen zodra de kop die heeft bereikt. Kleine verspreide verzoeken verspillen tijd aan zoeken en wachten op rotatie. Het Fast File System verandert de plaatsing zodat gewone bestandsbewerkingen meer van de overdrachtsbandbreedte van de schijf benutten.

Onderzoek de oude Unix-indeling

De vroege Unix-indeling plaatste alle inodes dicht bij het begin en alle bestandsgegevens erna. Het lezen van een bestand kon daardoor een lange zoekbeweging van metadata naar inhoud vereisen. Een vrijelijst verspreidde toewijzingen geleidelijk naarmate bestanden werden aangemaakt en verwijderd. Zelfs een sequentieel bestand kon veel niet-aangrenzende schijftoegangen opleveren.

Kleine blokken van 512 bytes maakten dit erger. Elke positioneringsvertraging leverde slechts een korte overdracht op voordat het volgende verzoek weer een zoekbeweging of rotatie nodig had. Historische metingen wezen uit dat het oude ontwerp soms maar 2% van de schijfbandbreedte haalde. Dat cijfer beschrijft het gemeten vroege ontwerp, geen vaste grens van Unix-interfaces.

Het Fast File System (FFS), begin jaren 1980 ontwikkeld in Berkeley, behield vertrouwde aanroepen zoals open, read en write, terwijl het de indeling en het toewijzingsbeleid veranderde. Grotere blokken, meestal 4 KiB, verhoogden het aantal overgedragen bytes per verzoek. Door metadata en inhoud dicht bij elkaar te houden, werd de afstand tussen verwante verzoeken kleiner.

Bouw groepen met eigen bronnen

Een cilinder is de verzameling sporen op dezelfde straal over de schijfoppervlakken. FFS vormt cilindergroepen uit naast elkaar gelegen cilinders. De inode en gegevens van een bestand kunnen in dezelfde groep staan, waardoor een zoekbeweging van metadata naar gegevens kort blijft.

Elke groep bevat een kopie van het superblok, eigen bitmaps voor inode- en gegevenstoewijzing, een deel van de inodetabel en gegevensblokken. De groep lijkt op een klein bestandssysteem, maar alle groepen horen bij één bestandssysteem. Een kopie van het superblok helpt ook bij herstel als één kopie beschadigd is. Ext4 bewaart kopieën in geselecteerde groepen in plaats van in elke groep.

Moderne schijven verbergen hun fysieke geometrie. Ext2, ext3 en ext4 gebruiken daarom blokgroepen, reeksen opeenvolgende logische blokadressen, om hetzelfde lokaliteitsdoel na te streven zonder van exacte cilinders afhankelijk te zijn.

Volg het aanmaken van een klein bestand

Het aanmaken van /docs/a.txt vereist een vrije inode, een gegevensblok, wijzigingen in toewijzingsbitmaps en een nieuwe directoryvermelding. FFS probeert het bestand in de groep van de bovenliggende directory te plaatsen. De nieuwe inode, bestandsgegevens, bitmaps en directorywijzigingen kunnen dan dicht bij elkaar liggen.

De bewerking vereist nog steeds meerdere afzonderlijke wijzigingen. Groeperen bespaart positioneringstijd; het brengt niet alle metadata en gegevens samen in één blok. Een indeling die rekening houdt met de schijf verlaagt de kosten om die structuren te bereiken zonder de bestandsbewerkingen van het programma te veranderen.

FFS gebruikt namen als aanwijzing voor welke bestanden een programma samen zal gebruiken. Het begrenst ook hoeveel ruimte één groot bestand in een groep kan innemen en weegt zo lokaliteit af tegen ruimte voor toekomstige toewijzingen.

Plaats directory's en bestanden

Een nieuwe directory komt in een groep met relatief weinig directory's en veel vrije inodes. Dit spreidt verschillende directory's en laat tegelijk ruimte voor hun toekomstige bestanden. De inode van een gewoon bestand komt in de groep van de bovenliggende directory en de gegevens komen dicht bij de inode.

Voor /a/b, /a/c en /a/d worden de drie bestanden dicht bij directory /a geplaatst. Een bestand /b/f volgt de eigen bovenliggende directory /b, meestal naar een andere groep. Dit benut lokaliteit in de naamruimte: een compiler die aan één project werkt, opent vaak meerdere bestanden in dezelfde directory. De directoryrelatie voorspelt toegangspatronen; ze garandeert niets voor elk afzonderlijk programma.

Maak een uitzondering voor een groot bestand

Eén groot bestand zou de vrije blokken van de groep kunnen opgebruiken en alle latere naburige bestanden naar elders verdringen. FFS houdt het eerste deel, bereikbaar via 12 directe pointers, in de groep van de inode. Bij blokken van 4 KiB is dat 48 KiB. Latere delen, elk bereikbaar via een indirect blok met 1.024 pointers, beslaan 4 MiB aan gegevens en gaan naar andere weinig gebruikte groepen.

Dit offert enige lokaliteit binnen het grote bestand op om lokaliteit voor de andere bestanden van de directory te behouden. Het grote bestand krijgt tussen delen een positioneringsvertraging, dus moet elk deel groot genoeg zijn om die kosten de moeite waard te maken.

Leid de deelgrootte af

Stel dat positionering T seconden duurt en de overdrachtssnelheid R bytes per seconde is. De overdracht van een deel C duurt C/R seconden. De fractie van de totale tijd die aan overdracht wordt besteed, is:

Oplossen geeft:

Bij 100 MB/s met 10 ms positionering is R maal T gelijk aan 1 MB. Een deel van 1 MB vereist 10 ms overdracht plus 10 ms positionering, wat 50% van de maximale bandbreedte geeft. Voor 90% vermenigvuldig je 1 MB met 0,9/0,1 om 9 MB te krijgen. Voor 99% is de vermenigvuldigingsfactor 99, wat 99 MB geeft. Zet milliseconden om naar seconden voordat je met MB/s vermenigvuldigt. De noemer bevat zowel overdrachts- als positioneringstijd; alleen door de overdrachtstijd delen zou de overhead verbergen.

Overdrachtssnelheden zijn sneller verbeterd dan positioneringsvertragingen, dus zijn grotere delen nodig om dezelfde fractie van het maximum te bereiken naarmate het verschil groter wordt.

Laat kleine bestanden passen en behoud compatibiliteit

FFS gebruikte ook deelblokken van 512 bytes zodat kleine bestanden geen heel blok van 4 KiB verspilden. Groeiende bestanden werden naar volledige blokken gekopieerd; de C-bibliotheek bufferde schrijfbewerkingen in stukken van 4 KiB om herhaald verplaatsen te verminderen. Historische parameterisatie liet rotatietussenruimten tussen opeenvolgende blokken, zodat een opgevraagd volgend blok de kop nog niet was gepasseerd. Moderne spoorbuffers maken die techniek overbodig door intern een spoor op te halen.

Lange namen, symbolische koppelingen en atomaire rename waren extra mogelijkheden van FFS. Voor de snelheidswinst door de indeling zelf hoefden bestaande programma's niet te worden gewijzigd.

Voor een programma lijkt één toevoeging één handeling. Op schijf verandert die meerdere structuren en een crash kan ertoe leiden dat slechts enkele daarvan zijn bijgewerkt. Consistentie na een crash gaat over de vraag hoe die gedeeltelijke resultaten kunnen worden voorkomen of hersteld.

Volg drie onafhankelijke schrijfbewerkingen

Eén blok van 4 KiB aan een bestaand bestand toevoegen verandert:

• Db, het nieuwe gegevensblok met de toegevoegde bytes.
• I, de inode met een grotere grootte en een pointer naar dat blok.
• B, de gegevensbitmap die het blok als toegewezen markeert.

Als alle drie de opslag bereiken, ontstaat de bedoelde consistente wijziging. Als geen ervan de opslag bereikt, blijft de oude consistente toestand bestaan. Het gevaar zit in de zes gedeeltelijke combinaties. Het apparaat kan verzoeken anders ordenen, dus als je ze in een bepaalde volgorde uitgeeft zonder te wachten, bepaalt dat niet de volgorde waarin ze worden voltooid.

Classificeer elke gedeeltelijke uitkomst

Een inconsistentie ontstaat wanneer metadata niet overeenkomen, bijvoorbeeld als een inode een blok claimt waarvan het toewijzingsbit vrij aangeeft. De allocator kan datzelfde blok dan aan een ander bestand geven. Een lek in de opslagruimte reserveert opslag die geen bestand kan bereiken. Ongeldige bestandsinhoud kan moeilijker te detecteren zijn: I en B komen volledig overeen, hoewel Db nooit is aangekomen.

Alleen Db laat geen toegewezen ruimte lekken, omdat de bitmap nog toestaat dat het blok opnieuw wordt gebruikt. Bytes naar een vrije locatie schrijven is niet hetzelfde als die toewijzen. Alleen B laat wel ruimte lekken, omdat de toewijzing behouden is gebleven zonder pointer van een eigenaar.

Scheid structuur van betekenis

Een controleprogramma kan pointers met bitmaps vergelijken. Het kan doorgaans niet vaststellen of aannemelijke bytes de bytes zijn die een programma wilde opslaan. De uitkomst met I en B laat deze grens zien: een structureel geldig bestand kan onjuiste inhoud hebben.

De gewenste overgang is atomair voor de hele wijziging: herstel naar de volledige oude toestand of de volledige nieuwe toestand. Een eenvoudig opslagmodel biedt alleen atomaire schrijfbewerkingen voor één sector, traditioneel 512 bytes. Meerdere bestandssysteemblokken overschrijden die eenheid, dus moet het bestandssysteem een sterker protocol opbouwen. De garanties voor atomaire schrijfbewerkingen van echte apparaten hangen af van het apparaat en de interface; het journaalprotocol moet zijn vastleggingsrecord binnen de ondersteunde atomaire eenheid laten passen.

Buffering vergroot het aantal wijzigingen dat verloren kan gaan, maar is niet de hoofdoorzaak. Zelfs als je elke schrijfbewerking onmiddellijk uitgeeft, kan een crash tussen afzonderlijke voltooiingen optreden. Een bestand aanmaken, hernoemen en verwijderen verandert ook meerdere structuren. Om de mogelijke fouttoestanden te begrijpen, begin je met dezelfde oefening: bepaal elk gewijzigd blok en vraag wat er gebeurt als slechts een deel behouden blijft.

Een bestandssysteemcontrole herstelt relaties tussen opgeslagen structuren nadat schade is ontstaan. De kracht is een breed overzicht van metadata; de zwakke punten zijn de kosten van het doorzoeken en het gebrek aan kennis over de bedoelde bestandsinhoud.

Reconstrueer het toewijzingsoverzicht

fsck, de bestandssysteemcontrole, onderzoekt een onzuiver afgesloten bestandssysteem voordat het normaal wordt aangekoppeld. Het controleert of de grootte en aantallen in het superblok redelijk zijn en kan een reservesuperblok gebruiken als de hoofdkopie beschadigd is.

Daarna doorzoekt het inodes en indirecte blokken om te bepalen naar welke gegevensblokken bestanden daadwerkelijk verwijzen. Uit die informatie over eigenaarschap bouwt het de toewijzingsbitmaps opnieuw op. Als een verder geldige inode naar blok 74 verwijst terwijl de bitmap 74 vrij noemt, moet de bitmap worden gewijzigd naar toegewezen. Als het systeem alleen op de bitmap zou vertrouwen, zou een latere toewijzing de bestandsgegevens kunnen overschrijven.

De omgekeerde afwijking is een bitmapbit dat als toegewezen is gemarkeerd zonder pointer vanuit een inode die eigenaar is. Door de bitmap te reconstrueren kan die ruimte weer beschikbaar komen. Herstel kiest een consistente relatie; het kan geen willekeurige ontbrekende toepassingsbytes reconstrueren.

Controleer objecten, namen en koppelingen

Elke toegewezen inode heeft een geldig type nodig, zoals gewoon bestand, directory of symbolische koppeling. Een inode die niet kan worden hersteld, wordt gewist en de toewijzingsgegevens worden aangepast.

Door vanaf de hoofddirectory te lopen kan fsck directoryverwijzingen naar elke inode tellen. Het vergelijkt deze waargenomen verwijzingen met de geregistreerde aantallen harde koppelingen en corrigeert fouten. Een toegewezen inode die geen directory bereikt, kan naar lost+found worden verplaatst. Zo krijgt herstelde inhoud een bereikbare naam zonder dat het oorspronkelijke pad bekend is.

Andere controles omvatten:

• Dubbel eigenaarschap: twee inodes claimen één gegevensblok. Een herstelactie kan één inode wissen of elk bestand een afzonderlijke kopie geven.
• Ongeldige adressen: pointers buiten het geldige bereik van het bestandssysteem moeten worden gewist.
• Directorystructuur: . en .. moeten geldig zijn en in de eenvoudige directoryindeling de eerste vermeldingen bezetten, vermeldingen moeten naar toegewezen inodes verwijzen en directory's mogen niet meerdere bovenliggende directory's hebben.

Deze controles beïnvloeden elkaar. Een ongeldige inode wissen verandert ook welke blokken toegewezen moeten zijn en welke directoryvermeldingen geldig blijven. Herstel vereist daarom een samenhangend beeld van de metadata, niet alleen een lijst verdachte afzonderlijke bits.

Begrijp wat een foutloze uitkomst vaststelt

Stel dat de inode en bitmap van een toevoeging de schijf hebben bereikt, maar de gegevens niet. De pointer ligt binnen het bereik, het toewijzingsbit is gezet en de koppelingsstructuur is geldig. fsck heeft geen afwijking in metadata om te herstellen. Het bestand kan de controle doorstaan terwijl het nieuw toegevoegde gebied oude bytes bevat.

De uitvoeringstijd hangt ook vooral af van de grootte van het bestandssysteem, niet van de hoeveelheid die vóór een crash is gewijzigd. Een crash tijdens één wijziging van drie blokken kan nog steeds vereisen dat alle metadata worden doorzocht. Op een groot bestandssysteem kan dit minuten tot uren duren, waarbij normale toegang tijdens de controle niet beschikbaar is.

Journaalregistratie vermindert het gebruikelijke herstelwerk na een crash door recente wijzigingen te registreren. Ze maakt een controleprogramma niet overbodig: softwarefouten of falende hardware kunnen structuren beschadigen op een manier die opnieuw toepassen uit het journaal niet kan herstellen. fsck blijft voor die gevallen een herstelhulpmiddel.

Een journaal registreert een wijziging voordat het bestandssysteem de gewone locaties overschrijft. Na een crash vertelt die registratie het herstelproces welke volledige wijzigingen opnieuw kunnen worden uitgevoerd. Dit is voorafgaande logregistratie. Ext3, ext4, XFS en NTFS gebruiken journaalregistratie, hoewel hun exacte logboekformaten verschillen.

Beschrijf een wijziging als een transactie

Voor een toevoeging registreert gegevensregistratie in een journaal kopieën van de nieuwe inode I, bitmap B en het gegevensblok Db. Een transactiebeginrecord, TxB, bevat een ID en de definitieve bestemmingen van de blokken. Een transactie-eindrecord, TxE, bevat de bijbehorende ID en markeert de vastlegging.

Volledige vervangende blokinhoud registreren is fysieke logregistratie. In plaats daarvan een bewerkingsbeschrijving registreren is logische logregistratie. Fysiek opnieuw uitvoeren heeft een nuttige eigenschap: dezelfde inhoud opnieuw naar hetzelfde adres schrijven heeft hetzelfde effect. Herstel kan daarom het overbrengen naar de definitieve locatie herhalen als dat vóór de crash gedeeltelijk was voltooid.

Leg vast na de inhoud

Het basisprotocol heeft vier fasen:

1. Schrijven naar het journaal: schrijf TxB en I, B en Db naar het journaal en wacht tot ze duurzaam zijn opgeslagen.
2. Vastleggen: schrijf TxE en wacht. De transactie is nu vastgelegd.
3. Overbrengen: kopieer I, B en Db vanuit het journaal naar hun definitieve locaties.
4. Vrijgeven: geef de journaalruimte van die transactie vrij voor later hergebruik.

TxE mag niet duurzaam worden opgeslagen vóór de inhoud van de transactie. Als alle vijf blokken zonder volgordegarantie zouden worden uitgegeven, zou een apparaat TxB en TxE kunnen voltooien terwijl Db ongeschreven blijft. Herstel zou een onvolledige transactie voor een geldige aanzien. In het basismodel past TxE binnen één atomaire sectorschrijfbewerking, zodat het als volledig vastleggingsrecord aanwezig of afwezig is.

Schrijfcaches van apparaten moeten de duurzaamheidsgrens ook respecteren. Cacheleegmaak- of geforceerde schrijfbewerkingen voorkomen dat een vluchtige apparaatcache het protocol laat geloven dat de inhoud veilig is terwijl stroomuitval die nog kan wissen.

Herstel van twee crashmomenten

Een crash na de inhoud maar vóór TxE laat een niet-vastgelegde transactie achter. Herstel negeert die en behoudt de oude bestandstoestand.

Een crash na TxE maar tijdens het overbrengen naar de definitieve locaties laat een vastgelegde transactie achter. Herstel schrijft alle blokinhoud op volgorde naar de definitieve locaties. Sommige schrijfbewerkingen herhalen mogelijk al uitgevoerd werk, wat voor deze blokinhoud geen kwaad kan. Dit is herstel door opnieuw uitvoeren. Journaalruimte kan pas opnieuw worden gebruikt als de vastgelegde blokinhoud de definitieve locaties heeft bereikt.

Het journaal is een circulair logboek. Het superblok houdt het actieve bereik bij, zodat vrijgekomen ruimte opnieuw kan worden gebruikt. Door meerdere wijzigingen in één transactie te bundelen kan één gedeeld directoryblok of één bitmap één keer worden geregistreerd. Het standaardinterval voor vastlegging in ext4 is 5 seconden, dus volgt vastlegging niet automatisch onmiddellijk op elke schrijfbewerking van een toepassing.

Scheid controlesommen van duurzaamheid

Een transactiecontrolesom kan ontbrekende of gedeeltelijk geschreven inhoudsblokken onthullen, ook wanneer een vastleggingsrecord aanwezig is. Een protocol op basis van controlesommen kan journaalschrijfbewerkingen samen uitgeven en alleen transacties accepteren waarvan de controle slaagt. Controlesommen detecteren onvolledige records; cacheleegmaakbewerkingen bepalen of bevestigde bytes werkelijk behouden blijven.

Een gebufferde, niet-vastgelegde schrijfbewerking van een toepassing kan nog steeds verdwijnen. Een programma dat duurzame voltooiing vereist, gebruikt fsync en controleert of dat lukt.

Gegevensregistratie in een journaal schrijft bestandsinhoud naar het journaal en daarna naar de definitieve locaties. Alleen metadata in het journaal registreren vermindert dat verkeer, maar de volgorde van gegevens en metadata bepaalt nog steeds wat na herstel zichtbaar kan worden.

Zorg dat gegevens vóór vastgelegde pointers komen

Bij geordende metadataregistratie in een journaal gaat Db rechtstreeks naar de definitieve locatie. TxB, I en B gaan naar het journaal. Deze twee groepen schrijfbewerkingen kunnen parallel lopen, maar beide moeten voltooid zijn voordat TxE de metadata vastlegt. Na vastlegging kunnen I en B naar de definitieve locaties worden overgebracht en kan de journaalruimte worden vrijgegeven.

De afhankelijkheid is de kern: het blok dat een pointer aanduidt, moet gereed zijn voordat die pointer kan worden hersteld. Als I eerst wordt vastgelegd, kan herstel een geldige pointer installeren naar bytes die zijn achtergelaten door een eerdere gebruiker van het blok. De metadata zouden overeenkomen zonder dat de bedoelde gegevens aanwezig zijn.

De geordende modus is de standaard. Alleen metadata in een journaal registreren betekent niet dat de geordende modus wordt gebruikt: de modus met ongeordend terugschrijven kan structureel correcte bestanden met verouderde inhoud herstellen. De modus met gegevensregistratie in een journaal laat het volledige protocol zien, maar kost een tweede schrijfbewerking voor de bestandsgegevens.

Voorkom dat opnieuw toepassen een hergebruikt blok beschadigt

Directory-inhoud telt als metadata. Stel dat een directoryblok op adres 1000 wordt geregistreerd, waarna de directory wordt verwijderd en hetzelfde adres gewone bestandsgegevens gaat bevatten. Die nieuwe gebruikersgegevens worden in de modus met alleen metadataregistratie niet geregistreerd. Als de oude directory-inhoud na een crash opnieuw wordt toegepast, overschrijft die de bytes van het nieuwe bestand.

Een vastgelegd intrekkingsrecord vertelt het herstelproces geregistreerde kopieën van dat blok uit transacties tot en met de intrekkende transactie over te slaan. Het verbiedt niet elk toekomstig gebruik van het adres. Als een latere transactie dat blok opnieuw registreert, kan de latere blokinhoud nog steeds opnieuw worden toegepast. Deze tijdsgrens onderscheidt intrekking van het permanent als onbruikbaar markeren van een blok.

Vergelijk alternatieven

Soft updates dwingen afhankelijkheden tussen gewone schrijfbewerkingen af zonder journaal. Door geïnitialiseerde gegevens vóór een pointer te schrijven, voorkom je bereikbare ongeldige inhoud, hoewel onderbroken bewerkingen ruimte kunnen laten lekken die een latere achtergrondcontrole weer beschikbaar maakt. FFS van FreeBSD gebruikt deze aanpak. Alle afhankelijkheden bijhouden maakt implementatie moeilijk.

Kopiëren bij schrijven schrijft gewijzigde blokken naar ongebruikte locaties en gebruikt een atomaire omschakeling van de wortelpointer om de nieuwe boom beschikbaar te maken. De oude boom blijft tot de omschakeling beschikbaar. ZFS, Btrfs en WAFL gebruiken verwante ontwerpen; oude blokken behouden maakt ook momentopnamen mogelijk.

Onderzoeksontwerpen op basis van terugverwijzingen registreren eigenaarschap van gegevens terug naar inodes, zodat onvolledige wijzigingen detecteerbare afwijkingen achterlaten. Optimistische consistentie na een crash vermindert het wachten en gebruikt controlesommen en andere controles om onvoltooid werk te detecteren. Elke aanpak weegt schrijfverkeer, herstelgaranties en implementatiecomplexiteit tegen elkaar af. Geordende metadataregistratie in een journaal houdt herstel kort en schrijft gewone bestandsgegevens één keer.

Een loggestructureerd bestandssysteem zet verspreide kleine wijzigingen om in grote sequentiële schrijfbewerkingen. Dit helpt bij een schijf met een hoge overdrachtssnelheid waarvan zoek- en rotatievertragingen kostbaar blijven.

Verzamel wijzigingen in een segment

LFS van Berkeley, ontwikkeld door Rosenblum en Ousterhout en gepubliceerd in 1991, ging uit van veranderende werklasten. Grotere geheugens handelden meer leesbewerkingen af vanuit de cache, waardoor schrijfbewerkingen een groter aandeel van het schijfverkeer vormden. De sequentiële bandbreedte groeide sneller dan de positioneringssnelheid. FFS had voor het aanmaken van een klein bestand nog steeds meerdere korte schrijfopdrachten voor metadata en gegevens nodig, en kleine schrijfbewerkingen werkten ook slecht met RAID met pariteit.

LFS buffert gewijzigde gegevens, inodes en vertaaltabelinformatie samen in het geheugen. Het schrijft ze als één groot segment naar een ongebruikt schijfgebied. Een blok bijwerken maakt een nieuwe versie op een nieuw adres; de vorige versie blijft fysiek aanwezig totdat het opruimen het segment vrijmaakt.

Segmenten amortiseren positioneringskosten net als grote delen bij FFS. Bij snelheid R, positioneringstijd T en gewenste overdrachtstijdfractie F is de gebufferde grootte:

Bij 200 MB/s en 5 ms vereist 95% een grootte van 19 MB. De overdracht duurt 95 ms, de positionering 5 ms en de effectieve snelheid is 19 MB per 0,1 s = 190 MB/s. Een hoge doelfractie kan een segment vereisen dat groter is dan de gebruikelijke honderden kilobytes tot enkele megabytes. De vereiste grootte volgt uit het apparaat en het doel, niet uit het woord “segment”.

Zoek een inode die blijft verplaatsen

De formule met een vaste inodetabel werkt niet meer: elke inodewijziging wordt op een nieuw adres geschreven. LFS voegt een inodevertaaltabel, of imap, toe die elk inodenummer aan het nieuwste schijfadres koppelt. Bijgewerkte imap-delen worden in het logboek geschreven naast de inodes die ze beschrijven.

Een vast checkpointgebied (CR) legt vast waar de nieuwste imap-delen staan. Het wordt periodiek bijgewerkt, bijvoorbeeld om de 30 seconden, zodat de incidentele schrijfbewerking op een vaste locatie het verkeer niet overheerst.

De opzoekketen is:

1. Lees bij het aankoppelen de CR om de huidige imap-delen te vinden.
2. Laad de imap in het geheugen.
3. Zoek het gevraagde inodenummer op in de imap.
4. Lees die nieuwste inode en volg de gegevenspointers.

Zodra de imap in de cache staat, gebruiken gewone bestandsleesbewerkingen vrijwel hetzelfde pad van inode naar gegevens als in FFS. De extra vertaalslag maakt verplaatsing betaalbaar zonder de stabiele identiteit van het bestand te veranderen.

Houd directoryvermeldingen stabiel

Een directory bewaart namen en inodenummers. Als /docs/report.txt wordt gewijzigd, verplaatst de inode maar behoudt die het nummer. De imap verandert; de directoryvermelding hoeft niet alleen door die verplaatsing te veranderen.

Zonder deze indirecte verwijzing zou een directory met fysieke inodeadressen telkens opnieuw moeten worden geschreven wanneer een onderliggende inode verplaatst. De eigen inode zou dan verplaatsen, wat een wijziging in de bovenliggende directory afdwingt, enzovoort tot aan de hoofddirectory. De imap doorbreekt dit recursieve wijzigingsprobleem.

LFS maakt schrijfbewerkingen sequentieel, niet alle leesbewerkingen. De ongewijzigde blokken van een bestand kunnen in oudere segmenten blijven terwijl latere versies van andere blokken naar elders verplaatsen. Voor het lezen van dat bestand kunnen nog steeds zoekbewegingen tussen segmenten nodig zijn; grote geheugencaches maken deel uit van de motivatie voor het ontwerp.

Door nieuwe versies naar ongebruikte locaties te schrijven blijven oude bytes fysiek aanwezig. LFS moet oude onbereikbare versies onderscheiden van nog gebruikte blokken, grote vrije gebieden terugwinnen en na een crash een bruikbare koppeling herstellen.

Ruim hele segmenten op

De segmentopruimer leest gedeeltelijk bezette segmenten, kopieert hun nog gebruikte blokken naar een kleiner aantal nieuwe segmenten en geeft de oude segmenten vrij. Als vier even grote segmenten elk voor een kwart nog gebruikte gegevens bevatten, vullen die gegevens samen één nieuw segment. Door de vier oude segmenten na het kopiëren vrij te geven win je drie segmenten aan bruikbare capaciteit.

Door hele segmenten op te ruimen blijven grote aaneengesloten gebieden behouden voor toekomstige sequentiële schrijfbewerkingen. Kopiëren heeft kosten: nog gebruikte blokken worden opnieuw gelezen en geschreven, ook als geen toepassing ze heeft gewijzigd. Bij een bijna volle schijf met voornamelijk nog gebruikte segmenten kan veel kopiëren nodig zijn om weinig vrije ruimte terug te winnen.

Bepaal of een blok nog wordt gebruikt

Een segmentoverzicht identificeert voor elk blok de inode van de eigenaar en de positie van het logische bestandsblok. Om een blok op adres A te testen, gebruik je de imap om de nieuwste inode van die eigenaar te vinden. Volg de pointer voor het vastgelegde logische blok. Als de pointer nog gelijk is aan A, is dit de gebruikte versie. Als die naar elders verwijst, is A verouderd.

Een overzicht koppelt bijvoorbeeld adres 600 aan inode 14, logisch blok 2. De huidige inode 14 laat logisch blok 2 naar adres 920 wijzen. Blok 600 is ongebruikt, ook als de bytes op geldige gegevens lijken. Of een blok nog wordt gebruikt, hangt af van de huidige bereikbaarheid, niet van hoe recent het is geschreven of of de inhoud nuttig lijkt.

Versienummers versnellen het uitsluiten. Een bestand verwijderen of tot nul inkorten verhoogt het versienummer van dat bestand in de imap. Een segmentblok met een oudere versie kan als ongebruikt worden aangemerkt zonder de inode te lezen.

Het opruimbeleid houdt ook rekening met verwachte wijzigingen. Hete segmenten bevatten vaak overschreven blokken; door te wachten kunnen meer van hun blokken ongebruikt raken zonder te kopiëren. Koude segmenten veranderen weinig, dus ruimt het oorspronkelijke LFS-beleid ze eerder op. Het beleid moet de gebruikte fractie, de leeftijd en de beschikbare ruimte tegen elkaar afwegen; alleen de temperatuur van een segment meet niet de directe kopieerkosten.

Herstel de koppeling en recent werk

LFS bewaart twee checkpointgebieden aan tegenoverliggende uiteinden van de schijf en werkt ze afwisselend bij. Elke wijziging schrijft een header met een tijdstempel, de inhoud en een afsluitend overeenkomstig tijdstempel. Herstel kiest het nieuwste gebied waarvan begin en einde overeenkomen. Een onderbroken nieuwere wijziging verdringt een ouder volledig checkpoint niet.

Het checkpoint bevat mogelijk niet de recentst voltooide segmenten. Daarom voert herstel voorwaarts herstel uit vanaf het daarin vastgelegde logboekeinde: het zoekt geldige latere wijzigingen en past die toe om de huidige koppeling opnieuw op te bouwen. Gegevens die nooit een geldige herstelbare wijziging vormden, kunnen na stroomuitval niet uit het geheugen worden teruggehaald.

Verwante systemen met kopiëren bij schrijven bewaren oude blokken om momentopnamen te ondersteunen; ZFS, Btrfs en WAFL delen dat algemene idee. SSD-controllers gebruiken vaak loggestructureerde flashvertaallagen, terwijl F2FS loggestructureerde ideeën op bestandssysteemniveau toepast voor flashopslag. Elk heeft nog steeds een manier nodig om ruimte van verouderde versies vrij te maken.

Een gedistribueerd bestandssysteem bewaart bestanden op een server terwijl programma's op clientmachines vertrouwde bestandsaanroepen gebruiken. De client vertaalt die aanroepen naar netwerkverzoeken. Vertragingen en storingen roepen een vraag op die lokale aanroepen meestal verbergen: wat moet een client doen als die niet kan bepalen of een verzoek is voltooid?

Houd de toestand van geopende bestanden op de client

Het Network File System (NFS) van Sun begon in de jaren 1980. NFSv2 maakte de server toestandsloos voor geopende bestanden. De server slaat bestanden op, maar onthoudt niet de descriptoren of huidige bestandsposities van elke client. Elk verzoek bevat voldoende informatie om zonder een eerder openingsverzoek te worden uitgevoerd.

Een bestandshandle identificeert het servervolume, het inodenummer en de inodegeneratie. De generatie verandert wanneer een inodenummer opnieuw wordt gebruikt. Zo voorkomt die dat een oude handle per ongeluk een ander bestand op die opnieuw gebruikte plaats aanduidt.

Om /home/ana/notes.txt te openen begint de client met een handle voor de hoofddirectory en stuurt die LOOKUP voor home, ana en notes.txt. De client bewaart de resulterende handle in de eigen toestand voor geopende bestanden. De eerste 4 KiB lezen wordt een READ-verzoek met die handle, positie 0 en aantal 4096. De lokale descriptor sluiten vereist geen NFSv2-CLOSE-verzoek, omdat de server geen vermelding voor een geopend bestand heeft om vrij te geven.

Herhaal zonder een effect te herhalen

Als geen antwoord aankomt, kan de client geen onderscheid maken tussen een verloren verzoek, een onbereikbare server of een verloren antwoord. Na een time-out verstuurt de client het verzoek opnieuw.

Een bewerking is idempotent wanneer herhalen hetzelfde effect heeft als één keer uitvoeren. READ, LOOKUP en GETATTR wijzigen de opgeslagen inhoud niet. Een WRITE met een expliciete positie herhaalt in dit model ook veilig dezelfde bytes op dezelfde locatie. Een verzoek herhalen dat zegt “voeg deze bytes aan het huidige einde toe” zou daarentegen een tweede kopie toevoegen; de positie in een NFS-WRITE voorkomt die dubbelzinnigheid.

Sommige verzoeken vereisen extra zorg. Een geslaagde MKDIR opnieuw proberen nadat het antwoord verloren is gegaan, kan “bestaat al” teruggeven. De directory is aanwezig, maar het herhaalde antwoord verschilt van de oorspronkelijke bevestiging. Toestandsloos herstel maakt niet van elke bewerking een eenvoudig herhaalbaar verzoek.

Maak bevestigingen betrouwbaar

NFSv2 moet een WRITE duurzaam opslaan voordat het succes bevestigt. Anders zou de server een blok kunnen bevestigen, het tijdens een crash uit het geheugen verliezen en daarna latere blokken accepteren. De client zou denken dat alle schrijfbewerkingen zijn geslaagd terwijl in het bestand een wijziging in het midden ontbreekt.

Duurzame antwoorden voorkomen die fout ten koste van prestaties. NFSv3 voegde instabiele schrijfbewerkingen toe, gevolgd door COMMIT, waardoor meerdere schrijfbewerkingen samen duurzaam kunnen worden gemaakt. De client moet een instabiele bevestiging onderscheiden van duurzame voltooiing.

Onderscheid versies van het protocol

Een protocol met toestand heeft mechanismen nodig om de toestand van geopende bestanden en vergrendelingen na een serverherstart te herstellen en toestand van gecrashte clients op te ruimen. NFSv4 accepteert die complexiteit bewust: het heeft OPEN, CLOSE, vergrendelingen en in tijd beperkte tijdelijke gebruiksrechten die clients verlengen. De Linux-client probeert normaal eerst versie 4.2 en valt zo nodig terug. NFSv2 toestandsloos noemen beschrijft dus niet elke NFS-versie.

Caching op clients bespaart netwerkverkeer, maar creëert meerdere kopieën van gedeelde bestanden. De consistentieregel bepaalt wanneer een andere machine moet stoppen met het gebruiken van een oude kopie en de wijzigingen van de schrijver moet ophalen.

Controleer NFS-caches bij overdracht tussen gebruikers

Bij consistentie tussen sluiten en opnieuw openen van NFS stuurt het sluiten van een gewijzigd bestand gebufferde schrijfbewerkingen naar de server. Een latere opening op een andere client controleert of de kopie actueel is en ziet die wijzigingen. GETATTR of een vergelijkbare controle vergelijkt serverattributen met gecachete attributen en verwijdert verouderde gecachete gegevens wanneer een wijziging wordt gedetecteerd.

Bij elke toegang controleren zou de server belasten. Linux bewaart attributen van gewone bestanden standaard tussen 3 en 60 seconden in de cache. Een proces dat een bestand openhoudt, kan daardoor tussen controles verouderde gecachete gegevens lezen. Openen is een sterker overdrachtsmoment dan een willekeurige leesbewerking via een al open descriptor. Consistentie tussen sluiten en opnieuw openen belooft niet dat elke afzonderlijke schrijfbewerking onmiddellijk zichtbaar is.

Hergebruik volledige bestanden met AFS-wijzigingsmeldingsbeloften

Het Andrew File System (AFS) is in de jaren 1980 bij Carnegie Mellon ontworpen om veel clients per server te ondersteunen. Als er geen geldige lokale kopie bestaat, haalt openen het hele bestand naar de lokale schijf. Lees- en schrijfbewerkingen gebruiken daarna die kopie en het sluiten van een gewijzigd bestand stuurt de hele nieuwe versie naar de server. Een geldige gecachete kopie kan opnieuw worden geopend zonder die opnieuw te downloaden.

AFSv1 controleerde bij elke opening de geldigheid en liet het doorlopen van paden aan de server over. AFSv2 verschoof het doorlopen naar clients, die directory's cachen, en introduceerde wijzigingsmeldingsbeloften. De server belooft een client te melden wanneer een gecachet object verandert. Tot die belofte wordt ingetrokken, gebruikt de client de kopie opnieuw zonder herhaalde controles. De bestandsidentificatie omvat een volume, een bestandsidentificatie en een uniekmaker.

Volg twee overlappende sessies

Stel dat clients A en B beide een bestand openen. A wijzigt de lokale kopie en sluit het bestand, waardoor de nieuwe versie naar de server gaat. De server trekt de wijzigingsmeldingsbeloften van andere clients in. Een latere opening op B haalt de nieuwe versie op, maar de al open sessie van B behoudt de bestaande kopie tot sluiten en opnieuw openen.

Als beide machines hun kopieën wijzigen, vervangt de machine die het laatst sluit het hele bestand op de server. Blokken uit de twee kopieën worden niet samengevoegd. Ook bij twee wijzigingen op verschillende posities kunnen de wijzigingen van één client verloren gaan, omdat de laatst sluitende client wint één volledige versie kiest. Processen op één clientmachine zien elkaars schrijfbewerkingen onmiddellijk.

Wijzigingsmeldingsbeloften zijn toestand op de server. Na een herstart van een client zijn gecachete bestanden verdacht omdat meldingen gemist kunnen zijn. Na een herstart van de server moeten clients de verloren beloften detecteren, via hartslagberichten of een melding van de server, en opnieuw controleren.

Stem caching af op de werklast

AFS bood ook een globale naamruimte, toegangscontrolelijsten en door beheerders beheerde volumes. AFSv2 verhoogde historisch de schaal van een server tot ongeveer 50 clients, tegenover ongeveer 20 voor AFSv1. Geen van beide cacheregels vervangt expliciete coördinatie, zoals bestandsvergrendeling, wanneer programma's veilige gedeelde wijzigingen nodig hebben.