Featherstitch: Zabij fsync() něžně

9. 11. 2009 | Jirka Bourek | Programování | 2623×

Stehování [Featherstitch] je zobecnění systému závislostí zápisů a zpětného přehrání [rollback] dat měkkých aktualizací. Výsledný systém je dostatečně obecný na to, aby nad jeho rozhraním mohla být implementována většina (možná všechny) strategií zajišťujících konzistenci souborového systému (např. žurnálování).

Obsah

• Stehování – základy: patche, závislosti a data pro vzetí zpět
• Optimalizace
• Výkonnost
• Skupiny patchů: Stehování pro uživatelský prostor
• Závěr

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

Měkké aktualizace, což je metoda udržování konzistence souborového systému na disku pomocí pečlivého řazení zápisových operací, byly na produkčním operačním systému (FreeBSD) implementovány pouze jednou. Lze se dohadovat o tom, proč nebyly implementovány jinde, konkrétně v Linuxu, ale moje teorie je, že na světě není tolik geniálních vývojářů souborových systémů, aby bylo možné napsat a spravovat víc než jednu instanci měkkých aktualizací. Chris Frost, student na UCLA, s teorií „příliš komplikované pro pouhé smrtelníky“ souhlasí, to je důvod, proč s několika spoluspiklenci napsal systém Featherstitch [Stehování] pro udržování konzistence dat na disku.

Stehování [Featherstitch] je zobecnění systému závislostí zápisů a zpětného přehrání [rollback] dat měkkých aktualizací. Výsledný systém je dostatečně obecný na to, aby nad jeho rozhraním mohla být implementována většina (možná všechny) strategií zajišťujících konzistenci souborového systému (např. žurnálování). Mezi technikami pro udržování konzistence souborového systému je přitom unikátní, protože aplikacím v uživatelském prostoru poskytuje bezpečný, efektivní a neblokující mechanismus, který umožňuje seskupovat a řadit zápisy bez používání fsync() nebo spoléhání se na chování specifické pro souborový systém (například režim data=ordered u ext3).

Stehování – základy: patche, závislosti a data pro vzetí zpět

Co je Stehování kromě toho, co vám vmetou do tváře nadšenci pro souborové systémy, když si stěžujete, že jsou měkké aktualizace příliš složité? Stehování vzešlo z měkkých aktualizací a s jejich přístupem má architekturou mnoho společného. Hlavní rozdíl mezi ním a měkkými aktualizacemi je v tom, že to druhé implementuje každou operaci souborového systému individuálně s různými sadami datových struktur specifických pro souborový systém FFS. Stehování naopak zobecňuje koncept sady aktualizací různých bloků a vytváří jednu datovou strukturu a jeden mechanismus řešící zápis, které sdílí všechny operace souborového systému. Výsledkem je, že Stehování lze pochopit a implementovat snáze než měkké aktualizace.

Stehování zaznamenává všechny změny souborového systému do „patchů“ (nedostatek původní terminologie ve vývoji softwaru znovu útočí). Patch zahrnuje číslo bloku, spojový seznam patchů, na kterých tento patch závisí, a „data pro vzetí zpět“. Tato data jsou diff změn na úrovni bytů, které tento patch vyvolá na daném bloku, včetně pozice, délky a obsahu rozsahu bytů přepsaných touto změnou. Jiná verze patche je optimalizována pro změny, které mění jednotlivé bity, například ty, které se dělají na bitmapě bloků. Pravidlo pro zapisování patche na úložiště je jednoduché: Jestliže u kteréhokoliv z patchů, na kterých tento patch závisí – jeho závislosti – ještě není potvrzeno, že je zapsán na disku, nelze tento patch zapsat.

Jinými slovy patche a závislosti jsou velmi podobné obecnému orientovanému acyklickému grafu [generic directed acyclic graf, DAG], kde jsou patche uzly a závislosti hrany – programátoři takových obrázků pravděpodobně ve svém životě nakreslili stovky či tisíce. Jenom si tedy představte, že z každého uzlu visí malý diff a máte dobrý myšlenkový model pro to, jak přemýšlet o Stehování. Zajímavé kousky se soustřeďují okolo omezení počtu malých smyček – v první implementaci byla velikost paměti, kterou Stehování spotřebovávalo pro data pro vzetí zpět, často dvojnásobkem velikosti dat zapisovaných na disk. Například rozbalení stromu zdrojových kódů jádra o velikosti 220 MB alokovalo přibližně 460 MB dat pro vzetí zpět.

