Co se vlastně stalo s chunkfs?

20. 7. 2009 | Jirka Bourek | Programování | 2641×

Chunkfs je princip návrhu souborových systémů, který má usnadnit a především zrychlit kontrolu a opravování diskových oddílů. Funguje tak, že souborový systém rozkouskuje a zabývá se jednotlivými částmi. Článek se zabývá popisem návrhu a implementací a popisuje měření výkonu.

Obsah

• Pozadí
• Návrh chunkfs
• Měření
• Implementace
• Výsledky
• Budoucí práce
• Závěry
• Poděkování

Originál tohoto článku pro LWN.net napsala Valerie Aurora (dříve Hensonová).

„Co se vlastně stalo s chunkfs?“ To je otázka, kterou slyším každých pár měsíců a pokaždé odpovídám stejně. „Chunkfs funguje, režie je rozumná a praktické je pouze v případě, že je součástí návrhu souborového systému od začátku, ne přilepeno dodatečně. Potřebuji jenom napsat článek, který shrne všechna data.“ Díky šéfredaktorovi LWN si nyní ten článek můžete přečíst.

Pozadí

Předtím, než popíšeme chunkfs, bychom měli mluvit o problémech, které vedly k jeho vytvoření. Chunkfs byl motivován rostoucími obtížemi s přečtením a modifikací všech dat potřebných k tomu, aby byl otestován celý souborový sytém. Jak kapacita úložných zařízení roste, kapacita zbytku systému pro čtení a ověření těchto dat nedrží s tímto růstem tempo. Výsledkem je, že doba testu „normálního“ souborového systémů roste, místo toho, aby zůstala stejná, což by bylo možné, kdyby paměť, propustnost, doba vyhledávání [seek time] v systému rostla úměrně s úložnou kapacitou. Různá tempa růstu v hardwaru – jako rozdíly mezi kapacitou RAM, propustnosti a latence – jsou částí toho, díky čemu je výzkum v oblasti systémů zajímavý.

K pochopení změny doby, která je potřeba k prověření a opravě souborového systému, je užitečná analogie porovnání růstu mojí knihovny (ano, někteří lidé stále vlastní knihy) s růstem mojí schopnosti číst, organizovat a najít knihy v této knihovně. Když jsem byla malá, všechny moje knihy se vešly na jednu poličku. Knihu, kterou jsem chtěla, jsem našla řádově v sekundách a každou jsem byla schopna přečíst za týden. Teď v dospělosti moje knihy zabírají několik polic (a navíc se hromadí na každém rovném povrchu). Umím číst mnohem rychleji, než když jsem byla dítě, lépe organizovat knihy, ale najít konkrétní knihu může zabrat několik minut a přečíst je všechny by mi zabralo rok nebo víc. Kdybych se pokoušela najít dvacetidolarovku, kterou jsem nechala v knize, trvalo by mi několik hodin prolistovat všechny knihy, než bych ji našla. I když jsem nyní lepší čtenář, moje knihovna rostla rychleji než moje schopnost číst nebo v ní něco hledat. A podobně jsou počítače rychlejší než kdy předtím, ale úložná kapacita rostla ještě rychleji.

Důsledkem tohoto fenoménu, který mě jako první zaujal, byla enormní nerovnost mezi dobou vyhledávání a kapacitou disku. Spočítala jsem odhad změny doby fsck z těchto předpovědí [PDF] od giganta v průmyslu úložných zařízení z roku 2006:

Zlepšení výkonnosti disků, 2006 – 2013
Kapacita:	16,0×
Propustnost:	5,0×
Doba vyhledávání:	1,2×
=> přinejmenším desetinásobný růst doby běhu fsck!

