Cos'è la ridondanza

I codici di ridondanza* sono ampiamente utilizzati nei sistemi informatici per aumentare l'affidabilità della memorizzazione dei dati. In Yandex, vengono utilizzati in molti progetti. Ad esempio, l'uso dei codici di ridondanza invece della replicazione nel nostro archivio oggetti interno consente di risparmiare milioni senza compromettere l'affidabilità. Tuttavia, nonostante la loro ampia diffusione, è raro trovare una descrizione chiara di come funzionano i codici di ridondanza. Chi desidera capire si trova di fronte a quanto segue (da Wikipedia):

Mi chiamo Vadim, e in Yandex mi occupo dello sviluppo dell'archivio oggetti interno MDS. In questo articolo, spiegherò con parole semplici le basi teoriche dei codici di ridondanza (codici di Reed-Solomon e LRC). Racconterò come funziona, senza complicate formule matematiche e termini rari. Alla fine, fornirò esempi dell'uso dei codici di ridondanza in Yandex.

Non approfondirò una serie di dettagli matematici, ma fornirò dei rimandi per chi desidera approfondire. Inoltre, segnalo che alcune definizioni matematiche potrebbero non essere rigorose, poiché l'articolo è destinato non ai matematici, ma agli ingegneri che vogliono comprendere il senso della questione.

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

1. La natura dei codici di ridondanza

Il concetto fondamentale di tutti i codici di ridondanza è estremamente semplice: conservare (o trasmettere) i dati in modo che non vadano 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, da cui 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 di n + m blocchi. In seguito considereremo solo i codici di ridondanza a blocchi, cioè quelli in cui i dati sono suddivisi in blocchi.

Per ripristinare tutti i n blocchi di dati, è necessario avere almeno n su n + m blocchi, poiché non è possibile ottenere n blocchi avendo solo n-1 blocco (in questo caso si dovrebbe prendere 1 blocco 'dal nulla'). Sono sufficienti n blocchi a caso da n + m blocchi per ripristinare tutti i dati? Questo dipende dal tipo di codici di ridondanza; ad esempio, i codici Reed-Solomon consentono di ripristinare tutti i dati con n blocchi a caso, mentre i codici di ridondanza LRC non sempre lo permettono.

Archiviazione dei dati

Nei sistemi di archiviazione dei dati, generalmente, ciascuno dei blocchi di dati e dei blocchi di codici di ridondanza viene registrato su un disco separato. Pertanto, in caso di guasto di un disco qualsiasi, i dati originali possono comunque essere ripristinati e letti. I dati possono essere ripristinati anche in caso di guasto simultaneo di più dischi.

Trasmissione dati

I codici di ridondanza possono essere utilizzati per la trasmissione affidabile dei dati su reti inaffidabili. I dati trasmessi vengono suddivisi in blocchi, e per ciascun blocco vengono calcolati i codici di ridondanza. Sia i blocchi di dati che quelli di codici di ridondanza vengono trasmessi attraverso la rete. In caso di errori in blocchi arbitrari (fino a un certo numero di blocchi), i dati possono comunque essere trasmessi senza errori attraverso la rete. I codici di Reed-Solomon, ad esempio, sono utilizzati per la trasmissione di dati su linee ottiche e nelle comunicazioni satellitari.

* Esistono anche codici di ridondanza in cui i dati non vengono suddivisi in blocchi, come i codici di Hamming e i codici CRC, ampiamente utilizzati per la trasmissione di dati nelle reti Ethernet. Questi sono codici per la codifica a prova di errore, progettati per la rilevazione degli errori, non per la loro correzione (il codice di Hamming consente anche di correggere parzialmente gli errori).

2. Codici di Reed-Solomon

I codici di Reed-Solomon sono tra i codici di ridondanza più diffusi, inventati negli anni '60 e adottati per la prima volta su larga scala negli anni '80 per la produzione in serie di dischi compatti.

Le questioni chiave per comprendere i codici Reed-Solomon sono due: 1) come creare blocchi di codici di ridondanza; 2) come recuperare dati tramite i blocchi di codici di ridondanza. Troveremo le risposte a queste domande.
Per semplificare, d'ora in poi assumiamo che n=6 e m=4. Altre configurazioni possono essere considerate per analogia.