Acyklicita závislostí patchů si zasluhuje o trochu více pozornosti. Na prvním místě je potřeba říci, že vyhnout se vytvoření kruhových závislostí patchů je na zodpovědnosti volajícího; Stehování je nedetekuje a ani se je nepokouší opravit. (Zjednodušené rozhraní exportované do uživatelského prostoru úplně znemožňuje vytvoření cyklů, o tom více později.) Nemožnost vytvořit kruhové závislosti mezi patchi nicméně neznamená, že není možné vytvořit cyklické závislosti mezi bloky. Patch je záznamem o změně bloku a pro každý blok může existovat více současně platných patchů. Představte si závislosti patchů takové, že patch A závisí na patchi B, který závisí na C. To je A->B->C, kde se „->“ čte jako „závisí na“. Jestliže se patch A bude aplikovat na blok 1, patch B na blok 2 a patch C také na blok 1, pak pohled na bloky a jejich existující patche jako celek nám ukazuje, že máme kruhovou závislost, kde blok 1 musí být zapsán před blokem 2, ale zároveň musí být blok 2 zapsán před blokem 1. To se nazývá „zacyklení na úrovni bloků“ a u systémů založených na řazení zápisů je to nejčastější příčina bolestí hlavy.

Jak Stehování, tak měkké aktualizace řeší cykly na úrovni bloků tak, že uchovávají o každé změně dost informací, aby ji mohly vzít zpět. Když dojde na zápis bloku, jsou všechny na něj aplikované patche, které nelze zapsat hned (protože jejich závislosti ještě nebyly zapsány), odvolány využitím dat pro vzetí zpět. V našem případě, kde se u A->B->C A i C aplikují na blok 1, se na bloku 1 odvolá změna A, blok 1 se zapíše s aplikovaným patchem C, pak se zapíše blok patche B a nakonec se znovu zapíše blok 1 s aplikovanými patchi A i C.

Optimalizace

První verze Stehování byla elegantní, všeobecná, snadno pochopitelná a výjimečně neefektivní. Při některých benchmarcích původní implementace alokovala pro patche a data pro vzetí zpět více než dvojnásobek dat, než bylo potřeba pro samotná data. Systém narazil na omezení procesorem při pouhých 128 blocích v cache bufferů.

Prvním cílem bylo zmenšit počet patchů potřebných k dokončení operace. V mnoha případech patch nikdy není brán zpět – pokud například zapisujeme do datového bloku souboru, když v souborovém systému neprobíhají jiné zápisy, není důvod, proč by kdy mělo být potřeba se vracet zpět k původní verzi bloku. V tomto případě Stehování vytváří „tvrdý patch“ – patch, který neobsahuje žádná data pro vzetí zpět. Další optimalizací je sloučení patchů, pokud je vždy možné je zapsat dohromady bez porušení jakýchkoli závislostí. Třetí optimalizace v některých případech slučuje překrývající se patche. Všechny tyto techniky pro snížení počtu patchů závisí na pravidlech pro vytváření patchů a závislostí, konkrétně na tom, že závislosti patche musí být specifikovány při jeho vytvoření. Některé příležitosti pro slučování lze odhalit při vytvoření patche, jiné když je patch aplikován a odstraněn z fronty.

Dalším významným cílem bylo efektivně najít patche připravené k zápisu. Normální cache bufferů obsahuje několik set tisíc bloků, takže jakékoliv datové struktury a algoritmy týkající se bloku musí být extrémně efektivní. Za normálních okolností musí cache bufferů v podstatě procházet seznam špinavých bloků a rozumně optimálním způsobem je zapisovat. Se Stehováním je možné najít špinavý blok, ale pak je potřeba projít jeho seznam patchů a zjistit, jestli některé z nich mají vyřešené závislosti, a tudíž je možné je zapsat. Tento seznam patchů může být dlouhý a může se ukázat, že žádné z patchů není možné zapsat, v takovém případě je potřeba se vzdát a přejít k dalšímu patchi. Místo náhodného prohledávání cache proto Stehování udržuje seznam patchů, které je možné zapsat, a když je patch aplikován, prohledá se seznam patchů, které na něm závisely. Ty, které nyní již zapsat lze, jsou pak přidány do seznamu k zapsání.

S těmito optimalizacemi paměťová režie Stehování klesla z 200 %+ na 4-18 % v sadě benchmarků, které se používaly pro hodnocení – stále je to dost, ale již je to v praktických mezích. Optimalizace popsané výše byly v některých případech implementovány pouze částečně, takže je zde stále místo pro zlepšování bez vymýšlení nových nápadů.

Výkonnost

