Btrfs

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk
Btrfs (B-tree file system)
SkaperChris Mason; Oracle Corporation
UtviklerFacebook, Fujitsu, Fusion-io, Intel, Linux Foundation, Netgear, Oracle Corporation, Red Hat, Strato AG og SUSE.
Utgittutvikling: 23. mars 2009; 8 år siden (2009-03-23) i versjon 2.6.29 av Linuxkjernen.
stabil: 29. juli 2013; 4 år siden (2013-07-29) i versjon 3.10 av Linuxkjernen.
StatusAktiv
OperativsystemLinux, ReactOS, Microsoft Windows
Skrevet iC
TypeFilsystem
LisensGNU General Public License versjon 2
Nettstedbtrfs.wiki.kernel.org/
Forgjengerext4

Btrfs, en forkortelse for B-tree file system, uttalt butter F S,[1] better F S,[2] eller b-tree F S,[3] 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.[4] Filsystemet er POSIX-kompatibelt.[5]

Blant andre egenskaper kan nevnes støtte for defragmentering (deriblant automatisk defragmentering gjennom opsjonen autodefrag),[6] data scrubbing,[6] online endring av størrelsen på diskvolumer,[7] offline filsystemsjekk (fsck),[8] transparent datakompresjon (zlib og Lempel-Ziv-Oberhumer)[9][10] av datafiler eller logiske disker, Union mount,[11] etc. Btrfs støtter harddisker på inntil 16 exbibyte (EiB) og filstørrelser på inntil 16 exbibyte (EiB).[12]

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.[13]

Datatrukturen ble beskrevet i forbindelse med filsystemer av Ohad Roed, en forsker ved IBM, under konferansen til USENIX i juni 2007.[14][15] 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.[16] Dette var begynnelsen på btrfs. Han hadde tidligere arbeidet med det journalførende filsystemet ReiserFS for SuSE.[17] Andre bidragsytere til utviklingen av btrfs har vært Facebook, Fujitsu, Fusion-io, Intel, Linux Foundation, Netgear, Red Hat, Strato AG og SuSE.[18]

En utviklingsversjon ble integrert i versjon 2.6.29 av Linuxkjernen den 23. mars 2009.[19] Første stabile versjon ble lansert 29. mars 2013 i versjon 3.10 av Linuxkjernen.[20]

Filsystemet er fri og åpen programvare og er lisensiert under GNU General Public License versjon 2, sammen med Linuxkjernen.[21]

Oppbygning[rediger | rediger kilde]

Journalførende filsystem[rediger | rediger kilde]

Utdypende artikler: Journalførende filsystemext3 og ext4

Det er viktig for forståelsen å ikke bare behandle btrfs isolert, men også se på den helhetlige sammenheng som btrfs oppstod innenfor.

Skjermbilde av Linuxdistribusjonen Elive. Elive benyttet filsystemet ReiserFS.

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.[22][23]

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.[24] Det var standard filsystem i operativsystemet IRIX fra versjon 5.3 i desember 1994.[24] I mai 2001 ble XFS tilføyd Linuxkjernen i form av patcher fra SGI,[25] før det ble integrert i kjernens versjon 2.6 den 18. desember 2003.[a]
  • ReiserFS ble utviklet av den amerikanske programmereren Hans Reiser og ble innlemmet i versjon 2.4.1 av Linuxkjernen den 30. januar 2001.[29][b]
  • Hans Reiser utviklet også etterfølgeren Reiser4.[39] Dette er blitt sponset av forvaltningsorganet Defense Advanced Research Projects Agency (DARPA)[40] så vel som av ApplianceWare, BigStorage, Inc., SuSE og Linspire,[40] og ble en del av versjon 3.15 av Linuxkjernen den 14. august 2014.
