Nii näeb välja üleküllus

Ülekülluskoode* kasutatakse laialdaselt arvutisüsteemides andmete salvestamise usaldusväärsuse suurendamiseks. Yandexis kasutatakse neid paljusid projekte. Näiteks ülekülluskoode kasutatakse meie sisemises objektigaleriis replikatsiooni asemel, mis säästab miljoneid ilma usaldusväärsuse vähenemiseta. Kuid vaatamata laialdasele levikule on ülekülluskoode kohta arusaadavat kirjeldust harva. Need, kes soovivad rohkem teada, seisavad silmitsi umbes järgmisega (välja arvatud Vikipeediale):

Minu nimi on Vadim, Yandexis tegelen ma sisemise objektigaleriiga MDS arendamisega. Selles artiklis selgitan lihtsate sõnadega ülekülluskoode (Reedi-Solomoni koode ja LRC teoreetilisi aluseid). Räägin, kuidas see töötab, ilma keerulise matemaatika ja haruldaste terminite kasutamiseta. Lõpus toon näiteid ülekülluskoode kasutamisest Yandexis.

Mõned matemaatilised detailid jäävad mul põhjalikult käsitlemata, kuid jagan viiteid neile, kes soovivad sügavamale minna. Samuti märgin, et mõned matemaatilised määratlused ei pruugi olla täpsed, kuna artikkel ei ole suunatud matemaatikutele, vaid inseneridele, kes soovivad mõista teema olemust.

* Ingliskeelses kirjanduses nimetatakse liigkoodideks sageli erase codes.

1. Liigkoodide olemus

Liigkoodide olemus on äärmiselt lihtne: salvestada (või edastada) andmeid nii, et need ei kaoks, kui tekivad vead (kõvakettavigu, andmeedastusvead jne).

Enamikus* liigkoodides jagatakse andmed n andmeplokiks, mille jaoks on välja 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ähendab neid, kus andmed jaotatakse plokkideks.

Kõigi n andmeplokkide taastamiseks on vaja, et oleks vähemalt n plokki n + m plokist, kuna n plokki ei saa taastada, omades vaid n-1 plokki (sellisel juhul tuleks üks plokk võtta 'õhust'). Kas piisab n suvalisest plokist n + m plokist, et taastada kõik andmed? See sõltub ülekoormuskoode tüübist; näiteks Reed-Solomoni koodid võimaldavad kõiki andmeid taastada suvaliste n plokkide kaudu, kuid LRC ülekoormuskoode ei pruugi alati piisata.

Andmete salvestamine

Andmesalvestussüsteemides salvestatakse tavaliselt iga andmeplokk ja ülekoormusplokk eraldi kettale. Sel juhul on andmed ikkagi võimalik taastada ja lugeda, isegi kui ükskõik milline ketas on rikki läinud. Andmed on võimalik taastada isegi mitme ketta samaaegse rikkumise korral.

Andmete edastamine

Liigne koodide abil saab usaldusväärselt edastada andmeid ebausaldusväärses võrgus. Edastatavad andmed jagatakse plokkideks, millele arvutatakse liigne kood. Võrgus edastatakse nii andmeplokid kui ka liigne koodide plokid. Kui teatud plokkides esinevad vead (aines kuni teatava arvu plokkideni), on andmeid siiski võimalik veatult edastada. Näiteks kasutatakse Reedi-Solomoni koode andmete edastamiseks optilistes sideliinides ja satelliitsides.

* On ka liigne koode, kus andmeid ei jagata plokkideks, näiteks Hamming'i koodid ja CRC koodid, mida laialdaselt kasutatakse andmete edastamiseks Etherneti võrkudes. Need on koodid, mis tagavad müra taluvuse, mõeldud vigade avastamiseks, mitte parandamiseks (Hamming'i kood võimaldab ka vigade osalist parandamist).

2. Reedi-Solomoni koodid

Reedi-Solomoni koodid on ühed levinumad liigne koodid, mis pärinevad juba 1960. aastatest ja said esmakordselt laialdast kasutust 1980. aastatel kompaktplaatide sarjatootmises.

