Nii näeb välja üleliigne

Üksikasjad, mis käsitlevad üleliigseid koode*, on laialdaselt rakendatud arvutisüsteemides andmete salvestamise usaldusväärsuse suurendamiseks. Yandexis kasutatakse neid paljuski erinevates projektides. Näiteks on üleliigsete koodide rakendamine meie sisemises objektide salvestamise süsteemis vähendanud kulusid miljoneid ilma usaldusväärsust vähendamata. Kuid hoolimata laialdasest kasutusest on arusaadav kirjeldus selle kohta, kuidas üleliigsed koodid töötavad, üliharv. Need, kes soovivad teemaga tutvuda, seisavad silmitsi umbes järgneva olukorraga (väljavõte Vikipeediad):

Minu nimi on Vadim, Yandexis töötan ma MDS sisemiste objektide salvestamise süsteemi arendamisega. Sellel artiklil selgitan lihtsate sõnadega üleliigsete koodide (Reedi-Salomoni ja LRC koodide) teoreetilisi aluseid. Räägin, kuidas see töötab, ilma keerulise matemaatika ja haruldaste terminite puudutamiseta. Lõpus toon välja näited üleliigsete koodide kasutamisest Yandexis.

Mõned matemaatilised detailid, mida ma ei käsitle süvitsi, kuid annan lingid neile, kes soovivad sügavamale teemasse süveneda. Samuti märgin, et mõned matemaatilised määratlused ei pruugi olla rangelt täpsed, kuna artikkel ei ole suunatud matemaatikutele, vaid inseneridele, kes soovivad mõista probleemi olemust.

* Ingli keelses kirjanduses nimetatakse üleliigseid koode sageli erasure codes.

1. Üleliigsete koodide olemus

Üleliigsete koodide olemus on äärmiselt lihtne: anda andmeid nii, et need ei kaoks, kui esinevad vead (nt kõvaketaste rike, andmete edastamise vead jne).

Enamikes* üleliigsetes koodides jagatakse andmed n andmeplokiks, mille jaoks arvutatakse m üleliigse koodi plokki, kokku on n + m plokki. Üleliigsed koodid on üles ehitatud nii, et n andmeplokki on võimalik taastada, kasutades ainult osa n + m plokkidest. Edasi käsitleme ainult plokkide üleliigseid koode, see tähendab selliseid, kus andmed jagatakse plokkideks.

Kogu n andmete bloke taastamiseks on vaja vähemalt n blokki n + m blokist, sest ei saa saada n blokki, omades ainult n-1 plokki (sel juhul tuleb 1 blokk võtta "õhust"). Kas n meelevaldselt valitud plokki n + m plokist on piisavad kõigi andmete taastamiseks? See sõltub ülemääraste koodide tüübist, näiteks Reed-Solomoni koodid võimaldavad taastada kõik andmed meelevaldsete n plokkide abil, kuid LRC ülemäärased koodid ei pruugi alati seda teha.

Andmete salvestamine

Andmesalvestussüsteemides on tavaliselt iga andme- ja ülemääraste koodide plokk salvestatud eraldi kettale. Seega, kui ükskõik milline ketas rikneb, on algandmed ikkagi võimalik taastada ja lugeda. Andmeid saab taastada isegi siis, kui mitu ketast riknevad korraga.

Andmete edastamine

Ülemääraseid koode saab kasutada usaldusväärseks andmete edastamiseks ebausaldusväärses võrgus. Edastatavad andmed jagatakse plokkideks, nende jaoks arvutatakse ülemäärase koodi. Võrgus edastatakse nii andmeplokid kui ka ülemääraste koodide plokid. Kui juhuslikes plokkides (kuni teatud arvu plokini) tekivad vead, on andmete edastamine siiski usaldusväärne. Reed-Solomoni koode kasutatakse näiteks andmete edastamiseks optiliste sideliinide ja satelliitside kaudu.

* On ka ülemääraseid koode, milles andmeid ei jagata plokkideks, näiteks Hamming-koodid ja CRC-koodid, mida laialdaselt kasutatakse andmete edastamiseks Ethernet-võrkudes. Need on koodid häirekindlaks kodeerimiseks, mis on mõeldud vigade tuvastamiseks, mitte nende parandamiseks (Hamming-kood võimaldab samuti osaliselt vigu parandada).

2. Reed-Solomoni koodid

Reed-Solomoni koodid on ühed levinumad ülemäärase koodi tüübid, mis leiutati 1960. aastatel ja said esmakordselt laialdast kasutamist 1980. aastatel kompaktdiskide seeriatootmises.

