So sieht Redundanz aus
Redundanzcodes* werden in Computersystemen häufig verwendet, um die Zuverlässigkeit der Datenspeicherung zu erhöhen. In Yandex werden sie in vielen Projekten verwendet. Beispielsweise spart die Verwendung von Redundanzcodes anstelle der Replikation in unserem internen Objektspeicher Millionen, ohne dass die Zuverlässigkeit darunter leidet. Doch trotz ihrer weiten Verbreitung sind klare Beschreibungen der Funktionsweise von Redundanzcodes sehr selten. Wer es verstehen will, steht ungefähr vor Folgendem (von ):
Mein Name ist Vadim, bei Yandex entwickle ich interne Objektspeicher-MDS. In diesem Artikel beschreibe ich in einfachen Worten die theoretischen Grundlagen von Redundanzcodes (Reed-Solomon- und LRC-Codes). Ich erkläre Ihnen, wie es funktioniert, ohne komplexe Mathematik und seltene Begriffe. Am Ende werde ich Beispiele für die Verwendung von Redundanzcodes in Yandex geben.
Ich werde einige mathematische Details nicht im Detail betrachten, aber ich werde Links für diejenigen bereitstellen, die tiefer eintauchen möchten. Ich möchte auch darauf hinweisen, dass einige mathematische Definitionen möglicherweise nicht streng sind, da der Artikel nicht für Mathematiker gedacht ist, sondern für Ingenieure, die den Kern des Problems verstehen möchten.
* In der englischsprachigen Literatur werden Redundanzcodes oft auch Erasure Codes genannt.
1. Das Wesen von Redundanzcodes
Das Wesen aller Redundanzcodes ist äußerst einfach: Daten so speichern (oder übertragen), dass sie bei Fehlern (Festplattenausfälle, Datenübertragungsfehler usw.) nicht verloren gehen.
In den meisten* Redundanzcodes werden die Daten in n Datenblöcke unterteilt, für die m Blöcke von Redundanzcodes gezählt werden, was insgesamt n + m Blöcke ergibt. Redundanzcodes sind so aufgebaut, dass n Datenblöcke mit nur einem Teil von n + m Blöcken wiederhergestellt werden können. Als nächstes betrachten wir nur Blockredundanzcodes, also solche, bei denen die Daten in Blöcke unterteilt sind.
Um alle n Datenblöcke wiederherzustellen, müssen Sie mindestens n von n + m Blöcken haben, da Sie nicht n Blöcke erhalten können, indem Sie nur n-1 Blöcke haben (in diesem Fall müssten Sie 1 Block „aus dem Nichts“ nehmen Luft"). Reichen n zufällige Blöcke mit n + m Blöcken aus, um alle Daten wiederherzustellen? Dies hängt von der Art der Redundanzcodes ab. Mit Reed-Solomon-Codes können Sie beispielsweise alle Daten mithilfe beliebiger n Blöcke wiederherstellen, mit LRC-Redundanzcodes jedoch nicht immer.
Datenspeicherung
In Datenspeichersystemen wird in der Regel jeder der Datenblöcke und Redundanzcodeblöcke auf eine separate Festplatte geschrieben. Wenn dann eine beliebige Festplatte ausfällt, können die Originaldaten immer noch wiederhergestellt und gelesen werden. Selbst wenn mehrere Festplatten gleichzeitig ausfallen, können Daten wiederhergestellt werden.
Datenübertragung
Redundanzcodes können verwendet werden, um Daten zuverlässig über ein unzuverlässiges Netzwerk zu übertragen. Die übertragenen Daten werden in Blöcke unterteilt und für sie werden Redundanzcodes berechnet. Sowohl Datenblöcke als auch Redundanzcodeblöcke werden über das Netzwerk übertragen. Treten Fehler in beliebigen Blöcken (bis zu einer bestimmten Anzahl von Blöcken) auf, können die Daten dennoch fehlerfrei ü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 sind, wie zum Beispiel Hamming-Codes und CRC-Codes, die häufig zur Datenübertragung in Ethernet-Netzwerken verwendet werden. Hierbei handelt es sich um Codes zur fehlerkorrigierenden Codierung. Sie sollen Fehler erkennen und nicht korrigieren (der Hamming-Code ermöglicht auch eine teilweise Korrektur von Fehlern).
2. Reed-Solomon-Codes
Reed-Solomon-Codes gehören zu den am weitesten verbreiteten Redundanzcodes, wurden bereits in den 1960er Jahren erfunden und erstmals in den 1980er Jahren in großem Umfang für die Massenproduktion von CDs verwendet.
Für das Verständnis von Reed-Solomon-Codes gibt es zwei Schlüsselfragen: 1) Wie erstellt man Blöcke mit Redundanzcodes? 2) Wie man Daten mithilfe von Redundanzcodeblöcken wiederherstellt. Lassen Sie uns Antworten darauf finden.
Der Einfachheit halber gehen wir weiterhin davon aus, dass n=6 und m=4. Andere Schemata werden analog betrachtet.
So erstellen Sie Redundanzcodeblöcke
Jeder Block von Redundanzcodes wird unabhängig von den anderen gezählt. Alle n Datenblöcke werden zum Zählen jedes Blocks verwendet. Im Diagramm unten sind X1–X6 Datenblöcke und P1–P4 Redundanzcodeblöcke.
Alle Datenblöcke müssen die gleiche Größe haben und zur Ausrichtung können Nullbits verwendet werden. Die resultierenden Redundanzcodeblöcke haben die gleiche Größe wie die Datenblöcke. Alle Datenblöcke sind in Wörter unterteilt (z. B. 16 Bit). Nehmen wir an, wir teilen die Datenblöcke in k Wörter auf. Dann werden auch alle Blöcke von Redundanzcodes in k Wörter unterteilt.
Um das i-te Wort jedes Redundanzblocks zu zählen, werden die i-ten Wörter aller Datenblöcke verwendet. Sie werden nach folgender Formel berechnet:
Hier sind die Werte x die Wörter von Datenblöcken, p sind die Wörter von Redundanzcodeblöcken, alle Alpha, Beta, Gamma und Delta sind speziell ausgewählte Zahlen, die für alle i gleich sind. Es muss gleich gesagt werden, dass alle diese Werte keine gewöhnlichen Zahlen sind, sondern Elemente des Galois-Feldes; die Operationen +, -, *, / sind keine uns allen bekannten Operationen, sondern spezielle Operationen, die an Elementen des Galois-Feldes eingeführt wurden Feld.
Warum werden Galoisfelder benötigt?
Es scheint, dass alles einfach ist: Wir unterteilen die Daten in Blöcke, die Blöcke in Wörter, anhand der Wörter der Datenblöcke zählen wir die Wörter der Redundanzcodeblöcke – wir erhalten Redundanzcodeblöcke. Im Allgemeinen funktioniert es so, aber der Teufel steckt im Detail:
- Wie oben erwähnt, ist die Wortgröße fest, in unserem Beispiel 16 Bit. Die obigen Formeln für Reed-Solomon-Codes sind so, dass bei Verwendung gewöhnlicher Ganzzahlen das Ergebnis der Berechnung von p möglicherweise nicht mit einem Wort gültiger Größe darstellbar ist.
- Bei der Datenwiederherstellung werden die oben genannten Formeln als Gleichungssystem betrachtet, das gelöst werden muss, um die Daten wiederherzustellen. Während des Lösungsprozesses kann es erforderlich sein, ganze Zahlen durcheinander zu dividieren, was zu einer reellen Zahl führt, die im Computerspeicher nicht genau dargestellt werden kann.
Diese Probleme verhindern die Verwendung von Ganzzahlen 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 durch Wörter der erforderlichen Länge (z. B. 16 Bit) dargestellt werden können, und das Ergebnis aller Operationen, an denen (Addition) beteiligt ist , Subtraktion, Multiplikation, Division) werden ebenfalls im Computerspeicher mit Wörtern der erforderlichen Länge dargestellt.
Solche „besonderen“ Zahlen werden von der Mathematik seit langem untersucht; sie werden Körper genannt. Ein Feld ist eine Menge von Elementen, für die Additions-, Subtraktions-, Multiplikations- und Divisionsoperationen definiert sind.
Galois*-Felder sind Felder, für die es ein eindeutiges Ergebnis jeder Operation (+, -, *, /) für zwei beliebige Elemente des Feldes gibt. Galoisfelder können für Zahlen konstruiert werden, die Potenzen von 2 sind: 2, 4, 8, 16 usw. (eigentlich Potenzen jeder Primzahl p, aber in der Praxis interessieren uns nur Potenzen von 2). Bei 16-Bit-Wörtern ist dies beispielsweise ein Feld mit 65 Elementen, für jedes Paar können Sie das Ergebnis einer beliebigen Operation (+, -, *, /) finden. Die Werte von x, p, Alpha, Beta, Gamma, Delta aus den obigen Gleichungen werden für Berechnungen als Elemente des Galois-Feldes betrachtet.
Somit verfügen wir über ein Gleichungssystem, mit dem wir Blöcke von Redundanzcodes konstruieren können, indem wir das entsprechende Computerprogramm schreiben. Mit demselben Gleichungssystem können Sie eine Datenwiederherstellung durchführen.
* Dies ist keine strenge Definition, sondern eher eine Beschreibung.
So stellen Sie Daten wieder her
Eine Wiederherstellung ist erforderlich, wenn einige der n + m Blöcke fehlen. Dabei kann es sich sowohl um Datenblöcke als auch um Redundanzcodeblöcke handeln. Das Fehlen von Datenblöcken und/oder Redundanzcodeblöcken bedeutet, dass die entsprechenden x- und/oder p-Variablen in den obigen Gleichungen unbekannt sind.
Die Gleichungen für Reed-Solomon-Codes können als Gleichungssystem betrachtet werden, in dem alle Alpha-, Beta-, Gamma- und Delta-Werte Konstanten sind, alle x und p, die den verfügbaren Blöcken entsprechen, bekannte Variablen sind und die übrigen x und p sind unbekannt.
Angenommen, die Datenblöcke 1, 2, 3 und der Redundanzcodeblock 2 sind nicht verfügbar, dann ergibt sich für die i-te Wortgruppe das folgende Gleichungssystem (Unbekannte sind rot markiert):
Wir haben ein System aus 4 Gleichungen mit 4 Unbekannten, was bedeutet, dass wir es lösen und die Daten wiederherstellen können!
Aus diesem Gleichungssystem ergeben sich eine Reihe von Schlussfolgerungen zur Datenwiederherstellung für Reed-Solomon-Codes (n Datenblöcke, m Redundanzcodeblöcke):
- Daten können wiederhergestellt werden, wenn m Blöcke oder weniger verloren gehen. Wenn m+1 oder mehr Blöcke verloren gehen, können die Daten nicht wiederhergestellt werden: Es ist unmöglich, ein System aus m Gleichungen mit m + 1 Unbekannten zu lösen.
- Um auch nur einen Datenblock wiederherzustellen, müssen Sie beliebige n der verbleibenden Blöcke verwenden, und Sie können jeden der Redundanzcodes verwenden.
Was muss ich sonst noch wissen?
In der obigen Beschreibung vermeide ich eine Reihe wichtiger Themen, deren Betrachtung einen tieferen Einblick in die Mathematik erfordert. Insbesondere sage ich nichts zu Folgendem:
- Das Gleichungssystem für Reed-Solomon-Codes muss eine (eindeutige) Lösung für jede Kombination von Unbekannten haben (nicht mehr als m Unbekannte). Basierend auf dieser Anforderung werden die Werte Alpha, Beta, Gamma und Delta ausgewählt.
- Ein Gleichungssystem muss automatisch konstruiert (je nachdem, welche Blöcke nicht verfügbar sind) und gelöst werden können.
- Wir müssen ein Galois-Feld erstellen: Für eine gegebene Wortgröße müssen wir in der Lage sein, das Ergebnis einer beliebigen Operation (+, -, *, /) für zwei beliebige Elemente zu finden.
Am Ende des Artikels finden Sie Literaturhinweise zu diesen wichtigen Themen.
Wahl zwischen n und m
Wie wählt man n und m in der Praxis aus? In der Praxis werden in Datenspeichersystemen Redundanzcodes verwendet, um Platz zu sparen, sodass m immer kleiner als n gewählt wird. Ihre spezifischen Werte hängen von einer Reihe von Faktoren ab, darunter:
- Zuverlässigkeit der Datenspeicherung. Je größer m, desto mehr Festplattenausfälle können überstanden werden, d. h. desto höher ist die Zuverlässigkeit.
- Redundanter Speicher. Je höher das m/n-Verhältnis ist, desto höher ist die Speicherredundanz und desto teurer wird das System.
- Bearbeitungszeit anfordern. Je größer die Summe n + m ist, desto länger ist die Antwortzeit auf Anfragen. Da das Lesen von Daten (während der Wiederherstellung) das Lesen von n Blöcken erfordert, die auf n verschiedenen Festplatten gespeichert sind, wird die Lesezeit von der langsamsten Festplatte bestimmt.
Darüber hinaus führt die Speicherung von Daten in mehreren DCs zu zusätzlichen Einschränkungen bei der Auswahl von n und m: Wenn 1 DC ausgeschaltet ist, müssen die Daten weiterhin zum Lesen verfügbar sein. Wenn beispielsweise Daten in 3 DCs gespeichert werden, muss die folgende Bedingung erfüllt sein: m >= n/2, andernfalls kann es vorkommen, dass die Daten nicht zum Lesen verfügbar sind, wenn 1 DC ausgeschaltet ist.
3. LRC – Lokale Wiederaufbauvorschriften
Um Daten mithilfe von Reed-Solomon-Codes wiederherzustellen, müssen Sie n beliebige Datenblöcke verwenden. Dies ist ein ganz wesentlicher Nachteil für verteilte Datenspeichersysteme, denn um Daten auf einer defekten Festplatte wiederherzustellen, müssen Sie die Daten von den meisten anderen Festplatten lesen, was zu einer großen zusätzlichen Belastung der Festplatten und des Netzwerks führt.
Die häufigsten Fehler sind die Unzugänglichkeit eines Datenblocks aufgrund eines Ausfalls oder einer Überlastung einer Festplatte. Ist es in diesem (häufigsten) Fall möglich, die übermäßige Belastung für die Datenwiederherstellung irgendwie zu reduzieren? Es stellt sich heraus, dass dies möglich ist: Es gibt speziell für diesen Zweck LRC-Redundanzcodes.
LRC (Local Reconstruction Codes) sind Redundanzcodes, die von Microsoft zur Verwendung in Windows Azure Storage erfunden wurden. Die Idee von LRC ist so einfach wie möglich: Teilen Sie alle Datenblöcke in zwei (oder mehr) Gruppen auf und lesen Sie einen Teil der Redundanzcodeblöcke für jede Gruppe separat aus. Dann werden einige Redundanzcodeblöcke unter Verwendung aller Datenblöcke gezählt (in LRC werden sie globale Redundanzcodes genannt) und einige - unter Verwendung einer von zwei Gruppen von Datenblöcken (sie werden lokale Redundanzcodes genannt).
LRC wird durch drei Zahlen bezeichnet: nrl, wobei n die Anzahl der Datenblöcke, r die Anzahl der globalen Redundanzcodeblöcke und l die Anzahl der lokalen Redundanzcodeblöcke 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 in Reed-Solomon-Codes.
Betrachten Sie beispielsweise das LRC 6-2-2-Schema. X1–X6 – 6 Datenblöcke, P1, P2 – 2 globale Redundanzblöcke, P3, P4 – 2 lokale Redundanzblöcke.
Die Redundanzcodeblöcke P1, P2 werden unter Verwendung aller Datenblöcke gezählt. Redundanzcodeblock P3 – unter Verwendung der Datenblöcke X1–X3, Redundanzcodeblock P4 – unter Verwendung der Datenblöcke X4–X6.
Der Rest erfolgt in LRC analog zu Reed-Solomon-Codes. Die Gleichungen zum Zählen der Wörter von Redundanzcodeblöcken lauten:
Um die Zahlen Alpha, Beta, Gamma, Delta auszuwählen, müssen eine Reihe von Bedingungen erfüllt sein, um die Möglichkeit der Datenwiederherstellung (also der Lösung des Gleichungssystems) zu gewährleisten. Mehr darüber können Sie unter lesen .
Auch in der Praxis wird die XOR-Operation zur Berechnung lokaler Redundanzcodes P3, P4 verwendet.
Aus dem Gleichungssystem für LRC ergeben sich eine Reihe von Schlussfolgerungen:
- Um einen beliebigen Datenblock wiederherzustellen, reicht es aus, n/l Blöcke zu lesen (in unserem Beispiel n/1).
- Wenn die Blöcke r + l nicht verfügbar sind und alle Blöcke in einer Gruppe enthalten sind, können die Daten nicht wiederhergestellt werden. Dies lässt sich leicht anhand eines Beispiels erklären. Lassen Sie die Blöcke X1–X3 und P3 nicht verfügbar sein: Dies sind r + l Blöcke aus derselben Gruppe, in unserem Fall 4. Dann haben wir ein System aus 3 Gleichungen mit 4 Unbekannten, die nicht gelöst werden können.
- In allen anderen Fällen der Nichtverfügbarkeit von r + l-Blöcken (wenn mindestens ein Block aus jeder Gruppe verfügbar ist) können die Daten im LRC wiederhergestellt werden.
Somit übertrifft LRC Reed-Solomon-Codes bei der Wiederherstellung von Daten nach einzelnen Fehlern. In Reed-Solomon-Codes müssen Sie zur Wiederherstellung auch nur eines Datenblocks n Blöcke verwenden, und in LRC reicht es zur Wiederherstellung eines Datenblocks aus, n/l Blöcke zu verwenden (in unserem Beispiel n/2). Andererseits ist LRC den Reed-Solomon-Codes hinsichtlich der maximal zulässigen Fehleranzahl unterlegen. In den obigen Beispielen können Reed-Solomon-Codes Daten für vier beliebige Fehler wiederherstellen, und für LRC gibt es zwei Kombinationen von vier Fehlern, bei denen die Daten nicht wiederhergestellt werden können.
Was wichtiger ist, hängt von der jeweiligen Situation ab, aber oft überwiegen die Einsparungen bei der Überlast, die LRC bietet, die etwas weniger zuverlässige Speicherung.
4. Andere Redundanzcodes
Neben Reed-Solomon- und LRC-Codes gibt es viele weitere Redundanzcodes. Unterschiedliche Redundanzcodes verwenden unterschiedliche Mathematik. Hier sind einige andere Redundanzcodes:
- Redundanzcode mit dem XOR-Operator. Die XOR-Operation wird an n Datenblöcken durchgeführt und 1 Block Redundanzcodes wird erhalten, d. h. ein n+1-Schema (n Datenblöcke, 1 Redundanzcode). Benutzt in , wobei Datenblöcke und Redundanzcodes zyklisch auf alle Festplatten des Arrays geschrieben werden.
- Gerade-ungerade-Algorithmus basierend auf der XOR-Operation. Ermöglicht den Aufbau von 2 Blöcken mit Redundanzcodes, also dem n+2-Schema.
- STAR-Algorithmus basierend auf der XOR-Operation. Ermöglicht den Aufbau von 3 Blöcken mit Redundanzcodes, also dem n+3-Schema.
- Pyramide-Codes sind weitere Redundanzcodes von Microsoft.
5. Verwendung in Yandex
Eine Reihe von Yandex-Infrastrukturprojekten verwenden Redundanzcodes für eine zuverlässige Datenspeicherung. Hier sind einige Beispiele:
- Interner MDS-Objektspeicher, über den ich am Anfang des Artikels geschrieben habe.
- — MapReduce-System von Yandex.
- (Yandex DataBase) – verteilte NewSQL-Datenbank.
MDS verwendet LRC-Redundanzcodes, 8-2-2-Schema. Daten mit Redundanzcodes werden auf 12 verschiedene Festplatten in verschiedenen Servern in 3 verschiedenen Domänencontrollern geschrieben: 4 Server in jedem Domänencontroller. Lesen Sie mehr dazu in .
YT verwendet sowohl Reed-Solomon-Codes (Schema 6-3), die als erste implementiert wurden, als auch LRC-Redundanzcodes (Schema 12-2-2), wobei LRC die bevorzugte Speichermethode ist.
YDB verwendet gerade-ungerade-basierte Redundanzcodes (Abbildung 4-2). Über Redundanzcodes in YDB bereits .
Die Verwendung unterschiedlicher Redundanzcodeschemata ist auf unterschiedliche Anforderungen an Systeme zurückzuführen. Beispielsweise werden in MDS mit LRC gespeicherte Daten gleichzeitig in drei DCs abgelegt. Für uns ist es wichtig, dass die Daten zum Lesen verfügbar bleiben, wenn einer der DCs ausfällt. Daher müssen die Blöcke auf die DCs verteilt werden, sodass bei Ausfall eines DCs die Anzahl der nicht zugänglichen Blöcke nicht mehr als zulässig ist. Im 3-1-8-Schema können Sie 2 Blöcke in jedem DC platzieren. Wenn dann ein DC ausgeschaltet wird, sind 2 Blöcke nicht verfügbar und die Daten können gelesen werden. Welches Schema wir auch wählen, wenn wir es in 4 DCs platzieren, in jedem Fall sollte (r + l) / n >= 4 sein, d. h. die Speicherredundanz beträgt mindestens 3 %.
In YT ist die Situation anders: Jeder YT-Cluster befindet sich vollständig in einem DC (verschiedene Cluster in verschiedenen DCs), daher gibt es keine solche Einschränkung. Das 1-12-2-Schema bietet 2 % Redundanz, d. h. die Datenspeicherung ist günstiger, und es übersteht ebenso wie das MDS-Schema bis zu vier gleichzeitige Festplattenausfälle.
Es gibt viele weitere Merkmale der Verwendung von Redundanzcodes in Datenspeicher- und -verarbeitungssystemen: Nuancen der Datenwiederherstellung, die Auswirkung der Wiederherstellung auf die Ausführungszeit von Abfragen, Merkmale der Datenaufzeichnung usw. Ich werde auf diese und andere Merkmale gesondert eingehen der Verwendung von Redundanzcodes in der Praxis, wenn das Thema interessant ist.
6. Verknüpfungen
- Eine Artikelserie über Reed-Solomon-Codes und Galois-Felder:
Sie werfen einen tieferen Blick auf die Mathematik in verständlicher Sprache. - Artikel von Microsoft über LRC:
In Abschnitt 2 wird kurz die Theorie erläutert und anschließend Erfahrungen mit LRC in der Praxis besprochen. - Gerade-ungerade-Schema:
- STAR-Schema:
- Pyramidencodes:
- Redundanzcodes im MDS:
- Redundanzcodes in YT:
- Redundanzcodes in YDB:
Source: habr.com