{"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\/ro\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Coduri de redundan\u021b\u0103: explicate simplu despre cum s\u0103 stochezi datele \u00een mod sigur \u0219i ieftin","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Coduri<\/p>\n

<\/p>\n

Iat\u0103 cum arat\u0103 redundan\u021ba<\/em><\/p>\n

<\/p>\n

Codurile de redundan\u021b\u0103* sunt larg utilizate \u00een sistemele de calcul pentru a cre\u0219te fiabilitatea stoc\u0103rii datelor. La Yandex, ele sunt folosite \u00een foarte multe proiecte. De exemplu, utilizarea codurilor de redundan\u021b\u0103 \u00een locul replic\u0103rii \u00een depozitul nostru intern de obiecte economise\u0219te milioane f\u0103r\u0103 a reduce fiabilitatea. Totu\u0219i, \u00een ciuda r\u0103sp\u00e2ndirii largi, o descriere clar\u0103 a modului \u00een care func\u021bioneaz\u0103 codurile de redundan\u021b\u0103 este destul de rar \u00eent\u00e2lnit\u0103. Cei care doresc s\u0103 \u00een\u021beleag\u0103 se confrunt\u0103 cu ceva de genul (din Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

M\u0103 numesc Vadim, la Yandex m\u0103 ocup de dezvoltarea depozitului intern de obiecte MDS. \u00cen acest articol voi descrie, \u00een cuvinte simple, fundamentele teoretice ale codurilor de redundan\u021b\u0103 (codurile Reed-Solomon \u0219i LRC). Voi explica cum func\u021bioneaz\u0103, f\u0103r\u0103 matematic\u0103 complex\u0103 \u0219i termeni rari. La final, voi prezenta exemple de utilizare a codurilor de redundan\u021b\u0103 la Yandex.<\/p>\n

<\/p>\n

O serie de detalii matematice nu le voi examina \u00een detaliu, dar voi oferi linkuri pentru cei care doresc s\u0103 aprofundeze subiectul. De asemenea, a\u0219 remarca faptul c\u0103 unele defini\u021bii matematice pot s\u0103 nu fie stricte, deoarece articolul este destinat nu matematicienilor, ci inginerilor care doresc s\u0103 \u00een\u021beleag\u0103 esen\u021ba problemei.<\/p>\n

<\/p>\n

* \u00cen literatura \u00een limba englez\u0103, codurile de redundan\u021b\u0103 sunt adesea numite erasure codes.<\/p>\n

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

1. Esen\u021ba codurilor de redundan\u021b\u0103<\/h1>\n

<\/p>\n

Esen\u021ba tuturor codurilor de redundan\u021b\u0103 este extrem de simpl\u0103: a stoca (sau a transmite) date astfel \u00eenc\u00e2t s\u0103 nu se piard\u0103 \u00een caz de erori (defec\u021biuni ale discurilor, erori de transmisie a datelor etc.). <\/p>\n

<\/p>\n

\u00cen majoritatea* codurilor de redundan\u021b\u0103, datele sunt \u00eemp\u0103r\u021bite \u00een n blocuri de date, pentru care se consider\u0103 m blocuri de coduri de redundan\u021b\u0103, astfel rezult\u00e2nd \u00een total n + m blocuri. Codurile de redundan\u021b\u0103 sunt construite astfel \u00eenc\u00e2t s\u0103 permit\u0103 recuperarea n blocuri de date, folosind doar o parte din n + m blocuri. \u00cen continuare, ne vom concentra doar pe codurile de redundan\u021b\u0103 pe blocuri, adic\u0103 pe cele \u00een care datele sunt \u00eemp\u0103r\u021bite \u00een blocuri.<\/p>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

Pentru a restaura toate n blocuri de date, este necesar s\u0103 ave\u021bi minimum n din n + m blocuri, deoarece nu este posibil s\u0103 ob\u021bine\u021bi n blocuri av\u00e2nd doar n-1 bloc (\u00een acest caz, ar trebui s\u0103 lua\u021bi 1 bloc \u201edin aer\u201d). Sunt suficiente n blocuri arbitrare din n + m blocuri pentru a restaura toate datele? Aceasta depinde de tipul de coduri de redundan\u021b\u0103, de exemplu, codurile Reed-Solomon permit restaurarea tuturor datelor cu ajutorul n blocuri arbitrare, \u00een timp ce codurile de redundan\u021b\u0103 LRC - nu \u00eentotdeauna.<\/p>\n

<\/p>\n

Stocarea datelor<\/h3>\n

<\/p>\n

\u00cen sistemele de stocare a datelor, de obicei, fiecare dintre blocurile de date \u0219i blocurile de coduri de redundan\u021b\u0103 sunt scrise pe un disc separat. Astfel, \u00een cazul defect\u0103rii unui disc arbitrar, datele originale pot fi restabilite \u0219i citite. Datele pot fi restaurate chiar \u0219i \u00een cazul defect\u0103rii simultane a mai multor discuri.<\/p>\n

<\/p>\n

Transferul de date<\/h3>\n

<\/p>\n

Codurile de redundan\u021b\u0103 pot fi utilizate pentru transmiterea fiabil\u0103 a datelor \u00eentr-o re\u021bea nesigur\u0103. Datele transmise sunt \u00eemp\u0103r\u021bite \u00een blocuri, pentru acestea se calculeaz\u0103 coduri de redundan\u021b\u0103. Prin re\u021bea sunt transmise at\u00e2t blocurile de date, c\u00e2t \u0219i blocurile de coduri de redundan\u021b\u0103. \u00cen cazul \u00een care apar erori \u00een blocuri arbitrare (p\u00e2n\u0103 la un anumit num\u0103r de blocuri), datele pot fi totu\u0219i transmise f\u0103r\u0103 erori prin re\u021bea. Codurile Reed-Solomon, de exemplu, sunt utilizate pentru transmiterea datelor prin linii de comunica\u021bie optic\u0103 \u0219i \u00een comunica\u021biile prin satelit.<\/p>\n

<\/p>\n

* Exist\u0103, de asemenea, coduri de redundan\u021b\u0103 \u00een care datele nu sunt \u00eemp\u0103r\u021bite \u00een blocuri, de exemplu, codurile Hamming \u0219i codurile CRC, utilizate pe scar\u0103 larg\u0103 pentru transmiterea datelor \u00een re\u021bele Ethernet. Acestea sunt coduri pentru codificarea rezistent\u0103 la interferen\u021be, destinate detect\u0103rii erorilor, nu corect\u0103rii acestora (codul Hamming permite, de asemenea, corectarea par\u021bial\u0103 a erorilor).<\/p>\n

<\/p>\n

2. Codurile Reed-Solomon<\/h1>\n

<\/p>\n

Codurile Reed-Solomon sunt unele dintre cele mai r\u0103sp\u00e2ndite coduri de redundan\u021b\u0103, inventate \u00eenc\u0103 \u00een anii 1960 \u0219i utilizate pe scar\u0103 larg\u0103 \u00een anii 1980 pentru produc\u021bia \u00een mas\u0103 de discuri compacte.<\/p>\n

<\/p>\n

Exist\u0103 dou\u0103 \u00eentreb\u0103ri cheie pentru \u00een\u021belegerea codurilor Reed-Solomon: 1) cum se creeaz\u0103 blocuri de coduri de redundan\u021b\u0103; 2) cum se recupereaz\u0103 datele cu ajutorul blocurilor de coduri de redundan\u021b\u0103. S\u0103 g\u0103sim r\u0103spunsuri la acestea.
\nPentru simplificare, vom considera c\u0103 n=6 \u0219i m=4. Alte scheme sunt examinate prin analogie.<\/p>\n

