Reiser FS

Het Reiser File System is een bestandssysteem ontwikkeld door de onderzoeksgroep van Hans Reiser voor Linux-systemen.

[bewerk] Geschiedenis

Het ReiserFS is ontstaan vanuit een idee dat Hans Reiser had in 1984 -- het verenigen van bestandssystemen met database-technologie. Het algemene idee was dat databases in staat moeten zijn om zeer efficiënt om te gaan met grote hoeveelheden kleine data en dat de meeste bestandssystemen dat ook moeten kunnen (kleine bestanden, in dat geval). Reiser vond het daarbij vreemd dat de meeste bestandssystemen nou juist geoptimaliseerd worden voor grote bestanden, terwijl de meeste bestanden vrij klein zijn.

Databases maken al sinds jaar en dag gebruik van bomen om data in op te slaan op een manier waarbij de data snel teruggevonden kan worden. Om precies te zijn, databases gebruiken B-Trees, gebalanceerde bomen. Gebalanceerde bomen zijn bomen waarin ieder pad van wortel naar blad een lengteverschil heeft van maximaal 1 met ieder ander pad van wortel naar een blad. Het gebruik van deze bomen betekent dat opzoeken van data (als die zoektocht altijd bij de wortel begint) vrij efficiënt geschiedt omdat de lengte van de zoektocht beperkt is. Zeker als het zoeken ondersteund wordt door het aanleggen van sleutels in iedere knoop van de boom, waarbij iedere sleutel een aanwijzing bevat over de inhoud van een subboom van de knoop. Een sleutel staat een zoekalgoritme toe om slim de richting van de verdere zoektocht te kiezen en zo gedeelten van de boom over te slaan waar de gezochte data toch niet kunnen zitten.

Er is al een aantal keer eerder geprobeerd om deze technieken toe te passen in bestandssystemen. Deze pogingen zijn echter altijd stukgelopen op het een of ander en daarom was het idee in 1984 niet populair. Reiser hield echter stug vol dat er geen inherente mismatch is tussen gebalanceerde bomen en bestandssystemen, maar dat het alleen een kwestie was van een betere implementatie bouwen dan voorheen het geval was. In 1993 volgde een revisie van zijn principedocument, kort daarna gevolgd door de eerste, experimentele implementatie van ReiserFS.

Na enige ontwikkeling werd het systeem stabiel genoeg om toegepast te worden en begon het Reiser-team optimalisaties in te voeren op weg naar het uiteindelijke doel: een database-achtig bestandssysteem. Eén van die optimalisaties was het invoeren van een journaal, waarmee het systeem journaling werd. De timing hiervan was perfect gezien vanuit de Linux-gemeenschap, die hard op zoek was naar een opvolger van het Second Extended File System -- op zich een prima bestandssysteem, maar een waarvan het ontbreken van journaling in combinatie met de opkomst van grote harddisks wel heel vervelend begon te worden. Rond 2000 had ReiserFS versie 3 zich opgewerkt tot het standaard-bestandssysteem van een aantal grote Linuxdistributies, waaronder SuSE. In oktober 2006 echter werd ReiserFS door Novell, sinds 2004 eigenaar van SUSE, ingeruild voor ext3. De aankondiging hiervan kwam daags nadat bekend was geworden dat Hans Reiser was gearresteerd op verdenking van moord op zijn echtgenote; tot de overstap zou echter al eerder zijn besloten.

[bewerk] Basisprincipes

In tegenstelling tot de meeste bestandssystemen, die harde schijven organiseren als lineaire ketens van data, beschouwt ReiserFS het bestandssysteem als een boom.

In het geval van versie 3 van ReiserFS (de meeste gebruikte en populaire versie), is deze boom een gebalanceerde boom -- een boom waarvan alle paden van wortel naar blad een onderling lengteverschil van maximaal 1 hebben. Sterker nog, ReiserFS beschouwt het systeem als een gedecoreerde, gebalanceerde boom waarbij de decoratie per knoop bestaat uit sleutels die een aanwijzing geven over de inhoud van subbomen van die knoop. Het idee is dat hierdoor snel gezocht kan worden in de boom.

