{"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 \u00dcberfl\u00fcssigkeit aus<\/em><\/p>\n

<\/p>\n

Fehlerkorrekturcodes* werden in Computersystemen h\u00e4ufig verwendet, um die Zuverl\u00e4ssigkeit der Datenspeicherung zu erh\u00f6hen. Bei Yandex werden sie in vielen Projekten eingesetzt. Zum Beispiel erm\u00f6glicht der Einsatz von Fehlerkorrekturcodes anstelle von Replikation in unserem internen Objektspeicher, Millionen zu sparen, ohne die Zuverl\u00e4ssigkeit zu verringern. Doch trotz ihrer weit verbreiteten Anwendung sind verst\u00e4ndliche Beschreibungen, wie Fehlerkorrekturcodes funktionieren, \u00e4u\u00dferst selten. Diejenigen, die mehr dar\u00fcber erfahren m\u00f6chten, sto\u00dfen oft auf Folgendes (aus Wikis<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

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\u00e4ren. Ich werde erl\u00e4utern, wie sie funktionieren, ganz ohne komplizierte Mathematik und seltene Begriffe. Am Ende werde ich Beispiele f\u00fcr die Verwendung von Fehlerkorrekturcodes bei Yandex anf\u00fchren.<\/p>\n

<\/p>\n

Einige mathematische Details werde ich nicht ausf\u00fchrlich behandeln, aber ich werde Links bereitstellen f\u00fcr diejenigen, die tiefer eintauchen m\u00f6chten. Ich m\u00f6chte auch darauf hinweisen, dass einige mathematische Definitionen nicht strikt sein k\u00f6nnen, da der Artikel nicht f\u00fcr Mathematiker, sondern f\u00fcr Ingenieure gedacht ist, die das Thema verstehen m\u00f6chten.<\/p>\n

<\/p>\n

* In der englischen Literatur werden Fehlerkorrekturcodes h\u00e4ufig als Erasure Codes bezeichnet.<\/p>\n

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

1. Die Grundidee der Fehlerkorrekturcodes<\/h1>\n

<\/p>\n

Die grundlegende Idee aller Fehlerkorrekturcodes ist ganz einfach: Daten so zu speichern (oder zu \u00fcbertragen), dass sie bei Fehlern (Festplattensch\u00e4den, \u00dcbertragungsfehlern usw.) nicht verloren gehen. <\/p>\n

<\/p>\n

In den meisten* Fehlerkorrekturcodes werden Daten in n Datenbl\u00f6cke aufgeteilt, f\u00fcr die m Fehlerkorrekturbl\u00f6cke berechnet werden, sodass insgesamt n + m Bl\u00f6cke entstehen. Die Fehlerkorrekturcodes werden so konstruiert, dass man n Datenbl\u00f6cke wiederherstellen kann, indem man nur einen Teil der n + m Bl\u00f6cke verwendet. Im Folgenden werden wir uns ausschlie\u00dflich mit blockweisen Fehlerkorrekturcodes befassen, das hei\u00dft mit solchen, bei denen die Daten in Bl\u00f6cke unterteilt werden.<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

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

<\/p>\n

Datenspeicherung<\/h3>\n

<\/p>\n

In Datenspeichersystemen wird in der Regel jeder Datenblock und jeder Redundanzcode auf einer separaten Festplatte gespeichert. Somit k\u00f6nnen die urspr\u00fcnglichen Daten auch bei einem Ausfall einer beliebigen Festplatte trotzdem wiederhergestellt und gelesen werden. Die Daten k\u00f6nnen auch dann wiederhergestellt werden, wenn mehrere Festplatten gleichzeitig ausfallen.<\/p>\n

<\/p>\n

Daten\u00fcbertragung<\/h3>\n

<\/p>\n

Redundanzcodes k\u00f6nnen zur zuverl\u00e4ssigen Daten\u00fcbertragung in einem unzuverl\u00e4ssigen Netzwerk verwendet werden. Die zu \u00fcbertragenden Daten werden in Bl\u00f6cke unterteilt, f\u00fcr die Redundanzcodes berechnet werden. Sowohl die Datenbl\u00f6cke als auch die Redundanzcodebl\u00f6cke werden \u00fcber das Netzwerk \u00fcbertragen. Bei Fehlern in beliebigen Bl\u00f6cken (bis zu einer bestimmten Anzahl von Bl\u00f6cken) k\u00f6nnen die Daten trotzdem fehlerfrei \u00fcber das Netzwerk \u00fcbertragen werden. Reed-Solomon-Codes beispielsweise werden f\u00fcr die 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, beispielsweise Hamming-Codes und CRC-Codes, die h\u00e4ufig f\u00fcr die Daten\u00fcbertragung in Ethernet-Netzwerken verwendet werden. Dies sind Codes zur fehlerkorrigierenden Codierung, die f\u00fcr die Fehlererkennung und nicht zur Fehlerkorrektur bestimmt sind (der Hamming-Code erlaubt auch teilweise Fehlerkorrekturen).<\/p>\n

<\/p>\n

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

<\/p>\n

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\u00fcr die Serienproduktion von CDs weithin Anwendung fanden.<\/p>\n

<\/p>\n

Zwei Schl\u00fcsselfragen f\u00fcr das Verst\u00e4ndnis der Reed-Solomon-Codes sind: 1) wie man Redundanzcodebl\u00f6cke erstellt; 2) wie man Daten mit Hilfe von Redundanzcodebl\u00f6cken wiederherstellt. Lassen Sie uns Antworten auf diese Fragen finden.
\nZur Vereinfachung nehmen wir im Folgenden an, dass n=6 und m=4. Andere Konstellationen werden analog betrachtet.<\/p>\n

