{"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\/et\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"\u00dclem\u00e4\u00e4rasuse koodid: lihtsustatult, kuidas usaldusv\u00e4\u00e4rselt ja odavalt andmeid salvestada","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Nii n\u00e4eb v\u00e4lja \u00fcleliigne<\/em><\/p>\n

<\/p>\n

\u00dcksikasjad, mis k\u00e4sitlevad \u00fcleliigseid koode*, on laialdaselt rakendatud arvutis\u00fcsteemides andmete salvestamise usaldusv\u00e4\u00e4rsuse suurendamiseks. Yandexis kasutatakse neid paljuski erinevates projektides. N\u00e4iteks on \u00fcleliigsete koodide rakendamine meie sisemises objektide salvestamise s\u00fcsteemis v\u00e4hendanud kulusid miljoneid ilma usaldusv\u00e4\u00e4rsust v\u00e4hendamata. Kuid hoolimata laialdasest kasutusest on arusaadav kirjeldus selle kohta, kuidas \u00fcleliigsed koodid t\u00f6\u00f6tavad, \u00fcliharv. Need, kes soovivad teemaga tutvuda, seisavad silmitsi umbes j\u00e4rgneva olukorraga (v\u00e4ljav\u00f5te Vikipeediad<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Minu nimi on Vadim, Yandexis t\u00f6\u00f6tan ma MDS sisemiste objektide salvestamise s\u00fcsteemi arendamisega. Sellel artiklil selgitan lihtsate s\u00f5nadega \u00fcleliigsete koodide (Reedi-Salomoni ja LRC koodide) teoreetilisi aluseid. R\u00e4\u00e4gin, kuidas see t\u00f6\u00f6tab, ilma keerulise matemaatika ja haruldaste terminite puudutamiseta. L\u00f5pus toon v\u00e4lja n\u00e4ited \u00fcleliigsete koodide kasutamisest Yandexis.<\/p>\n

<\/p>\n

M\u00f5ned matemaatilised detailid, mida ma ei k\u00e4sitle s\u00fcvitsi, kuid annan lingid neile, kes soovivad s\u00fcgavamale teemasse s\u00fcveneda. Samuti m\u00e4rgin, et m\u00f5ned matemaatilised m\u00e4\u00e4ratlused ei pruugi olla rangelt t\u00e4psed, kuna artikkel ei ole suunatud matemaatikutele, vaid inseneridele, kes soovivad m\u00f5ista probleemi olemust.<\/p>\n

<\/p>\n

* Ingli keelses kirjanduses nimetatakse \u00fcleliigseid koode sageli erasure codes.<\/p>\n

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

1. \u00dcleliigsete koodide olemus<\/h1>\n

<\/p>\n

\u00dcleliigsete koodide olemus on \u00e4\u00e4rmiselt lihtne: anda andmeid nii, et need ei kaoks, kui esinevad vead (nt k\u00f5vaketaste rike, andmete edastamise vead jne). <\/p>\n

<\/p>\n

Enamikes* \u00fcleliigsetes koodides jagatakse andmed n andmeplokiks, mille jaoks arvutatakse m \u00fcleliigse koodi plokki, kokku on n + m plokki. \u00dcleliigsed koodid on \u00fcles ehitatud nii, et n andmeplokki on v\u00f5imalik taastada, kasutades ainult osa n + m plokkidest. Edasi k\u00e4sitleme ainult plokkide \u00fcleliigseid koode, see t\u00e4hendab selliseid, kus andmed jagatakse plokkideks.<\/p>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Kogu n andmete bloke taastamiseks on vaja v\u00e4hemalt n blokki n + m blokist, sest ei saa saada n blokki, omades ainult n-1 plokki (sel juhul tuleb 1 blokk v\u00f5tta \"\u00f5hust\"). Kas n meelevaldselt valitud plokki n + m plokist on piisavad k\u00f5igi andmete taastamiseks? See s\u00f5ltub \u00fclem\u00e4\u00e4raste koodide t\u00fc\u00fcbist, n\u00e4iteks Reed-Solomoni koodid v\u00f5imaldavad taastada k\u00f5ik andmed meelevaldsete n plokkide abil, kuid LRC \u00fclem\u00e4\u00e4rased koodid ei pruugi alati seda teha.<\/p>\n

<\/p>\n

Andmete salvestamine<\/h3>\n

<\/p>\n

Andmesalvestuss\u00fcsteemides on tavaliselt iga andme- ja \u00fclem\u00e4\u00e4raste koodide plokk salvestatud eraldi kettale. Seega, kui \u00fcksk\u00f5ik milline ketas rikneb, on algandmed ikkagi v\u00f5imalik taastada ja lugeda. Andmeid saab taastada isegi siis, kui mitu ketast riknevad korraga.<\/p>\n

<\/p>\n

Andmete edastamine<\/h3>\n

<\/p>\n

\u00dclem\u00e4\u00e4raseid koode saab kasutada usaldusv\u00e4\u00e4rseks andmete edastamiseks ebausaldusv\u00e4\u00e4rses v\u00f5rgus. Edastatavad andmed jagatakse plokkideks, nende jaoks arvutatakse \u00fclem\u00e4\u00e4rase koodi. V\u00f5rgus edastatakse nii andmeplokid kui ka \u00fclem\u00e4\u00e4raste koodide plokid. Kui juhuslikes plokkides (kuni teatud arvu plokini) tekivad vead, on andmete edastamine siiski usaldusv\u00e4\u00e4rne. Reed-Solomoni koode kasutatakse n\u00e4iteks andmete edastamiseks optiliste sideliinide ja satelliitside kaudu.<\/p>\n

<\/p>\n

* On ka \u00fclem\u00e4\u00e4raseid koode, milles andmeid ei jagata plokkideks, n\u00e4iteks Hamming-koodid ja CRC-koodid, mida laialdaselt kasutatakse andmete edastamiseks Ethernet-v\u00f5rkudes. Need on koodid h\u00e4irekindlaks kodeerimiseks, mis on m\u00f5eldud vigade tuvastamiseks, mitte nende parandamiseks (Hamming-kood v\u00f5imaldab samuti osaliselt vigu parandada).<\/p>\n

<\/p>\n

2. Reed-Solomoni koodid<\/h1>\n

<\/p>\n

Reed-Solomoni koodid on \u00fched levinumad \u00fclem\u00e4\u00e4rase koodi t\u00fc\u00fcbid, mis leiutati 1960. aastatel ja said esmakordselt laialdast kasutamist 1980. aastatel kompaktdiskide seeriatootmises.<\/p>\n

<\/p>\n

Kaks peamist k\u00fcsimust Reed-Solomoni koodide m\u00f5istmiseks on: 1) kuidas luua \u00fclem\u00e4\u00e4raste koodide plokke; 2) kuidas taastada andmeid \u00fclem\u00e4\u00e4raste koodide plokkide abil. Leiam sellele vastused.
\nLihtsuse huvides eeldame edaspidi, et n=6 ja m=4. Teisi skeeme k\u00e4sitletakse sarnasel viisil.<\/p>\n

<\/p>\n

Kuidas luua \u00fclem\u00e4\u00e4raste koodide plokke<\/h3>\n

<\/p>\n

Iga parandusblokki loetakse s\u00f5ltumatuks teistest. Iga blokki arvestamiseks kasutatakse k\u00f5iki n andmeplokke. Alloleval skeemil on X1-X6 andmeplokid, P1\u2013P4 parandusplokid.<\/p>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

K\u00f5ik andmeplokid peavad olema samas suuruses, \u00fchtlustamiseks v\u00f5ib kasutada nulli bitsid. Saadud parandusplokid on sama suurusega kui andmeplokid. K\u00f5ik andmeplokid jagatakse s\u00f5nadeks (nt 16 bitti). Oletame, et oleme jaganud andmeplokid k s\u00f5naks. Siis jagatakse ka k\u00f5ik parandusplokid k s\u00f5naks.<\/p>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Iga parandusploki i-ndat s\u00f5na arvestatakse kasutades k\u00f5igi andmeplokkide i-nda s\u00f5na. Need arvutatakse j\u00e4rgmise valemi abil:<\/p>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Siin x v\u00e4\u00e4rtused on andmeplokkide s\u00f5nad, p on parandusplokkide s\u00f5nad, k\u00f5ik alfa, beeta, gamma ja delta on eriliselt valitud numbrid, mis on k\u00f5igi i jaoks \u00fchesugused. Tuleb kohe \u00f6elda, et k\u00f5ik need v\u00e4\u00e4rtused ei ole tavalised numbrid, vaid Galoisi v\u00e4li elemendid, operatsioonid +, -, *, \/ \u2013 ei ole meie jaoks harilikud operatsioonid, vaid Galoisi v\u00e4li elementide peal kehtivad erilised operatsioonid.<\/p>\n

<\/p>\n

Miks on Galoisi v\u00e4ljad vajalikud<\/h3>\n

<\/p>\n

\"\u00dclem\u00e4\u00e4rasuse<\/p>\n

<\/p>\n

Tundub, et k\u00f5ik on lihtne: jagame andmed plokkideks, plokid s\u00f5nadeks, andmeplokkide s\u00f5nade abil arvestame parandusplokkide s\u00f5nu \u2013 saame parandusplokid. \u00dcldiselt nii see toimib, kuid detailides peitub kurat:<\/p>\n

<\/p>\n

    \n
  1. Nagu eespool mainitud, on s\u00f5na suurus fikseeritud, meie n\u00e4ites 16 bitti. \u00dclaltoodud valemid Reed-Solomoni koodide jaoks on sellised, et tavaliste t\u00e4isarvude kasutamisel v\u00f5ib p arvutamise tulemus olla selline, mida ei saa sobiva suurusega s\u00f5naga esitada.<\/li>\n
  2. Andmete taastamisel k\u00e4sitletakse \u00fclaltoodud valemeid v\u00f5rrandis\u00fcsteemina, mille lahendamiseks on vaja taastada andmed. Lahendamise k\u00e4igus v\u00f5ib tekkida vajadus jagada t\u00e4isarve \u00fcksteisega, mille tulemusena tekib reaalne arv, mida ei saa t\u00e4pselt arvutisse m\u00e4llu salvestada.<\/li>\n<\/ol>\n

    <\/p>\n

    Need for Reed\u2013Solomon codes prevents the use of whole numbers. The solution to the problem is original; it can be described as follows: let\u2019s invent special numbers that can be represented using words of the required length (for example, 16 bits), and the result of all operations performed on them (addition, subtraction, multiplication, division) will also be represented in the computer's memory using words of the required length.<\/p>\n

    <\/p>\n

    Such 'special' numbers have long been studied in mathematics; they are called fields. A field is a set of elements with defined operations of addition, subtraction, multiplication, and division.<\/p>\n

    <\/p>\n

    Galois fields* are fields for which there exists and is unique a result for each operation (+, -, *, \/) between any two elements of the field. Galois fields can be built for numbers that are powers of 2: 2, 4, 8, 16, etc. (in fact, any prime number p, but in practice, we are only interested in powers of 2). For example, for words of size 16 bits, this is a field containing 65,536 elements, for each pair of which a result of any operation (+, -, *, \/) can be found. The values x, p, alpha, beta, gamma, delta from the equations above for calculations will be considered elements of the Galois field.<\/p>\n

    <\/p>\n

    Thus, we have a system of equations using which redundancy code blocks can be constructed by writing the corresponding computer program. This same system of equations can be used for data recovery.<\/p>\n

    <\/p>\n

    * This is not a strict definition, more of a description.<\/p>\n

    <\/p>\n

    How to Restore Data<\/h3>\n

    <\/p>\n

    Recovery is necessary when part of the n + m blocks is missing. These can be either data blocks or redundancy code blocks. The absence of data blocks and\/or redundancy code blocks means that in the equations above the corresponding variables x and\/or p are unknown.<\/p>\n

    <\/p>\n

    The equations for Reed\u2013Solomon codes can be seen as a system of equations where all values alpha, beta, gamma, delta are constants, all x and p corresponding to the available blocks are known variables, and the others x and p are unknown.<\/p>\n

    <\/p>\n

    For example, let blocks 1, 2, 3 of data and the redundancy code block 2 be unavailable; then for the i-th group of words, the following system of equations will be present (the unknowns are marked in red):<\/p>\n

    <\/p>\n

    \"\u00dclem\u00e4\u00e4rasuse<\/p>\n

    <\/p>\n

    Meil on s\u00fcsteem, mis koosneb 4 v\u00f5rrandist 4 tundmatuga, seega saame selle lahendada ja andmed taastada!<\/p>\n

    <\/p>\n

    Sellest v\u00f5rrandite s\u00fcsteemist j\u00e4relduvad mitmed j\u00e4reldused andmete taastamiseks Reed-Solomoni koodide puhul (n andmeplokki, m \u00fcleliigset koodiplokki):<\/p>\n

    <\/p>\n