ARCHIV

Jak funguje Unix - souborový systém

Jednou z nejzákladnějších součástí unixového systému je souborový systém, proto se dnes podíváme jak vlastně takový souborový systém funguje.

18.10.2005 06:00 | Aleš Hakl | Články autora | přečteno 20138×

Samotný Unix vznikl v podstatě jako experiment se souborovými systémy, je to v podstatě historicky první systém, jenž implementuje souborový systém tak, jak si jej dnes většinou představujeme.

Co to je souborový systém

Souborový systém je způsob ukládání dat na nějaké médium (pevný disk, paměť počítače...). Většinou se data organizují do souborů a soubory do adresářů a právě takovou organizací se budeme dnes zabývat. Mimo souborů může souborový systém obsahovat nejrůznější jiné objekty, ale ve skutečnosti se opět jedná o soubory, tak se těmito detaily nebudeme zabývat.

Z pohledu Unixu je souborový systém připojen do nějakého adresáře buďto uvnitř jiného systému souborů, nebo do tzv. kořenového adresáře (/). Zde můžeme nalézt tři druhy souborových systémů:

• lokální (ext2, reiserfs, XFS...)
• síťový (NFS, AFS, Samba...)
• virtuální (/proc, /sys, devfs...)

Vzhledem k tomu, že základem jsou lokální systémy a rozumný popis ostatních by byl nad rozsah několika knih, natož tohoto článku, budeme se zabývat pouze lokálními.

Jak to vypadá

Lokální souborový systém obecně pracuje nad nějakým blokovým zařízením (typicky pevný disk). Obsahem tohoto zařízení bude v nějaké formě následující:

• hlavička souborového systému (tzv. superblok)
• seznam volných bloků
• hlavičky souborů (tzv. i-uzly)
• adresáře
• vlastní data souborů
• případně tzv. žurnál

Hlavičky souborů (i-uzly)

Každá položka adresáře je svázána s takzvaným i-uzlem. Jedná se o datovou strukturu obsahující nejrůznější metadata (práva, vlastník...) a seznamy popisující polohu obsahu souboru na disku. Pro nás jsou nejzajímavější tyto seznamy. Obecně se jedná o seznam adres bloků souboru. Jako drobná optimalizace se na většině souborových systémů zavádí tzv. nepřímé bloky. Jedná se o to, že některé položky zmíněného seznamu neukazují na data, ale na další seznam bloků, případně na seznam obsahující opět odkazy na seznamy.

Tato datová struktura umožňuje ukládat na disk pouze ty bloky, které skutečně obsahují nějaká data, toto se nazývá "sparse file" nebo česky řídký soubor. Tohoto se často používá pro vytváření obrazů souborových systémů uvnitř souboru. Takovýto soubor máte pravděpodobně i na svém disku - soubor /var/log/lastlog právě tohoto mechanizmu využívá. Řídký soubor poznáme tak, že příkazy stat čí ls -ll nám zdělí větší velikost než příkaz du.

Většinou i-uzel obsahuje počet odkazů, jež na něj ukazují. I-uzel se označí jako volný, pokud tento počet klesne na nulu. Unix jako takový neumí přímo smazat soubor (či obecně i-uzel), nabízí pouze operaci unlink(2), která smaže odkaz na i-uzel. I-uzel se obvykle pro používané soubory ukládá do paměti, kde se ještě rozšíří o informace jako počet programů, jenž daný soubor používají, či zámky, které nad souborem existují. I-uzel se pochopitelně smaže až ve chvíli, kdy daný soubor nemá žádný proces otevřen.

Za zmínku také stojí, že délka souboru je pouze číslo v i-uzlu - soubor se zvětší automaticky zápisem za jeho konec. Pro zkrácení souboru existuje operace trunc(2), která jeho délku nastaví na konkrétní hodnotu a bloky, které se ocitnou za jeho koncem uvolní.

Jako alternativu, k výše popsané struktuře popisující rozložení souborů na disku, používají některé souborové systémy tzv. běhy. Rozložení souboru je pak reprezentováno seznamem jednotlivých úseků souboru (extentů). Každý úsek je zde popsán jako jeho první blok a počet dalších bloků, které za ním souvisle pokračují. Vyhledávání v této struktuře je ovšem pomalejší a neumožňuje tak snadnou realizaci řídkých souborů.

Adresáře

Adresář je ve své podstatě soubor, který obsahuje nějakou formu seznamu jmen souborů a čísel jim odpovídajících i-uzlů. Klasická implementace tohoto problému je prostý seznam, například v Systému V byl adresář soubor, který pro každý obsažený soubor obsahoval 14 bytů názvu a 2 byte čísla i-uzlu. Podobnou realizaci, samozřejmě s jiným způsobem uložení jmen souborů (bez omezení na 14 znaků) nalezneme v souborovém systému Ext2. Při vyhledávání souboru je pochopitelně nutno přečíst v nejnepříznivějším případě všechny položky adresáře, také mazání z této struktury přináší jisté problémy.

