David Madore's WebLog: Les détails de RAID6 et le choix d'un polynôme

Mon passage à RAID6 est essentiellement fini, mais comme j'aime bien connaître les détails de ce que j'utilise[#], j'ai voulu savoir un peu précisément comment il fonctionne (je sais ce que c'est qu'un code correcteur, bien sûr, mais je veux dire, savoir assez précisément comment les données sont organisées pour pouvoir reconstituer mes disques moi-même, ou aller y chercher n'importe quelle donnée, si jamais Linux cessait d'exister dans un pouf de logique).

L'idée de base est la suivante : à part les métadonnées dont je n'ai pas cherché à savoir comment elles sont organisées, un tableau RAID divise chaque disque (ou partition) du tableau en chunks (également appelés stripes), qui font par défaut 512ko. Si on a N disques dont N−k de données et k de redondance, alors un ensemble de N chunks au même emplacement sur chacun des disques s'appelle une stride, et une stride porte donc N−k chunks de données plus k chunks de redondance. Sur N−k disques (différents pour chaque chunk, comme je vais l'expliquer), les chunks contiennent les données de la stride : ce sont ces disques-là qui seront normalement lus, sauf erreur signalée (quand un disque accepte de lire un bloc, on peut considérer que les données sont correctes, parce qu'il y a des sommes de contrôle au niveau du disque). Les k disques restants contiennent des syndromes de contrôle, calculés octet par octet à partir des N−k chunks de données de la stride. Si j'écarte le RAID0, qui n'a aucune redondance, et le RAID1 qui pour lequel tous les disques sont de toute façon identiques, il reste uniquement k=1 pour le RAID5 et k=2 pour le RAID6. Pour le RAID5, la somme de contrôle s'appelle P, ou chunk de parité, et pour RAID6, les deux sommes de contrôle s'appellent P (la même que pour RAID5) et Q.

L'organisation d'un tableau RAID6 de 4 disques (en mode left-symmetric, le mode par défaut) ressemble à ceci, où chaque ligne représente une stride, chaque colonne un disque (ou partition) et chaque case un chunk :

	Disque 0	Disque 1	Disque 2	Disque 3
Stride 0	Q	D0	D1	P
Stride 1	D2	D3	P	Q
Stride 2	D5	P	Q	D4
Stride 3	P	Q	D6	D7
Stride 4	Q	D8	D9	P
Stride 5	D10	D11	P	Q
(etc., cycliquement)

Ici, D indique un chunk de données, P et Q des chunks de syndrome pour la stride. En l'absence d'erreur, les données se lisent donc en prenant le chunk 0 du disque 1 (ce qui donne D₀, le premier chunk de données), puis le chunk 0 du disque 2 (ce qui donne D₀), puis le 1 du disque 0 (D₂), puis le 1 du disque 1 (D₃), puis le 2 du disque 3 (D₄) et le 2 du disque 0 (D₅), et ainsi de suite, comme indiqué par ce tableau. Le rôle des disques est permuté cycliquement à chaque stride, ce qui assure qu'ils jouent tous le même rôle, et qu'il n'y en a pas un qui s'use prématurément (contraster avec RAID4, qui isole un disque uniquement pour la parité) ; la stride 0 attribue le syndrome Q au disque 0 et le syndrome P au dernier disque et les données aux autres disques dans l'ordre, et ensuite on décale cycliquement en décrémentant les numéros des disques. Pour du RAID5 on aurait une organisation semblable à ceci près qu'il n'y a pas de Q, donc la première stride attribue le syndrome P au dernier disque et les données aux autres, et la rotation se fait pareil (je parle toujours pour le mode mode left-symmetric : vous aurez sans doute deviné que right-symmetric tourne dans l'autre sens).

Le syndrome P est très facile à calculer : c'est simplement le XOR de tous les octets de données correspondants (c'est-à-dire que chaque octet d'un chunk P est le XOR des octets numérotés de la même manière dans chacun des chunks D de la même ligne) ; le syndrome Q, lui, est une combinaison linéaire des octets de données calculée dans le corps 𝔽₂₅₆ à 256 éléments, dont les coefficients sont g⁰, g¹, g², etc., où g est un élément primitif de 𝔽₂₅₆ et l'exposant est donné par le numéro du chunk de données à l'intérieur de la stride. Si je reprends le tableau précédent indiquant l'organisation du RAID6 sur 4 disques, ça fait :

	Disque 0	Disque 1	Disque 2	Disque 3