Reed-Solomon koodide mõistmiseks on kaks põhiküsimust: 1) kuidas luua ülemääraste koodide bloke; 2) kuidas taastada andmeid ülemääraste koodide abil. Otsime nendele vastuseid.
Lihtsustamiseks oletame edaspidi, et n=6 ja m=4. Teised skeemid käsitletakse analooge järgides.

Kuidas luua ülemääraste koodide bloke

Iga ülemääraste koodide blokk arvestatakse sõltumatult teistest. Iga bloki arvutamiseks kasutatakse kõiki n andmeblokke. Alloleval skeemil X1-X6 on andmeblokid, P1–P4 on ülemääraste koodide blokid.

Kõik andmeblokid peavad olema sama suurusega, tasakaalustamiseks võib kasutada nullbitte. Saadud ülemääraste koodide blokid on sama suurusega kui andmebloked. Kõik andmeblokid jagunevad sõnadeks (näiteks 16 bitti igas). Oletame, et jagasime andmeblokid k sõnaks. Siis jagunevad kõik ülemääraste koodide blokid samuti k sõnaks.

Iga ülemääraste koodide bloki i-sõna arvutamiseks kasutatakse kõikide andmeblokki i-sõnu. Need arvutatakse järgmise valemi järgi:

Siin on x väärtused – andmeplokkide sõnad, p – üleliigsete koodide plokkide sõnad, kõik alfa, beeta, gamma ja delta – spetsiaalselt valitud numbrid, mis on kõikidele i jaoks ühesugused. Tuleb kohe öelda, et kõik need väärtused ei ole tavalised numbrid, vaid Galois'i välja elemendid, operatsioonid +, -, *, / – ei ole kõigile tuttavad operatsioonid, vaid spetsiaalsed tehingud, mis on määratud Galois'i välja elementide üle.

Miks on Galois'i väljad vajalikud

Tundub, et kõik on lihtne: jagame andmed plokkideks, plokid sõnadeks, kasutades andmeplokkide sõnu, arvutame üleliigsete koodide plokkide sõnad – saame üleliigsete koodide plokid. Üldiselt see nii toimib, kuid diabol on detailides:

Nagu öeldud, on sõna suurus fikseeritud, meie näites 16 bitti. Ülaltoodud Reed-Solomoni koodide valemid on sellised, et tavaliste täisarvude kasutamisel võib p arvutamise tulemus olla esitatud lubatud suurusega sõnadega.
Andmete taastamisel käsitletakse ülaltoodud valemeid kui võrrandisüsteemi, mille lahendamine on vajalik andmete taastamiseks. Lahendamise käigus võib tekkida vajadus jagada üksteisega täisarve, mille tulemuseks on reaalnumber, mida arvutis täpselt esitada ei saa.

Need probleemid ei võimalda Reed-Salomoni koodide jaoks kasutada täisarve. Probleemi lahendus on originaalne ja seda võib kirjeldada järgmiselt: mõtleme välja erilised numbrid, mida saab esitada vajalikus pikkuses sõnadega (näiteks 16 bitti), ning kõik nendele numbritele tehtud operatsioonide (liitmine, lahutamine, korrutamine, jagamine) tulemused on samuti arvutis esitatud vajaliku pikkusega sõnadega.

Selliseid "erilisi" numbreid on juba ammu uuritud matemaatikas, neid nimetatakse väljadeks. Väli on elementide kogum, millel on määratletud liitmise, lahutamise, korrutamise ja jagamise operatsioonid.

Galois-väljad* on väljad, mille puhul on iga operatsiooni (+, -, *, /) tulemus iga kahe välja elemendi jaoks olemas ja ainus. Galois-välju 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äiteks 16-bitiste sõnade jaoks on see väli, mis sisaldab 65 536 elementi, mille jaoks saab leida iga operatsiooni (+, -, *, /) tulemust. Ülaltoodud valemites x, p, alfa, beeta, gamma, delta väärtused loetakse Galois-välja elementideks arvutuste tegemisel.

Seega on meil süsteem võrrandeid, millega saab ehitada üleliigsuse koodiplokke, kirjutades vastava arvutiprogrammi. Sama süsteemi abil saab teostada ka andmete taastamist.

