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

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

Shuru karne se pehle, ek reminder us notation ka jo hum baar baar use karenge, taaki koi bhi symbol unexplained na rahe:

Definition Is page pe use hone wale symbols

$n$ ::: array mein physical disks ki total number.
$D_{i}$ ::: stripe mein $i$ -vaa data block (tumhari file ke bytes ka ek chunk jo disk $i$ pe rehta hai).
$P$ ::: parity block — ek computed check value, tumhara data nahi.
$Q$ ::: doosra parity block (sirf RAID 6 mein), alag tarike se compute kiya gaya taaki nai information mile.
$\oplus$ ::: XOR — bit-by-bit "kya yeh do bits alag hain?". Iska ek magic law: $x \oplus x = 0$ aur $x \oplus 0 = x$ .
I/O ::: ek physical disk pe ek block ka ek read ya ek write.
redundancy ::: tumhare data ki single copy se zyada stored information (ek copy ya ek parity block), taaki ek khoyi hui disk ko rebuild kiya ja sake. RAID 0 har block ki exactly ek copy store karta hai lekin koi redundancy nahi — copy count aur redundancy alag cheezein hain.
RAID 0+1 ::: RAID 10 ka ulta-order cousin — tum pehle stripe karte ho (RAID 0) aur phir poori stripe ko mirror karte ho (RAID 1). RAID 10 ke jaisi hi disks aur jaisi hi 50% capacity, lekin alag failure behaviour (dekho L4·Q3). RAID 10 hai mirror-then-stripe; RAID 0+1 hai stripe-then-mirror.

Level 1 — Recognition

Recall Solution L1·Q1

(a) RAID 0 — pure striping. Yeh har block ki ek copy store karta hai, lekin zero redundancy rakhta hai (rebuild karne ke liye kuch bhi extra nahi). (b) RAID 1 — mirroring. (c) RAID 5 — striping + ek distributed parity. (d) RAID 6 — striping + double distributed parity ( $P$ aur $Q$ ). (e) RAID 10 — mirror phir stripe.

Recall Solution L1·Q2

(a) False. Koi redundancy nahi matlab koi bhi single failure poora array kho deta hai. (b) True. Do independent parities → do solvable unknowns. (c) True. Aadhi disks copies hain, toh usable $= n /2$ .

Level 2 — Application

Recall Solution L2·Q1

Raw = $10 \times 6 = 60$ TB. Yeh raha kyun har capacity rule kaam karta hai, phir number:

RAID 0 → $n$ : har disk unique data rakhti hai, kuch waste nahi → $10 \times 6 = 60$ TB.
RAID 1 → $n /2$ : har disk ka ek identical twin hai, toh aadhi disks pure copies hain → $\frac{10}{2} \times 6 = 30$ TB.
RAID 5 → $n - 1$ : ek disk ki worth of space parity pe spend hoti hai (rotated, koi single disk nahi) → $(10 - 1) \times 6 = 54$ TB.
RAID 6 → $n - 2$ : do parities $P$ aur $Q$ pe do disks ki worth of space spend hoti hai → $(10 - 2) \times 6 = 48$ TB.
RAID 10 → $n /2$ : mirroring already usable capacity ko aadha kar deta hai; pairs ke across striping speed add karta hai, space nahi → $\frac{10}{2} \times 6 = 30$ TB.

Recall Solution L2·Q2

Left to right karo (XOR associative hai, toh grouping free hai): $D_{1} \oplus D_{2} = 1101 \oplus 0011 = 1110$ (bit by bit: 1≠0→1, 1≠0→1, 0≠1→1, 1≠1→0). $1110 \oplus D_{3} = 1110 \oplus 1000 = 0110 = P$ Toh $P = 0110$ .

Recall Solution L2·Q3

Recovery rule: $D_{1} = P \oplus D_{2} \oplus D_{3}$ . $P \oplus D_{2} = 0110 \oplus 0011 = 0101$ $0101 \oplus D_{3} = 0101 \oplus 1000 = 1101 = D_{1}$ $D_{1} = 1101$ — exactly original. ✓

Recall Solution L2·Q4

4 I/Os: purana data $D_{o l d}$ read karo, purani parity $P_{o l d}$ read karo, naya data $D_{n e w}$ likho, nayi parity $P_{n e w}$ likho. Parity $P_{n e w} = P_{o l d} \oplus D_{o l d} \oplus D_{n e w}$ se recompute hoti hai (baaki disks ko touch karne ki zaroorat nahi).

Level 3 — Analysis

Recall Solution L3·Q1

Sahi nayi parity compute karne ke liye tumhe purane data ka contribution hatana aur naya daalna padta hai: $P_{n e w} = P_{o l d} \oplus D_{o l d} \oplus D_{n e w}$ Is formula ko $P_{o l d}$ aur $D_{o l d}$ chahiye, aur dono abhi disk pe hain — tumhe pehle unhe read karna padega. Toh: $D_{o l d}$ read karo, $P_{o l d}$ read karo (2 reads) → phir $D_{n e w}$ likho, $P_{n e w}$ likho (2 writes) = 4 I/Os. Woh 2 reads woh hidden cost hai jise naïve count bhool jaata hai.

