Hlavní navigace

Porovnání systémů Linux a FreeBSD (7)

8. 1. 2004
Doba čtení: 12 minut

Sdílet

Tímto dílem seriálu začíná kapitola zabývající se podrobně filesystémy (zejména Ext2 a UFS). Dnes se podíváme na základní princip unixového filesystému, jeho rozšíření, dostane se i na algoritmy alokace místa na disku a související problém fragmentace.

Filesystémy

Klasický unixový filesystém

Návrh linuxového filesystému Ext2 i filesystému FreeBSD UFS pochází z klasického unixového filesystému. Filesystém začíná superblokem, který obsahuje obecné informace — velikost filesystému, množství inod, inodu kořenového adresáře a podobné. Každému souboru a adresáři na klasickém unixovém filesystému odpovídá inoda. Inody jsou předalokovány ve speciální části filesystému, místo pro inody je určeno při vytváření filesystému a je dále neměnné. Velikost místa pro inody určuje maximální počet souborů a adresářů na filesystému. Místo, které se nepoužívá pro inody, se používá pro bloky. Velikost bloku je určena při vytváření filesystému. Inoda obsahuje všemožné informace o souboru nebo adresáři— délku, časy modifikace/vyt­voření/čtení, číslo uživatele a skupiny, práva přístupu a podobně. Inoda neobsahuje jméno souboru.

Inoda obsahuje 12 ukazatelů na prvních 12 bloků souboru. Pokud je soubor delší, ukazuje třináctý ukazatel na tzv. indirect block první úrovně — tento blok obsahuje ukazatele na další bloky inody. Počet ukazatelů v indirect bloku závisí na velikosti bloku. Pokud je soubor ještě delší, ukazuje čtrnáctý ukazatel v inodě na indirect blok druhé úrovně. Tento blok obsahuje ukazatele na další bloky, které teprve obsahují ukazatele na bloky souboru. Pokud je soubor tak dlouhý, že se na všechny bloky nepodaří ukázat ani pomocí indirect bloku druhé úrovně, použije se ukazatel na indirect blok třetí úrovně — pod ním jsou tři vrstvy bloků s ukazateli a pouze bloky poslední vrstvy ukazují na bloky souboru. Unixový filesystém umožňuje dělat v souborech díry. Pokud například uživatelský program zavolá syscally creat, lseek(10000), write, tak bude alokován pouze blok příslušející pozici 10000. Předchozí ukazatele budou mít hodnotu nula. Při jejich čtení jádro samo vrátí stránky plné nul, aniž by četlo cokoli z disku.

Adresáře jsou spravovány stejně jako soubory. Adresář je soubor obsahující sekvenci dvojic (jméno souboru, číslo inody). Je možno, aby na jednu inodu souboru ukazovalo několik položek adresářů — tato situace se nazývá hard-link. Není možno dělat hard-linky na adresáře.

K popisu volných bloků a volných inod se používají bitmapy. Každý bit v bitmapě odpovídá jednomu bloku (resp. jedné inodě) na filesystému. Z hlediska teoretické informatiky je sice bitmapa značně nevýhodná struktura pro popis volných bloků, ale v praxi se ukázala lepší než zřetězené seznamy volných bloků. Seznamy volných bloků mohou značně nabývat na velikosti (to lze sice řešit tak, že seznam uložíme do samotných volných bloků, ale to zase značně zpomaluje přístup a znemožňuje spojování volných bloků).

Rozšíření klasického unixového filesystému — Ext2 a UFS

Nejpoužívanějším filesystémem na Linuxu je Ext2 (čteno „second extended filesystem”). Struktura Ext2 je založena na klasickém unixovém filesystému. Filesystém byl rozdělen na tzv. skupiny (groups). Velikost skupiny je velikost bloku2*8. Na začátku každé skupiny se nacházejí inody, bitmapy pro inody a pro data téhle skupiny a kopie superbloku (použije se v případě, že byl hlavní superblok zničen). Rozdělení na skupiny omezuje přesouvání diskové hlavy a způsobuje rychlejší přístup. Pokud například z adresáře přistupujeme na inodu, je velká pravděpodobnost, že tato inoda bude ve stejné skupině, a že bude tedy rychle načtena; podobně když z inody přistupujeme na data, je pravděpodobné, že budou v téže skupině.

FreeBSD používá filesystém UFS (a je to jediný použitelný diskový filesystém na FreeBSD – ostatní filesystémy, které FreeBSD umí, jsou buď velmi jednoduché (FAT), plné chyb (Ext2 pro FreeBSD), nebo read-only (HPFS, NTFS, UDF)). UFS má rovněž disk rozdělen na skupiny podobně jako na Linuxu.

