Questa è l'apparenza della ridondanza

I codici di ridondanza* sono ampiamente utilizzati nei sistemi informatici per migliorare l'affidabilità della memorizzazione dei dati. In Yandex vengono utilizzati in molti progetti. Ad esempio, l'uso dei codici di ridondanza invece della replica nel nostro deposito oggetti interno fa risparmiare milioni senza ridurre l'affidabilità. Ma nonostante la loro ampia diffusione, una descrizione comprensibile su come funzionano i codici di ridondanza è molto rara. Coloro che desiderano capirlo si imbattono all'incirca in quanto segue (da Wikipedie):

Mi chiamo Vadim, in Yandex mi occupo dello sviluppo del deposito oggetti interno MDS. In questo articolo descriverò in modo semplice le basi teoriche dei codici di ridondanza (codici di Reed-Solomon e LRC). Spiegherò come funziona, senza matematica complessa e termini rari. Alla fine fornirò esempi di utilizzo dei codici di ridondanza in Yandex.

Non approfondirò una serie di dettagli matematici, ma fornirò link per chi desidera approfondire. Inoltre, annoterò che alcune definizioni matematiche potrebbero non essere rigorose, poiché l'articolo è indirizzato non ai matematici, ma agli ingegneri che desiderano capire il nocciolo della questione.

* Nella letteratura anglofona, i codici di ridondanza vengono spesso chiamati erasure codes.

1. L'essenza dei codici di ridondanza

L'essenza di tutti i codici di ridondanza è estremamente semplice: memorizzare (o trasferire) i dati in modo che non vengano persi in caso di errori (guasti dei dischi, errori di trasmissione dei dati, ecc.).

Nella maggior parte* dei codici di ridondanza, i dati vengono suddivisi in n blocchi di dati, per i quali vengono calcolati m blocchi di codici di ridondanza, per un totale di n + m blocchi. I codici di ridondanza sono costruiti in modo che sia possibile ripristinare n blocchi di dati utilizzando solo una parte dei n + m blocchi. Successivamente, ci concentreremo solo sui codici di ridondanza a blocchi, ovvero quelli in cui i dati vengono suddivisi in blocchi.

Per ripristinare tutti i n blocchi di dati, è necessario avere almeno n da n + m blocchi, poiché non è possibile ottenere n blocchi avendo solo n-1 blocco (in questo caso sarebbe necessario prendere 1 blocco "dal nulla"). È sufficiente avere n blocchi arbitrari da n + m blocchi per ripristinare tutti i dati? Questo dipende dal tipo di codici di ridondanza; ad esempio, i codici di Reed-Solomon consentono di ripristinare tutti i dati utilizzando n blocchi arbitrari, mentre i codici di ridondanza LRC non sempre.

Archiviazione dati

Nelle sistemi di archiviazione dati, di solito, ciascun blocco di dati e ciascun blocco di codice di ridondanza viene registrato su un disco separato. Pertanto, in caso di rottura di un disco qualsiasi, i dati originali possono comunque essere ripristinati e letti. I dati possono essere ripristinati anche in caso di rottura simultanea di più dischi.

Trasmissione dei dati

I codici di ridondanza possono essere utilizzati per la trasmissione affidabile dei dati in una rete inaffidabile. I dati trasmessi vengono suddivisi in blocchi, per i quali vengono calcolati codici di ridondanza. Sulla rete vengono inviati sia i blocchi di dati che i blocchi di codici di ridondanza. In caso di errori in blocchi arbitrari (fino a un certo numero di blocchi), i dati possono comunque essere trasmessi senza errori sulla rete. I codici di Reed-Solomon, ad esempio, vengono utilizzati per la trasmissione dei dati su linee di comunicazione ottiche e nelle comunicazioni satellitari.

* Ci sono anche codici di ridondanza in cui i dati non vengono suddivisi in blocchi, ad esempio i codici di Hamming e i codici CRC, ampiamente usati per la trasmissione dei dati nelle reti Ethernet. Questi sono codici per la codifica resistente agli errori, progettati per rilevare errori, ma non per correggerli (il codice di Hamming consente anche di correggere parzialmente errori).

2. Codici di Reed-Solomon