<\/p>\n

Wie man Redundanzcodebl\u00f6cke erstellt<\/h3>\n

<\/p>\n

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

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Alle Datenbl\u00f6cke m\u00fcssen gleich gro\u00df sein, zur Ausrichtung k\u00f6nnen Null-Bits verwendet werden. Die resultierenden Redundanzcode-Bl\u00f6cke haben die gleiche Gr\u00f6\u00dfe wie die Datenbl\u00f6cke. Alle Datenbl\u00f6cke werden in W\u00f6rter unterteilt (z. B. 16 Bit). Angenommen, wir haben die Datenbl\u00f6cke in k W\u00f6rter unterteilt. Dann werden auch alle Redundanzcode-Bl\u00f6cke in k W\u00f6rter unterteilt.<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

F\u00fcr die Berechnung des i-ten Wortes jedes Redundanzblocks werden die i-ten W\u00f6rter aller Datenbl\u00f6cke verwendet. Sie werden nach der folgenden Formel berechnet:<\/p>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

Hier sind die Werte x die W\u00f6rter der Datenbl\u00f6cke, p die W\u00f6rter der Redundanzcode-Bl\u00f6cke, und alle Alpha, Beta, Gamma und Delta sind speziell ausgew\u00e4hlte Zahlen, die f\u00fcr alle i gleich sind. Es sei gleich gesagt, dass all diese Werte keine gew\u00f6hnlichen Zahlen sind, sondern Elemente des Galois-Feldes. Die Operationen +, -, *, \/ sind keine f\u00fcr uns gewohnten Operationen, sondern spezielle Operationen, die \u00fcber den Elementen des Galois-Felds eingef\u00fchrt wurden.<\/p>\n

<\/p>\n

Warum werden Galois-Felder ben\u00f6tigt<\/h3>\n

<\/p>\n

\"Redundanzcodes:<\/p>\n

<\/p>\n

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