Stride 0	D0⊕2⊛D1	D0	D1	D0⊕D1
Stride 1	D2	D3	D2⊕D3	D2⊕2⊛D3
Stride 2	D5	D4⊕D5	D4⊕2⊛D5	D4
Stride 3	D6⊕D7	D6⊕2⊛D7	D6	D7
Stride 4	D8⊕2⊛D9	D8	D9	D8⊕D9
Stride 5	D10	D11	D10⊕D11	D10⊕2⊛D11
(etc., cycliquement)

J'ai noté ⊕ pour le XOR, qui est l'addition dans 𝔽₂₅₆, et ⊛ pour la multiplication dans ce dernier, l'élément primitif étant g=2 avec une représentation de 𝔽₂₅₆ de façon habituelle modulo un polynôme irréductible. Voyez ce document (temporairement indisponible sur kernel.org alors vous pouvez le consulter ici sur le cache Google) pour les détails. Mais sur le cas très simple de 4 disques, on se persuade très facilement qu'en connaissant deux quelconques des nombres u, v, u⊕v et u⊕2⊛v, on retrouve toujours u et v.

Quel polynôme irréductible est choisi pour les calculs ? Le document précédent affirme que la représentation de 𝔽₂₅₆ choisie est celle de AES/Rijndael, c'est-à-dire modulo x⁸+x⁴+x³+x²+1. J'ai sauté en l'air en voyant ça, parce que je sais très bien, pour faire faire ce genre d'exercice à mes étudiants, que le polynôme utilisé par AES/Rijndael n'est pas primitif (je veux dire, la classe de l'indéterminée modulo le polynôme, i.e., l'élément codé par 0x02, n'est pas d'ordre multiplicatif 255, mais 51). Du coup, ça voudrait dire que le RAID6 de Linux ne marche plus au-delà de 51 disques de données (ou du moins, ne peut pas corriger toutes les combinaisons de deux disques défaillants).

Heureusement, le polynôme d'AES/Rijndael est, en fait, x⁸+x⁴+x³+x+1, et c'est la première affirmation qui est fausse, la seconde est correcte, le RAID6 de Linux utilise bien x⁸+x⁴+x³+x²+1, qui est primitif, donc RAID6 marche comme annoncé (enfin, au moins mathématiquement — je n'ai pas 54 disques sous la main pour tester). M'enfin, ça reste une erreur et un sale coup du Club Contexte, d'avoir écrit ça. Et potentiellement dangereuse, si quelqu'un se précipite pour utiliser des implémentations matérielles optimisées des opérations AES afin d'accélérer le RAID6 ! J'ai écrit à Peter Anvin, qui a reconnu l'erreur (il avait bien remarqué que x⁸+x⁴+x³+x+1 n'était pas primitif et a cru à une faute de frappe, choisissant donc involontairement un polynôme non-standard) et m'a promis de la corriger.

Concrètement, donc, pour le choix x⁸+x⁴+x³+x²+1, calculer 2⊛v pour un octet v se fait en calculant soit 2v (la multiplication usuelle) soit 2v⊕0x11d, lequel des deux est inférieur à 256. Ceci, parce que 0x11d est le nombre 2⁸+2⁴+2³+2²+1.

Vérification concrète sur un de mes tableaux RAID6 : les 32 premiers octets de chacun des quatre disques du tableau sont :

/dev/sdc20
00000000  aa 98 b9 a6 40 e0 da c2  c6 ca 5c 14 ad c0 ae e8  |....@.....\.....|
00000010  40 e8 d0 f2 40 ee c2 f2  40 ee d0 d2 c6 d0 40 e6  |@...@...@.....@.|
/dev/sda20
00000000  58 46 53 42 00 00 10 00  00 00 00 00 03 10 6c 00  |XFSB..........l.|
00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
/dev/sdd20
00000000  79 6f 75 72 20 70 65 61  63 65 2e 0a 57 68 61 74  |your peace..What|
00000010  20 74 68 79 20 77 61 79  20 77 68 69 63 68 20 73  | thy way which s|
/dev/sdb20
00000000  21 29 26 30 20 70 75 61  63 65 2e 0a 54 78 0d 74  |!)&0 puace..Tx.t|
00000010  20 74 68 79 20 77 61 79  20 77 68 69 63 68 20 73  | thy way which s|

