{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/it\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Codici di ridondanza: spieghiamo in parole semplici come conservare dati in modo sicuro ed economico","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Codici<\/p>\n

<\/p>\n

Cos'\u00e8 la ridondanza<\/em><\/p>\n

<\/p>\n

I codici di ridondanza* sono ampiamente utilizzati nei sistemi informatici per aumentare l'affidabilit\u00e0 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\u00e0. Tuttavia, nonostante la loro ampia diffusione, \u00e8 raro trovare una descrizione chiara di come funzionano i codici di ridondanza. Chi desidera capire si trova di fronte a quanto segue (da Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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

<\/p>\n

Non approfondir\u00f2 una serie di dettagli matematici, ma fornir\u00f2 dei rimandi per chi desidera approfondire. Inoltre, segnalo che alcune definizioni matematiche potrebbero non essere rigorose, poich\u00e9 l'articolo \u00e8 destinato non ai matematici, ma agli ingegneri che vogliono comprendere il senso della questione.<\/p>\n

<\/p>\n

* Nella letteratura anglofona, i codici di ridondanza sono spesso chiamati erasure codes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. La natura dei codici di ridondanza<\/h1>\n

<\/p>\n

Il concetto fondamentale di tutti i codici di ridondanza \u00e8 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.). <\/p>\n

<\/p>\n

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\u00e8 quelli in cui i dati sono suddivisi in blocchi.<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

Per ripristinare tutti i n blocchi di dati, \u00e8 necessario avere almeno n su n + m blocchi, poich\u00e9 non \u00e8 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.<\/p>\n

<\/p>\n

Archiviazione dei dati<\/h3>\n

<\/p>\n

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\u00f9 dischi.<\/p>\n

<\/p>\n

Trasmissione dati<\/h3>\n

<\/p>\n

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.<\/p>\n

<\/p>\n

* 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).<\/p>\n

<\/p>\n

2. Codici di Reed-Solomon<\/h1>\n

<\/p>\n

I codici di Reed-Solomon sono tra i codici di ridondanza pi\u00f9 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.<\/p>\n

<\/p>\n

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.
\nPer semplificare, d'ora in poi assumiamo che n=6 e m=4. Altre configurazioni possono essere considerate per analogia.<\/p>\n

<\/p>\n

Come creare blocchi di codici di ridondanza<\/h3>\n

<\/p>\n

Ogni blocco di codici di ridondanza \u00e8 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\u2013P4 sono i blocchi di codici di ridondanza.<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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.<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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:<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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. \u00c8 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.<\/p>\n

<\/p>\n

A cosa servono i campi di Galois<\/h3>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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\u00ec i blocchi di codici di ridondanza. In generale funziona cos\u00ec, ma il diavolo \u00e8 nei dettagli:<\/p>\n

<\/p>\n

    \n
  1. Come detto in precedenza, la dimensione della parola \u00e8 fissa, nel nostro esempio \u00e8 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.<\/li>\n
  2. 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\u00e0 un numero reale, che non pu\u00f2 essere rappresentato esattamente nella memoria del computer.<\/li>\n<\/ol>\n

    <\/p>\n

    Questi problemi non consentono di utilizzare numeri interi per i codici di Reed-Solomon. La soluzione al problema \u00e8 originale e pu\u00f2 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\u00e0 anch'esso rappresentato nella memoria del computer tramite parole di lunghezza appropriata.<\/p>\n

    <\/p>\n

    Questi \"numeri speciali\" sono stati studiati a lungo dalla matematica e sono noti come campi. Un campo \u00e8 un insieme di elementi con determinate operazioni di somma, differenza, moltiplicazione e divisione.<\/p>\n

    <\/p>\n

    I campi di Galois* sono campi per i quali esiste e \u00e8 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\u00e0 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 \u00e8 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.<\/p>\n

    <\/p>\n

    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, \u00e8 possibile eseguire il ripristino dei dati.<\/p>\n

    <\/p>\n

    * Questa non \u00e8 una definizione rigorosa, ma piuttosto una descrizione.<\/p>\n

    <\/p>\n

    Come recuperare i dati<\/h3>\n

    <\/p>\n

    Il ripristino \u00e8 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.<\/p>\n

    <\/p>\n

    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.<\/p>\n

    <\/p>\n

    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):<\/p>\n

    <\/p>\n

    \"Codici<\/p>\n

    <\/p>\n

    Abbiamo un sistema di 4 equazioni con 4 incognite, il che significa che possiamo risolverlo e ripristinare i dati!<\/p>\n

    <\/p>\n

    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):<\/p>\n

    <\/p>\n