Garten Eden

#linux #programming #android #online #stuff

RAID-Fehlerkorrektur (Parität) erklärt

Ich muss zugeben, obwohl ich dachte, mit dem Thema RAID vertraut zu sein, brachte mich ein Artikel über das Erstellen eines Software-RAIDs unter Linux ins Grübeln. Dort wurde am Beispiel von RAID 5 erklärt, dass ein Ausfall einer Festplatte im Verbund nicht zum Datenverlust führt. Das ist richtig, aber trotzdem musste ich nachschlagen, wie das Ganze erreicht wird. Prompt folgte ein Erfolgserlebnis, weil ich durch einfache Simulationen auf dem Papier das System nachvollziehen konnte. Es folgt das Ergebnis meiner Recherche.

Versuchsanordnung

Nehmen wir an, es existieren n=3 Festplatten h0, h1 und h2 im RAID-5-Verbund. Und es sollen folgende Daten auf die Festplatten geschrieben werden:

10 10 11 01 10 11 01 00 00 11 …

Magie, erster Teil

Der erste Teil der Magie der Ausfallsicherheit offenbart sich in der Verteilung der Daten auf die Platten. Angenommen, es wird immer ein Bit pro Festplatte geschrieben. Immer um eine Stelle verschoben schreiben wir aber keine Nutzdaten, sondern die sogenannte Parität (dazu gleich mehr). Unsere Platten enthalten nun also folgenden Inhalt, wobei wir die Parität erst einmal mit einem x kennzeichnen.

h0  1  1  x  0  1  x  0  0  x  1  …
h1  0  x  1  1  x  1  1  x  0  1  …
h2  x  0  1  x  0  1  x  0  0  x

Magie, zweiter Teil

Berechnen wir nun die erwähnte Parität. Sie ist eine einfache XOR-Verknüpfung der übertragenen Daten in diesem Zyklus, in unserer Anordnung also der aktuellen Spalte. Zum einfachen Verständnis: Das Ergebnis der XOR-Operation ist 1, wenn die Bits verschieden sind (also bei 1 XOR 0 und 0 XOR 1), bei Gleichheit ist es 0. Für unseren Fall bedeutet dies, dass die ersten beiden Spalten das Paritätsbit 1 enthalten, die dritte 0. Die Anordnung sieht also so aus:

h0  1  1  0  0  1  0  0  0  0  1  …
h1  0  1  1  1  1  1  1  0  0  1  …
h2  1  0  1  1  0  1  1  0  0  0

Oh oh: Buffer I/O Error

Simulieren wir jetzt einen Ausfall der dritten Platte h2.

h0  1  1  0  0  1  0  0  0  0  1  …
h1  0  1  1  1  1  1  1  0  0  1  …
h2  1  0  1  1  0  1  1  0  0  0

Was geschieht?
Nun, in jeder n-ten (bei uns also dritten) Spalte fehlen die Paritätsbits, in den anderen Teile der Nutzdaten. Die Einzigartigkeit der XOR-Verknüpfung erlaubt uns jetzt aber die vollständige Rekonstruktion durch Rückwärtsrechnen. Das Paritätsbit wird zur Wiederherstellungsinformation.

„ROX“

Beginnen wir mit der zweiten Spalte, denn hier trat der erste Nutzdatenverlust auf. Das Paritätsbit ist hier 1, die Festplatte h0 enthält die Information 1. Die Frage ist nun: Welchen Wert hatte h2, damit 1 XOR ? = 1 ergibt? Schnell erschließt sich: Es musste eine 0 sein, damit das Ergebnis stimmt. Siehe da: richtig.
Genauso geht es mit der nächsten Spalte: Die Parität ist 0, also mussten die anderen Bits laut XOR-Definition identisch sein. Da h1 gleich 1 ist, musste auch h2 eine 1 gespeichert haben. Und so weiter.

Und so fort

Auf diese Weise können die Daten wiederhergestellt werden. Übrigens nicht nur bei n=3, sondern auch für mehr Festplatten. Wer Spaß daran hat, kann das ja mal simulieren. ;-)

flattr

Kommentare

Dein Kommentar:






Bisher...

 
15.09.2016 12:29 s…r sagt:
[noch nicht freigeschaltet]
 
08.02.2016 10:22 Thomas sagt:
@Paddi: Ich würde behaupten, dass Blöcke nicht angefangen sein können, sondern einfach aufgefüllt werden mit 0, bis vollständig.
 
18.11.2015 07:18 Ferdi W. sagt:
Echt cooler Beitrag. So einfach ist die Parität erklärt. Einfach nur DANKE! :)
 
26.10.2015 10:45 Paddi sagt:
Top erklärt, echt Wahnsinn!
Aber mich juckt jetzt die Frage: Was passiert, wenn eine Spalte nicht voll wird? Habe in meinem eigenen Beispiel 4 Platten und in der fünften Spalte nur einen Wert. Wie wird dann die Parität angegeben?

h0 1 1 1 x 1 0
h1 1 1 x 0 0 ?
h2 0 x 0 0 0
h3 x 1 0 1 x

h0 1 1 1 1 1 0
h1 1 1 1 0 0 ?
h2 0 1 0 0 0
h3 0 1 0 1 1
 
11.05.2014 17:08 Gustav Heinemann sagt:
Sehr guter Artikel, 1a erklärt. Selten besser gesehen und einfach verständlich.

Sehr schnell kapiert, danke - auf jeden Fall mehr! RAID 6 wäe mit der Parität evtl. noch interessant :)
 
01.05.2014 15:54 Robin Grube sagt:
Sehr gute Erkärung. :)
Genau dieses Wissen benöige ich für meine Prüfung. Vielen Dank für diese simple, aber sehr gute Erklärung.
 
