Löschcodierung 101

Diesen Beitrag teilen

In den Produktdatenblättern fast aller Speicheranbieter taucht im Zusammenhang mit Speichermanagement immer häufiger der Begriff Erasure Coding (EC) auf. Insbesondere All-Flash-Arrays bieten kein RAID mehr. Erasure Coding ist für SSDs deutlich besser geeignet als herkömmliches RAID-5 oder RAID-6. In dem Artikel erklären wir die Grundbegriffe der Erasure Coding, erklären die grundlegende Funktion und gehen auf die Vor- und Nachteile der Erasure Coding ein.
Erasure Coding wird durch zwei unterschiedliche Entwicklungen in der Unternehmens-IT motiviert. Mit zunehmender Kapazität der Festplatten dauert der Wiederaufbau eines defekten RAIDs immer länger. Es dauert ungefähr 20 Stunden, um eine aktuelle 16-TB-Festplatte vollständig neu zu beschreiben. Um den produktiven I/O durch den RAID-Rebuild nicht zu stören, laufen diese Rebuilds meist im Hintergrund mit niedriger Priorität. Dadurch verlängert sich die Erholungszeit entsprechend. Umbauzeiten von 1-2 Tagen sind keine Seltenheit mehr. Zudem bedeutet der Umbau einer einzelnen Platte aufgrund der Funktion von RAID-5 oder RAID-6 auch viel mechanische Belastung für alle Platten im RAID-Verbund. Es ist durchaus möglich, dass bei einem Rebuild weitere Platten ausfallen. In Umgebungen mit vielen Festplatten geht man daher oft weg von RAID-6 hin zur Mehrfachreplikation. Der komplette Datensatz wird also redundant (oft 3 mal) gespeichert. Dies erfordert entsprechend viele Speichermedien und erschwert die Dateiverwaltung.
Eine weitere Herausforderung ist die zunehmende Verbreitung virtueller Umgebungen und hyperkonvergenter Infrastrukturen (HCI). Dateisysteme umfassen nicht mehr nur Festplatten oder SSDs innerhalb eines Systems. Verteilte Dateisysteme bieten einen konsistenten Namensraum über mehrere Systeme hinweg. Dadurch ist es sehr einfach, z. B. um eine virtuelle Maschine auf einem beliebigen Host innerhalb der HCI zu starten. RAID funktioniert nur innerhalb eines Systems. Diese Einschränkung kann durch Löschcodierung aufgehoben werden.

Löschcodierung. Was ist es?

Die Löschcodierung gehört zum Bereich der sogenannten Fehlerkorrekturcodes, manchmal auch als Vorwärtsfehlerkorrektur (FEC) bezeichnet. Erasure Coding hat seinen wissenschaftlichen Hintergrund im mathematischen Bereich der linearen Algebra. Diese Codes werden seit den 1960er Jahren intensiv erforscht. Solche Codes wurden schon früh für die digitale Datenübertragung auf Langstrecken eingesetzt. Löschcodierung auf Datenträgern wurde erstmals 1982 mit der Einführung von Audio-CDs kommerziell genutzt. Löschcodes werden auch auf DVDs und bei DVB-S verwendet.
Der bekannteste Algorithmus ist der Reed-Solomon-Algorithmus, benannt nach den beiden Erfindern (beide Mathematiker). Daneben gibt es noch eine Reihe weiterer Algorithmen mit diversen Vor- und Nachteilen. Die Forschung ist noch lange nicht abgeschlossen, der intensive Einsatz von Erasure Coding wirft neue Fragen und Probleme auf, die es wert sind, näher betrachtet zu werden.
Das Grundprinzip dieser Codes ist jedoch immer gleich: Daten, die in ein System gelangen, werden in eine festgelegte Anzahl gleich großer Chunks (Data Chunks) aufgeteilt. Diese Chunks werden dann mit mathematischen Verfahren um Redundanzinformationen ergänzt (Redundanz-Chunks). Schließlich werden Datenblöcke und Redundanzblöcke auf einem Speichermedium gespeichert. Für Redundanzblöcke (horizontale Codes) können separate Platten bereitgestellt werden, oder die Redundanzinformationen werden zusammen mit Datenblöcken (vertikale Codes) auf dieselben Platten geschrieben. Letzteres ist die weitaus häufigere Methode.

Terminologie und Notation

Eine typische Schreibweise für die Löschcodierung wäre so etwas wie EC(20,16) oder EC(12,9). Mathematisch und allgemein ausgedrückt ist dies EC(n,k). Dabei ist n die Gesamtzahl der Festplatten in einem System und k die Anzahl der Datenfestplatten. Die Differenz n–k ist die Anzahl der Festplatten, die für Redundanz verwendet werden. Gleichzeitig ist dies auch die Anzahl der Festplatten, die in einem solchen Verbund ausfallen können, ohne dass die Datenintegrität verletzt wird. In der Praxis kursiert immer häufiger der deutlich verständlichere Begriff Erasure Coding 9+3. In diesem Beispiel ist die Erasure Coding 9+3 identisch mit EC(12,9). In diesem Verbund rotieren insgesamt 12 Platten, von denen 3 ausfallen können, ohne dass Daten verloren gehen.
Aufteilung von Festplatten zur Löschcodierung mit der Notation EC(20,16)
Das Verhältnis von Daten- zu Redundanzbrocken kann je nach verwendetem Algorithmus in Grenzen individuell eingestellt werden. Das Verhältnis wirkt sich auf die Leistung, die Anzahl der Festplatten, die ausfallen können, und die im Falle einer Wiederherstellung erforderliche CPU- und Netzwerkleistung aus. In der Praxis kann oder muss der Storage-Admin das Verhältnis selten individuell festlegen. In der Verwaltungsoberfläche bieten die Hersteller iie R. mehrere vorkonfigurierte Löschcodierungen an. Der Administrator muss dann nur noch zwischen Geschwindigkeitsoptimierung, Kapazitätsoptimierung oder Zuverlässigkeitsoptimierung wählen und überlässt es der Firmware, die passende Löschcodierung auszuwählen.

