Ovako izgleda višak

Redundantni kodovi* se široko koriste u računarskim sistemima za povećanje pouzdanosti skladištenja podataka. U Yandexu se koriste u mnogim projektima. Na primjer, korištenje redundantnih kodova umjesto replikacije u našoj internoj pohrani objekata štedi milione bez žrtvovanja pouzdanosti. Ali uprkos njihovoj širokoj upotrebi, jasni opisi kako funkcionišu redundantni kodovi su veoma retki. Oni koji žele razumjeti suočavaju se sa otprilike sljedećim (iz Wikipedia):

Moje ime je Vadim, u Yandexu razvijam MDS internu pohranu objekata. U ovom članku ću jednostavnim riječima opisati teorijske osnove redundantnih kodova (Reed-Solomon i LRC kodovi). Reći ću vam kako to funkcionira, bez složene matematike i rijetkih termina. Na kraju ću dati primjere korištenja redundantnih kodova u Yandexu.

Neću detaljno razmatrati brojne matematičke detalje, ali ću dati linkove za one koji žele dublje zaroniti. Također ću napomenuti da neke matematičke definicije možda nisu stroge, jer članak nije namijenjen matematičarima, već inženjerima koji žele razumjeti suštinu problema.

* U literaturi na engleskom jeziku, redundantni kodovi se često nazivaju kodovima za brisanje.

1. Suština redundantnih kodova

Suština svih redundantnih kodova je krajnje jednostavna: pohraniti (ili prenijeti) podatke tako da se ne izgube kada se pojave greške (kvarovi diska, greške u prijenosu podataka, itd.).

U većini* redundantnih kodova, podaci su podijeljeni u n blokova podataka, za koje se broji m blokova redundantnih kodova, što rezultira ukupno n + m blokova. Redundantni kodovi su konstruisani na takav način da se n blokova podataka može povratiti koristeći samo dio od n + m blokova. Zatim ćemo razmotriti samo blokove redundantne kodove, odnosno one u kojima su podaci podijeljeni u blokove.

Da biste oporavili svih n blokova podataka, morate imati najmanje n od n + m blokova, jer ne možete dobiti n blokova ako imate samo n-1 blok (u ovom slučaju, morali biste uzeti 1 blok iz tankog zrak"). Da li je n nasumičnih blokova od n + m blokova dovoljno za oporavak svih podataka? Ovo ovisi o vrsti redundantnih kodova, na primjer, Reed-Solomon kodovi vam omogućavaju da oporavite sve podatke koristeći proizvoljnih n blokova, ali LRC redundantni kodovi to ne čine uvijek.

Pohrana podataka

U sistemima za pohranu podataka, po pravilu, svaki od blokova podataka i blokova redundantnog koda zapisuje se na poseban disk. Zatim, ako proizvoljni disk pokvari, originalni podaci se i dalje mogu vratiti i pročitati. Podaci se mogu oporaviti čak i ako nekoliko diskova otkaže u isto vrijeme.

Prijenos podataka

Kodovi redundantnosti se mogu koristiti za pouzdan prijenos podataka preko nepouzdane mreže. Preneseni podaci se dijele na blokove i za njih se izračunavaju redundantni kodovi. I blokovi podataka i blokovi redundantnog koda se prenose preko mreže. Ako dođe do greške u proizvoljnim blokovima (do određenog broja blokova), podaci se i dalje mogu prenositi preko mreže bez greške. Reed-Solomon kodovi se, na primjer, koriste za prijenos podataka preko optičkih komunikacijskih linija iu satelitskim komunikacijama.

* Postoje i redundantni kodovi u kojima se podaci ne dijele na blokove, kao što su Hamming kodovi i CRC kodovi, koji se široko koriste za prijenos podataka u Ethernet mrežama. Ovo su kodovi za kodiranje za ispravljanje grešaka, dizajnirani su da otkriju greške, a ne da ih ispravljaju (Hemmingov kod takođe omogućava delimičnu ispravku grešaka).

2. Reed-Solomon kodovi

Reed-Solomon kodovi su jedan od najčešće korištenih redundantnih kodova, izmišljeni još 1960-ih i prvi put široko korišteni 1980-ih za masovnu proizvodnju kompaktnih diskova.

Postoje dva ključna pitanja za razumevanje Reed-Solomon kodova: 1) kako kreirati blokove redundantnih kodova; 2) kako oporaviti podatke koristeći redundantne kodne blokove. Hajde da nađemo odgovore na njih.
Radi jednostavnosti, dalje ćemo pretpostaviti da je n=6 i m=4. Druge sheme se razmatraju analogno.

