0xDEADBEEF

[RSS]
««« »»»

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

17. 9. 2017

B-trees, Sha­dowing, and Clones, Ohad Rodeh

Tento paper po­lo­žil zá­klady Btrfs – copy-on-write sou­bo­ro­vého sys­tému (FS), který pod­po­ruje efek­tivní vy­tvá­ření sna­pshotů a klonů.

Jako u mnoha jiných FS jsou i tady B-stromy po­u­žité jako klí­čová datová struk­tura. Jediná od­liš­nost oproti běžným ná­vrhům je fakt, že se změny ne­pro­vádí na místě a ne­do­chází k pře­pi­so­vání exis­tu­jí­cích dat.

Lidi z funk­ci­o­nál­ních kruhů tohle dobře znají. Jde o oby­čejné plně per­si­s­tentní stromy za­lo­žené na ko­pí­ro­vání cesty od listu ke kořeni. V han­tý­rce FS po­di­vínů se této tech­nice říká sha­dowing, ale jde o stejný prin­cip – při mo­di­fi­kaci B-stromu (po­u­ží­vají se B+stromy, které mají v lis­tech uka­za­tele na datové stránky), je vy­tvo­řena nová cesta od listu ke kořeni. Odtud po­chází ono copy-on-write – při zápisu se vždy ko­pí­ruje, nikdy se ne­pře­ma­zá­vají stará data, ale je vy­tvo­řena nová kopie. Staré verze exis­tují na disku dokud na ně něco od­ka­zuje a pak jsou od­stra­něny gar­bage collec­to­rem.

Lo­gicky z těchto sta­rých per­si­s­tent­ních ver­zích je možné vy­tvá­řet sna­pshoty a klony, tedy edi­to­va­telné his­to­rické větve sou­bo­ro­vého sys­tému, které s tím pů­vod­ním sdílí ma­xi­mum mož­ných dat. To je opět kla­sické struk­tu­rální sdí­lení (structu­ral sha­ring), které každý FP ako­lyta zná jako vlastní boty.

Ve světě sou­bo­ro­vých sys­témů je třeba se vy­po­řá­dat s ex­pli­citní alo­kací a uvol­ňo­vá­ním sma­za­ných bloků. Pro­tože na­vr­ho­vaný FS může sdílet datové bloky a struk­turu B-stromů mezi růz­nými klony, je nutné pro každý z nich udr­žo­vat čítač re­fe­rencí, který udává kolik poin­terů od­ka­zuje na ten který blok. Čítače re­fe­rencí jsou také udr­žo­vány v copy-on-write B-stro­mech. (CoW me­cha­nis­mus je, jak je vidět, dů­le­žitý pro odol­nost sys­tému proti pádu.)

Čítače re­fe­rencí umož­ňují levné klo­no­vání – stačí jen zko­pí­ro­vat kořen stromu a ak­tu­a­li­zo­vat re­f­count všech po­tomků (nově na ně uka­zuje o jeden rodič více). Všechny další změny se pro­vá­dějí líně.

Z od­ka­zo­va­ného článku vy­chází Btrfs, ale ten je – jako funkční systém a nejen pro­to­typ – mnohem kom­pli­ko­va­nější.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)