Sjednocující souborové systémy: Architektura, vlastnosti a návrhové volby

29. 4. 2009 | Jirka Bourek | Programování | 4202×

Sjednocující souborový systém (unioning filesystem) kombinuje jmenné prostory dvou či více souborových systémů a vytváří tak jediný spojený jmenný prostor. Vhodné například pro živá CD/DVD nebo NFS. Existují již dvě desetiletí, ale Linux ještě implementaci přijatou nemá. Tato série článků zkoumá, jaké jsou možnosti.

Originál tohoto článku napsala Valerie Aurora (dříve Henson), vyšel na LWN.net.

Sjednocující souborový systém kombinuje jmenné prostory dvou či více souborových systémů a vytváří tak jediný spojený jmenný prostor. To je užitečné pro věci, jako jsou live CD/DVD: ve sjednocujícím připojení lze připojit malý, zapisovatelný souborový systém nad souborový systém DVD, který je pouze pro čtení, a získat tak použitelný systém bez potřeby přenášet systémové soubory z DVD na kořenový souborový systém. Další použití je exportovat jediný základní souborový systém pouze pro čtení přes NFS několika klientům, z nichž každý by měl svůj vlastní malý zapisovatelný sjednoceně připojený překrývající souborový systém. Dalším použitím by mohla být výchozí sada souborů v domácím adresáři.

Sjednocující souborové systémy různých druhů zde byly od souborové služby (nebo souborového systému) Translucent [Translucent File Service] napsané okolo roku 1988 pro SunOS. BSD mělo sjednocující připojení od 4.4 BSD-Lite z roku 1994 a Plan 9 implementoval sjednocené adresáře přibližně ve stejné době. První prototyp spojujícího souborového systému byl Dědící souborový systém [Inheriting File System, IFS], který napsal Werner Almsberger pro Linux 0.99 roku 1993. Později byl opuštěn, jak psal Werner, protože jsem se na něj podíval nazpět a znechutila mě jeho složitost. Pozdější implementace pro Linux zahrnují unionfs (2003), aufs (2006) a sjednocující připojení (2004) stejně jako prototypy a různé implementace pro FUSE. Jak je tedy možné, že roku 2009 Linux stále nemá sjednocující souborový systém ve stromě?

Krátká odpověď je, že žádná z existujících implementací nedosáhla požadavků jaderných správců na jednoduchost, čistotu a správnost. Proč je tak složité napsat sjednocující souborový systém, který tyto standardy splní? V tomto článku projdeme obecné koncepty sjednocujících souborových systémů a běžné návrhové problémy a řešení. V následujícím článku projdeme nejvýznamnější soupeře v zápase o to stát se sjednocujícím souborovým systémem v hlavní řadě, stejně jako sjednocujícími souborovými systémy pro jiné operační systémy.

Příručka implementace sjednocujících souborových systémů

Nejprve definujme, jak by mohla vypadat užitečná implementace sjednocujícího souborového systému. Základní potřeba je mít jeden souborový systém pouze pro čtení a nad ním nějaký zapisovatelný překryv [overlay]. Překryv musí trvale ukládat změny a umožnit libovolnou manipulaci se sjednoceným jmenným prostorem (včetně trvalého odstranění částí z jmenného prostoru pouze pro čtení - "vybělení"). Implementace by měla být dostatečně rychlá, aby ji bylo možné použít jako kořenový souborový systém, a měla by vyžadovat pouze málo nebo žádné modifikace souborových systémů pod sebou. Měla by být implementována v jádře; souborové systémy založené na FUSE lze využít leckde, ale v mnoha případech vhodné nejsou (kořenové souborové systémy, embedded zařízení, souborové systémy s velkou (nebo dokonce střední) výkonností, atd.)

Úspěšný sjednocující souborový systém bude zlepšením (z pohledu využitého místa na disku, ceny za údržbu kódu, doby vývoje) oproti alternativám - bude kopírovat přes všechny soubory, chytře dělit souborové systémy přes několik připojovacích bodů nebo zapisovat celý nový souborový systém na disk. Pokud získáme všechny tyto vlastnosti sjednocujícího souborového systému, ale příliš přitom zkomplikujeme kód VFS, budeme mít sjednocující souborový systém za cenu pomalé, neudržovatelné a chybové implementace VFS. Pokud bude mít sjednocující souborový systém stejně nebo více kódu než implementace souborových systémů pod ním, začnete se ptát, jestli podporovat sjednocování v těchto souborových systémech interně nebude udržovatelnější.