Pro výkonnostní souboj muže proti muži autoři implementovali několik variant udržování konzistence souborového systému s rozhraním patche Stehování a porovnali je s ekvivalenty ext2 a ext3. Při použití formátu na disku ext2 reimplementovali měkké aktualizace, žurnálování pouze metadat a plné žurnálování dat i metadat. Žurnálování pouze metadat odpovídá režimu data=writeback u ext3 (data souboru jsou zapsána bez ohledu na stav metadat souborového systému, která na něj ukazují) a plné žurnálování odpovídá režimu data=full (všechna data jsou společně s metadaty zapsána přímo do žurnálu).

Použitý benchmark bylo rozbalení přibližně 200 MB velkého tar souboru (pochopitelně zdrojový kód jádra), výmaz výsledků předchozího běhu, spuštění Postmarku a modifikovaný benchmark Andrew file system – jinými slovy obvyklá směska otřesných, nekompletních a nereprezentativních benchmarků souborového systému, které používáme vždycky, protože nic lepšího není. Tyto nedostatky se projevují: S touto zátěží se ext3 choval přibližně stejně v režimech data=writeback i data=ordered (což se na systémech z reálného světa obvykle nestane), což je jeden z důvodů, proč autoři neimplementovali s pomocí Stehování režim ordered. Celkový výsledek měření výkonnosti je takový, že implementace pomocí Stehování byly vyrovnané nebo o něco lepší než srovnatelná verze ext3, co se doby běhu týče, ale využívaly přitom podstatně více času CPU.

Skupiny patchů: Stehování pro uživatelský prostor

Stehování tedy můžete použít k reimplementování všech druhů schémat udržování konzistence souborového systému – měkkých aktualizací, kopírování při zápisu, žurnálování všech příchutí – a bude to fungovat přibližně stejně rychle jako stará verze s tím, že se bude víc využívat CPU. Vzhledem k tomu, že v btrfs máte významné nové vlastnosti, jako jsou kontrolní součty a snímky [snapshot], je těžké nějak se vzrušovat nad skrytou reimplementací vnitřností souborového systému. Je to hezké, ale kromě vývojářů souborového systému to nikoho zajímat nebude, co?

Podle mě není nejlepší uplatnění Stehování v jádře, ale v uživatelském prostoru. Ve zkratce – Stehování exportuje aplikacím rozhraní, kterým mohou dosáhnout takových výsledků, co se konzistence na disku týče, jakých chtějí, A ZÁROVEŇ zachovat většinu výkonnostních výhod, které přicházejí se změnou řazení a zpožďováním zápisů. V současnosti mají aplikace jenom dvě praktické možnosti, jakými lze ovládat pořadí změn v souborovém systému: Čekat na dokončení všech zápisů použitím fsync(), nebo spoléhat na implementační detaily specifické pro souborový systém, jako je režim data=ordered v ext3. Stehování vám dává třetí možnost: Popsat přesné a minimální řadící vztahy mezi různými zápisy do souborového systému a pak nechat jádro měnit pořadí, zpožďovat a jinak optimalizovat zápisy v takovém rozsahu, který daná omezení umožňují.

Rozhraní pro uživatelský prostor je nazýváno „skupiny patchů“ [patchgroups]. Rozhraní předchází dvěma nevýhodám, které jsou obvykle spojeny s exportováním mechanismů pro udržování konzistence z jádra do uživatelského prostoru. Za prvé brání deadlockům způsobeným cyklickými závislostmi („Hej, jádro! Zápis A závisí na zápisu B! Jo, a zápis B závisí na zápisu A! Hezký den!“) V jádře lze chybné použití rozhraní prohlásit za chybu, ale pokud by závislostí zkazila aplikace, celé jádro by se zaseklo. A za druhé brání aplikaci brzdit své či cizí zápisy tím, že otevře transakci a udržuje ji otevřenou donekonečna a přitom do ní přidává nové změny (nebo spadne do nekonečné smyčky nebo spadne úplně nebo z jiného důvodu nedokáže své změny zabalit do úhledného balení).

Rozhraní skupin patchů jednoduše říká, že všechny tyto zápisy musí být na disku předtím, než je možné začít zapisovat jiné zápisy. Jakékoliv jiné zápisy, které probíhají mimo zápisy zmíněné, mohou být řazeny libovolně a zápisy uvnitř sady také nejsou vzájemně řazeny. Zde je příklad v pseudokódu, kde se skupina patchů používá:

/* Atomická aktualizace souboru použitím skupin patchů */

/* Vytvoří se skupina patchů, která sleduje vytvoření nové kopie souboru */
copy_pg = pg_create();

/* Řekne se jí, aby sledovala změny souborového systému do volání pg_disengage() */
pg_engage(copy_pg);

/* Otevře se zdrojový soubor, vygeneruje se jméno dočasného souboru atd. */

/* Dočasný soubor se vytvoří */
temp_fd = creat();

/* Z původního souboru se zkopírují data a provedou se změny */