Od té doby se konečně stala realitou úložná zařízení založená na flash. Disky bez rotujících částí (SSD) mají v porovnání s běžnými disky mnohem lepší dobu vyhledávání, trochu lepší propustnost a drasticky sníženou kapacitu, takže výkonnost fsck by měla být extrémě dobrá. (Nejsem schopna najít žádné měření doby běhu fsck na SSD, ale odhadla bych, že to budou řádově sekundy. Někdo z čtenářů?) SSD nicméně neřeší všechny naše problémy. Zaprvé jsou SSD prvkem v hierarchii cache v systému, jsou vrstvou mezi systémovou RAM a diskem, ne kompletní náhradou za disky. Pozice SSD se budou nadále zlepšovat, ale i tak bude trvat několik let nebo desetiletí, než budou klasické pevné disky zcela eliminovány – podívejte se na historii pásek. Pro uživatele laptopu je jednoduché zamávat rukama a říct „disky jsou pasé“, ale zkuste to říct Googlu, správci vašeho e-mailového serveru nebo dokonce vašemu MythTV stroji.

Za druhé nezapomeňme na to, že důvodem našeho zabývání se fsck je především to, že souborové systémy se občas poškodí. Jedním z důležitých zdrojů poškození souborového systému jsou selhání samotného úložného hardwaru. Zeptejte se jakéhokoliv výrobce SSD o četnosti poškození jeho hardwaru a oni vás zaplaví rovnicemi, laboratorními měřeními a simulacemi, které ukazují, že flash paměti v jejich SSD se nikdy neopotřebují při „normálním“ používání – ale přitom vám neprozradí žádné detaily o svých algoritmech vyrovnávání opotřebení nebo typech zátěže, podle kterých své předpovědi vytvořili. Výsledkem je, že ve skutečném světě se setkáváme s překvapeními, jak co se týče výkonnosti, tak co se týče spolehlivosti. Pokud jde o četnost selhání, dobré statistiky ještě nemáme, takže se musím spokojit se svými zkušenostmi a zkušenostmi kolegů jaderných hackerů. V praxi vidíme, že u SSD dochází k poškození mnohem častěji a rychleji než u disků, přičemž v takovém případě chyby nejraději sežerou nejchutnější a nejdůležitější části souborového systému. Můžete klidně věřit výrobcům hardwaru, když vám mávají a říkají, abyste si nelámali hlavičku, ale já osobně budu víc věřit penězům, které jsem si vydělala při konzultacích pro lidi s poškozenými SSD.

Jestliže tedy máme obavy z poškození souborového systému, důležitým ziskem z přístupu chunkfs je pro nás to, že poškození souborového systému je obvykle omezeno na jeho malou část bez ohledu na to, co je zdrojem poškození. Několik dalších principů souborových systémů zaměřených na opravování – jako je duplikace důležitých dat a počítání jejich kontrolních součtů – ještě zvyšuje pravděpodobnost obnovy dat po poškození. Takže jestliže vás doba běhu fsck nezajímá, protože hodláte po zbytek života používat SSD, můžete i tak číst dále, protože vám bude záležet na tom, abyste z SSD data získali zpět.

Závěr, ke kterému jsem dospěla, je, že souborové systémy by měly být odpočátku navrhovány s cílem poskytovat rychlé a spolehlivé testování a opravu. Některé z užitečných metod k dosažení tohoto cíle jsem zvýraznila v krátkém pojednání: Návrh souborových systémů zaměřených na opravování [PDF].

Návrh chunkfs

Chunkfs je nemelodické jméno pro takovou architekturu souborového systému, která je navržena s předpokladem, že v nějakém okamžiku bude souborový systém poškozen. Formát na disku tedy není optimalizován pouze pro výkonnost při normálním běhu, ale také pro rychlou a spolehlivou kontrolu. Základním konceptem chunkfs je, že jediný logický souborový systém je zkonstruován z několika jednotlivých souborových systémů (dílů [chunks]), z nichž každý lze otestovat a opravit individuálně.

To je skvělé, ale nyní máme stovku malých souborových systémů a jmenný prostor a prostor na disku je mezi nimi fragmentován – to lze těžko považovat za zlepšení. Pokud bychom například měli 100GB souborový systém rozdělený na 100 1GB velkých dílů a chtěli na něm vytvořit 2 GB velký soubor, nevešel by se do jednoho dílu – je potřeba ho nějak sdílet mezi několika. Jak tedy slepíme všechny díly zpátky dohromady, abychom mohli sdílet jmenný prostor i místo na disku, ale zároveň zachovali možnost testovat a opravit každý díl jednotlivě? Co potřebujeme, je způsob, jakým spojit soubor nebo adresář v jednom dílu a soubor nebo adresář v jiném dílu takovým způsobem, že spojení bude možné rychle a snadno ověřit a opravit bez plného fsck zbytku dílu. Řešením je něco, co jsme nazvali „pokračující [continuation] inode“. Pokračující inode „pokračuje“ soubor či adresář do dalšího dílu.