I codici di Reed-Solomon sono tra i codici di ridondanza più ampiamente utilizzati, inventati negli anni '60 e impiegati per la prima volta in modo diffuso negli anni '80 per la produzione di massa di Compact Disc.

Le due questioni chiave per comprendere i codici di Reed-Solomon sono: 1) come creare blocchi di codici di ridondanza; 2) come ripristinare i dati utilizzando blocchi di codici di ridondanza. Troviamo le risposte a queste domande.
Per semplificare, considereremo d'ora in poi che n=6 e m=4. Altri schemi saranno considerati per analogia.

Come creare blocchi di codici di ridondanza

Ogni blocco di codici ridondanti viene considerato indipendentemente dagli altri. Per il calcolo di ogni blocco vengono utilizzati tutti i n blocchi di dati. Nello schema sottostante X1-X6 sono i blocchi di dati, P1–P4 sono i blocchi di codici ridondanti.

Tutti i blocchi di dati devono avere la stessa dimensione; per allinearle è possibile utilizzare bit zero. I blocchi di codici ridondanti ottenuti avranno la stessa dimensione dei blocchi di dati. Tutti i blocchi di dati vengono suddivisi in parole (ad esempio, per 16 bit). Supponiamo di suddividere i blocchi di dati in k parole. Allora anche tutti i blocchi di codici ridondanti saranno suddivisi in k parole.

Per il calcolo della i-esima parola di ogni blocco di ridondanza verranno utilizzate le i-esime parole di tutti i blocchi di dati. Saranno calcolate secondo la seguente formula:

Qui i valori x sono le parole dei blocchi di dati, p sono le parole dei blocchi di codici ridondanti, tutti alfa, beta, gamma e delta sono numeri scelti in modo speciale, uguali per tutti i i. È importante sottolineare che tutti questi valori non sono numeri comuni, ma elementi del campo di Galois; le operazioni +, -, *, / non sono le operazioni che conosciamo, ma operazioni speciali introdotte sugli elementi del campo di Galois.

A cosa servono i campi di Galois

Sembra tutto semplice: suddividiamo i dati in blocchi, i blocchi in parole, e usando le parole dei blocchi di dati calcoliamo le parole dei blocchi di codici ridondanti, otteniamo i blocchi di codici ridondanti. In generale, funziona così, ma il diavolo è nei dettagli:

Come detto sopra, la dimensione della parola è fissa, nel nostro esempio 16 bit. Le formule sopra per i codici di Reed-Solomon sono tali che, utilizzando numeri interi comuni, il risultato del calcolo di p potrebbe non essere rappresentabile con una parola di dimensione consentita.
Nella fase di recupero dei dati, le formule sopra saranno considerate come un sistema di equazioni da risolvere per recuperare i dati. Nel processo di risoluzione potrebbe sorgere la necessità di eseguire divisioni tra numeri interi, il cui risultato sarà un numero reale, che non può essere rappresentato con precisione nella memoria del computer.

Questi problemi impediscono l'uso di numeri interi per i codici Reed-Solomon. La soluzione al problema è originale e può essere descritta come segue: inventiamo numeri speciali che possono essere rappresentati tramite parole di lunghezza desiderata (ad esempio, 16 bit), e il risultato di tutte le operazioni (somma, sottrazione, moltiplicazione, divisione) sarà anch'esso rappresentato in memoria del computer tramite parole della lunghezza desiderata.

Questi "numeri speciali" sono studiati da tempo dalla matematica e vengono chiamati campi. Un campo è un insieme di elementi con operazioni di somma, sottrazione, moltiplicazione e divisione definite per loro.

I campi di Galois* sono campi per i quali esiste un risultato unico per ogni operazione (+, -, *, \/) per qualsiasi coppia di elementi del campo. I campi di Galois possono essere costruiti per numeri che sono potenze di 2: 2, 4, 8, 16, ecc. (in realtà, per potenze di ogni numero primo p, ma nella pratica ci interessano solo le potenze di 2). Ad esempio, per le parole di dimensione 16 bit, questo campo contiene 65.536 elementi, per ciascuna delle coppie dei quali è possibile trovare il risultato di qualsiasi operazione (+, -, *, \/). I valori x, p, alfa, beta, gamma, delta delle equazioni precedenti per i calcoli saranno considerati elementi del campo di Galois.