Jednou alternativou ke sjednocujícím souborovým systémům je blokové zařízení s kopírováním při zápisu [copy on write, COW], často používané pro obrazy virtualizovaných systémů. COW blokové zařízení je řešením pro mnoho aplikací, ale pro některé je režie blokového zařízení mnohem vyšší než režie sjednocujícího souborového systému. Zápisy na souborový systém na COW blokovém zařízení vytvoří spoustu duplicitních bloků, jak jsou zapisovány bitmapy, žurnály a záznamy o adresářích. Změna, kterou lze zabalit do pár bytů záznamu adresáře ve sjednocujícím souborovém systému, může vyžadovat několik set kilobytů změn na blokové úrovni. A co hůře, změny na blokovém zařízení mívají tendence jenom růst; i se spojováním bloků podle obsahu (což není běžná vlastnost) se mohou dva logicky téměř stejné souborové systémy na úrovni bloků lišit o mnoho megabytů. Důležitý případ je ten, kdy vymažete spoustu souborů; se sjednocujícím souborovým systémem tato operace sníží místo potřebné pro uložení rozdílů. S COW blokovým zařízením využité místo vzroste.

Jeden problém, který by NEMĚL být řešen sjednocujícím souborovým systémem (a souborovými systémy obecně) je správa zdrojových kódu. Moderní systémy pro správu zdrojových kódů jsou poměrně dobré oproti tomu, s čím jsme museli žít okolo roku 1990. Software pro správu zdrojových kódů byl v té době tak chybový a pomalý, že se opravdu zdálo jako dobrý nápad implementovat jeho části v jádře; některé komerčně úspěšné dodnes používané systémy pro správu zdrojových kódu opravdu vyžadují explicitní podporu souborového systému. V současnosti je k dispozici mnoho rychlých a spolehlivých systémů pro správu zdrojových kódů a panuje obecná shoda v tom, že složitý software by měl být implementován mimo jádro. (Ti, kdo nesouhlasí, se mohou podílet na gitfs.)

Obecné koncepty

Většina sjednocujících souborových systémů sdílí některé obecné koncepty. Tato sekce popisuje větve, vybělení [whiteout], neprůhledné adresáře [opaque directories] a kopírování souborů výše [copy up].

Větve jsou různé souborové systémy, které jsou sjednoceny. Přístupové politiky ke větvím mohou být pouze pro čtení, zapisovatelné nebo složitější variace, které závisí na oprávnění ostatních větví. Větve jsou řazeny [ordered] nebo skládány [stacked]; obvykle je větev "nahoře" zapisovatelná a větev "dole" pouze pro čtení. Pořadí větví se někdy může změnit, mohou být odstraněny, přidávány nebo se jejich oprávnění mohou měnit za chodu.

Obvykle potřebná vlastnost je, že pokud je konkrétní záznam v adresáři smazán ze zapisovatelné větve, tento záznam v adresáři by se nikdy neměl objevit, i když se vyskytuje v nižší větvi. Tzn. smazání souboru jménem "x" by mělo vyústit v to, že následně v daném adresáři žádný soubor "x" nebude, i když soubor jménem "x" existuje v nižší větvi. Obvykle je to implementováno kombinací vybělení a neprůhledných adresářů. Vybělení je záznam v adresáři, který zakrývá všechny záznamy z nižších větví daného jména. Neprůhledný adresář neumožňuje jmennému prostoru z nižších větví projevit se od tohoto bodu dál ve jmenném prostoru.

Když se změní soubor pouze pro čtení, musí být zkopírován do některé zapisovatelné větve. Kopírování výše je obvykle spuštěno buď v okamžiku, kdy je soubor otevřen s povolením k zápisu, nebo když se objeví první zápis do jeho dat či metadat.

Běžné problémy návrhu

Sjednocující souborové systémy často naráží na stejné návrhové problémy. Tyto problémy často mají jenom několik zjevných řešení se zanesením kompromisů a v určitém ohledu lze sjednocující souborové systémy charakterizovat podle toho, jakou sadu kompromisů si vybraly. V této sekci projdeme několik nejvýznamnějších návrhových problémů a jejich běžná řešení.

