Ist das 2. Paritätsbit in RAID 6 eine einfache Berechnung?

Ich versuche zu verstehen, wie das 2. Paritätsbit oder -byte in RAID 6 gesetzt wird. Ich lese einen Artikel von H. Peter Anvin und er geht in die Galois-Feldalgebra, die für mich etwas neu ist. Wie auch immer, eine Mitarbeiterin von HP versuchte mir RAID 6 zu erklären und sie dachte, es seien nur zwei XOR-Operationen, eine für das erste Paritätsbit und eine für das zweite. Das macht für mich keinen Sinn, aber da ich das Papier noch durcharbeite, weiß ich nicht, ob es sich für RAID 6 im Gegensatz zu RAID n auf etwas Einfaches reduziert. Es sieht für mich so aus, als ob das 2. Paritätsbit etwas komplizierter ist als das XOR-basierte 1. Paritätsbit. Ist das wahr?

Der allgemeine Fall ist in der Tat etwas kompliziert.

Bei 4 Festplatten können Sie dies jedoch erheblich vereinfachen. Sie müssen keine ausgefallene Mathematik kennen. Sie müssen nur wissen, wie 4 Bits redundant gespeichert werden, und dann wissen Sie bereits alles. Wiederholen Sie einfach das gleiche Schema für jede Gruppe von 4 Bits, die Sie speichern müssen.

Wir können das Schema als 4 x 4 Tabellen darstellen. Die ersten 2 Bits unserer Daten bestimmen die Zeile und die letzten 2 Bits unserer Daten bestimmen die Spalte.

Datenträger 1: Speichern Sie einfach die ersten 2 Bits. Das ist:

00 00 00 00
01 01 01 01
10 10 10 10
11 11 11 11

Datenträger 2: Speichern Sie einfach die letzten 2 Bits. Das ist:

00 01 10 11
00 01 10 11
00 01 10 11
00 01 10 11

So weit, ist es gut. Bei Datenträger 1 + Datenträger 2 können wir unsere Originaldaten wiederherstellen: Datenträger 1 gibt die Zeile (die ersten 2 Bits der Originaldaten) und Datenträger 2 die Spalte (die letzten 2 Bits der Originaldaten) an.

Datenträger 3: Dies ist, was wir auf RAID5 tun, nur XOR die Bits:

00 01 10 11
01 00 11 10
10 11 00 01
11 10 01 00

Auch hier ist noch alles in Ordnung. Sie können die Originaldaten mit Datenträger 1 + Datenträger 3 oder Datenträger 2 + Datenträger 3 wiederherstellen. Eine wichtige Beobachtung ist, dass die Nachschlagetabelle für Datenträger 3 ein lateinisches Quadrat bildet : Alle Elemente jeder Zeile sind unterschiedlich, und alle Elemente jeder Spalte sind unterschiedlich deutlich. Wenn Sie beispielsweise die Daten auf Datenträger 1 kennen, kennen Sie die richtige Zeile, und Sie können die Daten auf Datenträger 3 verwenden, um die Spalte wiederherzustellen. Wenn Sie dagegen die Daten auf Datenträger 2 kennen, kennen Sie die rechte Spalte, und dann können Sie die Daten auf Datenträger 3 verwenden, um die Zeile wiederherzustellen.

Datenträger 4: Hier können wir die folgende Nachschlagetabelle verwenden:

00 01 10 11
10 11 00 01
11 10 01 00
01 00 11 10

Mach dir keine Sorgen, wie es aufgebaut ist; das interessiert uns nicht wirklich. Die entscheidenden Eigenschaften sind:

• Die Nachschlagetabellen von Datenträger 3 und Datenträger 4 sind lateinische Quadrate. Wenn Sie also 1 + 3 oder 1 + 4 oder 2 + 3 oder 2 + 4 kennen, können Sie sowohl Zeile als auch Spalte (dh die Originaldaten) wiederherstellen.

• Die Nachschlagetabellen von Datenträger 3 und Datenträger 4 bilden orthogonale lateinische Quadrate , wodurch die Daten wiederhergestellt werden können, wenn nur Datenträger 3 + 4 vorhanden sind.

Lassen Sie uns auf den zweiten Punkt näher eingehen. Durch Verketten der Nachschlagetabellen von Datenträger 3 und Datenträger 4 erhalten wir diese Matrix:

0000 0101 1010 1111
0110 0011 1100 1001
1011 1110 0001 0100
1101 1000 0111 0010

Beachten Sie nun, dass jede 4-Bit-Zeichenfolge in dieser Tabelle genau einmal vorkommt. Das heißt, wenn wir wissen, was auf den Datenträgern 3 + 4 gespeichert ist, wissen wir, wo wir uns in dieser Tabelle befinden. Wir kennen sowohl die Zeile als auch die Spalte und können daher die ursprünglichen Daten wiederherstellen.

