Deduplikation vs. Kompression: Zwei Ansätze zur Datenreduktion

Dem internationalen Markforschungsinstitut IDC zufolge verdoppelt sich die Datenmenge weltweit etwa alle 24 Monate. Bereits im Jahr 2020 soll das Digitale Universum ein Volumen von 44 Zettabyte umfassen. Umgerechnet wären das 44 Trillionen Gigabyte an Daten, die allein in einem Jahr produziert werden oder durch Kopie entstehen. Auswirkung hat diese Entwicklung vor allem auf Speichertechniken, Back-up-Prozeduren und Recovery-Systeme. Diese müssen in der Lage sein, die gewaltige Datenlast zu tragen und zu verarbeiten. Bei den Konzepten zur technischen Umsetzung stehen Methoden im Vordergrund, die eine Reduktion der physisch abgelegten Informationen ermöglichen und so die Kosten der Datenhaltung senken. Diese Methoden basieren im Wesentlichen auf zwei Ansätzen: Datenkompression und Deduplikation. Während die verlustfreie Kompression Redundanzen innerhalb einer Datei nutzt, um Daten zu verdichten, gleichen Deduplikations-Algorithmen Daten dateiübergreifend ab, um Wiederholungen zu vermeiden. Zentrales Anwendungsgebiet der Deduplikation ist daher die Datensicherung.

Deduplikation

Bei Deduplikation handelt es sich um einen Prozess der Datenreduktion, der im Wesentlichen auf einer Vermeidung von Datenredundanz auf einem Speichersystem beruht. Dabei kommt eine Deduplikations-Engine zum Einsatz, die sich spezieller Algorithmen bedient, um redundante Dateien oder Datenblöcke zu identifizieren und zu eliminieren. Sie lässt sich in eine Back-up-Software integrieren oder hardwarebasiert innerhalb des Speicher-Arrays sowie als zwischengeschaltete Appliance realisieren.

Ziel der Deduplikation in der Speichertechnik ist es, lediglich so viele Informationen auf einen nichtflüchtigen Datenträger zu schreiben, wie nötig sind, um eine Datei verlustfrei rekonstruieren zu können. Je mehr Duplikate entfernt werden, desto kleiner wird die Datenmenge, die gespeichert oder übertragen werden muss. Die Identifikation von Duplikaten kann wie beispielsweise bei Git oder Dropbox auf Datei-Ebene erfolgen, effizienter jedoch sind Deduplikations-Algorithmen, die auf der Sub-Datei-Ebene arbeiten. Dazu werden Dateien zunächst in Datenblöcke (Chunks) zerlegt und mit eindeutigen Prüfsummen, sogenannten Hashwerten, versehen. Als zentrale Kontrollinstanz dient eine Tracking-Datenbank, die sämtliche Prüfsummen beinhaltet.

Die blockbasierte Deduplikations-Methode untergliedert sich in 2 Varianten:

Deduplikation mit fester Blocklänge: Bei einer Deduplikation mit fester Blocklänge unterteilt der Algorithmus Dateien in Abschnitte mit exakt gleicher Länge. Diese orientiert sich in der Regel an der Clustergröße des Datei- oder RAID-Systems (typischerweise 4 KB), lässt sich mitunter jedoch auch manuell konfigurieren. In diesem Fall wird die individuell angepasste Blocklänge für alle Datenblöcke als Standard übernommen.

Deduplikation mit variabler Blocklänge: Bei einer Deduplikation mit variabler Blocklänge hingegen wird keine feste Standardlänge definiert. Stattdessen teilt der Algorithmus die Daten in unterschiedliche Blöcke auf, deren Länge je nach Art der zu verarbeitenden Daten variiert.