<\/p>\n

Cum se creeaz\u0103 blocuri de coduri de redundan\u021b\u0103<\/h3>\n

<\/p>\n

Fiecare bloc de coduri de redundan\u021b\u0103 este considerat independent de celelalte. Pentru calcularea fiec\u0103rui bloc se folosesc toate blocurile de date n. \u00cen diagrama de mai jos, X1-X6 sunt blocuri de date, iar P1\u2013P4 sunt blocuri de coduri de redundan\u021b\u0103.<\/p>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

Toate blocurile de date trebuie s\u0103 fie de dimensiuni egale, iar pentru aliniere se pot folosi bi\u021bi nuli. Blocurile ob\u021binute de coduri de redundan\u021b\u0103 vor avea aceea\u0219i dimensiune ca blocurile de date. Toate blocurile de date sunt \u00eemp\u0103r\u021bite \u00een cuvinte (de exemplu, c\u00e2te 16 bi\u021bi). Presupunem c\u0103 am \u00eemp\u0103r\u021bit blocurile de date \u00een k cuvinte. Atunci, toate blocurile de coduri de redundan\u021b\u0103 vor fi de asemenea \u00eemp\u0103r\u021bite \u00een k cuvinte.<\/p>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

Pentru calcularea celui i-lea cuv\u00e2nt din fiecare bloc de redundan\u021b\u0103 se vor folosi cele i-lea cuvinte ale tuturor blocurilor de date. Acestea vor fi calculate conform urm\u0103toarei formule:<\/p>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