Kako kreirati redundantne blokove koda

Svaki blok redundantnih kodova se broji nezavisno od ostalih. Svih n blokova podataka se koriste za brojanje svakog bloka. U dijagramu ispod, X1-X6 su blokovi podataka, P1-P4 su blokovi redundantnog koda.

Svi blokovi podataka moraju biti iste veličine, a nulti bitovi se mogu koristiti za poravnanje. Rezultirajući blokovi redundantnog koda bit će iste veličine kao blokovi podataka. Svi blokovi podataka podijeljeni su u riječi (na primjer, 16 bita). Recimo da smo blokove podataka podijelili na k riječi. Tada će svi blokovi redundantnih kodova također biti podijeljeni na k riječi.

Za brojanje i-te riječi svakog redundantnog bloka, koristit će se i-ta riječ svih blokova podataka. Oni će se izračunati prema sljedećoj formuli:

Ovdje su vrijednosti x riječi blokova podataka, p su riječi blokova redundantnog koda, svi alfa, beta, gama i delta su posebno odabrani brojevi koji su isti za sve i. Odmah se mora reći da sve ove vrijednosti nisu obični brojevi, već elementi polja Galois, operacije +, -, *, / nisu operacije poznate svima nama, već posebne operacije uvedene na elemente Galoisovog polja; polje.

Zašto su Galois polja potrebna?

Čini se da je sve jednostavno: podatke dijelimo na blokove, blokove na riječi, koristeći riječi blokova podataka brojimo riječi blokova redundantnog koda - dobivamo blokove redundantnog koda. Općenito ovako funkcionira, ali đavo je u detaljima:

Kao što je gore navedeno, veličina riječi je fiksna, u našem primjeru 16 bita. Formule iznad za Reed-Solomon kodove su takve da kada se koriste obični cijeli brojevi, rezultat izračunavanja p možda neće biti predstavljen korištenjem riječi važeće veličine.
Prilikom oporavka podataka, gornje formule će se smatrati sistemom jednačina koje se moraju riješiti da bi se podaci oporavili. Tokom procesa rješavanja, možda će biti potrebno podijeliti cijele brojeve jedni s drugima, što rezultira realnim brojem koji se ne može precizno predstaviti u memoriji računala.

Ovi problemi sprečavaju upotrebu celih brojeva za Reed-Solomon kodove. Rješenje problema je originalno, može se opisati na sljedeći način: smislimo posebne brojeve koji se mogu predstaviti riječima potrebne dužine (na primjer, 16 bita), i rezultat izvođenja svih operacija nad kojima (zbrajanje , oduzimanje, množenje, dijeljenje) će se također prikazati u memoriji računala pomoću riječi potrebne dužine.

Takve “posebne” brojeve matematika proučava već dugo vremena; Polje je skup elemenata za koje su definirane operacije sabiranja, oduzimanja, množenja i dijeljenja.

Galois* polja su polja za koja postoji jedinstveni rezultat svake operacije (+, -, *, /) za bilo koja dva elementa polja. Galois polja se mogu konstruisati za brojeve koji su stepena 2: 2, 4, 8, 16, itd. (zapravo stepena bilo kojeg prostog broja p, ali u praksi nas zanimaju samo stepeni 2). Na primjer, za 16-bitne riječi, ovo je polje koje sadrži 65 elemenata, za svaki par od kojih možete pronaći rezultat bilo koje operacije (+, -, *, /). Vrijednosti x, p, alfa, beta, gama, delta iz gornjih jednačina će se smatrati elementima Galois polja za proračune.

