Sven Erik Matzen

Software Architect | Cloud & Security Expert | AI-enabled Solutions

Elf Neunen: Erasure Coding, Reed-Solomon und wie die Cloud Daten praktisch unverlierbar macht

🎧 Listen to this article

Cloud Computing · 2026-08-07

EU-Kennzeichnung: vollständig KI-generierter Inhalt Vollständig KI-generierter Artikel (ohne Vorabprüfung).

Der Aufhänger: Die Festplatte, die sterben darf

Es gibt eine Zahl, die auf den Produktseiten der großen Cloud-Speicherdienste steht und die so selbstverständlich daherkommt, dass man sie kaum noch liest: 99,999999999 Prozent. Elf Neunen. Amazon nennt sie für S3, und andere Anbieter versprechen Ähnliches. In Worte übersetzt bedeutet sie: Wenn du zehn Millionen Objekte speicherst, musst du im statistischen Mittel damit rechnen, alle zehntausend Jahre eines davon zu verlieren. Anders gesagt: Ein einzelnes Objekt hat eine erwartete Lebensdauer, die die Existenzdauer der menschlichen Zivilisation um Größenordnungen übertrifft.

Das ist eine erstaunliche Behauptung, denn sie wird auf einer Grundlage aufgestellt, die alles andere als zuverlässig ist. Festplatten sterben. Sie sterben ständig, in jedem Rechenzentrum, jeden Tag. Eine einzelne Magnetplatte hat eine jährliche Ausfallrate von einigen Prozent; in einem Speichersystem mit Hunderttausenden von Laufwerken fällt praktisch stündlich eines aus. Server stürzen ab, Netzteile brennen durch, ganze Racks verlieren den Strom, und gelegentlich fällt eine komplette Halle aus. Aus lauter unzuverlässigen Bauteilen ein System zu bauen, das seine Daten mit elf Neunen bewahrt, ist ungefähr so, als wollte man aus einer Handvoll notorisch unpünktlicher Menschen ein Uhrwerk bauen, das auf die Millisekunde genau geht.

Der naive Weg dorthin ist alt und einfach: Mach Kopien. Speichere jedes Datum nicht einmal, sondern dreimal, auf drei verschiedenen Laufwerken in drei verschiedenen Racks. Fällt eines aus, sind noch zwei da. Das funktioniert – und es war jahrelang der De-facto-Standard, etwa im ursprünglichen Hadoop Distributed File System mit seinem Replikationsfaktor drei. Aber es hat einen brutalen Preis: Für jedes nützliche Byte zahlst du drei Byte. Zwei Drittel deiner teuren, stromfressenden, gekühlten Speicherinfrastruktur enthalten reine Redundanz. Bei den Datenmengen moderner Cloud-Anbieter – S3 verwaltet inzwischen Hunderte Billionen Objekte – ist das keine Fußnote, sondern ein Kostenfaktor, der über Milliarden entscheidet.

Es gibt einen eleganteren Weg, und er stammt aus einem mathematischen Aufsatz von 1960, lange bevor es Cloud-Speicher, Festplatten in dieser Form oder das Internet gab. Er heißt Erasure Coding, und sein bekanntester Vertreter ist der Reed-Solomon-Code. Seine Idee ist so kontraintuitiv wie schön: Man kann Redundanz hinzufügen, ohne Daten zu kopieren – indem man aus den Daten mathematische „Prüfsummen" berechnet, die so beschaffen sind, dass sich aus einer beliebigen ausreichenden Teilmenge aller Fragmente das Ganze rekonstruieren lässt. Statt drei vollständiger Kopien genügt am Ende ein Overhead von vielleicht fünfzig, dreißig oder gar achtzehn Prozent, um dieselbe oder eine bessere Ausfallsicherheit zu erreichen.

Für jemanden wie Sven – Senior AI Engineer mit einem Bein in der Cloud-Architektur und einem in der IT-Sicherheit – ist Erasure Coding ein Musterbeispiel dafür, wie ein tiefes mathematisches Resultat direkt in bare Betriebskosten und in eine harte Verfügbarkeitszusage übersetzt wird. Dieser Artikel nimmt dich auf die ganze Strecke mit: von der Frage, was „Langlebigkeit" überhaupt bedeutet, über die verblüffend einfache Grundidee, die Mathematik der Reed-Solomon-Codes und ihre Geschichte, bis zum eigentlichen Schmerzpunkt der Praxis – der Reparatur – und den klugen Codes, die eigens dafür erfunden wurden.

