B-stromy, persistence, copy-on-write a Btrfs
B-trees, Shadowing, and Clones, Ohad Rodeh
Tento paper položil základy Btrfs – copy-on-write souborového systému (FS) s podporou efektivního vytváření snapshotů a klonů.
Jako u mnoha jiných FS jsou i tady B-stromy použité jako klíčová datová struktura. Jediná odlišnost oproti běžným návrhům je fakt, že se změny neprovádí na místě a nedochází k přepisování existujících dat.
Lidi z funkcionálních kruhů tohle dobře znají. Jde o obyčejné plně persistentní stromy založené na kopírování cesty od listu ke kořeni. V hantýrce FS podivínů se této technice říká shadowing, ale jde o stejný princip – při modifikaci B-stromu (používají se B+stromy, které mají v listech ukazatele na datové stránky), je vytvořena nová cesta od listu ke kořeni. Odtud pochází ono copy-on-write – při zápisu se vždy kopíruje, nikdy se nepřemazávají stará data, ale je vytvořena nová kopie. Staré verze existují na disku dokud na ně něco odkazuje a pak jsou odstraněny garbage collectorem.
Logicky z těchto starých persistentních verzích je možné vytvářet snapshoty a klony, tedy editovatelné historické větve souborového systému, které s tím původním sdílí maximum možných dat. To je opět klasické strukturální sdílení (structural sharing), které každý FP akolyta zná jako vlastní boty.
Ve světě souborových systémů je třeba se vypořádat s explicitní alokací a uvolňováním smazaných bloků. Protože navrhovaný FS může sdílet datové bloky a strukturu B-stromů mezi různými klony, je nutné pro každý z nich udržovat čítač referencí, který udává kolik pointerů odkazuje na ten který blok. Čítače referencí jsou také udržovány v copy-on-write B-stromech. (CoW mechanismus je, jak je vidět, důležitý pro odolnost systému proti pádu.)
Čítače referencí umožňují levné klonování – stačí jen zkopírovat kořen stromu a aktualizovat refcount všech potomků (nově na ně ukazuje o jeden rodič více). Všechny další změny se provádějí líně.
Z odkazovaného článku vychází Btrfs, ale ten je – jako funkční systém a nejen prototyp – mnohem komplikovanější.
Relevantní čtení: