Ecco come si presenta la ridondanza
I codici di ridondanza* sono ampiamente utilizzati nei sistemi informatici per aumentare l'affidabilità dell'archiviazione dei dati. In Yandex vengono utilizzati in molti progetti. Ad esempio, l'utilizzo di codici di ridondanza invece della replica nel nostro storage di oggetti interno consente di risparmiare milioni senza sacrificare l'affidabilità. Ma nonostante il loro uso diffuso, le descrizioni chiare di come funzionano i codici di ridondanza sono molto rare. Coloro che vogliono capire si trovano di fronte approssimativamente a quanto segue (da ):
Mi chiamo Vadim, in Yandex sto sviluppando MDS per l'archiviazione di oggetti interni. In questo articolo descriverò in parole semplici i fondamenti teorici dei codici di ridondanza (codici Reed-Solomon e LRC). Ti dirò come funziona, senza matematica complessa e termini rari. Alla fine fornirò esempi di utilizzo dei codici di ridondanza in Yandex.
Non prenderò in considerazione in dettaglio una serie di dettagli matematici, ma fornirò collegamenti per coloro che vogliono approfondire. Noterò anche che alcune definizioni matematiche potrebbero non essere rigorose, poiché l'articolo non è destinato ai matematici, ma agli ingegneri che vogliono comprendere l'essenza della questione.
* Nella letteratura in lingua inglese, i codici di ridondanza sono spesso chiamati codici di cancellazione.
1. L'essenza dei codici di ridondanza
L'essenza di tutti i codici di ridondanza è estremamente semplice: archiviare (o trasmettere) i dati in modo che non vadano persi quando si verificano errori (guasti del disco, errori di trasferimento dati, ecc.).
Nella maggior parte* dei codici di ridondanza, i dati sono divisi in n blocchi di dati, per i quali vengono contati m blocchi di codici di ridondanza, per un totale di n + m blocchi. I codici di ridondanza sono costruiti in modo tale che n blocchi di dati possano essere recuperati utilizzando solo una porzione di n + m blocchi. Successivamente prenderemo in considerazione solo i codici di ridondanza a blocchi, cioè quelli in cui i dati sono suddivisi in blocchi.
Per recuperare tutti gli n blocchi di dati, è necessario avere almeno n di n + m blocchi, poiché non è possibile ottenere n blocchi avendo solo n-1 blocco (in questo caso, dovresti prendere 1 blocco "dal thin" aria"). Sono sufficienti n blocchi casuali di n + m blocchi per recuperare tutti i dati? Ciò dipende dal tipo di codici di ridondanza, ad esempio, i codici Reed-Solomon consentono di recuperare tutti i dati utilizzando n blocchi arbitrari, ma i codici di ridondanza LRC non sempre lo fanno.
Archiviazione dei dati
Nei sistemi di archiviazione dati, di norma, ciascuno dei blocchi di dati e dei blocchi di codice di ridondanza viene scritto su un disco separato. Quindi, se un disco arbitrario si guasta, i dati originali possono ancora essere ripristinati e letti. I dati possono essere recuperati anche se più dischi si guastano contemporaneamente.
Trasferimento dati
I codici di ridondanza possono essere utilizzati per trasmettere dati in modo affidabile su una rete inaffidabile. I dati trasmessi vengono suddivisi in blocchi e per essi vengono calcolati i codici di ridondanza. Sia i blocchi di dati che i blocchi di codice di ridondanza vengono trasmessi sulla rete. Se si verificano errori in blocchi arbitrari (fino a un certo numero di blocchi), i dati possono comunque essere trasmessi sulla rete senza errori. I codici Reed-Solomon, ad esempio, vengono utilizzati per trasmettere dati su linee di comunicazione ottica e nelle comunicazioni satellitari.
* Esistono anche codici di ridondanza in cui i dati non sono divisi in blocchi, come i codici Hamming e i codici CRC, che sono ampiamente utilizzati per la trasmissione dei dati nelle reti Ethernet. Si tratta di codici per la codifica di correzione degli errori, sono progettati per rilevare gli errori e non per correggerli (il codice Hamming consente anche la correzione parziale degli errori).
2. Codici Reed-Solomon
I codici Reed-Solomon sono uno dei codici di ridondanza più utilizzati, inventati negli anni '1960 e ampiamente utilizzati per la prima volta negli anni '1980 per la produzione di massa di compact disc.
Ci sono due domande chiave per comprendere i codici Reed-Solomon: 1) come creare blocchi di codici di ridondanza; 2) come recuperare i dati utilizzando blocchi di codice di ridondanza. Troviamo le risposte a loro.
Per semplicità, assumeremo inoltre che n=6 e m=4. Altri schemi sono considerati per analogia.
Come creare blocchi di codice ridondanti
Ogni blocco di codici di ridondanza viene conteggiato indipendentemente dagli altri. Tutti gli n blocchi di dati vengono utilizzati per contare ciascun blocco. Nello schema seguente, X1-X6 sono blocchi dati, P1-P4 sono blocchi di codice ridondanti.
Tutti i blocchi di dati devono avere la stessa dimensione e per l'allineamento è possibile utilizzare bit zero. I blocchi di codice di ridondanza risultanti avranno le stesse dimensioni dei blocchi di dati. Tutti i blocchi dati sono divisi in parole (ad esempio 16 bit). Diciamo di dividere i blocchi di dati in k parole. Quindi anche tutti i blocchi di codici di ridondanza verranno divisi in k parole.
Per contare la i-esima parola di ciascun blocco di ridondanza, verranno utilizzate le i-esime parole di tutti i blocchi dati. Verranno calcolati secondo la seguente formula:
Qui i valori x sono le parole dei blocchi di dati, p sono le parole dei blocchi di codice di ridondanza, tutti alfa, beta, gamma e delta sono numeri appositamente selezionati che sono uguali per tutti i. Va detto subito che tutti questi valori non sono numeri ordinari, ma elementi del campo di Galois; le operazioni +, -, *, / non sono operazioni familiari a tutti noi, ma operazioni speciali introdotte sugli elementi del campo di Galois campo.
Perché sono necessari i campi di Galois?
Sembrerebbe che tutto sia semplice: dividiamo i dati in blocchi, i blocchi in parole, usando le parole dei blocchi di dati contiamo le parole dei blocchi di codice di ridondanza - otteniamo blocchi di codice di ridondanza. In generale è così che funziona, ma il diavolo è nei dettagli:
- Come detto sopra, la dimensione della parola è fissa, nel nostro esempio 16 bit. Le formule precedenti per i codici Reed-Solomon sono tali che quando si utilizzano interi ordinari, il risultato del calcolo di p potrebbe non essere rappresentabile utilizzando una parola di dimensione valida.
- Durante il recupero dei dati, le formule di cui sopra verranno considerate come un sistema di equazioni che deve essere risolto per recuperare i dati. Durante il processo di soluzione, potrebbe essere necessario dividere i numeri interi tra loro, ottenendo così un numero reale che non può essere rappresentato accuratamente nella memoria del computer.
Questi problemi impediscono l'uso di numeri interi per i codici Reed-Solomon. La soluzione al problema è originale, può essere descritta come segue: inventiamo numeri speciali che possono essere rappresentati utilizzando parole della lunghezza richiesta (ad esempio 16 bit) e il risultato dell'esecuzione di tutte le operazioni su cui (addizione , sottrazione, moltiplicazione, divisione) verranno presentati anche nella memoria del computer utilizzando parole della lunghezza richiesta.
Tali numeri “speciali” sono stati studiati dalla matematica per molto tempo e sono chiamati campi. Un campo è un insieme di elementi per i quali sono definite le operazioni di addizione, sottrazione, moltiplicazione e divisione.
I campi Galois* sono campi per i quali esiste un risultato univoco 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 in pratica siamo interessati solo alle potenze di 2). Ad esempio, per le parole a 16 bit, questo è un campo contenente 65 elementi, per ciascuna coppia dei quali è possibile trovare il risultato di qualsiasi operazione (+, -, *, /). I valori di x, p, alfa, beta, gamma, delta delle equazioni sopra saranno considerati elementi del campo di Galois per i calcoli.
Abbiamo quindi un sistema di equazioni con cui possiamo costruire blocchi di codici di ridondanza scrivendo un programma per computer appropriato. Utilizzando lo stesso sistema di equazioni, puoi eseguire il ripristino dei dati.
* Questa non è una definizione rigorosa, ma piuttosto una descrizione.
Come recuperare i dati
Il restauro è necessario quando mancano alcuni degli n + m blocchi. Questi possono essere sia blocchi di dati che blocchi di codice di ridondanza. L'assenza di blocchi di dati e/o blocchi di codice di ridondanza significherà che le corrispondenti variabili x e/o p sono sconosciute nelle equazioni di cui sopra.
Le equazioni per i codici Reed-Solomon possono essere viste come un sistema di equazioni in cui tutti i valori alfa, beta, gamma, delta sono costanti, tutti x e p corrispondenti ai blocchi disponibili sono variabili note e i restanti x e p sono sconosciuti.
Ad esempio, se i blocchi dati 1, 2, 3 e il blocco codice di ridondanza 2 non sono disponibili, per l'i-esimo gruppo di parole ci sarà il seguente sistema di equazioni (le incognite sono contrassegnate 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 seguono una serie di conclusioni sul recupero dei dati per i codici Reed-Solomon (n blocchi di dati, m blocchi di codice di ridondanza):
- I dati possono essere recuperati se vengono persi m blocchi o meno. Se si perdono m+1 o più blocchi, i dati non possono essere ripristinati: è impossibile risolvere un sistema di m equazioni con m + 1 incognite.
- Per recuperare anche un solo blocco di dati, è necessario utilizzare n qualsiasi dei blocchi rimanenti ed è possibile utilizzare qualsiasi codice di ridondanza.
Cos'altro ho bisogno di sapere?
Nella descrizione sopra, evito una serie di questioni importanti che richiedono un'immersione più profonda nella matematica per essere prese in considerazione. In particolare non dico nulla su quanto segue:
- Il sistema di equazioni per i codici di Reed-Solomon deve avere una soluzione (unica) per qualsiasi combinazione di incognite (non più di m incognite). In base a questo requisito vengono selezionati i valori di alfa, beta, gamma e delta.
- Un sistema di equazioni deve poter essere costruito automaticamente (a seconda di quali blocchi non sono disponibili) e risolto.
- Dobbiamo costruire un campo Galois: per una data dimensione di parola, essere in grado di trovare il risultato di qualsiasi operazione (+, -, *, /) per due elementi qualsiasi.
Alla fine dell'articolo sono presenti riferimenti alla letteratura su questi importanti temi.
Scelta di n e m
Come scegliere n e m in 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 una serie di fattori, tra cui:
- Affidabilità dell'archiviazione dei dati. Maggiore è m, maggiore è il numero di guasti del disco a cui è possibile sopravvivere, ovvero maggiore è l'affidabilità.
- Archiviazione ridondante. Maggiore è il rapporto m/n, maggiore sarà la ridondanza dello storage e più costoso sarà il sistema.
- Richiedi tempo di elaborazione. Maggiore è la somma n+m, maggiore sarà il tempo di risposta alle richieste. Poiché la lettura dei dati (durante il ripristino) richiede la lettura di n blocchi archiviati su n dischi diversi, il tempo di lettura sarà determinato dal disco più lento.
Inoltre, la memorizzazione dei dati in più DC impone ulteriori restrizioni sulla scelta di n e m: se 1 DC è spento, i dati devono essere ancora disponibili per la lettura. Ad esempio, quando si memorizzano i dati in 3 DC, deve essere soddisfatta la seguente condizione: m >= n/2, altrimenti potrebbe verificarsi una situazione in cui i dati non sono disponibili per la lettura quando 1 DC è spento.
3. LRC - Codici di ricostruzione locale
Per recuperare i dati utilizzando i codici Reed-Solomon, è necessario utilizzare n blocchi di dati arbitrari. Questo è uno svantaggio molto significativo per i sistemi di archiviazione dati distribuiti, perché per ripristinare i dati su un disco rotto, dovrai leggere i dati dalla maggior parte degli altri, creando un grande carico aggiuntivo sui dischi e sulla rete.
Gli errori più comuni sono l'inaccessibilità di un blocco di dati a causa di un guasto o di un sovraccarico di un disco. È possibile ridurre in qualche modo il carico in eccesso per il ripristino dei dati in questo caso (più comune)? Si scopre che è possibile: esistono codici di ridondanza LRC specifici per questo scopo.
Gli LRC (Local Reconstruction Codes) sono codici di ridondanza inventati da Microsoft per l'utilizzo in Windows Azure Storage. L'idea di LRC è la più semplice possibile: dividere tutti i blocchi di dati in due (o più) gruppi e leggere separatamente parte dei blocchi di codice di ridondanza per ciascun gruppo. Quindi alcuni blocchi di codice di ridondanza verranno conteggiati utilizzando tutti i blocchi di dati (in LRC sono chiamati codici di ridondanza globali) e alcuni - utilizzando uno dei due gruppi di blocchi di dati (sono chiamati codici di ridondanza locali).
LRC è indicato da tre numeri: nrl, dove n è il numero di blocchi di dati, r è il numero di blocchi di codice di ridondanza globale, l è il numero di blocchi di codice di ridondanza locale. Per leggere i dati quando un blocco dati non è disponibile, è necessario leggere solo n/l blocchi: questo è l volte inferiore rispetto ai codici Reed-Solomon.
Ad esempio, considera lo schema LRC 6-2-2. X1–X6 — 6 blocchi dati, P1, P2 — 2 blocchi di ridondanza globale, P3, P4 — 2 blocchi di ridondanza locale.
I blocchi di codice di ridondanza P1, P2 vengono conteggiati utilizzando tutti i blocchi dati. Blocco di codice ridondante P3 - utilizzando i blocchi dati X1-X3, blocco di codice ridondante P4 - utilizzando i blocchi dati X4-X6.
Il resto viene fatto in LRC per analogia con i codici Reed-Solomon. Le equazioni per il conteggio delle parole dei blocchi di codice di ridondanza saranno:
Per selezionare i numeri alfa, beta, gamma, delta, è necessario soddisfare una serie di condizioni per garantire la possibilità di recupero dei dati (ovvero, risolvere il sistema di equazioni). Puoi leggere di più su di loro in .
Anche in pratica l'operazione XOR viene utilizzata per calcolare i codici di ridondanza locale P3, P4.
Dal sistema di equazioni per LRC derivano numerose conclusioni:
- Per recuperare 1 blocco dati qualsiasi è sufficiente leggere n/l blocchi (n/2 nel nostro esempio).
- Se i blocchi r + l non sono disponibili e tutti i blocchi sono inclusi in un gruppo, i dati non possono essere ripristinati. Questo è facile da spiegare con un esempio. Lasciamo che i blocchi X1–X3 e P3 non siano disponibili: questi sono r + l blocchi dello stesso gruppo, 4 nel nostro caso. Allora abbiamo un sistema di 3 equazioni con 4 incognite che non possono essere risolte.
- In tutti gli altri casi di indisponibilità dei blocchi r+l (quando è disponibile almeno un blocco per ogni gruppo), i dati nell'LRC possono essere ripristinati.
Pertanto, LRC supera i codici Reed-Solomon nel recupero dei dati dopo singoli errori. Nei codici Reed-Solomon, per recuperare anche un solo blocco di dati, è necessario utilizzare n blocchi, mentre in LRC, per recuperare un blocco di dati, è sufficiente utilizzare n/l blocchi (n/2 nel nostro esempio). D'altra parte, LRC è inferiore ai codici Reed-Solomon in termini di numero massimo di errori consentiti. Negli esempi precedenti, i codici Reed-Solomon possono recuperare i dati per 4 errori qualsiasi e per LRC ci sono 2 combinazioni di 4 errori quando i dati non possono essere recuperati.
Ciò che è più importante dipende dalla situazione specifica, ma spesso il risparmio sul carico in eccesso offerto da LRC supera lo storage leggermente meno affidabile.
4. Altri codici di ridondanza
Oltre ai codici Reed-Solomon e LRC, esistono molti altri codici di ridondanza. Diversi codici di ridondanza utilizzano matematiche diverse. Ecco alcuni altri codici di ridondanza:
- Codice di ridondanza che utilizza l'operatore XOR. L'operazione XOR viene eseguita su n blocchi dati e si ottiene 1 blocco di codici di ridondanza, cioè uno schema n+1 (n blocchi dati, 1 codice di ridondanza). Usato in , dove blocchi di dati e codici di ridondanza vengono scritti ciclicamente su tutti i dischi dell'array.
- Algoritmo pari-dispari basato sull'operazione XOR. Permette di costruire 2 blocchi di codici di ridondanza, ovvero lo schema n+2.
- Algoritmo STAR basato sull'operazione XOR. Permette di costruire 3 blocchi di codici di ridondanza, ovvero lo schema n+3.
- I codici Pyramide sono altri codici di ridondanza di Microsoft.
5. Utilizzare in Yandex
Numerosi progetti infrastrutturali Yandex utilizzano codici di ridondanza per l'archiviazione affidabile dei dati. Ecco alcuni esempi:
- Archiviazione di oggetti interni MDS, di cui ho scritto all'inizio dell'articolo.
- — Sistema MapReduce di Yandex.
- (Yandex DataBase) - database distribuito NewSQL.
MDS utilizza i codici di ridondanza LRC, schema 8-2-2. I dati con codici di ridondanza vengono scritti su 12 dischi diversi in server diversi in 3 controller di dominio diversi: 4 server in ciascun controller di dominio. Maggiori informazioni su questo argomento in .
YT utilizza sia i codici Reed-Solomon (Schema 6-3), che sono stati i primi a implementare, sia i codici di ridondanza LRC (Schema 12-2-2), dove LRC è il metodo di archiviazione preferito.
YDB utilizza codici di ridondanza basati su pari-dispari (Figura 4-2). Già sui codici di ridondanza in YDB .
L'uso di diversi schemi di codici di ridondanza è dovuto ai diversi requisiti dei sistemi. Ad esempio, in MDS, i dati archiviati utilizzando LRC vengono inseriti in 3 controller di dominio contemporaneamente. Per noi è importante che i dati rimangano disponibili per la lettura se 1 qualsiasi DC si guasta, pertanto i blocchi devono essere distribuiti tra i DC in modo che se qualche DC non è disponibile, il numero di blocchi inaccessibili non è superiore a quello consentito. Nello schema 8-2-2, puoi posizionare 4 blocchi in ciascuna DC, quindi quando una qualsiasi DC viene disattivata, 4 blocchi non saranno disponibili e i dati potranno essere letti. Qualunque sia lo schema scelto per posizionarlo in 3 DC, in ogni caso dovrebbe esserci (r + l) / n >= 0,5, ovvero la ridondanza di archiviazione sarà almeno del 50%.
In YT la situazione è diversa: ogni cluster YT è interamente situato in 1 DC (cluster diversi in DC diversi), quindi non esiste tale restrizione. Lo schema 12-2-2 fornisce una ridondanza del 33%, ovvero l'archiviazione dei dati è più economica e può anche sopravvivere fino a 4 interruzioni simultanee del disco, proprio come lo schema MDS.
Esistono molte altre funzionalità dell'uso dei codici di ridondanza nei sistemi di archiviazione ed elaborazione dei dati: sfumature del recupero dei dati, impatto del ripristino sul tempo di esecuzione delle query, funzionalità della registrazione dei dati, ecc. Parlerò separatamente di queste e di altre funzionalità dell'uso pratico dei codici di ridondanza, se l'argomento risulterà interessante.
6. Collegamenti
- Una serie di articoli sui codici Reed-Solomon e sui campi di Galois:
Danno uno sguardo più approfondito alla matematica in un linguaggio accessibile. - Articolo di Microsoft su LRC:
La sezione 2 spiega brevemente la teoria e poi discute le esperienze pratiche con LRC. - Schema pari-dispari:
- Schema STELLA:
- Codici piramidali:
- Codici di ridondanza in MDS:
- Codici di ridondanza in YT:
- Codici di ridondanza in YDB:
Fonte: habr.com