RAID — levels 0, 1, 5, 6, 10 — trade-offs: Visual walkthrough

4.2.39 · D2 · Coding › Operating Systems › RAID — levels 0, 1, 5, 6, 10 — trade-offs

Poore page mein hum sirf ek hi tool use karenge: ek operation jiska naam hai XOR. To shuru karte hain waheen se.

Step 1 — XOR se milte hain, "kya dono alag hain?" wala switch

KYA HAI. Kisi bhi disk se pehle, hum woh single operation define karte hain jis par yeh poora page tika hua hai. Ise $\oplus$ likhte hain (ek circle ke andar plus). Yeh do bits leta hai — bit bas ek $0$ ya $1$ hoti hai — aur ek bit output karta hai. Rule yeh hai: agar dono inputs alag hon to output $1$ , agar same hon to output $0$ .

0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0

Yahaan $\oplus$ operation hai; left side par har $0$ aur $1$ ek input bit hai; right side par har result output bit hai. Yahi poori definition hai — kuch bhi hidden nahi hai.

YEH TOOL KYU, addition kyun nahi? Ordinary addition se $1 + 1 = 2$ aata, jo ek bit nahi hai — overflow ho jaata. Hume ek aisi operation chahiye jo ${0, 1}$ ke andar rahe aur undo bhi ho sake. XOR dono kaam karta hai. (Yahi $\oplus$ aapne XOR and Boolean Algebra mein dekha tha.)

PICTURE. Truth table ko ek light-switch ki tarah socho: same inputs → light off ( $0$ ), alag inputs → light on ( $1$ ).

Step 2 — Woh do properties jo magic possible banati hain

KYA HAI. Step 1 ki table se do facts padh lo. Neeche har symbol ek single bit hai.

ek bit khud se x \oplus x = 0, ek bit zero se x \oplus 0 = x

$x \oplus x = 0$ : koi value khud se XOR ho to vanish ho jaati hai — kyunki koi cheez khud se kabhi alag nahi hoti, to switch off rehta hai.
$x \oplus 0 = x$ : koi value $0$ se XOR ho to unchanged rehti hai — kyunki $0$ wahaan agree karta hai jahan $x$ $0$ hai aur differ karta hai jahan $x$ $1$ hai, to exactly $x$ bach jaata hai.

Do aur bookkeeping facts, seedhe table se:

Commutative: $a \oplus b = b \oplus a$ (order matter nahi karta).
Associative: $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ (grouping matter nahi karta).

YEH KYU COLLECT KAR RAHE HAIN. Yahi chaar rules hain jo hum algebra mein use karenge. "Khud se vanish hona" woh trick hai jo ek lost disk recover karti hai; "commutative + associative" woh cheez hai jo hume terms freely shuffle karne deti hai taaki cancellation ho sake.

PICTURE. Do bits milte hain: identical pair → $0$ mein annihilate ho jaate hain; koi bhi cheez $0$ se milti hai → untouched pass ho jaati hai.

Step 3 — Disks set karo aur parity block $P$ banao

KYA HAI. Ab disks. $n$ disks ko side by side picture karo. Ek stripe par (sabhi disks ke across ek horizontal row) hum data blocks $D_{1}, D_{2}, \dots, D_{n - 1}$ store karte hain — ek per disk — aur aakhri disk ek computed parity block $P$ ke liye reserve karte hain. Har $D_{i}$ bas bits ki ek string hai jo disk $i$ par rehti hai. Hum define karte hain:

P = disk 1 ka data D_{1} \oplus disk 2 ka data D_{2} \oplus \dots \oplus aakhri data disk D_{n - 1}

Left to right padho: pehle do data blocks ko XOR karo, phir teesre ko us running result mein XOR karo, aur aise hi aage. $P$ final running total hai — woh "summary number" jo parent note ki Feynman story mein magic bola gaya tha.

IS TARAH DEFINE KYUN KAREIN? Step 2 ki wajah se, yeh single block secretly har $D_{i}$ ko is tarah "yaad rakhta" hai ki hum usse wapas peel kar sakte hain. Hum kisi bhi disk ki copy store nahi kar rahe — $P$ us se chhota hai ( $n - 1$ nahi, sirf ek block) — phir bhi yeh itna kafi rakhta hai ki koi ek lost block reconstruct ho sake. Yahi RAID 5 ki poori economy hai.