Dalším rozšířením UFS jsou fragmenty. Fragmenty lépe řeší problém velikosti bloku — pokud je blok moc malý, je filesystém pomalý, neboť bude hodně práce s bufferovou cachí a s vyhledáváním v indirect blocích. Pokud je blok moc velký, budou malé soubory zabírat zbytečně mnoho místa. UFS řeší tento problém tak, že používá větší velikost bloku, některé bloky rozděluje na menší fragmenty a do těch ukládá malé soubory. Velikost fragmentu je nejméně osmina velikosti bloku. Velikost bloku může být na UFS větší než velikost stránky (neboť bufferová cache na FreeBSD zvládá buffery větší než stránka; na Ext2 je maximální velikost bloku rovna velikosti stránky procesoru, na kterém Linux běží). V bitmapách jeden bit odpovídá jednomu fragmentu. Pro každou skupinu navíc existuje pole o velikosti 8, které říká, kolik volných fragmentů dané velikosti se ve skupině nachází. Pokud je třeba alokovat fragment dané velikosti, je vybrána skupina, ve které se fragment příslušné velikosti nachází, a pak je fragment nalezen v bitmapě (algoritmus prohledávání bitmapy funguje tak, že máme předpočítanou tabulku o velikosti 256, cyklicky bereme každý byte bitmapy, ten použijeme jako index do tabulky a bity výsledného bytu uloženého v tabulce říkají, zda je fragment dané velikosti v bytu dostupný. Odtud plyne omezení na velikost fragmentu jako osmina bloku). Při rozšiřování souboru alokovaného ve fragmentu FreeBSD buď alokuje větší fragment příslušné velikosti (optimalizace na místo na disku), nebo alokuje rovnou celý blok (optimalizace na rychlost— pokud se alokuje celý blok, tak ho již dále není třeba realokovat — filesystém bohužel v době zápisu bloku neví, jaká bude celková velikost souboru. Tento problém je vyřešen například v systému OS/2, kde uživatelský program může při vytváření souboru specifikovat jeho délku, pokud ji zná). Filesystém si pak na soubor vyhradí místo přesné velikosti. Filesystém sám mezi těmito dvěma algoritmy přepíná — pokud se začne zaplňovat, přepne na alokaci fragmentu přesné velikosti a do logu napíše optimization changed from TIME to SPACE. Když je na filesystému více volného místa, přepne zpátky.

V experimentálním FreeBSD 5 byla do filesystému přidána možnost dělat snapshoty. V kterémkoli okamžiku může správce udělat snapshot aktivního filesystému. Snapshot je soubor na daném filesystému obsahující konzistentní obsah blokového zařízení v době vzetí snapshotu. Dále se nemění, ani do něj není možno zapisovat. Snapshot je implementován jako soubor obsahující ukazatele na všechny alokvané bloky na filesystému. Při každém zápisu na filesystém je kontrolováno, zda blok nenáleží některému snapshotu, a pokud ano, tak je obsah snapshotu zkopírován jinam (je možno použít synchronní zápis snapshotu, což vede ke značnému zpomalení, ale zajišťuje konzistenci v případě výpadku, nebo asynchronní zápis, což konzistenci nezajišťuje). Nejčastějším použitím snapshotů je vytvoření konzistetní zálohy filesystému — po vzetí snapshotu může správce buď zálohovat celý snapshot a získat obraz blokového zařízení, nebo může snapshot namountovat read-only a zálohovat jednotlivé soubory, aniž by se během zálohování měnily. Dalším použitím snapshotů je možnost puštění fsck na namountovaném filesystému — vytvoří se snapshot, na něm se pustí fsck, a to místo zápisu modifikací do snapshotu říká ovladači namountovaného filesystému, jaké změny má provést. V kombinaci se soft-updates, které budou popsány později, to umožňuje okamžité zotavení po pádu a úplnou kontrolu filesystému na pozadí, zatímco je na filesystém možno běžně zapisovat.

Algoritmus alokace místa na disku