15.09.2013 19:49 Delikan sagt:
Verdammte scheiße, danke man. Damit konnte ich die Aufgabe in der Zwischenprüfung Fachinformatiker lösen.
 
07.07.2013 22:30 Eduard Dopler sagt:
Hallo Natalie, ich weiß nicht, wie du auf deine h3-Werte gekommen bist. Du rechnest in der ersten Spalte: 1 XOR 0 XOR 1 und das Ergebnis für h3 ist dann 0, nicht 1. Das kannst du dann einfach zurückrechnen. Reicht der Tipp?
 
05.07.2013 14:37 Natalie sagt:
Hallo,
finde den Artikel klasse. Habe das Prinzip sofort verstanden. Mit drei Festplatten versteh ich das sofort und kriege das auch bei anderen Musterbeispielen hin.
Nur leider steige ich bei 4 Festplatten aus, sobald es sich um ungerade Werte handelt, trotz vielem Überlegen.

Bsp.
h0 1 1 0 1 1 1 1 1 0 …
h1 0 0 1 1 1 0 1 0 0 …
h2 1 1 1 0 1 1 0 0 0 …
h3 1 0 0 1 0 0 1 1 0 …

Wenn jetzt hier die Platte h2 ausfällt, woher weiss ich dann, ob z.B. in der ersten Spalte, ob eine 1 oder eine 0 vorher drinnen war. Meine Wertereihe könnte ja 101 oder 100 lauten. Ich weiß zwar dass meine Paritätsziffer eine 1 ist (h3), jedoch kann ich daraus nicht ableiten, was in h2 vor dem Ausfall drinnen war, da ja beides möglich ist.

Vllt. kann mir das jemand nochmal aufzeigen. Das wäre super toll.
Vielen vielen Dank im Voraus!!!
 
04.04.2013 08:56 Marc sagt:
Klasse Artikel! Endlich konnte ich meinen Azubis die Raid Paritätenberechnung verständlich erklären, ohne das ich am Ende in fragende Gesichter schauen mußte ;-)
 
04.02.2013 21:06 Nicolas sagt:
sehr schön erklärt raid 5 hab ich nun verstanden, nun beiss ich mir die zähne an raid 6 aus
 
15.11.2012 10:20 Horst sagt:
Hallo,
habe gerade genau nach Informationen zu diesem Thema gesucht - und hier eine wirklich gelungene Erklärung gefunden, die selbst ich sofort verstanden habe! Habs gerade auch mal mit 4 Platten durchgespielt und .... ES FUNKTIONIERT :-)
Vielen Dank!
 
18.02.2012 15:02 Jan D sagt:
Hey,
habs grade mal "durchgerechnet", und ist echt sehr gut&einfach erklärt, vielen Dank!

Grüße
 
26.11.2011 10:59 Hubert sagt:
Oje ja klar - Danke
 
25.11.2011 11:31 Eduard Dopler sagt:
Wo liegt denn das Problem?
Versuche doch mal, alle Schritte genauso auszuführen wie bei drei Festplatten. Ich möchte dir nur ungern dein Erfolgserlebnis nehmen ;-)
 
25.11.2011 11:04 Hubert sagt:
Klasse - das ist echt super erklärt - kannst Du das mir mal mit 4 Platten erklären - das raff ich nähmlich immer noch nicht.

Dankeschön
 
27.10.2011 12:11 Kim sagt:
WOW! n-1 war mir schon immer klar, aber ich konnte es mir nicht erklären, ich war immer der Meinung dass für den Ernstfall alle Daten 2.fach geschrieben werden müssen. Endlcih habe ich es auch verstanden! Mir ist ein Licht aufgegangen. Top erklärung!
 
04.04.2011 00:09 Flo sagt:
Danke für die schöne Anleitung. Ist wirklich Klasse erklärt :)
 
26.03.2011 12:11 Eduard Dopler sagt:
Dann habe ich das so verstanden.
Du siehst es auf jeden Fall richtig: Man zahlt für die Wiederherstellungsinfos 1/n an Festplattenplatz.
 
26.03.2011 12:07 Freundhansen sagt:
Ich habe doch gar nichts zur grundsätzlichen RAID Technik gefragt?
Oder was meinst du?
 
26.03.2011 11:32 Eduard Dopler sagt:
Mir ging es mit diesem Blogeintrag nicht um die grundsätzliche RAID-Technik. Die kannst du einfach im Wikipedia-Artikel nachlesen.
Aber im Fall von drei Festplatten hast du Recht, ja.
 
26.03.2011 11:17 Freundhansen sagt:
Das ist eine gute Technik, und sie wurde sehr gut erklärt.

Allerdings zahlt man den Preis für die Datenwiederherstellung damit, dass das Datenvolumen natürlich auf allen Platten aufgebläht wird.
Wenn ich das richtig verstanden habe wird also nur noch 2/3 der gesamten Platten für Nutzdaten verwendet?
 
25.03.2011 19:40 Nathan sagt:
Schon intelligent, ich durfte da mal ein Referat drüber halten und mich hat auch ein Erfolgserlebnis ereilt, als ich das gerafft hatte. Aber danach hat es mich total begeistert!

Und ja, du hast das wunderbar und verständlich erklärt. Hättest du das nicht ein Jahr früher machen können ;-)
 
25.03.2011 15:21 compr00t sagt:
Schöner Artikel, gute Erklärung!
Wenn du magst, schreib den Link als Kommentar zu meinem Artikel :)

gruss
Patrick

de

Moment, lade ältere Artikel...

E-Mail (nicht öffentlich)

Homepage (optional)

Kommentar... (code-Tag erlaubt)