Znečištění jmenného prostoru: Vybělení, neprůhledné adresáře, přetrvávající čísla inodů a další přetrvávající data souborového systému jsou často ukládána ve zvláštně pojmenovaných souborech. Tyto soubory zanášejí nepořádek do dostupného jmenného prostoru a vytvářejí neočekávané chování. Nějaké menší znečištění souborového systému je v UNIXu akceptovatelné, pokud se omezuje na nejvyšší adresář (viz /lost+found), ale znečištění jmenného prostoru na úrovni adresářů nebo souborů obvykle vyvolává reptání. Řešení tohoto problému zahrnují různé způsoby stěhování znečištění souborového systému - přesunutí do jediného podadresáře v každém adresáři nebo v každém souborovém systému nebo na externí souborový systém - nebo vyhýbání se znečišťování jmenného prostorů úplně (což obecně vyžaduje podporu souborového systému po nimi).

Vybělení a neprůhledné adresáře: I když je koncept vybělení a neprůhledných adresářů poměrně obecný, implementace se liší. Nejběžnější volba je vytvořit záznam v adresáři se zvláštním jménem, jako je .wh.<jméno souboru>, které říká, že odpovídající záznam v adresáři nikdy nemá být vracen. To může způsobit srážky s uživatelskými soubory a bránit skládání jednoho spojení na druhé. Odstranění adresáře kvůli tomu navíc déle trvá, "prázdný" adresář může mít několik tisíc záznamů o vybělení, které je potřeba vymazat předtím, než může rmdir() doběhnout. Odstraňování adresáře se proto někdy odsouvá do zvláštního pracovního vlákna, aby se latence rmdir() snížila.

Další možností je vytvořit zvláštní typ záznamu v adresáři, který označuje vybělené záznamy v adresáři, a dávat vyběleným záznamům v adresáři rezervované číslo inodu. Jméno v samotném záznamu v adresáři je stejné jako to, které se vyběluje, a neobjevuje se ve výpisu adresáře. Tato podoba vybělení vyžaduje podporu souborového systému ve spojení, který musí ukládat potřebné příznaky, a nástrojů pro správu souborových systémů, aby tyto příznaky akceptovaly. Další možností je udělat z vybělených záznamů hard linky na speciální vybělené soubory nebo symbolické odkazy na rezervované cíle. Řešení pomocí hard linků vyžaduje počítat s možností, že se vyčerpá maximální počet odkazů na cílový soubor.

Adresáře lze označit za neprůhledné buď příznakem v inodu adresáře (opět vyžaduje podporu souborového systému pod spojením) nebo záznamem v adresáři s rezervovaným jménem, jako je ".opaque".

Časování kopírování adresářů: Když je založen soubor v zapisovatelné větvi v adresáři, který existuje jenom v jiné větvi, musí být kompletní adresářová cesta přítomna na zapisovatelné větvi. Cestu lze vytvářet podle potřeby, když je kopírován cílový soubor, nebo může být každý adresář preemptivně kopírován do zapisovatelné větve, když se otvírá. Vytváření cest na vyžádání zavádí složitost, problémy se zamykáním a přídavnou latenci při zapisování souborů. Vytváření cest při otevření adresáře kód zjednodušuje a zlepšuje latenci zapisování souborů, ale spotřebovává přídavné (často zanedbatelně) místo v zapisovatelné větvi.

Spotřeba paměti jádrem: Sjednocující souborové systémy často zavádějí nové datové struktury, kopie datových struktur navíc a celou škálu cachovaných metadat. Například sjednocení dvou souborových systémů může potřebovat alokaci tří VFS inodů pro jeden logický objekt. Nejběžnější implementace vybělení a odstranění duplicitních záznamů vyžaduje načtení všech záznamů v adresáři ze všech větví do paměti a vytvoření sjednoceného pohledu na adresářovou strukturu v ní. Pokud je tato cache udržována přes systémová volání, je potřeba se starat o její regenerování, když se větve pod ní změní. Když cachovány nejsou, je potřeba znovu alokovat paměť a záznamy spojovat opakovaně. V obou případech je potřeba alokovat pro jádro hodně paměti.

Čistota kódu: Jedním z hlavních cílů sjednocujícího souborového systému je znovuvyužít kód existujících souborových systémů s očekávaným ziskem v podobě jednoduchosti údržby a budoucího vývoje této kódové základny. Jestliže je implementace příliš komplexní nebo narušující, konečným efektem je složitější správa a vývoj. Nepřeberné množství a různost linuxových souborových systémů (na disku, v paměti, pseudo) demonstruje výhody čistého a jednoduchého rozhraní pro souborový systém.

