page header photo

februari 2016 Archieven

Sparse files


Geplaatst door hjt op 2016-02-01 19:17:27 | Permanente link | Categorie: Systeembeheer | Reacties: 0

Een weinig bekend fenomeen van UNIX- (en dus Linux-) filesystemen is de z.g. sparse file. Toch kom je de term tegen in de manpages van zeer bekende commando's zoals tar, rsync en zelfs (de Linux-versie van) cp.

Voor de uitleg hiervan is een stukje technische achtergrond nodig.

Als een applicatie een file opent, dan weet de kernel hoeveel bytes op dat moment al in die file zitten: de achtergrens is bekend. Verder houdt de kernel bij op welke plek (byte-positie) in de file die applicatie bezig is. Dat laatste heet de 'seek-pointer'. Applicaties kunnen allerlei manipulaties met die seek-pointer uithalen, maar het eenvoudigste model is dat één seekpointer functioneert per applicatie per file. Als meerdere applicaties tegelijk in dezelfde file bezig zijn dan hebben ze dus in deze situatie elk hun eigen seekpointer (een programmeur kan ook een constructie met een "shared seekpointer" opzetten maar dat komt veel minder vaak voor). Als een applicatie een read- of een write-opdracht op de file loslaat, dan vindt die operatie plaats waar op dat moment de seekpointer (van die applicatie) in die file wijst, en die seekpointer schuift mee. De volgende read of write vindt dus vanzelf plaats waar de vorige ophield.

Maar stel bijvoorbeeld dat je op een stukje uit de file een read-modify-write wilt doen. Dan zou je eerst vanaf het begin moeten lezen totdat de seek-pointer, al schuivend, de gewenste plek bereikt. Vervolgens lees je de te wijzigen bytes, en weer schuift de seek-pointer mee. Als je de gewijzigde bytes vervolgens weer terug wilt schrijven waar ze vandaan kwamen, dan staat de seekpointer dus net voorbij die plek, en dat is niet de bedoeling.

Daarom kan een applicatie met die pointer ook "seeken". Hij kan zeggen: "zet de pointer nu voor mij op positie zus-en-zo, want dadelijk ga ik schrijven (of lezen) en dat wil ik precies op die positie laten plaatsvinden. De "seek"-operatie doet zelf geen byte-transport, maar treft een voorbereiding voor de eerstkomende read of write. Dus: je hebt in files in eerste instantie een sequentieel access-gedrag omdat de seekpointer automatisch meeschuift met reads en writes, maar met deze "seek" krijg je ook een "random access" mogelijkheid.

Een "sparse" stuk in een file ontstaat als een applicatie een "seek" doet naar een plek die een stuk voorbij het einde (op dat moment) van de file ligt. Doet hij daarna een write, dan ontstaat een soort "gat" tussen dat oude einde van de file, en de nieuw-toegevoegde bytes. Als een applicatie op een later moment al lezend in dat gat terecht komt, dan leest hij nul-bytes. Zou hij echter schrijven, dan wordt op dat moment een stukje gat omgevormd tot "echt" gealloceerde diskruimte.

Als je "onder de motorkap" bekijkt hoe een file op een diskoppervlak is gelegd, dan zie je bijna nooit een aaneenliggende reeks disksectoren. Meestal is een file opgedeeld in porties sectoren, en die porties liggen verspreid over het diskoppervlak. De gebruikelijke vakterm hiervoor is "fragmentatie". De portiegrootte wordt gekozen bij het inrichten van het filesysteem (de "block size" parameter bij commando mkfs). In de boekhouding (i-node) van elke file zit een lijst die, op volgorde, aangeeft waar elke portie ligt. Maar in die lijst kan als plaatsaanduiding de waarde '0' voorkomen. Dat betekent dat die betreffende portie nooit "echt" op de disk is geschreven, maar is ontstaan als "gat" door zo'n 'seek' truc. Als een applicatie bytes wil lezen uit dat stuk van de file, dan ziet de kernel die locatiewaarde '0' staan, schudt ter plekke een portie nul-bytes uit zijn mouw, en geeft die aan de lezende applicatie. De applicatie heeft geen enkele mogelijkheid om te zien dat die nul-bytes niet echt van het diskoppervlak komen.