Recall Solution L3·Q2

RAID 6 do parities $P$ aur $Q$ rakhta hai, dono us block ko include karti hain jo tumne change kiya. Har ek ko apna read-modify-write chahiye:

$D_{o l d}$ , $P_{o l d}$ , $Q_{o l d}$ read karo → 3 reads.
$D_{n e w}$ , $P_{n e w}$ , $Q_{n e w}$ likho → 3 writes.

Total = 6 I/Os. Isliye RAID 6 small writes pe RAID 5 se slow hai.

Recall Solution L3·Q3

Ek large sequential read tab fast hota hai jab bahut saare disk heads ek saath data pull kar rahे hों. Toh sawaal yeh hai: har level ke liye, kitne spindles parallel mein useful data feed karte hain?

RAID 0 ≈ $n$ spindles: har disk unique data rakhti hai, sab $n$ ek saath read karte hain. Kuch waste nahi → sabse fast.
RAID 10 ≈ $n$ spindles tak: har mirror pair reads dono mein se kisi bhi twin se serve kar sakta hai, toh har pair ki dono disks ek saath alag alag parts stream kar sakti hain → essentially RAID 0 se match karta hai.
RAID 5 ≈ $n$ spindles read karte hain, lekin kisi bhi stripe mein sirf $n - 1$ data carry karte hain (har stripe mein ek block parity hai). Pure sequential read ke liye controller phir bhi saari disks spin karta hai, phir bhi useful-data bandwidth RAID 0/10 se thodi kum hoti hai kyunki har stripe mein ek disk ki worth parity hai, payload nahi. Isliye yeh thoda peeche hai.
RAID 1 (plain mirror, striped nahi): ek single mirror pair ke paas sirf 2 disks hain jo ek logical stream feed karti hain, toh yeh striped levels ki tarah bade $n$ ke saath scale nahi karta → sabse slow per usable-data.

Ordering, $≳$ symbol ke saath jiska matlab hai "lagbhag barabar, ya thoda faster than": $RAID 0 \approx RAID 10 ≳ RAID 5 > RAID 1 .$ Reads striped levels mein broadly similar hote hain; write side (parity penalty) real differentiator hai.

Recall Solution L3·Q4

RAID 5 ke paas ek parity equation hai, jo exactly ek unknown disk solve karta hai. Pehli dead disk rebuild karte waqt, baaki 11 disks ghanton tak hard read hoti hain — woh stress doosri failure ka chance badhata hai. Agar rebuild finish hone se pehle doosri disk mar jaaye, toh ab tumhare paas do unknowns hain lekin sirf ek equation hai → unsolvable → total loss. RAID 6 ek doosra, independent parity $Q$ rakhta hai, jo do equations deta hai, toh yeh do dead disks ke liye solve kar sakta hai aur us scenario mein survive kar sakta hai. Failure-rate reasoning ke liye Reliability and MTBF dekho.

Level 4 — Synthesis

Recall Solution L4·Q1

RAID 10 choose karo. Reasoning:

Write-heavy + small writes → parity ke read-modify-write penalty se bachao (RAID 5/6 out).
Disk failure availability ke saath survive karni chahiye → RAID 0 out.
RAID 10 = mirror then stripe → fast writes (koi parity recompute nahi) aur redundancy.

RAID 10 ki capacity $n /2$ disks hai. $20$ TB usable chahiye at $4$ TB/disk = $5$ usable data disks → $5$ mirror pairs → $n = 10$ disks (deta hai $10/2 \times 4 = 20$ TB usable). Odd hone par pairs up round karo; yahan exact hai.

Recall Solution L4·Q2

RAID 6 choose karo. Reasoning:

Large writes, rare → parity penalty big stripes pe amortise ho jaati hai, aur small-write cost irrelevant hai.
Cost matters → RAID 6 sirf 2 disks waste karta hai (vs RAID 10 jo aadha waste karta hai).
Long rebuilds ke dauran survive karni chahiye big disks ke saath → double parity chahiye (RAID 5 yahan unsafe hai, dekho L3·Q4).

RAID 6 usable = $n - 2$ disks. $100$ TB chahiye at $10$ TB/disk = $10$ usable data disks → $n - 2 = 10 \Rightarrow n = 12$ disks. Usable $= (12 - 2) \times 10 = 100$ TB. ✓

Recall Solution L4·Q3

RAID 10 zyada robust hai.

RAID 10 (mirror-then-stripe): har pair ek mirror hai. Ek pair tab tak survive karta hai jab tak uski do disks mein se ek live hai. Do failures tabhi fatal hain jab dono dead disks same pair mein hों. 4 pairs ke saath, doosri failure same pair mein sirf ~1 in 7 baar padti hai → usually survive karta hai.
RAID 0+1 (stripe-then-mirror): ek disk loss uski poori stripe ko maar deta hai, toh tum poori tarah doosri stripe pe lean kar rahe ho. Us surviving stripe mein doosri failure array ko maar deti hai. Vulnerability ki window bahut wide hai.