Kaks peamist küsimust Reed-Solomoni koodide mõistmiseks on: 1) kuidas luua ülemääraste koodide plokke; 2) kuidas taastada andmeid ülemääraste koodide plokkide abil. Leiam sellele vastused.
Lihtsuse huvides eeldame edaspidi, et n=6 ja m=4. Teisi skeeme käsitletakse sarnasel viisil.

Kuidas luua ülemääraste koodide plokke

Iga parandusblokki loetakse sõltumatuks teistest. Iga blokki arvestamiseks kasutatakse kõiki n andmeplokke. Alloleval skeemil on X1-X6 andmeplokid, P1–P4 parandusplokid.

Kõik andmeplokid peavad olema samas suuruses, ühtlustamiseks võib kasutada nulli bitsid. Saadud parandusplokid on sama suurusega kui andmeplokid. Kõik andmeplokid jagatakse sõnadeks (nt 16 bitti). Oletame, et oleme jaganud andmeplokid k sõnaks. Siis jagatakse ka kõik parandusplokid k sõnaks.

Iga parandusploki i-ndat sõna arvestatakse kasutades kõigi andmeplokkide i-nda sõna. Need arvutatakse järgmise valemi abil:

Siin x väärtused on andmeplokkide sõnad, p on parandusplokkide sõnad, kõik alfa, beeta, gamma ja delta on eriliselt valitud numbrid, mis on kõigi i jaoks ühesugused. Tuleb kohe öelda, et kõik need väärtused ei ole tavalised numbrid, vaid Galoisi väli elemendid, operatsioonid +, -, *, / – ei ole meie jaoks harilikud operatsioonid, vaid Galoisi väli elementide peal kehtivad erilised operatsioonid.

Miks on Galoisi väljad vajalikud

Tundub, et kõik on lihtne: jagame andmed plokkideks, plokid sõnadeks, andmeplokkide sõnade abil arvestame parandusplokkide sõnu – saame parandusplokid. Üldiselt nii see toimib, kuid detailides peitub kurat:

Nagu eespool mainitud, on sõna suurus fikseeritud, meie näites 16 bitti. Ülaltoodud valemid Reed-Solomoni koodide jaoks on sellised, et tavaliste täisarvude kasutamisel võib p arvutamise tulemus olla selline, mida ei saa sobiva suurusega sõnaga esitada.
Andmete taastamisel käsitletakse ülaltoodud valemeid võrrandisüsteemina, mille lahendamiseks on vaja taastada andmed. Lahendamise käigus võib tekkida vajadus jagada täisarve üksteisega, mille tulemusena tekib reaalne arv, mida ei saa täpselt arvutisse mällu salvestada.

Need for Reed–Solomon codes prevents the use of whole numbers. The solution to the problem is original; it can be described as follows: let’s 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.

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.

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.

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.

* This is not a strict definition, more of a description.

How to Restore Data

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.

The equations for Reed–Solomon 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.

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):

Meil on süsteem, mis koosneb 4 võrrandist 4 tundmatuga, seega saame selle lahendada ja andmed taastada!

Sellest võrrandite süsteemist järelduvad mitmed järeldused andmete taastamiseks Reed-Solomoni koodide puhul (n andmeplokki, m üleliigset koodiplokki):

Andmed on taastatavad, kui kaovad mistahes m plokki või vähem. Kui kaob m+1 või rohkem plokki, ei ole andmete taastamine võimalik: m võrrandi lahendamiseks ei saa lahendada süsteemi, kus on m + 1 tundmatut.
Isegi ühe andmeploki taastamiseks tuleb kasutada mistahes n ülejäänud plokki, kusjuures võib kasutada mistahes üleliigse koodi.

Mida veel peaks teadma

Ülal toodud kirjelduses jätan tähelepanuta mitmed olulised küsimused, mille arutamiseks tuleb sügavamalt matemaatikasse süveneda. Eelkõige ei räägi ma järgmistest:

Reed-Solomoni koodide võrrandite süsteem peab omama (ainult ühte) lahendust iga tundmatute kombinatsiooni puhul (mitte rohkem kui m tundmatut). Selle nõude alusel valitakse alfade, beetade, gamma ja delta väärtused.
Võrrandite süsteemi tuleb osata automaatselt koostada (sõltuvalt sellest, millised plokid on kättesaamatud) ja lahendada.
On vajalik luua Galois' väli: antud sõna suuruse jaoks tuleb osata leida mistahes kahe elemendi operatsiooni tulemus (+, -, *, /).

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

