Salle 6

RAID-Z

Le RAID-5 classique garde une bande fixe sur ses disques : des données et la parité de ces données. Pour en changer un morceau, il doit écrire les nouvelles données et la nouvelle parité, sur place, en deux écritures distinctes. Une coupure de courant entre les deux laisse une bande dont la parité ne correspond plus aux données, et rien sur le disque ne le signale. Quand un disque meurt plus tard, son contenu est reconstruit à partir de cette parité : faux, sans un mot. C’est le trou d’écriture (write hole).

Une petite écriture coûte cher aussi : pour calculer la nouvelle parité, le RAID-5 doit d’abord lire le reste de la bande, ou les anciennes données et l’ancienne parité. RAID-Z ne fait ni l’un ni l’autre, parce qu’il ne met jamais une bande à jour : chaque bloc a sa propre bande, aussi large que le bloc l’exige.

1 Un bloc, une bande

Quand ZFS écrit un bloc sur un vdev raidz, vdev_raidz_map_alloc découpe ce bloc, et ce bloc seul, en colonnes, une par disque enfant. Les colonnes de parité viennent d’abord, P, puis Q et R pour raidz2 et raidz3 (3 au plus). Les colonnes de données suivent, chacune une suite contiguë du bloc : pas un secteur par disque à tour de rôle, comme on dessine souvent le RAID. Viennent enfin les secteurs de saut qui arrondissent l’allocation. Choisissez une taille, une parité, un nombre de disques et une taille de secteur : la carte et chaque nombre sont ceux que calcule le code.

Un bloc de 24 Kio : 6 secteurs de données, 4 secteurs de parité, 2 secteurs de saut, sur 6 des 6 colonnes. asize = 48 Kio, 2,00 fois psize.

s
⌈psize / 2ashift⌉ = ⌈24576 / 4096⌉ = 6 code
f
b % dcols = 0 % 6 = 0 code
o
b / dcols = 0 / 6 = 0 code
q
s / (dcols − nparity) = 6 / 4 = 1 code
r
s − q × 4 = 6 − 4 = 2 code
bc
r + nparity = 2 + 2 = 4 code
tot
s + nparity × (q + 1) = 6 + 2 × 2 = 10 code
acols
dcols = 6 code
scols
dcols = 6 code
rm_nskip
roundup(tot, 3) − tot = 12 − 10 = 2 code
asize
roundup(6 + 2 × ⌈6 / 4⌉, 3) = 12 × 4096 = 49152 (48 Kio) code
Version texte de cette figure

Un bloc de 24 Kio : 6 secteurs de données, 4 secteurs de parité, 2 secteurs de saut, sur 6 des 6 colonnes. asize = 48 Kio, 2,00 fois psize.

  1. Colonne 0, P, sur l’enfant 0 à partir du secteur 0 : 2 secteurs de parité.
  2. Colonne 1, Q, sur l’enfant 1 à partir du secteur 0 : 2 secteurs de parité.
  3. Colonne 2, D0, sur l’enfant 2 à partir du secteur 0 : secteurs 0 et 1 du bloc.
  4. Colonne 3, D1, sur l’enfant 3 à partir du secteur 0 : secteurs 2 et 3 du bloc.
  5. Colonne 4, D2, sur l’enfant 4 au secteur 0 : secteur 4 du bloc. Puis un secteur de saut, le secteur 1 de cet enfant.
  6. Colonne 5, D3, sur l’enfant 5 au secteur 0 : secteur 5 du bloc. Puis un secteur de saut, le secteur 1 de cet enfant.

2 Pas de trou d’écriture

La parité d’un bloc RAID-Z est calculée à partir de ses propres colonnes de données, et toutes les colonnes partent ensemble vers leurs disques : rien d’ancien n’est lu, rien d’ancien n’est réécrit. Le bloc va dans de l’espace libre, comme tout bloc dans ZFS (copie sur écriture), et l’ancienne version reste où elle était jusqu’à ce qu’un groupe de transactions qui n’en a plus besoin soit validé par une seule écriture d’uberblock (groupes de transactions). Une coupure de courant au milieu laisse une bande à moitié écrite que rien ne désigne.

Cette moitié de l’argument n’est pas dans vdev_raidz.c : RAID-Z écrit une bande entière, et la copie sur écriture et la validation du txg garantissent que personne ne la lit avant qu’elle soit entière.

RAID-5 : la bande est mise à jour sur place

  1. Avant : D1 fait partie d’une bande partagée avec D0 et D2 ; P est leur parité.

  2. Lire D0, D2 (ou l’ancien D1 et P), calculer P′, écrire D1′ par-dessus D1. Le courant est coupé avant l’écriture de P′.

  3. Au redémarrage, P ne correspond plus à D0, D1′, D2, et rien ne le signale. Quand le disque 0 meurt, D0 est reconstruit à partir de la mauvaise parité : du bruit, en silence.