Aici valorile x reprezint\u0103 cuvintele blocurilor de date, p reprezint\u0103 cuvintele blocurilor de coduri de redundan\u021b\u0103, toate alfa, beta, gamma \u0219i delta sunt numere special alese, identice pentru toate i. Este important de men\u021bionat c\u0103 toate aceste valori nu sunt numere obi\u0219nuite, ci elemente ale unui c\u00e2mp Galois, iar opera\u021biile +, -, *, \/ nu sunt opera\u021bii standard, ci opera\u021bii speciale introduse pentru elementele c\u00e2mpului Galois.<\/p>\n

<\/p>\n

De ce sunt necesare c\u00e2mpurile Galois<\/h3>\n

<\/p>\n

\"Coduri<\/p>\n

<\/p>\n

Ar p\u0103rea c\u0103 totul este simplu: \u00eemp\u0103r\u021bim datele \u00een blocuri, blocurile \u00een cuvinte, folosind cuvintele blocurilor de date pentru a calcula cuvintele blocurilor de coduri de redundan\u021b\u0103 \u2014 ob\u021binem blocuri de coduri de redundan\u021b\u0103. \u00cen general, a\u0219a func\u021bioneaz\u0103, dar diavolul se afl\u0103 \u00een detalii:<\/p>\n