Toto však není jediná cesta, můžeme také nalézt hashovací tabulku či nějakou formu vyhledávacího stromu. Toto má ten význam, že se sníží časová náročnost vyhledání souboru v adresáři. Srovnání těchto technik celkem významně závisí na počtu a charakteru jmen souborů, proto případného zvídavého čtenáře odkáži na téměř libovolnou literaturu o datových strukturách.

Není nijak pevně dáno, že jeden soubor se v adresářové struktuře smí vyskytovat pouze jednou - pomocí operace link(2) můžeme k existujícímu souboru přiřadit další jméno - často se mluví o tzv. hard linku.

 Pokud vytvoříme nový adresář vzniknou v něm automaticky dva hard linky:

•  "." ukazuje na právě vytvořený adresář
• ".." - ukazuje na nadřazený adresář

Nově vytvořený adresář tedy začíná s třemi referencemi. Nový soubor pochopitelně má počet odkazů jedna.

Některé souborové systémy tyto odkazy do adresáře neukládají a namísto toho do i-uzlu adresáře ukládají ukazatel na nadřazený adresář.

Operace unlink(2) pochopitelně nefunguje na adresáře - pro ně existuje operace rmdir(2) mazající prázdné adresáře (tj. adresáře obsahující pouze "." a "..", neboli mající právě tři reference). Není doufám třeba zmiňovat, že "." a ".." nelze normálním způsobem smazat, už jenom proto, že se vlastně jedná o adresáře. Další zrada spočívá v tom, že pokud vytvoříme hard link na adresář, ve kterém tento hardlink leží, získáme poměrně zvláštní strukturu, která mnoho programů umí zmást a často jí není možno normální cestou smazat, proto může hard linky na adresáře vytvářet pouze uživatel root (předpokládá se, že když už někdo je uživatel root, tak že má alespoň hrubou představu, co dělá).

Volné bloky

Souborový systém udržuje seznam volných bloků, způsob jakým to provádí poměrně významě ovlivňuje výkon zápisu na souborový systém a nepřímo i výkon při čtení.

Původní implementace udržuje pole volných bloků, toto pole je umístěno do jednoho z těchto volných bloků a jeho poslední položka případně ukazuje na další podobné pole. Tento přístup má jednu zásadní výhodu - nezabírá na souborovém systému žádný prostor. Ovšem na druhou stranu způsobuje, že operační systém nemůže příliš plánovat rozmístění dat po disku - to po delším používání souborového systému způsobuje značnou fragmentaci souborů, což má negativní vliv na rychlost souborového systému.

Většina moderních souborových systémů používá nějakou formu bitové mapy, kde každý bit reprezentuje jeden blok a určuje, jestli je použitý nebo volný. Tato bitová mapa pochopitelně zabírá na disku nějaký prostor, ale na druhou stranu umožňuje operčnímu systému lépe plánovat rozložení dat na disku a tím efektivně omezovat fragmentaci.

Bitová mapa ovšem není jediný používaný přístup. Například v souborovém systému XFS nalezneme seznam volných bloků uložen jako seznam volných extentů indexovaný podle jejich pozice i délky.

Žurnál

Je celkem žádoucí, aby datové struktury popisující souborový systém zůstaly v konzistentním stavu, i pokud dojde k náhlé události, která znemožní dokončení probíhajícího zápisu. Některé souborové systémy tedy zavádějí technologii vypůjčenou ze světa databází, takzvaný žurnál.

Funguje to tak, že veškeré změny jsou nejprve zapsány do žurnálu, a až poté co byl žurnál prokazatelně zapsán na disk (alespoň z pohledu operačního systému), provedou se změny do  vlastních datových struktur souborového systému. A poté co spolehlivě proběhly tyto změny, označí se daná část žurnálu za provedenou a tudíž znovu použitelnou.

Pokud v průběhu této operace dojde k nějaké nenadálé události, jež znemožní její úspěšné dokončení (například výpadek proudu), není problém operaci dokončit při novém připojení souborového systému podle žurnálu. Pokud ještě nebyl dokončen zápis do žurnálu, nebyl souborový systém změněn a tudíž je možno celou operaci (v odborné terminologii transakci) zrušit.

Pokud žurnál pracuje pouze s metadaty (adresáře, i-uzly, seznam volných bloků...) může dojít k nekonzistenci dat v souborech, ovšem souborový systém zůstane v použitelném stavu. Aplikace pro které je konzistence jejich dat podstatná (typicky třeba databáze), si obvykle realizují ještě svůj vlastní žurnál nad svými daty.

