{"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: spiegazioni semplici su come memorizzare dati in modo sicuro ed economico","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Codici<\/p>\n

<\/p>\n

Questa \u00e8 l'apparenza della ridondanza<\/em><\/p>\n

<\/p>\n

I codici di ridondanza* sono ampiamente utilizzati nei sistemi informatici per migliorare l'affidabilit\u00e0 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\u00e0. Ma nonostante la loro ampia diffusione, una descrizione comprensibile su come funzionano i codici di ridondanza \u00e8 molto rara. Coloro che desiderano capirlo si imbattono all'incirca in quanto segue (da Wikipedie<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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

<\/p>\n

Non approfondir\u00f2 una serie di dettagli matematici, ma fornir\u00f2 link per chi desidera approfondire. Inoltre, annoter\u00f2 che alcune definizioni matematiche potrebbero non essere rigorose, poich\u00e9 l'articolo \u00e8 indirizzato non ai matematici, ma agli ingegneri che desiderano capire il nocciolo della questione.<\/p>\n

<\/p>\n

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

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

1. L'essenza dei codici di ridondanza<\/h1>\n

<\/p>\n

L'essenza di tutti i codici di ridondanza \u00e8 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.). <\/p>\n

<\/p>\n

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

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

Per ripristinare tutti i n blocchi di dati, \u00e8 necessario avere almeno n da n + m blocchi, poich\u00e9 non \u00e8 possibile ottenere n blocchi avendo solo n-1 blocco (in questo caso sarebbe necessario prendere 1 blocco \"dal nulla\"). \u00c8 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.<\/p>\n

<\/p>\n

Archiviazione dati<\/h3>\n

<\/p>\n

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

<\/p>\n

Trasmissione dei dati<\/h3>\n

<\/p>\n

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

<\/p>\n

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

<\/p>\n

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.
\nPer semplificare, considereremo d'ora in poi che n=6 e m=4. Altri schemi saranno considerati per analogia.<\/p>\n

<\/p>\n

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

<\/p>\n

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\u2013P4 sono i blocchi di codici ridondanti.<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

Tutti i blocchi di dati devono avere la stessa dimensione; per allinearle \u00e8 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.<\/p>\n

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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

<\/p>\n

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

<\/p>\n

\"Codici<\/p>\n

<\/p>\n

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\u00ec, ma il diavolo \u00e8 nei dettagli:<\/p>\n

<\/p>\n

    \n
  1. Come detto sopra, la dimensione della parola \u00e8 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.<\/li>\n
  2. 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\u00e0 di eseguire divisioni tra numeri interi, il cui risultato sar\u00e0 un numero reale, che non pu\u00f2 essere rappresentato con precisione nella memoria del computer.<\/li>\n<\/ol>\n

    <\/p>\n

    Questi problemi impediscono l'uso di numeri interi per i codici Reed-Solomon. La soluzione al problema \u00e8 originale e pu\u00f2 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\u00e0 anch'esso rappresentato in memoria del computer tramite parole della lunghezza desiderata.<\/p>\n

    <\/p>\n

    Questi \"numeri speciali\" sono studiati da tempo dalla matematica e vengono chiamati campi. Un campo \u00e8 un insieme di elementi con operazioni di somma, sottrazione, moltiplicazione e divisione definite per loro.<\/p>\n

    <\/p>\n

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

    <\/p>\n

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

    <\/p>\n

    * Questa non \u00e8 una definizione rigorosa, pi\u00f9 un descrizione.<\/p>\n

    <\/p>\n

    Come recuperare i dati<\/h3>\n

    <\/p>\n

    Il recupero \u00e8 necessario quando, da n + m blocchi, parte dei blocchi \u00e8 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.<\/p>\n

    <\/p>\n

    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.<\/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 gruppo i di parole avremo il seguente sistema di equazioni (le variabili sconosciute sono segnate in rosso):<\/p>\n

    <\/p>\n

    \"Codici<\/p>\n

    <\/p>\n

    Abbiamo un sistema di 4 equazioni con 4 incognite, quindi possiamo risolverlo e recuperare i dati!<\/p>\n

    <\/p>\n

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

    <\/p>\n