Teil 1: Zwei Begriffe, die man ständig verwechselt – Langlebigkeit und Verfügbarkeit

Bevor wir zur Mechanik kommen, lohnt es sich, zwei Eigenschaften scharf zu trennen, die im Marketing und in Alltagsgesprächen unentwegt durcheinandergeworfen werden, obwohl sie völlig verschiedene Dinge meinen.

Die erste ist Langlebigkeit (englisch durability). Sie beantwortet die Frage: Ist mein Datum überhaupt noch vorhanden – heute, in zehn Jahren, nach beliebig vielen Hardware-Ausfällen? Langlebigkeit betrifft den dauerhaften, nicht wiederherstellbaren Verlust. Ein Datum, das verloren ist, ist für immer weg; keine Wartezeit bringt es zurück. Die elf Neunen von S3 sind eine Langlebigkeitszusage.

Die zweite ist Verfügbarkeit (englisch availability). Sie beantwortet die Frage: Kann ich in diesem Moment auf mein Datum zugreifen? Ein Datum kann perfekt sicher gespeichert sein und trotzdem gerade unerreichbar – etwa weil der Server, der es hält, neu startet, weil eine Netzwerkverbindung gestört ist oder weil eine ganze Verfügbarkeitszone kurzzeitig offline ist. Verfügbarkeit wird typischerweise in weniger Neunen angegeben: Vier Neunen (99,99 Prozent) bedeuten schon rund eine Stunde Ausfall im Jahr.

Der Unterschied ist mehr als akademisch. Langlebigkeit und Verfügbarkeit stellen unterschiedliche Anforderungen an das System, und ein guter Speicherentwurf optimiert beide getrennt. Erasure Coding ist in erster Linie ein Werkzeug für Langlebigkeit – es sorgt dafür, dass Daten Ausfälle überleben. Dass sie auch jederzeit erreichbar sind, ist eine zweite Eigenschaft, die durch geografische Verteilung, Caching und schnelle Reparatur erkauft wird. Wir werden sehen, dass genau an dieser Nahtstelle – Langlebigkeit billig erreichen, ohne die Verfügbarkeit und die Reparaturkosten zu ruinieren – die interessantesten Ingenieursentscheidungen liegen.

Wie kommt man überhaupt auf eine Zahl wie elf Neunen? Vereinfacht so: Man modelliert die jährliche Ausfallwahrscheinlichkeit eines einzelnen Speicherfragments, man weiß, wie viele Fragmente gleichzeitig ausfallen müssen, damit ein Datum unrettbar verloren ist, und man weiß, wie schnell das System einen ausgefallenen Fragment ersetzt (repariert), bevor der nächste ausfällt. Aus dem Zusammenspiel dieser drei Größen – Ausfallrate, Anzahl tolerierbarer gleichzeitiger Ausfälle und Reparaturgeschwindigkeit – ergibt sich die Langlebigkeit. Erasure Coding wirkt auf die zweite Größe (es erhöht die Zahl tolerierbarer Ausfälle pro gespeichertem Byte dramatisch), und die Reparaturgeschwindigkeit ist der Grund, warum die im späteren Teil behandelten „lokalen" Codes erfunden wurden.

Teil 2: Die Grundidee – Redundanz ohne Kopie

Beginnen wir mit einem Bild, das ganz ohne höhere Mathematik auskommt und dennoch den Kern trifft.

Angenommen, du hast zwei Zahlen, a und b, und möchtest sie so speichern, dass du den Verlust eines beliebigen Speichermediums überlebst. Der Kopie-Ansatz: Speichere a und b je zweimal, auf vier Medien. Overhead: 100 Prozent. Der Erasure-Ansatz: Speichere a auf Medium 1, b auf Medium 2 und ihre Summe p = a + b auf Medium 3. Jetzt liegen drei Werte auf drei Medien, Overhead nur 50 Prozent. Fällt irgendein einzelnes Medium aus, kannst du den fehlenden Wert aus den beiden übrigen zurückrechnen: Fehlt a, so ist a = p − b; fehlt b, so ist b = p − a; fehlt p, so ist es ohnehin egal, denn a und b sind ja noch da. Ein einziges „Paritätssymbol" schützt zwei Datensymbole gegen einen beliebigen Ausfall.

