WikiDer > Reiser-Dateisystem

Es Reiser-Dateisystem (ReiserFS) ist ein Dateisystem entwickelt von der Forschungsgruppe von Hans Reiser vor dem Linux-Systeme.

Geschichte

Der ReiserFS entstand aus einer Idee, die Hans Reiser in 1984 -- vereinigen von Dateisystemen mit Datenbanktechnologie. Die allgemeine Idee war, dass Datenbanken in der Lage sein sollten, große Mengen kleiner Daten sehr effizient zu handhaben und die meisten Dateisysteme sollten dies können (in diesem Fall kleine Dateien). Reiser fand es seltsam, dass die meisten Dateisysteme für große Dateien optimiert sind, während die meisten Dateien recht klein sind.

Datenbanken haben verwendet Bäume Daten so zu speichern, dass die Daten schnell abgerufen werden können. Um genau zu sein, verwenden Datenbanken B-Trees, ausgewogene Bäume. Ausgeglichene Bäume sind Bäume, bei denen jeder Wurzel-zu-Blatt-Pfad eine Längendifferenz von höchstens 1 zu jedem anderen Wurzel-zu-Blatt-Pfad aufweist. Die Verwendung dieser Bäume bedeutet, dass das Nachschlagen von Daten (wenn diese Suche immer an der Wurzel beginnt) ziemlich effizient ist, da die Länge der Suche begrenzt ist. Vor allem, wenn die Suche durch die Erstellung von Schlüsseln in jedem Knoten des Baums unterstützt wird, wobei jeder Schlüssel einen Hinweis auf den Inhalt eines Teilbaums des Knotens enthält. Ein Schlüssel ermöglicht es einem Suchalgorithmus, die Richtung der weiteren Suche intelligent zu wählen und somit Teile des Baumes zu überspringen, in denen die gesuchten Daten nicht gefunden werden können.

Es wurden bereits mehrere Versuche unternommen, diese Techniken in Dateisystemen anzuwenden. Diese Versuche sind jedoch immer an der einen oder anderen Stelle gescheitert, weshalb die Idee 1984 nicht populär wurde. Reiser bestand jedoch darauf, dass es keine inhärente Diskrepanz zwischen ausgewogenen Bäumen und Dateisystemen gebe, es gehe nur darum, eine bessere Implementierung als zuvor zu entwickeln. Im 1993 folgte eine Überarbeitung des Hauptdokuments, kurz darauf folgte die erste experimentelle Implementierung von ReiserFS.

Nach einiger Entwicklung wurde das System stabil genug, um angenommen zu werden, und das Reiser-Team begann, Optimierungen für das ultimative Ziel zu implementieren: ein datenbankähnliches Dateisystem. Eine dieser Optimierungen war die Erfassung eines Journals, wodurch das System zum Journaling wurde. Der Zeitpunkt dafür war perfekt von der Linux-Community, der verzweifelt auf der Suche nach einem Nachfolger für die Zweites erweitertes Dateisystem -- ein feines Dateisystem an sich, aber eines, dessen fehlendes Journaling in Verbindung mit dem Aufkommen großer Festplatten wirklich nervig wurde. runden 2000 ReiserFS Version 3 hatte seinen Weg in das Standarddateisystem einer Reihe großer Linux-Distributionen gefunden, darunter SuSE. Im Oktober 2006 ReiserFS wurde jedoch von Novell verkauft, da 2004 Eigentümer von SUSE, eingetauscht für ext3. Die Bekanntgabe erfolgte einen Tag nachdem bekannt wurde, dass Hans Reiser wegen des Verdachts des Mordes an seiner Frau festgenommen worden war; der Wechsel wäre jedoch früher entschieden worden.

Grundprinzipien

Im Gegensatz zu den meisten Dateisystemen, die Festplatten ReiserFS organisiert sie als lineare Datenketten und betrachtet das Dateisystem als Baum.