Valiku n ja m

Kuidas praktikas valida n ja m? Praktikas kasutavad andmesalvestussüsteemid üleliigseid koode ruumi kokkuhoidmiseks, seega valitakse alati m väiksemaks kui n. Nende konkreetsed väärtused sõltuvad mitmest tegurist, sealhulgas:

Andmete salvestamise usaldusväärsus. Mida suurem on m, seda rohkem ketta tõrkeid saab üle elada, st usaldusväärsus on kõrgem.
Salvestuse üleliigsus. Mida suurem on suhe m / n, seda kõrgem on salvestuse üleliigsus ja seda kallim on süsteem.
Päringute töötlemise aeg. Mida suurem on summa n + m, seda kauem võtab aega päringutele vastamine. 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, andmete salvestamine mitmesse andmekeskusesse seab m ja n valikule täiendavaid piiranguid: ühe andmekeskuse sulgemisel peavad andmed olema ikkagi loetavad. Näiteks, andmete salvestamisel kolmes andmekeskuses peab olema täidetud tingimus: m >= n/2, vastasel juhul võib tekkida olukord, kus andmed ei ole ühe andmekeskuse sulgemisel loetavad.

3. LRC — Kohalikud rekonstrueerimiskoodid

Andmete taastamiseks Reed-Solomoni koodide abil tuleb kasutada n suvalist andmeplokki. See on väga oluline puudus hajutatud andmesalvestussüsteemide jaoks, kuna ühe katki läinud plaadi andmete taastamiseks tuleb lugeda andmeid enamuselt teistelt, luues suurt täiendavat koormust plaatidel ja võrgus.

Levinumad vead on ühe andmeploki kättesaamatuks muutumine kas plaadi rikke või ülemäärase koormuse tõttu. Kas on võimalik kuidagi vähendada liigset koormust andmete taastamiseks sellises (kõige levinumas) olukorras? Selgub, et on: selleks on olemas LRC üleliigsuse koodid.

LRC (Kohalikud rekonstrueerimiskoodid) on üleliigsuse koodid, mis mõeldi välja Microsoftis Windows Azure Storage'i rakendamiseks. LRC idee on äärmiselt lihtne: jagada kõik andmeplokid kaheks (või rohkemaks) grupiks ja arvutada iga grupi jaoks eraldi osa üleliigsuse blokke. Nii arvutatakse osa üleliigsuse blokke kõigi andmeplokkide abil (LRC-s nimetatakse neid globaalseteks üleliigsuse koodideks), ja osa ühte kahest andmeplokkide grupist (need nimetatakse kohalikele üleliigsuse koodideks).

LRC tähistatakse kolme numbri abil: n-r-l, kus n on andmeplokkide arv, r on globaalsete üleliigsuse koodide arv, l on kohalike üleliigsuse koodide arv. Ühe andmeploki kättesaamatuse korral andmete lugemiseks tuleb lugeda ainult n/l plokki — see on l korda vähem kui Reed-Solomoni koodide puhul.

Näiteks vaatame LRC skeemi 6-2-2. X1–X6 — 6 andmeplokki, P1, P2 — 2 globaalset üleliigsuse plokki, P3, P4 — 2 kohalikku üleliigsuse plokki.

Üleliigsuse plokid P1, P2 arvutatakse kõigi andmeplokkide abil. Üleliigsuse plokk P3 arvutatakse andmeplokkide X1–X3 abil, üleliigsuse plokk P4 arvutatakse andmeplokkide X4–X6 abil.

Ülejäänu tehakse LRC-s sarnaselt Reed-Solomoni koodidega. Üksused plokkide kõigi sõnade loendamiseks üleliigsete koodide seast on järgmised:

Alfa, beeta, gamma ja delta numbrite leidmiseks tuleb täita rida tingimusi, mis tagavad andmete taastamise võimaluse (st võrrandisüsteemi lahendamine). Täiendavat teavet nende kohta saab lugeda artiklis.
Samuti kasutatakse praktikas P3, P4 kohalike üleliigsete koodide loendamiseks XOR-operatsiooni.

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

Ühe andmeploki taastamiseks on piisav lugeda n/l plokki (n/2 meie näites).
Kui r + l plokki pole saadaval ja kõik plokid kuuluvad ühte gruppi, ei saa andmeid taastada. Seda on lihtne näidata näite abil. Oletame, et plokid X1–X3 ja P3 pole saadaval: see on r + l plokki ühest grupist, meie näites 4. Siis on meil 3 võrrandiga süsteem 4 tundmatuga, mida ei saa lahendada.
Kõigis teistes r + l plokkide puutumatuse juhtudel (kui igast grupist on vähemalt üks plokk saadaval) on andmed võimalik taastada LRC-s.