Hloubka zásobníku: Linuxové jádro má omezenou dostupnou hloubku zásobníku. Volání interních funkcí souborových systémů z neočekávané kódové cesty nebo ještě hůře rekurzivně, může snadno vést k překročení omezení jaderného zásobníku. Některé sjednocující souborové systémy jsou implementovány jako skládané nebo vrstvené souborové systémy, což z principu prohlubuje využívání zásobníku.

Počet větví: Spotřeba paměti je obvykle úměrná počtu větví, které se používají. Větve mohou být omezeny maximem stanoveným při překladu, ale alokace dostatku paměti pro toto maximum nemusí být možné. Dynamická alokace a realokace, když jsou větve přidávány a odebírány, může být komplexní a zavádět nové příležitosti k selhání.

Koherence změn: Běžně požadovanou vlastností je umožnit změnu více než jedné větve naráz. To vyžaduje nějakou metodu koherence cache mezi různými částmi souborového systému. Obvykle tato metoda přítomna není nebo je korektní pouze částečně. Uživatelé často požadují přímý přístup k souborovým systémům, které tvoří větve sjednocení (místo přístupu přes sjednocený souborový systém), což je situace, kterou je obzvláště těžké vyřešit.

Dynamická správa větví: Uživatelé často chtějí přidávat, měnit nebo odstraňovat politiky větví ve sjednocení, když je sjednocení stále připojeno. V jednoduchých případech je to záležitost prohledání připojovacích voleb a manipulace s datovými strukturami, ale může to mít významné důsledky na implementaci koherence cache.

readdir() a přátelé: Jedna z velkých tragédií UNIXového rozhraní pro souborové systémy je přechovávání rodiny readdir(), telldir(), seekdir() atd. ze standardu POSIX. Aplikace může začít číst záznamy v adresáři, kdykoliv čtení pozastavit a později pokračovat ze "stejného" místa v adresáři. Jádro musí vytvořit 32bitové magické hodnoty, které mu umožňují restartovat readdir() z místa, kde se naposledy zastavilo. Původně to bylo implementováno stejně jako pozice v souboru: záznamy v adresáři byly ukládány sekvenčně a počet vrácených se stal pořadovým číslem dalšího záznamu v adresáři. Aby podporoval readdir(), musí sjednocující souborový systém spojit záznamy z nižších souborových systémů, odstranit duplikáty a vybělení a vytvořit nějaký druh stabilního mapování, které mu umožní obnovit readdir() korektně. Podpora knihoven v uživatelském prostoru to může zjednodušit cachováním výsledků v paměti v uživatelském prostoru.

Stabilní, unikátní čísla inodů: NFS exporty a některé aplikace očekávají, že se čísla inodů souborů mezi rebooty, připojeními atd. nemění. Aplikace také očekávají, že soubory lze unikátně identifikovat kombinací ID zařízení a číslem inodu. Sjednocující souborový systém nemůže jednoduše zkopírovat číslo inodu ze souborového systému pod ním, protože stejný inode se pravděpodobně používá na více než jednom souborovém systému. Unikátní (ale ne stabilní) čísla inodů lze implementovat poměrně snadno, ale stabilní čísla inodů vyžadují nějaký druh stabilního mapování souborů ze souborového systému níže k přiřazeným číslům inodu.

mmap(): mmap() vždy představuje tu složitou část. Jednoduchý způsob, jak vypadat chytře, aniž by člověk o souborových systémech něco věděl, je moudře pokývnout a říct: "A co mmap()?" mmap() souboru ve sjednoceném souborovém systému je problematický, protože soubor může najednou zmizet a být nahrazen jiným (kopírováním výše nebo zápisem z jiného procesu) nebo se změnit bez spolupráce se sjednocujícím souborovým systémem (přímý přístup k souborovému systému pod větví). Některé sjednocující souborové systémy povolují podoby mmap(), které nejsou implementované korektně podle standardu POSIX.

rename() mezi větvemi: rename() je užitečné systémové volání, které umožňuje atomicky přejmenovat soubor na stejném souborovém systému. Některé sjednocující souborové systémy se snaží emulovat rename() mezi různými větvemi. Jiné prostě vrací EXDEV, chybový kód pro pokus přesunout soubor mezi souborovými systémy. Většina aplikací se dokáže se selháním rename() vyrovnat a použít běžné kopírování souboru.