Dakle, imamo sistem jednačina sa kojima možemo konstruisati blokove redundantnih kodova pisanjem odgovarajućeg kompjuterskog programa. Koristeći isti sistem jednačina, možete izvršiti oporavak podataka.

* Ovo nije stroga definicija, već opis.

Kako oporaviti podatke

Restauracija je potrebna kada neki od n + m blokova nedostaju. To mogu biti i blokovi podataka i blokovi redundantnog koda. Odsustvo blokova podataka i/ili blokova redundantnog koda će značiti da su odgovarajuće x i/ili p varijable nepoznate u gornjim jednačinama.

Jednačine za Reed-Solomon kodove se mogu posmatrati kao sistem jednačina u kojem su sve alfa, beta, gama, delta vrijednosti konstante, svi x i p koji odgovaraju dostupnim blokovima su poznate varijable, a preostali x i p su nepoznati.

Na primjer, neka blokovi podataka 1, 2, 3 i blok kodova redundancije 2 budu nedostupni, tada će za i-tu grupu riječi postojati sljedeći sistem jednadžbi (nepoznate su označene crvenom bojom):

Imamo sistem od 4 jednačine sa 4 nepoznate, što znači da ga možemo riješiti i vratiti podatke!

Iz ovog sistema jednadžbi slijedi niz zaključaka o obnavljanju podataka za Reed-Solomon kodove (n blokova podataka, m blokova redundantnih kodova):

Podaci se mogu oporaviti ako se izgubi bilo koji m blokova ili manje. Ako se izgubi m+1 ili više blokova, podaci se ne mogu vratiti: nemoguće je riješiti sistem m jednačina sa m + 1 nepoznatim.
Da biste obnovili čak i jedan blok podataka, trebate koristiti bilo koji n preostalih blokova, a možete koristiti bilo koji od redundantnih kodova.

Šta još treba da znate

U gornjem opisu izbjegavam niz važnih pitanja koja zahtijevaju dublje uronjenje u matematiku. Konkretno, ne govorim ništa o sljedećem:

Sistem jednačina za Reed-Solomon kodove mora imati (jedinstveno) rješenje za bilo koju kombinaciju nepoznatih (ne više od m nepoznatih). Na osnovu ovog zahtjeva biraju se vrijednosti alfa, beta, gama i delta.
Sistem jednačina mora biti u stanju da se automatski konstruiše (u zavisnosti od toga koji blokovi su nedostupni) i reši.
Moramo izgraditi Galois polje: za datu veličinu riječi, moći pronaći rezultat bilo koje operacije (+, -, *, /) za bilo koja dva elementa.

Na kraju članka nalaze se reference na literaturu o ovim važnim pitanjima.

Izbor n i m

Kako odabrati n i m u praksi? U praksi, u sistemima za skladištenje podataka, redundantni kodovi se koriste za uštedu prostora, pa se m uvijek bira manje od n. Njihove specifične vrijednosti zavise od brojnih faktora, uključujući:

Pouzdanost skladištenja podataka. Što je veći m, to je veći broj kvarova diska koji se mogu preživjeti, odnosno veća je pouzdanost.
Redundantna pohrana. Što je veći m/n odnos, to će biti veća redundantnost skladištenja, a sistem će biti skuplji.
Vrijeme obrade zahtjeva. Što je veći zbir n + m, duže će biti vrijeme odgovora na zahtjeve. Budući da čitanje podataka (tokom oporavka) zahtijeva čitanje n blokova pohranjenih na n različitih diskova, vrijeme čitanja će biti određeno najsporijim diskom.

Osim toga, pohranjivanje podataka u nekoliko DC-ova nameće dodatna ograničenja na izbor n i m: ako je 1 DC isključen, podaci i dalje moraju biti dostupni za čitanje. Na primjer, kada se podaci pohranjuju u 3 DC-a, mora biti ispunjen sljedeći uvjet: m >= n/2, inače može doći do situacije da podaci nisu dostupni za čitanje kada je 1 DC isključen.

