Room 6

RAID-Z

Classic RAID-5 keeps a fixed stripe across its disks: some data and the parity of that data. To change one piece, it must write the new data and the new parity, in place, as two separate writes. A power failure between the two leaves a stripe whose parity no longer matches its data, and nothing on disk says so. When a disk later dies, its contents are rebuilt from that parity: wrong, without a word. This is the write hole.

A small write is costly too: to compute the new parity, RAID-5 must first read the rest of the stripe, or the old data and the old parity. RAID-Z does neither, because it never updates a stripe: every block gets a stripe of its own, as wide as the block needs.

1 One block, one stripe

When ZFS writes a block to a raidz vdev, vdev_raidz_map_alloc cuts that block, and that block alone, into columns, one per child disk. The parity columns come first, P, then Q and R for raidz2 and raidz3 (3 at most). The data columns follow, each one a contiguous run of the block: not one sector per disk in turn, as RAID is often drawn. Then come the skip sectors that round the allocation up. Pick a size, a parity, a number of disks and a sector size: the map and every number are what the code computes.

24 KiB block: 6 data sectors, 4 parity sectors, 2 skip sectors, on 6 of 6 columns. asize = 48 KiB, 2.00 times 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 KiB) code
Text version of this figure

24 KiB block: 6 data sectors, 4 parity sectors, 2 skip sectors, on 6 of 6 columns. asize = 48 KiB, 2.00 times psize.

  1. Column 0, P, on child 0 from sector 0: 2 parity sectors.
  2. Column 1, Q, on child 1 from sector 0: 2 parity sectors.
  3. Column 2, D0, on child 2 from sector 0: sectors 0 and 1 of the block.
  4. Column 3, D1, on child 3 from sector 0: sectors 2 and 3 of the block.
  5. Column 4, D2, on child 4 at sector 0: sector 4 of the block. Then one skip sector, sector 1 of that child.
  6. Column 5, D3, on child 5 at sector 0: sector 5 of the block. Then one skip sector, sector 1 of that child.

2 No write hole

The parity of a RAID-Z block is computed from its own data columns, and every column is sent to its disk at once: nothing old is read, nothing old is rewritten. The block goes to free space, as every block does in ZFS (copy-on-write), and the old version stays where it was until a transaction group that no longer needs it is committed by a single uberblock write (transaction groups). A power failure in the middle leaves a half-written stripe that nothing points to.

That half of the argument is not in vdev_raidz.c: RAID-Z writes a whole stripe, and copy-on-write and the txg commit make sure no one reads it before it is whole.

RAID-5: the stripe is updated in place

  1. Before: D1 is part of a stripe shared with D0 and D2; P is their parity.

  2. Read D0, D2 (or the old D1 and P), compute P′, write D1′ over D1. The power fails before P′ is written.

  3. After the reboot, P no longer matches D0, D1′, D2, and nothing says so. When disk 0 dies, D0 is rebuilt from the wrong parity: garbage, silently.

RAID-Z: the new block gets a new stripe

  1. Before: the block (A0, A1 and their parity PA) is one stripe of its own.

  2. The new version (B0, B1, PB) goes to free space as a stripe of its own, parity computed from it alone. The power fails mid-write: B1 never lands.

  3. After the reboot, the last committed uberblock still points to the old block, untouched. The half-written stripe is referenced by nothing: it is free space.

The idea, at three depths

In one sentence

RAID-Z never updates a stripe: each block is written to free space as a stripe of its own, data and parity together, and the checksum in its parent tells which disk is lying when the block is read back.

In one paragraph

A raidz vdev of n children with p parity is one address space, interleaved sector by sector across the children. A block of s sectors starts somewhere in it and takes ⌈s / (n − p)⌉ rows: its data in columns that each hold a contiguous run of the block, and p parity columns as long as the longest data column. A small block uses only as many columns as it needs: one sector of data always costs p + 1 sectors, whatever the width. Every allocation is rounded up to a multiple of p + 1 sectors, the size of the smallest block. On a read, ZFS reads the data columns only, and checks them against the checksum in the parent block pointer. If it fails and no disk reported an error, ZFS reads everything and tries, one combination after another, which disks to disbelieve, until the checksum verifies; then it rewrites the bad column.

In detail

Cutting the block. By the time the I/O reaches the raidz vdev, its size has been padded to a whole sector.

vdev_raidz_map_alloc Excerpt of module/zfs/vdev_raidz.c, lines 615–649, OpenZFS zfs-2.4.4. View on 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 Everything is in sectors of 1 << ashift. b is where the block starts on the vdev, s its size. Sector b of the vdev is on child b % dcols, at sector b / dcols of that child.
  2. L628 One row: on a raidz that is not being expanded, the whole block is one stripe.
  3. L634–L643 q full rows of data, r sectors left over. The bc “big columns” get one more sector: the r data columns that hold the remainder, and the parity columns, which must be as long as the longest data column.
  4. L649 tot: data plus parity, the sectors actually written.