Určitě si všimnete, že na obrázku jsou dvě šipky, jedna ukazuje z původního inode na pokračující, druhá zpět z pokračujícího na původní. Když se testuje druhý díl, lze rychle otestovat platnost pokračujícího inode použitím zpětného ukazatele k vyhledání původního inode v jeho dílu. Toto je test „mezidílových odkazů“ – jakýchkoliv metadat souborového systému, která vytvářejí spojení mezi daty v dvou různých dílech. Mezidílové odkazy musí vždy mít dopředné a zpětné ukazatele, aby je bylo možné ověřit s počátkem v obou dílech.

Mezidílové odkazy musí splňovat jeden požadavek: Musíte být schopni rychle nalézt všechny křížové odkazy z dílu A do libovolného dílu B bez nutnosti prohledat celý díl A. Abychom viděli, proč je to nutné, podíváme se na příklad: Díl A má inode X, který je pokračován do dílu B. Co když bude díl A poškozen takovým způsobem, že inode X bude zcela ztracen? Dokončili bychom testování a opravu dílu A, který by tak byl interně konzistentní, ale díl B by stále obsahoval pokračující inode pro X, který by nyní nebylo možné vyhledat či smazat – sirotčí pokračující inode. Druhý krok testování dílu A je tedy nutně vyhledání všech odkazů na díl A z dílu B (a všech ostatních dílů) a ověření, jestli souhlasí. Pokud bychom nemohli, bylo by nutné prohledat všechny ostatní díly v souborovém systému, abychom otestovali jediný díl – a to není rychlé.

Souborový systém ve stylu chunkfs lze testovat a opravit inkrementálně a za běhu, zatímco většina souborových systémů musí být testována naráz a nepřipojena. Z tohoto pravidla existují výjimky jako je BSD FFS test za běhu založený na snímcích [snapshot] a mechanismus samoléčení NTFS za běhu, ale tyto možnosti jsou většinou přidávány dodatečně a jsou vážně omezeny, co se jejich rozsahu týče. Pokud například testování za běhu v BSD nalezne chybu, souborový systém musí být opraven odpojený obvyklým způsobem, což zahrnuje opětovné spuštění testovací fáze fsck.

Návrh chunkfs vyžaduje řešení několika složitých problémů, přičemž v tomto článku není místo pro jejich popis, ale můžete si o nich přečíst v našem pojednání Chunkfs: Jak použít rozděl a panuj ke zlepšení spolehlivosti a opravitelnosti souborového systému [PDF] pro Horká témata spolehlivosti z roku 2006.

Měření

Návrh souborových systémů zaměřených na opravování, konkrétně chunkfs, zní jako hezký nápad, ale jako vývojářka souborových systémů jsem měla spoustu hezkých nápadů, u nichž se ukázalo, že není možné je implementovat nebo že mají příliš velkou režii na to, aby je bylo možné prakticky použít. Otázky, které bylo potřeba zodpovědět u chunkfs byly: Lze to udělat? A pokud to lze udělat, převáží režie pokračujících inodů přínosy? Konkrétně potřebujeme porovnat čas, který zabere test jednotlivého dílu s časem, který zabere testování jeho spojení s ostatními díly (tj. ujištění se, že všechny dopředné a zpětné ukazatele pokračujících inodů souhlasí se svými protějšky v druhém dílu). Nejprve se blíže podívejme na dobu testu souborového systému chunkfs.

Čas potřebný k testu a opravě souborového systému s jedním poškozeným dílem je součtem dvou různých komponent: Času pro interní test dílu a času pro test křížových odkazů z a na tento díl.

T_fs = T_díl + T_křížové

Čas testu jednoho dílu je funkcí velikosti dílu a velikost dílu je celková velikost souborového systému dělená počtem dílů.