PICTURE. Ek stripe: data blocks ek XOR gate mein flow ho rahe hain, bahar aata hai parity block apne dedicated cell par.

Step 4 — Ek disk mar gayi: rescue set karo

KYA HAI. Maano disk $k$ fail ho gayi, to $D_{k}$ gone hai. Hamare paas abhi bhi baaki sabhi data blocks aur $P$ hain. Jo bhi hamare paas bacha hai usse collect karo aur sab XOR karo:

R = k se pehle ke survivors D_{1} \oplus \dots \oplus D_{k - 1} \oplus k ke baad ke survivors D_{k + 1} \oplus \dots \oplus D_{n - 1} \oplus summary P

$R$ hamaara candidate rescue value hai — ise "jo bhi bacha, XORed" kaho. Humne abhi kuch prove nahi kiya; humne sirf jo survived woh gather kiya hai.

YAHAAN SE SHURU KYU KAREIN? XOR self-inverse hai (Step 2), to kisi mixture ko undo karne ka natural move hai dobara XOR karna. Hum survivors ko wapas $P$ mein throw karte hain umeed se ki woh apne apne contributions cancel kar denge aur sirf wala missing wala bachega.

PICTURE. Array mein ek greyed-out dead disk; arrows har surviving block aur $P$ ko ek single XOR machine mein kheench rahe hain.

Step 5 — Dekho survivors cancel hote hain, term by term

KYA HAI. Step 3 ki $P$ ki definition ko $R$ mein substitute karo. Ab har survivor do baar appear karta hai: ek baar khud ke roop mein, ek baar $P$ ke andar chhupa hua.

R = (D_{1} \oplus \dots \oplus D_{k - 1} \oplus D_{k + 1} \oplus \dots) \oplus (yeh hai P D_{1} \oplus D_{2} \oplus \dots \oplus D_{k} \oplus \dots \oplus D_{n - 1})

Ab commutative + associative (Step 2) use karo har survivor ko uske twin ke saath pair karne ke liye:

R = = 0 (D_{1} \oplus D_{1}) \oplus = 0 (D_{2} \oplus D_{2}) \oplus \dots \oplus koi twin nahi! D_{k} \oplus \dots

Har pair $D_{i} \oplus D_{i}$ $x \oplus x = 0$ se $0$ ban jaata hai. Sirf woh term jiska koi partner nahi hai woh hai $D_{k}$ — kyunki $D_{k}$ survivors mein kabhi nahi aaya, woh sirf $P$ ke andar rehta hai. Woh saare zeros $x \oplus 0 = x$ se pass ho jaate hain, aur jo bachta hai woh hai:

R = D_{k}

YEH KYU KAAM KARTA HAI. Yahi toh punchline hai: $P$ ne $D_{k}$ ka contribution apne andar carry kiya tha, aur $P$ ke against har doosre block ko XOR karne se $D_{k}$ ke siwa sab kuch erase ho gaya. Dead disk wapas aa gayi.

PICTURE. Ek cancellation ladder: har survivor apne ghost se $P$ ke andar pair karta hai, dono $0$ mein collapse ho jaate hain, aur $D_{k}$ akela spotlight mein khada reh jaata hai.

Step 6 — Concrete numbers (derivation, checked)

KYA HAI. Teen 4-bit blocks lo aur poori machine chalao.

$D_{1} = 1011, D_{2} = 0110, D_{3} = 1100$ .
$P$ banao (Step 3): pehle $1011 \oplus 0110 = 1101$ (har column XOR karo), phir $1101 \oplus 1100 = 0001$ . To $P = 0001$ .
Ab disk 2 mar jaati hai. Rescue (Step 5): $D_{2} = P \oplus D_{1} \oplus D_{3}$ .
- $0001 \oplus 1011 = 1010$ ,
- $1010 \oplus 1100 = 0110$ .
Result $0110$ — exactly original $D_{2}$ . ✓

NUMBERS KYU DIKHAYEIN. Algebra symbolic tha; yeh prove karta hai ki ghosts ek real stripe par actually cancel hote hain. Column-by-column, "alag?" rule lost data ko bina kisi guessing ke reproduce karta hai.