Rozdíly implementace souborového systému: Různé souborové systémy mají různá pravidla o povolených jménech souboru, povolených znacích, délce jména, rozlišování malých a velkých písmen, jmen rozšířených atributů a jejich velikostí atd. Sjednocený souborový systém potřebuje překládat pravidla z jednoho souborového systému do jiného. Některé sjednocující souborové systémy prostě omezují typy souborových systému, které podporují, místo implementace překládacího kódu pro neobvyklé příklady použití.

Násobné hard linky: Soubor na nižší větvi může mít několik hard linků, tj. několik cest ukazujících na stejný inode. Když je soubor s několika hard linky na větvi pouze pro čtení změněn, striktní UNIXová sémantika vyžaduje najít všechny další cesty k tomuto souboru a také je zkopírovat do zapisovatelné větve. UNIXové souborové systémy bohužel obecně neposkytují efektivní způsob, jak najít všechny cesty k inodu. Některé sjednocující souborové systémy udržují seznam inodů s neobjevenými alternativními cestami a ty potom kopírují, když se k nové cestě přistupuje, jiné problém prostě ignorují. Kolik aplikací závisí na správném chování hard linků, když se používají tímto způsobem, je otevřená otázka.

Práva, vlastník a časové značky: Tyto atributy se často počítají použitím kombinace souborových systémů níže, volbami specifikovanými při připojení, uživatelem a umask v době připojení a politikami správy větví. Konkrétní politiky se značně liší.

Příliš mnoho funkcí: Vlastnosti poskytované sjednocujícím souborovým systémem občas překračují skutečné potřeby 99,9 % aplikací sjednocování. To může být důsledkem požadavků od uživatelů nebo přístupem "protože můžeme" - uživatelé žádají dvě nebo tři větve, ale je možné jich podporovat tisíce, tak hurá do toho, popřípadě je kód strukturován tak, že všechny kombinace vlastností X, Y a Z se implementují snadno, i když uživatelé chtějí pouze X a Y nebo Y a Z. Každá vlastnost může vypadat jako téměř zdarma, ale často to končí omezením implementace nebo vytvářením nových příležitostí pro chyby. Soustředění se na cíl je důležité.

Shrnutí

Sjednocující soubory je z principu obtížné implementovat, ale většina složitosti a ošklivosti pochází z řešení následujících problémů: vybělení, podpora readdir(), stabilní čísla inodů a souběžné modifikace jedné nebo více větví naráz. Málokterý z těchto problémů má zjevně nejlepší řešení, většina má jenom řešení s různými kompromisy.

Příště

V příštím článku projdeme sjednocující připojení v BSD, unionfs, aufs a linuxová sjednocující spojení. U každého z těchto sjednocujících souborových systémů se podíváme na specifické implementační detaily, včetně jaderných datových struktur a jejich řešení různých problémů popsaných v tomto článku. Také se podíváme na problémy obklopující začlenění každého z těchto řešení do jádra hlavní řady. Zakončením bude obecná analýza toho, co ve sjednocujících souborových systémech funguje, a co ne, jak z čistě technického úhlu pohledu, tak z pohledu návrhu software.

Pokračování příště...

Poděkování

K získání podkladů pro tento článek pomohlo mnoho diskuzí s vývojáři, ale konkrétně tento článek nejvíce získal z diskuzí s  pány: Erez Zadok, Christoph Hellwig a Jan Blunck.

       

Komentáře

[oroborus]

Tento clanok mal vyst IMHO 29.4, ale ja si ho mozem precitat teraz 28.4

[Robert Krátký]

Chyba v Matrixu...

[oroborus]

Tak to by som mal nahlasit do "Bug hunt" :)

[Robert Krátký]

Zbytečné. Bylo to v kombinaci s lidským faktorem.

[Fluttershy, yay!]

OT: Valerie Aurora je úžasné jméno...

[Mirek_]

Erez Zadok taky...

[Zdeněk Štěpánek]

Zajimavy clanek. Val sice napsala ajk je to strasne sliozite a ze je jeste tezsi to naprogramovat, ale ja aufs2 pouzivam na nfsroot klientech. / ze serveru je pres NFS pripojen rw a /var na klientovi se pripojuje pres aufs2 nekam do /aufs-data/ip_adresa:

mount -t aufs -o br=/aufs-data/$IP/var/:/var/ none /var/

[trekker.dk]

O aufs bude řeč - pokud autor tohoto fs nezmění přístup, do jádra se to nedostane.

[joe]

Což, dokud ho udržuje, je úplně jedno.