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

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. thumb|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.

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.

thumb|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.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: thumb|400px|right|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 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. thumb|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.

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

Btrfs

Źródło i licencja