State-of-the-Art garbage collection policies for NILFS2

Abstract

NILFS2 ist ein sogenanntes log-structured Dateisystem für Linux. Log-structured Dateisysteme schreiben sowohl Daten als auch die zugehörigen Metadaten in Form eines sequentiellen Logs. Dadurch wird die höhere sequentielle Schreibgeschwindigkeit der meisten Datenträger und Festplatten ausgenutzt. Diese Art von Dateisystem macht allerdings eine Form von Garbage-Collection notwendig. Das aktuelle NILFS2 verwendet eine sehr einfache Garbage-Collection-Strategie namens Timestamp. Diese Arbeit beschreibt die Implementierung von zwei zusätzlichen state-of-the-art Algorithmen (Greedy und Cost-Benefit) und vergleicht deren Performance. Des Weiteren werden in dieser Arbeit zwei Algorithmen zum Sammeln und Speichern der notwendigen Metadaten vorgestellt. Das Ergebnis ist eine Leistungsverbesserung des Dateisystems um einen Faktor 1.53 für einen Großteil der Einsatzgebiete.

NILFS2 is a log-structured file system for Linux. Log-structured file systems write data and meta-data into a sequential log, to take advantage of the better sequential write performance of most storage devices. This approach necessitates some form of garbage collection, to recover the free space from the log. Currently NILFS2 uses a very simple garbage collection algorithm called Timestamp. This thesis describes the implementation of two additional state-of-the-art algorithms (Greedy and Cost-Benefit), and compares their performance. Additionally it discusses and compares two algorithms to gather and store the necessary meta-data used by the above mentioned garbage collection algorithms. The very promising results show a performance improvement over the Timestamp algorithm by a factor of 1.53 for most scenarios.