Btrfs

Btrfs, en forkortelse for B-tree file system, uttalt butter F S,Oracle Corporation: Oracle Linux 7 with Q&A with Wim Coekaerts , 2014 better F S,Amanda McPherson: A Conversation with Chris Mason on BTRfs: the next generation file system for Linux , Linux Foundation, 22. juni 2009 eller b-tree F S,Valerie Henson: Chunkfs: Fast file system check and repair, 31. januar 2008 er et copy-on-write og journalførende filsystem for Linux. Btrfs er etterfølgeren til filsystemet ext4, og løser problemer knyttet til pooling, snapshots, sjekksummer og datasystemer hvor mange forskjellige typer innmatningsutstyr er integrerte. Filsystemet er POSIX-kompatibelt.SysadminGuide, wiki.kernel.org, 11. juni 2016

Blant andre egenskaper kan nevnes støtte for defragmentering (deriblant  automatisk defragmentering gjennom opsjonen autodefrag),1.1. Btrfs: Automatic defragmentation, scrubbing, performance improvements, Linux 3.0, kernelnewbies.org, 22. juli 2012 data scrubbing, online endring av størrelsen på diskvolumer,5.5 Resizing a Btrfs File System, Oracle® Linux Administrator's Solutions Guide for Release 6, 2016 offline filsystemsjekk (fsck),Btrfsck, wiki.kernel.org, 6. juli 2015 transparent datakompresjon (zlib og Lempel-Ziv-Oberhumer)Compression, wiki.kernel.org, 15. juli 2015Btrfs: add support for inode properties, git.kernel.org, 7. januar 2014 av datafiler eller logiske disker, Union mount,Changelog, wiki.kernel.org, 5. oktober 2016 etc. Btrfs støtter harddisker på inntil 16 exbibyte (EiB) og filstørrelser på inntil 16 exbibyte (EiB).Large File Support in Linux, SUSE Storage Administration Guide, 14. mars 2016

Datastrukturen til btrfs er et B-tre, en selvbalanserende tredatastruktur, som sorterer data og tillater søking, sekvensiell aksess, innsettelse og sletting i en logaritmisk tid.Btrfs design, wiki.kernel-org, 11. januar 2015

Datatrukturen ble beskrevet i forbindelse med filsystemer av Ohad Roed, en forsker ved IBM, under konferansen til USENIX i juni 2007.Ohad Rodeh: B-trees, Shadowing, and Clones, USENIX Linux Storage & Filesystem Workshop, 2007Ohad Rodeh: B-trees, shadowing, and clones , Association for Computing Machinery (ACM) Transactions on Storage, Volume V, No. N, august 2007 I juli samme år ble ingeniøren Chris Mason ansatt hos Oracle Corporation og begynte å arbeide på et nytt filsystem basert på B-trær.Michael Larabel: Lead Btrfs FIle-System Developers Join Facebook. phoronix.com, 4. desember 2013 Dette var begynnelsen på btrfs. Han hadde tidligere arbeidet med det journalførende filsystemet ReiserFS for SuSE.Interview: Chris Mason about Btrfs, wordpress.com, 7.august 2007 Andre bidragsytere til utviklingen av btrfs har vært Facebook, Fujitsu, Fusion-io, Intel, Linux Foundation, Netgear, Red Hat, Strato AG og SuSE.Contributors, wiki.kernel.org, 9. september 2016

En utviklingsversjon ble integrert i versjon 2.6.29 av Linuxkjernen den 23. mars 2009.Kernel Newbies: Linux 2.6.29, 23. mars 2009 Første stabile versjon ble lansert 29. mars 2013 i versjon 3.10 av Linuxkjernen.Kernel Newbies: Linux 3.10, 30. juni 2013 

Filsystemet er fri og åpen programvare og er lisensiert under GNU General Public License versjon 2, sammen med Linuxkjernen.Linus Torvalds: COPYING, kernel.org, besøkt 9. oktober 2016

Oppbygning
Journalførende filsystem

Det er viktig for forståelsen å ikke bare behandle btrfs isolert, men også se på den helhetlige sammenheng som btrfs oppstod innenfor. 
Liksom forgjengerne ext3 og ext4, er btrfs et journalførende filsystem. Dette betyr at filsystemet lagrer endringer av datafiler i en journal, før endringene blir foretatt. Ved systemkrasj og strømbrudd, er slike filsystemer lettere å gjenopprette og mindre sårbare for skader.

