Btrfs

B-trær i forbindelse med btrfs

Datatrukturen ble beskrevet i forbindelse med filsystemer av Ohad Roed, en forsker ved IBM, under konferansen til USENIX i juni 2007. I sitt opprinnelige forslag drøftet Rodeh B+ trær, som er i utbredt bruk som datastrukturer i databaser. Rohed påpekte at B+ trær ikke kunne tillate copy-on-write baserte snapshots på en effektiv måte. Årsaken er at løvnodene er lenket sammen: Hvis en løvnode blir kopiert på denne måten, vil dens søsken og foreldre også bli kopiert, såvel som deres søsken og foreldre, og så videre inntil hele treet er kopiert. 
I stedet foreslo han et modifisert B-tre uten noen sammenlenkede løv, med en referanseteller tilknyttet hver node i treet, lagret i en ad-hoc assosiativ tabellstruktur, og med visse kompromisser relatert til treets algoritmer for belastningsfordeling for å gjøre dem copy-on-write vennlige. Resultatet ville bli en datastruktur som var egnet for høyytelses objektlagring som kunne utføre copy-on-write snapshots samtidig som de utførte parallelle beregninger på en god måte.
I juli samme år ble ingeniøren Chris Mason ansatt hos Oracle Corporation og begynte å arbeide på et nytt filsystem med muligheter for snapshots basert på B-trær. Dette var begynnelsen på btrfs. Han hadde tidligere arbeidet med det journalførende filsystemet ReiserFS for SuSE. Han arbeidet ikke bare med metadata og fildata, men også rekursivt for å finne plass til å allokere treene selv. Dette gjorde at all traversering og alle modifikasjoner kunne utføres i en enkelt kode, noe som gjorde at copy-on-write, sjekksummer og speiling bare behøvde å implementeres en gang for å dra nytte av hele filsystemet.
Btrfs er strukturert i form av flere lag av slike trær, som alle bruker den samme B-tre implementasjonen. Trærne lagrer generiske elementer, som er sortert med en 136-biter nøkkel. De første 64 bitene av nøkkelen er en unik objekt-id. De midterste 8 bitene er et elementtypefelt, det er hardkodet som et elementfilter under oppslag i treet. Objekter kan ha flere elementer av flere datatyper. De resterende 64-biter benyttes på typespesifikke måter. Elementer for det samme objektet ender derfor opp som naboer til hverandre i treet, ordnet etter type. Ved å velge visse nøkkelverdier som er satt sammen av de resterende 64-biter, kan objekter videre plassere elementer av samme type i en spesiell rekkefølge.
Innvendige trenoder er kort og godt flate lister av nøkkelpeker-par, hvor pekeren er antallet logiske  blokker til en barnenode. Løvnoder inneholder elementnøkler som er pakket inn i fronten av noden og elementdata pakket inn på slutten, med to som vokser mot hverandre ettersom løvet fylles opp.

Rot-treet

Hvert tre opptrer som et objekt i rottreet (eller treet av trerøtter). Enkelte trær, slik som filsystemtrær og loggtrær, har et variabelt antall av instanser. Hver enkelt instans blir gitt sin egen objektid. Trær som er singletoner (datarelokasjons-trær, extent-trær og chunk-trær) tildeles en spesiell, fastsatt objektid ≤ 256. Rottreet opptrer for seg selv som et tre med objektid 1.
Trær refererer til hverandre gjennom objektid. De kan også referere til individuelle noder i andre trær som en triplett av treets objektid, som er nodens nivå innenfor treet og dens venstreplasserte   nøkkelverdi. Slike referanser er uavhengige av hvor treet blir lagret.

Filsystemtreet

