{"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":"Redundantsed koodid: lihtsustatult, kuidas usaldusv\u00e4\u00e4rselt ja odavalt andmeid salvestada","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Redundantsed<\/p>\n

<\/p>\n

Nii n\u00e4eb v\u00e4lja \u00fclek\u00fcllus<\/em><\/p>\n

<\/p>\n

\u00dclek\u00fclluskoode* kasutatakse laialdaselt arvutis\u00fcsteemides andmete salvestamise usaldusv\u00e4\u00e4rsuse suurendamiseks. Yandexis kasutatakse neid paljusid projekte. N\u00e4iteks \u00fclek\u00fclluskoode kasutatakse meie sisemises objektigaleriis replikatsiooni asemel, mis s\u00e4\u00e4stab miljoneid ilma usaldusv\u00e4\u00e4rsuse v\u00e4henemiseta. Kuid vaatamata laialdasele levikule on \u00fclek\u00fclluskoode kohta arusaadavat kirjeldust harva. Need, kes soovivad rohkem teada, seisavad silmitsi umbes j\u00e4rgmisega (v\u00e4lja arvatud Vikipeediale<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

Minu nimi on Vadim, Yandexis tegelen ma sisemise objektigaleriiga MDS arendamisega. Selles artiklis selgitan lihtsate s\u00f5nadega \u00fclek\u00fclluskoode (Reedi-Solomoni koode ja LRC teoreetilisi aluseid). R\u00e4\u00e4gin, kuidas see t\u00f6\u00f6tab, ilma keerulise matemaatika ja haruldaste terminite kasutamiseta. L\u00f5pus toon n\u00e4iteid \u00fclek\u00fclluskoode kasutamisest Yandexis.<\/p>\n

<\/p>\n

M\u00f5ned matemaatilised detailid j\u00e4\u00e4vad mul p\u00f5hjalikult k\u00e4sitlemata, kuid jagan viiteid neile, kes soovivad s\u00fcgavamale minna. Samuti m\u00e4rgin, et m\u00f5ned matemaatilised m\u00e4\u00e4ratlused ei pruugi olla t\u00e4psed, kuna artikkel ei ole suunatud matemaatikutele, vaid inseneridele, kes soovivad m\u00f5ista teema olemust.<\/p>\n

<\/p>\n

* Ingliskeelses kirjanduses nimetatakse liigkoodideks sageli erase codes.<\/p>\n

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

1. Liigkoodide olemus<\/h1>\n

<\/p>\n

Liigkoodide olemus on \u00e4\u00e4rmiselt lihtne: salvestada (v\u00f5i edastada) andmeid nii, et need ei kaoks, kui tekivad vead (k\u00f5vakettavigu, andmeedastusvead jne). <\/p>\n

<\/p>\n

Enamikus* liigkoodides jagatakse andmed n andmeplokiks, mille jaoks on v\u00e4lja arvutatud m liigkoodi plokki, kokku saame n + m plokki. Liigkoodid on konstrueeritud nii, et n andmeplokki saab taastada, kasutades ainult osa n + m plokist. Edasi vaatame ainult plokkide liigkoodide, see t\u00e4hendab neid, kus andmed jaotatakse plokkideks.<\/p>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

K\u00f5igi n andmeplokkide taastamiseks on vaja, et oleks v\u00e4hemalt n plokki n + m plokist, kuna n plokki ei saa taastada, omades vaid n-1 plokki (sellisel juhul tuleks \u00fcks plokk v\u00f5tta '\u00f5hust'). Kas piisab n suvalisest plokist n + m plokist, et taastada k\u00f5ik andmed? See s\u00f5ltub \u00fclekoormuskoode t\u00fc\u00fcbist; n\u00e4iteks Reed-Solomoni koodid v\u00f5imaldavad k\u00f5iki andmeid taastada suvaliste n plokkide kaudu, kuid LRC \u00fclekoormuskoode ei pruugi alati piisata.<\/p>\n

<\/p>\n

Andmete salvestamine<\/h3>\n

<\/p>\n

Andmesalvestuss\u00fcsteemides salvestatakse tavaliselt iga andmeplokk ja \u00fclekoormusplokk eraldi kettale. Sel juhul on andmed ikkagi v\u00f5imalik taastada ja lugeda, isegi kui \u00fcksk\u00f5ik milline ketas on rikki l\u00e4inud. Andmed on v\u00f5imalik taastada isegi mitme ketta samaaegse rikkumise korral.<\/p>\n

<\/p>\n

Andmete edastamine<\/h3>\n

<\/p>\n

Liigne koodide abil saab usaldusv\u00e4\u00e4rselt edastada andmeid ebausaldusv\u00e4\u00e4rses v\u00f5rgus. Edastatavad andmed jagatakse plokkideks, millele arvutatakse liigne kood. V\u00f5rgus edastatakse nii andmeplokid kui ka liigne koodide plokid. Kui teatud plokkides esinevad vead (aines kuni teatava arvu plokkideni), on andmeid siiski v\u00f5imalik veatult edastada. N\u00e4iteks kasutatakse Reedi-Solomoni koode andmete edastamiseks optilistes sideliinides ja satelliitsides.<\/p>\n

<\/p>\n

* On ka liigne koode, kus andmeid ei jagata plokkideks, n\u00e4iteks Hamming'i koodid ja CRC koodid, mida laialdaselt kasutatakse andmete edastamiseks Etherneti v\u00f5rkudes. Need on koodid, mis tagavad m\u00fcra taluvuse, m\u00f5eldud vigade avastamiseks, mitte parandamiseks (Hamming'i kood v\u00f5imaldab ka vigade osalist parandamist).<\/p>\n

<\/p>\n

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

<\/p>\n

Reedi-Solomoni koodid on \u00fched levinumad liigne koodid, mis p\u00e4rinevad juba 1960. aastatest ja said esmakordselt laialdast kasutust 1980. aastatel kompaktplaatide sarjatootmises.<\/p>\n

<\/p>\n

Reed-Solomon koodide m\u00f5istmiseks on kaks p\u00f5hik\u00fcsimust: 1) kuidas luua \u00fclem\u00e4\u00e4raste koodide bloke; 2) kuidas taastada andmeid \u00fclem\u00e4\u00e4raste koodide abil. Otsime nendele vastuseid.
\nLihtsustamiseks oletame edaspidi, et n=6 ja m=4. Teised skeemid k\u00e4sitletakse analooge j\u00e4rgides.<\/p>\n

