So sieht Überflüssigkeit aus

Fehlerkorrekturcodes* werden in Computersystemen häufig verwendet, um die Zuverlässigkeit der Datenspeicherung zu erhöhen. Bei Yandex werden sie in vielen Projekten eingesetzt. Zum Beispiel ermöglicht der Einsatz von Fehlerkorrekturcodes anstelle von Replikation in unserem internen Objektspeicher, Millionen zu sparen, ohne die Zuverlässigkeit zu verringern. Doch trotz ihrer weit verbreiteten Anwendung sind verständliche Beschreibungen, wie Fehlerkorrekturcodes funktionieren, äußerst selten. Diejenigen, die mehr darüber erfahren möchten, stoßen oft auf Folgendes (aus Wikis):

Mein Name ist Vadim, ich arbeite bei Yandex an der Entwicklung des internen Objektspeichers MDS. In diesem Artikel werde ich die theoretischen Grundlagen der Fehlerkorrekturcodes (Reed-Solomon-Codes und LRC) mit einfachen Worten erklären. Ich werde erläutern, wie sie funktionieren, ganz ohne komplizierte Mathematik und seltene Begriffe. Am Ende werde ich Beispiele für die Verwendung von Fehlerkorrekturcodes bei Yandex anführen.

Einige mathematische Details werde ich nicht ausführlich behandeln, aber ich werde Links bereitstellen für diejenigen, die tiefer eintauchen möchten. Ich möchte auch darauf hinweisen, dass einige mathematische Definitionen nicht strikt sein können, da der Artikel nicht für Mathematiker, sondern für Ingenieure gedacht ist, die das Thema verstehen möchten.

* In der englischen Literatur werden Fehlerkorrekturcodes häufig als Erasure Codes bezeichnet.

1. Die Grundidee der Fehlerkorrekturcodes

Die grundlegende Idee aller Fehlerkorrekturcodes ist ganz einfach: Daten so zu speichern (oder zu übertragen), dass sie bei Fehlern (Festplattenschäden, Übertragungsfehlern usw.) nicht verloren gehen.

In den meisten* Fehlerkorrekturcodes werden Daten in n Datenblöcke aufgeteilt, für die m Fehlerkorrekturblöcke berechnet werden, sodass insgesamt n + m Blöcke entstehen. Die Fehlerkorrekturcodes werden so konstruiert, dass man n Datenblöcke wiederherstellen kann, indem man nur einen Teil der n + m Blöcke verwendet. Im Folgenden werden wir uns ausschließlich mit blockweisen Fehlerkorrekturcodes befassen, das heißt mit solchen, bei denen die Daten in Blöcke unterteilt werden.

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

Datenspeicherung

In Datenspeichersystemen wird in der Regel jeder Datenblock und jeder Redundanzcode auf einer separaten Festplatte gespeichert. Somit können die ursprünglichen Daten auch bei einem Ausfall einer beliebigen Festplatte trotzdem wiederhergestellt und gelesen werden. Die Daten können auch dann wiederhergestellt werden, wenn mehrere Festplatten gleichzeitig ausfallen.

Datenübertragung

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

* Es gibt auch Redundanzcodes, bei denen die Daten nicht in Blöcke unterteilt werden, beispielsweise Hamming-Codes und CRC-Codes, die häufig für die Datenübertragung in Ethernet-Netzwerken verwendet werden. Dies sind Codes zur fehlerkorrigierenden Codierung, die für die Fehlererkennung und nicht zur Fehlerkorrektur bestimmt sind (der Hamming-Code erlaubt auch teilweise Fehlerkorrekturen).

2. Reed-Solomon-Codes

Die Reed-Solomon-Codes sind einer der am weitesten verbreiteten Redundanzcodes, die in den 1960er Jahren erfunden wurden und in den 1980er Jahren erstmals für die Serienproduktion von CDs weithin Anwendung fanden.

Zwei Schlüsselfragen für das Verständnis der Reed-Solomon-Codes sind: 1) wie man Redundanzcodeblöcke erstellt; 2) wie man Daten mit Hilfe von Redundanzcodeblöcken wiederherstellt. Lassen Sie uns Antworten auf diese Fragen finden.
Zur Vereinfachung nehmen wir im Folgenden an, dass n=6 und m=4. Andere Konstellationen werden analog betrachtet.

Wie man Redundanzcodeblöcke erstellt

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

Alle Datenblöcke müssen gleich groß sein, zur Ausrichtung können Null-Bits verwendet werden. Die resultierenden Redundanzcode-Blöcke haben die gleiche Größe wie die Datenblöcke. Alle Datenblöcke werden in Wörter unterteilt (z. B. 16 Bit). Angenommen, wir haben die Datenblöcke in k Wörter unterteilt. Dann werden auch alle Redundanzcode-Blöcke in k Wörter unterteilt.

Für die Berechnung des i-ten Wortes jedes Redundanzblocks werden die i-ten Wörter aller Datenblöcke verwendet. Sie werden nach der folgenden Formel berechnet:

Hier sind die Werte x die Wörter der Datenblöcke, p die Wörter der Redundanzcode-Blöcke, und alle Alpha, Beta, Gamma und Delta sind speziell ausgewählte Zahlen, die für alle i gleich sind. Es sei gleich gesagt, dass all diese Werte keine gewöhnlichen Zahlen sind, sondern Elemente des Galois-Feldes. Die Operationen +, -, *, / sind keine für uns gewohnten Operationen, sondern spezielle Operationen, die über den Elementen des Galois-Felds eingeführt wurden.

Warum werden Galois-Felder benötigt

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

Wie bereits erwähnt, ist die Wortgröße festgelegt, in unserem Beispiel 16 Bit. Die obigen Formeln für die Reed-Solomon-Codes sind so, dass bei Verwendung gewöhnlicher Ganzzahlen das Ergebnis der Berechnung von p möglicherweise nicht durch ein Wort der zulässigen Größe dargestellt werden kann.
Bei der Wiederherstellung von Daten werden die obigen Formeln als Gleichungssystem betrachtet, das gelöst werden muss, um die Daten wiederherzustellen. Während des Lösungsprozesses kann es notwendig sein, ganze Zahlen durch einander zu teilen, wobei das Ergebnis eine reelle Zahl ist, die nicht genau im Speicher des Computers dargestellt werden kann.

Diese Probleme verhindern die Verwendung ganzer Zahlen für Reed-Solomon-Codes. Die Lösung des Problems ist originell und lässt sich wie folgt beschreiben: Lassen Sie uns spezielle Zahlen erfinden, die man mit Wörtern der gewünschten Länge (z. B. 16 Bit) darstellen kann, und das Ergebnis aller Operationen (Addition, Subtraktion, Multiplikation, Division) wird ebenfalls im Speicher des Computers mithilfe von Wörtern der gewünschten Länge dargestellt.

Solche "speziellen" Zahlen werden seit langem von Mathematikern erforscht und heißen Körper. Ein Körper ist eine Menge von Elementen mit definierten Operationen der Addition, Subtraktion, Multiplikation und Division.

Galois-Körper* sind Körper, für die für jede Operation (+, -, *, /) und für beliebige zwei Elemente des Körpers ein eindeutiges Ergebnis existiert. Galois-Körper können für Zahlen konstruiert werden, die Potenzen von 2 sind: 2, 4, 8, 16 usw. (tatsächlich Potenzen jeder Primzahl p, aber in der Praxis interessieren wir uns nur für Potenzen von 2). Zum Beispiel ist für Wörter mit einer Größe von 16 Bit dieser Körper, der 65.536 Elemente enthält, für die jede Paarung ein Ergebnis jeder Operation (+, -, *, /) liefert. Die Werte x, p, alpha, beta, gamma, delta aus den obigen Gleichungen gelten für Berechnungen als Elemente des Galois-Körpers.

Somit haben wir ein Gleichungssystem, mit dem wir Blöcke von Redundanzcodes erstellen können, indem wir ein entsprechendes Computerprogramm schreiben. Mit demselben Gleichungssystem können Daten wiederhergestellt werden.

* Dies ist keine strikte Definition, eher eine Beschreibung.

Wie Daten wiederhergestellt werden

Die 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 in den obigen Gleichungen die entsprechenden Variablen x und/oder p unbekannt sind.

Die Gleichungen für Reed-Solomon-Codes können als ein Gleichungssystem betrachtet werden, in dem alle Werte alpha, beta, gamma, delta Konstanten sind, alle x und p, die den verfügbaren Blöcken entsprechen, - bekannte Variablen sind, während die übrigen x und p - unbekannt sind.

Zum Beispiel, lassen Sie uns annehmen, dass die Datenblöcke 1, 2, 3 und der Redundanzcodeblock 2 nicht verfügbar sind, dann wird für die i-te Gruppe von Wörtern das folgende Gleichungssystem (Unbekannte sind rot markiert) bestehen:

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 einige Schlussfolgerungen zur Datenwiederherstellung für Reed-Solomon-Codes (n Datenblöcke, m Redundanzblöcke):

Daten können bei Verlust beliebiger m Blöcke oder weniger wiederhergestellt werden. Bei Verlust von m+1 oder mehr Blöcken können die Daten nicht wiederhergestellt werden: man kann ein System aus m Gleichungen mit m + 1 Unbekannten nicht lösen.
Um sogar einen einzigen Datenblock wiederherzustellen, müssen beliebige n der verbleibenden Blöcke verwendet werden; dabei kann jeder der Redundanzcodes verwendet werden.

Was noch wichtig ist zu wissen

In der obigen Beschreibung überspringe ich mehrere wichtige Fragen, deren Betrachtung ein tieferes Eintauchen in die Mathematik erfordert. 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 Unbekannten) haben. Aus dieser Anforderung ergeben sich die Werte für Alpha, Beta, Gamma und Delta.
Das Gleichungssystem muss automatisch erstellt werden können (je nachdem, welche Blöcke nicht verfügbar sind) und gelöst werden können.
Es muss ein Galois-Feld konstruiert werden: für eine gegebene Wortgröße muss das Ergebnis jeder Operation (+, -, *, /) für beliebige zwei Elemente gefunden werden können.

Am Ende des Artikels gibt es Verweise auf Literatur zu diesen wichtigen Fragen.

Wahl von n und m

Wie wählt man n und m in der Praxis? In der Praxis verwenden Datenspeichersysteme Redundanzcodes zur Platzersparnis, deshalb wird m immer kleiner als n gewählt. Ihre konkreten Werte hängen von mehreren Faktoren ab, einschließlich:

Zuverlässigkeit der Datenspeicherung. Je höher m ist, desto mehr Festplattenausfälle können überstanden werden, d.h. die Zuverlässigkeit ist höher.
Redundanz der Speicherung. Je höher das Verhältnis m / n ist, desto höher ist die Redundanz der Speicherung, und desto teurer wird das System.
Verarbeitungszeit für Anfragen. Je höher die Summe n + m ist, desto länger wird die Antwortzeit auf die Anfragen sein. Da zur Datenlesung (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.

Darüber hinaus bringt die Speicherung von Daten in mehreren Rechenzentren zusätzliche Einschränkungen bei der Auswahl von n und m mit sich: Bei der Deaktivierung eines Rechenzentrums müssen die Daten weiterhin lesbar bleiben. Beispielsweise muss bei der Speicherung von Daten in 3 Rechenzentren die Bedingung m >= n/2 erfüllt sein, andernfalls kann es zu Situationen kommen, in denen die Daten bei der Deaktivierung eines Rechenzentrums nicht mehr lesbar sind.

3. LRC — Lokale Rekonstruktionscodes

Um Daten mit Reed-Solomon-Codes wiederherzustellen, müssen n beliebige Datenblöcke verwendet werden. Dies ist ein sehr wesentlicher Nachteil für verteilte Datenspeichersysteme, da für die Wiederherstellung der Daten auf einer defekten Festplatte Daten von den meisten anderen gelesen werden müssen, was eine hohe zusätzliche Belastung für die Festplatten und das Netzwerk verursacht.

Die häufigsten Fehler sind die Nichterreichbarkeit eines Datenblocks aufgrund eines Ausfalls oder einer Überlastung einer Festplatte. Kann man die übermäßige Belastung bei der Wiederherstellung von Daten in einem solchen (am häufigsten auftretenden) Fall irgendwie reduzieren? Es stellt sich heraus, dass es möglich ist: dafür gibt es spezielle LRC-Redundanzcodes.

LRC (Lokale Rekonstruktionscodes) sind Redundanzcodes, die von Microsoft für die Verwendung in Windows Azure Storage entwickelt wurden. Die Idee der LRC ist denkbar einfach: Alle Datenblöcke werden in zwei (oder mehr) Gruppen unterteilt und ein Teil der Redundanzcodes wird für jede Gruppe separat berechnet. Ein Teil der Redundanzcodes wird also anhand aller Datenblöcke (in LRC als globale Redundanzcodes bezeichnet) und ein anderer Teil mit Hilfe einer der beiden Gruppen von Datenblöcken (diese werden lokale Redundanzcodes genannt) berechnet.

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 bei der Nichterreichbarkeit eines Datenblocks zu lesen, müssen nur n/l Blöcke gelesen werden – das ist l-mal weniger als bei Reed-Solomon-Codes.

Zum Beispiel betrachten wir 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 Redundanzblöcke P1, P2 werden anhand aller Datenblöcke berechnet. Der Redundanzblock P3 wird mithilfe der Datenblöcke X1–X3 berechnet, der Redundanzblock P4 mithilfe der Datenblöcke X4–X6.

Der Rest wird im LRC nach dem Vorbild der Reed-Solomon-Codes durchgeführt. Die Gleichungen zur Berechnung der Wortanzahl der Blockcodes für Redundanz sind wie folgt:

Um die Werte alpha, beta, gamma, delta zu bestimmen, müssen eine Reihe von Bedingungen erfüllt werden, die die Möglichkeit der Datenwiederherstellung garantieren (d.h. die Lösung des Gleichungssystems). Nähere Informationen dazu finden Sie in Artikel.
Auch in der Praxis werden für die Berechnung der lokalen Redundanzcodes P3, P4 die XOR-Operation verwendet.

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

Um einen beliebigen 1-Datenblock wiederherzustellen, ist es ausreichend, 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. Das lässt sich leicht anhand eines Beispiels 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, in unserem Fall 4. Dann haben wir ein System aus 3 Gleichungen mit 4 Unbekannten, das nicht gelöst werden kann.
In allen anderen Fällen der Nichtverfügbarkeit von r + l Blöcken (wenn aus jeder Gruppe mindestens ein Block verfügbar ist) können die Daten im LRC wiederhergestellt werden.

Damit übertrifft LRC die Reed-Solomon-Codes bei der Datenwiederherstellung nach Einzel-Fehlern. Bei Reed-Solomon-Codes müssen zur Wiederherstellung selbst eines Datenblocks n Blöcke verwendet werden, während im LRC zur Wiederherstellung eines Datenblocks nur n/l Blöcke erforderlich sind (n/2 in unserem Beispiel). Andererseits hat LRC im Vergleich zu Reed-Solomon-Codes eine geringere maximale Anzahl zulässiger Fehler. In den obigen Beispielen können die Reed-Solomon-Codes Daten bei beliebigen 4 Fehlern wiederherstellen, wohingegen es für LRC 2 Kombinationen aus 4 Fehlern gibt, bei denen die Daten nicht wiederhergestellt werden können.

Was wichtiger ist, hängt von der konkreten Situation ab, aber oft überwiegt die Reduktion der Redundanzlast, die LRC bietet, die geringfügig geringere Zuverlässigkeit der Speicherung.

4. Andere Redundanzcodes

Neben den Reed-Solomon-Codes und LRC gibt es viele andere Redundanzcodes. Unterschiedliche Redundanzcodes verwenden unterschiedliche Mathematik. Hier sind einige andere Redundanzcodes:

Redundanzcode mit Hilfe des XOR-Operators. Die XOR-Operation wird auf n Datenblöcken durchgeführt, und es entsteht 1 Block von Redundanzcodes, das heißt, das Schema ist n+1 (n Datenblöcke, 1 Redundanzcode). Verwendet in RAID 5, wo Datenblöcke und Redundanzcodes zyklisch auf alle Festplatten des Arrays geschrieben werden.
Der Even-Odd-Algorithmus, der auf der XOR-Operation basiert. Er ermöglicht den Aufbau von 2 Redundanzcodeblöcken, also Schema n+2.
Der STAR-Algorithmus, der auf der XOR-Operation basiert. Er ermöglicht den Aufbau von 3 Redundanzcodeblöcken, also Schema n+3.
Pyramide-Codes – weitere Redundanzcodes von Microsoft.

5. Verwendung bei Yandex

Eine Reihe von Infrastrukturprojekten von Yandex verwenden Redundanzcodes für die zuverlässige Speicherung von Daten. Hier sind einige Beispiele:

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

In MDS werden LRC-Redundanzcodes verwendet, Schema 8-2-2. Daten mit Redundanzcodes werden auf 12 verschiedenen 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 Reed-Solomon-Codes (Schema 6-3), die zuerst implementiert wurden, als auch LRC-Redundanzcodes (Schema 12-2-2) verwendet, wobei LRC die bevorzugte Methode zur Speicherung ist.

In YDB werden auf Even-Odd basierende Redundanzcodes verwendet (Schema 4-2). Über die Redundanzcodes in YDB wurde bereits auf Highload berichtet..

Die Verwendung verschiedener Redundanzcodes basiert auf unterschiedlichen Anforderungen, die an die Systeme gestellt werden. Zum Beispiel werden in MDS die mit LRC gespeicherten Daten sofort in 3 Rechenzentren platziert. Es ist wichtig, dass die Daten beim Ausfall eines beliebigen Rechenzentrums lesbar bleiben, deshalb müssen die Blöcke so über die Rechenzentren verteilt werden, dass bei der Nichterreichbarkeit eines Rechenzentrums die Anzahl der nicht erreichbaren Blöcke nicht höher ist als zulässig. Im Schema 8-2-2 können jeweils 4 Blöcke in jedem Rechenzentrum platziert werden, wodurch beim Ausfall eines Rechenzentrums 4 Blöcke nicht erreichbar wären, die Daten aber weiterhin gelesen werden können. Egal welches Schema wir bei der Platzierung in 3 Rechenzentren wählen, es muss in jedem Fall (r + l) / n >= 0,5 sein, das heißt, die Redundanz der Speicherung muss mindestens 50% betragen.

In YT ist die Situation anders: Jeder YT-Cluster befindet sich vollständig in einem Rechenzentrum (verschiedene Cluster in verschiedenen Rechenzentren), wodurch es keine solche Einschränkung gibt. Das Schema 12-2-2 bietet eine Redundanz von 33%, was bedeutet, dass die Speicherung der Daten kostengünstiger ist, während sie auch bis zu 4 gleichzeitige Festplattenausfälle überstehen können, genau wie im MDS-Schema.

Es gibt noch viele Besonderheiten bei der Anwendung von Redundanzcodes in Speichersystemen und Datenverarbeitung: Nuancen der Datenwiederherstellung, Einfluss der Wiederherstellung auf die Ausführungszeit von Abfragen, Besonderheiten beim Schreiben von Daten usw. Ich plane, separat über diese und weitere Aspekte der praktischen Anwendung von Redundanzcodes zu berichten, wenn das Thema interessiert.