Brukersynlige datafiler og kataloger befinner seg i filsystemtreet. Der er et filsystemtre per undervolum. Undervolumer kan nøstes, og i slike tilfeller opptrer de som et katalogelement (beskrevet nedenfor) hvis data er en referanse til det nøstede undervolumets filsystemtre.
Innenfor filsystemtreet har hver datafil og katalogobjekt et inodeelement. Utvidede filattributter og tilgangen til aksesskontrollister blir lagret sammen med det separate elementet.
Innenfor hver katalog, opptrer et aksesspunkt til katalogen som et katalogelement, hvor høyre nøkkelverdi er en CRC-32C hashfunksjon av deres filnavn. Dens data er en lokaliseringsnøkkel, eller en nøkkel til inodeelementet den peker på. Katalogelementet kan således fungere som en indeks for oppslag i inodene, men er ikke brukt til iterasjon fordi de er sortert som en hashfunksjon som utfører en tilfeldig permutasjon.
Dette betyr at brukerprogrammer som gjentatte ganger åpner filer i en stor katalog således vil generere mange flere disksøk mellom filer som ikke er naboer i treet. Dette medfører en nevneverdig svekkelse i ytelsen til andre filsystemer med hashfunksjonordnede kataloger. Dette gjelder blant annet ReiserFS, ext3 (med Htre-indekser aktivert) og ext4, som alle har navn som er krytptiserte ved hjelp av Tiny Encryption Algorithm. For å unngå dette, må hver katalog aksesseres av et katalogindekselement, der de høyre bitene av elementets nøkkelverdi er satt til en katalogteller som inkrementeres for hver ny katalogtilgang. Gjentagelser av disse indekselementene returnerer således katalogaksesser i omtrent samme rekkefølge som de er lagret på disken.
I tillegg til inode-elementer, har filer og kataloger også et referanseelement hvor nøkkelverdien i de høyre bitene er satt til objektid til deres foreldrekatalog. Datadelen av referanseelementet er filnavnet som inoden er kjent under i denne katalogen. Dette gjør det mulig å traversere oppover gjennom kataloghierarkiet og sørger for en måte til å veilede inodene tilbake til veiene i treet.
Filer med faste koblinger i flere kataloger har flere referanseelementer, et for hver foreldrekatalog. Filer med flere faste koblinger i samme katalog pakker alle koblingens filnavn inn i det samme referanse-element. Der var en konstruksjonsfeil som begrenset antallet faste koblinger i samme katalog til det som var mulig å pakke inn i en enkelt treblokk (som standard er blokkstørrelsen 4 Kb, filnavn har en gjennomsnittlig lengde på 8 bytes og hodet til filnavn er gjennomsnittlig 4 bytes. Dette gir mindre enn 350.). Applikasjoner som gjorde mye bruk av flere faste koblinger til samme katalog, slik som Git, Gnus, GMame og BackupPC, viste seg senere å krasje etter at de hadde nådd denne grensen. Denne grensen ble til slutt fjernet (en forandring som ble integrert i versjon 3.7 av Linuxkjernen) ved å introdusere utvidede referanseelementer som kunne holde rede på faste koblinger.

«Extents»

Fildata holdes utenfor treet i extents, som stadig kjører på diskblokker. Størrelsen på en extent-blokk er 4 Kb i størrelse som standard, har ikke hoder og inneholder bare fildata (som kan være komprimert). I komprimerte extents, er individuelle blokker ikke komprimert separat; i stedet omfatter kompresjonen av strømmen den enkelte extent i sin helhet.
Filer har utvidede dataelementer som holder rede på de extents som holder på deres innhold. Den høyre delen av elementets nøkkelverdi er det innledende byte offset til denne extent. Dette gjør det mulig å foreta effektive søk i store filer med mange extents, fordi den korrekte extent for enhver gitt filoffset kan beregnes med bare et enkelt oppslag i treet.
Snapshots og klonede filer deler extents. Når en liten del av en større slik extent blir overskrevet, kan det resulterende copy-on-write skape tre nye extents: En liten en som inneholder de overskrevne data, og to større som har umodifiserte data på hver side av overskrivingen. For å unngå å måtte skrive umodifiserte data på nytt, kan copy-on-write i stedet skape bookend extents, eller extents som kort og godt er deler av eksisterende extents. Extent dataelementer tillater således å inkludere en offset til den extent som de sporer; elementer for bookends er de som har offset som ikke er lik null.
Hvis datafilen er liten nok til å passe innenfor en trenode, blir den i stedet dyttet inn i treet og lagret på innsiden av dataelementets extent. Hver trenode er lagret i sin egen treblokk – en enkelt ukomprimert blokk med et hode. Treblokken blir betraktet som en frittstående enkeltblokk-extent.