* See ei ole rangelt öeldes määratlus, pigem kirjeldus.

Kuidas andmeid taastada

Taastamine on vajalik, kui n + m plokist osa plokke puudub. Need võivad olla nii andmeplokid kui ka liigse koodi plokid. Andmeplokkide ja/või liigse koodi plokkide puudumine tähendab, et ülaltoodud võrrandites pole vastavaid muutujaid x ja/või p.

Reedi-Solomoni koodide võrrandeid võib käsitleda kui võrrandite süsteemi, kus kõik alfa, beeta, gamma, delta väärtused on konstandid, kõik x ja p, mis vastavad kergesti kätte saadavatele plokkidele, on teadaolevad muutujad, ja teised x ja p on tundmatud.

Näiteks, oletame, et andmeplokid 1, 2, 3 ja liigse koodi plokk 2 on kergesti kätte saamata, siis i-nda sõna rühma jaoks tekib järgmine võrrandite süsteem (tundmatud on esile tõstetud punasega):

Meil on 4 võrrandi ja 4 tundmatuga süsteem, seega saame selle lahendada ja andmeid taastada!

Sellest võrrandite süsteemist järelduvad mitmed tähelepanekud andmete taastamise kohta Reedi-Solomoni koodide puhul (n andmeplokki, m liigse koodi plokki):

Andmeid saab taastada, kui kaotatakse kuni m blokki või vähem. Kui kaotatakse m+1 või rohkem blokk, siis andmeid taastada ei saa: m võrrandite süsteemi m + 1 tundmatuga lahendada ei saa.
Isegi ühe andmebloki taastamiseks tuleb kasutada igasuguseid n ülejäänud bloke, samas võib kasutada igasuguseid ülekande koodide n.

Mis veel on oluline teada

Ülaltoodud kirjelduses jätan tähelepanuta mitu olulist küsimust, mille arutamiseks tuleb matemaatikasse sügavamale süveneda. Eriti ei räägi ma järgmistest asjadest:

Reed-Solomoni koodide võrrandite süsteemil peab olema (ainus) lahendus mis tahes tundmatute kombinatsioonide korral (kuni m tundmatut). Selle nõude põhjal valitakse alfa, beeta, gamma ja delta väärtused.
Võrrandite süsteem peab olema võimeline automaatselt ehitama (sõltuvalt sellest, millised blokid on kättesaamatud) ja lahendama.
Galois' väli tuleb luua: antud sõnumi suuruse jaoks peab olema võimalik leida mis tahes operatsiooni (+, -, *, /) tulemus igasuguste kahe elemendi jaoks.

Artikli lõpus on lingid kirjandusele nende oluliste küsimuste kohta.

n ja m valimine

Kuidas praktikas valida n ja m? Andmesalvestussüsteemides kasutatakse redundantsuskoodide abil ruumi kokkuhoiuks, seega valitakse m alati väiksem kui n. Nende konkreetsed väärtused sõltuvad mitmetest teguritest, sealhulgas:

Andmete salvestamise usaldusväärsus. Mida suurem on m, seda rohkem kettahäireid suudetakse taluda, mis tähendab kõrgemat usaldusväärsust.
Salvestuse redundantsus. Mida kõrgem on suhe m / n, seda suurem on salvestuse redundantsus ja seda kallim on süsteem.
Päringute töötlemise aeg. Mida suurem on summa n + m, seda pikem on päringute vastamise aeg. Kuna andmete lugemiseks (taastamise ajal) tuleb lugeda n plokki, mis asuvad n erineval kettal, siis määrab lugemise aeg kõige aeglasem ketas.

Lisaks sellele seab andmete säilitamine mitmes andme keskuses täiendavad piirangud n ja m valikule: ühe DС väljalülitamisel peavad andmed siiski olema loetavad. Näiteks, kui andmeid hoitakse 3 DС-s, peab kehtima tingimus: m >= n/2; vastasel juhul võib juhtuda, et andmed pole pärast ühe DС väljalülitamist loetavad.

3. LRC — Kohalik rekonstrueerimise kood