Das ist im Kern das Prinzip von RAID-5 und, ausbuchstabiert, von jedem Erasure Code. Verallgemeinert lautet es: Man nimmt k Datenfragmente, berechnet aus ihnen m Paritätsfragmente und speichert alle n = k + m Fragmente auf n verschiedenen Ausfalldomänen (Laufwerken, Servern, Racks, Rechenzentren). Der entscheidende Anspruch, den ein guter Code erfüllt, ist verblüffend stark:

Aus beliebigen k der n Fragmente lässt sich das ursprüngliche Datum vollständig rekonstruieren.

Das heißt: Das System toleriert den gleichzeitigen Verlust von bis zu m Fragmenten – egal welche m es sind. Ein Code, der diese Eigenschaft besitzt, heißt MDS-Code (Maximum Distance Separable). Er ist in einem präzisen Sinn optimal: Mit m Paritätsfragmenten kann man höchstens m Ausfälle tolerieren (das besagt die sogenannte Singleton-Schranke), und ein MDS-Code erreicht dieses Maximum. Reed-Solomon-Codes sind MDS. Nichts wird verschwendet: Jedes einzelne Paritätsfragment kauft dir genau einen weiteren tolerierbaren Ausfall.

Rechne einmal nach, was das bedeutet. Ein Code mit k = 6 Daten- und m = 3 Paritätsfragmenten (n = 9) hat einen Speicher-Overhead von 9/6 = 1,5 – also 50 Prozent zusätzlich – und übersteht drei gleichzeitige Ausfälle. Dreifache Replikation hat 200 Prozent Overhead und übersteht ebenfalls „nur" zwei Ausfälle (bei drei verlorenen Kopien ist das Datum weg). Der Erasure Code ist also gleichzeitig sparsamer und ausfallsicherer. Facebooks HDFS nutzt RS(10,4): zehn Daten, vier Parität, Overhead 1,4, übersteht vier beliebige Ausfälle. Backblaze speichert in seinen „Vaults" mit 17+3: siebzehn Daten, drei Parität, Overhead nur rund 1,18, übersteht drei Ausfälle. Man sieht die Stellschraube: Je größer man k relativ zu m wählt, desto geringer der Overhead – aber desto größer auch die „Streubreite", über die ein Datum verteilt liegt, mit Folgen für die Reparatur, auf die wir noch kommen.

Die naheliegende Frage ist: Wie berechnet man die Paritätsfragmente so, dass die MDS-Eigenschaft garantiert gilt – dass wirklich jede Teilmenge von k Fragmenten genügt, nicht nur manche? Die einfache Summe von oben reicht dafür nicht, sobald man mehr als ein Paritätsfragment will (zwei simple Summen wären linear abhängig und schützten nicht gegen zwei Ausfälle). Hier kommt die Mathematik von Reed und Solomon ins Spiel.

Teil 3: Die Mathematik der Reed-Solomon-Codes

Daten als Polynom

Die ursprüngliche Sichtweise von Irving Reed und Gustave Solomon aus dem Jahr 1960 ist von bestechender Klarheit. Fasse deine k Datensymbole d₀, d₁, …, d_{k-1} als die Koeffizienten eines Polynoms vom Grad k−1 auf:

P(x) = d₀ + d₁·x + d₂·x² + … + d_{k-1}·x^{k-1}

Ein solches Polynom ist durch k Koeffizienten eindeutig bestimmt – und, das ist der Clou, ebenso eindeutig durch seine Werte an k verschiedenen Stellen. Das ist der uralte Satz über Polynominterpolation: Durch k Punkte in allgemeiner Lage geht genau ein Polynom vom Grad k−1. Durch zwei Punkte geht genau eine Gerade (Grad 1), durch drei Punkte genau eine Parabel (Grad 2), und so weiter.

Jetzt kommt die Kodierung: Werte das Polynom nicht an k, sondern an n verschiedenen Stellen aus (x = 0, 1, 2, …, n−1). Das ergibt n Symbole – die kodierten Fragmente. Weil das Polynom nur Grad k−1 hat, ist es durch je k dieser n Werte bereits vollständig festgelegt. Verlierst du also bis zu m = n−k der Werte, kannst du aus den verbleibenden k das Polynom eindeutig interpolieren und daraus wieder alle ursprünglichen Koeffizienten – deine Daten – ablesen. Genau das ist die MDS-Eigenschaft, und sie ergibt sich hier zwangsläufig aus einem Satz der Algebra: n Auswertungen eines Polynoms vom Grad k−1, und je k davon rekonstruieren es. Reparatur ist Interpolation.