Come creare blocchi di codici di ridondanza

Ogni blocco di codici di ridondanza è considerato indipendente dagli altri. Per calcolare ogni blocco si utilizzano tutti i n blocchi di dati. Nello schema sottostante, X1-X6 rappresentano i blocchi di dati, P1–P4 sono i blocchi di codici di ridondanza.

Tutti i blocchi di dati devono essere della stessa dimensione; per l'allineamento si possono utilizzare bit zero. I blocchi di codici di ridondanza ottenuti avranno la stessa dimensione dei blocchi di dati. Tutti i blocchi di dati vengono suddivisi in parole (ad esempio, di 16 bit). Supponiamo che abbiamo suddiviso i blocchi di dati in k parole. Allora tutti i blocchi di codici di ridondanza saranno anch'essi suddivisi in k parole.

Per il calcolo della i-esima parola di ciascun blocco di ridondanza si utilizzeranno le i-esime parole di tutti i blocchi di dati. Esse verranno calcolate secondo la seguente formula:

Qui valori x sono parole dei blocchi di dati, p sono parole dei blocchi di codici di ridondanza, tutti alpha, beta, gamma e delta sono numeri scelti in modo particolare, identici per tutti i i. È necessario dire subito che tutti questi valori non sono numeri normali, ma elementi di un campo di Galois, le operazioni +, -, *, / non sono le operazioni a cui siamo abituati, ma operazioni speciali definite sugli elementi di un campo di Galois.

A cosa servono i campi di Galois

Potrebbe sembrare tutto semplice: dividiamo i dati in blocchi, i blocchi in parole, e usando le parole dei blocchi di dati calcoliamo le parole dei blocchi di codici di ridondanza, ottenendo così i blocchi di codici di ridondanza. In generale funziona così, ma il diavolo è nei dettagli:

Come detto in precedenza, la dimensione della parola è fissa, nel nostro esempio è di 16 bit. Le formule sopra per i codici di Reed-Solomon sono tali che, utilizzando numeri interi normali, il risultato del calcolo p potrebbe non essere rappresentabile con una parola di dimensione valida.
Nel ripristino dei dati, le formule di cui sopra saranno considerate come un sistema di equazioni da risolvere per recuperare i dati. Durante il processo di risoluzione, potrebbe rendersi necessario eseguire la divisione tra numeri interi, il cui risultato sarà un numero reale, che non può essere rappresentato esattamente nella memoria del computer.

Questi problemi non consentono di utilizzare numeri interi per i codici di Reed-Solomon. La soluzione al problema è originale e può essere descritta come segue: inventiamo numeri speciali che possano essere rappresentati usando parole di lunghezza appropriata (ad esempio, 16 bit), e il risultato di tutte le operazioni su di essi (somma, differenza, moltiplicazione, divisione) sarà anch'esso rappresentato nella memoria del computer tramite parole di lunghezza appropriata.

Questi "numeri speciali" sono stati studiati a lungo dalla matematica e sono noti come campi. Un campo è un insieme di elementi con determinate operazioni di somma, differenza, moltiplicazione e divisione.

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

In questo modo, abbiamo un sistema di equazioni attraverso il quale possiamo costruire blocchi di codici di ridondanza scrivendo il relativo programma informatico. Utilizzando questo stesso sistema di equazioni, è possibile eseguire il ripristino dei dati.

* Questa non è una definizione rigorosa, ma piuttosto una descrizione.

Come recuperare i dati

Il ripristino è necessario quando, da n + m blocchi, alcuni blocchi sono assenti. 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 non sono conosciute.

Le equazioni per i codici di Reed-Solomon possono essere considerate come un sistema di equazioni in cui tutti i valori alpha, beta, gamma, delta sono costanti, tutte le x e p, corrispondenti ai blocchi disponibili, sono variabili note, 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 i-esimo gruppo di parole avremo il seguente sistema di equazioni (le sconosciute sono evidenziate in rosso):

