Krátká historie Btrfs

25. 8. 2009 | Jirka Bourek

Články - Krátká historie Btrfs  

Btrfs bývá označován za budoucnost linuxových souborových systémů. Přečtěte si, co vedlo k jeho vzniku, kdo za ním stojí, jak se liší od ZFS a jak bude jeho vývoj pokračovat.

Obsah

• Btrfs: Před historií
• Btrfs: Začátek
• Btrfs: Politika
• Btrfs: Stručné srovnání se ZFS
• Btrfs: Co dál?

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

Pravděpodobně jste slyšeli o tom novém hustém týpkovi ze sídliště souborových systémů, btrfs (v angličtině vyslovováno „butter-eff-ess“) – konec konců Linus Torvalds ho používá jako kořenový souborový systém na jednom ze svých laptopů. Možná o něm ale nevíte o moc víc než několik klíčových slov na vysoké úrovni – kopírování při zápisu, kontrolní součty, zapisovatelné snímky [snapshot] – a pár senzačních příběhů – benchmarky na Phoronixu, btrfs vykrádá ZFS, btrfs je tajný plán Oraclu pro nadvládu nad Linuxem atd. Když dojde na souborové systémy, je těžké odlišit pravdu od řečí hanebných pomlouvačů: Kód je příliš komplexní, charakteristiky příliš přehnané a uživatelé jsou naštvaní, když přijdou o data. Věci nejde vyřešit ani bitvou benchmarků: Zátěže souborového systému se divoce liší, takže je možné přijít s rozumným argumentem, proč je kterýkoliv benchmark naprosto irelevantní nebo kriticky důležitý.

V tomto článku se podíváme do zákulisí návrhu a vývoje btrfs na mnoha úrovních – technické, politické, osobní – a budeme ho sledovat od jeho počátků v dílně po současnou pozici Linusova kořenového souborového systému. Znalost pozadí a motivace u každého kroku vám pomůže pochopit, proč se na btrfs začalo pracovat, jak funguje a kam bude směrovat v budoucnu. Na konci byste měli být schopni i strávit popis formátu btrfs na disku.

Upozornění: Musím upozornit na dvě věci: Za prvé, několik let jsem v Sunu pracovala na ZFS. Za druhé, už jsem byla předvolána k výpovědi při různých soudních přích mezi Sunem a NetApp a ráda bych se vyhnula tomu, že bych jim poskytla jakoukoliv záminku mě předvolat znovu. Budu se snažit být férová, čestná a puntičkářsky přesná.

Btrfs: Před historií

Představte si, že jste vývojář souborových systémů pro Linux. Je rok 2007 a jste na Linux Storage and File systems workshop. S linuxovými souborovými systémy to vypadá bledě: Reiserfs, který má problémy s kvalitou a neudržitelným modelem financování, právě ztratil veškerou důvěryhodnost, protože Hans Reiser byl před pár měsíci zatčen. ext4 je stále ve vývoji; ve skutečnosti se dokonce ještě ani nenazývá ext4. A co je důležité, ext4 je pouze přímočaré rozšíření 30 let starého formátu a co se vlastností týče, je světelné roky za konkurencí. Firmy ve stejné době omezují financování vývoje Linuxu; oddělení Linuxu v IBM končí období hájení a potřebuje ukázat ziskovost. Další firmy se bojí blížící se recese a výzkum hází přes palubu. Chtějí projekty, kde se čas do dokončení počítá v měsících, ne letech.

Věčně doufající, vývojáři souborových systémů se sešli i tak. Protože se workshop koná společně s USENIX FAST '07, předneslo na něm několik výzkumníků ze školství i průmyslu své nápady. Jedním z nich byl Ohad Rodeh, který vyvinul druh b-stromu, který je přátelský ke kopírování při zápisu [PDF]. Pokud začneme od začátku, b-stromy jsou ve své přirozené formě s COW [copy-on-write, kopírování při zápisu] značně nekompatibilní. Listy stromu jsou spojeny dohromady, takže když se pozice jednoho listu změní (zápisem, což implikuje kopírování do nového bloku), odkaz v sousedním listě se mění, což spustí další kopírování při zápisu a změnu pozice, což změní odkaz v dalším listu… Výsledkem je, že celý b-strom musí být od začátku do konce přepsán, kdykoliv se změní jeden list.

