CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 4 of 6 · 5 min read

Parity in code

Think of a recipe that needs one more step to double-check the answer. You add all the numbers a second way, and if the totals differ, you know that you erred. The analogy stops in one place: the check here also tells you which number to rebuild, because you know which disk is gone.

In plain words: The program below builds an array of four disks, three for data and one for parity, with three stripes of four bytes. It removes disk 1, rebuilds it from the other three, and checks the result. It then does a small write: it changes one data block and updates the parity without reading the other data disks.

A worked example. The new parity of a small write is the old parity XOR the old data XOR the new data. This needs two reads (old data, old parity) and two writes (new data, new parity), so one logical write costs four disk operations. This is the small-write penalty of RAID 5. A write of a full stripe needs no reads, because the new parity comes from the new data.

The key lines.

#include <stdio.h>
#include <string.h>

#define DISKS 4        /* 3 data blocks and 1 parity block in each stripe */
#define STRIPES 3
#define BLK 4          /* bytes per block, small to print */

static unsigned char d[DISKS][STRIPES][BLK];

static void parity_of(int s, unsigned char *out) {         /* parity = XOR of the data blocks */
    memset(out, 0, BLK);
    for (int k = 0; k < DISKS - 1; k++)
        for (int i = 0; i < BLK; i++) out[i] ^= d[k][s][i];
}

static void show(const char *title) {
    printf("%s\n", title);
    for (int s = 0; s < STRIPES; s++) {
        printf("  stripe %d:", s);
        for (int k = 0; k < DISKS; k++) {
            printf(" [");
            for (int i = 0; i < BLK; i++) printf("%02x", d[k][s][i]);
            printf("]");
        }
        printf("\n");
    }
}

int main(void) {
    for (int k = 0; k < DISKS - 1; k++)                      /* fill the data disks */
        for (int s = 0; s < STRIPES; s++)
            for (int i = 0; i < BLK; i++) d[k][s][i] = (unsigned char)(17 * k + 5 * s + 3 * i + 1);
    for (int s = 0; s < STRIPES; s++) parity_of(s, d[DISKS - 1][s]);
    show("healthy array (disks 0-2 data, disk 3 parity):");

    unsigned char lost[STRIPES][BLK];                        /* disk 1 fails */
    memcpy(lost, d[1], sizeof lost); memset(d[1], 0, sizeof d[1]);
    for (int s = 0; s < STRIPES; s++) {                      /* rebuild: XOR of all survivors */
        for (int i = 0; i < BLK; i++) {
            unsigned char x = 0;
            for (int k = 0; k < DISKS; k++) if (k != 1) x ^= d[k][s][i];
            d[1][s][i] = x;
        }
    }
    printf("rebuilt disk 1 %s the lost data\n", memcmp(lost, d[1], sizeof lost) == 0 ? "matches" : "DIFFERS from");

    /* small write: new parity = old parity XOR old data XOR new data (2 reads, 2 writes) */
    unsigned char newdata[BLK] = {0xde, 0xad, 0xbe, 0xef}, np[BLK];
    for (int i = 0; i < BLK; i++) np[i] = d[3][0][i] ^ d[0][0][i] ^ newdata[i];
    memcpy(d[0][0], newdata, BLK); memcpy(d[3][0], np, BLK);
    unsigned char full[BLK]; parity_of(0, full);
    printf("small-write parity %s the full recomputation\n", memcmp(full, d[3][0], BLK) == 0 ? "equals" : "differs from");
    return 0;
}

Output on the test machine:

healthy array (disks 0-2 data, disk 3 parity):
  stripe 0: [0104070a] [1215181b] [2326292c] [3037363d]
  stripe 1: [06090c0f] [171a1d20] [282b2e31] [39383f1e]
  stripe 2: [0b0e1114] [1c1f2225] [2d303336] [3a210007]
rebuilt disk 1 matches the lost data
small-write parity equals the full recomputation

The first byte of stripe 0 can be checked by hand: 0x01 XOR 0x12 XOR 0x23 = 0x30, which is the first byte of the parity block.

Small-write penalty

The small-write penalty is the extra work that a parity RAID does when a write covers less than a full stripe. It must read the old data and the old parity, and write the new data and the new parity, so it does four disk operations for one logical write.

Example: a 4 KiB overwrite in RAID 5 causes two reads and two writes.

Check yourself: 1. Why does the rebuild use all the surviving disks? 2. How many disk operations does a small write need in RAID 5? 3. Why does a full-stripe write avoid the penalty?