Vorteile des Erasure Coding

Erasure Coding kann mehr und flexiblere Redundanz bieten als RAID-5 und RAID-6. Dies haben wir bereits kurz skizziert. Neben den technischen Vorteilen ist beim Erasure Coding in der Regel auch die Anschaffung der Hardware deutlich günstiger, da im Vergleich zu RAID deutlich weniger Festplatten bei gleicher oder besserer Redundanz benötigt werden.
Ein Rechenbeispiel:
Wir gehen davon aus, dass ein Speichersystem die Löschcodierung EC(12,9) oder 9+3 anbietet. In einem Setup mit insgesamt 12 Festplatten können also 3 Festplatten ausfallen und die Datenintegrität bleibt erhalten. Diese Redundanz ist mit herkömmlichem RAID nicht möglich. Um eine Redundanz größer als zwei Platten zu erhalten, würde man zB auf ein RAID-5 mit drei Ablegern zurückgreifen. Wir gehen weiterhin davon aus, dass wir moderne 16 TB Festplatten verwenden. Diese Platten kosten derzeit (September 2020) jeweils rund 400 €. Der EC(12,9) hat neun Datenplatten, dh 9 x 16 TB = 144 TB nutzbar für das Dateisystem. Insgesamt müssen 12 Platten beschafft werden, also 12 x 400 € = 4,800 €.
Ganz anders sieht die Rechnung bei gleicher nutzbarer Kapazität aber dreifacher Replikation eines RAID-5 aus. Für 144 TB nutzbare Kapazität benötigt man auch hier 9 Platten. Zusätzlich eine zehnte Platte für Redundanz in einem RAID-5. Da wir aber dreifach redundant schreiben, braucht man letztendlich 3 x 10 Platten = 30 Platten. Mit denselben 16-TB-Festplatten wie oben erhalten Sie 30 x 400 € = 12,000 € Anschaffungskosten. In diesem Beispiel ist RAID-5 mit Replikation zweieinhalb Mal so teuer in der Anschaffung wie ein ebenso redundantes System auf Basis von Erasure Coding.
Weitere Einsparungen ergeben sich aus dem geringeren Platzbedarf (Volumen und Footprint) im Rechenzentrum (12 Platten vs. 30 Platten). Damit einher gehen eine Reduzierung des Stromverbrauchs und eine Klimatisierung des Serverraums. Letzteres spielt allerdings bei der TCO-Betrachtung im Gesamtbetrieb nur eine marginale Rolle.

Jede Medaille hat zwei Seiten

Wenn eine Festplatte oder ein Speicherknoten ausfällt, müssen die Daten rekonstruiert werden. Dazu werden verschiedene noch intakte Datenbrocken sowie intakte Redundanzbrocken ausgelesen und daraus die fehlenden Daten nach dem Erasure-Coding-Algorithmus berechnet. Die Wiederherstellung mit Erasure Coding ist etwas rechenintensiver als dies bei herkömmlichem RAID der Fall ist. Je nach Algorithmus kann die Wiederherstellung besonders E/A-intensiv sein, da möglicherweise viele Chunks gelesen werden müssen. Bei verteilten Dateisystemen muss dieser Umstand bei der Dimensionierung der Netzwerkverbindungen berücksichtigt werden.
Neuere Implementierungen im Bereich HCI und verteilte Dateisysteme verwenden sogenannte Locally Repairable Codes (LRC). Redundanz wird so hergestellt und verteilt, dass z. B. der Ausfall einer einzelnen Platte innerhalb eines Storage Nodes auch innerhalb des betroffenen Storage Nodes rekonstruiert werden kann. Somit entsteht im Falle einer Wiederherstellung kein zusätzlicher Netzwerkverkehr. Chunks von benachbarten Nodes müssen nur dann gelesen werden, wenn mehrere Platten oder ein kompletter Storage Node ausfallen. Bei einem RAID-Rebuild wird eine ausgefallene und ausgetauschte Festplatte blockweise identisch mit dem Zustand vor dem Ausfall beschrieben. Bei der Löschcodierung werden die Redundanzinformationen in einem verteilten System gespeichert. Während des Neuaufbaus können die aufgrund eines Festplattenausfalls fehlenden Daten- und Redundanzblöcke neu berechnet und auf die verbleibenden Festplatten im System geschrieben werden. Dadurch ist die I/O-Performance einer einzelnen Festplatte nicht mehr der Flaschenhals bei einem Rebuild, wie es bei RAID der Fall ist.
Viele Unternehmensspeichersysteme verwenden jetzt Löschcodierung. Auch alle Cloud-Anbieter setzen bei ihren Speicherprodukten auf Erasure Coding. Bei Cristie Data verwenden wir auch Erasure Coding, zB bei unseren CLOUDBRIK-Angeboten.