Ohadovy b-stromy jsou jiné: Za prvé se zbavil odkazů mezi listy ve stromě – což také „vyhazuje spoustu existující literatury o b-stromech“, jak říká ve svých slidech [PDF] – ale ponechává dost vlastností b-stromů, aby byly stále užitečné. (To je poměrně standardní podoba b-stromů v souborových systémech, občas se nazývají „b+stromy“.) Přidal nějaké algoritmy pro procházení stromem, které využívají čítání odkazů, aby se omezila velikost části stromu, kterou je nutné projít, když se maže snímek, stejně jako pár dalších věcí – proaktivní dělení a spojování vnitřních uzlů, aby vkládání a mazání nepotřebovalo žádné procházení [backtracing]. Výsledkem je jednoduchá, robustní datová struktura, která velmi efektivně sleduje rozsahy [extent] (skupiny spojitých datových bloků) v souborovém systému postaveném na COW. Ohad vlastně vytvořil prototyp systému před několika lety, ale s touto oblastí výzkumu skončil a chtěl jenom, aby někdo vzal jeho b-stromy přátelské pro COW a dobře je využil.

Btrfs: Začátek

Chris Mason tyhle b-stromy přátelské pro COW vzal a pracoval s nimi dále. V té době Chris pracoval na Reiserfs, kde se hodně naučil o tom, co v souborovém systému dělat, a co ne. Reiserfs měl několik hezkých vlastností – shlukování malých souborů, b-stromy pro rychlé vyhledávání, flexibilní rozvržení – nicméně implementace byla nahodilá a ad hoc. Kódové cesty se divoce množily a s nimi i potenciální chyby.

Chris měl nápad: Co kdyby všechno v souborovém systému – inody, data souborů, záznamy v adresáři, bitové mapy – byly položky v b-stromě s kopírováním při zápisu? Všechny zápisy a čtení by procházely stejnou cestou kódu, takovou, která by všechny položky sloučila do jednoho uzlu v b-stromě a nechala je tam bez starosti o jejich typ. Pak stačí kód napsat jednou a získáte kontrolní součty, čítání odkazů (pro snímky), kompresi, fragmentaci atd. pro cokoliv v souborovém systému.

Proto Chris přišel s následující základní strukturou btrfs („btrfs“ je zkratka pro "b-tree file system") – btrfs se skládá ze tří typů struktur na disku: hlaviček bloků, klíčů a položek, které jsou aktuálně definovány takto:

struct btrfs_header {
    u8 csum[32];
    u8 fsid[16];
    __le64 blocknr;
    __le64 flags;

    u8 chunk_tree_uid[16];
    __le64 generation;
    __le64 owner;
    __le32 nritems;
    u8 level;
}

struct btrfs_disk_key {
    __le64 objectid;
    u8 type;
    __le64 offset;
}

struct btrfs_item {
    struct btrfs_disk_key key;
    __le32 offset;
    __le32 size;
}

Uvnitř b-stromu (tj. ve „větvích“ stromu, což je opakem listů na dně stromu) se uzly skládají pouze z klíčů a hlaviček bloků. Klíče říkají, kde hledat položku, kterou chcete, a hlavičky bloků říkají, kde je další uzel nebo list v b-stromě umístěn na disku.

Listy b-stromu obsahují položky, které jsou kombinací klíčů a dat. Podobně jako u Reiserfs jsou data a položky shromážděny s extrémně efektivním využitím místa: Hlavičky položek (tj. struktura item popsaná výše) jsou sloučeny na začátku bloků, zatímco data spojená s každou položkou jsou naskládána dohromady a začínají na konci bloku. Jak je ukázáno na obrázku napravo, hlavičky položek a data rostou směrem k sobě.

Kromě toho, že je to efektivní z hlediska kódu, je toto schéma efektivní i co se týče prostoru a času. Souborové systémy do daného bloku souborového systému obvykle vkládají jenom jeden druh dat – bitové mapy nebo inody nebo záznamy v adresáři. Tím se plýtvá místem na disku, protože nevyužité místo jednoho druhu bloku nelze využít pro jiné účely, a zároveň časem, protože dostat se k jednomu konkrétnímu kousku dat souboru vyžaduje čtení několika různých druhů metadat, přičemž každý druh je uložen v jiném bloku souborového systému. V btrfs jsou položky sloučeny dohromady (nebo vytlačeny do listů) v takovém uspořádání, které optimalizuje jak čas přístupu, tak využití místa na disku. Rozdíl můžete vidět z těchto (velmi schématických a velmi zjednodušených) diagramů. Staré souborové systémy většinou organizují data takto:

Btrfs na druhou stranu vytváří na disku rozvržení, jako je toto:

V obou obrázcích červená barva značí vyplýtvané místo na disku a červená šipka značí posun hlaviček.

Každý druh metadat a dat na souborovém systému – záznam v adresáři, inode, rozšířený atribut, samotná data souboru – se ukládá v konkrétním typu položky. Pokud se vrátíme k definici položky, vidíme, že první prvek je klíč:

struct btrfs_disk_key {
    __le64 objectid;
    u8 type;
    __le64 offset;
}

Začněme polem objectid. Každý objekt v souborovém systému – většinou inode – má unikátní objectid. To je poměrně standardní věc – je to ekvivalent čísel inodů. Btrfs je zajímavý tím, že objectid tvoří nejvýznamnější bity klíče položky – toho, který používáme při vyhledávání položky v b-stromě – a nižší bity jsou různé druhy položek spojené s daným objectid. Výsledkem je, že se všechny informace spojené s daným objectid shromažďují. Pokud alokujete sousedící objectid, pak jsou všechny položky těchto objectid také alokovány blízko u sebe. Pár <objectid, type> automaticky shlukuje související data bez ohledu na jejich skutečný obsah, což je opakem přístupu klasických souborových systémů, které píší samostatné optimalizované alokátory pro každý druh dat souborového systému.

Pole type říká, jaký typ dat je v položce uložen. Je to inode? Záznam v adresáři? Je to rozsah, který říká, kde jsou data souboru na disku? Jsou to samotná data souboru? S kombinací objectid a typu lze v b-stromě najít libovolná data souborového systému.

Měli bychom se v rychlosti podívat na samotnou strukturu uzlů b-stromu a listů. Každý uzel a list je rozsah v b-stromě – uzly jsou rozsahy plné párů <klíč, hlavička bloku> a listy obsahují položky. Rozsáhlá data souboru jsou uložena mimo listy b-stromu, přičemž položka popisující rozsah je uchovávána v samotném listu. (Co je „rozsáhlý“ soubor, je laditelné v závislosti na zátěži.) Každý rozsah popisující část b-stromu má kontrolní součet a počet odkazů, což umožňuje zapisovatelné snapshoty. Každý rozsah také zahrnuje explicitní zpětný odkaz na každý z rozsahů, které na něj ukazují.

Zpětné odkazy dávají btrfs podstatnou výhodu oproti každému jinému souborovému systému ve své třídě, protože s nimi je možné rychle a efektivně migrovat data, inkrementálně souborový systém kontrolovat a opravovat a kontrolovat správnost čítání odkazů během normální práce. Důkazem je, že btrfs již nyní podporuje rychlé, efektivní odstranění zařízení a zmenšení dostupného úložného prostoru souborového systému. Většina ostatních souborových systémů má „zmenšení souborového systému“ na seznamu vlastností, ale obvykle to skončí neefektivní a pomalou implementací, která navíc přijde o několik let později – nebo vůbec. Pro příklad ext3/4 umí souborový systém zmenšit – procházením celého souborového systému a hledáním dat umístěných v oblasti, kde se bude odstraňovat zařízení. To je pomalý, vytěžující a k chybám náchylný proces. ZFS souborový systém stále zmenšit neumí.

Výsledek je krásně obecný a elegantní: Všechno na disku je b-strom, který obsahuje rozsahy položek, pro které jsou počítány odkazy a kontrolní součty, a tyto položky organizuje podle klíčů <objectid, type>. Velká část kódu btrfs se nezajímá o to, co je v položkách uloženo, pouze ví, jak je z b-stromu vyjmout nebo je tam přidat. Optimalizace rozvržení disku je jednoduchá: Alokování věcí s podobnými klíči blízko u sebe.

Btrfs: Politika

