So sieht Redundanz aus

Redundanzcodes* werden in Computersystemen häufig eingesetzt, um die Zuverlässigkeit der Datenspeicherung zu erhöhen. Bei Yandex kommen sie in vielen Projekten zum Einsatz. Zum Beispiel spart der Einsatz von Redundanzcodes anstelle von Replikation in unserem internen Objektspeicher Millionen, ohne die Zuverlässigkeit zu beeinträchtigen. Trotz ihrer breiten Anwendung ist eine verständliche Erklärung, wie Redundanzcodes funktionieren, selten zu finden. Diejenigen, die mehr darüber erfahren möchten, stoßen auf folgendes (aus Wikis):

Ich heiße Vadim und arbeite bei Yandex an der Entwicklung des internen Objektspeichers MDS. In diesem Artikel werde ich die theoretischen Grundlagen der Redundanzcodes (Reed-Solomon-Codes und LRC) in einfachen Worten erklären. Ich werde erläutern, wie es funktioniert, ohne komplizierte Mathematik oder seltene Begriffe. Am Ende werde ich Beispiele für die Verwendung von Redundanzcodes bei Yandex geben.

Einige mathematische Details werde ich nicht näher erläutern, aber ich werde Links bereitstellen für diejenigen, die tiefer eintauchen möchten. Außerdem möchte ich anmerken, dass einige mathematische Definitionen möglicherweise nicht strikt sind, da der Artikel nicht für Mathematiker, sondern für Ingenieure gedacht ist, die die Grundlagen verstehen möchten.

* In der englischsprachigen Literatur werden Redundanzcodes oft als Erasure Codes bezeichnet.

1. Die Grundlagen der Redundanzcodes

Die grundlegende Idee aller Redundanzcodes ist äußerst einfach: Daten so zu speichern (oder zu übertragen), dass sie bei Fehlern (wie Festplattenausfällen, Übertragungsfehlern usw.) nicht verloren gehen.

In den meisten Redundanzcodes werden die Daten in n Datenblöcke aufgeteilt, für die m Redundanzcodeblöcke berechnet werden. Insgesamt ergibt sich also eine Anzahl von n + m Blöcken. Die Redundanzcodes werden so konstruiert, dass n Datenblöcke wiederhergestellt werden können, indem man nur einen Teil der n + m Blöcke verwendet. Im Folgenden betrachten wir nur blockbasierte Redundanzcodes, das heißt, solche, bei denen die Daten in Blöcke unterteilt sind.

Um alle n Datenblöcke wiederherzustellen, benötigt man mindestens n von n + m Blöcken, da man n Blöcke nicht mit nur n-1 Block erhalten kann (in diesem Fall müsste man 1 Block "aus der Luft" nehmen). Reichen n beliebige Blöcke aus n + m Blöcken zur Wiederherstellung aller Daten? Das hängt vom Typ der Redundanzcodes ab; beispielsweise ermöglichen Reed-Solomon-Codes die Wiederherstellung aller Daten mit beliebigen n Blöcken, während LRC-Redundanzcodes das nicht immer tun.

Datenspeicherung

In Datenspeichersystemen wird in der Regel jeder der Datenblöcke und Redundanzcode-Blöcke auf einer separaten Festplatte gespeichert. Dadurch können die ursprünglichen Daten auch bei einem Ausfall einer beliebigen Festplatte wiederhergestellt und gelesen werden. Daten können sogar bei gleichzeitigen Ausfällen mehrerer Festplatten wiederhergestellt werden.

Datenübergabe

Redundanzcodes können zur zuverlässigen Datenübertragung in unzuverlässigen Netzwerken eingesetzt werden. Die übertragenen Daten werden in Blöcke unterteilt, für die Redundanzcodes berechnet werden. Sowohl die Datenblöcke als auch die Redundanzcodes werden über das Netzwerk übertragen. Bei Fehlern in beliebigen Blöcken (bis zu einer bestimmten Anzahl von Blöcken) können die Daten dennoch ohne Fehler über das Netzwerk übertragen werden. Reed-Solomon-Codes werden beispielsweise zur Datenübertragung über optische Kommunikationsleitungen und in der Satellitenkommunikation verwendet.

* Es gibt auch Redundanzcodes, bei denen die Daten nicht in Blöcke unterteilt werden, wie zum Beispiel Hamming-Codes und CRC-Codes, die weit verbreitet in Ethernet-Netzen genutzt werden. Diese Codes sind für fehlerresistente Kodierung gedacht; sie dienen der Fehlererkennung, nicht der Fehlerkorrektur (der Hamming-Code ermöglicht zudem teilweise Fehlerkorrekturen).

2. Reed-Solomon-Codes

Die Reed-Solomon-Codes gehören zu den am weitesten verbreiteten Redundanzcodes, die bereits in den 1960er Jahren entwickelt wurden und erstmals in den 1980er Jahren für die Serienproduktion von Compact Discs breite Anwendung fanden.

Zwei wesentliche Fragen zum Verständnis der Reed-Solomon-Codes sind: 1) Wie erstellt man Redundanzcodes? 2) Wie stellt man Daten mithilfe von Redundanzcodes wieder her? Wir werden Antworten darauf finden.
Zur Vereinfachung nehmen wir im Folgenden an, dass n=6 und m=4. Andere Schemen werden analog betrachtet.

Wie man Redundanzcodes erstellt

Jeder Redundanzcodeblock wird unabhängig von den anderen betrachtet. Für die Berechnung jedes Blocks werden alle n Datenblöcke verwendet. In der folgenden Abbildung stehen X1-X6 für die Datenblöcke, P1–P4 für die Redundanzcodeblöcke.

Alle Datenblöcke müssen die gleiche Größe haben; zur Ausrichtung können Nullbits verwendet werden. Die entstandenen Redundanzcodeblöcke haben die gleiche Größe wie die Datenblöcke. Alle Datenblöcke werden in Wörter aufgeteilt (beispielsweise in 16-Bit-Wörter). Angenommen, wir haben die Datenblöcke in k Wörter unterteilt. Dann werden auch alle Redundanzcodeblöcke in k Wörter unterteilt.

Zur Berechnung des i-ten Wortes jedes Redundanzcodeblocks werden die i-ten Wörter aller Datenblöcke verwendet. Diese werden nach folgender Formel berechnet:

Hier sind die Werte x – Wörter der Datenblöcke, p – Wörter der Blockcodes zur Redundanz, alle Alpha, Beta, Gamma und Delta – speziell ausgewählte Zahlen, die für alle i gleich sind. Zunächst sei gesagt, dass all diese Werte keine gewöhnlichen Zahlen sind, sondern Elemente eines Galois-Feldes; die Operationen +, -, *, / sind nicht die gewohnten Operationen, sondern spezielle Operationen, die über den Elementen des Galois-Feldes definiert wurden.

Wozu dienen Galois-Felder?

Es scheint einfach zu sein: Wir teilen die Daten in Blöcke, die Blöcke in Wörter, und unter Verwendung der Wörter der Datenblöcke berechnen wir die Wörter der Redundanzcodes – wir erhalten die Redundanzcodes. Im Großen und Ganzen funktioniert das so, aber der Teufel steckt im Detail:

Wie oben erwähnt, ist die Wortgröße fix, in unserem Beispiel 16 Bit. Die oben angegebenen Formeln für die Reed-Solomon-Codes sind so gestaltet, dass bei der Verwendung gewöhnlicher Ganzzahlen das Ergebnis der Berechnung p möglicherweise nicht mit einem Wort von zulässiger Größe darstellbar ist.
Beim Datenwiederherstellungsverfahren werden die oben genannten Formeln als Gleichungssystem betrachtet, das gelöst werden muss, um die Daten wiederherzustellen. Während des Lösens kann es erforderlich sein, ganze Zahlen zu dividieren, was zu einer reellen Zahl führt, die nicht exakt im Computer gespeichert werden kann.

Diese Herausforderungen machen es unmöglich, für die Reed-Solomon-Codes ganze Zahlen zu verwenden. Die Lösung des Problems ist originell und kann wie folgt beschrieben werden: Lassen Sie uns spezielle Zahlen erfinden, die mit Worten der erforderlichen Länge (z. B. 16 Bit) dargestellt werden können, wobei das Ergebnis aller darauf durchgeführten Operationen (Addition, Subtraktion, Multiplikation, Division) ebenfalls in der Computer-Speicher mit Wörtern der entsprechenden Länge dargestellt wird.

Solche "speziellen" Zahlen werden seit Langem in der Mathematik untersucht und als Felder bezeichnet. Ein Feld ist eine Menge von Elementen mit bestimmten für sie definierten Operationen wie Addition, Subtraktion, Multiplikation und Division.

Galois-Felder* sind Felder, für die für jede Operation (+, -, *, /) zwischen beliebigen zwei Elementen ein eindeutiges Ergebnis existiert. Galois-Felder können für Zahlen konstruiert werden, die eine Potenz von 2 sind: 2, 4, 8, 16 usw. (tatsächlich auch für jede Potenz einer Primzahl p, aber in der Praxis interessieren wir uns nur für Potenzen von 2). Zum Beispiel ist für Worte mit einer Größe von 16 Bit dieses Feld das, das 65.536 Elemente enthält, für jede Paar, von denen das Ergebnis jeder Operation (+, -, *, /) bestimmt werden kann. Die Werte x, p, alpha, beta, gamma, delta aus den obigen Gleichungen werden für Berechnungen als Elemente des Galois-Feldes verwendet.

Somit haben wir ein Gleichungssystem, mit dem wir redundant Codeblöcke erstellen können, indem wir das entsprechende Computerprogramm schreiben. Mit diesem Gleichungssystem können wir auch Daten wiederherstellen.

* Dies ist keine strikte Definition, sondern eher eine Beschreibung.

Wie man Daten wiederherstellt

Wiederherstellung ist erforderlich, wenn von n + m Blöcken einige Blöcke fehlen. Dies können sowohl Datenblöcke als auch Blöcke von Redundanzcodes sein. Das Fehlen von Datenblöcken und/oder Redundanzcodeblöcken bedeutet, dass die entsprechenden Variablen x und/oder p in den obigen Gleichungen unbekannt sind.

Die Gleichungen für Reed-Solomon-Codes können als Gleichungssystem betrachtet werden, in dem alle Werte Alpha, Beta, Gamma, Delta - Konstanten sind, und alle x und p, die den verfügbaren Blöcken entsprechen, - bekannte Variablen sind, während andere x und p - unbekannt sind.

Angenommen, die Datenblöcke 1, 2, 3 und der Redundanzcodeblock 2 sind nicht verfügbar, dann hat die i-te Blockgruppe folgendes Gleichungssystem (unbekannte sind rot markiert):

Wir haben ein System aus 4 Gleichungen mit 4 Unbekannten, also können wir es lösen und die Daten wiederherstellen!

Aus diesem Gleichungssystem ergeben sich mehrere Schlussfolgerungen zur Datenwiederherstellung für Reed-Solomon-Codes (n Datenblöcke, m Redundanzcodeblöcke):

Daten können wiederhergestellt werden, wenn bis zu m Blöcke verloren gehen. Bei einem Verlust von m+1 oder mehr Blöcken kann die Datenwiederherstellung nicht durchgeführt werden: Es ist unmöglich, ein System aus m Gleichungen mit m + 1 Unbekannten zu lösen.
Um auch nur einen Block Daten wiederherzustellen, müssen beliebige n der verbleibenden Blöcke verwendet werden, wobei jeder der Redundanzcodes eingesetzt werden kann.

Was sollte man sonst noch wissen?

In der oben genannten Beschreibung lasse ich einige wichtige Fragen außer Acht, die eine tiefere Beschäftigung mit der Mathematik erfordern. Insbesondere sage ich nichts über Folgendes:

Das Gleichungssystem für Reed-Solomon-Codes muss (eine eindeutige) Lösung für alle Kombinationen von Unbekannten (nicht mehr als m Unbekannte) haben. Basierend auf dieser Anforderung werden die Werte für Alpha, Beta, Gamma und Delta ausgewählt.
Das Gleichungssystem muss automatisch aufgebaut (abhängig davon, welche Blöcke nicht verfügbar sind) und gelöst werden können.
Ein Galois-Feld muss aufgebaut werden: für eine gegebene Wortgröße müssen die Ergebnisse beliebiger Operationen (+, -, *, /) für beliebige zwei Elemente gefunden werden.

Am Ende des Artikels finden sich Literaturverweise zu diesen wichtigen Themen.

Die Wahl von n und m

Wie wählt man in der Praxis n und m aus? In der Praxis werden Redundanzcodes in Datenspeichersystemen verwendet, um Platz zu sparen, weshalb m immer kleiner als n gewählt wird. Ihre konkreten Werte hängen von mehreren Faktoren ab, darunter:

Zuverlässigkeit der Datenspeicherung. Je größer m ist, desto mehr Festplattenausfälle kann das System überstehen, das heißt, die Zuverlässigkeit ist höher.
Redundanz der Speicherung. Je höher das Verhältnis m / n ist, desto größer ist die Redundanz der Speicherung und desto teurer wird das System.
Verarbeitungszeiten von Anfragen. Je größer die Summe n + m ist, desto länger wird die Antwortzeit auf Anfragen sein. Da zum Lesen der Daten (während der Wiederherstellung) n Blöcke gelesen werden müssen, die auf n verschiedenen Festplatten gespeichert sind, wird die Lesezeit durch die langsamste Festplatte bestimmt.

Außerdem bringt die Speicherung von Daten in mehreren Rechenzentren zusätzliche Einschränkungen bei der Auswahl von n und m mit sich: Wenn ein Rechenzentrum ausfällt, müssen die Daten weiterhin lesbar sein. Beispielsweise muss bei der Speicherung von Daten in 3 Rechenzentren die Bedingung m >= n/2 erfüllt sein, da es ansonsten zu einer Situation kommen kann, in der die Daten bei einem Ausfall eines Rechenzentrums nicht mehr lesbar sind.

3. LRC — Lokale Rekonstruktionscodes

Zum Wiederherstellen von Daten mit Reed-Solomon-Codes müssen n beliebige Datenblöcke verwendet werden. Das ist ein erheblicher Nachteil für verteilte Datenspeichersysteme, da für die Wiederherstellung von Daten auf einer defekten Festplatte die Daten von den meisten anderen gelesen werden müssen, was eine große zusätzliche Belastung für die Festplatten und das Netzwerk verursacht.

Die häufigsten Fehler sind die Nichterreichbarkeit eines Datenblocks aufgrund einer Fehlfunktion oder Überlastung einer Festplatte. Gibt es Möglichkeiten, die übermäßige Belastung bei der Wiederherstellung von Daten in solch einem (häufigen) Fall zu reduzieren? Tatsächlich gibt es einen Lösungsansatz: Speziell dafür wurden LRC-Redundanzcodes entwickelt.

LRC (Local Reconstruction Codes) – Redundanzcodes, die von Microsoft für die Verwendung in Windows Azure Storage entwickelt wurden. Die Idee hinter LRC ist einfach: Teilen Sie alle Datenblöcke in zwei (oder mehr) Gruppen und berechnen Sie einen Teil der Redundanzcodes für jede Gruppe separat. Ein Teil der Redundanzcodes wird unter Verwendung aller Datenblöcke (in LRC als globale Redundanzcodes bezeichnet) berechnet, während der andere Teil mithilfe einer der beiden Gruppen von Datenblöcken berechnet wird (diese werden als lokale Redundanzcodes bezeichnet).

LRC wird durch drei Zahlen dargestellt: n-r-l, wobei n die Anzahl der Datenblöcke, r die Anzahl der globalen Redundanzcodes und l die Anzahl der lokalen Redundanzcodes ist. Um Daten zu lesen, wenn ein Datenblock nicht verfügbar ist, müssen Sie nur n/l Blöcke lesen – das ist l-mal weniger als bei Reed-Solomon-Codes.

Betrachten wir als Beispiel das LRC-Schema 6-2-2. X1–X6 sind 6 Datenblöcke, P1, P2 sind 2 globale Redundanzblöcke, P3, P4 sind 2 lokale Redundanzblöcke.

Die Redundanzprüfziffern P1 und P2 werden mit allen Datenblöcken berechnet. Die Redundanzprüfziffer P3 wird mit den Datenblöcken X1–X3 berechnet, während die Redundanzprüfziffer P4 mit den Datenblöcken X4–X6 erfolgt.

Der Rest erfolgt im LRC analog zu den Reed-Solomon-Codes. Die Gleichungen zur Berechnung der Prüfzahlen für die Redundanz werden wie folgt aussehen:

Um die Werte für Alpha, Beta, Gamma und Delta zu bestimmen, müssen mehrere Bedingungen erfüllt sein, die die Möglichkeit der Datenrekonstruktion gewährleisten (d.h. die Lösung des Gleichungssystems). Weitere Details dazu finden Sie in Artikel.
In der Praxis wird auch für die Berechnung der lokalen Redundanzcodes P3 und P4 die XOR-Operation angewendet.

Aus dem Gleichungssystem für LRC ergeben sich mehrere Schlussfolgerungen:

Um einen beliebigen Datenblock wiederherzustellen, reicht es aus, n/l Blöcke zu lesen (n/2 in unserem Beispiel).
Wenn r + l Blöcke nicht verfügbar sind und alle Blöcke zu einer Gruppe gehören, können die Daten nicht wiederhergestellt werden. Dies lässt sich leicht am Beispiel erklären. Nehmen wir an, die Blöcke X1–X3 und P3 sind nicht verfügbar: Das sind r + l Blöcke aus einer Gruppe, insgesamt 4 in unserem Fall. Dann haben wir ein System aus 3 Gleichungen mit 4 Unbekannten, das sich nicht lösen lässt.
In allen anderen Fällen der Unzugänglichkeit von r + l Blöcken (wenn aus jeder Gruppe mindestens ein Block verfügbar ist) können die Daten im LRC wiederhergestellt werden.

Somit hat LRC Vorteile gegenüber den Reed-Solomon-Codes bei der Wiederherstellung von Daten nach einzelnen Fehlern. Bei Reed-Solomon-Codes müssen zur Wiederherstellung eines einzelnen Datenblocks n Blöcke verwendet werden, während für die Wiederherstellung eines Datenblocks im LRC nur n/l Blöcke benötigt werden (n/2 in unserem Beispiel). Auf der anderen Seite hat LRC im Vergleich zu Reed-Solomon-Codes eine Begrenzung bezüglich der maximal zulässigen Fehleranzahl. In den obigen Beispielen können die Reed-Solomon-Codes Daten bei bis zu 4 Fehlern wiederherstellen, während es für LRC 2 Kombinationen von 4 Fehlern gibt, bei denen eine Wiederherstellung nicht möglich ist.

Was wichtiger ist, hängt von der spezifischen Situation ab, aber oft überwiegt die Einsparung an redundanter Last, die LRC bietet, die etwas geringere Zuverlässigkeit der Speicherung.

4. Weitere Redundanzcodes

Neben Reed-Solomon-Codes und LRC gibt es viele andere Redundanzcodes. Verschiedene Redundanzcodes verwenden unterschiedliche mathematische Ansätze. Hier sind einige weitere Redundanzcodes:

Redundanzcode mittels XOR-Operator. Die XOR-Operation wird über n Datenblöcke ausgeführt, was zu 1 Block von Redundanzcodes führt, also Schema n+1 (n Datenblöcke, 1 Redundanzcode). Wird verwendet in RAID 5, wo Daten- und Redundanzcodeblöcke zyklisch auf alle Festplatten des Arrays geschrieben werden.
Der Even-Odd-Algorithmus, der auf der XOR-Operation basiert. Er ermöglicht die Erstellung von 2 Redundanzcodeblöcken, also Schema n+2.
Der STAR-Algorithmus, der auf der XOR-Operation basiert. Er ermöglicht die Erstellung von 3 Redundanzcodeblöcken, also Schema n+3.
Pyramide-Codes – weitere Redundanzcodes von Microsoft.

5. Verwendung bei Yandex

Eine Reihe von Infrastrukturprojekten von Yandex nutzt Redundanzcodes für eine zuverlässige Datenspeicherung. Hier sind einige Beispiele:

Das interne objektbasierte Speichersystem MDS, über das ich zu Beginn des Artikels geschrieben habe.
YT – das MapReduce-System von Yandex.
YDB (Yandex DataBase) – eine verteilte NewSQL-Datenbank.

Im MDS werden LRC-Redundanzcodes verwendet, Schema 8-2-2. Daten mit Redundanzcodes werden auf 12 verschiedene Festplatten in verschiedenen Servern in 3 verschiedenen Rechenzentren geschrieben: jeweils 4 Server in jedem Rechenzentrum. Weitere Informationen dazu finden Sie in Artikel.

In YT werden sowohl die Reed-Solomon-Codes (Schema 6-3), die zuerst implementiert wurden, als auch die LRC-Redundanzcodes (Schema 12-2-2) verwendet, wobei LRC die bevorzugte Speichermethode ist.

In YDB kommen Redundanzcodes zum Einsatz, die auf dem Even-Odd-Prinzip basieren (Schema 4-2). Über die Redundanzcodes in YDB wurde bereits beim Highload berichtet..

Die Anwendung verschiedener Redundanzschemas ist durch unterschiedliche Anforderungen an die Systeme bedingt. Beispielsweise werden in MDS die mit LRC gespeicherten Daten sofort in 3 Rechenzentren abgelegt. Es ist wichtig, dass die Daten weiterhin lesbar sind, selbst wenn eines der Rechenzentren ausfällt, daher müssen die Blöcke so auf die Rechenzentren verteilt werden, dass bei Ausfall eines Rechenzentrums die Anzahl der nicht verfügbaren Blöcke innerhalb der zulässigen Grenzen bleibt. Im Schema 8-2-2 können 4 Blöcke in jedem Rechenzentrum platziert werden, sodass bei Ausschaltung eines Rechenzentrums 4 Blöcke nicht verfügbar sind, aber die Daten weiterhin lesbar bleiben. Egal welches Schema wir bei der Verteilung auf 3 Rechenzentren wählen, es muss stets (r + l) / n >= 0,5 gelten, was bedeutet, dass die Redundanz der Speicherung mindestens 50 % beträgt.

Bei YT verhält es sich anders: Jeder YT-Cluster ist vollständig in einem Rechenzentrum untergebracht (verschiedene Cluster in verschiedenen Rechenzentren), daher gibt es dort keine solche Einschränkung. Das 12-2-2-Schema bietet eine Redundanz von 33 %, was bedeutet, dass die Speicherung von Daten kostengünstiger ist, während diese auch bis zu 4 gleichzeitige Ausfälle von Festplatten überstehen können, ähnlich wie im MDS-Schema.

Es gibt noch viele weitere Besonderheiten bei der Anwendung von Redundanzcodes in Speicher- und Verarbeitungssystemen: Aspekte der Datenwiederherstellung, die Auswirkungen der Wiederherstellung auf die Ausführungszeiten von Abfragen, Besonderheiten beim Schreiben von Daten usw. Ich plane, separat über diese und andere Besonderheiten der praktischen Anwendung von Redundanzcodes zu berichten, wenn das Thema von Interesse ist.