Skjermbilde av Mandriva Linux 2010. Denne distribusjonen benyttet filsystemet Journaled File System.
  • Journaled File System (JFS) ble utviklet av IBM og lansert for operativsystemet AIX i februar 1990.[41] I september 1994 ble det også tatt i bruk i OS/2 3.0 «Warp».[42] En rekke Linuxdistribusjoner støtter eller har støttet JFS.[43][c]
  • ZFS (Zettabyte File System) ble utviklet av Sun Microsystems for operativsystemet OpenSolaris i 2005.[44] Det ble i utgangspunktet lisensiert under en åpen kildekodelisens, men Oracle Corporation endret denne i 2010 til en proprietær lisens for operativsystemet Solaris.[45] Grunnet lisensieringsproblemer er det ikke mulig å videreutvikle ZFS for Linuxkjernen,[45][46] selv om en rekke Linuxdistribusjoner har hatt støtte for det.[47][d] OpenZFS oppstod som en fork av ZFS i 2010,[48] og støttes også av Linuxkjernen. Lisensieringsproblemene med ZFS har likevel helt klart bidratt til at btrfs vokste frem som et alternativ.[49]

XFS,[50] ReiserFS[51] og JFS[52] 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.[e]

Reiser4 er implementert i form av et B* tre.[58] Et B* tre er en variant av et B-tre, som foretar en belastningsfordeling mellom nabonoder internt i treet, for å pakke dem tettere.[59]

Som vi skal se, kan B+ trær ikke brukes på btrfs, fordi det er et copy-on-write filsystem.[14] I stedet er btrfs implementert som et B-tre.[14] 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[rediger | rediger kilde]

Utdypende artikkel: B-tre

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.[13] 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:[60]

Et B-tre av femte orden.

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[rediger | rediger kilde]

Datatrukturen ble beskrevet i forbindelse med filsystemer av Ohad Roed, en forsker ved IBM, under konferansen til USENIX i juni 2007.[14] I sitt opprinnelige forslag drøftet Rodeh B+ trær, som er i utbredt bruk som datastrukturer i databaser.[f] 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.

Hovedkvarteret til Oracle Corporation bygning 300, i Redwood Shores, Redwood City, California. Chris Mason, som var den opprinnelige arkitekten til btrfs, var ansatt av Oracle Corporation.

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.[14]

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.[16] Dette var begynnelsen på btrfs. Han hadde tidligere arbeidet med det journalførende filsystemet ReiserFS for SuSE.[17] 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.[63]

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.[63][64]

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.[63]

Rot-treet[rediger | rediger kilde]

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[rediger | rediger kilde]

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.

Logoen til Fujitsu. Det japanske multinasjonale IT-konsernet Fujitsu Limited (nihongo: 富士通株式会社) er blant de som har bidratt til utviklingen av btrfs.

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,[65] ext3 (med Htre-indekser aktivert[66]) 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.[67] Denne grensen ble til slutt fjernet[68] (en forandring som ble integrert i versjon 3.7 av Linuxkjernen[69]) ved å introdusere utvidede referanseelementer som kunne holde rede på faste koblinger.

«Extents»[rediger | rediger kilde]

Raleigh's Red Hat Tower. Det amerikanske programvareselskapet Red Hat har hatt en sentral rolle i utviklingen av btrfs.

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.[64]

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[rediger | rediger kilde]

Extent allokasjonstreet fungerer som et allokasjonskart for filsystemet. I motsetning til andre trær, har ikke elementene i dette treet objektid'er og representer regioner av plass: Deres nøkkelverdier til venstre og til høyre er den innledende offset og lengden til regionene som de representerer.

Logoer til SuSe. Det tyske programvareselskapet SuSE (Software und Systementwicklung) er en av bidragsyterene til btrfs

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.[64]

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,[70] 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[rediger | rediger kilde]

Utdypende artikkel: Datakorrupsjon

En Intel Core i7 920 mikroprosessor. Intel Corporation er mest kjent for å produsere mikroprosessorer, men har også en avdeling for programvareutvikling og har vært en av bidragsyterne til btrfs.

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.[71][72]

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.[73][74]

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.[73][75]

Loggtreet[rediger | rediger kilde]

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[rediger | rediger kilde]

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.

Det globale amerikanske nettverkselskapet NETGEAR, Inc. er blant bidragsyterne til btrfs

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[rediger | rediger kilde]

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.[76]

Superblokker[rediger | rediger kilde]