3. LRC - Lokalni kodovi za rekonstrukciju

Da biste oporavili podatke pomoću Reed-Solomon kodova, morate koristiti n proizvoljnih blokova podataka. Ovo je veoma značajan nedostatak za distribuirane sisteme za skladištenje podataka, jer da biste vratili podatke na jednom pokvarenom disku, moraćete da čitate podatke sa većine drugih, stvarajući veliko dodatno opterećenje na diskovima i mreži.

Najčešće greške su nedostupnost jednog bloka podataka zbog kvara ili preopterećenja jednog diska. Da li je moguće nekako smanjiti višak opterećenja za oporavak podataka u ovom (najčešćem) slučaju? Ispostavilo se da možete: postoje LRC redundantni kodovi posebno za ovu svrhu.

LRC (Lokalne rekonstrukcijske šifre) su redundantni kodovi koje je razvio Microsoft za upotrebu u Windows Azure Storage. Ideja iza LRC-a je vrlo jednostavna: podijeliti sve blokove podataka u dvije (ili više) grupa i izračunati dio blokova redundančnog koda za svaku grupu zasebno. Zatim će se neki od blokova redundančnog koda izračunati korištenjem svih blokova podataka (u LRC-u se to naziva globalni redundančni kodovi), a neki će se izračunati korištenjem jedne od dvije grupe blokova podataka (oni se nazivaju lokalni redundančni kodovi).

LRC je označen sa tri broja: nrl, gdje je n broj blokova podataka, r je broj blokova globalnog redundantnog koda, l je broj blokova lokalnog redundantnog koda. Da biste pročitali podatke kada je jedan blok podataka nedostupan, morate pročitati samo n/l blokova - to je l puta manje nego u Reed-Solomon kodovima.

Na primjer, razmotrite LRC 6-2-2 shemu. X1–X6 — 6 blokova podataka, P1, P2 — 2 globalna redundantna bloka, P3, P4 — 2 lokalna redundantna bloka.

Redundantni kodni blokovi P1, P2 se broje koristeći sve blokove podataka. Redundantni kodni blok P3 - korištenjem blokova podataka X1-X3, redundantni kodni blok P4 - korištenjem podatkovnih blokova X4-X6.

Ostalo se radi u LRC-u po analogiji sa Reed-Solomon kodovima. Jednačine za brojanje riječi redundantnih kodnih blokova će biti:

Da biste odabrali brojeve alfa, beta, gama, delta, moraju biti ispunjeni brojni uslovi koji garantuju mogućnost oporavka podataka (tj. rješavanja sistema jednačina). Više o njima možete pročitati u članak.
Također u praksi, operacija XOR se koristi za izračunavanje lokalnih redundantnih kodova P3, P4.

Iz sistema jednadžbi za LRC slijedi niz zaključaka:

Da biste povratili bilo koji 1 blok podataka, dovoljno je pročitati n/l blokova (n/2 u našem primjeru).
Ako su r + l blokovi nedostupni, a svi blokovi su uključeni u jednu grupu, podaci se ne mogu vratiti. Ovo je lako objasniti na primjeru. Neka su blokovi X1–X3 i P3 nedostupni: to su r + l blokovi iz iste grupe, u našem slučaju 4. Tada imamo sistem od 3 jednačine sa 4 nepoznate koje se ne mogu riješiti.
U svim ostalim slučajevima nedostupnosti r + l blokova (kada je barem jedan blok dostupan iz svake grupe), podaci u LRC-u se mogu vratiti.

Dakle, LRC nadmašuje Reed-Solomon kodove u oporavku podataka nakon pojedinačnih grešaka. U Reed-Solomon kodovima, da biste povratili čak i jedan blok podataka, potrebno je koristiti n blokova, a u LRC-u, za oporavak jednog bloka podataka, dovoljno je koristiti n/l blokova (n/2 u našem primjeru). S druge strane, LRC je inferiorniji od Reed-Solomon kodova u smislu maksimalnog broja dozvoljenih grešaka. U gornjim primjerima, Reed-Solomon kodovi mogu oporaviti podatke za bilo koje 4 greške, a za LRC postoje 2 kombinacije od 4 greške kada se podaci ne mogu oporaviti.