Visiblement, le disque 1 (/dev/sda20, ne me demandez pas comment ils se sont retrouvés dans cet ordre dans le tableau) contient le début D₀ des données (il s'agit d'un filesystem XFS, donc ça commence par XFSB), et le disque 2 (/dev/sdd20) contient aussi un chunk de données (D₁, un bout d'un fichier[#2]). Le disque 3 (/dev/sdb20) contient le XOR de ces deux chunks, P=D₀⊕D₁, ce qui est assez visible puisque comme D₀ contient beaucoup de 0, sur ces octets-là il s'agit de la même chose que D₁. Et enfin le disque 0 (/dev/sdc20) contient Q=D₀⊕2⊛D₁, ce qui comme D₁ ne contient que des octets ASCII (donc <0x80), vaut en fait D₀⊕2D₁, et ça se voit par exemple au fait que beaucoup d'espaces (0x20) dans D₁ deviennent des arrobas (0x40) dans Q (lorsque D₀ contient 0). Ici, rien ne permet de vérifier qu'on a le bon polynôme. En revanche, si je considère la stride 2 (à l'offset 0x80000 parce que j'utilise des chunks de 256ko),

/dev/sdc20
00080000  f6 2a 28 86 e1 68 a8 fe  b3 63 2c 2d 26 a8 22 f8  |.*(..h...c,-&.".|
00080010  f2 13 c6 e4 9a 7c 55 3f  25 bf 75 48 7a db f7 8e  |.....|U?%.uHz...|
/dev/sda20
00080000  09 d5 d7 79 1e 97 57 01  4c 9c d3 d2 d9 57 dd 07  |...y..W.L....W..|
00080010  0d ec 39 1b 65 83 aa c0  da 05 0d 37 85 24 08 71  |..9.e......7.$.q|
/dev/sdd20
00080000  0e ab af ee 20 2f b2 1e  84 39 a7 a5 b3 b2 bb 12  |.... /...9......|
00080010  06 d9 6e 2a d6 07 55 81  b5 d9 92 ef 0b 54 0c fe  |..n*..U......T..|
/dev/sdb20
00080000  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00080010  ff ff ff ff ff ff ff ff  ff ba 78 7f ff ff ff ff  |..........x.....|

— cette fois on peut faire le calcul : sur le premier octet, par exemple, D₄ contient 0xff, D₅ contient 0xf6, on vérifie que P contient 0xff⊕0xf6=0x09, et comme Q doit contenir 0xff⊕2⊛0xf6=0x0e, c'est que 2⊛0xf6=0xf1 et comme 2×0xf6=0x1ec, le polynôme utilisé est représenté par 0x1ec⊕0xf1=0x11d, comme je l'annonçais (et ce n'est pas le polynôme de AES/Rijndael).

À ce stade-là, je m'estime satisfait dans le fait que j'ai compris comment les choses fonctionnent.

[#] En fait, cette affirmation est parfaitement fausse : en général, quand je regarde comment quelque chose fonctionne, surtout en informatique, je suis tellement dégoûté par ce que je découvre que je n'ose plus m'en servir.

[#2] Si vous voulez tout savoir, ce fichier contient des phrases complètement dénuées de sens dans un style assez pompeux : Jesus strong first whoredoms, where no bread along which is in your peace. What thy way which shall be killed. And when God. They are come to pass, the image with him: for thy mine eyes unto the Midian was the land whither the same there arose a man be fulfilled: But I spoken by you, and his tabernacle at the altar another: for the time of tempted in thing, the figunto thee: they believe it to them: but thou hast given me to be unto you the Shushan is with man's wife. Il s'agit du résultat du passage de dissociated press sur la bible du roi Jacques que j'avais fait il y a longtemps parce que je trouvais le résultat très amusant.