Zásadním problémem ve filesystému je určit, na kterém místě budou alokovány bloky souborů, aby docházelo k co nejnižší fragmentaci (fragmentace nastává na všech filesystémech a nemá nic společného s fragmenty na UFS, o kterých jsem se zmiňoval v předchozí kapitole). Fragmentace je jev, kdy soubor není uložen v souvislých blocích. Značně zpomaluje přístup k souborům — například pokud máme disk s přenosovou rychlostí 10MB/s a dobou přesunu hlavy 10ms, tak pokud bude soubor uložen ve fragmentech o velikosti 100kB, bude načítán dvakrát pomaleji. Neexistuje žádná teorie, která by se problémem alokace bloků na disku zabývala — všechny algoritmy jsou v podstatě empiricky vyzkoušené. Značnou nevýhodou při vývoji algoritmu pro alokaci místa je, že to, zda je dobrý či špatný, se pozná zpravidla až po několika měsících provozu — v podobě veliké nebo malé fragmentace. Navíc při různých použitích operačního systému jsou vyráběny soubory jiné velikosti a jsou mazány a vyráběny v jiném pořadí, proto algoritmus, který se osvědčí při jednom druhu zátěže, může zcela selhat při jiném druhu. Obecně platí, že na fragmentaci má velmi špatný vliv používání filesystému delší dobu ve stavu, kdy je téměř celý zaplněn (například moje HPFS partition o velikosti 1,7G, která byla zaplněna na 93 – 97 procent po dobu čtyř let, má již průměrnou velikost fragmentu 38kB. Jiná partition, která byla podobně zaplněna, ale byla používána pro uložení operačního systému a nebylo na ni moc zapisováno, má průměrnou velikost fragmentu 74kB). Když už k zaplnění dojde, pro snížení fragmentace by měly být odmazány ty soubory, které byly zapsány naposledy a které zaplnění způsobily. Velmi nepříjemné je také, pokud jsou současně zapisovány dva dlouhé soubory v jednom adresáři. I když se filesystémy snaží tuto situaci alespoň trochu řešit, mnohdy výsledek dopadá tak, že jsou soubory na disku proházené jeden mezi druhým s velmi malými fragmenty, což rychlost čtení sníží na polovinu.

Kvůli nemožnosti odladění nebo rychlého vyzkoušení se algoritmy alokace příliš nemění. Bylo empiricky ověřeno, že existující algoritmy mají rozumné výsledky při většině běžných použití, a nikdo tyto algoritmy nemá odvahu měnit, neboť by to mohlo přinést zhoršení, na které by se příliš pozdě a velmi těžko přišlo.

Na linuxovém filesystému Ext2 je algoritmus alokace následující: nejdříve se určí blok, poblíž něhož chceme alokovat (nazývaný goal). V případě, že soubor zatím nemá žádné bloky, je goal roven začátku skupiny. V případě, že soubor nějaké bloky má, je goal blok za posledním existujícím blokem souboru. Pak se zavolá funkce pro alokaci ( ext2_new_block), která má za cíl alokovat blok poblíž goalu. Funkce pracuje následovně — pokud je goal volný, vrátí rovnou jej. Pokud je volný blok s číslem větším než goal a menším než (goal + 63) & 63, je alokován tento blok. Pak se v bitmapě napravo od goalu hledá volný byte (čili 8 volných bloků), pokud je nalezen, alokuje se první blok na začátku tohoto souvislého volného místa. Pokud se v bitmapě nenalézá žádný volný byte, začne se hledat po jednotlivých bitech — najde se první volný blok napravo od goalu, a ten se alokuje. Pokud se ani takový blok nenajde, alokace pokračuje od začátku v další skupině (opět — nejdříve se hledá byte, pak se hledá bit, pak se přeskočí do další skupiny). Algoritmus nikdy nealokuje blok před goalem. Jediná možnost, kdy začne prohlížet bity před goalem, je, pokud už prošel celý disk, nic volného na něm nenalezl a vrátil se opět do výchozí skupiny.

Aby se zabránilo volání funkce alokátoru (která je celkem náročná) při každém zapsaném bloku a aby se zabránilo střídání bloků, pokud budeme současně zapisovat dva soubory, dělá Linux prealokaci. Alokační rutina nealokuje jeden blok, ale alokuje více souvislých bloků za alokovaným blokem, pokud se za ním nějaké volné bloky nacházejí. Implicitní hodnota je 8 předalokovaných bloků (to je dost málo — pokud budeme současně zapisovat dva soubory, budou se nám střídat po osmi blocích, což je celkem nepříjemné). Tuto hodnotu je možno změnit v superbloku, nicméně standardní programy mke2fs a tune2fs její nastavení neumožňují — člověk si tedy bude muset sám editovat obsah superbloku na disku. Když je soubor zavřen, jsou zbývající předalokované bloky uvolněny.