RAID-Z : le nouveau bloc a une nouvelle bande

  1. Avant : le bloc (A0, A1 et leur parité PA) forme une bande à lui seul.

  2. La nouvelle version (B0, B1, PB) va dans de l’espace libre, en une bande à elle seule, sa parité calculée à partir d’elle seule. Le courant est coupé en pleine écriture : B1 n’arrive jamais.

  3. Au redémarrage, le dernier uberblock validé désigne toujours l’ancien bloc, intact. La bande à moitié écrite n’est désignée par rien : c’est de l’espace libre.

L’idée, à trois profondeurs

En une phrase

RAID-Z ne met jamais une bande à jour : chaque bloc est écrit dans de l’espace libre comme une bande à lui seul, données et parité ensemble, et la somme de contrôle de son parent dit quel disque ment quand on relit le bloc.

En un paragraphe

Un vdev raidz de n enfants avec p parités est un seul espace d’adresses, entrelacé secteur par secteur sur les enfants. Un bloc de s secteurs y commence quelque part et occupe ⌈s / (n − p)⌉ rangées : ses données dans des colonnes qui contiennent chacune une suite contiguë du bloc, et p colonnes de parité aussi longues que la plus longue colonne de données. Un petit bloc n’utilise que les colonnes dont il a besoin : un secteur de données coûte toujours p + 1 secteurs, quelle que soit la largeur. Chaque allocation est arrondie à un multiple de p + 1 secteurs, la taille du plus petit bloc. À la lecture, ZFS ne lit que les colonnes de données et les vérifie contre la somme de contrôle du pointeur de bloc parent. Si elle échoue et qu’aucun disque n’a signalé d’erreur, ZFS lit tout et essaie, une combinaison après l’autre, quels disques ne pas croire, jusqu’à ce que la somme de contrôle soit vérifiée ; puis il réécrit la colonne fausse.

En détail

Découper le bloc. Quand l’entrée-sortie atteint le vdev raidz, sa taille a été complétée jusqu’à un secteur entier.

vdev_raidz_map_alloc Extrait de module/zfs/vdev_raidz.c, lignes 615–649, OpenZFS zfs-2.4.4. Voir sur GitHub
	raidz_row_t *rr;
	/* The starting RAIDZ (parent) vdev sector of the block. */
	uint64_t b = zio->io_offset >> ashift;
	/* The zio's size in units of the vdev's minimum sector size. */
	uint64_t s = zio->io_size >> ashift;
	/* The first column for this stripe. */
	uint64_t f = b % dcols;
	/* The starting byte offset on each child vdev. */
	uint64_t o = (b / dcols) << ashift;
	uint64_t acols, scols;

	raidz_map_t *rm =
	    kmem_zalloc(offsetof(raidz_map_t, rm_row[1]), KM_SLEEP);
	rm->rm_nrows = 1;

	/*
	 * "Quotient": The number of data sectors for this stripe on all but
	 * the "big column" child vdevs that also contain "remainder" data.
	 */
	uint64_t q = s / (dcols - nparity);

	/*
	 * "Remainder": The number of partial stripe data sectors in this I/O.
	 * This will add a sector to some, but not all, child vdevs.
	 */
	uint64_t r = s - q * (dcols - nparity);

	/* The number of "big columns" - those which contain remainder data. */
	uint64_t bc = (r == 0 ? 0 : r + nparity);

	/*
	 * The total number of data and parity sectors associated with
	 * this I/O.
	 */
	uint64_t tot = s + nparity * (q + (r == 0 ? 0 : 1));
  1. L617–L623 Tout est en secteurs de 1 << ashift. b est l’endroit où le bloc commence sur le vdev, s sa taille. Le secteur b du vdev est sur l’enfant b % dcols, au secteur b / dcols de cet enfant.
  2. L628 Une rangée : sur un raidz qui n’est pas en cours d’extension, le bloc entier forme une seule bande.
  3. L634–L643 q rangées pleines de données, r secteurs restants. Les bc « grandes colonnes » ont un secteur de plus : les r colonnes de données qui portent le reste, et les colonnes de parité, qui doivent être aussi longues que la plus longue colonne de données.
  4. L649 tot : données plus parité, les secteurs réellement écrits.

Placer les colonnes. La même fonction donne ensuite à chaque colonne son enfant, son décalage et sa taille.