Die Art der Blockeinteilung hat einen gravierenden Einfluss auf die Effizienz der Datendeduplikation. Deutlich wird dies vor allem dann, wenn deduplizierte Dateien nachträglich verändert werden. Erweitert man einen Datenblock mit festen Blockgrenzen um zusätzliche Informationen, verschiebt sich in der Regel auch der Inhalt aller nachfolgenden Blöcke im Verhältnis zu den festdefinierten Blockgrenzen. Obwohl die Änderung nur einen Datenblock betrifft, werden auch alle nachfolgenden Segmente einer Datei aufgrund der Verschiebung der Blockgrenzen vom Deduplikations-Algorithmus als neu eingestuft. Es sei denn, die veränderten Bytes betragen exakt ein Mehrfaches der festgelegten Blocklänge. Da als neu eingestufte Datenblöcke erneut gesichert werden, erhöhen sich im Fall eines Back-ups bei einer Deduplikation mit fester Blocklänge sowohl der Rechenaufwand als auch die Auslastung der Bandbreite.

Nutzt ein Algorithmus hingegen variable Blockgrenzen, wirken sich die Veränderungen eines einzelnen Datenblocks nicht auf die angrenzenden Segmente aus. Stattdessen wird lediglich der veränderte Datenblock um die neuen Bytes erweitert und gespeichert. Dies entlastet das Netzwerk, da bei einem Back-up weniger Daten übertragen werden. Die Flexibilität in Bezug auf Dateiänderungen ist jedoch rechenintensiver, da ein Algorithmus erst einmal herausfinden muss, wie die Chunks aufgeteilt sind.

Die Identifizierung redundanter Chunks beruht auf der Annahme, dass Datenblöcke mit identischen Hashwerten identische Informationen beinhalten. Um redundante Chunks auszufiltern, braucht der Deduplikations-Algorithmus neu ermittelte Hashwerte somit lediglich mit der Tracking-Datenbank abzugleichen. Findet er dabei identische Prüfsummen, werden die redundanten Chunks durch einen Zeiger (Pointer) ersetzt, der auf den Speicherort des identischen Datenblocks verweist. Ein solcher Pointer nimmt deutlich weniger Platz in Anspruch als der Datenblock selbst. Je mehr Chunks in einer Datei durch Platzhalter ersetzt werden können, desto weniger Speicherplatz benötigt diese. Voraussagen lässt sich die Effizienz der Datenreduktion durch Deduplikations-Algorithmen jedoch nicht, da diese stark von der Ausgangsdatei und deren Datenstruktur abhängt. Zudem eignet sich die Deduplikation nur für unverschlüsselte Daten. Bei Verschlüsselungssystemen werden Redundanzen gezielt vermieden, was eine Mustererkennung unmöglich macht.

Deduplikation lässt sich entweder am Speicherziel oder an der Datenquelle realisieren.

Quell-Deduplikation

Werden redundante Daten bereits vor der Übertragung ans Speicherziel entfernt, spricht man von einer Quell-Deduplikation. Die Deduplikations-Engine ist in diesem Fall zum Beispiel in die Back-up-Software integriert. Redundante Informationen werden direkt im Dateisystem der Datenquelle eliminiert. Dazu scannt die Back-up-Software neu erstellte Datenblöcke in regelmäßigen Abständen und vergleicht diese mit denen, die bereits auf dem Back-up-Server gesichert wurden. Findet sich ein redundanter Dateiblock, wird dieser beim nächsten Back-up übersprungen. Wurde eine Datei überarbeitet, überträgt die Back-up-Software lediglich die neuen Datei-Anteile.

Der große Vorteil dieser Deduplikations-Methode ist, dass im Rahmen der Datensicherung lediglich neue Informationen an den Backup-Server übertragen werden, was sowohl die Bandbreite als auch die Kapazität des Speicherziels entlastet. Im Gegensatz zur Deduplikation am Speicherziel ist die quellenbasierte Methode jedoch mit einem deutlich höheren Rechenaufwand für die Back-up-Software verbunden und dadurch nicht für jedes Einsatzszenario geeignet.

Ziel-Deduplikation

Bei der Ziel-Deduplikation erfolgt die Datenreduktion außerhalb der Datenquelle. Dabei kann die Deduplikations-Engine entweder in das Hardware-Array integriert oder diesem als unabhängige Appliance vorgeschaltet werden. In beiden Fällen reduziert die Ziel-Deduplikation zwar die benötigte Speicherkapazität, anders als bei der Quell-Deduplikation hat dies jedoch keinen Einfluss auf die Datenmenge, die während des Back-ups vom Quellsystem zum Speicherziel über LAN oder WAN übertragen wird. Je nachdem, welcher Aufbau für die Ziel-Deduplikation gewählt wird, unterscheidet man zwischen Post-Process-Deduplikation und Inline-Deduplikation.