De seek-parameter van het dd-commando geeft een mooie demonstratie:

$  dd if=/dev/urandom of=demofile bs=1000 seek=1000000 count=1
$  ls -l demofile
-rw-rw-r-- 1 hjt all 1000001000 Jan  8 16:46 demofile

Een tipje van de sluier wordt opgelicht met de -s flag van ls:

$  ls -sk demofile
20 demofile

Wow! Deze file is ongeveer 'n Gigabyte groot, en kost 20K ruimte op disk! Je kunt zelfs nog kleiner tegenkomen, want het is afhankelijk van de block size van de betreffende partitie. Vroeger demonstreerde ik zo'n Gigabyte-file wel 'ns op een floppy. De ls -l maakte daar werkelijk indruk.

Hierbij moet je nog weten dat ls -l de databytes van een file telt, inclusief gat(en). Commando ls -s telt gealloceerde diskblokken, maar daarbij tellen de z.g. indirect-blokken mee. Indirect-blokken zijn extensies van de i-node die nodig zijn als de lijst van locaties niet meer in de i-node zelf past.

Voor systeembeheerders is het nuttig om op z'n minst te weten dat het sparse fenomeen bestaat. Als je een backup maakt van een bijna volle partitie dan leest de backup-software ook de nul-bytes uit de gaten mee. Moet de backup later worden teruggeschreven naar een even grote partitie, dan worden die nul-bytes echt geschreven, en kosten dus opeens "echt" disk-oppervlak. Als je pech hebt dan past de backup dus niet meer op de partitie waar hij oorspronkelijk wel vandaan kwam.

Het is daarom altijd verstandig om wat marge te houden in de vullingsgraad van je diskpartities. Het is moeilijk om te achterhalen hoeveel van die sparse gaten op een bepaald moment aanwezig zijn. Standaard UNIX-tools maken ze niet veel, tenzij je er speciaal om vraagt (bijv. bij tar met de -S flag). Maar soms tref je een niet-standaard applicatie die er dol op is om ze te maken.

Wie bedenkt nou zo iets...

De oorsprong ligt in de schaak-hobby van Ken Thompson. Hij was, samen met Dennis Ritchie, de ontwerper van UNIX, maar met zijn Belle-computer ook ooit wereldkampioen computerschaak. Thompson had een bekende encyclopedie van schaakopeningen overgetypt (later is hij zich op eindspelen gaan concentreren), en omgevormd tot een computer database. Daarbij had hij een algoritme bedacht dat aan elke stelling op een schaakbord een uniek nummer toekent. Dat nummer moest de zoek-key voor de database worden. Elk record in zijn database had, in bytes gemeten, dezelfde lengte. Een bloedsnelle manier om bij een gegeven stelling het bijbehorende databaserecord te vinden was dus: bouw de database als een file die bestaat uit alle records gewoon achter elkaar geplaatst, reken bij een gegeven stelling het keygetal uit, reken dan keygetal × recordsize uit, en doe in de file een 'seek' naar die bytepositie.

Maar dit speelde in de tijd dat een 70Mb disk nog zo groot was als een wasmachine, en een 3-fasen stroomaansluiting nodig had. Dus zo'n file als hierboven beschreven zou onmogelijk worden qua diskruimte, omdat het schaakspel zo vreselijk veel mogelijke stellingen kent, dus even zoveel records in de database zou kosten. Maar lang niet alle stellingen kwamen in die openingen-encyclopedie voor. Dus de database was "sparse": ze bevatte in de praktijk heel veel minder records dan in theorie zou kunnen. En toen bedacht Thompson dus, inmiddels al meer dan 40 jaar geleden, deze manier om een heel grote file te maken, die in de praktijk maar weinig echte diskruimte kost. In de toenmalige UNIX-kernel bestond het support hiervoor, ten opzichte van wat er al was, slechts uit een handvol regels code extra. Geniaal! En er zijn nog steeds nuttige toepassingen voor.