Linuxkjernen inneholder flere slike journalførende filsystemer, som har hatt stor innflytelse på utviklingen av btrfs. Av disse vil vi fremheve XFS, ReiserFS, Reiser4, Journaled File System (JFS), ZFS og OpenZFS:

 XFS er et 64-biter filsystem som ble utviklet av Silicon Graphics Inc. (SGI) i 1993."xFS: the extension of EFS - "x" for to-be-determined (but the name stuck)" , xfs.org, XFS User Guide. A guide for XFS filesystem users and administrators. Edition 0, 2006 Det var standard filsystem i operativsystemet IRIX fra versjon 5.3 i desember 1994. I mai 2001 ble XFS tilføyd Linuxkjernen i form av patcher fra SGI,Russel Ingram: Linux + XFS HOWTO. Linux on Steroids, tldp.org, 12. mai 2002 før det ble integrert i kjernens versjon 2.6 den 18. desember 2003.

 ReiserFS ble utviklet av den amerikanske programmereren Hans Reiser og ble innlemmet i versjon 2.4.1 av Linuxkjernen den 30. januar 2001.

 Hans Reiser utviklet også etterfølgeren Reiser4.Future Vision - Reiser4, reiser4.wiki.kernel.org, 25. august 2016 Dette er blitt sponset av forvaltningsorganet Defense Advanced Research Projects Agency (DARPA)Credits - Reiser4 FS, reiser4.wiki.kernel.org, 18. november 2009 så vel som av ApplianceWare, BigStorage, Inc., SuSE og Linspire, og ble en del av versjon 3.15 av Linuxkjernen den 14. august 2014.

 Journaled File System (JFS) ble utviklet av IBM og lansert for operativsystemet AIX i februar 1990.JFS, wiki.archlinux.org, 30. august 2016 I september 1994 ble det også tatt i bruk i OS/2 3.0 «Warp».OS/2 Warp Installation and Update Manual, IBM En rekke Linuxdistribusjoner støtter eller har støttet JFS.

 ZFS (Zettabyte File System) ble utviklet av Sun Microsystems for operativsystemet OpenSolaris i 2005.ZFS: The Last Word in Filesystems, Jeff Bonwick's blog, Oracle Corporation, 31. oktober 2005 Det ble i utgangspunktet lisensiert under en åpen kildekodelisens, men Oracle Corporation endret denne i 2010 til en proprietær lisens for operativsystemet Solaris.Ryan Paul: Uptake of native Linux ZFS port hampered by license conflict, arstechnica.com, 6. september 2009 Grunnet lisensieringsproblemer er det ikke mulig å videreutvikle ZFS for Linuxkjernen,Dustin Kirkland: ZFS Licensing and Linux, ubuntu.com, 18. februar 2016 selv om en rekke Linuxdistribusjoner har hatt støtte for det.ZFS On Linux, Lawrence Livermore National Laboratory OpenZFS oppstod som en fork av ZFS i 2010,Bryan Cantrill: Fork Yeah! The rise and Development of Illumos, slideshare.net, 8. desember 2011 og støttes også av Linuxkjernen. Lisensieringsproblemene med ZFS har likevel helt klart bidratt til at btrfs vokste frem som et alternativ.ZFS Vs. BTRFS, reddit.com, 2015

XFS,XFS Filesystem Structure. Documentation of the XFS filesystem on-disk structures. Edition 0 , xfs.org ReiserFSFlorian Buchholz: The structure of the Reiser file system, jcoppens.com, 17. september 2008 og JFSJFS, Archwiki, 30. august 2016 er implementert som B+ trær. Denne datastrukturen kan betraktes som en variant av B-trær, hvor hver node bare inneholder nøkler og ikke nøkkelpar. B+ trær er vanlig innenfor filsystemer.

Reiser4 er implementert i form av et B* tre.V4, reiser4.wiki.kernel.org, 25. august 2016 Et B* tre er en variant av et B-tre, som foretar en belastningsfordeling mellom nabonoder internt i treet, for å pakke dem tettere.

Som vi skal se, kan B+ trær ikke brukes på btrfs, fordi det er et copy-on-write filsystem. I stedet er btrfs implementert som et B-tre. Også ZFS og avleggeren OpenZFS er copy-on-write filsystemer, men de er implementert som hashtabeller. ZFS har mange likheter med btrfs på andre områder, og kunne ha blitt en konkurrent, hvis det ikke hadde vært for lisensieringsproblemene som er knyttet til det.

B-trærs logaritmiske tidsaspekt

Datastrukturen til btrfs er et B-tre, en selvbalanserende tredatastruktur, som sorterer data og tillater søking, sekvensiell aksess, innsettelse og sletting i en logaritmisk tid. Et søk gjennom en sortert tabell med  dataposter kan gjøres med omkring  sammenligninger. Hvis tabellen har 1 000 000 dataposter, kan en spesifikk datapost bli lokalisert etter maksimum 20 sammenligninger: .

Informatikeren Douglas Earl Comer har angitt følgende beste og verste tilfeller av høyden på et B-tre:
La h være høyden i et klassisk B-tre, n > 0 være antall innganger i treet, og m være maksimalt antall barn som en node kan ha. Hver node kan da ha maksimum m−1 nøkler. Gjennom et induksjonsbevis kan vi da vise at høyden til treet, med alle sine noder fylt, har n= mh+1−1 innganger. I det beste tilfellet er høyden av B-treet:



La d være minimum antall barn som en intern node (ikke roten) kan ha. For et ordinært B-tre, er d=⌈m/2⌉. Det verste tilfellet av høyden på et tre (hvor roten har høyde 0), blir derfor:



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.Valerie Aurora: A short history of btrfs, LWN.net, 2009

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.Btrfs Main Page, btrfs.wiki.kernel.org, 5. oktober 2016

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 inneholder 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:Sean Bartell: Re: Restoring BTRFS partition, linux-btrfs, 20. april 2010 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.

Egenskaper

I versjon 3.14 av Linuxkjernen, implementerer btrfs følgende egenskaper:2. Features, btrfs.wiki.kernel.org, 5. oktober 2016Changelog, btrfs.wiki.kernel.org, 5. oktober 2016

 Et for det meste selvhelberedende filsystem i mange sammenhenger, på grunn av naturen til copy-on-write
 Støtte for online defragmentering, og automatisk defragmentering gjennom opsjonen autodefrag
 Støtte for online endring av størrelsen på diskvolumer
 Online tilføyelse og fjerning av utstyrsblokker (en type utstyrsfiler)
 Online balansering (flytting av objekter mellom utstyrsblokker for å oppnå belastningsfordeling)
 Offline filsystemsjekk (fsck)
 Online data scrubbing for å finne feil, fikse dem automatisk og skape redundante kopier av filer
 RAID 0, RAID 1 og RAID 10
 Undervolumer (en eller flere mountbare rotkataloger med hver sin diskpartisjon)
 Transparent datakompresjon (zlib eller Lempel-Ziv-Oberhumer), konfigurerbar for hver datafil eller hvert volum.
 Snapshots eller copy-on-write kloner av undervolumer
 Filkloner (copy-on-write på individuelle filer, eller bytestrømmer i disse)
 Sjekksummer på data og metadata (CRC-32C)
 På stedet konvertering fra ext3/ext4 til btrfs (uten rollback)
 Union mounting av lagringsenheter kjent som filsystem-seeding
 Sletting av blokker (frigjøre plass på enkelte vitualiserte oppsetninger og forbedret wear leveling på Solid state drives med TRIM)
 Send/receive (bruke verktøyet diff til å lagre forskjeller mellom snapshots i en binærstrøm)
 Hierarkisk quotas per undervolum

Kloning

Undervolumer og snapshots

Send/motta

Quotagrupper

På stedet ext2/3/4 konvertering

Historie

Bidragsytere
Btrfs 1.0, som hadde et ferdig diskformat, var opprinnelig ment å bli lansert i slutten av 2008.Development timeline. From btrfs Wiki, wiki.kernel.org 11. desember 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.Thorsten Leemhuis: Kernel Log: Coming in 3.0 (Part 2) - Filesystems, 21. juni 2011
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.Michael Larabel: Lead Btrfs FIle-System Developers Join Facebook, Phoronix, 4. desember 2013Sam Varghese: Facebook lures top Btrfs hackers, ITWire, 27. november 2013

Linuxdistribusjoner
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.SUSE Linux Enterprise Server 12 Release Notes, suse.com, 10. oktober 2014 Deretter fulgte OpenSUSE versjon 13.2 den 14. november 2014.Douglas DeMaio: What to expect from Btrfs on openSUSE 13.2?, opensuse.org, 12. november 2014 Dette er kanskje naturlig, sett i lys av den aktive rollen som SuSE har spilt i 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 i 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.Red Hat: Chapter 4. Btrfs, Red Hat Enterprise Linux 6. ⁠6.0 Release Notes. Release Notes for Red Hat Enterprise Linux 6, 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.Martin Loschwitz: Red Hat Enterprise Linux 7 tested, Linux Magazine, Issue 166/2014, 2014 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.3.4 Installing a System With a Btrfs Root File System, Oracle® Linux. Installation Guide for Release 7, Oracle Corporation, 2014

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;Slackware Release Announcement, slackware.com, 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;How to install btrfs-tools on Debian 6 (Squeeze), 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;Christopher Tozzi: Ubuntu 10.10s New File System: btrfs , The VAR Guy, 2. august 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.Z98: ReactOS 0.4.1 Released, 17. mai 2016

Microsoft Windows 10

Noter

Referanser
Comer 1979
Comer 1979, side 129
Giampaolo 1998
Ramakrishnan 2002

 Litteratur 




 Eksterne lenker 


Kategori:Linuxkjernens filsystemer
Kategori:Facebook
Kategori:Fujitsu
Kategori:Fusion-io
Kategori:Intel-produkter
Kategori:Oracle Corporation
Kategori:Red Hat
Kategori:SUSE Linux
Kategori:Programvare fra 2013