In diesem Artikel werde ich versuchen, ein einfaches Beispiel für mein eigenes Fehlerkorrektursystem zu zeigen, das auf RAID-6 basiert. Stellen Sie sich insbesondere eine Situation vor, in der Sie Systemredundanz bereitstellen müssen, damit diese dem Ausfall von einem oder zwei Laufwerken standhält.
Als Bonus Informationen zur Funktionsweise der Fehlerkorrektur in RAID-5, da RAID-6 eine verbesserte Version von RAID-5 ist.
Überblick
Angenommen, Sie haben drei Festplatten mit einigen Daten. Nennen wir sie D1, D2 und D3. Um ein RAID-6-System verwenden zu können, benötigen Sie zwei zusätzliche Laufwerke: PD und RS. In wenigen Minuten werde ich beschreiben, wofür PD und RS stehen. Insgesamt also fünf Laufwerke: D1, D2, D3, PD und RS.
Also die Situation:
- D1, D2 und D3 enthalten beliebige Daten . Sagen wir Fotos von Katzen.
- Eine spezielle Festplatten-PD (Parity Drive, manchmal P in der Dokumentation) enthält komprimierte Daten, die automatisch aus D1, D2 und D3 generiert werden.
- Zweite Spezialscheibe RS (Reed-Solomon-Codes, manchmal auch als Q bezeichnet) für dieselben Daten wie PD.
Lassen Sie uns sehen, wie grundlegende Operationen an einem solchen Array ausgeführt werden.
Wie die Wiederherstellung funktioniert
Wenn Sie PD und RS richtig berechnen, können Sie einen Ausfall von bis zu zwei Festplatten schmerzlos überstehen. Das Wiederherstellungsverfahren hängt davon ab, welche bestimmten Festplatten ausfallen. Normalerweise werden sieben Situationen betrachtet. Unten sind sie von einfach bis komplex sortiert.
- Verlust der PD (nur eine Festplatte).
Ein sehr einfacher Fall. Das PD-Laufwerk enthält nur automatisch generierte Daten, sodass es unter Verwendung der Originaldaten auf den Laufwerken D1, D2 und D3 wiederhergestellt werden kann.
- : D1, D2 D3 ( ).
, , , RAID-5: PD . PD, . RS ( ).
- RS ( ).
1: , RS, — .
- PD RS ( ).
1 3. , PD, RS.
- RS ( ).
, . PD, , № 2. , RS.
- PD ( ).
. ( D3), PD, . RS (D1 D2), D3. PD. , — .
- ( ).
. PD, RS . — .
In den folgenden Abschnitten werden wir diese Fälle genauer untersuchen und den Quellcode (in Python) sehen, der die eigentliche Datenwiederherstellung durchführt.
Beachten Sie, dass tatsächliche RAID-6-Arrays nicht ein ganzes Laufwerk für PD oder RS zuweisen. Diese Daten werden auf alle Laufwerke verteilt. Verschiedene Controller verwenden unterschiedliche Methoden: Links asynchron oder rechts synchron, es kann zu einer Verschiebung in Bezug auf RAID-Daten, Latenz usw. kommen. Lassen wir die Diskussion darüber, warum dies geschieht und wie echte Streifen aussehen, beiseite. RAID-6. Konzentrieren wir uns speziell auf die Reed-Solomon-Codes.
Testdaten
Definieren wir "Benutzerdaten". Stellen Sie der Einfachheit halber die Größe jeder "Festplatte" auf 5 Byte ein.
| Scheibe | ASCII-Daten | Daten in HEX |
|---|---|---|
D1
|
zuerst | 0x66, 0x69, 0x72, 0x73, 0x74 |
D2
|
sek | 0x73, 0x65, 0x63, 0x6e, 0x64 |
D3
|
dritte | 0x74, 0x68, 0x69, 0x72, 0x64 |
Schauen wir uns nun die genannten Szenarien genauer an.
Situation 1. Verlust der PD-Festplatte
Zum Generieren von PD werden nur Benutzerdatenplatten benötigt. In unserem Fall sind dies D1, D2 und D3. Die PD-Festplatte wird einfach von allen Benutzerdaten XOR-verknüpft.
Um den Offset 0 für PD zu generieren, müssen alle Bytes vom Offset 0 über alle Festplatten komprimiert werden. Das Gleiche gilt für Offset 1 und so weiter:
PD [0] = D1 [0] x oder D2 [0] x oder D3 [0] PD [1] = D1 [1] xoder D2 [1] xoder D3 [1] PD [2] = D1 [2] xoder D2 [2] xoder D3 [2] PD [3] = D1 [3] xoder D2 [3] xoder D3 [3] PD [4] = D1 [4] xoder D2 [4] xoder D3 [4]
Beispiel:
PD [0] = 0x66 x oder 0x73 x oder 0x74 => 0x61 PD [1] = 0x69 x oder 0x65 x oder 0x63 => 0x64 PD [2] = 0x72 x oder 0x63 x oder 0x69 => 0x78 PD [3] = 0x73 xor 0x6e xor 0x72 => 0x6f PD [4] = 0x74 x oder 0x64 x oder 0x64 => 0x74
Ja, das ist sehr einfach. Wenn Sie dies für ganze Festplatten (in unserem Fall 5 Byte) tun, erhalten Sie eine korrekt generierte PD:
| Scheibe | Daten in HEX |
|---|---|
PD
|
0x61, 0x64, 0x78, 0x6f, 0x74 |
Wenn also nur PD ausfällt, ist es ziemlich trivial, es von D1, D2 und D3 wiederherzustellen.
Situation 2. Verlust eines der Datenspeicher: D1, D2 oder D3
Übrigens funktioniert die RAID-5-Fehlerbehebung so. Wenn nur eine Benutzerdatendiskette ausfällt, können wir die PD-Diskette verwenden, um die fehlenden Benutzerdaten neu zu berechnen.
Angenommen, D2 ist verloren. D1, D3, PD und RS blieben auf Lager. Berühren Sie in diesem Fall nicht einmal RS. Es werden nur die Laufwerke D1, D3 und PD benötigt. Um die fehlenden Daten zu berechnen, können Sie die XOR-Funktion wie in der vorherigen Situation erneut verwenden.
Um die Benutzerdaten von Offset 0 wiederherzustellen, xorimieren Sie die Bytes von den Null-Offsets der Benutzerdatenplatten, die mit dem Byte von der Null-Offset-PD übrig bleiben (D1 und D3). Wiederholen Sie diesen Vorgang für Offset 1 usw.
D2 [0] = D1 [0] x oder D3 [0] x oder PD [0] D2 [1] = D1 [1] x oder D3 [1] x oder PD [1] D2 [2] = D1 [2] x oder D3 [2] x oder PD [2] D2 [3] = D1 [3] x oder D3 [3] x oder PD [3] D2 [4] = D1 [4] xoder D3 [4] xoder PD [4]
Beispiel:
D2 [0] = 0x66 x oder 0x74 x oder 0x61 => 0x73 (s) D2 [1] = 0x69 x oder 0x63 x oder 0x64 => 0x65 (e) D2 [2] = 0x72 x oder 0x69 x oder 0x78 => 0x63 (c) D2 [3] = 0x73 x oder 0x72 x oder 0x6f => 0x6e (n) D2 [4] = 0x74 x oder 0x64 x oder 0x74 => 0x64 (d)
Wie Sie sehen können, ist es sehr einfach, Daten von einer fehlenden Festplatte wiederherzustellen. Es spielt keine Rolle, welche Disc fehlt: Die XOR-Funktion funktioniert immer.
Situation 3. Verlust der RS-Festplatte
Jetzt kommen die Feldcodes Reed-Solomon und Galois ins Spiel. Aber keine Sorge, Sie müssen kein Mathematiker sein, um sie zu benutzen.
Wenn wir nur das RS-Laufwerk verlieren oder ein neues System wie RAID-6 erstellen, müssen wir nur die Codes neu generieren. Verwenden Sie dazu die Tabellen gflog und gfilog mit unveränderlichem Inhalt sowie Daten von vorhandenen Laufwerken D1, D2 und D3.
Die gflog-Tabelle sieht immer so aus:
0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b, 0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71, 0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45, 0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6, 0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88, 0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40, 0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d, 0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57, 0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18, 0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e, 0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61, 0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2, 0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6, 0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a, 0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7, 0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf.
Die gfilog-Tabelle ist ebenfalls persistent:
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26, 0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, 0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23, 0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1, 0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0, 0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2, 0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce, 0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc, 0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54, 0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73, 0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff, 0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41, 0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6, 0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09, 0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16, 0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01.
Es ist nicht erforderlich, diese Tabellen in das Programm aufzunehmen. Sie können zur Laufzeit den folgenden Generierungsalgorithmus verwenden:
# gflog_tables.py
def generate_tables():
polynomial = 0x11d
s = 8
gf_elements = 1 << s
gflog = gf_elements * [0]
gfilog = gf_elements * [0]
b = 1
for i in range(0, gf_elements):
gflog[b] = i & 255
gfilog[i] = b & 255
b <<= 1
if b & gf_elements:
b ^= polynomial
gflog[1] = 0;
return (gflog, gfilog)
def dump_table(caption, tab):
item = 0
print("--- {} ---".format(caption))
for i in tab:
print("0x{:02x}, ".format(i), end="")
item += 1
if item % 16 == 0:
item = 0
print()
print("")
(gflog, gfilog) = generate_tables()
# Uncomment if you want to see the tables on the console:
#
# dump_table("gflog", gflog)
# dump_table("gfilog", gfilog)
Nachdem die Tabellen deklariert wurden, müssen einige Operationen definiert werden. Jetzt arbeiten wir in einem endlichen Feld (Galois-Feld), sodass die grundlegenden arithmetischen Operationen eine andere Implementierung haben (obwohl die Bedeutung etwas ähnlich ist). Sie müssen die grundlegenden Operationen neu definieren - Addition, Multiplikation und Division:
# rs_functions.py
from gflog_tables import *
# Addition
def gf_add(*args):
result = 0
for arg in args:
result ^= arg
return result
# Indexing
# First drive is 1, second drive is 2, etc...
def gf_drive(index):
global gfilog
return gfilog[index - 1]
# Multiplication
def gf_mul(a, b):
global gflog
global gfilog
if a == 0 or b == 0:
return 0
else:
return gfilog[(gflog[a] + gflog[b]) % 255]
# Division helper
def sub_gf8(a, b):
if a > b:
return a - b
else:
return (255 - (0 - (a - b)))
# Division
def gf_div(a, b):
global gfilog
global gflog
return gfilog[sub_gf8(gflog[a], gflog[b])]
Da die Hilfsfunktionen deklariert sind, versuchen wir, die RS-Datenträgerdaten zu generieren.
# case 3 -- recover_rs.py
from rs_functions import *
# Here are our drives, together with their data.
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
image2 = [ ord('s'), ord('e'), ord('c'), ord('n'), ord('d') ]
image3 = [ ord('t'), ord('h'), ord('i'), ord('r'), ord('d') ]
# This is a placeholder for our RS drive. It will be regenerated
# in the lines below.
imageRS = [0] * 5
# And this is our loop that generates the RS data using nothing more
# than the user data drives.
for i in range(0, 5):
imageRS[i] = gf_add(gf_mul(gf_drive(1), image1[i]),
gf_mul(gf_drive(2), image2[i]),
gf_mul(gf_drive(3), image3[i]))
dump_table("imageRS", imageRS)
Nach dem Ausführen des Skripts
recover_rs.py
enthält die RS-Festplatte die folgenden Daten:
| Scheibe | Daten in HEX |
|---|---|
RS
|
0x4d, 0x1e, 0x0d, 0x7a, 0x31 |
Im Moment sind D1-, D2- und D3-Laufwerke durch den vollständigen RAID-6-Fehlerkorrekturalgorithmus geschützt, da wir PD und RS korrekt generiert haben.
Es ist wichtig zu beachten, dass die aktuellen RS-Daten nur für D1, D2 und D3 in dieser bestimmten Reihenfolge gültig sind . Somit werden die RS für D1, D2 und D3 seine verschieden von D3, D2 und D1 , obwohl die tatsächlichen Daten auf den Platten gleich sind. Dies ist wichtig zu beachten, da Sie bei der Wiederherstellung von RAID-6-Daten die richtige Festplattensequenz innerhalb des Arrays kennen müssen. Wenn das Array klein ist, können Sie glücklicherweise die Generierung der RS-Daten erzwingen, um die richtige Plattensequenz zu finden.
Situation 4. Verlust von PD und RS
Dies ist auch eine einfache Situation: Wir führen zuerst Szenario 1 und dann Szenario 3 aus. Ich
wiederhole, in diesem Fall sind die Benutzerdaten nicht betroffen. Wir können sie verwenden, um eine PD zu erstellen. Dann RS erstellen. Beide Fälle wurden bereits in den Punkten 1 und 3 beschrieben.
Situation 5. Verlust von RS und einer Datenplatte
Und hier ist es nicht schwer. Wir haben eine Datenfestplatte verloren, aber wir haben immer noch eine PD, sodass wir Szenario 2 ausführen können, um die fehlende Datenfestplatte wiederherzustellen. Verwenden Sie dann alle Datenfestplatten für die RS-Regeneration wie in Szenario 3. Der vollständige Satz von Festplatten wird jetzt wiederhergestellt.
Situation 6. Verlust von PD und einer Datenplatte
Der allgemeine Ansatz besteht darin, zuerst die fehlende Datenfestplatte mit anderen Festplatten in Kombination mit RS wiederherzustellen und dann, nachdem alle Datenfestplatten wiederhergestellt wurden, die PD neu zu generieren (Szenario 2).
In dieser Situation müssen Sie einige Berechnungen durchführen. Angenommen, wir haben zusammen mit PD die Datenplatte D2 verloren. Wir haben also D1, D3 und RS auf Lager.
Dank der RS-Disk können wir D2 wiederherstellen, indem wir D1, D3 und RS wie folgt kombinieren:
# case 6 -- recover_d2_and_pd.py
from rs_functions import *
# We have these drives...
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
image3 = [ ord('t'), ord('h'), ord('i'), ord('r'), ord('d') ]
imageRS = [ 0x4d, 0x1e, 0x0d, 0x7a, 0x31 ]
# ...and these drives are dead
imagePD = [0] * 5
image2 = [0] * 5
for i in range(0, 5):
partialRS = gf_add(gf_mul(gf_drive(1), image1[i]),
imageRS[i], # Use RS drive instead of the dead drive.
gf_mul(gf_drive(3), image3[i]))
# gf_drive(2) is our dead drive.
div_result = gf_div(1, gf_drive(2))
# This will generate the data from the dead D2 drive.
image2[i] = gf_mul(div_result, partialRS)
# This will generate the data from the dead PD drive.
imagePD[i] = gf_add(image1[i], image2[i], image3[i])
dump_table("image2", image2)
dump_table("imagePD", imagePD)
Zunächst müssen Sie einen Wert generieren,
partialRS
indem Sie (gf_add) die Rückgabewerte
gf_mul
für alle Bytes aller gültigen Datenträger zusammen mit dem RS-Wert anstelle des fehlenden Datenträgers hinzufügen (in unserem Fall D2).
Wir verwenden den Wert dann
partialRS
, um die D2-Daten neu zu generieren, indem wir eins durch den Dead Disk Index (
gf_drive(2)
) dividieren und das Ergebnis mit multiplizieren
partialRS
. Das Argument
gf_drive(2)
gibt den Index unserer toten Festplatte an. Wenn D1 fehlschlägt, würden wir hier verwenden
gf_drive(1)
.
Stellen Sie nach der Neuerstellung von D2 alle Datenfestplatten wieder her. In diesem Fall führen wir die PD-Regeneration wie in Szenario 1 durch: Im obigen Code erfolgt dies durch Hinzufügen von (gf_add) Daten von allen Festplatten. Falls du dich erinnerst
gf_add
Das Galois-Feld ist eine einfache XOR-Operation. Anstatt Bytes von allen Datenplatten manuell zu xoring, können Sie das verwenden
gf_add
.
Situation 7. Verlust von zwei Datensammlern
Dies ist das interessanteste und schwierigste Szenario. Angenommen, die Datenträger D2 und D3 sind nicht in Betrieb. In diesem Fall müssen Sie die D1-, PD- und RS-Festplatten verwenden, um die fehlenden Festplatten neu zu generieren.
Dies ist ein anderer Ansatz als in früheren Fällen. Ein allgemeiner Ansatz besteht darin, zuerst Daten für D2 zu generieren und dann dieselbe Schätzung wie in Szenario 2 zu verwenden, um Daten für D3 zu generieren. Hier ist der Code:
# case 7 -- recover_d2_and_d3.py
from rs_functions import *
# These drives are still alive.
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
imagePD = [ 0x61, 0x64, 0x78, 0x6f, 0x74 ]
imageRS = [ 0x4d, 0x1e, 0x0d, 0x7a, 0x31 ]
# These drives are dead, we can't read from them.
image2 = [0] * 5
image3 = [0] * 5
for i in range(0, 5):
partialPD = gf_add(image1[i]) # add other drives if they exist
partialRS = gf_add(gf_mul(gf_drive(1), image1[i])) # add other drives if they exist
g = gf_div(1, gf_add(gf_drive(2), gf_drive(3)))
xoredPD = gf_add(partialPD, imagePD[i])
xoredRS = gf_add(partialRS, imageRS[i])
mid = gf_add(gf_mul(gf_drive(3), xoredPD), xoredRS) # gf_drive(3) is the second drive we've lost
# Regenerate data for D2.
data = gf_mul(mid, g)
image2[i] = data
# Regenerate data for D3.
image3[i] = gf_add(image1[i], image2[i], imagePD[i])
# or:
#
# image3[i] = gf_add(data, xoredPD)
dump_table("image2", image2)
dump_table("image3", image3)
Zunächst müssen Sie alle Bytes aller vorhandenen Datenfestplatten hinzufügen, um sie zu generieren
partialPD
. In diesem Beispiel haben wir nur eine Datendiskette, daher ist der Parameter
partialPD
einfach der Inhalt der D1-Diskette. RAID-6-Arrays erstrecken sich jedoch über mehrere Laufwerke. Wenn wir also mehr als eine Datenfestplatte haben, z. B. drei Live-Datenfestplatten, sieht die partielle PD-Berechnung folgendermaßen aus:
partialPD = gf_add(image1[i], image2[i], image3[i])
Als nächstes brauchen wir einen Parameter
partialRS
. Sie kann wie folgt berechnet werden, indem Daten von vorhandenen Festplatten hinzugefügt werden:
partialRS = gf_add(A, B, C, ..., Z)
where A = gf_mul(gf_drive(1), image1[i])
B = gf_mul(gf_drive(2), image2[i]) if we have drive 2
C = gf_mul(gf_drive(3), image3[i]) if we have drive 3
etc.
In unserem Fall ist nur noch ein Datenlaufwerk (D1) übrig, daher ist unser Laufwerk
partialRS
einfach
gf_mul(gf_drive(1), image1[i])
.
Dann müssen Sie den Parameter generieren,
g
indem Sie einen durch die Summe der toten Plattenindizes (D2 und D3) dividieren.
Als nächstes kommt der Parameter
xoredPD
; Sie wird berechnet, indem der Inhalt der PD zum
partialPD
zuvor berechneten Parameter hinzugefügt wird . Der nächste Parameter wird
xoredRS
auf ähnliche Weise berechnet, indem er
partialRS
dem RS-Inhalt hinzugefügt wird.
Nun zum kniffligen Teil. Sie können die Daten von der ersten defekten Festplatte, dh von der D2-Festplatte, berechnen . Multiplizieren Sie dazu den Index der zweiten defekten Festplatte (D3) mit einem Parameter
xoredPD
und fügen Sie dem Ergebnis einen Parameter hinzu
xoredRS
. Dann nach dem Multiplizieren des Ergebnisses mit dem Parameter
g
erhalten wir den Inhalt der D2-Platte.
Da wir gerade Daten für D2 wiederhergestellt haben, unterscheidet sich dieser Fall nicht von Szenario 2 - Verlust einer Datenplatte (D3). Um ein D3-Laufwerk zu erstellen, müssen alle Live-Datenlaufwerke (D1 und D2) zur PD hinzugefügt werden.
Erledigt! Wir haben einen kompletten Satz Discs zurückgegeben.
Epilog
Ich habe Python gewählt, um zu demonstrieren, dass das Korrigieren von Fehlern mit Reed-Solomon-Codes nicht viel Programmier- oder Verarbeitungsleistung erfordert. Alles ist sehr schnell und die Implementierung kann sehr kompakt sein. Natürlich sollte eine effizientere Implementierung unter Berücksichtigung der Parallelverarbeitung geschrieben werden. Da jedes Byte unabhängig von den anderen berechnet wird, ist die Parallelisierung nicht schwierig.
Es ist zu beachten, dass das beschriebene Datenwiederherstellungsverfahren nicht auf separaten physischen Datenträgern verwendet werden muss. "Festplatten" können als "Puffer" beim Übertragen von Daten über einen unzuverlässigen Kanal betrachtet werden, und eine solche Fehlerkorrektur bleibt wirksam. Hier sind intensivere Berechnungen erforderlich als bei Hamming-Codes, es können jedoch zwei gefallene Ströme ausgelöst werden. Dies ist eine leistungsstarke Ausfallsicherheitsfunktion.
Natürlich ist RAID-6 alles andere als eine neue Erfindung, und die Reed-Solomon-Codes sind noch älter. Sie wurden bereits in der Voyager 2-Mission verwendet , was ziemlich cool ist.
Zu den moderneren Alternativen für Reed-Solomon- Codes gehören Turbo-Codes - ich hoffe, ich habe auch die Möglichkeit, mich mit ihnen zu befassen .