Post-Process-Deduplikation: Ist die Deduplikation-Engine in das Array integriert, werden Back-up Daten erst unmanipuliert auf dem Speichermedium abgelegt und anschließend dedupliziert. Man spricht in diesem Fall von Post-Process-Deduplikation oder nachfolgender Deduplikation. Diese Art der Deduplikation bietet den Vorteil, dass Daten relativ schnell auf das Speicherziel übertragen werden können. Allerdings stehen diese Daten nach der Übertragung nicht unmittelbar zur Verfügung, da der Back-up-Vorgang zunächst abgeschlossen sein muss, bevor Redundanzen eliminiert werden können. Somit werden Daten auf der Festplatte 3 Mal adressiert, bevor sie für eine Replikation oder den Abruf zur Verfügung stehen. Dies erhöht die Auslastung des Speichersystems. Zudem muss das Back-up-System zunächst 2 separate Speicherzonen zur Verfügung stellen: Eine für die Ausgangsdaten und eine für die deduplizierten Daten. Somit wird temporär deutlich mehr physikalischer Speicher benötigt als bei einer Deduplikation, die inline vonstattengeht. Anders als diese ermöglicht Post-Process-Deduplikation jedoch eine effizientere Datenreduktion auf Basis variabler Datenblöcke.

Inline-Deduplikation: Ist die Deduplikation-Engine vor dem Speichermedium angesiedelt, ist es möglich, redundante Daten unmittelbar während der Übertragung zu entfernen, noch bevor diese auf das Speichermedium geschrieben werden. Dies verringert zwar den Schreibdurchsatz und begrenzt die Deduplikation auf Datenblöcke mit fester Länge, verringert jedoch den benötigten physikalischen Speicher, der auf dem Zielsystem vorgehalten werden muss, im Vergleich zu einer nachfolgenden Deduplikation erheblich. Zudem stehen Daten, die inline dedupliziert wurden, unverzüglich zur Verfügung – zum Beispiel für eine Datenwiederherstellung oder die Vervielfältigung.

Datenkompression

Bei der Datenkompression werden Dateien in eine alternative Darstellung überführt, die effizienter ist als die ursprüngliche. Ziel dieser Codierung ist es, sowohl den benötigten Speicherplatz als auch die Übertragungszeit zu reduzieren. Solch ein Codiergewinn lässt sich dabei durch 2 unterschiedliche Ansätze erreichen:

Redundanz-Kompression: Bei einer verlustfreien Kompression auf Grundlage einer Redundanzreduktion lassen sich Daten auch nach der Kompression wieder bit-genau dekomprimieren. Eingangs- und Ausgangsdaten sind somit identisch. Eine solche Redundanz-Kompression ist nur möglich, wenn eine Datei redundante Informationen beinhaltet.

Irrelevanz-Kompression: Bei einer verlustbehafteten Kompression werden irrelevante Informationen entfernt, um eine Datei zu komprimieren. Dies geht in jedem Fall mit einem Datenverlust einher. Die Ursprungsdaten lassen sich nach einer Irrelevanz-Kompression daher nur noch annähernd wiederherstellen. Welche Daten als irrelevant eingestuft werden, ist Ermessenssache. Bei einer Audiokompression via MP3 werden beispielsweise Frequenzmuster entfernt, von denen angenommen wird, dass der Mensch diese kaum oder gar nicht hört.

Während Kompression auf der Ebene von Speichersystemen grundsätzlich verlustfrei erfolgt, werden Datenverluste in anderen Bereichen wie der Bild-, Video- und Audio-Übertragung bewusst in Kauf genommen, um eine Reduktion der Dateigröße zu erzielen.

Sowohl die Codierung als auch die Decodierung einer Datei erfordert Berechnungsaufwand. Dieser hängt in erster Linie von der verwendeten Kompressionsmethode ab. Während einige Techniken auf eine möglichst kompakte Darstellung der Ausgangsdaten ausgelegt sind, steht bei anderen eine Reduktion der benötigten Rechenzeit im Mittelpunkt. Die Wahl der Kompressionsmethode richtet sich daher immer nach den Anforderungen des Einsatzgebiets.