T_díl = f(velikost_díl)

velikost_díl = velikost_fs / n_dílů

Čas testu mezidílových odkazů z tohoto a na tento díl závisí na počtu takových odkazů. Přesný počet mezidílových odkazů se bude lišit, ale obecně budou mít větší díly méně křížových odkazů a menší díly více odkazů – tzn. čas testu odkazů poroste s tím, jak poroste počet dílů.

T_křížové = f(n_dílů)

Čas testu dílu tedy klesá s tím, jak dělíme souborový systém na menší díly, ale zároveň s tím roste doba testu mezidílových odkazů. Navíc s tím, jak roste počet dílů, roste i dodatečné místo na disku spotřebované pokračujícími inody stejně jako režie způsobená vyhledáváním pokračujících inodů při normální práci. My přitom chceme najít ideální kompromis, kde bude součet obou časů minimální a zároveň režie způsobená pokračujícími inody malá.

Existuje takový bod? Odpověď záleží na rozvržení souborů a adresářů ve skutečném světě – pokud budou mezidílové odkazy extrémně běžné, režie pokračujících inodů převáží přínosy. Přišli jsme s jednoduchým způsobem, jak odhadnout počet mezidílových odkazů v souborovém systému chunkfs: Vezme se „skutečný“ používaný souborový systém ext3 a pro každý soubor se změří počet skupin bloků, které obsahují data tohoto souboru. Poté se pro každý adresář měří počet skupin bloků obsahujících soubory v tomto adresáři. Pokud sečteme počet skupin bloků mínus jedna pro všechny soubory a adresáře, dostaneme počet mezidílových odkazů v podobném souborovém systému chunkfs o velikosti skupin bloků souborového systému ext3 (detaily zde).

Karuna Sagar napsal nástroj nazvaný cref pro měření těchto křížových odkazů a já přidala nějaký kód pro odhad nejhoršího případu doby testu křížových odkazů (za předpokladu jednoho vyhledávání [seek] na křížový odkaz). Výsledky byly povzbudivé; za předpokladu, že se hardware bude vyvíjet podle předpovědí, průměrný čas testovování mezidílových křížových odkazů bude roku 2013 kolem pěti vteřin a nejhorší případ by v takovém případě byl okolo 160 vteřin (přibližně 2,5 minuty.). To platí pro velikost dílu 1 GB, takže doba testu dílu jako takového by byla pár sekund. Tento odhad je nejhorší ještě v jednom ohledu: Alokátor ext3 není nijak optimalizován k tomu, aby omezoval mezidílové odkazy. Souborový systém ve stylu chunkfs by měl mnohem vhodnější alokátor.

Implementace

Prototyp chunkfs vznikl třikrát. První prototyp, který napsal Amit Gud jako svou diplomovou práci [PDF] v letech 2006-2007, implementoval chunkfs jako modifikaci ovladače ext2 ve FUSE. Všimněte si, že návrh chunkfs popsaný v této práci je v některých ohledech zastaralý, nejnovější verzi vizte v pojednání o chunkfs [PDF]. Amit také implementaci v polovině roku 2007 jen tak pro zábavu portoval do jádra. Výsledky byly povzbudivé. Naší hlavní obavou bylo, že pokračující inody se budou divoce množit, čímž zlikvidují veškeré přínosy. Ve skutečnosti ovšem tyto inody byly relativně vzácné – objevily se u 2,5 % ze všech souborů na souborovém systému a žádný soubor neměl více než 10 pokračujících inodů. Testovací zátěž obsahovala simulaci stárnutí systému opakovaným mazáním souborů při zaplňování zbytku testovacího souborového systému (Bylo by zajímavé vidět výsledky z použití Impressions [PDF], což je velmi sofistikovaný nástroj pro generování realistických obrazů souborových systémů.)

