Filesystem
-=-=-=-=-=-=
I came, I saw, I deleted all your files.
Jedna z prvních funkcí, které OS dělaly je file system. Ten má
za úkol namnožit jeden disk na mnoho souborů. UNIX jako první měl
hiearchickou strukturu na rozdíl od MSDOSu ale nemá více disku pod
písmenky, ale každý filesystém se připojuje do nějakého podadresáře
hlavního filesystému. (na tento systém už částečně přešly i Windows,
které místo adresáře / mají "tento počítač" :) Na filesystém je opět
kladeno několik protichůdných požadavků
- Rychlost
- Úspornost
- Bezpečnost
- Aby nebyly příliš malé omezení na velikost FS a souborů
Jeden ze způsobů je rozdělit disk na bloky určité velikosti a ty
přidělovat souborům. Je ale nutné někde držet tabulku komu který
blok patří.
FAT
Mezi nejklasičtější řešení patří FAT. Na disku se vyhradí místo,
kde každý blok má svoje číslo. To označuje následující blok.
Pokud chcete načíst soubor a víte jeho první bok, načtete první
blok a pomocí tohoto čísla se dostanete na další atd. až na konci
je jakási zarážka. Nepoužité bloky jsou potom označeny speciálním
číslem.
Tato struktura má ale překvapivě všechny záporné vlastnosti:
Je pomalá - pro načtení každého bloku potřebujete jeden přístup
do fat. Jsou metody, které jich potřebují mnohem méně. Alokace
volných bloků znamená, že musíte projít celou FAT a najít
nepoužité bloky. Není možné bloky udržovat ve stejném seznamu
jako soubory, protože by to přinášelo velkou fragmentaci (bloky
se nemusí uvolňovat a přidávat do seznamu tak, jak jdou fyzicky
za sebou). A je téměř nemožné používat nějaké chytřejší alokační
algoritmy zabraňující fragmentaci
Je nebezpečná - Je velmi snadné tabulku poškodit. Přepsáním několika
KB disku můžete ztratit veškteré informace o rozložení disku.
Je možné udržovat dvě kopie FAT, ale to zase zdržuje. Také je
náchylná k crosschainům, lostchainům apod.
Je omezená - to asi všichni znáte. Napřed v DOSu FAT omezili
na 32MB, pak na 2GB apod. Je to dané tím, že je třeba určit
velikost ukazatelů a to omezuje počet bloků.
Je marnotratná - FAT je přinejmenším omezena tím, že se musí celá
vejít do paměti (jinak není možný žádný efektivní algoritmus
na vyhledání volných bloků) (mimochodem FAT32 se už do RAM
nevejde). To omezuje počet bloků na disku a zvětšuje je. To
přináší další plýtvání.
Je mnoho přirozených cest jak tuto strukturu vylepšit:
1) udělat dvě kopie - zvýší to bezpečnost ale zhorší všechny ostatní
paramety
2) umístit ji doprostřed disku, aby byla blíž datům - zvýší rychlost
a bezpečnost (většinou se přepisuje začátek disku) a ostatní
neovlivní. To používá třeba OS/2
3) rozdělit disk na části (groups). To přináší mnoho zajimavých
vylepšení:
1) částečně odpadají limity na velikost disku, protože group se
může chovat do jisté míry jako oddělená parition.
2) je možné zrychlyt alokaci bloků, protože je možné védst
informaci o počtu volných bloku v každé části a pokoušet se
alokovat pouze tam, kde to má smysl. Navíc je možné tyto
informace využít v algoritmech zabraňujících fragmentaci
3) Je možné udržovat "lokalitu dat". Tedy adresář, jeho soubory
a záznamy o rozložení ukládat pokud možno do stejné části.
To zvyšuje rychlost (informace jsou blízko dat) a snižuje
fragmentaci
4) zvyšuje to bezpečnost, protože přemazáním části disku
poškodíte maximálně pár group
To je první z rozšíření, které má ext2fs v Linuxu
UNIXový filesystém
Inode
UNIXy zase používají úplně jiný způsob uložení informací
o souborech. Volné místo na disktu je spravováno pomocí bitmapy -
každý blok ma bit, pokud je nastaven na 1, je použitý, jinak je
volný. To zrychluje postup vyhledávání volného místa. Ve Vivafs
navíc mají bitmapu po čtyřech a osmi blocích, která ještě urychluje
vyhledávání ale zase zvyšuje marnostratnost. V případě, že je disk
rozdělen do částí, jsou bitmapy dostatečně malé, aby je bylo možné
projít.
Každý soubor je v UNIXu represenotván číslem Inode. Každá inoda
má pevně danou pozici v inodové tabulce. Každá inoda obsahuje
informace o velikosti souboru, přístupových právech apod. Navíc
ale obsahuje přímo několik odkazů na bloky souboru, takže několik
prvních KB souboru lze načíst bez dalších přístupů na disk. Pak
obsahuje odkaz na indirect block. To je blok obsahující pouze odkazy
na další bloky s daty. Takže několik dalších MB souboru lze načíst
s jedním přístupem navíc. Pak obsahuje odkaz na dva double a triple
indirect bloky. Ty obsahují odkazy na indirect bloky a tak soubor
může mít i několik GB.
Inodová
tabulka inonoda 2 data
+-------+ +----------+ +----------+
|ino0 | | parametry| +-------------->| blok0 |
|ino1 | | souboru | | +------------>| blok1 |
|ino2 +----->|(práva...)| | | | blok2 |
|ino3 | | | | | +--------+ | blok3 |
...... |direct bl.+------+ | |direct b|>| blok4 |
|direct bl.+--------+ |direct b|>| ..... |
|indirect b+---------->|direct b|>| |
|dindirect | | ..... | | |
|tindirect | | | | |
+----------+
Tento způsob je velmi rychlý, je také poměrně bezpečný - protože
tabulky jsou rozdistribuovány a pomocí inodvých tabulek lze opravit
bitmapy a naopak. Jeho hlavní omezení je v tom, že velikosti tabulek
na inody jsou pevně dané a tak se může stát, že dojdou. V Linuxu
se mi to ale ještě nestalo. Existují filesystémy co Inode tabulku
održují v B stromech a tak může neomezeně růst a zmenšovat se
za celkem malou cenu v rychlosti. Na druhou stranu to ale zmenšuje
bezpečnost, protože Inode tabulka se může snadno rozpadnout.
Adresáře
Adresáře v UNIXu jsou vpodstatě jenom převodní tabulky mezi
jménem souboru a adresářem. Adresáře se běžně udžřují jako normální
soubory obsahující záznamy za sebou. Má to ale nevýhodu, že když
nějaký soubor smažete, vytvoří se díra a tak některé adresáře
zabírají zbytečně mnoho místa.
Jiná metoda jak udržovat adresáře jsou bstromy a nebo hashovací
tabulky. To umožňuje mnohem rychlejší proheldávání adresářů (V
UNIXU se to většinou obcházi tak, že při prvním přistupu se adresář
nahraje do paměti a tam se zahashuje). Takové uložení adresářů
používá Amiga. Nevýhoda ale zase je, že vypsání souborů v adresáři
je pomalé. Na Amize se to také řešilo tak, že se adresář navíc
ukládal normálně. Vypisování v Inodových filesystémech je také
pomalé. Protože pokud potřebujete nejenom jméno ale i některé další
informace (délku souboru apod.) je nutné načíst i inody jednotlivých
souborů. Proto je directory cache v UNIXu důležitá.
Superblock
Superblock je blok obsahující informace o filesystému - o jaký
typ se jedná, jak je velký a další parametry. V DOSu se jmenuje MBR.
Protože se jedná o velmi důležitá data, UNIXové filesystémy mají
hned několik kopií tohoto superblocku. Ext2fs dělá na začátku každé
groupy jeden.
Klasické UNIXové informace ukládají do superblocku ještě jednu
šikovnou informaci - jestli je vpořádku. Při pripojení filesystému
se nastaví flag, že filesystém je používán. Potom, co se filesystém
odmountuje, flag se zpátky snuluje. Navíc v případě, že při přístupu
k filesystému se vyskytla chyba, nastaví flag, že filesystém je
vadný. Při rebootu se potom tyto flagy zkontrolují a v případě,
že filesystém není v pořádku, zkontroluje se.
Hard linky a symbolické linky
Inodový přístup v UNIXových filesystémech má jednu zajímavou
výhodu - je možné vytvořit více adresářových položek pro jednu inodu
a tak jednomu souboru dát dvě jména. To se v UNIXu často používá.
Inoda potom zaniká pouze v případě, že žádná adresářová položka už
na ni neukazuje. Musí tedy mít čítač odkazů na ni.
Toto řešení má ale jedno omezení - není možné tyto linky
provádět mezi filesystémy. Většina UNIXů navíc neumožňuje hard
linkovat adresáře. To odstraňuje soft link. To je soubor se
speciálním flagem obsahující pouze cestu na nový soubor. Při
otevření tohoto souboru se tento link následuje a otevře se soubor
jiný. To narozdíl od hard linku umožňuje dělat libovolně. Chová
se ale trochu jinak - je o něco pomalejší, nastavením přístupových
práv pro link se nezmění přístupová práva původního souboru a pokud
smažete původní soubor, inoda se uvolní a link přestane fungovat.
Někeré zajímavé vylepšení
Extend based alokace
Jiné vylepšení inodového systému je neukládat ukazatele
na jednotlivé bloky ale na bloky bloků (soubor začína blokem 10,
je sfragmentován po bloce 18, začíná na 22 a končí na 40). Při
nízké fragmentaci (na Ext2fs je většinou pod 10%) by to mohlo úplně
zamezit indirect a double indirect blokům. Probém tohoto řešení
je to, že se špatně implementují děravé soubory z POSIXu. (UNIXové
filesystémy většinou umožňují udělat do souboru díru, která čte
jako samé nuly. V tohoto uložení to vyžaduje předělání celé tabulky
v případě, že díra vzniká uprostřed) Do Ext2 se do budoucna plánuje,
že bude podporovat obojí. Po založení souboru bude používat tento
způsob a potom, co do něj někdo vytvoří díru (nestává se to často)
Inoda se překonvertuje.
Sparse bitmap
Sparse bitmap je jiný formát uložení alokačních informací.
Výchází také z uvahy, že soubory jsou často málo fragmentované.
Narozdil od extend alokace ale neukládá intervaly, ale bitmapy.
Není možné uložit bitmapu celého disku (kde 1 znamená, že zrovna tam
je soubor uložen a 0 že není). Tato bitmapa by byla většinou nulová
a tak by zabírala zbytečně mnoho místa. Sparse bitmap se zkládá
z položek, kde každá obsahuje část této bitmapy. Obsahuje začátek
bitmapy a velikost této části (0-256) pak následuje bitmapa.
Tento způsob uložení je mnohem optimálnější, než normální direct
a indirect bloky. Stejně jako v extendové alokaci jsou problémy
s dírama v souborech. Narozdíl ale od extendů lépe podporuje "trochu
sfragmentované soubory". Tento způsob uložení používá Vsta. Poslední
implementační problém je to, že vytváření a práce s těmito bitmapama
je poněkud pomalá a tak při dnešním poměru výkon CPU/výkon disku se
často nevyplácí.
Defragmentační algoritmy
Jedním z největších problémů filesystému je fragmentace. Tu ale
lze omezit vhodnou heruistikou. Existuje mnoho způsobů například.
Nejjdenodušší asi je pre-alokace. Při zápisu do souboru se naalokuje
hned několik dalších bloků. To zamezí tomu, aby jiný soubor
nenaalokoval bloky těsně za tímto souborem a nezamezil jeho růstu.
Navíc to urychlí alokaci, protože se neprovádí tak často. (Tento
algoritmus používá většina FS - Ext2, nebo i Windows :)
Dalším vylepšením je to, že na začátku se pro soubor najde malá
díra a v případě že soubor z ní vyroste, najde se díra větší. To
zařídí, aby malé soubory učině zaplácaly malé díry a velké soubory
se sice na začátku jednou, nebo dvakrát sfragmentují ale vzhledem
k jejich velikosti to nevadí.
Při použití bitmap se nabízí další jednoduché vylepšení
- pokusit se alokovat (a prealokovat) tak, aby se v bitmapě
vyskytovalý buď 00, nebo FF. To způsobí, že díry ve filesystému
jsou dostatečně velké. Při alokaci je pak dobré se napřed dívat
po 00 a teprve když se žádná nenajde hledat nulový bit. To způsobí,
že u "špatně" zaplňených bloků systém bude prostě čekat, až se tento
blok uvolní tak dlouho, jak jen to bude možné.
Je samozřejmě i mnoho dalších algoritmů. Ext2fs v Linuxu
implementuje všechny zmíněné a výsledek je docela dobrý. Za 5 let
používání Linuxu a po několika reinstalacích je fragmentace mého
disku asi 8%. Takže defragmentační program vůbec není třeba.
Komprese
Další z možných vylepšení filesystému je komprese. Asi
nejklasičtější program na kompresi disku je stacker jeho obdoba
pod Linuxem je double. Ten funguje tak, že vytvoří normální disk
dvojnásobné (nebo větší) velikosti, než je fyzická velikost a disk
potom kompresuje tak, jako by se jednalo o jeden soubor. Tento
postup má ale několik nevýhod. Výsledné komprese se může výrazně
lišit od té odhadnuté na začátku a tak se může stát, že virtuální
disk je sice plný ale fyzický ne, nebo naopak, že na fyzický disk
se už nic nevejde ale na virtuální ještě ano. To je větší problém,
protože systém bude chtít na disk zapsat, ale kompresní program to
už udělat nemůže. Většina programů se zachová tak, že dá disk read
only, nebo hlásí špatný sektor.
Navíc toto řešení způsobuje dvojí fragmentaci. Jedna je klasická
na virtuálním disku. Druhá je na fyzickém - v případě, že na určité
místo se uloží data, která se zabalí méně, než ta přehcházející.
Proto je fragmentace opravdový problém. I bezpečnost není nejlepší -
při poškození fyzického disku se jednak může rozbít alokační tabulka
kompresního programu a jednak poškodit data, které pak rozhodí
filesystém na virtuálním disku.
Existuje i jiné řešení - přidělat kompresi rovnou do filesystému
- soubory se při ukládání budou kompresovat a ukladat se rovnou
zabalené. To zvyšuje bezpečnost - tabulky filesystému kompresované
nejsou a tak jsou mnohem méně náchylné vůči chybám. Zabraňuje
dvojité fragmentaci. Má i několik dalších výhod - je možné u každého
souboru nastavit jak bude pakován a tak zabalit pouze málo používané
soubory apod. I toto řešení ale zvyšuje fragmentaci (v případě,
že někdo uloží doprostřed souboru nová data, která se zabalí jinak)
jinak se ale zdá být ve všech ohledech lepší.
Pro ext2fs existuje patch e2compr, který implementuje popsanou
metodu. Funguje velmi spolehlivě. Je zatím ve vývoji ale bude
pravděpodobně zařazen do oficiálního Linuxu před verzí 2.2.
Některé zajímavé filesystémy
Ext2fs
Je mnoho různých přístupů k filesystému. Do jednoho filesystému
není možné dát všechny tato vylepšení, protože jsou často
protichůdná. Proto jsem si vybral několik zajímavějších filesystému
a popíšu krátce jejich implementaci.
Jako první jsem si vybral Ext2fs, protože je to velmi rychlý
a bezpečný filesystém. Jeho autoři podrobně studovali ostatní
dostupné návrhy a vytvořili překvapivě jednoduchý filesystém, který
přesto v mnoha parametrech předčí i ty nejsložitější konkurenty.
Používá ho Linux a tak umí vše, co běžné UNIXové filesystémy (hard
linky, soft linky, děravé soubory apod.) Velikost filesystému je
omezena na (tedy 4,5TB), velikost souboru na 4GB, délka názvu na 256
znaků.
Filesystém je poněkud marnotratný, ale není to nejhorší.
Na 300MB disku je režije za tabulky 10MB, tedy okolo 3%. To lze
snížit, pokud snížíte počet Inode. Standardně se vytváří jedna Inode
na 4KB. Můj (téměř plný) disk obsahuje 154432 inod z nihž je 113255
vloných.
Superblock obsahuje magické číslo EF53 hexa (Extended Filesystem
verze 5.3), informaci o tom, jestli je filesystem vpořádku,
velikosti inod a další informace. Také lze nastavit počet rebootů
po kterém se filesystem zkontroluje (defaultně 20), nebo časový
interval a minimální počet bloků a inod pro některého uživatele
(roota).
Velikost bloků je volitebná, nejčastěji se používá 1KB. Disk je
rozdělený do skupin (group) standardně po 8192 blocích. Každá groupa
obsahuje kopii superblocku, všechny descriptory group (kde jsou
bitmapy, kolik je volných bloků a inod, kolik je v inodě adresářů),
tabulku inod, bitmapu bloků a bitmapu inod.
Inoda obsahuje všechny běžné informace, 6 ukazatelů na bloky,
jeden na indirect, double indirect a triple indirect.
Filesystém provádí všechny popsané defragmentační algoritmy.
Navíc podporuje fast symbolické linky - pokud je název dostatečně
krátký, nahraje se přímo do tabulky pro bloky a tak se ušetří 1KB.
Navíc je ale filesystém velmi rozšiřitelný. Inody obsahují místo
na atributy a další dodatečné informace. V inodách jsou položky
a atributy plánované pro ACL, kompresi, intervalovou alokaci,
swapování do filesystému a další rozšíření. Většina z nich již
byla experimentálně implementována. Pod GNU hurdem byly přidány
translatory.
Existují ovladače pro Linux, Hurd, Planem9, Windows95 (read
only), Dos, DJGPP, WindowsNT, OS/2 a další.
Extend based filesystém
Tento filesystém implementuje například Vsta. Extend based
filesystem kombinuje nápad z Extent based alokace (ukládat
intervaly) s jednoduchým vylepšením FAT - ukazatel na další blok se
nedává do zvláštní tabulky ale na začátek tohoto bloku. Takže každý
blok je uveden délkou souvislého intervalu a ukazatelem na další.
To umožňuje používat velmi malé bloky (třeba i velikosti 1
byte). To šetří mnoho místa. Protože se Inoda ukládá začátku prvního
extentu souboru, odpadá omezení na počet inod (číslo inode je potom
fyzická pozice inode na disku). Extend je based filesystem velmi
rychlý na čtení - pokud víte začátek souboru, jedním přístupem
načtete celý první fragment souboru a víte začátek dat, přístupová
práva apod. Takže vlastně nepotřebujete žádné přístupy navíc.
Volné bloky se udržují také v seznamu. Seznamy se třídí a bloky
se spojují pokud to je možné. List začíná v nějakém sektoru,
tam je několik položek seznamu plus ukazatel na další sektor se
seznamem. Pokud v daném sektoru klesne počet položek na 0, sektor se
uvolní a nezabírá žádné místo na disku. Díky tomu je režije disku
na udržování tabulek s volným místem nulová. Pokud na disku není
žádné volné místo, ani žádné takové sektory neexistují.
Tento způsob ukládání volného místa umožňuje relativně
inteligentní alokaci - je velmi jednoduché alokovat dopředu.
Vsta při vytvoření souboru naalokuje první sektor (512 byte).
Pokud soubor přesáhne tuto délku, naalokuje souvislý blok za tímto
sektorem až do délky 64 kb (to lze v lineárních seznamech udělat
velmi snadno). Kdyby byl disk rozdělen do group, bylo by možné dělat
i další popsané optimalizace
Tento přístup má ale i některé nevýhody - je velmi těžké
filesystém opravit, více se fragmentuje (protože se může rozpadnou
na velmi malé části), má problémy s děravými soubory apod.
V poslední době se vyskytlo několik projektů, které se snaží
na tomto principu vyvinou bezpečnější a méně se fragmentující
filesystém. Také buffer cache v systému musí být navržena poněkud
jinak a pracovat z bloky libovolné délky.
LOG FS (Journaling FS)
Jeden z nejšílenějších a nejzajímavějších návrhů filesystémů
posledních let je logfs. Má oproti popsaným filesystémům dvě hlavní
výhody - několikanásobně rychlejší zápisy a téměř 100% odolnost
vůči pádům systému - po opětovném nastartování systému není nutné
filesystém kontrolovat.
Jak tohoto lze dosáhnout? Na začátky bylo pozorování, že
klasické filesystémy se nechovají nejlépe například v situaci, kdy
máte fragmentovaný soubor a ten chcete na několika místech přepsat.
Disk potom musí jezdit po oddělených částech souboru a přepisovat
je. Tato situace je například velmi častá u adresářů.
LogFS se chová úplně jinak. Základní myšlenka spočívá v tom,
že data se sekvenčně zapisují do "logu" což je jakýsi seznam změn.
To způsobí zrychlení při zápisu. Disk totiž vůbec nemusí seekovat.
Jednotlivé změny se napřed udržují v cache a zkoncentrují na větší
bloky a teprve potom se asynchroně uloží. Inody potom obsahují
informace o tom, kde jsou poslední verze jednotlivých částí souboru.
Protože se Inody logují stejným způsobem, je filesystém v každém
svém stádiu na disku korektní. Jiný důsledek je také to, že mazání
a vytváření souborů nevyžaduje krátké zápisy do jednotlivých tabulek
ve filesystému a tak je několikanásobně rychlejší.
Protože jsou inody náhodně roztroušené po disku a stále se
stěhují, je nutné udžovat mapu inod, která hlídá, kam se která
inoda odstěhovala. Remapovací tabulka také obsahuje o tom, jestli je
inoda obsazená, nebo volná a o verzi. Tato tabulka se ukládá do logu
stejně jako všechny ostatní a stejně tak se cachuje.
Pokud přeskočíme hledání v inodové mapě, je čtení z disku stejné
jako v klasických filesystémech a proto i stejně rychlé.
Jedna z věcí, o které jsem zde pomlčel je co se stane v případě,
že log dojde na konec disku. Zde je řešení také ale celkem
jednoduché. Filesystém je schopný zjistit, které pozice na disku
jsou ještě třeba a které jsou už free. Disk si rozdělí na nějaké
větší segmenty (1MB). V případě, že log je na konci, najde nějaký
volný segmenty a začne zapisovat tam. Protože jsou segmenty velké,
není zpomalení velké. V případě, že žádný volný segmenty není,
najdou se dva částečně použité, spojí do jednoho a tak se nový
segment uvolní. To lze udělat tak, že prostě segmenty načtete
do cache, uvolníte je a oni se potom samy uloží do logu.
K určování volných bloků se používá informace ze začátku.
Ta obsahuje informace o tom, které bloky jsou obsaženy kterými
soubory a verze těchto souborů. Pokud verze nesedí, ví se, že bloky
jsou volné. Pokud verze sedí, je nutné porovnat data z inod. Navíc
filesystém udržuje v paměti informace o počtu volných bloků v každém
segmentu.
Experimentální výsledky ukazují, že filesystém je
několikanásobně rychlejší při zápisu a asi o 10% pomalejší při čtení
kvůli zvýšené fragmentaci.
ReiserFS
ReiserFS je poslední zajímavý filesystém, o kterém bych
chtěl napsat. Tento filesystém navrh Hans Reiser a napsal
jeho ovladač pro Linux. ReiserFS je zatím v vývoji a ovladač
není v oficiálním kernelu. Kód je ale už velmi stabilní
a některé servery jej používají pro squid cache. Naní ale
zaručena zatím zpětná kompatibilita. Domácí stránka se nachází
na http://idiom.com/beverly/reiserfs.html.
Jeho autor se narozdíl od autorů ostatních filesystémů zaměřil
zejména na krátké soubory. Běžné filesystémy nejsou z tohoto
pohledu příliš efektivní. Autor předpokládá, že to je důvod,
proč na disku malých souboru je relativně málo - autoři aplikací
je sami spojují do větších, aby ušetřili místo. Na DOSu to je
vzhledem k neefektivitě dat mnohem častější, než na UNIXu. Ale i tam
například pošta je jeden soubor, přesto že by to mohl být adresář
obsahunící jednotlivé dopisy. Proto autor předpokládá že počet
krátkých souborů stoupne v případě, že filesystém je bude dobře
zvládat.
Velikost souborů zaokrouhlují na velikost bloku a tím plýtvají
místem (na FAT pod DOSem a Windowsy je na 1GB disku jeden blok
dlouhý 128KB a každý soubor, který obsahuje třeba jenom jeden znak
zabírá celý blok). I když není počet bloků omezen, je volba jejich
velikosti problematická. Menší bloky přináší zpomalení a zvětší
alokační tabulky. Větší bloky sice zrýchlí ale zase zvýší režii
způsobenou zaokrouhlováním. Například na Ext2FS bloky velké 1KB jsou
o 20% pomalejší, než bloky o velikosti 4KB, přesto se ale bežně
používají právě kvůli úspoře místa, která je ale také sporná.
Jedno z řešení přinesl Fast Filesystém z FreeBSD. Ten umí
některé bloky rozdělit na menší fragmenty (0.5KB) kam ukládá konce
souborů a umí tak uložit více souborů do jednoho bloku. Toto řešení
přejímá hodně dalších filesystémů - například VivaFS a i Ext2FS má
v superblocku vynechané místo pro fragmenty, jako možné rozšíření.
Fragmenty ale přináší i své nevýhody - zvyšují fragmentaci,
komplikují kód atd. VivaFS ještě rozšířil tento způsob a umí uložit
konec souboru přímo do inody, pokud je tam na něj místo. Jiné
řešení má například extend based filesystém, který alokační tabulky
kompresuje a tak může používat malé bloky. ReiserFS používá cosi
jako fragmenty ale nemají pevnou velikost a tak šetří ještě více
místa. Navíc ukládá soubory přímo do adresářových položek.
Dalším problémem Inodových filesystému je omezení celkového
počtu souborů na disku. To samozřejmě v reiserFS také odpadá.
Posledním velkým problémem je pomalé handlování adresářů. Pokud
chcete otevřít soubor v adresáři obsahujícím 2000 souborů, musíte
všechny adresářové položky načíst a prohledat. To chvíli potrvá.
Jedno z řešení přinesla Amiga, která adresáře ukládá jako hashovací
tabulky. To umožňuje velmi rychlé vyhledání souboru v adresáři ale
zase přináší problémy s vypisováním adresářů, které je poměrně
pomalé. Jiný přístup jsou B stromy. To je datová struktura,
která umí velmi rychle vyhledávat. Klasické stromy fungují tak,
že data jsou uspořádány podle jednoduchého pravidla - prvky menší,
než aktuální jsou vlevo a větší jsou vpravo:
Linux
/ \
FreeBSD XeniX
/ \ /
DOS Hurd TOS
Pokud například chcete najít Hurd, postupujete následujícím
způsobem:
- začnete v kořeni (tedy Linux). Hurd je v abecedě před Linuxem
a je tedy menší - vydáte se doleva
- Vlevo je FreeBSD. Hurd je v abecedě později, vydáte se doprava
- A našli jste Hurd
B stromy jsou stromy optimalizované pro uložení na disk -
na každé úrovni není jenom jedna položka ale hned několik a vychází
i několik potomků tak, aby se jedna položka vešla pěkně do jednoho
bloku. Navíc se B stromy vyvažují, takže nedochází k degeneraci
(nestane se, aby všichni potomci byli nalevo a strom se zdegeneroval
na seznam). B stromy také zaručují, že všechny položky jsou z 1/2
plné.
Adresáře z B stromy mají následující vlastnosti
- Rychlé vyhledávání (v logaritmickém čase - pro 65536 souborů
potřebujete 16 porovnání
- Vytváření, mazání a přejmenovávání souboru také v logaritmickém
čase
- Alespoň 1/2 místa určená pro adresář bude použita
B stromy mají tak velké výhody pro práci z velkými adresáři, že
například MacOS používá filesystém, který má pouze jeden centrální
adresář, který obsahuje soubory z celou cestou. To ušetří dost
místa tím, že podadresáře nejsou krátké soubory a nezaokrouhlují se.
Nepřináší to žádné výrazné zpomalení - díky vlastnostem B stromů
jednotlivé podadresáře jsou uloženy pohromadě. Jde s nimi velmi
rychle pracovat a navíc jsou velmi rychlé operace procující s celým
adresářovým stromem, protože je celý uložen pohromadě.
ReiserFS se tímto přístupem inspiruje. Ale rozvádí ho ještě dál.
Do stromu neukládá pouze adresáře ale celé soubory. Jednotlivé
položky ve stromu jsou soubory a vyhledávací klíče jsou cosi jako
inody. To má opět zajímavé vlastnosti. Soubory se stejnými klíči
mají tendenci býl uloženy blízko sebe. Navíc se více souborů může
pospojovat do jednoho bloku v B stromu. Soubory delší než jeden
blok se potom ukládají do speciálních listů B stromů, na kterých
se už neprovádí vyvažování. Adresářové položky ale nejsou uloženy
v souborech, jako tomu bývá pod Inodovými filesystémy, ale také
do tohoto centrálního stromu.
Jeho stromy mají zajímavé vlastnosti. Například optimalizují
rozložení tak, aby udžovali lokalitu dat apod.
Výsledkem je velmi rychlý filesystém. Při práci s dlouhými
soubory jsou tu sice některé nedostatky (například uřezávání konce
souboru zhoršuje fragmentaci, ale FFS má stejný problém), ale přesto
ve smýšených testech většinou Ext2FS porazí.
Pro smýšený bechmark autor použil následující soubory:
+----------------+------------+------------------+
| počet souborů | velikost | celková velikost |
+----------------+------------+------------------+
| 5 | 0-10M | 33,712,005 |
| 21 | 0-1M | 9,335,273 |
| 113 | 0-100K | 6,193,394 |
| 615 | 0-10K | 3,055,154 |
| 3002 | 0-1K | 1,479,559 |
| 12244 | 0-100B | 610,149 |
+----------------+------------+------------------+
Zaplnění 506MB disku bylo následující:
ext2 reiserfs poměr
58% 43% 1.35
Náledující tabulka obsahuje vždy čase ve formátu:
ReiserFS,poměr k ext2FS(kolikrát je ReiserFS rychlejší)
1 - všechny soubory v jednom adresáři
2 - soubory v deseti podadresářích
2 - soubory v 100 podadresářích
2 - soubory v 1000 pod-podadresářích
+------------------------------+----------+----------+----------+----------+
| Akce | 1 | 2 | 3 | 4 |
+------------------------------+----------+----------+----------+----------+
|Vytvoření testovacích souborů | 4:31,26 |42.35,3.16|25.95,1.68|54.84,1.34|
|Vypsání všech souborů | 9:05,2.63| 5:11,1.44| 4:14,1.17| 5:05,1.27|
|Vytvoření záložní kopie |30:30,7.7 | 5:39,1.3 | 5:39,1.3 | 7:06,1.5 |
|Vypsání informací o souborech |15:23,26 | 2:37,4.2 | 1:29,2.08| 1:59,3.1 |
|Smazání testovacách souborů | 3:32,10 |56.17,2.5 |53.52,2.08| 1:58,4.0 |
+------------------------------+----------+----------+----------+----------+
Testy ukazují, že ReiserFS je často rychlejší, než Ext2FS. Zatím
výsledky nejsou definitivní - ReiserFS zatím neumí použít directory
cache a proto práce z adresáři je relativně pomalá, ale přesto
o sobě dávají B stromy vědět.
výheň