Warum endliche Körper – GF(2⁸)

Ein Detail macht das Ganze erst praktikabel. Würde man mit gewöhnlichen reellen Zahlen rechnen, würden die Auswertungen P(x) für große x astronomisch groß, die Rundungsfehler unbeherrschbar, und Symbole wären keine handlichen Bytes. Reed und Solomon rechnen deshalb nicht in den reellen Zahlen, sondern in einem endlichen Körper, auch Galois-Feld genannt (nach dem früh verstorbenen französischen Mathematiker Évariste Galois).

Ein endlicher Körper ist eine endliche Menge von Elementen, in der man wie gewohnt addieren, subtrahieren, multiplizieren und dividieren kann und in der alle vertrauten Rechengesetze gelten – nur dass das Ergebnis niemals aus der Menge herausläuft. Für Speichersysteme ist der Körper der Wahl GF(2⁸), das Galois-Feld mit 256 Elementen. Der Grund ist Bequemlichkeit: Jedes Element lässt sich als ein Byte darstellen. Ein Datensymbol ist ein Byte, ein Fragment ist eine Folge von Bytes, und die gesamte Codierung ist byteweise Arithmetik.

Die Arithmetik in GF(2⁸) ist reizvoll fremdartig. Die Addition ist einfach das bitweise XOR zweier Bytes – blitzschnell, und jedes Element ist sein eigenes Negatives (a + a = 0), sodass Addition und Subtraktion zusammenfallen. Die Multiplikation ist Polynommultiplikation der Bit-Muster modulo eines festen „primitiven" Polynoms achten Grades; für GF(2⁸) ist das üblicherweise x⁸ + x⁴ + x³ + x² + 1 (hexadezimal 0x11D). In der Praxis wird sie über kleine Log-/Antilog-Tabellen oder spezielle CPU-Befehle realisiert. Wichtig ist nur: In GF(2⁸) gelten alle Körperaxiome, also funktioniert die Polynominterpolation genau wie in der Schule – nur exakt, ohne Rundung, und mit Bytes als Zahlen.

Die Vandermonde-Matrix und systematische Codes

In der Praxis formuliert man die Kodierung selten als Polynomauswertung, sondern als Matrix-Vektor-Multiplikation, was auf dasselbe hinausläuft und auf moderner Hardware bequemer ist. Man packt die k Datensymbole in einen Vektor d und multipliziert ihn mit einer festen Generatormatrix G der Größe n × k:

c = G · d

Wählt man für G eine Vandermonde-Matrix (deren Zeilen die Potenzen 1, xᵢ, xᵢ², … der n Auswertungsstellen sind), so ist garantiert, dass je k Zeilen von G linear unabhängig sind – und genau das ist wieder die MDS-Eigenschaft: Aus je k der n kodierten Werte lässt sich d durch Lösen eines linearen Gleichungssystems (Invertieren der zugehörigen k × k-Teilmatrix) zurückgewinnen.

Ein praktischer Kniff verdient Erwähnung: der systematische Code. Man wählt G so (durch eine einfache Umformung), dass die ersten k kodierten Fragmente identisch mit den Originaldaten sind und nur die restlichen m Fragmente „echte" Paritätsdaten enthalten. Der Vorteil ist enorm: Solange alle Datenfragmente vorhanden sind (der Normalfall), muss man zum Lesen überhaupt nichts dekodieren – man liest die Daten einfach direkt. Die teure Interpolation fällt nur an, wenn tatsächlich ein Datenfragment fehlt und aus den Paritätsfragmenten wiederhergestellt werden muss. Fast alle produktiven Systeme – von RAID-6 über HDFS bis zu Backblazes offener Reed-Solomon-Bibliothek, die eine systematische Vandermonde-Konstruktion verwendet – arbeiten systematisch.

Fassen wir die Kette zusammen: Daten sind Koeffizienten eines Polynoms; Kodierung ist Auswertung an n Stellen (oder, äquivalent, Multiplikation mit einer Vandermonde-Matrix); gerechnet wird byteweise im Galois-Feld GF(2⁸); und weil je k Auswertungen ein Polynom vom Grad k−1 eindeutig festlegen, genügen beliebige k von n Fragmenten zur vollständigen Wiederherstellung. Das ist die ganze Magie – ein Satz über Polynome, in Betriebssicherheit übersetzt.