Ve stejné době, kdy Chris řešil technický návrh btrfs, řešil také, jak vývoj btrfs financovat jak krátkodobě, tak dlouhodobě. Chris se nedávno přesunul ze SUSE do zvláštní skupiny Linux v Oracle, která zaměstnává několik vysoce postavených vývojářů úložných zařízení v Linuxu, ke kterým patří Martin K. Peterson, Zach Brown a Jens Axboe. Oracle financuje značnou část vývoje Linuxu, něco z toho je zjevně spojeno s databází Oracle (OCFS2, DIF/DIX) a něco méně zjevně (práce na obecné blokové vrstvě, syslety). Tady je, jak to Chris řekl v nedávném interview s Amandou McPherson z Linux Foundation:

Amanda: Proč jsi s tímto projektem začal? A proč ho Oracle podporuje tak výrazně?

Chris: Na Btrfs jsem začal pracovat brzy poté, co jsem nastoupil do Oracle. Měl jsem unikátní příležitost podívat se na věci, které v Linuxu chybí, a měl jsem pocit, že Btrfs je nejlepší způsob, jak je řešit.

Linux je pro Oracle velmi důležitá platforma. Význačně ho používáme v interní práci a má pro nás širokou základnu zákazníků. Chceme, aby byl Linux silný jako operační systém pro datová centra, a inovace v oblasti ukládání je pro Oracle přirozený způsob, jak k tomu přispět.

Jinými slovy Oracle je rád, že může Linux použít jako platformu, a je ochoten investovat do jeho vývoje, i když není přímo spojen s výkonem databáze Oracle. Podívejte se na to takto: Kolik operačních systémů je z velké části psáno a financováno vaší konkurencí? I když je lákavé mít operační systém zcela pod svou kontrolou – jako je tomu u Solarisu – také to znamená platit za většinu vývoje pro takovou platformu. Závěrem je, že Oracle věří, že je v jeho zájmu použít své vlastní experty k tomu, aby Linux zůstal silný.

Po několika měsících programování a diskuzích o návrhu se Zachem Brownem a mnoha dalšími Chris zaslal btrfs k revizím. Od té chvíle je možné sledovat historii btrfs stejně jako historii jakéhokoliv jiného open source projektu z e-mailových konferencí a historie zdrojového kódu. Btrfs je nyní v hlavní řadě jádra a pracují na něm vývojáři z Red Hatu, SUSE, Intelu, IBM, HP, Fujitsu atd. Btrfs je opravdový projekt s otevřeným zdrojovým kódem – nejenom licencí, ale také komunitou.

Btrfs: Stručné srovnání se ZFS

Lidé se často ptají na vztah mezi btrfs a ZFS. Z jednoho úhlu pohledu jsou tyto dva souborové systémy velmi podobné: Oba jsou souborové systémy s kontrolními součty a kopírováním při zápisu s podporou více zařízení a zapisovatelnými snímky. Z jiného úhlu pohledu se podstatně liší: Mezi jinými věcmi architekturou, vývojovým modelem, dospělostí, licencí a hostitelským operačním systémem. Místo odpovídání na jednotlivé otázky proto poskytnu stručnou historii vývoje ZFS a srovnám ji s btrfs u několika klíčových položek.

Když začalo ZFS, se souborovými systémy pro Solaris to také vypadalo bledě. Logující UFS se blížil ke konci provazu, co se týče výkonnosti a velikosti souborového systému. UFS byl tak opožděný, že mnoho zákazníků platilo velké peníze Veritasu, aby místo toho mohli používat VxFS. Solaris potřeboval nový souborový systém a potřeboval ho rychle.

Jeff Bonwick se rozhodl, že problém vyřeší a začal uvnitř Sunu projekt ZFS. Jeho motto bylo stejné jako pro subsystém virtuální paměti – proč by správa a používání disku nemohlo být tak snadná jako u paměti? Centrální datovou strukturou na disku byl slab – kousek disku dělený do bloků stejné velikosti, jako je to u jaderného alokátoru paměti SLAB, který také vytvořil. Místo rozsahů ZFS používá jeden ukazatel na blok pro každý blok, ale každý objekt používá jinou velikost bloku – např. 512 bytů nebo 128 kilobytů podle velikosti objektu. Blokové adresy se překládají pomocí mechanismu podobného virtuální paměti, takže bloky lze přemisťovat bez znalosti vyšších vrstev. Všechna data a metadata souborového systému se ukládají v objektech. A všechny změny souborového systému se popisují jako změny objektů, které se zapisují kopírováním při zápisu.