Reida — Solomoni koodide abil andmete taastamiseks peab olema n suvalist andmeplokki. See on hajutatud andmete salvestussüsteemide puhul suur puudus, kuna ühe rikka ketta andmete taastamiseks tuleb lugeda andmeid enamikest teistest, mis tekitab kettale ja võrgule suure lisakoormuse.

Sagedasemad vead on üksiku andmeploki kättesaadavuse probleem, mis võib tuleneda ühe ketta rikke või ülekoormuse tõttu. Kas on võimalik kuidagi vähendada liigset koormust andmete taastamiseks sellistes (kõige levinumates) juhtudel? Selgub, et jah: selleks on olemas LRC üleliigsete koodide süsteem.

LRC (Kohalike Rekonstruktsioonikoodid) — Microsofti välja töötatud ülekandekoodid, mida kasutatakse Windows Azure Storage'is. LRC idee on lihtne: jagada kõik andmeplokid kahte (või rohkem) gruppi ja arvutada iga grupi jaoks eraldi osa plokke ülekandekoodidest. Niisiis, osa ülekandekoodidest arvutatakse kõigi andmeplokkide alusel (LRC-s nimetatakse neid globaalseteks ülekandekoodideks), ja osa ühe grupi andmeplokkide alusel (neid nimetatakse lokaalseteks ülekandekoodideks).

LRC tähistatakse kolme arvuga: n-r-l, kus n — andmeplokkide arv, r — globaalsete ülekandekoodide arv, l — kohalike ülekandekoodide arv. Andmete lugemiseks, kui üks andmeplokk ei ole kätte saadav, on vaja lugeda vaid n/l plokki — see on l korda vähem, kui Reed-Solomoni koodide puhul.

Kujutame näiteks LRC mudelit 6-2-2. X1–X6 — 6 andmeplokki, P1, P2 — 2 globaalset ülekandekoodide plokki, P3, P4 — 2 kohalikku ülekandekoodide plokki.

P1 ja P2 pariteedikoodide plokid arvutatakse kõigi andmeplokkide põhjal. P3 pariteedikoodi plokk arvutatakse andmeplokkide X1–X3 põhjal, P4 pariteedikoodi plokk arvutatakse andmeplokkide X4–X6 põhjal.

Ülejäänu tehakse LRC-s Reed-Salomone koodide sarnasel viisil. Suhted pariteedikoodide plokkide sõnade arvutamiseks on järgmised:

Alfa, beeta, gamma ja delta numbrite valimiseks tuleb täita hulga tingimusi, mis tagavad andmete taastamise võimaluse (st lahenduste süsteemi). Täiendavat teavet nende kohta leiate artiklis.
Samuti kasutatakse praktikas kohalike pariteedikoodide P3, P4 arvutamiseks XOR operatsiooni.

LRC võrrandisüsteemist tulenevad mitmed järeldused:

Iga 1 andmeploki taastamiseks piisab n/l ploki lugemisest (n/2 meie näites).
Kui r + l plokki pole saadaval ning kõik plokid kuuluvad ühte gruppi, siis andmeid taastada ei saa. Seda on lihtne seletada näite abil. Oletame, et plokid X1–X3 ja P3 pole saadaval: need on r + l plokid ühest grupist, 4 meie juhul. Seega on meil 3 võrrandi süsteem 4 tundmatuga, mida ei saa lahendada.
Kõikides teistes olukordades, kui r + l blokid ei ole saadaval (kui igast grupist on saadaval vähemalt üks blokk), on LRC andmed taastatav.

Seega on LRC üle Reed-Salomoni koodide andmete taastamisel üksikute vigade pärast. Reed-Salomoni koodide puhul on ühe andmeploki taastamiseks vaja kasutada n plokki, kuid LRC korral piisab ühe andmeploki taastamiseks n/l plokist (n/2 meie näites). Teisest küljest on LRC Reed-Salomoni koodidele alla jäänud lubatud vigade maksimaalses arvus. Ülaltoodud näidetes suudavad Reed-Salomoni koodid taastada andmeid igasuguste 4 vea korral, samas kui LRC puhul on 4 vea korral 2 kombinatsiooni, kus andmeid ei ole võimalik taastada.