Im Rahmen einer Live-Übertragung von Video- oder Tonaufnahmen empfiehlt sich beispielsweise ein Verfahren, das eine möglichst schnelle Kompression und Wiederherstellung der Daten ermöglicht. Ein vergleichsweise geringerer Codiergewinn und mögliche Qualitätseinbußen sind in diesem Fall vertretbar. Anders hingegen verhält es sich mit Dateien, die einer großen Anzahl von Nutzern über einen File-Server zur Verfügung stehen sollen. Hier kann ein höherer Zeitaufwand für die Kompression in Kauf genommen werden, sodass in diesem Fall in der Regel ein leistungsfähiger Kompressions-Algorithmus zum Einsatz kommt, der ohne Qualitätsverluste einen hohen Codiergewinn ermöglicht.

Cloud Backup von IONOS

Maximaler Schutz für Ihre Unternehmensdaten: Einfache Backups für Cloud-Infrastruktur, PCs und Smartphones, inklusive persönlichem Berater!

Umfassender Schutz

Einfache Wiederherstellung

Schnelle Datenspeicherung

Verlustfreie Datenkompression

Während ein Deduplikations-Algorithmus nach gleichen Datenabschnitten in unterschiedlichen Dateien sucht und redundante Datensegmente durch verweisende Platzhalter ersetzt, arbeiten Verfahren zur verlustfreien Datenkompression mit sogenannten Repräsentanzen. Dabei werden Abschnitte, die sich innerhalb einer Datei mehrmals wiederholen, durch eine deutlich kürzere Darstellung ersetzt. Veranschaulichen lässt sich dies an folgendem Beispiel.

Ausgangstext: ABCDEABCEEABCEE

Codierung: ABC = 1; EE = 2

Komprimierter Text: 1DE1212

Der Ausgangstext mit einer Länge von 15 Zeichen lässt sich durch die Codierung auf 7 Zeichen verkürzen. Der Codiergewinn beträgt somit mehr als 50 Prozent. Voraussetzung für eine solche Kompression ist jedoch, dass sowohl das codierende als auch das decodierende System die Codierung kennen.

Die meisten verlustfreien Verfahren nutzen die Wiederholung von Zeichen oder Zeichenkombinationen innerhalb einer Datei. Bekannte wiederholungsbasierte Kompressionsverfahren sind das Word-Coding und das Lempel-Ziv-Verfahren (LZ77).

Word-Coding: Kompressionsverfahren auf Basis des Word-Codings eigenen sich vor allem für Textdateien. Grundprinzip ist das Ersetzen von Wörtern durch kürzere Repräsentanzen. Dazu wird im ersten Schritt eine Liste angelegt und jedem Wort in der Datei ein Wert zugewiesen. So lassen sich ganze Texte in Zahlencodes umrechnen.

Ausgangstext:                       sein oder nicht sein

Codierung:                           sein = 1; oder = 2, nicht = 3

Komprimierter Text:              1231

Da bei diesem Kompressionsverfahren zusätzlich zu den Nutzdaten auch die Wortliste gespeichert werden muss, ist Word-Coding bei längeren Texten mit vielen Wiederholungen am effektivsten.

Lempel-Ziv-Verfahren: Auch das Lempel-Ziv-Verfahren stellt eine wörterbuchbasierte Methode dar, die es ermöglicht, Zeichenfolgen auf Grundlage von Redundanzen zu komprimieren. Dabei nutzt der Kompressions-Algorithmus den bisher eingelesenen Inhalt als Wörterbuch, sodass selbiges nicht zusätzlich mitgeliefert werden muss. Der Verweis auf eine identische Zeichenfolge im bisher eingelesenen Datenstrom erfolgt durch ein sogenanntes Tripel, das Position und Länge des zu kopierenden Teils sowie das erste nicht übereinstimmende Zeichen codiert. Der Abgleich erfolgt durch einen Suchpuffer und einen Vorschaupuffer. Findet sich für ein Zeichen keine Übereinstimmung, lautet das Tripel (0, 0, x), wobei x für das entsprechende Zeichen steht. Folgendes Beispiel zeigt eine LZ77-Codierung des Wortes BANANE:

Die Zeichen bzw. Zeichenfolgen im Vorschaupuffer werden mit den bereits eingelesenen Zeichen im Suchpuffer vergleichen. Finden sich Übereinstimmungen, werden die entsprechenden Zeichen im Vorschaupuffer durch ein verweisendes Tripel ersetzt. In Zeile 4 kommt es zu einer Ersetzung der Zeichen ANE durch das Tripel (2,2, E). Dieses liest sich folgendermaßen:

2 = Ersetze die aktuelle Zeichenfolge durch eine bereits eingelesene Zeichenfolge die an Position 2 des Suchpuffers beginnt (A).

2 = Die Ersetzung umfasst zwei Zeichen (A und N)

E = Das erste Zeichen nach der Ersetzung lautet E.

Da sich die meisten Daten mittels LZ77 effektiv komprimieren lassen, sind Nachfolger dieses Algorithmus – wie LZSS – bis heute weit verbreitet, unter anderem werden sie für das Zip-Dateiformat, in PNG-Bildern oder in PDFs genutzt.

Neben wiederholungsbasierten Verfahren kommen bei der verlustfreien Kompression zudem häufigkeitsbasierte Methoden wie die Lauflängen-Codierung oder die Huffman-Codierung zum Einsatz.

Lauflängen-Codierung: Bei der Lauflängen-Codierung werden Redundanzen ins Visier genommen, die durch ein Aufeinanderfolgen gleicher Zeichen in einer Sequenz entstehen. Verdeutlichen lässt sich dies an der schematischen Darstellung einer einzelnen Bildzeile einer Schwarz-Weiß-Grafik.
Ausgangsdaten: WWWWWSSSSWWSSWWWWWWSSSSSSWWW
Eine deutliche Reduktion der zu speichernden Daten ergibt sich hier, wenn sich wiederholende Zeichen als Wertpaar aus Zeichenwert und Anzahl der Wiederholungen notiert werden.
Komprimierte Datei: 5W4S2W2S6W6S3W

Die Lauflängen-Codierung kommt in der Bildkompression zum Einsatz, verliert jedoch umso stärker an Effizienz, je mehr Farbzustände codiert werden müssen. Während sich Schwarz-Weiß-Skizzen mit zwei Farbzuständen ausdrücken lassen, werden für 8-Bit-Graustufenbilder schon 256 Grautöne benötigt. Die Wahrscheinlichkeit, dass mehr als zwei aufeinanderfolgende Pixel den gleichen Farbwert aufweisen, nimmt bei komplexen Bildern mit feinen Farbabstufungen deutlich ab. Da die Codierung im Beispiel auf zweistelligen Wertpaaren basiert, ergibt sich ein Codiergewinn hier erst, wenn mindestens 3 gleiche Zeichen aufeinanderfolgen. Eine abgewandelte Form der Lauflängen-Codierung ist Teil des bekannten JPEG-Bildkompressionsverfahrens.

Huffman-Codierung: Bei der Datenkompression gemäß Huffman wird zunächst die Häufigkeit aller in einer Datei vorkommenden Zeichen ermittelt. Im nächsten Schritt werden die Zeichen in eine Bit-Folge übersetzt, wobei sich die Länge der Repräsentanz nach der Häufigkeit richtet. Die grafische Darstellung der Huffman-Codierung erfolgt als Wurzelbaum mit den zu codierenden Zeichen als Blätter. Veranschaulichen lässt sich dies am Beispielsatz „this is an example of a huffman tree“.

Zeichen

Leerzeichen

a

e

f

h

i

m

n

s

t

l

o

p

r

u

x

Häufigkeit

7

4

4

3

2

2

2

2

2

2

1

1

1

1

1

1

Die jeweilige Binär-Codierung eines Zeichens ergibt sich aus dem Pfad von der Wurzel zum Blatt. Wobei Verzweigungen nach links mit einer 0 und Verzweigungen nach rechts mit einer 1 codiert werden.