Žurnál ovšem není jediná možnost, jak tento problém řešit. Klasické řešení je zapisovat bloky v takovém pořadí aby připadné přerušení zápisu příliš nevadilo a aby byl program fsck schopen snadno zjistit, kdy k tomuto přerušení došlo a souborový systém na základě této informace dovést do konzistentního stavu. Jinou alternativu představuje souborový systém Ext2, ten tento problém neřeší vůbec nijak a problém konzistence po havárii plně přesouvá na program fsck, ten je díky tomu neuvěřitelně rozsáhlý a inteligentní. Toto platí pouze pro jeho implementaci v Linuxu, BSD verze používají výše uvedený trik s pořadím zápisu. Ext2 většinu své rychlosti získává právě tím, že konzistenci dat nijak neřeší.

Žurnál ovšem přináší nevýhodu v tom, že na disku zabírá nějaké, typicky konstantní, místo. Kolik prostoru zabere můžeme obvykle nastavit při vytváření souborového systému. V některých případech existuje nástroj, jenž umí změnit velikost žurnálu na již existujícím souborovém systému (obvykle je nutné aby byl odpojen). Ovšem při dnešních velikostech disků je velikost žurnálu většinou zanedbatelná.

Rozmístění struktur na disku

Způsob rozmístění těchto struktur na disku zásadně ovlivňuje výkon souborového systému, jeho spolehlivost i některé další parametry, jako například maximální počet souborů.

První důležitý faktor je způsob uložení i-uzlů. Existují ve své podstatě dva přístupy:

• V samostatné tabulce konstantní velikosti
• Mezi datovými bloky

V poslední době se nejčastěji používá druhá varianta, mezi jejíž výhody patří pád omezení počtu souborů a rovnoměrnější rozprostření metadat po disku. Její nevýhodou je, že nelze úplně jednoznačně možné určit, zda-li je číslo i-uzlu platné, avšak jedná se o nevýhodu spíše teoretickou, protože ověřovat číslo i-uzlu potřebujeme pouze ve velmi speciálních případech. Druhou nevýhodou je, že v tomto případě i-uzel obvykle zabere celý blok disku, tento problém ovšem také není příliš signifikantní, protože v moderních souborových systémech obsahuje i-uzel spoustu informací a jeho velikost je většinou srovnatelná s velikostí bloku.

Je rozumné aby data, která spolu logicky souvisí, byly na disku co nejblíže(sníží se tim doba  potřebná k tomu aby je disk nalezl). Toto lze řešit různě.

Například souborový systém Ext2 si v tomto směru pomáhá rozdělením disku na více částí, kdy každá tato část má svoji vlastní bitmapu volných bloků a tabulku i-uzlů. Podobný trik nalezneme v souborovém systému XFS, který se snaží spolu související data rozmístit do vhodných částí disku podle poměrně složitých pravidel.

Další problém nastavá při použití zařízení, kde blok má omezený počet přepsání (paměť Flash, optická média), zde je vhodné, aby nedocházelo ke zbytečným zápisům a ty užitečné zápisy byly co nejrovnoměrněji rozloženy po všech blocích zařízení. Typickými filesystémy řešící tento problém jsou ISO 9660 a UDF (speciálně určené pro optická media a tudíž hodně odlišné od běžných unixových souborových systémů) a JFFS (určený pro paměti Flash, mající poměrně netradiční strukturu). Poznamenejme, že i přes tento problém se na paměťových kartách používá a téměř vždy používal souborový systém FAT. Pravdou je, že v poslední době se výdrž těchto pamětí zvýšila na tolik, že v běžných aplikacích nemá příliš význam se tímto problémem zabývat. Dalším faktem je to, že většina paměťových karet má poměrně rozsáhlou vnitřní logiku, jež se snaží uživatele od tohoto problému výrazně odstínit.

Významně se lišící řešení

Výše popsané řešení jsou víceméně klasická, ovšem některé souborové systémy jdou cestou významně odlišnou, ty, které jsou pro nás zajímavé, zmíníme v této části. Mezi asi nejzajímavější souborové systémy v tomto směru patří ReiserFS a NTFS ze světa na druhé straně barikády. Z historických důvodů také stojí zmínit souborový systém FAT. A nakonec se podíváme na jednu specialitu - ono se totiž dá jít úplně jinou cestou.

ReiserFS v4

Souborový systém ReiserFS je význačný tím, že vše kromě bitmapy volných bloků je uloženo v jednom velkém vyhledávácím stromu. Mezi různými verzemi nalezneme rozdíly, ale základní myšlenka je ve své podstatě stejná.

