Den andra november förra året presenterade Mikulas Patocka filsystemet Spad FS genom att posta det till mejllistan Linux kernel. Mikulas Patocka är doktorand vid fakulteten för matematik och fysik vid Charles universitet i Prag. Han forskar på filsystem och Spad FS är plattformen för nya mekanismer och strukturer.

Spad FS är alltså i högsta grad ett experimentellt filsystem, men Mikulas Patocka har valt att göra det tillgängligt för andra, både för att sprida sina idéer och för att få återkoppling på sina forskningsresultat.

Spad FS orsakade en hel del diskussioner, inte minst för att Andrew Morton i stort sett samtidigt presenterade ext 4. En person som tyckte att Spad FS verkade intressant var Linus Torvalds, som efter att ha tittat på det sa: ”It doesn’t look horrible to me.” Linus Torvalds kommentar gällde i första hand källkoden, men han har även sagt att Spad FS innehåller flera designval han ser som intressanta för framtida filsystem.

Ett av de valen gäller hantering av index och annan sidoinformation som krävs för att organisera filer och deras data i en struktur på ett fysiskt lagringsmedia. Problemet som Linus Torvalds ser med dagens system är att informationen lagras i separata noder kallade inoder. Att informationen är separat placerad innebär att datorn för att hitta en fil måste leta upp minst en inod och sedan gå vidare till den korrekta platsen för filen.

Ger prestandaproblem

Denna så kallade indirektion orsakar prestandaproblem. Cacheminnen och cachehanteringslogiken klarar inte att med stor träffsäkerhet automatiskt följa inoderna och hämta korrekta filer och fildata. I stället måste operativsystemet hämta inoderna och sedan göra en separat läsning till rätt sektorer på hårddisken för att få in ytterligare inoder och fildata.

Spad FS löser det genom att integrera inoderna och annan sidoinformation med filinnehållet. Den huvudsakliga datastrukturen i Spad FS är fnode_block, som är en del av katalogstrukturen. I fnode_block lagras filnamn, filattribut, tid och datum för filåtkomst, filstorlekar, start av fildata samt länkar till andra fnode_block.

Vid uppslagning av en katalog eller fil finns informationen direkt tillgänglig för fortsatt inhämtning när korrekt fnode_block har identifierats.

Utökningsbar hashtabell

De flesta filsystem, exempelvis Reiser FS, använder en typ av trädstruktur som kallas B-trees för att lagra filsystemets struktur av inoder och data. Spad FS använder i stället en speciell variant av hashtabellen. Den stora fördelen med hashtabeller framför trädstrukturer är att så länge två element inte har samma index i hashtabellen (det vill säga att det inte finns någon kollision) är uppslagningstiden konstant och låg. Problemen med hashtabeller är hur kollsioner hanteras samt hur hashtabellen ska utökas när den börjar bli full och antalet kollisioner helt enkelt blir för många.

När en kollision uppstår i en enkel hashtabell kopplas de element som har samma hashindex samman i en länkad lista. Det innebär att sökningen övergår till en kostsam linjär variant om en kollision uppstår. Om tabellen ska utökas och storleken på det hashindex som används behöver utökas måste hela tabellen också hashas om, en potentiellt tidskrävande operation. Dessa egenskaper gör att en enkel hashtabell normalt inte används för att bygga filsystem.

Den typ av hashtabell som används i Spad FS kallas utökningsbar (extendible). Utökningsbar hashning presenterades av forskare vid IBM redan 1979 och löser problemen med kollisioner och utökning av tabellstorleken genom att införa en extra nivås indirektion.

Det innebär att tabellen består av en primär och en sekundär tabell, där element i primärtabellen pekar in i den större hashtabellen med en sekundärnyckel där sedan elementen lagras. Resultatet blir en datastruktur där både primär-och sekundärtabellen kan utökas gradvis i takt med att nya element läggs in i strukturen. Kollisioner elimineras direkt när ett nytt element läggs till genom att ytterligare en plats skapas i sekundärtabellen.

Behålls i cacheminnet

