Advanced data deduplication techniques and their application

Data deduplication describes a class of approaches that reduce the storage capacity needed to store data or the amount of data that has to be transferred over a network. These approaches detect coarse-grained redundancies within a data set, e.g. a file system, and remove them.rnrnOne of the most important applications of data deduplication are backup storage systems where these approaches are able to reduce the storage requirements to a small fraction of the logical backup data size.rnThis thesis introduces multiple new extensions of so-called fingerprinting-based data deduplication. It starts with the presentation of a novel system design, which allows using a cluster of servers to perform exact data deduplication with small chunks in a scalable way.rnrnAfterwards, a combination of compression approaches for an important, but often over- looked, data structure in data deduplication systems, so called block and file recipes, is introduced. Using these compression approaches that exploit unique properties of data deduplication systems, the size of these recipes can be reduced by more than 92% in all investigated data sets. As file recipes can occupy a significant fraction of the overall storage capacity of data deduplication systems, the compression enables significant savings.rnrnA technique to increase the write throughput of data deduplication systems, based on the aforementioned block and file recipes, is introduced next. The novel Block Locality Caching (BLC) uses properties of block and file recipes to overcome the chunk lookup disk bottleneck of data deduplication systems. This chunk lookup disk bottleneck either limits the scalability or the throughput of data deduplication systems. The presented BLC overcomes the disk bottleneck more efficiently than existing approaches. Furthermore, it is shown that it is less prone to aging effects.rnrnFinally, it is investigated if large HPC storage systems inhibit redundancies that can be found by fingerprinting-based data deduplication. Over 3 PB of HPC storage data from different data sets have been analyzed. In most data sets, between 20 and 30% of the data can be classified as redundant. According to these results, future work in HPC storage systems should further investigate how data deduplication can be integrated into future HPC storage systems.rnrnThis thesis presents important novel work in different area of data deduplication re- search.In dieser Doktorarbeit werden mehrere Forschungsergebnisse über verschiedene Aspekte von Datendeduplizierungssystemen vorgestellt. Datendeduplizierung beschreibt eine Klasse von Ansätzen, die es erlauben, die zur Speicherung von Daten notwendig Speicherkapazität zu reduzieren. Datendeduplizierungstechniken werden weiterhin eingesetzt, um die Menge der Daten, die über ein Netzwerk transferiert werden müssen, zu reduzieren. Diese Ansätze erkennen grob-körnige Redundanzen innerhalb einer Datenmenge und entfernen diese.rnrnEin wichtiges Anwendungsgebiet für Datendeduplizierungstechniken sind Speichersysteme zur Datensicherung, da hier die zu speichernde Datenmenge auf einen kleinen Teil der logischen Backupdaten reduziert werden kann. Dieses ermöglicht oftmals erhebliche Kosteneinsparungen im Betrieb von Datensicherungssystemen.rnrnIn dieser Arbeit werden mehrere neue Techniken für Fingerabdruck-basierende Datendeduplizierungssysteme vorgestellt. Die Arbeit startet mit der Vorstellung eines neuartigen Designs, um einen Cluster von Rechnern zu verwenden, der exakte Deduplizierung mit kleinen Chunks ermöglicht. Anschließend wird eine Kombination von Komprimierungstechniken eingeführt, die die Größe einer wichtigen und speicher-intensiven Datenstruktur von Datendeduplizierungssystemen, den sogenannten Block- und Dateirezepten, reduzieren.rnrnEine weitere neuartige Technik, die Block- und Dateirezepte verwendet, wird als nächstes vorgestellt. Das Blocklokalitätscaching (BLC) verwendet Eigenschaften von diesen Rezepten um den Festplattenflaschenhals von Datendeduplizierungssystemen zu über- winden. Dieser Flaschenhals limitiert entweder die Skalierbarkeit oder den Datendurchsatz von Datendeduplizierungssystemen. Der BLC-Ansatz ist dabei effizienter als existier- ende Ansätze. Es wird weiterhin gezeigt, dass der BLC-Ansatz weniger anfällig für Alterungserscheinungen als existierende Ansätze ist. Daher nimmt mit dem BLC-Ansatz der Durchsatz auch bei langlebigen Datendeduplizierungssystemen nicht ab.rnrnIm letzten Teil dieser Arbeit wird untersucht, ob die Speichersysteme von großen Hochleistungsrechnern (HPC) Redundanzen von der Art beinhaltet, die von Fingerabdruck-basierender Datendeduplizierung vermieden werden können. Dazu wurden mehr als 3 PB Daten aus verschiedenen Rechenzentren analysiert. Das Ergebnis lässt darauf schließen, dass in den meisten Rechenzentren zwischen 20 und 30% der Daten als redundant klassifiziert werden können. Dieses zeigt, dass die zukünftige Forschung im Bereich der Speichersysteme von Hochleistungsrechensystemen beinhalten sollte, wie Datendeduplizierung in diesen Systemen eingesetzt werden kann