Strato AG, et datterselskap av Deutsche Telekom, er blant dem som har deltatt i utviklingen av btrfs

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.[77]

Speilinger av superblokker blir lagret på faste lokasjoner:[78] 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[rediger | rediger kilde]

I versjon 3.14 av Linuxkjernen, implementerer btrfs følgende egenskaper:[71][79]

Kloning[rediger | rediger kilde]

Undervolumer og snapshots[rediger | rediger kilde]

Send/motta[rediger | rediger kilde]

Quotagrupper[rediger | rediger kilde]

På stedet ext2/3/4 konvertering[rediger | rediger kilde]

Historie[rediger | rediger kilde]

Bidragsytere[rediger | rediger kilde]

Btrfs 1.0, som hadde et ferdig diskformat, var opprinnelig ment å bli lansert i slutten av 2008.[84] En utviklingsversjon av btrfs ble integrert i versjon 2.6.29 av Linuxkjernen den 23. mars 2009.[19] Første stabile versjon ble lansert 29. mars 2013 i versjon 3.10 av Linuxkjernen.[20]

Den 22. juli 2011 ble btrfs sin automatiske defragmentering (gjennom opsjonen autodefrag) og data scrubbing integrert i versjon 3.0 av Linuxkjernen.[6] Ved siden av Mason ved Oracle, bidro Miao Xie ved Fujitsu til filsystemets ytelsesforbedringer i versjon 3.0 av Linuxkjernen.[85]

SUSE Linux 10.0 med skrivebordsmiljøet GNOME. OpenSUSE 13.2 var blant de første Linuxdistribusjoner som benyttet Btrfs som standard.

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.[86][87]

Linuxdistribusjoner[rediger | rediger kilde]

Red Hat Enterprise Linux versjon 6.0 «Santiago» innførte støtte for btrfs
Oracle Linux Server 6. Oracle Linux innførte også støtte for btrfs i versjon 6.0

SUSE Linux[rediger | rediger kilde]

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.[88] Deretter fulgte OpenSUSE versjon 13.2 den 14. november 2014.[89] 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[rediger | rediger kilde]

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.[90] I versjon 26, som ble lansert 11. juli 2017, er det ennå ikke blitt standard.

Red Hat Enterprise Linux[rediger | rediger kilde]

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

Oracle Linux[rediger | rediger kilde]

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.[28]

Andre distribusjoner[rediger | rediger kilde]

Av andre store Linuxdistribusjoner er det likedan. Slackware innførte støtte for btrfs i versjon 13.37 som ble lansert 25. april 2011;[92] 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;[93] 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;[94] i versjon 16.04 «Xenial Xerus», som ble lansert 21. april 2016, er det ennå ikke blitt standard.

ReactOS[rediger | rediger kilde]

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

Microsoft Windows 10[rediger | rediger kilde]

Noter[rediger | rediger kilde]

Type numrering
  1. ^ Gentoo var i 2002 den første Linuxdistribusjonen som benyttet XFS som standard;[26] filsystemet er også standard i Red Hat Enterprise Linux 7.0[27] og Oracle Linux 7.0.[28]
  2. ^ ReiserFS har vært standard i distribusjonene Elive, FTOSX Desktop,[30] Xandros,[31] Kurumin,[32] Libranet,[33] Linspire,[34] GoboLinux,[35] Slackware[36] og YOPER.[37][29] ReiserFS var også standard i SUSE Linux Enterprise Server og SUSE Linux Enterprise Desktop, inntil Novell den 12. oktober 2006 besluttet seg for å gå over til ext3.[38]
  3. ^ En rekke Linuxdistribusjoner støtter eller har støttet JFS,[43] deriblant ALT Linux, Arch Linux, Debian, Gentoo, Knoppix, Mandriva Linux, Onyx, Red Hat Linux, Slackware, SUSE Linux, Turbolinux og United Linux,[43] og det var standard i den tidligere distribusjonen Shark Linux.[43]
  4. ^ Eksempler Linuxdistribusjoner som benytter eller har benyttet ZFS er Arch Linux, Debian, Fedora, Gentoo, OpenSUSE, Red Hat Enterprise Linux, CentOS og Ubuntu [47].
  5. ^ Av andre filsystemer som bruker B+ trær kan vi nevne Novell Storage Services (NSS)[53], NTFS (brukt til indeksering),[54] ReFS,[55] Be File System (i BeOS)[56] og i HAMMER,[57] som er filsystemet til DragonFly BSD.
  6. ^ Blant databaser som bruker B+ trær kan nevnes: IBM DB2,[61] IBM Informix,[61] Microsoft SQL Server,[61] Oracle Database,[61] Sybase ASE[61] og SQLite.[62]

Referanser[rediger | rediger kilde]

  1. ^ Oracle Corporation: Oracle Linux 7 with Q&A with Wim Coekaerts, 2014
  2. ^ Amanda McPherson: A Conversation with Chris Mason on BTRfs: the next generation file system for Linux Arkivert 20120624090157 hos WebCite, Linux Foundation, 22. juni 2009
  3. ^ Valerie Henson: Chunkfs: Fast file system check and repair, 31. januar 2008
  4. ^ McPherson, Amanda (22. juni 2009). «A Conversation with Chris Mason on BTRfs: the next generation file system for Linux». Linux Foundation. Arkivert fra originalen 2012-06-24. Besøkt 1. september 2009. 
  5. ^ SysadminGuide, wiki.kernel.org, 11. juni 2016
  6. ^ a b c d 1.1. Btrfs: Automatic defragmentation, scrubbing, performance improvements, Linux 3.0, kernelnewbies.org, 22. juli 2012
  7. ^ a b 5.5 Resizing a Btrfs File System, Oracle® Linux Administrator's Solutions Guide for Release 6, 2016
  8. ^ a b Btrfsck, wiki.kernel.org, 6. juli 2015
  9. ^ a b Compression, wiki.kernel.org, 15. juli 2015
  10. ^ a b Btrfs: add support for inode properties, git.kernel.org, 7. januar 2014
  11. ^ a b Changelog, wiki.kernel.org, 5. oktober 2016
  12. ^ Large File Support in Linux, SUSE Storage Administration Guide, 14. mars 2016
  13. ^ a b Btrfs design, wiki.kernel-org, 11. januar 2015
  14. ^ a b c d e Ohad Rodeh: B-trees, Shadowing, and Clones, USENIX Linux Storage & Filesystem Workshop, 2007
  15. ^ Ohad Rodeh: B-trees, shadowing, and clones, Association for Computing Machinery (ACM) Transactions on Storage, Volume V, No. N, august 2007
  16. ^ a b Michael Larabel: Lead Btrfs FIle-System Developers Join Facebook. phoronix.com, 4. desember 2013
  17. ^ a b Interview: Chris Mason about Btrfs, wordpress.com, 7.august 2007
  18. ^ Contributors, wiki.kernel.org, 9. september 2016
  19. ^ a b Kernel Newbies: Linux 2.6.29, 23. mars 2009
  20. ^ a b Kernel Newbies: Linux 3.10, 30. juni 2013
  21. ^ Linus Torvalds: COPYING, kernel.org, besøkt 9. oktober 2016
  22. ^ Jones, M Tim (2008-06-04), Anatomy of Linux journaling file systems, IBM DeveloperWorks, http://www.ibm.com/developerworks/library/l-journaling-filesystems/index.html, besøkt 2009-04-13 
  23. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014-01-21), Crash Consistency: FSCK and Journaling, Arpaci-Dusseau Books, http://pages.cs.wisc.edu/~remzi/OSTEP/file-journaling.pdf 
  24. ^ a b "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
  25. ^ Russel Ingram: Linux + XFS HOWTO. Linux on Steroids, tldp.org, 12. mai 2002
  26. ^ Gentoo Linux Reloaded, O'Reilly Linux Devcenter, 2016
  27. ^ a b c Martin Loschwitz: Red Hat Enterprise Linux 7 tested, Linux Magazine, Issue 166/2014, 2014
  28. ^ a b 3.4 Installing a System With a Btrfs Root File System, Oracle® Linux. Installation Guide for Release 7, Oracle Corporation, 2014
  29. ^ a b ReiserFS, Data Recovery Glossary, DiskInternals, ltd., 2016
  30. ^ FTOSX Desktop, DistroWatch, 1. juli 2016
  31. ^ N. Heron: Review of Xandros Desktop 1.0, OSNews.com, 25. november 2002
  32. ^ Kirumin Linux, DistroWatch, 1. juli 2016
  33. ^ Libranet GNU/Linux, DistroWatch, 1. juli 2016
  34. ^ Linspire, DistroWatch, 1. juli 2016
  35. ^ GoboLinux, DistroWatch, 10. oktober 2016
  36. ^ Slackware Linux, DistroWatch, 10. oktober 2016,
  37. ^ Yoper Linux, DistroWatch, 1. juli 2016
  38. ^ What are reiserfs?, liquisearch.com
  39. ^ Future Vision - Reiser4, reiser4.wiki.kernel.org, 25. august 2016
  40. ^ a b Credits - Reiser4 FS, reiser4.wiki.kernel.org, 18. november 2009
  41. ^ JFS, wiki.archlinux.org, 30. august 2016
  42. ^ OS/2 Warp Installation and Update Manual, IBM
  43. ^ a b c d JFS for Linux, jfs.sourceforge.net
  44. ^ ZFS: The Last Word in Filesystems, Jeff Bonwick's blog, Oracle Corporation, 31. oktober 2005
  45. ^ a b Ryan Paul: Uptake of native Linux ZFS port hampered by license conflict, arstechnica.com, 6. september 2009
  46. ^ Dustin Kirkland: ZFS Licensing and Linux, ubuntu.com, 18. februar 2016
  47. ^ a b ZFS On Linux, Lawrence Livermore National Laboratory
  48. ^ Bryan Cantrill: Fork Yeah! The rise and Development of Illumos, slideshare.net, 8. desember 2011
  49. ^ ZFS Vs. BTRFS, reddit.com, 2015
  50. ^ XFS Filesystem Structure. Documentation of the XFS filesystem on-disk structures. Edition 0, xfs.org
  51. ^ Florian Buchholz: The structure of the Reiser file system, jcoppens.com, 17. september 2008
  52. ^ JFS, Archwiki, 30. august 2016
  53. ^ We are redesigning an application that currently stores..., Micro Focus, 31. oktober 2002
  54. ^ NTFS INDX Parsing, williballenthin.com
  55. ^ Michael Larabel: Microsoft's ReFS File-System: Competitor To Btrfs?, phoronix, 17. januar 2012
  56. ^ Giampaolo 1998
  57. ^ Timm Müller: HAMMER File System, wr.informatik.uni-hamburg.de, 13. juli 2012
  58. ^ V4, reiser4.wiki.kernel.org, 25. august 2016
  59. ^ Comer 1979, side 129
  60. ^ Comer 1979
  61. ^ a b c d e Ramakrishnan 2002
  62. ^ SQLite Version 3 Overview, sqlite.org, 2004
  63. ^ a b c Valerie Aurora: A short history of btrfs, LWN.net, 2009
  64. ^ a b c Btrfs Main Page, btrfs.wiki.kernel.org, 5. oktober 2016
  65. ^ Reiser, Hans (7. desember 2001). «Re: Ext2 directory index: ALS paper and benchmarks». ReiserFS developers mailing list. Besøkt 28. august 2009. 
  66. ^ Mason, Chris. «Acp». Oracle personal web page. Besøkt 5. november 2011. 
  67. ^ Fasheh, Mark (2012-10-09), btrfs: extended inode refs, https://git.kernel.org/?p=linux/kernel/git/mason/linux-btrfs.git;a=commit;h=f186373fef005cee948a4a39e6a14c2e5f517298, besøkt 2012-11-07 [død lenke]
  68. ^ Torvalds, Linus (2012-10-10), «Pull btrfs update from Chris Mason», git.kernel.org, https://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=72055425e53540d9d0e59a57ac8c9b8ce77b62d5, besøkt 2012-11-07 [død lenke]
  69. ^ Larabel, Michael (24. desember 2010). «Benchmarks Of The Btrfs Space Cache Option». Phoronix. Besøkt 16. november 2012. 
  70. ^ a b 2. Features, btrfs.wiki.kernel.org, 5. oktober 2016
  71. ^ a b «FAQ - btrfs Wiki: What checksum function does Btrfs use?». The btrfs Project. Besøkt 19. september 2013. 
  72. ^ a b Bierman, Margaret; Grimmer, Lenz (August 2012). «How I Use the Advanced Capabilities of Btrfs». Besøkt 20. september 2013. 
  73. ^ Salter, Jim (15. januar 2014). «Bitrot and atomic COWs: Inside "next-gen" filesystems». Ars Technica. Arkivert fra originalen 2015-03-23. Besøkt 15. januar 2014. 
  74. ^ Coekaerts, Wim (28. september 2011). «btrfs scrub - go fix corruptions with mirror copies please!». Besøkt 20. september 2013. 
  75. ^ Mason, Chris; Rodeh, Ohad; Bacik, Josef (2012-07-09), BTRFS: The Linux B-tree Filesystem, IBM Research, http://domino.watson.ibm.com/library/CyberDig.nsf/papers/6E1C5B6A1B6EDD9885257A38006B6130/$File/rj10501.pdf, besøkt 2012-11-12 
  76. ^ Mason, Chris (30. april 2008). «Multiple device support». Btrfs wiki. Arkivert fra originalen 20. juli 2011. Besøkt 5. november 2011. 
  77. ^ Sean Bartell: Re: Restoring BTRFS partition, linux-btrfs, 20. april 2010
  78. ^ Changelog, btrfs.wiki.kernel.org, 5. oktober 2016
  79. ^ «btrfs: Readonly snapshots». Besøkt 12. desember 2011. 
  80. ^ Mason, Chris (25. juni 2015). «Conversion from Ext3 (Btrfs documentation)». Besøkt 22. april 2016. 
  81. ^ Corbet, Jonathan (2012-07-11), Btrfs send/receive, LWN.net, https://lwn.net/Articles/506244/, besøkt 2012-11-14 
  82. ^ Jansen, Arne (2011) (PDF), Btrfs Subvolume Quota Groups, Strato AG, http://sensille.com/qgroups.pdf, besøkt 2012-11-14 
  83. ^ Development timeline. From btrfs Wiki, wiki.kernel.org 11. desember 2008
  84. ^ Thorsten Leemhuis: Kernel Log: Coming in 3.0 (Part 2) - Filesystems, 21. juni 2011
  85. ^ Michael Larabel: Lead Btrfs FIle-System Developers Join Facebook, Phoronix, 4. desember 2013
  86. ^ Sam Varghese: Facebook lures top Btrfs hackers, ITWire, 27. november 2013
  87. ^ SUSE Linux Enterprise Server 12 Release Notes, suse.com, 10. oktober 2014
  88. ^ Douglas DeMaio: What to expect from Btrfs on openSUSE 13.2?, opensuse.org, 12. november 2014
  89. ^ «Release Notes for Fedora 11». Fedora Project. Arkivert fra originalen 2009-06-12. Besøkt 15. juni 2009. 
  90. ^ 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
  91. ^ Slackware Release Announcement, slackware.com, 25. april 2011
  92. ^ How to install btrfs-tools on Debian 6 (Squeeze), 6. februar 2011
  93. ^ Christopher Tozzi: Ubuntu 10.10s New File System: btrfs, The VAR Guy, 2. august 2010
  94. ^ Z98: ReactOS 0.4.1 Released, 17. mai 2016

Litteratur[rediger | rediger kilde]

  • Comer, Douglas (Juni 1979). The Ubiquitous B-Tree. Computing Surveys, 11 (2): 123–137, juni 1979. 
  • Giampaolo, Dominic (November 1998). Practical File System Design. Morgan Kaufmann; 23. november 1998. ISBN 1558604979. ISBN 978-1558604971. 
  • Ramakrishnan, Raghu; Gehrke, Johannes (August 2002). Database Management Systems. McGraw-Hill; 3. utgave, 14. august 2002. ISBN 0072465638. ISBN 978-0072465631. 

Eksterne lenker[rediger | rediger kilde]