vdev_raidz_map_alloc Extrait de module/zfs/vdev_raidz.c, lignes 677–700, OpenZFS zfs-2.4.4. Voir sur GitHub
	for (uint64_t c = 0; c < scols; c++) {
		raidz_col_t *rc = &rr->rr_col[c];
		uint64_t col = f + c;
		uint64_t coff = o;
		if (col >= dcols) {
			col -= dcols;
			coff += 1ULL << ashift;
		}
		rc->rc_devidx = col;
		rc->rc_offset = coff;

		if (c >= acols)
			rc->rc_size = 0;
		else if (c < bc)
			rc->rc_size = (q + 1) << ashift;
		else
			rc->rc_size = q << ashift;

		asize += rc->rc_size;
	}

	ASSERT3U(asize, ==, tot << ashift);
	rm->rm_nskip = roundup(tot, nparity + 1) - tot;
	rm->rm_skipstart = bc;
  1. L679–L686 La colonne c est sur l’enfant f + c. Après le dernier enfant, elle repart de l’enfant 0, un secteur plus bas : le bloc est une suite de secteurs consécutifs de l’espace d’adresses du vdev.
  2. L688–L693 Une colonne au-delà d’acols ne porte pas de données (un bloc plus étroit que le vdev) ; les bc premières colonnes ont q + 1 secteurs, les autres q.
  3. L699–L700 Le bourrage : roundup(tot, nparity + 1) - tot secteurs de saut, à partir de la colonne bc. Où ils tombent : un après chaque colonne courte, en revenant sur les colonnes de parité si la bande manque de colonnes. Ils sont écrits à zéro, dans la même entrée-sortie que leur colonne, ou dans une entrée-sortie facultative à part pour une colonne sans données, pour que la file du disque puisse fusionner des écritures contiguës.

Ce que l’allocateur réserve. La carte écrit tot secteurs ; l’allocateur a déjà réservé la taille arrondie, calculée à partir de la seule taille.