Nackdelen med utökningsbar hashning är att alla åtkomster tar två uppslagningar, det finns alltid en indirektion. Med dagens stora filsystem, där motsvarande B-tree kan innehålla många nivåer av noder och ett flertal indirektionssteg, är det dock en klar förbättring. Inte minst för processorer med stort cacheminne, där hela den primära hashtabellen kan läsas in och behållas i minnet. Det gör det möjligt att snabbt hitta var rätt element finns lagrat utan att de två hashuppslagningarna ger upphov till mer än en diskåtkomst.

Att utökningsbar hashning nu börjar bli intressant kan man exempelvis se i att IBM använder det i filsystemet Tiger Sharc, ett system speciellt framtaget för multimedieservrar. Här är den garanterade åtkomsttiden till filinnehållet avgörande för att man ska kunna möta de realtidskrav som strömmande media ställer.

Ett annat koncept som gör att Spad FS skiljer sig från andra filsystem är hur det hanterar problem vid krascher. I ett journalförande filsystem, exempelvis ext 3 eller XFS, dokumenteras alla operationer i filsystemet innan de utförs. Varje operation betraktas som atomisk och om ett oväntat avbrott inträffar kommer filsystemets tillstånd att återskapas utifrån journalen.

Kombinerat koncept

Spad FS använder i stället något som kallas kraschräknare. Varje gång filsystemet monteras räknas dess kraschräknare upp ett steg och varje gång det avmonteras kommer kraschräknaren att räknas ned ett steg.

Spad FS kombinerar konceptet med transaktionsräknare och applicerar det på samtliga kataloger och andra datastrukturer i filsystemet.

Räknarna i Spad FS är samlade i en tabell. Vid montering läses tabellen i datorns minne och innehållet uppdateras varje gång någon form av åtkomst mot en del av filsystemet utförs. Genom att analysera innehållet i tabellen och jämföra den med kopian i minnet kan status för filsystemet övervakas i detalj.

När en fil i en katalog skapas räknas motsvarande kraschräknare för katalogen upp. Eftersom kraschräknaren på disk inte räknas upp kommer dock status efter en krasch visa att filen inte är korrekt. Vid läsning av en fil räknas transaktionsräknaren upp för att visa att filen har använts, men så länge filen inte skrivs sker inga ytterligare uppräkningar av kraschräknaren.

På liknande sätt används transaktionsräknare i kombination med kraschräknare för att implementera olika atomiska filoperationer, exempelvis att ta bort, byta namn eller flytta filer.

Vid synkronisering skrivs tabellen med räknare ut till hårddisken och alla cacheminnen töms. Det gör att filsystemets tillstånd så som det beskrivs av tabellen på hårddisken är detsamma som i datorns minne. Synkronisering sker i Spad FS antingen när operativsystemet begär synkronisering, periodiskt eller när filsystemet behöver mer utrymme i minnet och vissa block därför behöver frigöras.

Den stora skillnaden mellan ett journalförande filsystem och Spad FS är att varje liten operation i det förstnämnda är atomisk, medan de atomiska operationerna i Spad FS kan vara mer komplexa och bestå av flera deloperationer som utförs tillsammans. Att flytta en fil innebär i ett journalförande filsystem att flera atomiska operationer utförs, medan det i Spad FS är en atomisk operation.

Färre diskåtkomster

De integrerade inoderna, användningen av hashtabeller och kraschräknaren gör tillsammans att antalet diskåtkomster som krävs för att nå en fil är lägre med Spad FS än med filsystem som ext 3 och Reiser FS. Vidare är den interna strukturen i Spad FS bättre anpassad för cacheminnen i moderna processorer. Vi kan alltså förvänta oss att Spad FS uppvisar bättre prestanda än vad andra filsystem gör.

 Spad-fs MB/s
Prestanda vid skrivning, omskrivning och läsning av en åtta gigabyte stor fil i Linux med olika filsystem.

