Ovako izgleda redundancija
Redundancijski kodovi* naširoko se koriste u računalnim sustavima za povećanje pouzdanosti pohrane podataka. U Yandexu se koriste u mnogim projektima. Na primjer, korištenje redundantnih kodova umjesto replikacije u našoj internoj pohrani objekata štedi milijune bez žrtvovanja pouzdanosti. No unatoč njihovoj širokoj upotrebi, jasni opisi rada redundantnih kodova vrlo su rijetki. Oni koji žele razumjeti suočavaju se otprilike sa sljedećim (od ):
Moje ime je Vadim, u Yandexu razvijam internu pohranu objekata MDS. U ovom ću članku jednostavnim riječima opisati teorijske temelje redundantnih kodova (Reed-Solomon i LRC kodovi). Reći ću vam kako to radi, bez složene matematike i rijetkih izraza. Na kraju ću dati primjere korištenja redundantnih kodova u Yandexu.
Neću detaljno razmatrati niz matematičkih detalja, ali ću dati poveznice za one koji žele zaroniti dublje. 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 bit problema.
* U literaturi na engleskom jeziku redundantni kodovi često se nazivaju kodovi za brisanje.
1. Suština redundantnih kodova
Bit svih redundantnih kodova je krajnje jednostavna: pohraniti (ili prenijeti) podatke tako da se ne izgube kada se pojave greške (kvar diska, greška u prijenosu podataka itd.).
U većini* redundantnih kodova, podaci su podijeljeni u n podatkovnih blokova, za koje se broji m blokova redundantnih kodova, što rezultira ukupnim brojem od n + m blokova. Redundancijski kodovi konstruirani su na takav način da se n blokova podataka može vratiti korištenjem samo dijela od n + m blokova. Zatim ćemo razmotriti samo blok 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, budući da ne možete dobiti n blokova ako imate samo n-1 blok (u ovom slučaju, morali biste uzeti 1 blok „iz mrtve točke“ zrak"). Jesu li n nasumičnih blokova od n + m blokova dovoljni za oporavak svih podataka? To ovisi o vrsti redundantnih kodova, na primjer, Reed-Solomonovi kodovi vam omogućuju oporavak svih podataka pomoću proizvoljnih n blokova, ali LRC redundantni kodovi to ne čine uvijek.
Pohrana podataka
U sustavima za pohranu podataka u pravilu se svaki od blokova podataka i blokova redundantnog koda zapisuje na poseban disk. Zatim, ako proizvoljni disk zakaže, izvorni podaci još uvijek se mogu obnoviti i pročitati. Podaci se mogu oporaviti čak i ako nekoliko diskova otkaže u isto vrijeme.
Prijenos podataka
Kodovi redundantnosti mogu se koristiti za pouzdan prijenos podataka preko nepouzdane mreže. Preneseni podaci podijeljeni su u blokove, a za njih su izračunati redundantni kodovi. Mrežom se prenose i blokovi podataka i blokovi redundantnog koda. Ako se pogreške pojave u proizvoljnim blokovima (do određenog broja blokova), podaci se i dalje mogu prenositi mrežom bez grešaka. Reed-Solomonovi kodovi, na primjer, koriste se za prijenos podataka preko optičkih komunikacijskih linija iu satelitskim komunikacijama.
* Postoje i redundantni kodovi u kojima podaci nisu podijeljeni u blokove, kao što su Hammingovi kodovi i CRC kodovi, koji se široko koriste za prijenos podataka u Ethernet mrežama. To su kodovi za kodiranje s ispravljanjem pogrešaka, dizajnirani su za otkrivanje pogrešaka, a ne za njihovo ispravljanje (Hammingov kod omogućuje i djelomično ispravljanje pogrešaka).
2. Reed-Solomonovi zakonici
Reed-Solomonovi kodovi jedan su od najčešće korištenih redundantnih kodova, izumljen 1960-ih, a prvi put široko korišten 1980-ih za masovnu proizvodnju kompaktnih diskova.
Dva su ključna pitanja za razumijevanje Reed-Solomonovih kodova: 1) kako stvoriti blokove redundantnih kodova; 2) kako oporaviti podatke korištenjem redundantnih blokova koda. Pronađimo odgovore na njih.
Radi jednostavnosti, dalje ćemo pretpostaviti da je n=6 i m=4. Druge sheme razmatraju se analogno.
Kako stvoriti blokove redundantnog koda
Svaki blok redundantnih kodova broji se neovisno o ostalima. Svih n blokova podataka koristi se za brojanje svakog bloka. U donjem dijagramu, X1-X6 su blokovi podataka, P1-P4 su blokovi redundantnog koda.
Svi podatkovni blokovi moraju biti iste veličine, a nula bitova 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 podijelimo blokove podataka u k riječi. Tada će svi blokovi redundantnih kodova također biti podijeljeni u k riječi.
Za brojanje i-te riječi svakog redundantnog bloka koristit će se i-te riječi 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. Mora se odmah reći da sve ove vrijednosti nisu obični brojevi, već elementi Galoisovog polja; operacije +, -, *, / nisu svima nama poznate operacije, već posebne operacije uvedene na elemente Galoisovog polja. polje.
Zašto su potrebna Galoisova polja?
Čini se da je sve jednostavno: dijelimo podatke u blokove, blokove u riječi, koristeći riječi blokova podataka brojimo riječi blokova redundantnog koda - dobivamo blokove redundantnog koda. Općenito to ovako funkcionira, ali vrag je u detaljima:
- Kao što je gore navedeno, veličina riječi je fiksna, u našem primjeru 16 bita. Gornje formule za Reed-Solomonove kodove su takve da kada se koriste obični cijeli brojevi, rezultat izračuna p možda neće biti moguće predstaviti korištenjem riječi važeće veličine.
- Prilikom oporavka podataka, gornje formule smatrat će se sustavom jednadžbi koje je potrebno riješiti kako bi se podaci oporavili. Tijekom procesa rješavanja može biti potrebno podijeliti cijele brojeve jedan s drugim, što rezultira stvarnim brojem koji se ne može točno prikazati u memoriji računala.
Ovi problemi sprječavaju korištenje cijelih brojeva za Reed-Solomonove kodove. Rješenje problema je originalno, može se opisati na sljedeći način: osmislimo posebne brojeve koji se mogu predstaviti riječima potrebne duljine (na primjer, 16 bita), a rezultat izvođenja svih operacija na kojima (zbrajanje , oduzimanje, množenje, dijeljenje) također će se prikazati u memoriji računala pomoću riječi potrebne duljine.
Takve "posebne" brojeve matematika proučava već dugo vremena, oni se nazivaju polja. Polje je skup elemenata s definiranim operacijama zbrajanja, oduzimanja, množenja i dijeljenja.
Galois* polja su polja za koja postoji jedinstven rezultat svake operacije (+, -, *, /) za bilo koja dva elementa polja. Galoisova polja mogu se konstruirati za brojeve koji su potencije broja 2: 2, 4, 8, 16 itd. (zapravo potencije bilo kojeg prostog broja p, ali u praksi nas zanimaju samo potencije broja 2). Na primjer, za 16-bitne riječi, ovo je polje koje sadrži 65 elemenata, za svaki par možete pronaći rezultat bilo koje operacije (+, -, *, /). Vrijednosti x, p, alfa, beta, gama, delta iz gornjih jednadžbi smatrat će se elementima Galoisovog polja za izračune.
Dakle, imamo sustav jednadžbi pomoću kojeg možemo konstruirati blokove redundantnih kodova pisanjem odgovarajućeg računalnog programa. Koristeći isti sustav jednadžbi, možete izvršiti oporavak podataka.
* Ovo nije stroga definicija, već prije opis.
Kako vratiti podatke
Obnova je potrebna kada neki od n + m blokova nedostaju. To mogu biti i blokovi podataka i blokovi redundantnog koda. Odsutnost podatkovnih blokova i/ili redundantnih kodnih blokova značit će da su odgovarajuće x i/ili p varijable nepoznate u gornjim jednadžbama.
Jednadžbe za Reed-Solomonove kodove mogu se promatrati kao sustav jednadžbi 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 podatkovni blokovi 1, 2, 3 i redundantni kodni blok 2 budu nedostupni, tada će za i-tu grupu riječi postojati sljedeći sustav jednadžbi (nepoznate su označene crvenom bojom):
Imamo sustav od 4 jednadžbe s 4 nepoznanice, što znači da ga možemo riješiti i vratiti podatke!
Iz ovog sustava jednadžbi slijedi niz zaključaka o obnavljanju podataka za Reed-Solomonove kodove (n blokova podataka, m blokova redundantnog koda):
- 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 sustav od m jednadžbi s m + 1 nepoznanica.
- Za oporavak čak i jednog podatkovnog bloka, morate koristiti bilo koji n od preostalih blokova, a možete koristiti bilo koji redundantni kod.
Što još moram znati?
U gornjem opisu izbjegavam niz važnih pitanja koja zahtijevaju dublje poniranje u matematiku. Posebno ne govorim ništa o sljedećem:
- Sustav jednadžbi za Reed-Solomonove kodove mora imati (jedinstveno) rješenje za bilo koju kombinaciju nepoznanica (ne više od m nepoznanica). Na temelju ovog zahtjeva odabiru se vrijednosti alfa, beta, gama i delta.
- Sustav jednadžbi mora se moći automatski konstruirati (ovisno o tome koji su blokovi nedostupni) i riješiti.
- Moramo izgraditi Galoisovo polje: za zadanu 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 sustavima za pohranjivanje podataka, redundancijski kodovi se koriste za uštedu prostora, tako da se m uvijek bira manje od n. Njihove specifične vrijednosti ovise o nizu čimbenika, uključujući:
- Pouzdanost pohrane podataka. Što je veći m, veći je broj kvarova na disku koji se može preživjeti, odnosno veća je pouzdanost.
- Redundantna pohrana. Što je veći omjer m/n, to će biti veća redundantnost pohrane i sustav će biti skuplji.
- Vrijeme obrade zahtjeva. Što je veći zbroj n + m, to će biti duže vrijeme odgovora na zahtjeve. Budući da čitanje podataka (tijekom oporavka) zahtijeva čitanje n blokova pohranjenih na n različitih diskova, vrijeme čitanja će biti određeno prema najsporijem disku.
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 u kojoj podaci nisu dostupni za čitanje kada je 1 DC isključen.
3. LRC - Lokalni kodeksi obnove
Za oporavak podataka korištenjem Reed-Solomonovih kodova, morate koristiti n proizvoljnih blokova podataka. Ovo je vrlo značajan nedostatak za distribuirane sustave za pohranu podataka, jer da biste vratili podatke na jedan pokvareni disk, morat ćete čitati podatke s većine ostalih, stvarajući veliko dodatno opterećenje na diskovima i mreži.
Najčešće pogreške su nedostupnost jednog bloka podataka zbog kvara ili preopterećenosti jednog diska. Je li 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 (Local Reconstruction Codes) su redundantni kodovi koje je izmislio Microsoft za korištenje u Windows Azure Storageu. Ideja LRC-a je što je moguće jednostavnija: podijelite sve blokove podataka u dvije (ili više) grupa i pročitajte dio blokova redundantnog koda za svaku grupu zasebno. Tada će se neki blokovi redundantnih kodova brojati korištenjem svih blokova podataka (u LRC-u oni se nazivaju globalnim redundantnim kodovima), a neki - korištenjem jedne od dvije grupe blokova podataka (oni se nazivaju lokalnim redundantnim kodovima).
LRC se označava s tri broja: nrl, gdje je n broj blokova podataka, r je broj globalnih redundantnih kodnih blokova, l je broj lokalnih redundantnih kodnih blokova. Za čitanje podataka kada je jedan blok podataka nedostupan, trebate čitati samo n/l blokova - to je l puta manje nego u Reed-Solomon kodovima.
Na primjer, razmotrite shemu LRC 6-2-2. X1–X6 — 6 podatkovnih blokova, P1, P2 — 2 globalna redundantna bloka, P3, P4 — 2 lokalna redundantna bloka.
Blokovi redundantnog koda P1, P2 broje se pomoću svih blokova podataka. Redundancijski kodni blok P3 - pomoću podatkovnih blokova X1-X3, redundantni kodni blok P4 - pomoću podatkovnih blokova X4-X6.
Ostatak se radi u LRC-u po analogiji s Reed-Solomonovim kodovima. Jednadžbe za brojanje riječi blokova redundantnog koda bit će:
Za odabir brojeva alfa, beta, gama, delta potrebno je ispuniti niz uvjeta koji jamče mogućnost oporavka podataka (odnosno rješavanja sustava jednadžbi). Više o njima možete pročitati u .
Također u praksi, XOR operacija se koristi za izračunavanje lokalnih redundantnih kodova P3, P4.
Iz sustava jednadžbi za LRC proizlazi niz zaključaka:
- Za oporavak bilo kojeg 1 bloka 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, tada se podaci ne mogu vratiti. To je lako objasniti primjerom. Neka su blokovi X1–X3 i P3 nedostupni: to su r + l blokovi iz iste grupe, 4 u našem slučaju. Zatim imamo sustav od 3 jednadžbe s 4 nepoznanice 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.
Stoga LRC nadmašuje Reed-Solomonove kodove u obnavljanju podataka nakon pojedinačne pogreške. U Reed-Solomonovim kodovima, za oporavak čak i jednog bloka podataka, potrebno je koristiti n blokova, au LRC-u, za oporavak jednog bloka podataka, dovoljno je koristiti n/l blokova (n/2 u našem primjeru). S druge strane, LRC je inferioran Reed-Solomonovim kodovima u pogledu maksimalnog broja dopuštenih pogrešaka. U gornjim primjerima, Reed-Solomonovi kodovi mogu oporaviti podatke za bilo koje 4 pogreške, a za LRC postoje 2 kombinacije 4 pogreške kada se podaci ne mogu oporaviti.
Što je važnije ovisi o konkretnoj situaciji, ali često uštede u prekomjernom opterećenju koje osigurava LRC nadmašuju nešto manje pouzdano skladištenje.
4. Ostali kodovi zalihosti
Osim kodova Reed-Solomon i LRC, postoje mnogi drugi redundantni kodovi. Različiti redundancijski kodovi koriste različitu matematiku. Evo nekih drugih redundantnih kodova:
- Kod redundantnosti pomoću XOR operatora. Operacija XOR izvodi se na n podatkovnih blokova, te se dobiva 1 blok redundantnih kodova, odnosno n+1 shema (n podatkovnih blokova, 1 redundantni kod). Korišteno u , gdje se blokovi podataka i redundancijski kodovi ciklički zapisuju na sve diskove niza.
- Par-nepar algoritam temeljen na operaciji XOR. Omogućuje vam da izgradite 2 bloka redundantnih kodova, odnosno shemu n+2.
- STAR algoritam temeljen na operaciji XOR. Omogućuje vam da izgradite 3 bloka redundantnih kodova, odnosno shemu n+3.
- Pyramide kodovi su još jedan redundantni kod od Microsofta.
5. Koristite u Yandexu
Brojni infrastrukturni projekti Yandexa koriste redundantne kodove za pouzdanu pohranu podataka. Evo nekoliko primjera:
- MDS interna pohrana objekata, o čemu sam pisao na početku članka.
- — MapReduce sustav Yandex.
- (Yandex baza podataka) - newSQL distribuirana baza podataka.
MDS koristi LRC redundantne kodove, shemu 8-2-2. Podaci s redundancijskim kodovima zapisuju se na 12 različitih diskova u različitim poslužiteljima u 3 različita DC-a: 4 poslužitelja u svakom DC-u. Pročitajte više o ovome u .
YT koristi Reed-Solomonove kodove (Shema 6-3), koji su prvi implementirani, i LRC redundantne kodove (Shema 12-2-2), pri čemu je LRC preferirana metoda pohrane.
YDB koristi redundantne kodove bazirane na par-nepar (Slika 4-2). Već o redundantnim kodovima u YDB-u .
Korištenje različitih shema redundantnog koda je zbog različitih zahtjeva za sustave. Na primjer, u MDS-u, podaci pohranjeni pomoću LRC-a smješteni su u 3 DC-a odjednom. Za nas je važno da podaci ostanu dostupni za čitanje ako 1 od bilo kojeg DC-a ne uspije, stoga blokovi moraju biti raspoređeni po DC-ovima tako da, ako je bilo koji DC nedostupan, broj nedostupnih blokova nije veći od dopuštenog. U shemi 8-2-2 možete postaviti 4 bloka u svaki DC, a zatim kada je bilo koji DC isključen, 4 bloka će biti nedostupna, a podaci se mogu čitati. Koju god shemu odabrali kada ga postavljamo u 3 DC-a, u svakom slučaju treba postojati (r + l) / n >= 0,5, odnosno redundancija pohrane bit će najmanje 50%.
U YT situacija je drugačija: svaki YT klaster je u cijelosti smješten u 1 DC (različiti klasteri u različitim DC), tako da nema tog ograničenja. Shema 12-2-2 daje 33% redundancije, odnosno pohranjivanje podataka je jeftinije, a može preživjeti i do 4 istovremena ispada diska, baš kao i MDS shema.
Postoji mnogo više značajki upotrebe redundantnih kodova u sustavima za pohranu i obradu podataka: nijanse oporavka podataka, utjecaj oporavka na vrijeme izvršenja upita, značajke snimanja podataka itd. O ovim i drugim značajkama ću govoriti zasebno korištenja redundantnih kodova u praksi, ako će tema biti zanimljiva.
6. Poveznice
- Niz članaka o Reed-Solomon kodovima i Galoisovim poljima:
Oni pristupačnim jezikom dublje sagledavaju matematiku. - Microsoftov članak o LRC-u:
Odjeljak 2 ukratko objašnjava teoriju, a zatim raspravlja o iskustvima s LRC-om u praksi. - Shema par-nepar:
- STAR shema:
- Šifre piramide:
- Redundancijski kodovi u MDS-u:
- Redundantni kodovi u YT-u:
- Redundantni kodovi u YDB-u:
Izvor: www.habr.com