Teil 4: Von den Sternen zur Cloud – eine kurze Geschichte

Reed und Solomon veröffentlichten ihren Aufsatz „Polynomial Codes over Certain Finite Fields" 1960 im Journal of the Society for Industrial and Applied Mathematics. Ihr Motiv war nicht Speicherplatz, sondern fehlerbehaftete Übertragung: verrauschte Funkkanäle, bei denen einzelne Symbole verfälscht ankommen. Bemerkenswert ist, dass ihr Code zunächst eher eine mathematische Kuriosität blieb – ein effizientes Dekodierverfahren (der Berlekamp-Massey-Algorithmus) wurde erst Jahre später gefunden und machte die praktische Nutzung überhaupt erst möglich.

Danach eroberte Reed-Solomon fast unbemerkt die gesamte Technikwelt. Die Voyager-Sonden funkten ab den späten 1970ern ihre Bilder aus dem äußeren Sonnensystem mit Reed-Solomon-Schutz zur Erde. Die Compact Disc und später DVD verdanken ihm, dass ein Kratzer im Datenträger nicht die Musik zerstört – der Code füllt die Lücke aus der Redundanz auf. QR-Codes enthalten Reed-Solomon-Redundanz und bleiben deshalb selbst dann lesbar, wenn ein Teil des Musters verdeckt oder beschädigt ist. Auch DSL und digitales Fernsehen setzen darauf. Der 1960er-Aufsatz gehört zu jenen seltenen theoretischen Arbeiten, deren Anwendungen praktisch jeder Mensch täglich dutzendfach berührt, ohne es zu ahnen.

In der Speicherwelt kam der Code über einen Umweg an. Die RAID-Systeme der 1980er und 1990er begannen mit einfacher XOR-Parität (RAID-5, ein tolerierter Laufwerksausfall). Als Platten größer und die Rebuild-Zeiten länger wurden – und damit die Gefahr, dass während einer Reparatur ein zweites Laufwerk stirbt –, führte RAID-6 ein zweites, unabhängiges Paritätssymbol ein, und für dieses zweite Symbol braucht man genau die Reed-Solomon-Arithmetik über einem Galois-Feld. RAID-6 toleriert zwei gleichzeitige Ausfälle.

Der eigentliche Sprung kam mit den verteilten Speichersystemen der Cloud-Ära. Amazon S3 startete 2006 und war einer der ersten großmaßstäblichen kommerziellen Dienste, der auf Redundanz über viele Maschinen und Standorte hinweg setzte. Google, Facebook und Microsoft bauten in den folgenden Jahren riesige Speichersysteme, in denen dreifache Replikation aus Kostengründen zunehmend durch Erasure Coding ersetzt wurde. Ein sichtbarer Meilenstein im Open-Source-Bereich war HDFS-EC: Mit Hadoop 3.0 (2017) hielt natives Reed-Solomon-Erasure-Coding Einzug ins Hadoop-Ökosystem und senkte den Speicher-Overhead „kalter" Daten von 200 Prozent (dreifache Replikation) auf rund 40 bis 50 Prozent bei gleicher oder besserer Ausfallsicherheit. Der aktuelle Forschungsstand ist in einer 2025 erschienenen Übersichtsarbeit in den ACM Transactions on Storage dokumentiert, die Vergangenheit, Gegenwart und Zukunft des Erasure Coding für Speichersysteme zusammenfasst.

Teil 5: Der wunde Punkt – die Reparatur

Bis hierher klingt Erasure Coding wie ein reiner Gewinn: gleiche Sicherheit, weniger Speicher. Doch es gibt einen Preis, und er offenbart sich nicht beim Speichern, sondern beim Reparieren. Genau hier liegt die spannendste Ingenieursarbeit der letzten fünfzehn Jahre.

Warum Reparatur teuer ist