Huffman Coding — Quelle: https://en.wikipedia.org/wiki/Huffman_coding#/media/File:Huffman_tree_2.svg

Für die Zeichen des Beispielsatzes ergibt sich somit folgender Code:

Leerzeichen	a	e	f	h	i	m	n
111	010	000	1101	1010	1000	0111	0010
s	t	l	o	p	r	u	x
1011	0110	11001	00110	10011	11000	00111	10010

Während sich häufig vorkommende Zeichen wie das Leerzeichen, a und e in diesem Beispiel mit lediglich 3 Bit codieren lassen, erfordern seltenere Zeichen wie r, u oder x 5 Bit. Im Vergleich dazu verwendet der Zeichensatz ASCII beispielsweise 7 Bit pro Zeichen. In ASCII-kompatiblen Zeichensätzen wie UTF-8 oder ISO 8859-1 (Latin-1) wird in der Regel jedoch ein achtes Bit ergänzt, da heutige Rechner mit 8,16,32 oder 64 Bit arbeiten. In der Huffman-Codierung lässt sich Text somit deutlich kompakter speichern.

Folgende Zeichenkette zeigt den Beispielsatz „this is an example of a huffman tree“ als Binärfolge nach Huffman:

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

Im Vergleich dazu die Bitfolge für den gleichen Inhalt gemäß ASCII-Codierung mit ergänztem achten Bit (jeweils die erste Null):

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101

Je nach Verteilung der Zeichenhäufigkeit lassen sich mit der Huffman-Codierung Daten auf bis zu 1/3 der ursprünglichen Größe reduzieren. Zu beachten ist jedoch, dass auch der Wurzelbaum zur anschließenden Decodierung gespeichert werden muss.

Eine Huffman-Codierung kommt nicht nur bei der Kompression von Textdateien zu Einsatz. Anwendung findet die Methode auch als Teilschritt des Bildkompressionsverfahrens JPEG und im Zip-Format, das eine Kombination aus LZSS und Huffman darstellt.

Verlustbehaftete Kompression

Während die verlustfreie Datenkompression nur dann möglich ist, wenn sich innerhalb einer Datei Redundanzen finden, ist die verlustbehaftete Datenkompression auf Basis der Irrelevanz-Reduktion prinzipiell immer möglich. Vorausgesetzt man nimmt Datenverluste in Kauf. Grundsätzlich beinhaltet die verlustbehaftete Datenkompression somit immer eine Entscheidung darüber, welcher Anteil der Originaldaten entbehrlich ist. Eine theoretische Grenze für eine maximale Kompression lässt sich mit der Rate-Distortion-Theorie ausloten, die das Verhältnis von Kompression und Signalqualität beschreibt.

Verlustbehaftete Kompressionsverfahren orientieren sich in der Regel an der menschlichen Wahrnehmung. So werden bei der Kompression von Audiodaten durch MP3, AAC oder WMA beispielsweise die Frequenzanteile entfernt, die außerhalb des menschlichen Hörbereichs liegen. Ein gängiges Beispiel für Irrelevanz-Reduktion im Bildbericht ist das JPEG-Verfahren, das verlustfreie und verlustbehaftete Kompressionsmethoden kombiniert. Zu Letzteren zählen beispielsweise die Farbumrechnung vom RGB-Farbraum ins YCbCr-Farbmodell, die diskrete Cosinus-Transformation (DCT) sowie die Quantisierung.

Deduplikation und Datenkompression im Vergleich

Um Back-up-Prozeduren zu realisieren oder die Ablage in Standard-Dateisystemen zu optimieren, setzen Unternehmen in der Regel auf Deduplikation. Dies liegt vor allem daran, dass Deduplikations-Systeme extrem effizient arbeiten, wenn identische Dateien abgelegt werden sollen.

Datenkompressionsverfahren hingegen sind in der Regel mit einem höheren Rechenaufwand verbunden und benötigen daher aufwendigere Plattformen. Am effektivsten lassen sich Speichersysteme mit einer Kombination beider Datenreduktionsverfahren nutzen. Dabei werden Redundanzen aus den zu speichernden Dateien zunächst durch Deduplikation entfernt und die verbliebenen Daten anschließend komprimiert.