|
|
|
|
Introduction Definition of Terms internal-fragmentation external-fragmentation standard formulation fragmentationX fragmented path Link to my old page Copyright and Contact |
|
|
|
Description download |
|
|
|
Description download |
|
|
|
|
|
|
|
|
|
Description download |
|
|
|
Description download Measurements on 2.4.8 Measurements on 2.4.10 |
|
|
|
Filesystem Homepages ReiserFS Ext2FS Ext3FS XFS JFS Benchmarks & Results ReiserFS benchs Denis'+Kresimir's site Randy's tests Yves' YAFB tests Literature Smith's site My master thesis |
|
|
Last changes: Do Feb 5 09:40:02 CET 2004
|
|
Ich gebe hier Auszüge aus der Einleitung und der Zusammenfassung der Diplomarbeit wieder. Wen die Arbeit interessiert, kann sie als pdf runterladen. Wenn die Arbeit zitiert wird, bitte ich um Zusendung einer Email an loizides AT
Analyse und Simulation von Fragmentierungseffekten beim ReiserFS Dateisystem (Inhaltsverzeichnis)
Einleitung
Dateisysteme sind eine wichtige Softwarekomponente von Betriebssystemen. Sie stellen insbesondere im Kontext von UNIX-Betriebssystemen den Namensraum zur Benennung von Betriebssystemobjekten zur Verfügung. Gleichzeitig realisieren sie die Verwaltung des persistenten Datenspeichers. Bei der Entwicklung eines Dateisystems kommt es daher nicht nur auf Performanz und Flexibilität, sondern auch auf Zuverlässigkeit an.Das Reiser-Dateisystem ist ein sehr modernes, unter LINUX entwickeltes Dateisystem, das jedes der genannten Kriterien auf innovative Weise zu lösen versucht. Im Unterschied zu den klassischen Dateisystemen verwaltet es seine Datenstruktur in Form eines einzigen balancierten Baums. Damit löst es das Problem konventioneller Dateisysteme, kleine Dateien gemeinsam mit großen effektiv zu verwalten. Zur Protokollierung von Metadatenänderungen reserviert es einen speziellen Bereich auf der Platte, indem es nach dem Konzept von Datenbanken eine effiziente Strategie zur Konsistenzerhaltung seiner Metadaten umsetzt.
Mit seinen Eigenschaften ist es dem unter LINUX sehr verbreiteten Ext2-Dateisystem in jeder Hinsicht überlegen. Es ist daher kein Wunder, daß es seit dem Erreichen einer stabil lauffähigen Version und der standardmäßigen Auslieferung mit dem LINUX-Kernel der Version 2.4 zahlreich Verwendung findet.
Bedingt durch die junge Entwicklungsgeschichte gibt es noch keine zuverlässigen Erkenntnisse über das Performanzverhalten des Reiser-Dateisystems nach langer und intensiver Benutzung. Praktisch jedes Dateisystem unterliegt alterungsbedingten Performanzverlusten, die sich je nach Dateisystem und Benutzungsweise unterschiedlich stark bemerkbar machen. Diese Alterungseffekte treten in der Regel in Form von externer Fragmentierung auf.
Das Ziel dieser Arbeit ist daher, eine Analyse und Simulation von Fragmentierungseffekten beim Reiser-Dateisystem vorzunehmen. Dazu stellen wir eine Methode vor, eine objektive Bemaßung der Fragmentierung eines Dateisystems vorzunehmen, die wir mit Performanzmessungen an gealterten Systemen vergleichen. Um die normalerweise erst nach intensiver Benutzung auftretenden Effekte festzustellen, implementieren wir zwei verschiedene Simulationstypen zur künstlichen Alterung eines Dateisystems. Die Ergebnisse eines der beiden Typen verwenden wir, um das Langzeitverhalten von Reiser- Dateisystemen im Vergleich zu dem konventionellen Ext2-Dateisystem zu studieren.
Alterung in Form von Fragmentierungseffekten tritt auf, wenn die Datenblöcke einer Datei weit verstreut auf dem Datenträger verteilt liegen, so daß insbesondere die Übertragungszeit beim sequentiellen Lesen sinkt. Dabei spielt der Umstand eine große Rolle, daß einem persistenten Speichermedium in der Regel ein mechanisches Gerät zugrundeliegt. Dieses Gerät ermöglicht eine Zugriffszeit in der Größenordnung von Millisekunden, während beispielsweise die Zugriffszeit auf den Hauptspeicher in der Größenordnung von Nanosekunden liegt. Daher ist die Anordnung der Blöcke auf der Festplatte, die den effektiven Zugriff auf Daten und Metadaten dauerhaft gewährleistet, trotz der immer besseren Festplattentechnik ein überaus wichtiges Designziel eines Dateisystems. Wenn man typische Festplattendatenblätter von heute mit solchen von 1975 vergleicht, stellt man fest, daß sich seitdem die Speicherplatzgröße um den Faktor 10000, die Zugriffszeiten konstruktionsbedingt aber nur um den Faktor 10 verbessert haben. Das bedeutet strenggenommen sogar, daß heutzutage eine geschickte Anordnung der Daten auf der Platte im Verhältnis noch wichtiger geworden ist als früher. Dateisysteme werden zudem durch ein anderes Nutzungs- und Erwartungsverhalten des Anwenders mit viel größeren Datenmengen und echtzeitkritischen Anwendungen stärkerer Belastungen ausgesetzt. Natürlich verbergen zugriffsoptimierte Anwendungen sowie Zwischenspeicherstrategien der an dem Zugriff beteiligten Betriebssystemsoftware- und Hardwarekomponenten auf unterschiedlichste Weise den Sachverhalt, daß auch heutzutage Festplatten ineffizient im Zugriff und performant im kontinuierlichen Datentransfer sind. [...]
Zusammenfassung
Das Ziel dieser Arbeit ist die Analyse und Simulation von Fragmentierungseffekten am Reiser-Dateisystem sowie ihre objektive Bemaßung.Zu diesem Zweck untersuchen wir die beteiligten Komponenten aus Hardware und Software. Insbesondere vertiefen wir Festplatten- und Dateisystemtechniken sowie ihre Zusammenarbeit im virtuellen Dateisystem unter LINUX. Dabei arbeiten wir die Unterschiede zwischen dem fortschrittlichen Reiser- und dem klassischen Ext2-Dateisystem heraus.
Wir definieren verschiedene Maße zur Zustandscharakterisierung eines Dateisystems und geben eine Einführung in die Problematik der kontrollierten und anwendungsbasierten Langzeitsimulation von Alterungseffekten. Daraufhin stellen wir zwei von uns entwickelte Simulationsmethoden vor: Die Alterungssimulation und die Applikationssimulation. Die entwickelte Applikationssimulation hat bisher noch kein Resultat geliefert. Mit ihrer Hilfe versprechen wir uns bei weiteren Vorhaben, den Anwendungscharakter der Simulation in den Vordergrund zu stellen.
Die Ergebnisse der durchgeführten Alterungssimulationen zeigen, daß externe Fragmentierung bei Reiser-Dateisystem zu Performanzverlusten führt. Bei den Tests durch Anhängen sinkt die über alle Dateigrößen gemittelte Leseperformanz des gealterten Dateisystems im schlechtesten Fall um 600% bezogen auf die Referenzkopie. Bei der im Vergleich moderaten Belastung der Alterungstests durch Erzeugen und Löschen sinkt dieselbe Meßgröße um 40% im Vergleich zur Referenz. Ext2 schneidet bei den Appendtests wesentlich schlechter ab. Im schlechtesten Fall sinkt die Leseperformanz um den Faktor 14. Bei der moderaten Alterungsmessung dagegen sinkt die Performanz nur auf 80% des Referenzwerts. Allerdings sind die absoluten Meßwerte beider Systeme bei dem gewählten Szenario in derselben Größenordnung. Die Fragmentierungsmaße korrelieren bis auf wenige Ausnahmen bei Ext2 in allen Fällen mit den Meßwerten.
Für die Appendtests zeigen wir, daß sich durch eine einmalig zu Beginn der Simulation für jede Datei vorgenommene Preallokation von Blöcken mit anschließender Freigabe des Speicherplatzes die Leseperformanz bei Reiser um bis zu 200% im Vergleich zu dem ohne Preallokation gealterten gemessenen Wert erhöht. Bei Ext2 hat dieser einmalige Vorgang keine meßbaren Vorteile.
Wir führen darüber hinaus eine Methode vor, mit der wir die Performanz der Lesetests durch das gemessene Blocklayout berechnen können. An Hand eines Simulationsergebnisses für das Reiser-Dateisystem zeigen wir, daß wir damit den Verlauf der Meßwerte grob bestimmen können.