Extent allokasjonstre

Extent allokasjonstreet fungerer som et allokasjonskart for filsystemet. I motsetning til andre trær, har ikke elementene i dette treet objektid'er og representerer regioner av plass: Deres nøkkelverdier til venstre og til høyre er den innledende offset og lengden til regionene som de representerer.
Filsystemets inndeler dets allokerte plass i blokkgrupper, som er allokerte regioner av variabel størrelse som alternerer suksessivt mellom de valgte metadata extents (trenoder) og data extents (filinnhold). Standard ratio mellom data og metadata blokkgrupper er 1:2. De er ment å arbeide som Orlov blokkallokatoren og blokkgruppene i ext3 ved å allokere relaterte filer sammen og unngå fragmentering ved å etterlate seg allokasjonsgap mellom gruppene. ext3 blokkgrupper har fastsatte lokasjoner som er beregnet ut fra størrelsen på filsystemet, mens de i btrfs er dynamiske og skapes etter behov. Hver blokkgruppe er assosiert med et blokkgruppe-element. Inodeelementer i filsystemtreet inkluderer en referanse til deres nåværende blokkgruppe.
Extent elementer inneholder en referanse bakover til den trenoden eller den filen som inneholder denne extent. Det kan være flere slike referanser bakover hvis en extent er delt mellom flere snapshots. Hvis der er for mange referanser bakover til at de kan fylle elementet, omdannes de til individuelle extent datareferanse-elementer. Trenoder har i sin tur referanser tilbake til trærne som inneholder dem. Dette gjør det mulig å finne hvilke extents eller trenoder som befinner seg i en region ved å foreta et B-tre range lookup på offsetpar som er knyttet til denne regionen og deretter følge referansene bakover. For relokalisering av data, tillater dette en effektiv traversering oppover fra de relokaliserte blokkene for raskt å finne og ordne alle referanser til disse blokkene, uten å måtte gå gjennom hele filsystemet. Dette gjør det også mulig for filsystemet å effektivt minske, flytte og defragmentere dets lagring online.
Extent allokasjonstreet er, som alle andre trær i filsystemet, copy-on-write. Når man skriver til filsystemet kan man således forårsake en kaskade hvor endrede trenoder og fildata resulterer i at nye extents blir allokert, slik at extenttreet selv blir forandret. For å unngå å skape en tilbakekobling, kan extent trenoder som fortsatt er i minnet men ennå ikke er lagret på disken bli oppdatert på stedet for å reflektere de nye copy-on-write extents.
I teorien gjør extent allokasjonstreet en konvensjonell free-space bitmap unødvendig fordi extent allokasjonstær fungerer som en B-tre versjon av et BSP-tre. I praksis blir likevel et rød-svart tre med bitmaps av sidestørrelse brukt for å øke hastigheten på allokasjonene. Siden versjon 2.6.37 av Linuxkjernen, via mount-opsjonen space_cache, er disse bitmaps vedvarende tilstede på disken som spesielle extents som er unntatt fra sjekksummer og copy-on-write. Extentelementet som sporer disse extents blir lagret i rottreet.

Sjekksumtreet og data scrubbing