Bei dreifacher Replikation ist die Reparatur trivial. Fällt eine Kopie aus, kopiert man eine der beiden übrigen einfach auf ein neues Laufwerk – man liest genau so viele Daten, wie man wiederherstellt, und das von einer einzigen Quelle. Bei einem Reed-Solomon-Code ist das anders und viel unangenehmer: Um ein einziges verlorenes Fragment eines RS(k,m)-Codes wiederherzustellen, muss man k andere Fragmente vollständig lesen, sie über das Netzwerk zu einer Maschine transportieren und dort die Interpolation rechnen. Bei RS(10,4) bedeutet das: Um 1 Fragment zu ersetzen, liest man 10. Der Reparaturverkehr ist ein Vielfaches der reparierten Datenmenge.

Warum ist das schlimm? Weil Reparatur nicht die Ausnahme, sondern der Dauerzustand ist. In einem großen Cluster fällt ständig irgendwo etwas aus, und das System repariert permanent im Hintergrund. Dieser „Reparatur-Datenverkehr" verbraucht Netzwerkbandbreite und Platten-I/O, die dann für die eigentliche Nutzarbeit fehlen. Bei Facebook wurde beobachtet, dass die Reparatur von Reed-Solomon-kodierten Daten einen erheblichen Anteil des Cluster-internen Netzwerkverkehrs ausmachte – ein realer, messbarer Betriebskostenposten. Zudem verlängert teure Reparatur das Zeitfenster, in dem das System verwundbar ist: Solange ein Fragment fehlt, ist der Puffer gegen den nächsten Ausfall kleiner. Langsame Reparatur untergräbt direkt die Langlebigkeit.

Es gibt also einen fundamentalen Zielkonflikt: Große k senken den Speicher-Overhead, verteuern aber die Reparatur (man muss mehr Fragmente lesen). Das ist eine jener Abwägungen, die in verteilten Speichersystemen immer wiederkehren – man kann sich Speicher, Reparaturbandbreite und Ausfallsicherheit nicht gleichzeitig alle drei nach Wunsch aussuchen.

Local Reconstruction Codes – Microsofts Antwort

Der klügste Ausweg besteht darin, die klassische MDS-Eigenschaft ein kleines Stück weit aufzugeben, um die typische Reparatur – den Ausfall eines einzelnen Fragments, der weitaus häufigste Fall – drastisch zu verbilligen. Genau das leisten Local Reconstruction Codes (LRC), vorgestellt von Cheng Huang und Kollegen bei Microsoft in einem mit dem Best-Paper-Award ausgezeichneten Aufsatz auf der USENIX ATC 2012, der die Grundlage der Erasure-Coding-Schicht von Windows Azure Storage bildet.

Die Idee: Neben den globalen Paritätsfragmenten, die alle Daten schützen, führt man zusätzliche lokale Paritäten ein, von denen jede nur eine Gruppe der Datenfragmente absichert. Konkret teilt der in der Arbeit beschriebene LRC(12,2,2) die zwölf Datenfragmente in zwei Gruppen zu je sechs, berechnet für jede Gruppe eine lokale Parität und dazu zwei globale Paritäten – insgesamt sechzehn Fragmente, Overhead 16/12 ≈ 1,33. Fällt nun ein einzelnes Datenfragment aus, muss man es nicht mehr aus zwölf, sondern nur noch aus den sechs Fragmenten seiner lokalen Gruppe rekonstruieren. Der Reparaturverkehr für den häufigsten Fall halbiert sich. Der Preis dafür: Ein LRC ist kein reiner MDS-Code mehr – er kann nicht jede beliebige Kombination von Ausfällen in seiner Größenklasse tolerieren, sondern ist so konstruiert, dass er alle „realistischen" Ausfallmuster (jede Dreifachkombination und die allermeisten Vierfachkombinationen) auffängt, während er die seltenen, pathologischen Muster preisgibt. Für den Betrieb ist das ein hervorragender Tausch: geringer Speicher-Overhead und billige Reparatur, erkauft mit einem hauchdünnen, statistisch vernachlässigbaren Verlust an Ausfalltoleranz.

Facebooks „warmes" BLOB-Speichersystem f4, beschrieben auf der OSDI 2014, verfolgt eine verwandte Strategie mit Reed-Solomon und geografischer Verteilung, um selten geänderte, aber nicht kalte Daten platzsparend und trotzdem ausfallsicher zu halten. Beide Systeme zeigen dasselbe Muster: Der reine, mathematisch optimale Code ist selten das, was am Ende produktiv läuft; er wird um die praktischen Zwänge – Reparaturbandbreite, Rechenzentrumstopologie, Zugriffsmuster – herum maßgeschneidert.