Placing the columns. The same function then gives each column its child, its offset and its size.

vdev_raidz_map_alloc Excerpt of module/zfs/vdev_raidz.c, lines 677–700, OpenZFS zfs-2.4.4. View on 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 Column c is on child f + c. Past the last child it wraps to child 0, one sector further down: the block is a run of consecutive sectors of the vdev’s address space.
  2. L688–L693 A column past acols holds no data (a block narrower than the vdev); the first bc columns have q + 1 sectors, the others q.
  3. L699–L700 The padding: roundup(tot, nparity + 1) - tot skip sectors, from column bc on. Where they land: one after each short column, wrapping onto the parity columns if the stripe runs out of columns. They are written as zeros, in the same I/O as their column, or as an optional I/O of their own for a column with no data, so that the disk queue can merge contiguous writes.

What the allocator reserves. The map writes tot sectors; the allocator has already reserved the rounded-up size, computed from the size alone.

vdev_raidz_psize_to_asize Excerpt of module/zfs/vdev_raidz.c, lines 2305–2317, OpenZFS zfs-2.4.4. View on 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 Data sectors: psize rounded up to a sector.
  2. L2316 Plus nparity parity sectors for each row of cols - nparity data sectors that is started.
  3. L2317 Rounded up to a multiple of nparity + 1. On a raidz2 of 12 disks with 4 KiB sectors, a 4 KiB block takes 12 KiB, an 8 KiB block 24 KiB (two skip sectors), a 40 KiB block 48 KiB: the figure computes any other.

In raidz1, the parity column and the first data column swap children in every other megabyte of the vdev, so that parity is not always on the same disk; the comment there says the benefit is doubtful but the on-disk format must keep it forever. Set the first sector b to 256 with 4 KiB sectors to see it.

Reading it back. A normal read asks only for the data columns; parity is read when a disk is missing, or by a scrub or a resilver. The block is reassembled and checked against the checksum in its parent block pointer. A missing disk is an error ZFS knows about: its data column is rebuilt from the first parity column still valid, P before Q before R (the choice). But a disk can also return the wrong bytes and report success. Then the checksum fails and no disk is to blame. ZFS reads every column, and calls vdev_raidz_combrec.

vdev_raidz_combrec Excerpt of module/zfs/vdev_raidz.c, lines 3523–3558, OpenZFS zfs-2.4.4. View on 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 Suppose one disk is lying, then two, up to nparity.
  2. L3532–L3536 n logical children. Without expansion it is the number of disks, and logical child i is disk i.
  3. L3542–L3546 The first combination, disks 0 to num_failures - 1; the loop after this excerpt walks through the others in the order the comment above the function lists.
  4. L3549–L3558 raidz_reconstruct treats those disks as dead, rebuilds their data columns from parity and asks the checksum again. EINVAL: with the errors already known, more columns dead than parity; try more failures. 0: the checksum verifies.

The checksum is the oracle. Parity alone can rebuild a column ZFS knows to be missing, but it cannot say which of the columns it has is lying; the checksum, stored one level up in the tree, can. When a combination verifies, its data columns are marked as checksum errors, the parity that was read but not used is regenerated and compared, and the good data is written back to every column found wrong. A disk that returns bad parity is not caught by a normal read, which does not read parity; a scrub reads every column. With more missing disks than parity, the vdev cannot be opened; with one up to nparity, it is degraded.

Resilver. When a disk comes back after missing some writes, ZFS does not copy the whole disk. A resilver walks the tree of block pointers, indirect block by indirect block, and visits each block. It skips the blocks born outside the range of txgs that some disk missed, then asks the vdev whether this block touches such a disk.

vdev_raidz_need_resilver Excerpt of module/zfs/vdev_raidz.c, lines 4011–4037, OpenZFS zfs-2.4.4. View on 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 The block was not born while a disk was missing writes: nothing to do.
  2. L4021–L4022 A block with at least as many columns as disks touches them all.
  3. L4024–L4035 Otherwise, only if one of the s + nparity disks from the first column on missed writes. In the figure, set a disk to missing and read: the result says whether a resilver would rewrite this block.

What the figure leaves out

The figure runs the arithmetic of vdev_raidz_map_alloc and vdev_raidz_psize_to_asize as the code writes it, so every layout and every number is the code’s. The read follows the code’s decisions (which columns are read, which parity rebuilds what, the order of the combinations, what is written back), but tracks only whether each column is right or wrong, not its bytes: a rebuild is right exactly when every column it reads is right. It leaves out disks that missed writes (read as stale, not missing), slow disks skipped on purpose, gang blocks, the scrub path, and dRAID. Blocks are limited to 128 KiB and 16 disks so the map stays legible. RAID-Z expansion, which adds a disk to an existing raidz and gives older blocks maps of several rows, is left for another time.