Kjo është se si duket teprica
Kodet e tepricës* përdoren gjerësisht në sistemet kompjuterike për të rritur besueshmërinë e ruajtjes së të dhënave. Në Yandex ato përdoren në shumë projekte. Për shembull, përdorimi i kodeve të tepricës në vend të përsëritjes në ruajtjen e objekteve tona të brendshme kursen miliona pa sakrifikuar besueshmërinë. Por pavarësisht përdorimit të tyre të gjerë, përshkrimet e qarta se si funksionojnë kodet e tepricës janë shumë të rralla. Ata që duan të kuptojnë përballen afërsisht me sa vijon (nga ):
Emri im është Vadim, në Yandex po zhvilloj ruajtjen e objekteve të brendshme MDS. Në këtë artikull, unë do të përshkruaj me fjalë të thjeshta bazat teorike të kodeve të tepricës (kodet Reed-Solomon dhe LRC). Unë do t'ju tregoj se si funksionon, pa matematikë komplekse dhe terma të rrallë. Në fund do të jap shembuj të përdorimit të kodeve të tepricës në Yandex.
Unë nuk do të shqyrtoj një numër detajesh matematikore në detaje, por do të jap lidhje për ata që duan të zhyten më thellë. Do të vërej gjithashtu se disa përkufizime matematikore mund të mos jenë strikte, pasi artikulli nuk është menduar për matematikanët, por për inxhinierët që duan të kuptojnë thelbin e çështjes.
* Në literaturën në gjuhën angleze, kodet e tepricës quhen shpesh kode fshirjeje.
1. Thelbi i kodeve të tepricës
Thelbi i të gjithë kodeve të tepricës është jashtëzakonisht i thjeshtë: ruani (ose transmetoni) të dhënat në mënyrë që të mos humbasin kur ndodhin gabime (dështimet e diskut, gabimet e transferimit të të dhënave, etj.).
Në shumicën e kodeve* të tepricës, të dhënat ndahen në n blloqe të dhënash, për të cilat numërohen m blloqe kodesh tepricë, duke rezultuar në një total prej n + m blloqe. Kodet e tepricës janë ndërtuar në atë mënyrë që n blloqe të dhënash të mund të rikuperohen duke përdorur vetëm një pjesë të blloqeve n + m. Më pas, ne do të shqyrtojmë vetëm kodet e tepricës së bllokut, domethënë ato në të cilat të dhënat ndahen në blloqe.
Për të rikuperuar të gjitha n blloqet e të dhënave, duhet të keni të paktën n nga n + m blloqe, pasi nuk mund të merrni n blloqe duke pasur vetëm n-1 bllok (në këtë rast, do të duhet të merrni 1 bllok "nga i hollë ajri”). A mjaftojnë n blloqe të rastësishme prej n + m blloqe për të rikuperuar të gjitha të dhënat? Kjo varet nga lloji i kodeve të tepricës, për shembull, kodet Reed-Solomon ju lejojnë të rikuperoni të gjitha të dhënat duke përdorur n blloqe arbitrare, por kodet e tepricës LRC jo gjithmonë.
Ruajtja e të dhënave
Në sistemet e ruajtjes së të dhënave, si rregull, secili prej blloqeve të të dhënave dhe blloqeve të kodit të tepricës shkruhet në një disk të veçantë. Pastaj, nëse një disk arbitrar dështon, të dhënat origjinale ende mund të restaurohen dhe lexohen. Të dhënat mund të rikuperohen edhe nëse disa disqe dështojnë në të njëjtën kohë.
Transferimi i të dhënave
Kodet e tepricës mund të përdoren për të transmetuar në mënyrë të besueshme të dhëna përmes një rrjeti jo të besueshëm. Të dhënat e transmetuara ndahen në blloqe dhe për to llogariten kodet e tepricës. Të dy blloqet e të dhënave dhe blloqet e kodeve të tepërta transmetohen përmes rrjetit. Nëse ndodhin gabime në blloqe arbitrare (deri në një numër të caktuar blloqesh), të dhënat ende mund të transmetohen në rrjet pa gabime. Kodet Reed-Solomon, për shembull, përdoren për të transmetuar të dhëna mbi linjat e komunikimit optik dhe në komunikimet satelitore.
* Ekzistojnë gjithashtu kode të tepërta në të cilat të dhënat nuk ndahen në blloqe, si kodet Hamming dhe kodet CRC, të cilat përdoren gjerësisht për transmetimin e të dhënave në rrjetet Ethernet. Këto janë kode për kodimin e korrigjimit të gabimeve, ato janë krijuar për të zbuluar gabimet dhe jo për t'i korrigjuar ato (kodi Hamming gjithashtu lejon korrigjimin e pjesshëm të gabimeve).
2. Kodet Reed-Solomon
Kodet Reed-Solomon janë një nga kodet më të përdorura të tepricës, të shpikur në vitet 1960 dhe të përdorura për herë të parë gjerësisht në vitet 1980 për prodhimin masiv të disqeve kompakte.
Ka dy pyetje kyçe për të kuptuar kodet Reed-Solomon: 1) si të krijohen blloqe kodesh tepricë; 2) si të rikuperoni të dhënat duke përdorur blloqe kodi të tepërt. Le të gjejmë përgjigje për to.
Për thjeshtësi, më tej do të supozojmë se n=6 dhe m=4. Skemat e tjera konsiderohen me analogji.
Si të krijoni blloqe kodesh tepricë
Çdo bllok i kodeve të tepricës llogaritet në mënyrë të pavarur nga të tjerët. Të gjitha n blloqet e të dhënave përdoren për të numëruar çdo bllok. Në diagramin e mëposhtëm, X1-X6 janë blloqe të dhënash, P1-P4 janë blloqe kodesh të tepërta.
Të gjitha blloqet e të dhënave duhet të kenë të njëjtën madhësi dhe zero bit mund të përdoren për rreshtim. Blloqet e kodit të tepricës që rezultojnë do të kenë të njëjtën madhësi si blloqet e të dhënave. Të gjitha blloqet e të dhënave ndahen në fjalë (për shembull, 16 bit). Le të themi se i ndajmë blloqet e të dhënave në k fjalë. Pastaj të gjitha blloqet e kodeve të tepricës do të ndahen gjithashtu në k fjalë.
Për të numëruar fjalën i-të të çdo blloku të tepricës, do të përdoren fjalët i-të të të gjitha blloqeve të të dhënave. Ato do të llogariten sipas formulës së mëposhtme:
Këtu vlerat x janë fjalët e blloqeve të të dhënave, p janë fjalët e blloqeve të kodit të tepricës, të gjithë alfa, beta, gama dhe delta janë numra të zgjedhur posaçërisht që janë të njëjtë për të gjithë i. Duhet thënë menjëherë se të gjitha këto vlera nuk janë numra të zakonshëm, por elementë të fushës Galois; operacionet +, -, *, / nuk janë operacione të njohura për të gjithë ne, por operacione speciale të futura në elementë të Galois. fushë.
Pse nevojiten fushat Galois?
Duket se gjithçka është e thjeshtë: ne i ndajmë të dhënat në blloqe, blloqet në fjalë, duke përdorur fjalët e blloqeve të të dhënave, numërojmë fjalët e blloqeve të kodit të tepricës - marrim blloqe të kodit të tepricës. Në përgjithësi, kështu funksionon, por djalli është në detaje:
- Siç u tha më lart, madhësia e fjalës është fikse, në shembullin tonë 16 bit. Formulat e mësipërme për kodet Reed-Solomon janë të tilla që kur përdoren numra të plotë të zakonshëm, rezultati i llogaritjes p mund të mos jetë i përfaqësuar duke përdorur një fjalë me madhësi të vlefshme.
- Kur rikuperoni të dhënat, formulat e mësipërme do të konsiderohen si një sistem ekuacionesh që duhet të zgjidhen për të rikuperuar të dhënat. Gjatë procesit të zgjidhjes, mund të jetë e nevojshme të ndahen numrat e plotë me njëri-tjetrin, duke rezultuar në një numër real që nuk mund të përfaqësohet me saktësi në kujtesën e kompjuterit.
Këto probleme parandalojnë përdorimin e numrave të plotë për kodet Reed-Solomon. Zgjidhja e problemit është origjinale, mund të përshkruhet si më poshtë: le të dalim me numra të veçantë që mund të përfaqësohen duke përdorur fjalë të gjatësisë së kërkuar (për shembull, 16 bit), dhe rezultatin e kryerjes së të gjitha operacioneve në të cilat (shtimi , zbritja, shumëzimi, pjesëtimi) do të paraqiten gjithashtu në kujtesën e kompjuterit duke përdorur fjalë të gjatësisë së kërkuar.
Numra të tillë "të veçantë" janë studiuar nga matematika për një kohë të gjatë; ato quhen fusha. Një fushë është një grup elementësh me veprimet e mbledhjes, zbritjes, shumëzimit dhe pjesëtimit të përcaktuara për to.
Fushat Galois* janë fusha për të cilat ka një rezultat unik të secilit operacion (+, -, *, /) për çdo dy elementë të fushës. Fushat Galois mund të ndërtohen për numra që janë fuqitë e 2: 2, 4, 8, 16, etj. (në fakt fuqitë e çdo numri të thjeshtë p, por në praktikë ne jemi të interesuar vetëm për fuqitë e 2). Për shembull, për fjalët 16-bit, kjo është një fushë që përmban 65 elementë, për secilën palë prej të cilave mund të gjeni rezultatin e çdo operacioni (+, -, *, /). Vlerat e x, p, alfa, beta, gama, delta nga ekuacionet e mësipërme do të konsiderohen elementë të fushës Galois për llogaritjet.
Kështu, ne kemi një sistem ekuacionesh me të cilin mund të ndërtojmë blloqe kodesh të tepricës duke shkruar një program të përshtatshëm kompjuterik. Duke përdorur të njëjtin sistem ekuacionesh, mund të kryeni rikuperimin e të dhënave.
* Ky nuk është një përkufizim i rreptë, por më tepër një përshkrim.
Si të rikuperoni të dhënat
Restaurimi nevojitet kur disa nga blloqet n + m mungojnë. Këto mund të jenë blloqe të dhënash dhe blloqe kodesh të tepërta. Mungesa e blloqeve të të dhënave dhe/ose blloqeve të kodit të tepricës do të thotë që variablat korrespondues x dhe/ose p janë të panjohura në ekuacionet e mësipërme.
Ekuacionet për kodet Reed-Solomon mund të shihen si një sistem ekuacionesh në të cilat të gjitha vlerat alfa, beta, gama, delta janë konstante, të gjitha x dhe p që korrespondojnë me blloqet e disponueshme janë variabla të njohur, dhe x dhe p të mbetura. janë të panjohura.
Për shembull, le të mos disponohen blloqet e të dhënave 1, 2, 3 dhe blloku i kodit të tepërt 2, atëherë për grupin e i-të të fjalëve do të ketë sistemin e mëposhtëm të ekuacioneve (të panjohurat janë shënuar me të kuqe):
Ne kemi një sistem prej 4 ekuacionesh me 4 të panjohura, që do të thotë se mund ta zgjidhim atë dhe të rivendosim të dhënat!
Nga ky sistem ekuacionesh rrjedhin një sërë përfundimesh në lidhje me rikuperimin e të dhënave për kodet Reed-Solomon (n blloqe të dhënash, m blloqe kodesh tepricë):
- Të dhënat mund të rikuperohen nëse humbet ndonjë m blloqe ose më pak. Nëse m+1 ose më shumë blloqe humbasin, të dhënat nuk mund të rikthehen: është e pamundur të zgjidhet një sistem me ekuacione m me m + 1 të panjohura.
- Për të rikuperuar qoftë edhe një bllok të dhënash, duhet të përdorni cilindo nga blloqet e mbetura dhe mund të përdorni cilindo nga kodet e tepricës.
Çfarë tjetër duhet të dini
Në përshkrimin e mësipërm, unë shmang një numër çështjesh të rëndësishme që kërkojnë një zhytje më të thellë në matematikë për t'u marrë në konsideratë. Në veçanti, nuk po them asgjë për sa vijon:
- Sistemi i ekuacioneve për kodet Reed-Solomon duhet të ketë një zgjidhje (unike) për çdo kombinim të panjohurash (jo më shumë se m të panjohura). Bazuar në këtë kërkesë, zgjidhen vlerat e alfa, beta, gama dhe delta.
- Një sistem ekuacionesh duhet të jetë në gjendje të ndërtohet automatikisht (në varësi të cilat blloqe nuk janë të disponueshme) dhe të zgjidhet.
- Duhet të ndërtojmë një fushë Galois: për një madhësi të caktuar fjale, të jemi në gjendje të gjejmë rezultatin e çdo operacioni (+, -, *, /) për çdo dy element.
Në fund të artikullit ka referenca për literaturën për këto çështje të rëndësishme.
Zgjedhja e n dhe m
Si të zgjidhni n dhe m në praktikë? Në praktikë, në sistemet e ruajtjes së të dhënave, kodet e tepricës përdoren për të kursyer hapësirë, kështu që m zgjidhet gjithmonë më pak se n. Vlerat e tyre specifike varen nga një numër faktorësh, duke përfshirë:
- Besueshmëria e ruajtjes së të dhënave. Sa më i madh m, aq më i madh është numri i dështimeve të diskut që mund të mbijetojnë, domethënë, aq më i lartë është besueshmëria.
- Magazinim i tepërt. Sa më i lartë të jetë raporti m/n, aq më i lartë do të jetë teprica e ruajtjes dhe aq më i shtrenjtë do të jetë sistemi.
- Koha e përpunimit të kërkesës. Sa më e madhe të jetë shuma n + m, aq më e gjatë do të jetë koha e përgjigjes ndaj kërkesave. Meqenëse leximi i të dhënave (gjatë rikuperimit) kërkon leximin e n blloqeve të ruajtura në n disqe të ndryshëm, koha e leximit do të përcaktohet nga disku më i ngadalshëm.
Përveç kësaj, ruajtja e të dhënave në disa DC imponon kufizime shtesë në zgjedhjen e n dhe m: nëse 1 DC është i fikur, të dhënat duhet të jenë ende të disponueshme për lexim. Për shembull, kur ruani të dhënat në 3 DC, duhet të plotësohet kushti i mëposhtëm: m >= n/2, përndryshe mund të ketë një situatë ku të dhënat nuk janë të disponueshme për lexim kur 1 DC është i fikur.
3. LRC - Kodet Lokale të Rindërtimit
Për të rikuperuar të dhënat duke përdorur kodet Reed-Solomon, duhet të përdorni n blloqe arbitrare të të dhënave. Ky është një disavantazh shumë domethënës për sistemet e ruajtjes së të dhënave të shpërndara, sepse për të rivendosur të dhënat në një disk të thyer, do t'ju duhet të lexoni të dhëna nga shumica e të tjerëve, duke krijuar një ngarkesë të madhe shtesë në disqe dhe në rrjet.
Gabimet më të zakonshme janë paarritshmëria e një blloku të të dhënave për shkak të dështimit ose mbingarkesës së një disku. A është e mundur të zvogëlohet disi ngarkesa e tepërt për rikuperimin e të dhënave në këtë rast (më të zakonshëm)? Rezulton se mundeni: ka kode të tepricës LRC posaçërisht për këtë qëllim.
LRC (Kodet e Rindërtimit Lokal) janë kode të tepricës të shpikur nga Microsoft për përdorim në Windows Azure Storage. Ideja e LRC është sa më e thjeshtë që të jetë e mundur: ndani të gjitha blloqet e të dhënave në dy (ose më shumë) grupe dhe lexoni një pjesë të blloqeve të kodit të tepricës për secilin grup veç e veç. Pastaj disa blloqe kodesh të tepricës do të numërohen duke përdorur të gjitha blloqet e të dhënave (në LRC quhen kode të tepricës globale), dhe disa - duke përdorur një nga dy grupet e blloqeve të të dhënave (ato quhen kode lokale të tepricës).
LRC shënohet me tre numra: nrl, ku n është numri i blloqeve të të dhënave, r është numri i blloqeve të kodit të tepricës globale, l është numri i blloqeve lokale të kodit të tepricës. Për të lexuar të dhëna kur një bllok i të dhënave nuk është i disponueshëm, duhet të lexoni vetëm blloqe n/l - kjo është XNUMX herë më pak se në kodet Reed-Solomon.
Për shembull, merrni parasysh skemën LRC 6-2-2. X1–X6 — 6 blloqe të dhënash, P1, P2 — 2 blloqe globale të tepricës, P3, P4 — 2 blloqe lokale të tepricës.
Blloqet e kodit të tepricës P1, P2 numërohen duke përdorur të gjitha blloqet e të dhënave. Blloku i kodit të tepricës P3 - duke përdorur blloqet e të dhënave X1-X3, blloku i kodit të tepricës P4 - duke përdorur blloqet e të dhënave X4-X6.
Pjesa tjetër bëhet në LRC në analogji me kodet Reed-Solomon. Ekuacionet për numërimin e fjalëve të blloqeve të kodit të tepricës do të jenë:
Për të zgjedhur numrat alfa, beta, gama, delta, duhet të plotësohen një sërë kushtesh për të garantuar mundësinë e rikuperimit të të dhënave (d.m.th., zgjidhjen e sistemit të ekuacioneve). Ju mund të lexoni më shumë rreth tyre në .
Gjithashtu në praktikë, operacioni XOR përdoret për të llogaritur kodet lokale të tepricës P3, P4.
Një numër përfundimesh rrjedhin nga sistemi i ekuacioneve për LRC:
- Për të rikuperuar çdo 1 bllok të dhënash, mjafton të lexoni blloqe n/l (n/2 në shembullin tonë).
- Nëse blloqet r + l nuk janë të disponueshme dhe të gjitha blloqet përfshihen në një grup, atëherë të dhënat nuk mund të rikthehen. Kjo është e lehtë të shpjegohet me një shembull. Le të mos jenë të disponueshëm blloqet X1–X3 dhe P3: këto janë blloqe r + l nga i njëjti grup, 4 në rastin tonë. Atëherë kemi një sistem prej 3 ekuacionesh me 4 të panjohura që nuk mund të zgjidhen.
- Në të gjitha rastet e tjera të padisponueshmërisë së blloqeve r + l (kur të paktën një bllok është i disponueshëm nga secili grup), të dhënat në LRC mund të rikthehen.
Kështu, LRC tejkalon kodet Reed-Solomon në rikuperimin e të dhënave pas gabimeve të vetme. Në kodet Reed-Solomon, për të rikuperuar qoftë edhe një bllok të dhënash, duhet të përdorni n blloqe, dhe në LRC, për të rikuperuar një bllok të dhënash, mjafton të përdorni blloqe n/l (n/2 në shembullin tonë). Nga ana tjetër, LRC është inferior ndaj kodeve Reed-Solomon për sa i përket numrit maksimal të gabimeve të lejueshme. Në shembujt e mësipërm, kodet Reed-Solomon mund të rikuperojnë të dhëna për çdo 4 gabime, dhe për LRC ka 2 kombinime të 4 gabimeve kur të dhënat nuk mund të rikuperohen.
Ajo që është më e rëndësishme varet nga situata specifike, por shpesh kursimet në ngarkesë të tepërt që ofron LRC tejkalojnë ruajtjen pak më pak të besueshme.
4. Kode të tjera të tepricës
Përveç kodeve Reed-Solomon dhe LRC, ka shumë kode të tjera të tepricës. Kode të ndryshme të tepricës përdorin matematikë të ndryshme. Këtu janë disa kode të tjera të tepricës:
- Kodi i tepricës duke përdorur operatorin XOR. Operacioni XOR kryhet në n blloqe të dhënash dhe fitohet 1 bllok kodesh tepricë, domethënë një skemë n+1 (n blloqe të dhënash, 1 kod tepricë). Përdorur në , ku blloqet e të dhënave dhe kodet e tepricës shkruhen në mënyrë ciklike në të gjithë disqet e grupit.
- Algoritmi çift-tek i bazuar në operacionin XOR. Ju lejon të ndërtoni 2 blloqe kodesh të tepricës, domethënë skemën n+2.
- Algoritmi STAR i bazuar në operacionin XOR. Ju lejon të ndërtoni 3 blloqe kodesh të tepricës, domethënë skemën n+3.
- Kodet piramidale janë një tjetër kod tepricë nga Microsoft.
5. Përdorni në Yandex
Një numër i projekteve të infrastrukturës Yandex përdorin kode të tepërta për ruajtjen e besueshme të të dhënave. Ketu jane disa shembuj:
- Ruajtja e brendshme e objektit MDS, për të cilën kam shkruar në fillim të artikullit.
- - Sistemi MapReduce i Yandex.
- (Yandex DataBase) - baza e të dhënave e shpërndarë newSQL.
MDS përdor kodet e tepricës LRC, skema 8-2-2. Të dhënat me kode të tepërta shkruhen në 12 disqe të ndryshëm në serverë të ndryshëm në 3 DC të ndryshme: 4 serverë në çdo DC. Lexoni më shumë rreth kësaj në .
YT përdor të dy kodet Reed-Solomon (Skema 6-3), të cilat ishin të parat që zbatuan, dhe kodet e tepricës LRC (Skema 12-2-2), me LRC që është metoda e preferuar e ruajtjes.
YDB përdor kodet e tepricës me bazë çift-tek (Figura 4-2). Rreth kodeve të tepricës në YDB tashmë .
Përdorimi i skemave të ndryshme të kodit të tepricës është për shkak të kërkesave të ndryshme për sistemet. Për shembull, në MDS, të dhënat e ruajtura duke përdorur LRC vendosen në 3 DC menjëherë. Është e rëndësishme për ne që të dhënat të mbeten të disponueshme për lexim nëse 1 nga çdo DC dështon, prandaj blloqet duhet të shpërndahen nëpër DC në mënyrë që nëse ndonjë DC nuk është i disponueshëm, numri i blloqeve të paarritshme nuk është më shumë se i lejueshëm. Në skemën 8-2-2, mund të vendosni 4 blloqe në çdo DC, atëherë kur çdo DC është i fikur, 4 blloqe nuk do të jenë të disponueshme dhe të dhënat mund të lexohen. Çfarëdo skeme që zgjedhim kur e vendosim në 3 DC, në çdo rast duhet të jetë (r + l) / n >= 0,5, domethënë teprica e ruajtjes do të jetë së paku 50%.
Në YT situata është e ndryshme: çdo grup YT ndodhet tërësisht në 1 DC (grupe të ndryshme në DC të ndryshme), kështu që nuk ka një kufizim të tillë. Skema 12-2-2 siguron 33% tepricë, domethënë ruajtja e të dhënave është më e lirë dhe gjithashtu mund të mbijetojë deri në 4 ndërprerje të njëkohshme të diskut, ashtu si skema MDS.
Ka shumë më tepër veçori të përdorimit të kodeve të tepricës në sistemet e ruajtjes dhe përpunimit të të dhënave: nuancat e rikuperimit të të dhënave, ndikimi i rikuperimit në kohën e ekzekutimit të pyetjes, veçoritë e regjistrimit të të dhënave, etj. Unë do të flas veçmas për këto dhe veçori të tjera të përdorimit të kodeve të tepricës në praktikë, nëse tema do të jetë interesante.
6. Lidhjet
- Një seri artikujsh rreth kodeve Reed-Solomon dhe fushave Galois:
Ata i hedhin një vështrim më të thellë matematikës në një gjuhë të arritshme. - Artikull nga Microsoft për LRC:
Seksioni 2 shpjegon shkurtimisht teorinë dhe më pas diskuton përvojat me LRC në praktikë. - Skema çift-tek:
- Skema STAR:
- Kodet piramidale:
- Kodet e tepricës në MDS:
- Kodet e tepricës në YT:
- Kodet e tepricës në YDB:
Burimi: www.habr.com