<\/p>\n

    \n
  1. Wie bereits erw\u00e4hnt, ist die Wortgr\u00f6\u00dfe festgelegt, in unserem Beispiel 16 Bit. Die obigen Formeln f\u00fcr die Reed-Solomon-Codes sind so, dass bei Verwendung gew\u00f6hnlicher Ganzzahlen das Ergebnis der Berechnung von p m\u00f6glicherweise nicht durch ein Wort der zul\u00e4ssigen Gr\u00f6\u00dfe dargestellt werden kann.<\/li>\n
  2. Bei der Wiederherstellung von Daten werden die obigen Formeln als Gleichungssystem betrachtet, das gel\u00f6st werden muss, um die Daten wiederherzustellen. W\u00e4hrend des L\u00f6sungsprozesses 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.<\/li>\n<\/ol>\n

    <\/p>\n

    Diese Probleme verhindern die Verwendung ganzer Zahlen f\u00fcr Reed-Solomon-Codes. Die L\u00f6sung des Problems ist originell und l\u00e4sst sich wie folgt beschreiben: Lassen Sie uns spezielle Zahlen erfinden, die man mit W\u00f6rtern der gew\u00fcnschten L\u00e4nge (z. B. 16 Bit) darstellen kann, und das Ergebnis aller Operationen (Addition, Subtraktion, Multiplikation, Division) wird ebenfalls im Speicher des Computers mithilfe von W\u00f6rtern der gew\u00fcnschten L\u00e4nge dargestellt.<\/p>\n

    <\/p>\n

    Solche \"speziellen\" Zahlen werden seit langem von Mathematikern erforscht und hei\u00dfen K\u00f6rper. Ein K\u00f6rper ist eine Menge von Elementen mit definierten Operationen der Addition, Subtraktion, Multiplikation und Division.<\/p>\n

    <\/p>\n

    Galois-K\u00f6rper* sind K\u00f6rper, f\u00fcr die f\u00fcr jede Operation (+, -, *, \/) und f\u00fcr beliebige zwei Elemente des K\u00f6rpers ein eindeutiges Ergebnis existiert. Galois-K\u00f6rper k\u00f6nnen f\u00fcr Zahlen konstruiert werden, die Potenzen von 2 sind: 2, 4, 8, 16 usw. (tats\u00e4chlich Potenzen jeder Primzahl p, aber in der Praxis interessieren wir uns nur f\u00fcr Potenzen von 2). Zum Beispiel ist f\u00fcr W\u00f6rter mit einer Gr\u00f6\u00dfe von 16 Bit dieser K\u00f6rper, der 65.536 Elemente enth\u00e4lt, f\u00fcr die jede Paarung ein Ergebnis jeder Operation (+, -, *, \/) liefert. Die Werte x, p, alpha, beta, gamma, delta aus den obigen Gleichungen gelten f\u00fcr Berechnungen als Elemente des Galois-K\u00f6rpers.<\/p>\n

    <\/p>\n

    Somit haben wir ein Gleichungssystem, mit dem wir Bl\u00f6cke von Redundanzcodes erstellen k\u00f6nnen, indem wir ein entsprechendes Computerprogramm schreiben. Mit demselben Gleichungssystem k\u00f6nnen Daten wiederhergestellt werden.<\/p>\n

    <\/p>\n

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

    <\/p>\n

    Wie Daten wiederhergestellt werden<\/h3>\n

    <\/p>\n

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

    <\/p>\n

    Die Gleichungen f\u00fcr Reed-Solomon-Codes k\u00f6nnen als ein Gleichungssystem betrachtet werden, in dem alle Werte alpha, beta, gamma, delta Konstanten sind, alle x und p, die den verf\u00fcgbaren Bl\u00f6cken entsprechen, - bekannte Variablen sind, w\u00e4hrend die \u00fcbrigen x und p - unbekannt sind.<\/p>\n

    <\/p>\n

    Zum Beispiel, lassen Sie uns annehmen, dass die Datenbl\u00f6cke 1, 2, 3 und der Redundanzcodeblock 2 nicht verf\u00fcgbar sind, dann wird f\u00fcr die i-te Gruppe von W\u00f6rtern das folgende Gleichungssystem (Unbekannte sind rot markiert) bestehen:<\/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 einige Schlussfolgerungen zur Datenwiederherstellung f\u00fcr Reed-Solomon-Codes (n Datenbl\u00f6cke, m Redundanzbl\u00f6cke):<\/p>\n

    <\/p>\n