Seega on LRC Reed-Solomoni koodidest parem andmete taastamisel pärast üksikvigu. Reed-Solomoni koodide puhul on ühe andmeploki taastamiseks vajalik n plokki, LRC puhul piisab ühe andmeploki taastamiseks n/l plokist (n/2 meie näites). Teisest küljest on LRC Reed-Solomoni koodidest halvem maksimaalse lubatud vigade arvus. Ülaltoodud näidetes saavad Reed-Solomoni koodid taastada andmeid mis tahes 4 vea korral, samas kui LRC-l on 2 kombinatsiooni 4 veast, kui andmeid ei saa taastada.

Oluline on see, et see sõltub konkreetsest olukorrast, kuid tihti kaalub LRC-st saadud üleliigse koormuse kokkuhoid üles veidi väiksema andmete salvestamise usaldusväärsuse.

4. Muud üleliigsed koodid

Lisaks Reed-Solomoni ja LRC koodidele on olemas palju muid üleliigseid koode. Erinevad üleliigsed koodid kasutavad erinevat matemaatikat. Siin on mõned teised üleliigsed koodid:

Üleliigsete koodide XOR-operaatoriga. XOR-operatsioonit tehakse n andmeplokki ja saadakse 1 üleliigse koodiplokk, st skeem n+1 (n andmeplokki, 1 üleliigse koodiga). Kasutatakse RAID 5, kus andmeplokid ja üleliigsed koodid salvestatakse tsükliliselt kõigile kompuutri ketastele.
Even-odd algoritm, mis põhineb XOR-operatsioonil. See võimaldab luua 2 ülearune koodiblokki, st skeem n+2.
STAR algoritm, mis põhineb XOR-operatsioonil. See võimaldab luua 3 ülearune koodiblokki, st skeem n+3.
Pyramide koodid — veel ühed ülearune koodid Microsoftilt.

5. Kasutamine Yandexis

Mitmed Yandexi infrastruktuuri projektid kasutavad ülearuse koode usaldusväärse andmete salvestamise tagamiseks. Siin on mõned näited:

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

MDS-is kasutatakse LRC ülearuse koode, skeem 8-2-2. Andmed ülearuse koodidega kirjutatakse 12 erinevale kettale erinevates serverites 3 erinevas andmekeskuses: igas andmekeskuses 4 serverit. Rohkem selle kohta leiate artiklis.

YT-s kasutatakse nii Reed-Salomon koodide (skeem 6-3), mis olid esimesed ellu viidud, kui ka LRC ülearuse koode (skeem 12-2-2), kusjuures LRC on eelistatud salvestamisviis.

YDB-s kasutatakse ülearuse koode, mis põhinevad even-odd (skeem 4-2). Ülearuse koode YDB-s on juba räägitud Highload'is..

Erinevate ülearuse koodide skeemide kasutamine on tingitud erinevatest süsteemidele esitatud nõuetest. Näiteks MDS-is salvestatakse LRC abil andmed kohe 3 andmekeskuses. Meile on oluline, et andmed oleksid loetavad, kui üks andmekeskus ebaõnnestub, seetõttu peavad plokid olema jaotatud andmekeskuste vahel nii, et mis tahes andmekeskuse puudumisel oleks puuduvate plokkide arv mitte suurem kui lubatud. Skeemi 8-2-2 puhul võib igas andmekeskuses asuda 4 plokki, siis on 1 andmekeskuse väljalülitamisel puuduv 4 plokki ja andmeid on võimalik lugeda. Ükskõik, millise skeemi me valime 3 andmekeskuses, peab igal juhul olema (r + l) / n >= 0,5, st salvestamise ülearus peab olema minimaalne 50%.

YT-s on olukord teine: iga YT kluster asub täielikult 1 andmekeskuses (erinevad klastrid erinevates andmekeskustes), seega ei ole seal sellist piirangut. Skeem 12-2-2 annab 33% ülearuse, st andmete salvestamine osutub odavamaks ja need võivad taluda kuni 4 samaaegset kettavea, nagu MDS-s.

Andmed, mille üleliigsete koodide rakendamisega on seotud, hõlmavad paljusid aspekte: andmete taastamise nüansid, taastamise mõju päringute täitmise ajale, andmete salvestamise omadused jne. Kavatseme rääkida eraldi nendest ja muudest aspektidest, kui teema huvi pakub.