/* Všechny změny jsou hotovy, nyní se tato skupina patchů zabalí */
pg_disengage(copy_pg);

Dočasný soubor nyní obsahuje novou verzi souboru a všechny s tím spojené změny souborového systému jsou součástí současné skupiny patchů. Nyní budeme chtít vložit následující rename() do oddělené skupiny patchů, která závisí na skupině patchů obsahující novou verzi souboru.

/* Pro rename() se vytvoří nová skupina patchů */
rename_pg = pg_create();

pg_engage(rename_pg);

/*
	* ZDE SE DĚJE KOUZLO: Tady říkáme souborovému systému, že 
	* rename() se nesmí projevit na disku, dokud nejsou uloženy 
	* změny v dočasném souboru. Pokud bychom neměli skupiny patchů,
	* použili bychom zde místo nich fsync(). fsync() lze také 
	* považovat za:
	* 
	* pg_depend(všechny předchozí zápisy do tohoto souboru, this_pg);
	* pg_sync(this_pg);
	*/

/* Nová skupina patchů (rename_pg) závisí na skupině patchů copy_pg */
pg_depend(copy_pg, rename_pg);

/* Toto rename() se stane součástí skupiny patchů rename_pg */
rename();

/* Vše připraveno! */
pg_disengage(rename_pg);

/* Úklid. */
pg_close(copy_pg);
pg_close(rename_pg);

Ve zkratce: Už žádná další chyba fsync() ve Firefoxu, O_PONÍCI pro každého, kdo nějakého chce, a za velmi malou cenu pro ty, kdo je nechtějí.

Závěr

Stehování je zobecnění a zjednodušení měkkých aktualizací s rozumnou, ale ne hvězdnou výkonností a režií. Skutečně zazáří, když dojde na exportování užitečného a bezpečného rozhraní pro řazení zápisů aplikacím v uživatelském prostoru. Nahrazuje enormní a výkonnost ničící kladivo fsync() minimálním a elegantním mechanismem pro řazení a seskupování zápisů.

Když dojde na samotné pojednání o Stehování, doporučuji přečíst si ho celé jednoduše kvůli stručnému a přitom přesnému shrnutí složitých záležitostí týkajících se ukládání. Někdy z toho mám pocit, že čtu vydestilované tři hodiny na Linux Storage and File Systems Workshop spojené s několika dalšími týdny diskuzí v mailových konferencích, to vše v jednom odstavci. Například sekce 7 mimořádně pregnantně popisuje možnosti, jak korektně zapsat zápisovou cache disku včetně specifických příkazů, jak pro SCSI, tak pro ATA, a stručné shrnutí kvality podpory těchto příkazů v hardwaru.

       

Komentáře

[Ladicek]

kde jsou patche smyčky a závislosti hrany

Nejsou ty patche spíš uzly?

[aubi]

Tady se primlouvam za opravdu urychlene nahrazeni vyrazu smycka slovem uzel (ma-li to byt vtipne, tak treba uzlik). Napsat, ze jde o acyklicky graf, kde jsou smycky, to je hodne pritazene za vlasy. Zrovna v grafech ta terminologie existuje.

[Petr Zelenka]

Ano, ano! Musel jsem nalistovat originál abych se ujistil, že nejsem úplně mimo takhle večír :)

[David Jaša]

ale pokud by závislostí zkazila aplikace

To í mi tam nějak nesedí.

[Jirka P]

To víš, když ty aplikace (nebo kdo vlastně) dneska tak chlastaj...

[petr_p]

A já si vnucoval představu, že se jedná o smyčku, tedy o cyklus délky 1 (A→A), kde patch je nálepka na hraně. Opravte to, prosím, jinak to nedává smysl.

[Semo]

V originale sa bavia o "circles and arrows". Akonahle sa sipky prekladaju grafarsky na hrany, tak kruzky sa musia prekladat na vrcholy (prip. uzly).

[trekker.dk]

OK, OK, kolik se Vás tu ještě seběhne?

Oprava je samozřejmě teoreticky možná, prakticky je Robert někde pryč a ostatní admini si téhle diskuze nevšimli nebo nechtějí sahat do textu.

[lip]

Bleee to nejde cist. Original je srozumitelnejsi nez tenhle preklad, navic ma svih.

Prekladal bych jen veci, u kterych existuje jasny cesky termin, ostatni bych ponechal v originale, maximalne "priohnul".

Doktori maji latinu, v IT by se mela pouzivat u odbornych terminu anglictitna. Ono ani v anglictine neni pro vsechno jeden nazev, ale tech prekladu do cestiny existuje hafo a premyslet u kazde vety, jak vypadala v puvodnim clanku, zrovna k pochopeni nepomaha.