Oluline on see, et see sõltub konkreetsest olukorrast, kuid sageli kaaluvad LRC pakkumise üleliigse koormuse kokkuhoid üles veidi väiksemad salvestamise töökindluse näitajad.

4. Teised ülekandekoodid

Lisaks Reed-Salomoni ja LRC koodidele on olemas palju teisi ülekandekoodide vorme. Erinevad koodid kasutavad erinevat matemaatikat. Siin on mõned teised ülekandekoodid:

XOR-operatsiooni abil loodud ülejäägikood. XOR-operatsioon toimub n andmeplokki üle ja tulemuseks on 1 ülejäägikoodi plokk, ehk skeem n+1 (n andmeplokki, 1 ülejäägikood). Kasutatakse RAID 5, kus andmeplokid ja ülejäägikoodid kirjutatakse tsükliliselt kõikidesse ketastesse.
Even-odd algoritm, mis põhineb XOR-operatsioonil. Selle abil saab luua 2 ülejäägikoodi plokki, ehk skeem n+2.
STAR algoritm, mis põhineb XOR-operatsioonil. Selle abil saab luua 3 ülejäägikoodi plokki, ehk skeem n+3.
Pyramide codes — veel mõned Microsofti ülejäägikoodid.

5. Kasutamine Yandexis

Mitmed Yandexi infrastruktuuri projektid kasutavad ülejäägikodeerimist andmete usaldusväärseks salvestamiseks. Siin on mõned näited:

MDS sisemine objektihoidla, millest ma rääkisin artikli alguses.
YT — Yandexi MapReduce süsteem.
YDB (Yandex DataBase) — jaotatud newSQL andmebaas.

MDS-is kasutatakse LRC ülejäägikoodide skeemi 8-2-2. Ülejäägikoodidega andmed kirjutatakse 12 erinevale kettale erinevates serverites 3 erinevas andmekeskuses: igas andmekeskuses 4 serverit. Rohkem infot leiate artiklis.

YT-s kasutatakse nii Reed-Solomoni koode (skeem 6-3), mis oli esmakordselt ellu viidud, kui ka LRC üleliigseid koode (skeem 12-2-2), kusjuures LRC on eelistatud salvestamise viis.

YDB-s kasutatakse üleliigseid koode, mis põhinevad even-odd (skeem 4-2). Üleliigsete koodide kohta YDB-s on juba räägitud Highloadis..

Erinevate üleliigsete koodide skeemide rakendamine on tingitud erinevatest nõudmistest, mida süsteemidele esitatakse. Näiteks MDS-s salvestatakse LRC-ga hallatavad andmed kohe 3 andmekeskusesse. Meile on oluline, et andmed jääksid lugemiseks kättesaadavaks, kui ükskõik milline andmekeskus ebaõnnestub, seega peavad blokkide jaotamine andmekeskuste vahel olema selline, et ühe andmekeskuse mittefunktsioneerimise korral ei ületaks mittefunktsioneerivate blokkide arv lubatud piiri. Skeemis 8-2-2 saab igas andmekeskuses paigutada 4 bloki, siis on mis tahes andmekeskuse väljalülitamise korral 4 bloki mittefunktsioneerimist, ja andmed on endiselt loetavad. Ükskõik, millist skeemi me valime 3 andmekeskusesse asetamiseks, peab igal juhul olema (r + l) / n >= 0,5, st salvestamise üleliigsus jääb vähemalt 50%.

YT-s olukord on teine: iga YT klastri täielik asukoht on 1 andmekeskuses (erinevad klastrid erinevates andmekeskustes), seega pole seal sellist piirangut. Skeem 12-2-2 pakub 33% jääkrediteerimist, mis tähendab, et andmete salvestamine on odavam, samal ajal kui need suudavad taluda kuni 4 samaaegset ketta väljalülitamist, nagu ka skeem MDS-i puhul.

Andmete salvestamise ja töötlemise süsteemides on veel palju eripära, mis puudutavad jääkrediteerimise koode: andmete taastamise nüansid, taastamise mõju päringute täitmise ajale, andmete kirjutamise eripära jne. Kavatseme rääkida eraldi nende ja muude jääkrediteerimise koodide praktilise rakendamise eripäradest, kui teema on huvitav.