Tyto implementace byly dobrým počátečním krokem, ale byly založeny na starších verzích návrhu chunkfs předtím, než jsme vyřešili důležité problémy. V těchto implementacích bylo potřeba testovat všechny díly, do kterých se od připojení zapisovalo. Vzhledem k tomu, že při běžném používání je většina souborového systému neaktivní, doba kontroly se v testovacích případech snížila o 2/3, ale my se zde nesnažíme o trojnásobné zlepšení, ale stonásobné. Také chyběl způsob, jak najít všechny odkazy na konkrétní poškozené díly, takže se testovaly pouze odkazy vedoucí z tohoto dílu ven. Používala se stará verze řešení pevných odkazů, kde bylo možné selhání při vytváření pevného odkazu v situaci, kdy v cílovém dílu došlo místo, namísto toho, aby se vytvořilo pokračování do dílu, kde místo bylo. Byl to první krok, ale postrádal klíčovou vlastnost: Drasticky omezenou dobu opravy souborového systému.

V polovině roku 2007 jsem se rozhodla napsat prototyp chunkfs jako vrstveného souborového systému, podobně jako unionfs nebo ecryptfs, který by byl zcela nezávislý na klientském souborovém systému použitém v každém dílu. Pokračující inody jsou implementovány jako běžné soubory, které pro ukládání s pokračováním spojených metadat (dopředné a zpětné ukazatele a posun a délka souboru uloženého v pokračujícím inode) používají rozšířené atributy. Když data souboru překročí zvolenou velikost (v mém prototypu 40 k), je v dalším dílu alokován pokračující inode a data od daného místa v souboru dále jsou alokována v datech tohoto inodu. Všechny pokračující inody vycházející z konkrétního dílu jsou drženy v jednom adresáři, takže je lze rychle prohledat v mezidílové fázi fsck.

Abych ověřila, že je prototyp schopen se obnovit při poškození souborového systému na jednom dílu bez testu celého souborového systému, implementovala jsem jednoduchý shellový skript. Ten nejprve provede fsck poškozeného dílu spuštěním fsck z ext2. To může skončit smazáním nebo přesunem libovolných souborů v dílu, čímž se díl může desynchronizovat oproti ostatním. V druhé fázi skript připojí nyní opravené souborové systémy a čte jejich adresáře /chunks, aby našel všechna spojení do poškozeného dílu a ověřil jejich konzistenci. Když najde osiřelé pokračování – pokračování, jehož původní inode v poškozeném dílu byl zničen nebo ztracen – smaže pokračující inode.

Testovací skript fsck má nedostatek v jednom konkrétním ohledu: Testuje všechny díly, protože jsem nenapsala kód, který by označil díl jako poškozený. To je obecně obtížný problém; někdy víme, že byl díl poškozen, protože disk ohlásil chybu při I/O nebo jsme při používání souborového systému narazili na nekonzistenci; pak můžeme označit souborový systém za poškozený a vyžadující fsck. Nicméně mnoho druhů poškození je tichých – jak přijít na to, které díly byly v tichosti poškozeny? Nemůžeme, ale můžeme díly tiše „gruntovat“ jejich testováním na pozadí. V současnosti ext2/3/4 spouští paranoidní fsck každých N připojení nebo M dní od posledního testu. To bohužel zavádí neočekávaná řádově minutová či hodinová zpoždění při bootu; pokud máte štěstí, stihnete si před dokončením dát šálek kávy; když máte smůlu, budete zjišťovat, jak to zakázat, zatímco vás budou pozorovat všichni, kteří byli na vaší přednášce o použitelnosti Linuxu. (Pište si: Restartuje a na příkazovou řádku jádra přidejte „fastboot“.) S chunkfs bychom mohli spouštět fsck při každém bootu, čímž by se k době bootování pokaždé přidalo několik vteřin, ale zamezilo by se příležitostným dlouhým zpožděním. Také bychom mohli testovat neaktivní díly na pozadí, i když se bude souborový systém používat.

Výsledky

V lednu 2008 jsem o chunkfs měla přednášku na LCA, která zahrnovala i živé předvedení konečného prototypu chunkfs v akci: Vytváření souborů, jejich pokračování do dalšího dílu, úmyslné poškození dílu a oprava souborového systému. Protože jsem si pečlivě připravila jako zálohu typescript pro případ, že by se něco nepovedlo, demo proběhlo perfektně. K dispozici je video z přednášky [Ogg Theora].

