0xDEADBEEF

[RSS]
««« »»»

B-stromy, persistence, copy-on-write a Btrfs

17. 9. 2017

B-trees, Shadowing, and Clones, Ohad Rodeh

Tento paper položil základy Btrfs – copy-on-write souborového systému (FS), který podporuje efektivní 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í:

píše k47 (@kaja47, k47)