PICTURE. Chaar bit-strings coloured columns ki tarah stack ki gayi hain, XOR har column mein sweep kar raha hai, recovered $D_{2}$ original se match karte hue glow kar raha hai.

Step 7 — Edge case: parity ONE disk kyun fix karta hai, kabhi do nahi

KYA HAI. Agar do disks ek saath mar jayein — maano $D_{j}$ aur $D_{k}$ ? Rescue chalao: jo bhi hamare paas bacha hai sab XOR karo. Ab do terms ke koi twin nahi hain, to clean answer ki jagah hume milta hai:

R = D_{j} \oplus D_{k}

YEH DEAD END KYU HAI. Yeh ek equation hai do unknowns ke saath — jaise koi bole " $x + y = 5$ " aur pooche $x$ kya hai. Infinitely many $(D_{j}, D_{k})$ ek hi $R$ de sakte hain; parity unhe alag nahi kar sakta. Ek parity block = ek equation = sirf ek missing block ke liye solve kar sakte hain. Yahi exact reason hai ki RAID 5 sirf single failure survive karta hai.

RAID 6 ka fix (kyun ek doosra XOR help nahi karta). Ek aur plain XOR parity $P^{'}$ add karne se sirf $P^{'} = P$ milega — same equation dobara, useless. RAID 6 iske bajaye ek doosra, independent check compute karta hai $Q = ⨁_{i} g^{i} D_{i}$ , jahan $g^{i}$ ek Galois field $GF(2^8)$ se distinct nonzero multipliers hain. Kyunki har block alag-alag weight se hai, $P$ aur $Q$ do alag equations hain do unknowns mein — ab solvable. Do independent equations → do failures survivable.

PICTURE. Left: ek plane mein ek line (ek equation), unknown pair freely uspe slide karta hai — unsolvable. Right: do crossing lines (P aur Q) ek single point pin karte hain — solved.

Ek-picture summary

KYA HAI. Poora safar ek canvas par: $\oplus$ define karo → data ko $P$ mein fold karo → ek disk mar jaati hai → survivors ko $P$ ke against XOR karo → ghosts cancel hote hain → $D_{k}$ wapas aata hai; aur woh wall do failures par jahan ek equation do unknowns hold nahi kar sakta.

Recall Feynman: ek story ki tarah batao

Tum aur tumhare dost ek comic ki ek-ek page yaad karte ho. Ek extra dost ek "summary" yaad karta hai: har letter ke liye woh note karta hai ki kitne real pages par us jagah ink thi — odd ya even — woh odd/even flag hi XOR hai. Ab ek dost gayab ho jaata hai. Baki log apne pages padhte hain, summary-dost apne flags padhta hai, aur saath milkar woh exactly reconstruct kar sakte hain ki missing page par kya tha — kyunki summary mein pehle se missing page ka contribution "pata" tha, aur baaki sabke answers cancel out ho jaate hain, sirf gap bachta hai. Lekin agar do dost gayab ho jayein, to survivors aur ek summary sirf do missing pages ka combination bata sakte hain, har ek alag nahi — ek clue, do blanks. Isliye single parity (RAID 5) ek dost bachata hai, aur isliye tumhe ek doosri, cleverly different summary chahiye (RAID 6 ka $Q$ ) do bachane ke liye.

Active recall

XOR ka output

a \oplus b

kya hoga?

1

agar

a

aur

b

differ karein,

0

agar same hon.

Recovery ke dauran kaunsa XOR law ek survivor ko cancel karta hai?

x \oplus x = 0

— ek block

P

ke andar apni copy se XOR hoke vanish ho jaata hai.

Recovery proof mein

x \oplus 0 = x

kyun matter karta hai?

Saare cancelled pairs

0

ban jaate hain, aur

D_{k}

ko un zeros se XOR karne par

D_{k}

unchanged bachta hai.

Lost block

D_{k}

kaise rebuild karte hain?

D_{k} = P \oplus (XOR of all surviving data blocks)

Single parity sirf ek disk kyun recover kar sakta hai?

Do dead blocks se

R = D_{j} \oplus D_{k}

milta hai — ek equation, do unknowns, unsolvable.

Doosra XOR parity RAID 6 protection kyun nahi deta?

Doosra XOR pehli equation ke barabar hai; RAID 6 ek independent

GF (2^{8})

parity

Q

use karta hai taaki do equations do unknowns solve kar sakein.