vdev_raidz_psize_to_asize Extrait de module/zfs/vdev_raidz.c, lignes 2305–2317, OpenZFS zfs-2.4.4. Voir sur GitHub
static uint64_t
vdev_raidz_psize_to_asize(vdev_t *vd, uint64_t psize, uint64_t txg)
{
	vdev_raidz_t *vdrz = vd->vdev_tsd;
	uint64_t asize;
	uint64_t ashift = vd->vdev_top->vdev_ashift;
	uint64_t nparity = vdrz->vd_nparity;

	uint64_t cols = vdev_raidz_get_logical_width(vdrz, txg);

	asize = ((psize - 1) >> ashift) + 1;
	asize += nparity * ((asize + cols - nparity - 1) / (cols - nparity));
	asize = roundup(asize, nparity + 1) << ashift;
  1. L2315 Secteurs de données : psize arrondi au secteur.
  2. L2316 Plus nparity secteurs de parité pour chaque rangée de cols - nparity secteurs de données entamée.
  3. L2317 Arrondi à un multiple de nparity + 1. Sur un raidz2 de 12 disques à secteurs de 4 Kio, un bloc de 4 Kio prend 12 Kio, un bloc de 8 Kio 24 Kio (deux secteurs de saut), un bloc de 40 Kio 48 Kio : la figure calcule tous les autres.

En raidz1, la colonne de parité et la première colonne de données échangent leurs enfants un mégaoctet sur deux du vdev, pour que la parité ne soit pas toujours sur le même disque ; le commentaire juge le gain douteux, mais le format sur disque doit le garder pour toujours. Mettez le premier secteur b à 256 avec des secteurs de 4 Kio pour le voir.

Relire le bloc. Une lecture ordinaire ne demande que les colonnes de données ; la parité est lue quand un disque manque, ou par un scrub ou un resilver. Le bloc est réassemblé et vérifié contre la somme de contrôle de son pointeur de bloc parent. Un disque absent est une erreur que ZFS connaît : sa colonne de données est reconstruite à partir de la première colonne de parité encore valide, P avant Q avant R (le choix). Mais un disque peut aussi renvoyer de faux octets en annonçant un succès. La somme de contrôle échoue alors, et aucun disque n’est en cause. ZFS lit toutes les colonnes et appelle vdev_raidz_combrec.

vdev_raidz_combrec Extrait de module/zfs/vdev_raidz.c, lignes 3523–3558, OpenZFS zfs-2.4.4. Voir sur GitHub
	for (int num_failures = 1; num_failures <= nparity; num_failures++) {
		int tstore[VDEV_RAIDZ_MAXPARITY + 2];
		int *ltgts = &tstore[1]; /* value is logical child ID */


		/*
		 * Determine number of logical children, n.  See comment
		 * above raidz_simulate_failure().
		 */
		int n = 0;
		for (int w = physical_width;
		    w >= original_width; w--) {
			n += w;
		}

		ASSERT3U(num_failures, <=, nparity);
		ASSERT3U(num_failures, <=, VDEV_RAIDZ_MAXPARITY);

		/* Handle corner cases in combrec logic */
		ltgts[-1] = -1;
		for (int i = 0; i < num_failures; i++) {
			ltgts[i] = i;
		}
		ltgts[num_failures] = n;

		for (;;) {
			int err = raidz_reconstruct(zio, ltgts, num_failures,
			    nparity);
			if (err == EINVAL) {
				/*
				 * Reconstruction not possible with this #
				 * failures; try more failures.
				 */
				break;
			} else if (err == 0)
				return (0);
  1. L3523 Supposer qu’un disque ment, puis deux, jusqu’à nparity.
  2. L3532–L3536 n enfants logiques. Sans extension, c’est le nombre de disques, et l’enfant logique i est le disque i.
  3. L3542–L3546 La première combinaison, les disques 0 à num_failures - 1 ; la boucle qui suit cet extrait parcourt les autres dans l’ordre que donne le commentaire au-dessus de la fonction.
  4. L3549–L3558 raidz_reconstruct tient ces disques pour morts, reconstruit leurs colonnes de données à partir de la parité et redemande la somme de contrôle. EINVAL : avec les erreurs déjà connues, plus de colonnes mortes que de parités ; essayer davantage de pannes. 0 : la somme de contrôle est vérifiée.

La somme de contrôle est l’oracle. La parité seule peut reconstruire une colonne que ZFS sait absente, mais elle ne peut pas dire laquelle des colonnes qu’elle a sous la main ment ; la somme de contrôle, rangée un niveau plus haut dans l’arbre, le peut. Quand une combinaison est vérifiée, ses colonnes de données sont marquées en erreur de somme de contrôle, la parité lue mais pas utilisée est régénérée et comparée, et les bonnes données sont réécrites dans chaque colonne trouvée fausse. Un disque qui renvoie une parité fausse n’est pas pris par une lecture ordinaire, qui ne lit pas la parité ; un scrub lit toutes les colonnes. Avec plus de disques absents que de parités, le vdev ne peut pas être ouvert ; avec un à nparity, il est dégradé.

Resilver. Quand un disque revient après avoir manqué des écritures, ZFS ne recopie pas le disque entier. Un resilver parcourt l’arbre des pointeurs de bloc, bloc indirect par bloc indirect, et visite chaque bloc. Il saute les blocs nés hors de l’intervalle de txg qu’un disque a manqués, puis demande au vdev si ce bloc touche un tel disque.

vdev_raidz_need_resilver Extrait de module/zfs/vdev_raidz.c, lignes 4011–4037, OpenZFS zfs-2.4.4. Voir sur GitHub
	uint64_t s = ((psize - 1) >> ashift) + 1;
	/* The first column for this stripe. */
	uint64_t f = b % dcols;

	/* Unreachable by sequential resilver. */
	ASSERT3U(phys_birth, !=, TXG_UNKNOWN);

	if (!vdev_dtl_contains(vd, DTL_PARTIAL, phys_birth, 1))
		return (B_FALSE);

	if (s + nparity >= dcols)
		return (B_TRUE);

	for (uint64_t c = 0; c < s + nparity; c++) {
		uint64_t devidx = (f + c) % dcols;
		vdev_t *cvd = vd->vdev_child[devidx];

		/*
		 * dsl_scan_need_resilver() already checked vd with
		 * vdev_dtl_contains(). So here just check cvd with
		 * vdev_dtl_empty(), cheaper and a good approximation.
		 */
		if (!vdev_dtl_empty(cvd, DTL_PARTIAL))
			return (B_TRUE);
	}

	return (B_FALSE);
  1. L4018–L4019 Le bloc n’est pas né pendant qu’un disque manquait des écritures : rien à faire.
  2. L4021–L4022 Un bloc qui a au moins autant de colonnes que de disques les touche tous.
  3. L4024–L4035 Sinon, seulement si l’un des s + nparity disques à partir de la première colonne a manqué des écritures. Dans la figure, déclarez un disque absent et lisez : le résultat dit si un resilver réécrirait ce bloc.

Ce que la figure laisse de côté

La figure fait tourner l’arithmétique de vdev_raidz_map_alloc et de vdev_raidz_psize_to_asize telle que le code l’écrit : chaque carte et chaque nombre sont ceux du code. La lecture suit les décisions du code (quelles colonnes sont lues, quelle parité reconstruit quoi, l’ordre des combinaisons, ce qui est réécrit), mais ne suit que si chaque colonne est juste ou fausse, pas ses octets : une reconstruction est juste exactement quand toutes les colonnes qu’elle lit sont justes. Elle laisse de côté les disques qui ont manqué des écritures (lus comme périmés, pas absents), les disques lents écartés exprès, les blocs gang, le chemin du scrub et dRAID. Les blocs sont limités à 128 Kio et 16 disques pour que la carte reste lisible. L’extension RAIDZ, qui ajoute un disque à un raidz existant et donne aux blocs plus anciens des cartes de plusieurs rangées, sera pour une autre fois.