Tato struktura umožňuje provádět atomické transakce bez nutnosti dvojího zápisu dat na disk. Jedná se o to, že uzel stromu se okopíruje a odkazy na něj se obdobným způsobem aktualizují - dojde tedy k rekurzi až ke kořenu stromu. Pouze tento kořen stromu je nutné aktualizovat standardním způsobem pomocí žurnálu. Žurnál se použije také tehdy, pokud je to vhodné s ohledem na rozložení dat na disku. Je totiž pochopitelné, že výše uvedené schéma atomického zápisu mění umístění bloků na disku.

NTFS

Tento souborový systém je zajímavý tím, že je přímo postaven na atributech souborů, dokonce i obsah souboru je ve své podstatě jeho atributem. Také je zajímavé, že téměř všechny jeho datové struktury jsou soubory. Dokonce i bootsektor disku je reprezentován jako soubor v seznamu souborů.

Souborový systém udržuje seznam souborů, jedná se o jeden dlouhý seznam všech souborů a jím odpovídajících atributů pro celý souborový systém. Hodnota atributu může být buďto uvedena přímo v tomto seznamu nebo se může jednat o odkaz na jiná místa disku, tzv. běh.

Také jsou zajímavé mnohé postupy používané při alokaci prostoru na zařízení, NTFS (zřejmě z výkonových důvodů) zanechává volný prostor v okolí nejrůznějších datových struktur. Volný prostor je ovšem automaticky zmenšen, pokud není jiná možnost kam běžná data uložit.

Z této struktury vyplývá mnoho zajímavých vlastností, bohužel je tento souborový systém specifický pro operační systém Windows NT a firma Microsoft, jež jej vyvíjí jeho detailní specifikace nedává k dispozici, dokonce ani operační systém Windows NT neumí využít všechny vlastnosti tohoto souborového systému (on zřejmě umí, ale ne úplně dokumentovaným způsobem).

FAT

Souborový systém FAT v mnohém připomíná výše popsané Unixové systémy. Nicméně nemá i-uzly. Informace, jež by i-uzel obsahoval jsou z části obsaženy v položkách adresáře a z druhé části v něčem, co kdysi byla bitmapa volných bloků, zvaném File Allocation Table.

Podle této tabulky vznikl i název celého souborového systému. Jedná se o seznam všech bloků a každá položka obsahuje buďto informaci o tom, jaký blok v souboru za tímto následuje nebo speciální hodnotu označující konec souboru, z nějakého důvodu nepoužitelný blok a nebo prázdný blok. Není doufám potřeba zdůrazňovat, že pokud dojde k nějakému poškození této tabulky, souborový systém v lepším případě nepůjde připojit vůbec a v horším případě se začnou dít podivné věci.

Mnohé rozšíření souborového systému FAT (klasicky třeba jména souboru delší než 8+3 znaky) jsou realizována přídáním nějaké podivné položky adresáře, původní implementace v DOSu totiž mnohé položky adresáře prostě ignorovala a tak je bez problémů možné ukládat právě do adresářů různé rozšířené informace.

Log-structured

Souborový systém "Log-structured filesystem" existujici v NetBSD (v aktuálních verzích bohužel neudržovaný) a souborový systém JFFS používaný v nejrůznějších linuxových embeded zařízeních jsou typickými zástupci této kategorie. Podobnou strukturu používají některé databáze a servery GoogleFS pro ukládání metadat.

Základní myšlenkou je, že souborový systém obsahuje pouze žurnál do kterého se zapisují jeho změny, pokud přestane být k dispozici prostor pro zápis dalších změn, dojde k odstranění starých záznamů, které byly nahrazeny novějšími.

Tato struktura je inspirována snahou o co nejrychlejší zápis s tím, že většina čtení je uspokojena z cache a tudíž rychlost čtení není až tak kritická. Další vlastnost, jež tyto souborové systémy mají, je relativně rovnoměrné rozložení zátěže na zařízení, což je hlavní motivací souborového systému JFFS optimalizovaného pro paměti Flash. Aktualní verzi JFFS zvanou JFFS2 používají nejrůznější malé zařízení jako jsou linuxová PDA, webkamery a malé routery (či servisní procesor v serveru Sun Fire V20z).

Pokud něco z tohoto článku není pochopitelné nebo snad vypadá jako naprostý blábol, uvítám vaše příspěvky, dotazy a připomínky v diskuzi.

Zdroje

• R.Card, T.Ts'o, S.Tweedie: Design and Implementation of the Second Extended Filesystem
• namesys.com (ReiserFS)
• A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, and G. Peck: Scalability in the XFS File System
• Linux-NTFS: NTFS documentation
• M. J. Bach: The Design of the UNIX Operating System, Prentice Hall, 1986
• Souborové systémy v Linuxu

Verze pro tisk