Wenn Sie darauf bestehen, die Verbindung zu Galois-Feldern zu sehen, betrachten Sie das Feld . Beschriften Sie die Elemente des Feldes mit ; diese entsprechen 2-Bit-Strings ( ≈ , ≈ , ≈ , ≈ ). Nun kann jeder 4-Bit - String kann encode als ein Paar sein , wobei .$F = GF(2^2)$$F = \{0,1,x,x+1\}$$0$00$1$01$x$10$x+1$11$(a,b)$$a,b \in F$

Ein Paar wird nun wie folgt gespeichert:$(a,b)$

• Datenträger 1 speichert .$a$
• Datenträger 2 speichert .$b$
• Datenträger 3 speichert .$a+b$
• Datenträger 4 speichert .$xa+b$

Wenn Sie beispielsweise nur und angeben, können Sie und lösen . Mit der Regel können Sie finden$p = a+b$$q = xa+b$$a$$b$$2 \equiv 0$

• $p + q = (xa+b) + (a+b) = (x+1)a + 2b \equiv (x+1)a$ ,
• $p + xq = (xa+b) + x(a+b) = 2xa + (x+1)b \equiv (x+1)b$ .

Teilen Sie dann durch , um und usw. zu erhalten. Letztendlich liefert dieser Ansatz jedoch genau die gleichen Nachschlagetabellen wie oben dargestellt.$x+1$$a$$b$

Die Berechnung für ist definitiv schwieriger als die für erforderliche XOR-Berechnung, obwohl es sich in gewissem Sinne um dieselbe Art der Berechnung handelt: eine Polynomauswertung.$Q$$P$

Ohne die in der Verknüpfung beschriebenen detaillierten Berechnungstechniken besteht die Idee darin, die Datenbytes / Laufwerke , als die Koeffizienten eines Polynoms . Dann,$n$$D_0$$D_1, \ldots, D_{n-1}$$D(x) = D_0 + D_1x + \cdots + D_{n-1}x^{n-1}$