ReiserFS versie 3 verdeelt het bestandssysteem in een drietal soorten knopen:

1. Ongeformatteerde knopen, waarin allerlei data opgeslagen kan worden zonder verdere aanwijzingen. In dit geval beslaan de data in de knoop de gehele knoop.
2. Geformatteerde knopen, waarin stukken data die niet bij elkaar horen opgeslagen kunnen worden tezamen met een index van welke stukken waar in de knoop zitten; ook bevat een geformatteerde knoop verwijzingen naar andere knopen.
3. Interne knopen, die alleen doorverwijzingen naar andere knopen bevatten.

Knopen worden door het ReiserFS systeem afgebeeld op blokken op de harde schijf. Ongeformatteerde knopen zijn pure data-blokken, gebruikt voor stukken van bestanden die een heel blok bezetten. Geformatteerde knopen worden gebruikt om kleinere (stukken van) bestanden op te slaan -- hiermee bereikt ReiserFS een groot voordeel boven veel andere bestandssystemen, namelijk dat stukken van datablokken niet verloren gaan aan kleine bestanden (of de laatste stukken van grote bestanden) die niet een heel blok innemen maar waarvoor wel een heel blok gereserveerd moet worden. De indexering van geformatteerde knopen laat namelijk toe dat stukken van verschillende bestanden in hetzelfde blok opgeslagen liggen.

Interne knopen bevatten daarentegen alleen verwijzingen naar andere knopen -- deze blokken zijn structuurblokken, indexeringsblokken voor intern gebruik door het bestandssysteem.

Een ReiserFS-boom begint altijd met een interne knoop als wortel. Daarna volgen een aantal lagen interne knopen -- de indexering van de echte data. Vervolgens begint iedere data-houdende subboom met een aantal lagen geformatteerde knopen, waarin kleine bestanden en verwijzingen opgeslagen liggen. De laatste laag van geformatteerde knopen bevat over het algemeen een grote hoeveelheid bestandseinden, de laatste stukken van bestanden die niet groot genoeg zijn voor een eigen blok. Deze einden horen bij de bladeren van de boom: ongeformatteerde knopen, waarin de stukken van grote bestande opgeslagen liggen.

Het ReiserFS systeem heeft, door zijn opbouw, een groot aantal voordelen. Met name het snel opzoeken van data is goed mogelijk door de gebalanceerde boom structuur en het gebruik van indexerende sleutels in iedere geformatteerde en interne knoop. Bovendien heeft het bestandssysteem een structuur waarop makkelijk uitbreidingen kunnen worden geprojecteerd, zoals het journaling systeem waarmee ReiserFS zich een plaats verworven heeft in het Linux besturingssysteem.

ReiserFS heeft echter ook een aantal nadelen die inherent zijn aan gebalanceerde bomen. Met name heeft ReiserFS er last van als een bestand uitgebreid wordt zodat een bestandsdeel meer ruimte nodig heeft dan in zijn eigen blok voorradig is -- niet vreselijk als dat bestandsdeel in een ongeformatterde knoop zit, maar als het verplaatst moet worden van een geformatteerde knoop naar een andere knoop is dat een dure operatie (de boom moet dan niet alleen uitgebreid worden, maar geheel opnieuw in balans gebracht worden). Een groot gedeelte van het voortgaande onderzoek naar ReiserFS bestaat eruit om deze zwakte te ondervangen.

[bewerk] Bronnen

• ReiserFS v.3 Whitepaper
• ReiserFS v.4 Whitepaper
• Reiser4 Transaction Design Document
• Future Vision van Hans Reiser, 1993 editie

Deze bronnen waren ten tijde dat dit artikel geschreven werd beschikbaar op de website van Namesys. [1]