Pertanto, abbiamo un sistema di equazioni, che ci permette di costruire blocchi di codici di ridondanza scrivendo un'apposita programma informatica. Con lo stesso sistema di equazioni è possibile eseguire il recupero dei dati.

* Questa non è una definizione rigorosa, più un descrizione.

Come recuperare i dati

Il recupero è necessario quando, da n + m blocchi, parte dei blocchi è mancante. Questi possono essere sia blocchi di dati che blocchi di codici di ridondanza. L'assenza di blocchi di dati e/o di blocchi di codici di ridondanza significa che nelle equazioni precedenti le corrispondenti variabili x e/o p sono sconosciute.

Le equazioni per i codici Reed-Solomon possono essere considerate come un sistema di equazioni in cui tutti i valori alfa, beta, gamma, delta sono costanti, tutte le x e p corrispondenti ai blocchi disponibili sono variabili conosciute, mentre le altre x e p sono sconosciute.

Ad esempio, supponiamo che i blocchi di dati 1, 2, 3 e il blocco di codici di ridondanza 2 non siano disponibili, allora per il gruppo i di parole avremo il seguente sistema di equazioni (le variabili sconosciute sono segnate in rosso):

Abbiamo un sistema di 4 equazioni con 4 incognite, quindi possiamo risolverlo e recuperare i dati!

Da questo sistema di equazioni derivano alcune conclusioni sul recupero dei dati per i codici Di Reed-Solomon (n blocchi di dati, m blocchi di codici di ridondanza):

I dati possono essere recuperati in caso di perdita di qualsiasi m blocchi o meno. In caso di perdita di m + 1 blocchi o più, i dati non possono essere recuperati: non è possibile risolvere un sistema di m equazioni con m + 1 incognite.
Per recuperare anche un solo blocco di dati, è necessario utilizzare qualsiasi n dei blocchi rimanenti, e si può usare qualsiasi dei codici di ridondanza.

Cosa altro bisogna sapere

Nella descrizione sopra, evito di trattare alcune questioni importanti, che richiederebbero un'approfondita comprensione della matematica. In particolare, non parlo di quanto segue:

Il sistema di equazioni per i codici Di Reed-Solomon deve avere una (e unica) soluzione per qualsiasi combinazione di incognite (non più di m incognite). In base a questo requisito vengono scelti i valori di alfa, beta, gamma e delta.
Il sistema di equazioni deve essere in grado di essere costruito automaticamente (a seconda dei blocchi non disponibili) e risolto.
È necessario costruire un campo di Galois: per una data dimensione della parola, essere in grado di trovare il risultato di qualsiasi operazione (+, -, *, /) per qualsiasi due elementi.

Alla fine dell'articolo ci sono riferimenti alla letteratura su queste questioni importanti.

Scelta di n e m

Come scegliere n e m nella pratica? In pratica, nei sistemi di archiviazione dati, i codici di ridondanza vengono utilizzati per risparmiare spazio, quindi m viene sempre scelto inferiore a n. I loro valori specifici dipendono da vari fattori, tra cui:

Affidabilità dell'archiviazione dei dati. Maggiore è m, maggiore è il numero di guasti ai dischi che possono essere sopportati, ossia maggiore è l'affidabilità.
Ridondanza dell'archiviazione. Maggiore è il rapporto m / n, maggiore sarà la ridondanza dell'archiviazione, e maggiore sarà il costo del sistema.
Tempo di elaborazione delle richieste. Maggiore è la somma n + m, più lungo sarà il tempo di risposta alle richieste. Poiché per leggere i dati (durante il recupero) è necessario leggere n blocchi, memorizzati su n dischi diversi, il tempo di lettura sarà determinato dal disco più lento.

Inoltre, la conservazione dei dati in più DC impone ulteriori vincoli sulla scelta di n e m: in caso di disconnessione di 1 DC, i dati devono comunque essere accessibili in lettura. Ad esempio, conservando i dati in 3 DC, deve valere la condizione: m >= n/2; altrimenti, è possibile che i dati non siano accessibili in lettura in caso di disconnessione di 1 DC.

3. LRC — Codici di Ricostruzione Locale