Ve shrnutí btrfs na disku všechno organizuje do b-stromu rozsahů, který obsahuje položky a data. ZFS na disku všechno organizuje do stromu ukazatelů na bloky s různými velikostmi bloku podle velikosti objektu. Btrfs počítá kontrolní součty a odkazy rozsahů, ZFS počítá kontrolní součty a počty odkazů bloků proměnné velikosti. Oba souborové systémy zapisují změny na disk kopírováním při zápisu – používané rozsahy či bloky nikdy nejsou přepisovány na místě, vždy jsou nejprve zkopírovány někam jinam.

Takže i když je seznam vlastností těchto dvou souborových systémů vcelku podobný, implementace se naprosto různí. Je to trochu jako sbíhavá evoluce vačnatců a placentálních savců – vačnatá myš a placentální myš vypadají zvnějšku téměř identicky, ale jejich implementace se podstatně liší!

Podle mého mínění je základní architektura btrfs mnohem vhodnější pro ukládání než u ZFS. Jedním z velkých problémů přístupu ZFS – „desky“ bloků dané velikosti – je fragmentace. Každý blok může obsahovat objekty pouze jedné velikosti, takže lze snadno skončit například se souborem složeným ze 64k bloků, který potřebuje narůst o jeden blok, ale žádné 64k bloky k dispozici nejsou, i když je souborový systém téměř plný skoro prázdných slabů 512bytových bloků, 4k bloků, 128k bloků atd. Abychom tento problém vyřešili, vyvinuli jsme (my, vývojáři ZFS) způsoby, jak vytvořit velké bloky z malých bloků („spolčení bloků“) a další nepříjemné obcházení problémů. Na naši obranu – v té tobě se b-stromy a rozsahy zdály naprosto nekompatibilní s kopírováním při zápisu a podoba s virtuální pamětí nám dobře sloužila v mnoha dalších aspektech.

V kontrastu s tím přístup položek v b-stromě extrémně efektivně využívá místo a je flexibilní. Defragmentace je nepřetržitá – opakované balení položek je efektivně součástí normální kódové cesty, která připravuje zápis rozsahů na disk. Počítání kontrolních součtů, čítání odkazů a provádění dalších nejrůznějších déletrvajících prací na úrovni rozsahů redukuje režii a umožňuje nové vlastnosti (jako je rychlé reverzní mapování z rozsahu na všechno, co se na něj odkazuje).

Nyní několik osobních předpovědí (založených čistě na veřejných informacích – nemám žádné zákulisní informace). Btrfs bude výchozím souborovým systémem pro Linux během dvou let. Btrfs jako projekt nebude (a v tomto bodě ani nemůže být) Oraclem zrušen. Pokud budou vyřešeny všechny záležitosti okolo duševního vlastnictví (velké pokud), ZFS bude portován na Linux, ale oproti btrfs bude mít zastoupení jenom pár procent. Vraťte se sem za dva roky a uvidíte, jestli jsem se v něčem trefila!

Btrfs: Co dál?

Btrfs míří k verzi 1.0 po více než dvou letech od prvního oznámení. To je mnohem rychleji, než mnoho veteránů souborových systémů – včetně mě – čekalo, obzvláště vzhledem k tomu, že po většinu toho času měl btrfs pouze jednoho vývojáře pracujícího na plný úvazek. Btrfs není připraven pro produkční nasazení – tj. pro ukládání a vybavování dat, jejichž ztráta by vás naštvala – ale je připraven pro široké testování – například na vašem laptopu, který se denně zálohuje, nebo na experimentálním netbooku, který stejně přeinstalováváte každých pár týdnů.

Mějte na paměti, že se nedávno měnil formát btrfs na disku: Commit, který přišel těsně po vydání 2.6.30, mění formát na disku způsobem, který je nekompatibilní se staršími jádry. Pokud vytvoříte souborový systém btrfs s jádrem a nástroji pro 2.6.30 nebo starší a nabootujete nové jádro s novým formátem, nebudete schopni souborový systém nadále se starším jádrem používat. Linus Torvalds na to přišel složitým způsobem. Pokud se to nicméně stane vám, nepanikařte – na btrfs wiki lze najít záchranné obrazy a další užitečné informace.