<\/p>\n

    \n
  1. A\u0219a cum am men\u021bionat mai sus, dimensiunea cuv\u00e2ntului este fix\u0103; \u00een exemplul nostru este de 16 bi\u021bi. Formulele de mai sus pentru codurile Reed-Solomon sunt astfel \u00eenc\u00e2t, atunci c\u00e2nd se folosesc numere \u00eentregi obi\u0219nuite, rezultatul calculului p poate s\u0103 nu fie reprezentabil printr-un cuv\u00e2nt de dimensiune acceptabil\u0103.<\/li>\n
  2. La recuperarea datelor, formulele de mai sus vor fi considerate ca un sistem de ecua\u021bii care trebuie rezolvat pentru a recupera datele. \u00cen procesul de solu\u021bionare, poate ap\u0103rea necesitatea de a \u00eemp\u0103r\u021bi numere \u00eentregi, rezultatul fiind un num\u0103r real, care nu poate fi reprezentat exact \u00een memoria computerului.<\/li>\n<\/ol>\n

    <\/p>\n

    Aceste probleme \u00eempiedic\u0103 utilizarea numerelor \u00eentregi pentru codurile Reed-Solomon. Solu\u021bia problemei este original\u0103 \u0219i poate fi descris\u0103 astfel: s\u0103 venim cu numere speciale care pot fi reprezentate folosind cuvinte de lungimea necesar\u0103 (de exemplu, 16 bi\u021bi), iar rezultatul tuturor opera\u021biunilor efectuate asupra lor (adunare, sc\u0103dere, \u00eenmul\u021bire, \u00eemp\u0103r\u021bire) va fi, de asemenea, reprezentat \u00een memoria computerului prin cuvinte de lungimea necesar\u0103.<\/p>\n

    <\/p>\n

    Aceste \u201enumere speciale\u201d sunt studiate de matematic\u0103 de mult timp \u0219i se numesc c\u00e2mpuri. Un c\u00e2mp este un set de elemente cu opera\u021bii specifice de adunare, sc\u0103dere, \u00eenmul\u021bire \u0219i \u00eemp\u0103r\u021bire.<\/p>\n

    <\/p>\n

    C\u00e2mpurile Galois* sunt c\u00e2mpuri pentru care exist\u0103 \u0219i este unic\u0103 rezultatul fiec\u0103rei opera\u021biuni (+, -, *, \/) pentru orice dou\u0103 elemente ale c\u00e2mpului. C\u00e2mpurile Galois pot fi construite pentru numere care sunt puteri ale lui 2: 2, 4, 8, 16 etc. (de fapt, puteri ale oric\u0103rui num\u0103r prim p, dar \u00een practic\u0103 ne intereseaz\u0103 doar puterile lui 2). De exemplu, pentru cuvinte de dimensiune de 16 bi\u021bi, acest c\u00e2mp con\u021bine 65.536 de elemente, pentru fiecare pereche dintre acestea put\u00e2ndu-se g\u0103si rezultatul oric\u0103rei opera\u021biuni (+, -, *, \/). Valorile x, p, alfa, beta, gamma, delta din ecua\u021biile de mai sus pentru calcule vor fi considerate elemente ale c\u00e2mpului Galois.<\/p>\n

    <\/p>\n

    Prin urmare, avem un sistem de ecua\u021bii, cu ajutorul c\u0103ruia putem construi blocuri de coduri de redundan\u021b\u0103, scriind un program de calculator corespunz\u0103tor. Cu acest sistem de ecua\u021bii putem efectua, de asemenea, recuperarea datelor.<\/p>\n

    <\/p>\n

    * Aceasta nu este o defini\u021bie strict\u0103, ci mai degrab\u0103 o descriere.<\/p>\n

    <\/p>\n

    Cum s\u0103 recuper\u0103m datele<\/h3>\n

    <\/p>\n

    Recuperarea este necesar\u0103 atunci c\u00e2nd din n + m blocuri, o parte a blocurilor lipse\u0219te. Acestea pot fi at\u00e2t blocuri de date, c\u00e2t \u0219i blocuri de coduri de redundan\u021b\u0103. Lipsa blocurilor de date \u0219i\/sau a blocurilor de coduri de redundan\u021b\u0103 va \u00eensemna c\u0103 \u00een ecua\u021biile de mai sus sunt necunoscute variabilele corespunz\u0103toare x \u0219i\/sau p.<\/p>\n

    <\/p>\n

    Ecua\u021biile pentru codurile Reed-Solomon pot fi considerate un sistem de ecua\u021bii \u00een care toate valorile alfa, beta, gamma, delta sunt constante, toate x \u0219i p, corespunz\u0103toare blocurilor disponibile, sunt variabile cunoscute, iar celelalte x \u0219i p sunt necunoscute.<\/p>\n

    <\/p>\n

    De exemplu, s\u0103 presupunem c\u0103 blocurile de date 1, 2, 3 \u0219i blocul de coduri de redundan\u021b\u0103 2 sunt indisponibile, atunci pentru grupa i de cuvinte va exista urm\u0103torul sistem de ecua\u021bii (necunoscutele sunt marcate cu ro\u0219u):<\/p>\n

    <\/p>\n

    \"Coduri<\/p>\n

    <\/p>\n

    Avem un sistem de 4 ecua\u021bii cu 4 necunoscute, ceea ce \u00eenseamn\u0103 c\u0103 putem s\u0103-l rezolv\u0103m \u0219i s\u0103 recuper\u0103m datele!<\/p>\n

    <\/p>\n

    Din acest sistem de ecua\u021bii rezult\u0103 o serie de concluzii despre recuperarea datelor pentru codurile Reed-Solomon (n blocuri de date, m blocuri de coduri de redundan\u021b\u0103):<\/p>\n

    <\/p>\n