Abbiamo un sistema di 4 equazioni con 4 incognite, il che significa che possiamo risolverlo e ripristinare i dati!

Da questo sistema di equazioni derivano alcune conclusioni sul ripristino 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 un massimo di m blocchi. Con la perdita di m+1 o più blocchi, 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, utilizzando qualsiasi dei codici di ridondanza.

Cosa c'è altro da sapere

Nella descrizione sopra, evito di trattare una serie di questioni importanti che richiederebbero un'analisi più approfondita della matematica. In particolare, non dico nulla riguardo a quanto segue:

Il sistema di equazioni per i codici di Reed-Solomon deve avere una (unica) soluzione per qualsiasi combinazione di incognite (non più di m incognite). Da questo requisito si scelgono i valori di alfa, beta, gamma e delta.
È necessario saper costruire automaticamente il sistema di equazioni (in base ai blocchi non disponibili) e risolverlo.
Deve essere costruito un campo di Galois: per una data dimensione della parola, saper trovare il risultato di qualsiasi operazione (+, -, *, /) per qualsiasi coppia di elementi.

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

Scelta di n e m

Come scegliere concretamente n e m? Nelle pratiche nei sistemi di archiviazione, i codici di ridondanza vengono utilizzati per risparmiare spazio, quindi si sceglie sempre m minore di n. I loro valori specifici dipendono da vari fattori, tra cui:

Affidabilità dell'archiviazione dei dati. Maggiore è m, maggiori sono i guasti ai dischi che possono essere tollerati, quindi l'affidabilità aumenta.
Ridondanza di archiviazione. Maggiore è il rapporto m / n, maggiore sarà la ridondanza di archiviazione e più costosa sarà la sistemazione.
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 ripristino) è necessario leggere n blocchi su n dischi diversi, il tempo di lettura sarà determinato dal disco più lento.

Inoltre, archiviare i dati in più DC impone ulteriori restrizioni sulla scelta di n e m: se un DC viene disattivato, i dati devono ancora essere accessibili per la lettura. Ad esempio, se i dati sono archiviati in 3 DC, deve essere rispettata la condizione: m >= n/2, altrimenti c'è il rischio che i dati non siano accessibili per la lettura in caso di disattivazione di 1 DC.

3. LRC — Local Reconstruction Codes

Per ripristinare i dati con i codici Reed-Solomon è necessario utilizzare n blocchi di dati arbitrari. Questo è un grosso svantaggio per i sistemi di storage distribuiti, poiché per il recupero dei dati da un disco guasto è necessario leggere i dati dalla maggior parte degli altri, creando così un carico aggiuntivo significativo sui dischi e sulla rete.

Gli errori più comuni comprendono l'inaccessibilità di un blocco di dati a causa di un guasto o dell'eccessivo carico di un disco. Esiste un modo per ridurre il carico eccessivo durante il recupero dei dati in questo (il caso più comune)? A quanto pare, sì: i codici di ridondanza LRC sono stati creati appositamente per questo scopo.

LRC (Local Reconstruction Codes) — codici di ridondanza sviluppati da Microsoft per l'uso in Windows Azure Storage. L'idea alla base dell'LRC è molto 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 sarà calcolata utilizzando tutti i blocchi di dati (in LRC sono chiamati codici di ridondanza globali), mentre l'altra parte sarà calcolata utilizzando uno dei due gruppi di blocchi di dati (chiamati codici di ridondanza locali).

LRC è rappresentato da tre numeri: n-r-l, dove n è il numero di blocchi di dati, r è il numero di blocchi di codici di ridondanza globali, e l è il numero di blocchi di codici di ridondanza locali. Per leggere i dati quando un blocco di dati non è disponibile, è necessario leggere solo n/l blocchi — questo è l/i volte inferiore rispetto ai codici di Reed-Solomon.

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

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

Il resto è gestito in LRC in modo analogo ai codici di Reed-Solomon. Le equazioni per il calcolo delle parole nei blocchi di codici di ridondanza sono le seguenti:

Per determinare i valori alpha, beta, gamma, delta è necessario soddisfare una serie di condizioni che garantiscano la possibilità di recuperare i dati (cioè la soluzione del sistema di equazioni). Per maggiori dettagli, si può leggere in articolo.
In pratica, per il calcolo dei codici di ridondanza locali P3 e P4 si applica anche l'operazione XOR.

Dal sistema di equazioni per LRC derivano una serie di 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 è facilmente spiegabile con un esempio. Supponiamo che i blocchi X1–X3 e P3 non siano disponibili: questi sono r + l blocchi di un unico gruppo, 4 nel nostro caso. Abbiamo quindi un sistema di 3 equazioni con 4 incognite, che non può essere risolto.
Nei restanti casi di indisponibilità dei blocchi r + l (quando almeno un blocco è disponibile in ogni gruppo) i dati nell'LRC possono essere recuperati.

Così, l'LRC supera i codici di Reed-Solomon nel recupero dei dati dopo errori singoli. Nei codici di Reed-Solomon, per recuperare anche un solo blocco di dati è necessario utilizzare n blocchi, mentre nell'LRC per recuperare un blocco di dati è sufficiente utilizzare n/l blocchi (n/2 nel nostro esempio). D'altro canto, l'LRC è svantaggiato rispetto ai codici di Reed-Solomon per il numero massimo di errori tollerabili. Negli esempi sopra, i codici di Reed-Solomon possono recuperare i dati con qualsiasi 4 errori, mentre per l'LRC esistono 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 in carico ridondante offerto dall'LRC supera una leggera minore affidabilità del storage.

4. Altri codici di ridondanza

Oltre ai codici di Reed-Solomon e all'LRC, ci sono molti altri codici di ridondanza. Diversi codici di ridondanza utilizzano matematiche diverse. Ecco alcuni altri codici di ridondanza:

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

5. Utilizzo in Yandex

Diversi progetti infrastrutturali di Yandex applicano i codici di ridondanza per un'archiviazione dati sicura. Ecco alcuni esempi:

L'archivio oggetti interno MDS, di cui ho parlato all'inizio dell'articolo.
YT — Sistema MapReduce di Yandex.
YDB (Yandex DataBase) — database distribuito newSQL.

In MDS vengono utilizzati codici di ridondanza LRC, schema 8-2-2. I dati con i codici di ridondanza vengono scritti su 12 dischi diversi in server diversi in 3 diversi DC: 4 server in ogni DC. Maggiori dettagli su questo puoi trovarli in articolo.

In YT si utilizzano sia i codici Reed-Solomon (schema 6-3), che sono stati implementati per primi, sia i codici di ridondanza LRC (schema 12-2-2), con LRC come metodo di archiviazione preferito.

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

L'uso di diverse schemi di codici di ridondanza è determinato dalle diverse esigenze richieste dai sistemi. Ad esempio, nei MDS i dati archiviati tramite LRC sono distribuiti immediatamente in 3 DC. È fondamentale che i dati rimangano leggibili anche in caso di guasto di uno qualsiasi dei DC, quindi i blocchi devono essere distribuiti tra i DC in modo che, con la non disponibilità di uno qualsiasi di essi, il numero di blocchi non disponibili non superi il limite consentito. Nello schema 8-2-2 è possibile collocare 4 blocchi in ciascun DC, quindi, disattivando uno dei DC, saranno non disponibili 4 blocchi, e i dati potranno ancora essere letti. Qualunque schema scegliamo per la distribuzione nei 3 DC, deve comunque valere (r + l) / n >= 0,5, ossia la ridondanza di archiviazione sarà almeno del 50%.

In YT, the situation is different: each YT cluster is entirely located in one data center (different clusters in different data centers), so there is no such restriction. The 12-2-2 scheme provides 33% redundancy, meaning data storage is cheaper, and it can also withstand up to 4 simultaneous disk failures, just like the scheme in MDS.

There are many other specific features of applying redundancy codes in data storage and processing systems: nuances of data recovery, the impact of recovery on query execution time, specifics of data writing, etc. I plan to discuss these and other practical aspects of redundancy codes separately, if the topic is of interest.