$\qquad \begin{align*} P &= D(1) = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1}\\ Q &= D(\alpha) = D_0 \oplus D_1\cdot\alpha \oplus \cdots \oplus D_{n-1}\cdot\alpha^{n-1}\\ &= ((\cdots(D_{n-1}\cdot\alpha \oplus D_{n-2})\cdot\alpha \oplus \cdots \oplus D_1\cdot\alpha) \oplus D_0 \end{align*}$

Dabei ist ein Element (bezeichnet mit in dem vom OP zitierten Artikel) des Galois-Feldes GF (auch bezeichnet mit ), dessen Elemente sind die Bit-Bytes, und die zweite Zeile der Gleichung für kann als Horner-Regel erkannt werden. Natürlich kann die Berechnung für auch als Verwendung der Horner-Regel angesehen werden, außer dass wir die Multiplikationen mit als NOPs ignorieren und alle Klammern in der Horner-Regel entfernen, da sie nicht erforderlich sind.$\alpha$$\{02\} = (00000010)$$(2^8)$$\mathbb F_{2^8}$$256$$256$ $8$$Q$$P = D(1)$$1$

Nachdem die Laufwerke geschrieben wurden,

• Wenn eines oder beide von und fehlschlagen, gibt es kein Problem; und können neu berechnet und auf Ersatzlaufwerken gespeichert werden.$P$$Q$$P$$Q$

• Wenn der einzige Fehler ein Datenlaufwerk ist , beispielsweise das te Laufwerk, kann dessen Inhalt neu berechnet werden, da $i$

  $$D_i = D_0 \oplus D_1 \oplus \cdots \oplus D_{i-1} \oplus D_{i+1} \oplus \cdots \oplus D_{n-1} \oplus P.$$

• Wenn ein Datenlaufwerk und ausfallen, kann das Datenlaufwerk wie oben beschrieben neu berechnet werden, und dann kann neu berechnet werden.$Q$$Q$

• Was in den anderen Fällen zu tun ist: Ein Datenlaufwerk und ein Fehler oder zwei Datenlaufwerke sind komplizierter zu beschreiben, aber die Methoden können unter Verwendung der hier beschriebenen Polynomperspektive leichter verstanden werden. Wenn beispielsweise der te und der te Antrieb ausgefallen sind, ist die Rekonstruktion effektiv die Lösung der simultanen Gleichungen: wobei die rechte Seite aus dem Inhalt der nicht ausgefallenen Laufwerke berechnet werden kann.$P$$i$$j$

  $$\begin{align*} D_i \oplus D_j &= P \oplus \sum_{k: k \neq i, j} D_k\\ \alpha^i\cdot D_i \oplus \alpha^j \cdot D_j &= Q \oplus \sum_{k: k \neq i, j} D_k\cdot\alpha^k. \end{align*}$$

Der Raid-6 mit drei Datenträgern ist trivial: Speichern Sie einfach dieselben Informationen auf Datenträger 1, Datenträger 2 und Datenträger 3. Zwei Datenträger können ausfallen, und Sie können die Daten trotzdem wiederherstellen. Ein Raid-6 mit drei Festplatten ist also im Grunde nur ein Raid-1 mit drei Festplatten.

Im Fall von vier Datenträgern gibt es zwei Daten- "Datenträger" (nennen wir sie und ) und zwei Paritäts- "Datenträger" (nennen wir sie und ). Darüber hinaus haben wir in einer Zeit auf zwei Bits , die von jeder Platte zu arbeiten, so dass das Mindestdatenelement (deren Paritätserzeugung wird hier gezeigt) vier Bits sind: Zwei Bits auf der Platte und zwei Bits auf der Platte . Dadurch werden zwei Bits der Parität erzeugen und zwei weitere Bits der Parität . Wenn wir mehr Bits haben, wiederholen wir dieses Schema einfach nach Bedarf.$A$$B$$P$$Q$$A$$B$$P$$Q$

Die erste Parität wird normal unter Verwendung eines Standard-XOR ( ) berechnet :$P$$⊕$

$P = A ⊕ B$

Für die zweite Parität müssen wir eines der Datenelemente entstellen, bevor wir das XOR ausführen, damit es sich von :$Q$$P$

$Q = A ⊕ B^*$

Das verstümmelte wird aus wie folgt berechnet : Das erste Bit von ist das XOR beider Bits von , und das zweite Bit von ist eine Kopie des ersten Bits von :$B^*$$B$$B^*$$B$$B^*$$B$

$B^* = (B^*_1, B^*_2) = (B_1 ⊕ B_2, B_1)$

Die obige Formel führt zu der folgenden Tabelle für die Berechnung von aus :$B^*$$B$

$00 \rightarrow 00$
$01 \rightarrow 10$
$10 \rightarrow 11$
$11 \rightarrow 01$

Beachten Sie, dass der Wert beim Zerlegen unverändert bleibt, während die anderen Werte einen Zyklus von drei durchlaufen: .$00$$01 \rightarrow 10 \rightarrow 11 \rightarrow 01$

Das Entwirren ist ziemlich einfach: Aufgrund der zyklischen Eigenschaft wiederholen Sie das Entwirren einfach zweimal, um ein Entwirren durchzuführen. Oder invertieren Sie die obige Formel für , was zu Folgendem führt:$B^*$

$B = (B^*_2, B^*_1 ⊕ B^*_2)$

Das Entwirren ist also etwas symmetrisch zum Zerfleischen.

Jetzt kommt die Magie, die uns später die Wiederherstellung in dem Szenario ermöglicht, dass die beiden Datenfestplatten ausfallen und nur die Paritätsfestplatten überleben: Was passiert, wenn und XORed werden? Schauen wir uns jetzt an:$B$$B^*$

$B ⊕ B^* = (B_1, B_2) ⊕ (B_1 ⊕ B_2, B_1) = (B_1 ⊕ B_1 ⊕ B_2, B_1 ⊕ B_2) = (B_2, B_1 ⊕ B_2)$

Das schöne Ergebnis: XORing und identisch ist ein unmangle Schritt auf zum Durchführen . Somit kann aus werden, indem eine Mangel darauf aufgetragen wird: . Und da das Ergebnis der XOR-Verknüpfung der beiden Paritätswerte und , wird eine Wiederherstellung allein von den Paritätsplatten möglich.$B$$B^*$$B$$B$$B ⊕ B^*$$B = (B ⊕ B^*)^*$$(B ⊕ B^*)$$P$$Q$

Jetzt haben wir alles zusammen: Um und auf einem RAID-6 zu speichern , berechnen wir zuerst das verstümmelte Datum und dann die Standardparität aus und und die verstümmelte Parität aus und :$A$$B$$B^*$$P$$A$$B$$Q$$A$$B^*$

$B^* = (B_1 ⊕ B_2, B_1)$
$P = A ⊕ B$
$Q = A ⊕ B^*$

Die Wiederherstellung nach dem Ausfall von zwei Festplatten erfolgt wie folgt:

• Wenn und überleben, neu berechnet nur und . $A$$B$$P$$Q$
• Wenn und überleben, stellen Sie und berechnen Sie . $A$$P$$B = P ⊕ A$$Q$
• Wenn und überleben, stellen Sie und berechnen Sie . $B$$P$$A = P ⊕ B$$Q$
• Wenn und überleben, erholen , dann erholen von über eine unmangle Operation (oder eine Doppel mangle), dann Recompute . $A$$Q$$B^* = Q ⊕ A$$B$$B^*$$P$
• Wenn und überleben, berechnen Sie das verstümmelte aus , stellen Sie dann und berechnen Sie . $B$$Q$$B^*$$B$$A = Q ⊕ B^*$$P$
• Wenn und überleben, verwenden Sie die oben erläuterte Formel und stellen Sie dann . $P$$Q$$B = (P ⊕ Q)^*$$A = P ⊕ B$

In dem fünf Platten Fall gibt es drei Datenscheiben , und und wieder zwei Paritätsplatten und . Der bemerkenswerteste Unterschied besteht darin, dass die Mangel bei der Berechnung von zweimal an wird :$A$$B$$C$$P$$Q$$C$$Q$

$P = A ⊕ B ⊕ C$
$Q = A ⊕ B^* ⊕ C^{**}$

Die Wiederherstellung im Fall mit fünf Festplatten erfolgt nach denselben Prinzipien wie im Fall mit vier Festplatten. In diesen Fällen, in denen zwei Datenplatten und entweder oder überleben, muss man zwei Werte aus der Parität herausnehmen und nicht nur einen, und im Fall von die richtige Entwirrungsfunktion verwenden . Zum Beispiel wird wie folgt aus , und : .$P$$Q$$Q$$C$$A$$B$$Q$$C = (Q ⊕ A ⊕ B^*)^*$

Der schwierigste Fall ist, wenn die Festplatten , und überleben. Dann wird zuerst aus und XOR-verknüpft , und dann wird vor dem XOR-Verknüpfung mit entstellt . Das kartiert und lässt Ebene :$A$$P$$Q$$A$$P$$Q$$(P ⊕ A)$$(Q ⊕ A)$$B$$C$

$(P ⊕ A)^* ⊕ (Q ⊕ A) = (A ⊕ B ⊕ C ⊕ A)^* ⊕ (A ⊕ B^* ⊕ C^{**} ⊕ A) =$
$= (B ⊕ C)^* ⊕ (B^* ⊕ C^{**}) = (B^* ⊕ C^*) ⊕ (B^* ⊕ C^{**}) =$
$= B^* ⊕ C^* ⊕ B^* ⊕ C^{**} = B^* ⊕ B^* ⊕ C^* ⊕ C^{**} = (C ⊕ C^*)^* =$
$= (C^{**})^* = C^{***} = C$

Bei sechs oder mehr Festplatten bleibt das Prinzip dasselbe, aber der Mangle-Vorgang muss durch eine mit einem längeren Zyklus ersetzt werden. Dies erfordert auch die Verwendung von mehr Bits. Mit vier Bits ist eine mögliche Mangle-Operation:

$M^* = (M_1 ⊕ M_4, M_1, M_2, M_3)$

$0000$ wird erneut auf abgebildet , während alle anderen Werte einen 15-stufigen Zyklus durchlaufen:$0000$$0001 \rightarrow 1000 \rightarrow 1100 \rightarrow 1110 \rightarrow 1111 \rightarrow 0111 \rightarrow 1011 \rightarrow 0101 \rightarrow 1010 \rightarrow 1101 \rightarrow 0110 \rightarrow 0011 \rightarrow 1001 \rightarrow 0100 \rightarrow 0010 \rightarrow 0001$

Mit seinem 15-stufigen Zyklus kann dieses Mangle-Op für bis zu 15 Datenfestplatten und zwei Paritätsfestplatten verwendet werden. Für die Parität werden alle Werte unverändert zusammen XOR-verknüpft, und für wird das Datum der ersten Festplatte nicht entstellt, das Datum der zweiten Festplatte wird einmal entstellt, das Datum der dritten Festplatte wird zweimal entstellt und so weiter.$P$$Q$

Es sieht für mich verdammt kompliziert aus .

Somit ist in der obigen Formel die Berechnung von P nur das XOR jedes Streifens. Dies liegt daran, dass die Addition in zwei charakteristischen endlichen Feldern auf die XOR-Operation reduziert wird. Die Berechnung von Q ist das XOR einer verschobenen Version jedes Streifens.

(P ist das erste Paritätsbit und Q ist das zweite.)

Es klingt also so, als ob die Erklärung, die Sie erhalten haben, eine gültige Beschreibung der Berechnung auf hoher Ebene ist, ohne auf die mathematische Theorie und Details einzugehen, die weder Sie noch sie (oder ich oder die meisten anderen) tatsächlich verstehen.