Regenerating Codes – die theoretische Grenze

Parallel zur Ingenieurspraxis hat die Informationstheorie das Reparaturproblem grundsätzlich vermessen. In einer einflussreichen Arbeit führten Alexandros Dimakis und Kollegen 2010 die Regenerating Codes ein. Ihr Ausgangspunkt war ein überraschendes Ergebnis: Um ein verlorenes Fragment zu reparieren, muss man gar nicht k ganze Fragmente herunterladen – es genügt, von mehr Knoten je ein kleineres Stück zu holen. Mit Methoden des Network Coding leiteten sie eine fundamentale Schranke für den Zielkonflikt zwischen Speicher pro Knoten und Reparaturbandbreite ab und identifizierten zwei extreme Betriebspunkte: minimaler Speicher (MSR-Codes, so sparsam wie MDS, aber mit optimierter Reparatur) und minimale Reparaturbandbreite (MBR-Codes). Diese Arbeit hat ein ganzes Forschungsfeld begründet und liefert das theoretische Fundament, gegen das sich praktische Codes wie LRC messen lassen. Ich bin der Meinung, dass gerade dieses Wechselspiel – ein tiefes Unmöglichkeits-/Optimalitätsresultat auf der einen, pragmatische, betrieblich getriebene Konstruktionen auf der anderen Seite – Erasure Coding zu einem der lehrreichsten Felder der angewandten Informatik macht.

Teil 6: Die Praxis – wie elf Neunen wirklich zustande kommen

Kehren wir zur Eingangszahl zurück. Wie genau erreicht ein realer Dienst wie S3 seine elf Neunen? Erasure Coding ist eine notwendige, aber nicht die einzige Zutat. Es kommen mehrere Schichten zusammen.

Geografische Verteilung. Ein Code, dessen n Fragmente alle im selben Rack oder gar auf demselben Server liegen, schützt nur gegen Laufwerksausfälle, nicht gegen den Brand einer Halle. Große Dienste verteilen die Fragmente deshalb bewusst über mehrere Verfügbarkeitszonen – physisch getrennte Rechenzentren mit unabhängiger Stromversorgung und Kühlung. Amazon beschreibt S3 als so ausgelegt, dass es den gleichzeitigen Verlust von Daten in zwei Einrichtungen übersteht. Der Erasure Code sorgt dann dafür, dass selbst der Ausfall einer ganzen Zone nur einen Teil der Fragmente kostet – wenige genug, dass die verbleibenden zur Rekonstruktion reichen.

Prüfsummen und Scrubbing. Festplatten versagen nicht nur laut (das Laufwerk verschwindet), sondern auch leise: Ein Byte kippt, ohne dass die Platte es meldet – die sogenannte stille Datenkorruption oder bit rot. Dagegen speichert das System zu jedem Fragment eine Prüfsumme und liest im Hintergrund kontinuierlich alle Daten, verifiziert die Prüfsummen und ersetzt korrupte Fragmente proaktiv aus der Redundanz, lange bevor sie gebraucht werden. Dieses Scrubbing (auch anti-entropy oder background auditing) ist die stille Dauerarbeit, die verhindert, dass sich unbemerkte Fehler ansammeln, bis im Ernstfall die Redundanz nicht mehr reicht.

Schnelle, automatische Reparatur. Wie im vorigen Teil gesehen, ist die Reparaturgeschwindigkeit ein direkter Faktor der Langlebigkeitsrechnung. Je schneller ein ausgefallenes Fragment ersetzt wird, desto kürzer das Fenster erhöhter Verwundbarkeit. Deshalb investieren die Systeme so viel in billige (lokale) Reparatur.

Die konkreten Kennzahlen illustrieren den Gewinn. Backblaze hat sein Vorgehen öffentlich dokumentiert und sogar eine Reed-Solomon-Bibliothek quelloffen gemacht: In einem „Vault" wird jede Datei in 17 Datenfragmente zerlegt, um 3 Paritätsfragmente ergänzt und über 20 Laufwerke in 20 verschiedenen Servern verteilt. Das System übersteht den gleichzeitigen Ausfall von drei beliebigen dieser zwanzig Laufwerke, bei einem Speicher-Overhead von nur rund 18 Prozent – verglichen mit 200 Prozent bei dreifacher Replikation. Genau in dieser Zahl steckt der ökonomische Grund, warum Erasure Coding die Großspeicher der Welt erobert hat: Bei Exabyte-Beständen ist der Unterschied zwischen 1,18-fachem und 3-fachem physischem Speicher der Unterschied zwischen einem und mehreren Rechenzentren voller Festplatten.

Zum ehrlichen Bild gehören die Grenzen. Erasure Coding ist nicht kostenlos. Erstens die Rechenlast: Kodierung und – vor allem – Dekodierung kosten CPU-Zyklen (Galois-Feld-Arithmetik), weshalb Erasure Coding bevorzugt für „warme" bis „kalte" Daten eingesetzt wird, die selten geschrieben und nicht in Mikrosekunden gelesen werden müssen; heiße, latenzkritische Daten liegen oft weiterhin repliziert vor. Zweitens die schon behandelte Reparaturbandbreite. Drittens ein Nachteil bei kleinen Objekten: Ein Datum in k Fragmente zu zerlegen lohnt sich nur, wenn diese Fragmente eine sinnvolle Größe haben; für viele winzige Objekte entsteht Verwaltungs-Overhead, weshalb Systeme kleine Objekte oft erst zu großen Blöcken zusammenfassen, bevor sie kodieren. Und viertens die höhere Lese-Latenz im Fehlerfall: Fehlt ein Datenfragment, muss rekonstruiert werden, was langsamer ist als das bloße Lesen einer intakten Kopie. Es ist, wie so oft in der Speichertechnik, eine Frage der Abwägung zwischen Speicherplatz, Rechenaufwand, Latenz und Ausfallsicherheit – man kann nicht alle Ecken gleichzeitig gewinnen.

Erkenntnis zum Mitnehmen

Der Kerngedanke des Erasure Coding lässt sich in einem Satz fassen: Redundanz muss keine Kopie sein. Statt Daten stumpf zu vervielfachen, kann man sie in ein mathematisches Gewebe einbetten, aus dem sich das Ganze aus jeder ausreichenden Teilmenge zurückgewinnen lässt – und das für einen Bruchteil des Speicherpreises. Reed-Solomon-Codes leisten das seit 1960 mit einem einzigen tiefen Prinzip: Daten sind ein Polynom, und ein Polynom vom Grad k−1 ist durch je k seiner Werte eindeutig bestimmt.

Doch die eigentliche, übertragbare Lehre steckt in der zweiten Hälfte der Geschichte. Der mathematisch optimale Code (der reine MDS-Reed-Solomon) ist selten der, der am Ende in Produktion läuft. Erst die Auseinandersetzung mit den praktischen Zwängen – wie teuer ist die Reparatur, wie ist das Rechenzentrum topologisch aufgebaut, welche Ausfallmuster sind realistisch, welche vernachlässigbar – führt zu den Codes, die tatsächlich Milliarden Objekte tragen: Local Reconstruction Codes, die etwas theoretische Optimalität gegen billige Reparatur tauschen. Für Svens Arbeit – ob in der Cloud-Architektur oder im Sicherheitsdesign – ist das die eigentlich wertvolle Haltung: Ein System nicht nur gegen den Normalbetrieb zu entwerfen, sondern explizit gegen den Ausfall und, noch eine Ebene tiefer, gegen die Kosten der Wiederherstellung nach dem Ausfall. Die Frage lautet nie nur „Wie schütze ich das Datum?", sondern „Was kostet es mich, wenn ich es reparieren muss – und wie oft werde ich das tun?"

Reflexionsfrage

Erasure Coding erkauft dramatische Speichereinsparungen mit teurer Reparatur, und die klügsten realen Systeme geben ein Quäntchen mathematische Optimalität preis, um den häufigsten Fehlerfall billig zu machen. Wo in deinen eigenen Systemen optimierst du implizit für den seltenen Katastrophenfall, obwohl die eigentlichen Betriebskosten im häufigen Kleinfall stecken – und würdest du, wie die LRC-Erfinder, bewusst eine Spur theoretischer Sauberkeit gegen einen handfesten Gewinn im Alltagsbetrieb tauschen?

Querverweise im Vault

Quellen

Hinweis: Dieser Artikel gibt den überprüfbaren, wissenschaftlich gesicherten Stand wieder. Wo eigene Einschätzungen einfließen, sind sie mit „Ich bin der Meinung, dass ..." gekennzeichnet.

← All articles