Order matters: mirror-then-stripe damage ko ek single pair mein localise karta hai.

Level 5 — Mastery

Recall Solution L5·Q1

Right-hand side se shuru karo aur $P$ substitute karo: $P \oplus ⨁_{i \neq = k} D_{i} = (⨁_{all i} D_{i}) \oplus ⨁_{i \neq = k} D_{i} .$ Har surviving $D_{i}$ ( $i \neq = k$ ) ko $P$ ke andar uski copy ke saath group karo. Commutativity/associativity se hum unhe pair kar sakte hain, aur self-inverse $x \oplus x = 0$ se har pair vanish ho jaata hai: $= D_{k} \oplus (⨁_{i \neq = k} (D_{i} \oplus D_{i})) = D_{k} \oplus 0 = D_{k} .$ Sirf woh term jo bina partner ke hai — $D_{k}$ — survive karta hai. $■$ Isliye single parity exactly ek erasure fix karta hai: ek equation, ek unknown.

Recall Solution L5·Q2

Do dead data disks $D_{a}, D_{b}$ ke saath, survivors dete hain: $P_{1} \oplus ⨁_{i \neq = a, b} D_{i} = D_{a} \oplus D_{b} .$ $P_{2}$ , $P_{1}$ ke identical hai, toh woh same equation $D_{a} \oplus D_{b}$ yield karta hai. Ek equation ki do copies phir bhi sirf ek equation hai do unknowns ke saath → infinitely many $(D_{a}, D_{b})$ use satisfy karte hain → unrecoverable. RAID 6 instead $Q = ⨁_{i} g^{i} \cdot D_{i}$ compute karta hai GF(2^8) pe, jahan $D_{i}$ ko ek distinct field element $g^{i}$ se multiply karna har disk ko alag tarike se weight karta hai. Ab $Q$ equation $P$ equation se linearly independent hai, ek solvable $2 \times 2$ system deta hai → dono unknowns recover ho jaate hain.

Recall Solution L5·Q3

(a) RAID 5 with $n = 2$ : ek single data block ki parity bas uski copy hai ( $P = D_{1}$ ). Toh yeh RAID 1 (mirroring) mein degenerate ho jaata hai. Usable $= n - 1 = 1$ disk, same as $n = 2$ ke liye $n /2$ . (b) RAID 6, $n = 3$ : usable $= n - 2 = 1$ disk. Teen mein se do disks parity hain — extremely wasteful, aur minimum size jahan RAID 6 sense bhi karta hai. (c) $P = 0000 \oplus 0000 \oplus \dots = 0000$ . All-zero data ki parity zero hai (identity $x \oplus 0 = x$ ). (d) RAID 1 with $n = 1$ ke paas mirror karne ke liye koi twin nahi — yeh sirf ek single plain disk hai, koi redundancy nahi. Meaningful mirror nahi hai.

Recall Solution L5·Q4

$P = D_{1} \oplus D_{2} \oplus D_{3} = 1010 \oplus 0111 \oplus 0001.$ Step: $1010 \oplus 0111 = 1101$ . Phir $1101 \oplus 0001 = 1100 = P$ . Recover: $D_{3} = P \oplus D_{1} \oplus D_{2} = 1100 \oplus 1010 \oplus 0111$ . $1100 \oplus 1010 = 0110$ ; $0110 \oplus 0111 = 0001 = D_{3}$ . ✓ Original se match karta hai — round-trip close ho jaata hai.

L4·Q3 se failure-survival counting visually dekhna zyada aasaan hai:

Figure — RAID — levels 0, 1, 5, 6, 10 — trade-offs

Recall

RAID 5 ka ek small write 4 I/Os kyun kosta hai?

Tumhe

D_{n e w}

aur

P_{n e w}

likhne se pehle

D_{o l d}

aur

P_{o l d}

read karne padte hain — do hidden reads plus do writes.

Single XOR parity sirf ek dead disk kyun recover kar sakta hai?

Ek parity = ek equation = ek solvable unknown.

RAID 6 doosre XOR ki jagah

GF (2^{8})

Q

kyun use karta hai?

Doosra XOR same equation deta hai;

Q

disks ko

g^{i}

se weight karta hai linearly independent hone ke liye, toh do unknowns solvable hain.

Write-heavy DB ke liye jo redundancy chahta ho, kaun sa level?

RAID 10 — fast writes (koi parity recompute nahi) plus redundancy.

Saste bade archive ke liye jo long rebuilds survive kare, kaun sa level?

RAID 6 — sirf 2 disks waste, rebuild ke dauran doosri failure survive karta hai.

RAID 10 aur RAID 0+1 mein kya fark hai?

RAID 10 = mirror then stripe (damage ek pair mein localise karta hai); RAID 0+1 = stripe then mirror (ek disk ek poori stripe maar deta hai).