Mějte na paměti, že jsem se nikdy nedonutila k tomu, abych tuto přednášku shlédla, takže nevím, jestli neobsahuje nějaké trapné chyby. Pokud chcete, můžete společně s předvedením sledovat výstup dema s poznámkami.

Přístup „sbírka souborových systémů“ byl nakonec složitější, než jsem doufala. Prototyp používal pro jednotlivé díly souborový systém ext2 – rozumná volba pro kód, který má být vyhozen, ale nepoužitelné pro produkční nasazení. Jakmile však přejdete na jakýkoliv spolehlivější souborový systém, máte pro každý díl jeden žurnál, což představuje značnou režii. Krom toho se zdálo pravděpodobné, že budeme potřebovat další žurnál pro obnovení po pádu během mezidílových operací. Dalším zdrojem složitostí bylo použití vrstveného souborového systému – ve zkratce, když chunkfs komunikuje s VFS, předstírá, že je klientským souborovým systémem, kdežto když komunikuje s tímto souborovým systémem, předstírá, že je VFS. Vzhledem k tomu, že nic z toho není oficiálně podporováno, končí to dlouhým seznamem hacků a obcházení problémů a je tedy jednoduché narazit na překvapivé chyby související s čítáním odkazů nebo zamykáním. Ve shrnutí tento přístup fungoval pro prototyp, ale nezdálo se, že má cenu investovat do něj čas, aby dosáhl kvality pro dodávání, obzvláště s úsvitem btrfs.

Budoucí práce

Když jsem začala pracovat na chunkfs, budoucnost souborových systémů v Linuxu vypadala neutěšeně. Jaderný prototyp chunkfs se zdál být jedinou praktickou cestou, jak dostat návrh zaměřený na opravování mezi linuxové souborové systémy. To vše se teď změnilo; vývoj souborových systémů je populární a dobře financovaná aktivita a Linux má slibný souborový systém budoucí generace (btrfs), který implementuje mnoho z principů souborových systémů zaměřených na opravování, včetně kontrolních součtů, kouzelných čísel a redundantních metadat. Chunkfs posloužil svému účelu jako demonstrace síly takových souborových systémů a nemám pro něj další vývojové plány.

Závěry

Tři prototypy chunkfs a naše odhady mezidílových odkazů používaných v reálném světě ukázaly, že architektura chunkfs funguje tak, jak bylo tvrzeno. Prototypy nás také přesvědčily, že by bylo složité přizpůsobit existující žurnálovací souborové systémy architektuře chunkfs. Vlastnosti, které zajišťují kontrolu a opravu souborového systému, fungují nejlépe, když jsou do architektury daného souborového systému navrženy od počátku. Btrfs je příklad souborového systému navrženého od začátku s cílem mít rychlou a spolehlivou kontrolu a opravování.

Poděkování

Při návrhu a prototypování chunkfs štědře pomohlo mnoho lidí a organizací. Arjan van de Ven je spoluvynálezce původní architektury chunkfs. Theodore Ts'o a Zach Brown poskytovali neocenitelné rady a kritiku, když se řešily detaily. Od účastníků workshopu Horká témata spolehlivosti jsme měli cennou zpětnou vazbu a podporu. Karuna Sagar napsal nástroj pro měření křížových odkazů, který nám poskytl důvěru, abychom s implementací pokračovali. Amit Gud jako postgraduální student Kansas State University napsal dva prototypy. Vývoj třetího prototypu byl v různých stádiích financován firmami Intel, EMC a VAH Consulting. A nakonec příliš velká spousta lidí na to, aby je zde bylo možné vyjmenovat, pomáhala v diskuzích o chunkfs v mailových konferencích a já jim velmi děkuji za pomoc.

       

Komentáře

[Jackie Chan]

Postne niekto link na originalny clanok? Nejak som ho na LWN.net nemohol najst :(

[progdan]

http://lwn.net/Articles/337680/

[Robert Krátký]

Link je celou dobu pod "Odkazy a zdroje"

[Petr Tomášek]

Tak teda kdybych netušil, co tam asi bylo v originále, tak bych naprosto nepochopil, že tu je řeč o „produkční kvalitě“...

[geebranz]

Looks good

www.metalbuildingsabilenetx.com