Per ripristinare i dati utilizzando i codici di Reed-Solomon, è necessario usare n blocchi di dati arbitrari. Questo è uno svantaggio molto significativo per i sistemi distribuiti di archiviazione dei dati, poiché per ripristinare i dati su un disco danneggiato è necessario leggere i dati dalla maggior parte degli altri, generando un gran carico aggiuntivo su dischi e rete.

Gli errori più comuni sono l'inaccessibilità di un blocco di dati a causa di un guasto o sovraccarico di un disco. Esiste un modo per ridurre il carico eccessivo per il ripristino dei dati in tale (casi più comuni) situazione? A quanto pare, sì: esistono appositamente codici di ridondanza LRC.

LRC (Codici di Ricostruzione Locale) sono codici di ridondanza ideati da Microsoft per l'uso in Windows Azure Storage. L'idea dell'LRC è estremamente semplice: suddividere tutti i blocchi di dati in due (o più) gruppi e calcolare una parte dei blocchi di codici di ridondanza per ciascun gruppo separatamente. Così, una parte dei blocchi di codici di ridondanza viene calcolata utilizzando tutti i blocchi di dati (in LRC sono chiamati codici di ridondanza globali), mentre una parte viene calcolata utilizzando uno dei due gruppi di blocchi di dati (chiamati codici di ridondanza locali).

LRC è indicato da tre numeri: n-r-l, dove n è il numero di blocchi di dati, r è il numero di blocchi di codici di ridondanza globali, l è il numero di blocchi di codici di ridondanza locali. Per leggere i dati in caso di mancanza di un blocco di dati, è necessario leggere solo n/l blocchi — questo è l di meno rispetto ai codici di Reed-Solomon.

Ad esempio, consideriamo lo schema LRC 6-2-2. X1–X6 sono 6 blocchi di dati, P1, P2 sono 2 blocchi di ridondanza globali, P3, P4 sono 2 blocchi di ridondanza locali.

I blocchi di codici di ridondanza P1, P2 sono calcolati utilizzando tutti i blocchi di dati. Il blocco di codici di ridondanza P3 è calcolato utilizzando i blocchi di dati X1–X3, il blocco di codici di ridondanza P4 è calcolato utilizzando i blocchi di dati X4–X6.

Il resto viene fatto in LRC analogamente ai codici di Reed-Solomon. Le equazioni per il conteggio delle parole dei blocchi di codici di ridondanza saranno le seguenti:

Per scegliere i numeri alfa, beta, gamma, delta è necessario soddisfare una serie di condizioni che garantiscano la possibilità di recupero dei dati (cioè la soluzione del sistema di equazioni). Maggiori dettagli possono essere letti in abbiamo chiarito il corretto completamento dei programmi che utilizzano il mediastreamer..
Inoltre, nella pratica per il conteggio dei codici di ridondanza locali P3, P4 si utilizza l'operazione XOR.

Dalla sistema di equazioni per LRC seguono diverse conclusioni:

Per recuperare un singolo blocco di dati è sufficiente leggere n/l blocchi (n/2 nel nostro esempio).
Se non sono disponibili r + l blocchi e tutti i blocchi appartengono a un unico gruppo, i dati non possono essere recuperati. Questo è facile spiegare con un esempio. Supponiamo che non siano disponibili i blocchi X1–X3 e P3: questi sono r + l blocchi di un unico gruppo, 4 nel nostro caso. Allora abbiamo un sistema di 3 equazioni con 4 incognite, che non può essere risolto.
In tutti gli altri casi di indisponibilità di r + l blocchi (quando da ciascun gruppo è disponibile almeno un blocco) i dati in LRC possono essere recuperati.

Pertanto, LRC ha vantaggi rispetto ai codici Reed-Solomon nel recupero dei dati dopo errori singoli. Nei codici Reed-Solomon, per recuperare anche un solo blocco di dati, è necessario utilizzare n blocchi, mentre in LRC per recuperare un singolo blocco di dati è sufficiente utilizzare n/l blocchi (n/2 nel nostro esempio). D'altra parte, LRC è svantaggiato rispetto ai codici Reed-Solomon per il numero massimo di errori consentiti. Negli esempi sopra, i codici Reed-Solomon possono recuperare i dati in presenza di qualsiasi 4 errori, mentre per LRC ci sono 2 combinazioni di 4 errori in cui i dati non possono essere recuperati.