CRC-32C sjekksummer blir beregnet for både data og metadata og blir lagret som sjekksumelementer i sjekksumtreet. Det er plass til 256 biter for metadata sjekksummer og opp til en full løvblokk (omkring 4 Kb eller mer) for datasjekksummer. Opsjoner for flere sjekksumalgoritmer er planlagt i fremtiden.
Det er et sjekksumelement per kontinuerlig kjøring av allokerte blokker, med sjekksummer per blokk pakket inn i elementdataene. Hvis det er flere sjekksummer enn det er plass for, flyttes de over til et nytt sjekksumelement i et nytt løv. Hvis filsystemet oppdager en sjekksum-mismatch mens det leser en blokk, prøver det først å hente eller skape en god kopi av denne blokken fra et annet utstyr, hvis intern speiling eller RAID-teknikker er i bruk.
Btrfs kan foreta en online sjekk av hele filsystemet ved å trigge en data scrubbing i bakgrunnen. Denne skanner hele filsystemet, sjekker dets integritet og prøver automatisk å rapportere og reparere enhver skadet blokk, hvis noe slikt finnes underveis.

Loggtreet

En fsync er en forespørsel om å sende modifiserte data øyeblikkelig til et stabilt lagringsmedium. Programmer som ofte benytter fsync (slik som databaser) kan potensielt generere en stor mengde redundante skrivinger ved å tvinge filsystemet til å repetere copy-on-write og således ofte sende forespørsler om modifiserte deler av treet til lagring. For å unngå dette blir det skapt et midlertidig loggtre per undervolum for å journalføre copy-on-write som er trigget av fsync. Loggtrær sporer sitt eget innhold og holder sine egne sjekksumelementer. Deres elementer blir gjennomgått på nytt og slettet under neste skriving av hele treet (hvis der var et systemkrasj) under neste mouting.

Chunk- og utstyrstrær

Utstyrsblokker er inndelt i chunks på 256 Mb eller mer. Chunks kan bli speilet eller stripet over flere former for utstyr. Speilingen eller stripingen er transparent for resten av filsystemet, som bare ser et enkelt, logisk adresserom som chunks blir plassert innenfor.
Alt dette blir sporet av chunktreet, hvor hvert utstyr er representert som et utstyrselement og enhver mapping fra en logisk chunk til den underliggende fysiske chunk blir lagret i et chunk kartleggingselement. Utstyrstreet er det inverse av chunk-treet, og inneholder extentelementer for utstyr som mapper byterekkefølgen til utstyrsblokkene tilbake til de enkelte chunks. Liksom tilfellet er i extent allokasjonstrær, tillater dette btrfs å effektivt begrense eller fjerne utstyr fra volumer ved å lokalisere de chunks som de inneholder (og relokalisere deres innhold).
Filsystemet, chunks og utstyr blir alle tildelt en Universally Unique Identifier (UUID). Hodet til enhver trenode innholder både UUID til dens tilhørende chunk og UUID til filsystemet. De ulike chunks i chunktreet, rottreet, utstyrstreet og extenttreet blir alltid speilet, selv på volumer med et enkelt utstyr. Disse har alle som intensjon å forbedre oddsene for en vellykket berging av data i tilfeller av skadde sektorer.

Relokasjonstrær

Defragmentering, minsking av volumstørrelsen og rebalanseting krever at extents blir relokalisert. Likevel, ved å foreta en enkel copy-on-write på den relokaliserte extent, vil man bryte delingen mellom snapshots og brukerens diskområde. For å bevare delingen, benyttes en oppdater-og-swap algoritme, hvor et spesielt relokasjonstre fungerer som et diskområde for de rammede metadata. Den extent som skal relokaliseres blir først kopiert til dens destinasjon. Ved å følge de tilbakeførende referansene oppover gjennom undervolumets filsystemtre, blir metadata som peker på de gamle extent progressivt oppdatert til å peke på de nye; ethvert nylig oppdatert element blir lagret i relokasjonstreet. Når oppdateringen er fullført, blir elementene i relokasjonstreet swappet med deres motparter i det undervolum som er påvirket, og relokasjonstreet blir forkastet.

Superblokker

Alle filsystemets trær, inkludert chunktreet selv, er lagret i chunks, noe som skaper et potensielt høna og egget-problem når man mounter filsystemet. Når man foretar en oppstart av en mounting, må en liste med fysiske adresser til chunks som tilhører disse chunks og rottrærne bli lagret i superblokken.
Speilinger av superblokker blir lagret på faste lokasjoner: 64 Kb i hver utstyrsblokk, med tilleggskopier ved 64 Mb, 256 Gb og 1 Pb. Når et superblokk-speil blir oppdatert, inkrementeres dets generasjonsnummer. Under mounting brukes kopien med det høyeste generasjonstallet. Alle speil av superblokker blir oppdatert ved siden av hverandre, bortsett fra i Solid state drive-modus som alternerer oppdateringer blant speilene for å sørge for wear levelling.