Algoritmus alokace byl vyvinut po zkušenostech s předchozími linuxovými filesystémy (Minix, Ext, XiaFS) a v praxi se ukázal jako kvalitní. Cílem algoritmu není a ani nesmí být „co nejméně zfragmentovat právě zapisovaný soubor” (algoritmus fungující podle tohoto cíle vypadá tak, že nalezne nejdelší volný úsek na disku a na jeho začátek začne zapisovat. Je zřejmé, že po delším provozu by na disku byly všechny velké úseky vyčerpány a zbyla by tam spousta malých kousíčků, což by fragmentaci mnohonásobně zvyšovalo). Můžeme si všimnout některých základních vlastností tohoto algoritmu.

  • Prohledávání pouze dopředu — ačkoli pro minimalizaci pohybu diskové hlavy by mohlo být vhodnější alokovat blízký blok vzadu než vzdálený blok vpředu, algoritmus bloky vzadu nealokuje. Sám jsem alokaci směrem dozadu napsal při psaní ovladače filesystému HPFS a výsledek nebyl moc dobrý — soubor se rozlézal dopředu i dozadu a vzdálenost mezi fragmenty byla v důsledku toho ještě větší, než kdyby se prohledávalo jen dopředu.
  • Vyhledávání celého volného bytu — to fragmentaci výrazně omezuje — soubor má pak aspoň osm souvislých bloků. Například filesystém XiaFS tohle nedělal, hledal jen následující volný bit a fragmentoval se značně. Nemá cenu si myslet, že pokud místo bytu budeme vyhledávat slovo, dvojslovo nebo větší souvislý úsek, tak fragmentaci ještě omezíme. Tím bychom omezili fragmentaci toho jednoho souboru, ale došlo by k závažnějšímu jevu — k fragmentaci volného místa na disku. Na disku by pak zůstávala spousta malých kousků volného místa, které jsme přeskočili ve snaze nezfragmentovat soubor, a jednoho dne pak zjistíme, že tyto kousíčky jsou jediné volné místo, které na disku zbylo. Vyhledávání delších úseků jsem také kdysi napsal a nebylo to dobré.
  • Snaha zaplnit skupinu — pokud se ve skupině nevyskytuje volný byte, vyhledá se jakýkoli volný bit ve skupině. To sice značně zfragmentuje soubor, ale zabraňuje to fragmentaci volného místa, neboť skupiny jsou zcela zaplňovány. Kdyby se místo toho hledal volný byte v jiné skupině, došlo by po nějaké době k situaci, že v žádné skupině žádný volný byte není a po disku je spousta malých volných kousíčků.

Alokátor na FreeBSD UFS (funkce ffs_alloc) pracuje podobně — také se snaží blok alokovat blízko předchozího bloku souboru, ale od Linuxu se liší. V bitmapě nehledá osm souvislých bloků, ale pouze jeden blok (bloky jsou ovšem větší než fragmenty; v bitmapě každý bit odpovídá jednomu fragmentu). Když blok není nalezen vpředu ve skupině, hledá se od začátku skupiny. Pokud je celá skupina plná, hledá se další skupina pomocí tzv. „kvadratického rehashování”. Kvadratické rehashování spočívá v tom, že se filesystém podívá na následující skupinu, pokud je plná, tak na skupinu o dvě vzdálenou, pokud je plná, tak na skupinu o čtyři vzdálenou, pak o osm skupin dále atd. Tím se zajišťuje lepší distribuovanost dat po disku a omezuje se situace, kdy se dva soubory budou vzájemně míchat mezi sebou. Další zvláštností alokátoru je, že pokud je v souboru alokován první nepřímý blok nebo pokud je alokován blok v nastaveném intervalu, tak přeskočí do další skupiny (přesněji: najde se další skupina, ve které je nadprůměrný počet volných bloků). Na první pohled to způsobuje fragmentaci souboru. Na druhou stranu to však umožňuje malé soubory ukládat ve skupině s jejich inodami a adresáři, neboť velké soubory tuto skupinu nezaplní.

Alokátor má rovněž optimalizace pro přístup k disku — může znát geometrii disku a snaží se pak bloky alokovat ve stejném válci. V případě, že máme disk, který se točí rychleji, než je počítač schopen odebírat data, může alokátor občas pár sektorů přeskočit, aby se data vždy četla přesně pod diskovou hlavou a nemuselo se čekat na jednu otáčku disku. Obě tyto optimalizace pocházejí ze starých dob, na moderních discích nemají absolutně žádný význam a je třeba je nechat vypnuté — současné disky svoji fyzickou geometrii skrývají, často nemají ani stejný počet sektorů na všech stopách, a pokud vůbec adresaci pomocí trojice (stopa/hlava/sek­tor) umožňují, přepočítávají tuto adresu na svoji interní reprezentaci. Vynechávání sektorů, aby se data četla rovnou pod hlavou, je zbytečné a zpomalující, neboť disky mají velikou read-ahead cache.

UX DAy - tip 2

Jak již bylo řečeno, UFS může rozdělit blok na menší fragmenty. Alokátor má i funkce na alokaci fragmentů. V případě rozšiřování souboru jsou fragmenty přemisťovány do větších fragmentů nebo do bloku.

FreeBSD dělá tzv. clusterování zápisu. Zapisovaná data jsou skládána do bloků o velikosti až 128kB, tyto bloky jsou pak pomocí jednoho požadavku na blokové zařízení zapsány. Při skládání dat do clusteru filesystém dělá přemisťování nesouvislých bloků do souvislé oblasti. Je otázkou, zda je to dobré, nebo ne — zapisování dat po velkých blocích jistě pomůže zvýšit rychlost, nicméně přemisťování bloků je zase značně zpomalující.

Byl pro vás článek přínosný?