Ciò che è più importante dipende dalla situazione specifica, ma spesso il risparmio di carico ridondante fornito da LRC supera una leggermente minore affidabilità di archiviazione.

4. Altri codici di ridondanza

Oltre ai codici Reed-Solomon e LRC, ci sono molti altri codici di ridondanza. Diversi codici di ridondanza utilizzano matematica diversa. Ecco alcuni altri codici di ridondanza:

Codice di ridondanza tramite operatore XOR. L'operazione XOR viene eseguita su n blocchi di dati, ottenendo 1 blocco di codici di ridondanza, cioè schema n+1 (n blocchi di dati, 1 codice di ridondanza). Utilizzato in RAID 5, dove i blocchi di dati e i codici di ridondanza sono scritti ciclicamente su tutti i dischi dell'array.
L'algoritmo even-odd, basato sull'operazione XOR. Permette di costruire 2 blocchi di codici di ridondanza, ovvero uno schema n+2.
L'algoritmo STAR, basato sull'operazione XOR. Permette di costruire 3 blocchi di codici di ridondanza, ovvero uno schema n+3.
I codici Pyramide — ulteriori codici di ridondanza di Microsoft.

5. Utilizzo in Yandex

Una serie di progetti infrastrutturali di Yandex utilizza codici di ridondanza per un'archiviazione dati affidabile. Ecco alcuni esempi:

Lo storage oggetti interno MDS, di cui ho parlato all'inizio dell'articolo.
YT — Il sistema MapReduce di Yandex.
YDB (Yandex DataBase) — un database distribuito newSQL.

In MDS si utilizzano codici di ridondanza LRC, schema 8-2-2. I dati con i codici di ridondanza vengono scritti su 12 dischi diversi in server differenti in 3 diversi DC: 4 server in ciascun DC. Maggiori dettagli su questo si possono trovare in abbiamo chiarito il corretto completamento dei programmi che utilizzano il mediastreamer..

In YT vengono utilizzati sia codici di Reed-Solomon (schema 6-3), che sono stati implementati per primi, sia codici di ridondanza LRC (schema 12-2-2), con LRC come modalità di archiviazione preferita.

In YDB si utilizzano codici di ridondanza basati su even-odd (schema 4-2). Già si è parlato dei codici di ridondanza in YDB nella conferenza Highload.

L'applicazione di diversi schemi di codici di ridondanza è determinata da varie esigenze poste ai sistemi. Ad esempio, in MDS i dati archiviati con LRC sono distribuiti in 3 DC. È importante che i dati rimangano accessibili in lettura in caso di guasto di uno qualsiasi dei DC, quindi i blocchi devono essere distribuiti tra i DC in modo tale che, in caso di inaccessibilità di un DC, il numero di blocchi non disponibili non superi il limite consentito. Nello schema 8-2-2, possono essere collocati 4 blocchi in ciascun DC, quindi in caso di disconnessione di un qualsiasi DC, 4 blocchi non saranno disponibili, e i dati potranno essere letti. Qualunque schema scegliamo per la distribuzione nei 3 DC, in ogni caso deve esserci (r + l) / n >= 0,5, ovvero la ridondanza di archiviazione sarà almeno del 50%.

In YT la situazione è diversa: ogni cluster YT è completamente situato in 1 DC (diversi cluster in DC diversi), quindi non ci sono tali vincoli. Lo schema 12-2-2 offre una ridondanza del 33%, quindi archiviare i dati risulta più economico, mentre possono anche resistere fino a 4 disconnessioni di dischi simultanee, proprio come nel caso dello schema in MDS.

Ci sono ancora molte peculiarità nell'applicazione dei codici di ridondanza nei sistemi di archiviazione e elaborazione dei dati: sfumature nel recupero dei dati, impatto del recupero sui tempi di esecuzione delle query, peculiarità nella registrazione dei dati, ecc. Intendo parlare separatamente di queste e di altre peculiarità dell'applicazione dei codici di ridondanza nella pratica, se il tema risulterà interessante.