Bidragsytere

Btrfs 1.0, som hadde et ferdig diskformat, var opprinnelig ment å bli lansert i slutten av 2008. En utviklingsversjon av btrfs ble integrert i versjon 2.6.29 av Linuxkjernen den 23. mars 2009. Første stabile versjon ble lansert 29. mars 2013 i versjon 3.10 av Linuxkjernen.
Den 22. juli 2011 ble btrfs sin automatiske defragmentering (gjennom opsjonen autodefrag) og data scrubbing integrert i versjon 3.0 av Linuxkjernen. Ved siden av Mason ved Oracle, bidro Miao Xie ved Fujitsu til filsystemets ytelsesforbedringer i versjon 3.0 av Linuxkjernen.
I juni 2012 forlot Chris Mason Oracle Corporation for å arbeide for Fusion-io. Et år senere forlot han også dette selskapet sammen med Josef Bacik, for å arbeide for Facebook. I begge selskapene har Mason fortsatt arbeidet med btrfs.

SUSE Linux

Den første Linuxdistribusjonen som tok i bruk btrfs som standard filsystem var SUSE Linux Enterprise Server versjon 12.0, som ble lansert 10. oktober 2014. Deretter fulgte OpenSUSE versjon 13.2 den 14. november 2014. Dette er kanskje naturlig, sett i lys av den aktive rollen som SuSE har spilt under utviklingen av btrfs. Andre distribusjoner har lenge hatt støtte for btrfs, uten at «støtte» i denne sammenheng betyr standard.

Fedora

Verd å merke seg er distribusjonene til selskapet Red Hat, som også har spilt en aktiv rolle under utviklingsprosessen. Eksperimentell støtte for filsystemet Btrfs ble innført i Fedora versjon 11 «Leonidas» den 9. juni 2009, og det kunne aktiveres med kommandoen IcantbelieveitsnotBTR ved oppstart. I versjon 26, som ble lansert 11. juli 2017, er det ennå ikke blitt standard.

Red Hat Enterprise Linux

Likeledes ble støtte for btrfs lansert sammen med Red Hat Enterprise Linux (RHEL) versjon 6 «Santiago» den 10. november 2010. Også i RHEL versjon 7 «Maipo», som ble lansert 10. juni 2014, ble det støttet, men var ennå ikke blitt standard. I stedet ble det journalførende filsystemet XFS gjort til standard, som erstatning for ext4.

Oracle Linux

Verd å merke seg er også Oracle Linux. Det blir utviklet av Oracle Corporation, som også var blant selskapene som stod bak btrfs. Oracle Linux er basert på RHEL, og tilhører samme familie av operativsystemer.  Versjon 7, som ble lansert 23. juli 2014, har støtte for btrfs, men benytter XFS som standard.

Andre distribusjoner

Av andre store Linuxdistribusjoner er det likedan. Slackware innførte støtte for btrfs i versjon 13.37 som ble lansert 25. april 2011; i versjon 14.2, som ble lansert 30. juni 2016, er det ennå ikke blitt standard. Debian innførte støtte for btrfs i versjon 6.0 «Squeeze», som ble lansert 6. februar 2011; i versjon 8.0 «Jessie», som ble lansert 15. april 2015, var det ennå ikke blitt standard. Ubuntu innførte støtte i versjon 10.10 «Maverick Meerkat», som ble lansert 10. oktober 2010; i versjon 16.04 «Xenial Xerus», som ble lansert 21. april 2016, er det ennå ikke blitt standard.

ReactOS

Den 17. mai 2016 ble støtte for Btrfs introdusert i versjon 0.4.1 av ReactOS.