Deduplikation
Deduplikation (aus englisch deduplication), auch Datendeduplikation oder Deduplizierung, ist in der Informationstechnik ein Prozess, der redundante Daten identifiziert (Duplikaterkennung) und eliminiert, bevor diese auf einen nichtflüchtigen Datenträger geschrieben werden. Der Prozess komprimiert wie andere Verfahren auch die Datenmenge, die von einem Sender an einen Empfänger geschickt wird. Es ist nahezu unmöglich, die Effizienz bei der Verwendung von Deduplikationsalgorithmen vorherzusagen, da sie immer von der Datenstruktur und der Änderungsrate abhängig ist. Deduplikation kann eine sehr effiziente Methode sein, Datenmengen zu reduzieren, bei denen eine Mustererkennung möglich ist (unverschlüsselte Daten).
Vorrangiges Einsatzgebiet der Deduplikation ist vorerst die Datensicherung (Backup), bei der sich in der Praxis meistens eine stärkere Datenkomprimierung als mit anderen Methoden erzielen lässt. Das Verfahren eignet sich grundsätzlich für jeden Einsatzbereich, bei dem Daten wiederholt kopiert werden.
Funktionsweise
Deduplikationssysteme unterteilen die Dateien in Blöcke gleicher Größe (meist Zweierpotenzen) und berechnen für jeden Block eine Prüfsumme. Hierin liegt auch die Abgrenzung zum Single Instance Storage (SIS), das identische Dateien eliminieren soll (siehe auch inhaltsadressierte Speichersysteme, CAS).
Alle Prüfsummen werden anschließend zusammen mit einem Verweis auf die entsprechende Datei und die Position innerhalb der Datei gespeichert. Kommt eine neue Datei hinzu, so wird auch ihr Inhalt in Blöcke unterteilt und daraus die Prüfsummen berechnet. Anschließend wird verglichen, ob eine Prüfsumme bereits existiert. Dieser Vergleich der Prüfsummen ist wesentlich schneller, als die Dateiinhalte direkt miteinander zu vergleichen. Wird eine identische Prüfsumme gefunden, ist dies ein Hinweis darauf, dass möglicherweise ein identischer Datenblock gefunden wurde, es muss allerdings noch geprüft werden, ob die Inhalte tatsächlich identisch sind, da es sich auch um eine Kollision handeln kann.
Wurde ein identischer Datenblock gefunden, wird einer der Blöcke entfernt und stattdessen nur ein Verweis auf den anderen Datenblock gespeichert. Dieser Verweis benötigt weniger Speicherplatz als der Block selbst.
Für die Selektion der Blöcke gibt es zwei Methoden. Beim „Reverse-Referencing“ wird der erste gemeinsame Block gespeichert, alle weiteren identischen erhalten einen Verweis auf den ersten. Das „Forward-Referencing“ legt immer den zuletzt aufgetretenen gemeinsamen Datenblock ab und referenziert die vorher aufgetretenen Elemente. Bei diesem Methodenstreit geht es darum, ob Daten schneller gespeichert oder schneller wiederhergestellt werden sollen. Weitere Vorgehensweisen, wie „Inband“ und „Outband“, konkurrieren darum, ob der Datenstrom „on the fly“, also im laufenden Betrieb, analysiert wird oder erst nachdem dieser am Zielort gespeichert worden ist. Im ersten Fall darf nur ein Datenstrom existieren, im zweiten können die Daten mittels mehrerer Datenströme parallel untersucht werden.
Beispiel
Bei der Datensicherung von Festplatten auf Bandmedien ist das Verhältnis von neuen bzw. veränderten zu unveränderten Daten zwischen zwei Vollsicherungen meist nur relativ gering. Zwei Vollsicherungen benötigen bei der klassischen Datensicherung aber trotzdem mindestens die doppelte Speicherkapazität auf dem Band, verglichen mit den Originaldaten. Die Deduplikation erkennt die identischen Datenbestandteile. In einer Liste werden dazu eindeutige Segmente festgehalten, und beim erneuten Auftreten dieses Datenteils werden Zeitpunkt und Ort im Datenstrom notiert, so dass letztlich die Originaldaten wiederhergestellt werden können.
Allerdings handelt es sich damit nicht mehr um voneinander unabhängige Vollsicherungen, d. h., dass der Verlust eines Versionsstandes zu unwiederbringlichem Datenverlust führt. Deduplikation verzichtet somit, ähnlich der inkrementellen Sicherungen, auf Datensicherheit zugunsten des Speicherbedarfs.
Chunking
Das Ziel ist es, die Daten so in Stücke zu zerlegen, dass möglichst viele identische Datenblöcke entstehen, die dedupliziert werden können. Der Vorgang zur Zerlegung heißt Chunking (von englisch chunk ‚Stück‘, ‚Block‘). Der Vorgang zur eindeutigen Identifikation von Blöcken heißt Fingerprinting und kann beispielsweise durch eine kryptographische Hashfunktion erfolgen.
Je kleinteiliger die Änderungen einer Datei bestimmt werden können, desto weniger muss redundant gesichert werden. Allerdings vergrößert sich dadurch der Index, also der Bauplan, wie und aus welchen Bestandteilen die Datei beim Aufruf wieder zusammengesetzt wird. Dieser Zielkonflikt muss bei der Wahl der Blockgröße für das Chunking berücksichtigt werden.
Weblinks
- Oliver Kluge: Dateisysteme mit Deduplizierung im Test. In: Linux-Magazin.
- Michael Bergler: Was ist de-dublication oder Deduplikation?
- Remove Duplicate Lines From a List, Online Deduplication. In: text-filter.com.