Laboratorio RAID
Sistemi · 6.5 RAID

Laboratorio RAID

Scegli un livello, distruggi uno o più dischi e chiedi a ogni blocco dove è finito: salvo su un'altra copia, ricostruibile dalla parità o perso per sempre.

datoparità Pparità QHammingrecuperabileperso

File A

Sotto il cofano

Come si recupera un dato perso

Velocità

Parità XOR · RAID 3, 4, 5

Quattro dischi di dati, un disco di parità

Ogni disco contiene un byte della parola “CIAO”. Clicca un bit per cambiarlo, distruggi un disco e guarda come si ricostruisce colonna per colonna.

XOR (⊕): se viene 1 gli 1 sono dispari
se viene 0 gli 1 sono pari

Perché la parità risparmia spazio

La riga P è una sola, qualunque sia il numero di dischi di dati che protegge. Il mirroring invece fa una copia di ogni disco: metà dello spazio va sempre alla protezione.

P non contiene i dati. Contiene un solo bit per colonna, che dice se gli 1 sono pari o dispari. Da sola non serve a niente: funziona insieme ai dischi sopravvissuti, perché in ogni colonna resta un solo valore possibile per il bit mancante.

Il mirroring è la fotocopia di tutto il quaderno. La parità è il totale scritto in fondo a ogni colonna: occupa una riga sola, ma se cancelli due numeri della stessa colonna non sai più quali erano.

  • In cambio: sopporta un solo guasto alla volta.
  • Ogni scrittura deve aggiornare anche P.
  • Per ricostruire un disco bisogna leggere tutti gli altri.
Codice di Hamming (7,4) · RAID 2

Tre cerchi di controllo che si sovrappongono

I 4 bit di dati d1–d4 stanno su Disk 0–3, i controlli Ha, Hb, Hc su Disk 4–6. Regola: in ogni cerchio il numero di 1 deve essere pari.

Come funziona Hamming, passo per passo

La regola dello XOR
XOR = 1il numero di 1 è dispari1 ⊕ 1 ⊕ 1 = 1 · tre 1
XOR = 0il numero di 1 è pari1 ⊕ 0 ⊕ 1 = 0 · due 1

Quindi in un cerchio: se alla fine viene 0 è tutto a posto, se viene 1 qualcosa è cambiato.

Ha, Hb, Hc sono entrambe le cose
Alla scritturasono il risultatoHa = d1 ⊕ d2 ⊕ d4
1 ⊕ 0 ⊕ 1 = 0 → si salva Ha = 0
Alla letturasono un fattored1 ⊕ d2 ⊕ d4 ⊕ Ha = ?
1 ⊕ 0 ⊕ 1 ⊕ 0 = 0 ✓

Perché alla lettura deve venire 0? Ha vale esattamente d1 ⊕ d2 ⊕ d4, quindi rimetterlo nello XOR è come fare X ⊕ X, e uno XOR con se stesso dà sempre 0. Se viene 1, qualcosa è cambiato dopo la scrittura.

I nomi: Ha, Hb, Hc sono i bit di controllo che Hamming aggiunge ai dati. I tre risultati della rilettura (per esempio 0, 1, 1) si chiamano sindrome: tutti 0 = nessun errore, altrimenti indicano quale bit è sbagliato.

  1. Il problema

    Un disco può restituire un bit sbagliato senza segnalarlo. Con un solo bit di parità ti accorgi che c'è un errore, perché gli 1 diventano dispari, ma non sai dove sta. Qualsiasi dei bit potrebbe essere il colpevole.

  2. L'idea: tre controlli che si sovrappongono

    Invece di un controllo su tutti i bit, se ne usano tre, ognuno su un gruppo diverso: i tre cerchi. Ogni bit sta in una combinazione diversa di cerchi, e quella combinazione è il suo indirizzo.

    Ha = d1 ⊕ d2 ⊕ d4
    Hb = d1 ⊕ d3 ⊕ d4
    Hc = d2 ⊕ d3 ⊕ d4

  3. Scrittura: chi decide Ha, Hb, Hc

    d1–d4 sono i tuoi dati: valgono quello che valgono e nessuno li tocca. Ha, Hb, Hc non sono dati. Li sceglie il controller, in automatico, ogni volta che scrive.

    La regola è fissata una volta per tutte: in ogni cerchio il numero di 1 deve essere pari. Per questo il controller calcola ogni H come XOR dei dati del suo cerchio: Ha = d1 ⊕ d2 ⊕ d4.

    XOR o somma? Si fa lo XOR, non la somma. Con lo XOR, se alla fine viene 1 gli 1 sono dispari, se viene 0 sono pari. Per questo nelle animazioni contiamo gli 1: è il modo di fare lo XOR a mente. Esempio: 1 ⊕ 0 ⊕ 1 → due 1, pari → 0. La somma darebbe 2, che non è un bit.

    Perché proprio pari? Serve un riferimento: per accorgerti che qualcosa è cambiato devi sapere com'era quando era giusto. È come un cassiere che aggiunge monete finché il totale è una cifra tonda. Se il giorno dopo il conto non è più tondo, qualcuno ha toccato la cassa. Andrebbe bene anche “sempre dispari”: conta solo che la regola sia fissa.

  4. Lettura: un bit è cambiato, come lo trovo

    Più tardi il controller rilegge i 7 bit e riconta gli 1 di ogni cerchio, questa volta compreso il bit H. Se un cerchio non è più pari, qualcosa al suo interno è cambiato dopo la scrittura. I dati scritti erano 1011. Con “Quale bit si guasta?” scegli tu il bit che si corrompe senza avviso (si parte con d3), poi guarda la rilettura. Per ogni cerchio il controller rifà lo XOR, compreso H: se tutto è a posto deve venire 0.

  5. Un disco si rompe: come recupero il bit

    Qui è più facile, perché il controller sa già quale bit manca: il disco non risponde. Si cerca un cerchio che contiene un solo bit sconosciuto e si sceglie il valore che lo rende pari.

    Esempio: mancano d1 e d4. Il cerchio Hc contiene d4 ma non d1. I suoi bit d2, d3, Hc valgono 0, 1, 0: c'è un solo 1, quindi d4 = 1. Ora in Ha manca solo d1. I bit d2, d4, Ha valgono 0, 1, 0: c'è un solo 1, quindi d1 = 1.

  6. Perché bastano 3 controlli

    Tre cerchi, ognuno giusto o sbagliato, danno 2 × 2 × 2 = 8 risposte possibili. Una vuol dire “nessun errore”, le altre 7 indicano ciascuna uno dei 7 bit. Il codice è costruito in modo che nessun indirizzo si ripeta.