Im Fall der Version 3 von ReiserFS (der am weitesten verbreiteten und beliebtesten Version) ist dieser Baum ein ausgewogener Baum – ein Baum, bei dem alle Wurzel-zu-Blatt-Pfade einen gegenseitigen Längenunterschied von bis zu 1 aufweisen. Tatsächlich betrachtet ReiserFS das System als dekorierten, ausgewogenen Baum, bei dem die Dekoration pro Knoten aus Schlüsseln besteht, die den Inhalt von Unterbäumen dieses Knotens angeben. Die Idee ist, dass dies eine schnelle Suche im Baum ermöglicht.

ReiserFS Version 3 unterteilt das Dateisystem in drei Arten von Knoten:

1. Unformatierte Knoten, in denen alle Arten von Daten ohne weitere Anweisungen gespeichert werden können. In diesem Fall belegen die Daten im Knoten den gesamten Knoten.
2. Formatierte Knoten, in denen nicht zusammengehörige Daten zusammen mit einem Index gespeichert werden können, welche Teile sich wo im Knoten befinden; auch ein formatierter Knoten enthält Verweise auf andere Knoten.
3. Interne Knoten, die nur Verweise auf andere Knoten enthalten.

Knoten werden vom ReiserFS-System Blöcken auf der Festplatte zugeordnet. Unformatierte Knoten sind reine Datenblöcke, die für Dateiteile verwendet werden, die einen ganzen Block belegen. Formatierte Knoten werden verwendet, um kleinere (Stücke von) Dateien zu speichern – dies ermöglicht ReiserFS gegenüber vielen anderen Dateisystemen einen großen Vorteil, nämlich dass keine Datenblöcke an kleine Dateien (oder die letzten Stücke großer Dateien) verloren gehen, die nicht einen ganzen Block belegen, sondern für die ein ganzer Block reserviert werden muss. Die Indizierung formatierter Knoten ermöglicht das Speichern von Teilen unterschiedlicher Dateien im selben Block.

Interne Knoten hingegen enthalten nur Verweise auf andere Knoten -- diese Blöcke sind Strukturblöcke, Indizierungsblöcke für die interne Verwendung durch das Dateisystem.

Ein ReiserFS-Baum beginnt immer mit einem internen Knoten als Wurzel. Dann folgt eine Reihe von Schichten interner Knoten – die Indizierung der echten Daten. Als nächstes beginnt jeder datenhaltende Unterbaum mit einer Reihe von Schichten formatierter Knoten, die kleine Dateien und Referenzen speichern. Die letzte Schicht formatierter Knoten enthält im Allgemeinen eine große Anzahl von Dateiunterbrechungen, die letzten Dateien, die nicht groß genug für einen eigenen Block sind. Diese Enden gehören zu den Blättern des Baumes: unformatierte Knoten, in denen die Stücke großer Dateien gespeichert werden.

Das ReiserFS-System hat aufgrund seiner Struktur eine Vielzahl von Vorteilen. Durch die ausgewogene Baumstruktur und die Verwendung von Indexierungsschlüsseln in jedem formatierten und internen Knoten ist insbesondere ein schneller Datenabruf gut möglich. Darüber hinaus verfügt das Dateisystem über eine Struktur, auf die Erweiterungen leicht projiziert werden können, wie beispielsweise das Journaling-System, das ReiserFS in Linux übernommen hat. Betriebssystem.

ReiserFS hat jedoch auch einige Nachteile, die balancierten Bäumen innewohnen. Insbesondere leidet ReiserFS, wenn eine Datei so expandiert wird, dass ein Dateiteil mehr Platz benötigt, als im eigenen Block zur Verfügung steht. Das ist nicht schlimm, wenn sich diese Komponente in einem unformatierten Node befindet, aber wenn sie von einem formatierten Node zu einem anderen Node verschoben werden muss, ist das eine "teure" Operation. Der Baum muss dann nicht nur erweitert, sondern komplett neu ausbalanciert werden. Ein Großteil der laufenden Forschungen zu ReiserFS zielt darauf ab, diese Schwäche zu beheben.