Mikulas Patocka har publicerat en del resultat. Figur ett, här ovanför visar de prestanda i megabyte per sekund som uppmätts vid bearbetning som skrivning, omskrivning och läsning av en åtta gigabyte stor fil med filsystemen ext 2, ext 3, Reiser FS och Spad FS. Systemet som använts är Linux 2.6 (Lin) samt en experimentell version av Linux som Mikulas Patocka själv har utvecklat (Spad).

 
Figuren visar tidsåtgången uppmätt vid mer komplex sekvens vid bearbetning av en stor mängd filer.

Figur nr två visar tidsåtgången i sekunder för en mer komplex sekvens av operationer. Källkodsarkivet av Open Solaris packas upp och källkodsstrukturen kopieras till en ny katalog där den blir genomsökt efter specifik information och sedan blir raderad.

Märkliga bieffekter

Hanteringen av inoder och annan sidoinformation ger tyvärr upphov till en del bieffekter. Filer byter inodnummer när de flyttas, får ett nytt namn eller om en hård länk skapas till filen. Vidare kan en fils inodnummer ändras om dess katalogsida delas upp på flera sidor. Det kan ske om innehållet i katalogen ökar. Spad FS kommer heller inte att klara åtkomst av filer via inodnummer för nfs-servrar.

Det är inte svårt att komma igång med Spad FS. Du behöver ett Linuxsystem baserat på 2.6-kärnan som klarar moduler. Vidare krävs det att den hårddisk du ska använda klarar att atomiskt skriva en sektor, något de flesta moderna hårddiskar kan.

Inte nästa stora system

Gå in på Spad FS webbplats och ladda ned källkod och användarhandbok. Därefter är det bara att börja experimentera. Notera att det handlar just om att experimentera eftersom Spad FS är ett filsystem under utveckling. Använd det bara för att lagra det du är beredd att förlora och har (minst) en säkerhetskopia av.

Spad FS kommer troligen inte att bli nästa stora filsystem. Det är experimentellt, nytt och spännande, men tillför inte tillräckligt många nya funktioner för att det ska kunna ersätta något av de etablerade systemen.

Att inoden för en fil ändras när katalogen där den ligger fylls med fler filer är en bieffekt som kan förvirra system, program och administratörer. Att Spad FS inte heller ser ut att fungera bra med nfs gör det mycket mindre intressant för serverprogram, som annars skulle kunna dra nytta av dess höga och garanterade prestanda.

Få nya funktioner

Spad FS har även en hel del konkurrens. I oktober förra året presenterade Andrew Morton ext 4. Målsättningen vid utvecklingen där har, till skillnad från med Spad FS, varit att möta behovet av stora diskar och stöd för flera andra filsystem. Samtidigt har det varit viktigt att behålla kompatibiliteten med gamla system och framför allt att inte hota stabiliteten. En mycket konservativ utgångspunkt, med andra ord.

Lyfter vi blicken bortom Linux presenterade Sun för ett par år sedan filsystemet ZFS, ett spännande sätt att lösa hantering av volymer, snapshots, versioner och säkerhetskopiering.

Spad FS, ext 4 och ZFS visar att filsystemutvecklarna inte lider brist på problem att lösa och idéer på hur de ska lösas.

Vår bedömning är att Spad FS i dag är för mycket en plattform för att experimentera med filsystemsteknik för att vara riktigt användbart som huvudfilsystem. Precis som Linus Torvalds tror vi dock att delar av tekniken i Spad FS kommer att leta sig in i nya versioner av redan etablerade filsystem.

 Så går du vidare, länkar:

Fakta

Ordlista

  • B-tree. En trädbaserad datastruktur vanligt förekommande som grundläggande datastruktur för att lagra data i databaser och filsystem.
  • Cacheminne. Ett snabbt fysiskt minne implementerat i eller i närheten av en processor. Det används för att lagra temporära kopior av instruktioner eller data för att minska åtkomsttiden från processorn.
  • Hashtabell. En tabellbaserad datastruktur där lagrade data är associerade med en nyckel som transformeras med en hashfunktion till index in i tabellen. Hashtabeller används för att lagra databaser och klarar snabb uppslagning.
  • Inod. En inod är en del av en trädbaserad datastruktur som används i filsystem för att lagra information om filer, kataloger och information för andra typer av filelement.