<\/p>\n

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

<\/p>\n

Iga \u00fclem\u00e4\u00e4raste koodide blokk arvestatakse s\u00f5ltumatult teistest. Iga bloki arvutamiseks kasutatakse k\u00f5iki n andmeblokke. Alloleval skeemil X1-X6 on andmeblokid, P1\u2013P4 on \u00fclem\u00e4\u00e4raste koodide blokid.<\/p>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

K\u00f5ik andmeblokid peavad olema sama suurusega, tasakaalustamiseks v\u00f5ib kasutada nullbitte. Saadud \u00fclem\u00e4\u00e4raste koodide blokid on sama suurusega kui andmebloked. K\u00f5ik andmeblokid jagunevad s\u00f5nadeks (n\u00e4iteks 16 bitti igas). Oletame, et jagasime andmeblokid k s\u00f5naks. Siis jagunevad k\u00f5ik \u00fclem\u00e4\u00e4raste koodide blokid samuti k s\u00f5naks.<\/p>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

Iga \u00fclem\u00e4\u00e4raste koodide bloki i-s\u00f5na arvutamiseks kasutatakse k\u00f5ikide andmeblokki i-s\u00f5nu. Need arvutatakse j\u00e4rgmise valemi j\u00e4rgi:<\/p>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

Siin on x v\u00e4\u00e4rtused \u2013 andmeplokkide s\u00f5nad, p \u2013 \u00fcleliigsete koodide plokkide s\u00f5nad, k\u00f5ik alfa, beeta, gamma ja delta \u2013 spetsiaalselt valitud numbrid, mis on k\u00f5ikidele i jaoks \u00fchesugused. Tuleb kohe \u00f6elda, et k\u00f5ik need v\u00e4\u00e4rtused ei ole tavalised numbrid, vaid Galois'i v\u00e4lja elemendid, operatsioonid +, -, *, \/ \u2013 ei ole k\u00f5igile tuttavad operatsioonid, vaid spetsiaalsed tehingud, mis on m\u00e4\u00e4ratud Galois'i v\u00e4lja elementide \u00fcle.<\/p>\n

<\/p>\n

Miks on Galois'i v\u00e4ljad vajalikud<\/h3>\n

<\/p>\n

\"Redundantsed<\/p>\n

<\/p>\n

Tundub, et k\u00f5ik on lihtne: jagame andmed plokkideks, plokid s\u00f5nadeks, kasutades andmeplokkide s\u00f5nu, arvutame \u00fcleliigsete koodide plokkide s\u00f5nad \u2013 saame \u00fcleliigsete koodide plokid. \u00dcldiselt see nii toimib, kuid diabol on detailides:<\/p>\n

