LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> 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 16065×

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ů:

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

Verze pro tisk

pridej.cz

 

DISKUZE

Díky 25.10.2005 11:16 Jaroslav Syrový




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

8.1.2017 17:51 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 19. ledna od 18:30 v pražském hackerspacu Brmlab. Tentokrát je tématem srazu ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. K vidění bude mechanická klávesnice dasKeyboard, trackball Logitech nebo grafický tablet (a velký touchpad) Wacom. Přineste i vy ukázat svoje zajímavé klávesnice a další HW. V 18:20 je sraz před budovou, v 18:30 jdeme společně dovnitř, je tedy dobré přijít včas. Podle zájmu se později přesuneme do nějaké restaurace v okolí.
Přidat komentář

1.12.2016 22:13 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.
Komentářů: 1

4.9.2016 20:13 /Pavel `Goldenfish' Kysilka
PR: Dne 22.9.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, provozování ERP v cloudu, o hostování různých typů softwaru, ale třeba i o zálohování dat nabízeném podnikům formou služby.
Přidat komentář

1.9.2016 11:27 /Honza Javorek
Česká konference o Pythonu, PyCon CZ, stále hledá přednášející skrz dobrovolné přihlášky. Máte-li zajímavé téma, neváhejte a zkuste jej přihlásit, uzávěrka je již 12. září. Konference letos přijímá i přednášky v češtině a nabízí pomoc s přípravou začínajícím speakerům. Řečníci mají navíc vstup zadarmo! Více na webu.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

17.4.2017 19:15 / Jakub shoop
chyba

9.3.2017 11:44 / Jaromir Obr
Re: chyba

18.1.2017 20:18 / martin horky
Spolupraca linuxu a microsoftu

17.1.2017 9:57 / Pavel Hrubeš
Re: Externí USB televizní karta

4.12.2016 22:54 / František Kučera
Dárek

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze