{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Redundanzcodes: Einfach erkl\u00e4rt, wie man Daten zuverl\u00e4ssig und kosteng\u00fcnstig speichert","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Redundanzcodes:<\/p>\n

<\/p>\n

So sieht Redundanz aus<\/em><\/p>\n

<\/p>\n

Redundanzcodes* werden in Computersystemen h\u00e4ufig eingesetzt, um die Zuverl\u00e4ssigkeit der Datenspeicherung zu erh\u00f6hen. 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\u00e4ssigkeit zu beeintr\u00e4chtigen. Trotz ihrer breiten Anwendung ist eine verst\u00e4ndliche Erkl\u00e4rung, wie Redundanzcodes funktionieren, selten zu finden. Diejenigen, die mehr dar\u00fcber erfahren m\u00f6chten, sto\u00dfen auf folgendes (aus Wikis<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Ich hei\u00dfe 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\u00e4ren. Ich werde erl\u00e4utern, wie es funktioniert, ohne komplizierte Mathematik oder seltene Begriffe. Am Ende werde ich Beispiele f\u00fcr die Verwendung von Redundanzcodes bei Yandex geben.<\/p>\n

<\/p>\n

Einige mathematische Details werde ich nicht n\u00e4her erl\u00e4utern, aber ich werde Links bereitstellen f\u00fcr diejenigen, die tiefer eintauchen m\u00f6chten. Au\u00dferdem m\u00f6chte ich anmerken, dass einige mathematische Definitionen m\u00f6glicherweise nicht strikt sind, da der Artikel nicht f\u00fcr Mathematiker, sondern f\u00fcr Ingenieure gedacht ist, die die Grundlagen verstehen m\u00f6chten.<\/p>\n

<\/p>\n

* In der englischsprachigen Literatur werden Redundanzcodes oft als Erasure Codes bezeichnet.<\/p>\n

<\/a><\/noindex><\/p>\n

1. Die Grundlagen der Redundanzcodes<\/h1>\n

<\/p>\n

Die grundlegende Idee aller Redundanzcodes ist \u00e4u\u00dferst einfach: Daten so zu speichern (oder zu \u00fcbertragen), dass sie bei Fehlern (wie Festplattenausf\u00e4llen, \u00dcbertragungsfehlern usw.) nicht verloren gehen. <\/p>\n

<\/p>\n

In den meisten Redundanzcodes werden die Daten in n Datenbl\u00f6cke aufgeteilt, f\u00fcr die m Redundanzcodebl\u00f6cke berechnet werden. Insgesamt ergibt sich also eine Anzahl von n + m Bl\u00f6cken. Die Redundanzcodes werden so konstruiert, dass n Datenbl\u00f6cke wiederhergestellt werden k\u00f6nnen, indem man nur einen Teil der n + m Bl\u00f6cke verwendet. Im Folgenden betrachten wir nur blockbasierte Redundanzcodes, das hei\u00dft, solche, bei denen die Daten in Bl\u00f6cke unterteilt sind.<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Um alle n Datenbl\u00f6cke wiederherzustellen, ben\u00f6tigt man mindestens n von n + m Bl\u00f6cken, da man n Bl\u00f6cke nicht mit nur n-1 Block erhalten kann (in diesem Fall m\u00fcsste man 1 Block \"aus der Luft\" nehmen). Reichen n beliebige Bl\u00f6cke aus n + m Bl\u00f6cken zur Wiederherstellung aller Daten? Das h\u00e4ngt vom Typ der Redundanzcodes ab; beispielsweise erm\u00f6glichen Reed-Solomon-Codes die Wiederherstellung aller Daten mit beliebigen n Bl\u00f6cken, w\u00e4hrend LRC-Redundanzcodes das nicht immer tun.<\/p>\n

<\/p>\n

Datenspeicherung<\/h3>\n

<\/p>\n

In Datenspeichersystemen wird in der Regel jeder der Datenbl\u00f6cke und Redundanzcode-Bl\u00f6cke auf einer separaten Festplatte gespeichert. Dadurch k\u00f6nnen die urspr\u00fcnglichen Daten auch bei einem Ausfall einer beliebigen Festplatte wiederhergestellt und gelesen werden. Daten k\u00f6nnen sogar bei gleichzeitigen Ausf\u00e4llen mehrerer Festplatten wiederhergestellt werden.<\/p>\n

<\/p>\n

Daten\u00fcbergabe<\/h3>\n

<\/p>\n

Redundanzcodes k\u00f6nnen zur zuverl\u00e4ssigen Daten\u00fcbertragung in unzuverl\u00e4ssigen Netzwerken eingesetzt werden. Die \u00fcbertragenen Daten werden in Bl\u00f6cke unterteilt, f\u00fcr die Redundanzcodes berechnet werden. Sowohl die Datenbl\u00f6cke als auch die Redundanzcodes werden \u00fcber das Netzwerk \u00fcbertragen. Bei Fehlern in beliebigen Bl\u00f6cken (bis zu einer bestimmten Anzahl von Bl\u00f6cken) k\u00f6nnen die Daten dennoch ohne Fehler \u00fcber das Netzwerk \u00fcbertragen werden. Reed-Solomon-Codes werden beispielsweise zur Daten\u00fcbertragung \u00fcber optische Kommunikationsleitungen und in der Satellitenkommunikation verwendet.<\/p>\n

<\/p>\n

* Es gibt auch Redundanzcodes, bei denen die Daten nicht in Bl\u00f6cke unterteilt werden, wie zum Beispiel Hamming-Codes und CRC-Codes, die weit verbreitet in Ethernet-Netzen genutzt werden. Diese Codes sind f\u00fcr fehlerresistente Kodierung gedacht; sie dienen der Fehlererkennung, nicht der Fehlerkorrektur (der Hamming-Code erm\u00f6glicht zudem teilweise Fehlerkorrekturen).<\/p>\n

<\/p>\n

2. Reed-Solomon-Codes<\/h1>\n

<\/p>\n

Die Reed-Solomon-Codes geh\u00f6ren zu den am weitesten verbreiteten Redundanzcodes, die bereits in den 1960er Jahren entwickelt wurden und erstmals in den 1980er Jahren f\u00fcr die Serienproduktion von Compact Discs breite Anwendung fanden.<\/p>\n

<\/p>\n

Zwei wesentliche Fragen zum Verst\u00e4ndnis 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.
\nZur Vereinfachung nehmen wir im Folgenden an, dass n=6 und m=4. Andere Schemen werden analog betrachtet.<\/p>\n

<\/p>\n

Wie man Redundanzcodes erstellt<\/h3>\n

<\/p>\n

Jeder Redundanzcodeblock wird unabh\u00e4ngig von den anderen betrachtet. F\u00fcr die Berechnung jedes Blocks werden alle n Datenbl\u00f6cke verwendet. In der folgenden Abbildung stehen X1-X6 f\u00fcr die Datenbl\u00f6cke, P1\u2013P4 f\u00fcr die Redundanzcodebl\u00f6cke.<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Alle Datenbl\u00f6cke m\u00fcssen die gleiche Gr\u00f6\u00dfe haben; zur Ausrichtung k\u00f6nnen Nullbits verwendet werden. Die entstandenen Redundanzcodebl\u00f6cke haben die gleiche Gr\u00f6\u00dfe wie die Datenbl\u00f6cke. Alle Datenbl\u00f6cke werden in W\u00f6rter aufgeteilt (beispielsweise in 16-Bit-W\u00f6rter). Angenommen, wir haben die Datenbl\u00f6cke in k W\u00f6rter unterteilt. Dann werden auch alle Redundanzcodebl\u00f6cke in k W\u00f6rter unterteilt.<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Zur Berechnung des i-ten Wortes jedes Redundanzcodeblocks werden die i-ten W\u00f6rter aller Datenbl\u00f6cke verwendet. Diese werden nach folgender Formel berechnet:<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Hier sind die Werte x \u2013 W\u00f6rter der Datenbl\u00f6cke, p \u2013 W\u00f6rter der Blockcodes zur Redundanz, alle Alpha, Beta, Gamma und Delta \u2013 speziell ausgew\u00e4hlte Zahlen, die f\u00fcr alle i gleich sind. Zun\u00e4chst sei gesagt, dass all diese Werte keine gew\u00f6hnlichen Zahlen sind, sondern Elemente eines Galois-Feldes; die Operationen +, -, *, \/ sind nicht die gewohnten Operationen, sondern spezielle Operationen, die \u00fcber den Elementen des Galois-Feldes definiert wurden.<\/p>\n

<\/p>\n

Wozu dienen Galois-Felder?<\/h3>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Es scheint einfach zu sein: Wir teilen die Daten in Bl\u00f6cke, die Bl\u00f6cke in W\u00f6rter, und unter Verwendung der W\u00f6rter der Datenbl\u00f6cke berechnen wir die W\u00f6rter der Redundanzcodes \u2013 wir erhalten die Redundanzcodes. Im Gro\u00dfen und Ganzen funktioniert das so, aber der Teufel steckt im Detail:<\/p>\n

<\/p>\n

    \n
  1. Wie oben erw\u00e4hnt, ist die Wortgr\u00f6\u00dfe fix, in unserem Beispiel 16 Bit. Die oben angegebenen Formeln f\u00fcr die Reed-Solomon-Codes sind so gestaltet, dass bei der Verwendung gew\u00f6hnlicher Ganzzahlen das Ergebnis der Berechnung p m\u00f6glicherweise nicht mit einem Wort von zul\u00e4ssiger Gr\u00f6\u00dfe darstellbar ist.<\/li>\n
  2. Beim Datenwiederherstellungsverfahren werden die oben genannten Formeln als Gleichungssystem betrachtet, das gel\u00f6st werden muss, um die Daten wiederherzustellen. W\u00e4hrend des L\u00f6sens kann es erforderlich sein, ganze Zahlen zu dividieren, was zu einer reellen Zahl f\u00fchrt, die nicht exakt im Computer gespeichert werden kann.<\/li>\n<\/ol>\n

    <\/p>\n

    Diese Herausforderungen machen es unm\u00f6glich, f\u00fcr die Reed-Solomon-Codes ganze Zahlen zu verwenden. Die L\u00f6sung des Problems ist originell und kann wie folgt beschrieben werden: Lassen Sie uns spezielle Zahlen erfinden, die mit Worten der erforderlichen L\u00e4nge (z. B. 16 Bit) dargestellt werden k\u00f6nnen, wobei das Ergebnis aller darauf durchgef\u00fchrten Operationen (Addition, Subtraktion, Multiplikation, Division) ebenfalls in der Computer-Speicher mit W\u00f6rtern der entsprechenden L\u00e4nge dargestellt wird.<\/p>\n

    <\/p>\n

    Solche \"speziellen\" Zahlen werden seit Langem in der Mathematik untersucht und als Felder bezeichnet. Ein Feld ist eine Menge von Elementen mit bestimmten f\u00fcr sie definierten Operationen wie Addition, Subtraktion, Multiplikation und Division.<\/p>\n

    <\/p>\n

    Galois-Felder* sind Felder, f\u00fcr die f\u00fcr jede Operation (+, -, *, \/) zwischen beliebigen zwei Elementen ein eindeutiges Ergebnis existiert. Galois-Felder k\u00f6nnen f\u00fcr Zahlen konstruiert werden, die eine Potenz von 2 sind: 2, 4, 8, 16 usw. (tats\u00e4chlich auch f\u00fcr jede Potenz einer Primzahl p, aber in der Praxis interessieren wir uns nur f\u00fcr Potenzen von 2). Zum Beispiel ist f\u00fcr Worte mit einer Gr\u00f6\u00dfe von 16 Bit dieses Feld das, das 65.536 Elemente enth\u00e4lt, f\u00fcr 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\u00fcr Berechnungen als Elemente des Galois-Feldes verwendet.<\/p>\n

    <\/p>\n

    Somit haben wir ein Gleichungssystem, mit dem wir redundant Codebl\u00f6cke erstellen k\u00f6nnen, indem wir das entsprechende Computerprogramm schreiben. Mit diesem Gleichungssystem k\u00f6nnen wir auch Daten wiederherstellen.<\/p>\n

    <\/p>\n

    * Dies ist keine strikte Definition, sondern eher eine Beschreibung.<\/p>\n

    <\/p>\n

    Wie man Daten wiederherstellt<\/h3>\n

    <\/p>\n

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

    <\/p>\n

    Die Gleichungen f\u00fcr Reed-Solomon-Codes k\u00f6nnen als Gleichungssystem betrachtet werden, in dem alle Werte Alpha, Beta, Gamma, Delta - Konstanten sind, und alle x und p, die den verf\u00fcgbaren Bl\u00f6cken entsprechen, - bekannte Variablen sind, w\u00e4hrend andere x und p - unbekannt sind.<\/p>\n

    <\/p>\n

    Angenommen, die Datenbl\u00f6cke 1, 2, 3 und der Redundanzcodeblock 2 sind nicht verf\u00fcgbar, dann hat die i-te Blockgruppe folgendes Gleichungssystem (unbekannte sind rot markiert):<\/p>\n

    <\/p>\n

    \"Redundanzcodes:<\/p>\n

    <\/p>\n

    Wir haben ein System aus 4 Gleichungen mit 4 Unbekannten, also k\u00f6nnen wir es l\u00f6sen und die Daten wiederherstellen!<\/p>\n

    <\/p>\n

    Aus diesem Gleichungssystem ergeben sich mehrere Schlussfolgerungen zur Datenwiederherstellung f\u00fcr Reed-Solomon-Codes (n Datenbl\u00f6cke, m Redundanzcodebl\u00f6cke):<\/p>\n

    <\/p>\n