Ono što je još važnije zavisi od konkretne situacije, ali često uštede u višku opterećenja koje LRC obezbeđuje nadmašuju nešto manje pouzdano skladištenje.

4. Druge redundantne šifre

Osim kodova Reed-Solomon i LRC, postoje mnogi drugi kodovi redundancije. Različiti kodovi redundancije koriste različitu matematiku. Evo još nekih kodova redundancije:

Redundantni kod koji koristi XOR operator. XOR operacija se izvodi na n blokova podataka i dobija se 1 blok redundantnih kodova, odnosno n+1 šema (n blokova podataka, 1 redundantni kod). Korišćen u RAID 5, gdje se blokovi podataka i redundantni kodovi ciklički upisuju na sve diskove niza.
Parno-neparni algoritam baziran na operaciji XOR. Omogućava vam da izgradite 2 bloka redundantnih kodova, odnosno n+2 šemu.
STAR algoritam baziran na operaciji XOR. Omogućava vam da napravite 3 bloka redundantnih kodova, odnosno n+3 šeme.
Piramidni kodovi su još jedan Microsoftov redundantni kod.

5. Koristite u Yandexu

Brojni Yandex infrastrukturni projekti koriste redundantne kodove za pouzdano skladištenje podataka. Evo nekoliko primjera:

MDS interno skladištenje objekata, o čemu sam pisao na početku članka.
YT — MapReduce sistem Yandex.
YDB (Yandex DataBase) - novaSQL distribuirana baza podataka.

MDS koristi LRC redundantne kodove, šemu 8-2-2. Podaci sa redundantnim kodovima se zapisuju na 12 različitih diskova u različitim serverima u 3 različita DC-a: 4 servera u svakom DC-u. Više o ovome pročitajte u članak.

YT koristi i Reed-Solomon kodove (Shema 6-3), koji su prvi implementirani, i LRC redundantne kodove (Shema 12-2-2), pri čemu je LRC poželjna metoda skladištenja.

YDB koristi redundantne kodove bazirane na par-nepar (slika 4-2). O redundantnim kodovima u YDB-u već rečeno na Highload-u.

Upotreba različitih shema redundantnog koda je posljedica različitih zahtjeva za sisteme. Na primjer, u MDS-u, podaci pohranjeni pomoću LRC-a se stavljaju u 3 DC-a odjednom. Za nas je važno da podaci ostanu dostupni za čitanje ako 1 od bilo kojeg DC-a otkaže, stoga blokovi moraju biti raspoređeni među DC-ovima tako da ako je bilo koji DC nedostupan, broj nedostupnih blokova nije veći od dozvoljenog. U shemi 8-2-2, možete postaviti 4 bloka u svaki DC, a onda kada je bilo koji DC isključen, 4 bloka će biti nedostupna i podaci se mogu čitati. Koju god shemu da odaberemo kada je smještamo u 3 DC, u svakom slučaju treba biti (r + l) / n >= 0,5, odnosno redundantnost skladištenja će biti najmanje 50%.

U YT situacija je drugačija: svaki YT klaster je u potpunosti lociran u 1 DC (različiti klasteri u različitim DC-ovima), tako da nema takvog ograničenja. Šema 12-2-2 pruža 33% redundantnosti, odnosno pohranjivanje podataka je jeftinije, a može preživjeti i do 4 istovremena prekida rada diska, baš kao i MDS šema.

Postoji mnogo više karakteristika upotrebe redundantnih kodova u sistemima za skladištenje i obradu podataka: nijanse oporavka podataka, uticaj oporavka na vreme izvršenja upita, karakteristike snimanja podataka, itd. O ovim i drugim karakteristikama ću govoriti odvojeno. upotrebe redundantnih kodova u praksi, ako će tema biti interesantna.