<\/p>\n

    \n
  1. Nagu \u00f6eldud, on s\u00f5na suurus fikseeritud, meie n\u00e4ites 16 bitti. \u00dclaltoodud Reed-Solomoni koodide valemid on sellised, et tavaliste t\u00e4isarvude kasutamisel v\u00f5ib p arvutamise tulemus olla esitatud lubatud suurusega s\u00f5nadega.<\/li>\n
  2. Andmete taastamisel k\u00e4sitletakse \u00fclaltoodud valemeid kui v\u00f5rrandis\u00fcsteemi, mille lahendamine on vajalik andmete taastamiseks. Lahendamise k\u00e4igus v\u00f5ib tekkida vajadus jagada \u00fcksteisega t\u00e4isarve, mille tulemuseks on reaalnumber, mida arvutis t\u00e4pselt esitada ei saa.<\/li>\n<\/ol>\n

    <\/p>\n

    Need probleemid ei v\u00f5imalda Reed-Salomoni koodide jaoks kasutada t\u00e4isarve. Probleemi lahendus on originaalne ja seda v\u00f5ib kirjeldada j\u00e4rgmiselt: m\u00f5tleme v\u00e4lja erilised numbrid, mida saab esitada vajalikus pikkuses s\u00f5nadega (n\u00e4iteks 16 bitti), ning k\u00f5ik nendele numbritele tehtud operatsioonide (liitmine, lahutamine, korrutamine, jagamine) tulemused on samuti arvutis esitatud vajaliku pikkusega s\u00f5nadega.<\/p>\n

    <\/p>\n

    Selliseid \"erilisi\" numbreid on juba ammu uuritud matemaatikas, neid nimetatakse v\u00e4ljadeks. V\u00e4li on elementide kogum, millel on m\u00e4\u00e4ratletud liitmise, lahutamise, korrutamise ja jagamise operatsioonid.<\/p>\n

    <\/p>\n

    Galois-v\u00e4ljad* on v\u00e4ljad, mille puhul on iga operatsiooni (+, -, *, \/) tulemus iga kahe v\u00e4lja elemendi jaoks olemas ja ainus. Galois-v\u00e4lju saab ehitada arvudele, mis on 2 astmes: 2, 4, 8, 16 jne. (tegelikult mis tahes algarvu p astmes, kuid praktikas huvitavad meid ainult 2 astmed). N\u00e4iteks 16-bitiste s\u00f5nade jaoks on see v\u00e4li, mis sisaldab 65 536 elementi, mille jaoks saab leida iga operatsiooni (+, -, *, \/) tulemust. \u00dclaltoodud valemites x, p, alfa, beeta, gamma, delta v\u00e4\u00e4rtused loetakse Galois-v\u00e4lja elementideks arvutuste tegemisel.<\/p>\n

    <\/p>\n

    Seega on meil s\u00fcsteem v\u00f5rrandeid, millega saab ehitada \u00fcleliigsuse koodiplokke, kirjutades vastava arvutiprogrammi. Sama s\u00fcsteemi abil saab teostada ka andmete taastamist.<\/p>\n

    <\/p>\n

    * See ei ole rangelt \u00f6eldes m\u00e4\u00e4ratlus, pigem kirjeldus.<\/p>\n

    <\/p>\n

    Kuidas andmeid taastada<\/h3>\n

    <\/p>\n

    Taastamine on vajalik, kui n + m plokist osa plokke puudub. Need v\u00f5ivad olla nii andmeplokid kui ka liigse koodi plokid. Andmeplokkide ja\/v\u00f5i liigse koodi plokkide puudumine t\u00e4hendab, et \u00fclaltoodud v\u00f5rrandites pole vastavaid muutujaid x ja\/v\u00f5i p.<\/p>\n

    <\/p>\n

    Reedi-Solomoni koodide v\u00f5rrandeid v\u00f5ib k\u00e4sitleda kui v\u00f5rrandite s\u00fcsteemi, kus k\u00f5ik alfa, beeta, gamma, delta v\u00e4\u00e4rtused on konstandid, k\u00f5ik x ja p, mis vastavad kergesti k\u00e4tte saadavatele plokkidele, on teadaolevad muutujad, ja teised x ja p on tundmatud.<\/p>\n

    <\/p>\n

    N\u00e4iteks, oletame, et andmeplokid 1, 2, 3 ja liigse koodi plokk 2 on kergesti k\u00e4tte saamata, siis i-nda s\u00f5na r\u00fchma jaoks tekib j\u00e4rgmine v\u00f5rrandite s\u00fcsteem (tundmatud on esile t\u00f5stetud punasega):<\/p>\n

    <\/p>\n

    \"Redundantsed<\/p>\n

    <\/p>\n

    Meil on 4 v\u00f5rrandi ja 4 tundmatuga s\u00fcsteem, seega saame selle lahendada ja andmeid taastada!<\/p>\n

    <\/p>\n

    Sellest v\u00f5rrandite s\u00fcsteemist j\u00e4relduvad mitmed t\u00e4helepanekud andmete taastamise kohta Reedi-Solomoni koodide puhul (n andmeplokki, m liigse koodi plokki):<\/p>\n

    <\/p>\n