Kjo është mënyra e tepërt
Kodat e tepërt* 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 kodave të tepërt në vend të riprodhimit në magazinën tonë të brendshme të objekteve kursen miliona pa ulur besueshmërinë. Por, megjithë përhapjen e gjerë, një përshkrim i qartë i mënyrës se si funksionojnë kodet e tepërt, është shumë i rrallë. Ata që duan të kuptojnë përballen afërsisht me këtë (nga ):
Emri im është Vadim, në Yandex merrem me zhvillimin e magazinës së brendshme të objekteve MDS. Në këtë artikull, do të përshkruaj në mënyrë të thjeshtë bazat teorike të kodeve të tepërt (kodeve Reed-Solomon dhe LRC). Do të tregoj se si funksionon, pa matematikë të komplikuar dhe terma të rrallë. Në fund do të jap shembuj të përdorimit të kodeve të tepërt në Yandex.
Disa detaje matematikore nuk do t'i shqyrtoj në detaje, por do t'u jap lidhje për ata që dëshirojnë të thellohen më shumë. Po ashtu, dua të theksoj se disa përkufizime matematikore mund të mos jenë strikte, pasi artikulli nuk është për matematikantët, por për inxhinierët që duan të kuptojnë thelbin e çështjes.
* Në literaturën anglishtfolëse, kodet e mbivlerësisë shpesh quhen kodet e fshirjes.
1. Thelbi i kodeve të mbivlerësisë
Thelbi i të gjithë kodeve të mbivlerësisë është shumë i thjeshtë: të ruhet (ose të transmetohet) të dhëna në mënyrë që ato të mos humbasin kur ndodhin gabime (prishje disku, gabime në transmetimin e të dhënave, etj.).
Në shumicën* e kodeve të mbivlerësisë, të dhënat ndahen në n blloqe të dhënash, për to llogariten m blloqe kode mbivlerësie, kështu që gjithsej kemi n + m blloqe. Kodet e mbivlerësisë ndërtohen në mënyrë që të jetë e mundur të rikuperohen n blloqe të dhënash, duke përdorur vetëm një pjesë të n + m blloqeve. Më poshtë do të shqyrtojmë vetëm kodet bllok të mbivlerësisë, dmth ato ku të dhënat ndahen në blloqe.
PĂ«r tĂ« rikuperuar tĂ« gjitha n blloqet e tĂ« dhĂ«nave, nevojitet tĂ« paktĂ«n n nga n + m blloqet, pasi nuk Ă«shtĂ« e mundur tĂ« merrni n blloqe duke pasur vetĂ«m n-1 bllok (nĂ« kĂ«tĂ« rast do tĂ« duhej tĂ« merrni 1 bllok «nga ajri»). A janĂ« tĂ« mjaftueshme n blloqet arbitrare nga n + m pĂ«r rikuperimin e tĂ« gjithĂ« tĂ« dhĂ«nave? Kjo varet nga lloji i kodĂ«ve tĂ« tepĂ«rt, pĂ«r shembull, kodet Reed-Solomon lejojnĂ« rikuperimin e tĂ« gjitha tĂ« dhĂ«nave me ndihmĂ«n e n blloqeve arbitrare, ndĂ«rsa kodet e tepĂ«rt LRC â jo gjithmonĂ«.
Ruajtja e të dhënave
Në sistemet e ruajtjes së të dhënave, zakonisht, çdo bllok të dhënash dhe bllok kodesh të tepërt shkruhet në një disk të veçantë. Atëherë, në rast të një dëmtimi të një disku, të dhënat origjinale mund të rikuperohen dhe të lexohen. Të dhënat mund të rikuperohen edhe nëse disa disqe dëmtohen në të njëjtën kohë.
Transferta e të dhënave
Kode e mbipeshës mund të përdoren për transmetimin e besueshëm të të dhënave në një rrjet të pasigurt. Të dhënat e transmetuara ndahen në blloqe, për të cilat llogariten kodet e mbipeshës. Blloqet e të dhënave dhe blloqet e kodit të mbipeshës dërgohen përmes rrjetit. Në rast se ndodhin gabime në blloqe të rastit (madje deri në një numër të caktuar blloqesh), të dhënat prapë mund të dërgohen pa gabime përmes rrjetit. Kodet e Reed-Solomon, për shembull, përdoren për transmetimin e të dhënave përmes linjave optike të komunikimit dhe në komunikimin satelitor.
* Ekzistojnë gjithashtu kode mbipeshash, ku të dhënat nuk ndahen në blloqe, siç janë kodet Hamming dhe kodet CRC, të cilat aplikohen gjerësisht për transmetimin e të dhënave në rrjetet Ethernet. Këto janë kode për kodimin rezistent ndaj ndërhyrjeve, janë destinuar për zbuloj gabimesh 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ë disa nga kodet e mbipeshës më të shpeshta, të shpikura që në vitet 1960 dhe që për herë të parë gjetën përdorim të gjerë në vitet 1980 për prodhiminNë masë të diskëve kompakt.
Dy pyetje kyçe për të kuptuar kodet e Reid-Solomon janë dy: 1) si të krijoni blloqe kodesh tepër; 2) si të rikuperoni të dhëna duke përdorur blloqet e kodesh tepër. Do të gjejmë përgjigjet për to.
Për thjeshtësim, më tej do të supozojmë se n=6 dhe m=4. Schemat e tjera shqyrtohen në përputhje.
Si të krijoni blloqe kodesh tepër
Ădo bllok kodesh tepĂ«r konsiderohet pavarĂ«sisht nga tĂ« tjerĂ«t. PĂ«r llogaritjen e çdo blloku pĂ«rdoren tĂ« gjithĂ« n blloket e tĂ« dhĂ«nave. NĂ« diagramin mĂ« poshtĂ«, X1-X6 janĂ« blloket e tĂ« dhĂ«nave, P1âP4 janĂ« blloket e kodesh tepĂ«r.
Të gjithë blloket e të dhënave duhet të kenë të njëjtin madhësi, për rregullimin mund të përdoren bitet zero. Blloket e kodesh tepër të obtenuara do të kenë të njëjtin madhësi si blloket e të dhënave. Të gjithë blloket e të dhënave ndahen në fjalë (p.sh., nga 16 bit). Le të supozojmë se kemi ndarë blloket e të dhënave në k fjalë. Atëherë të gjithë blloket e kodesh tepër gjithashtu do të shpërndahen në k fjalë.
Për llogaritjen e fjalës i të çdo blloku tepër do të përdoren fjalët e i-ta të të gjithë blloket e të dhënave. Ato do të llogariten sipas formulës më poshtë:
Këtu, vlerat x janë fjalët e bllokut të të dhënave, p janë fjalët e bllokut të kodit të tepërt, të gjithë alfa, beta, gamma dhe delta janë numra të zgjedhur veçanërisht, 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 së Galois, operacionet +, -, *, / janë operacione speciale, të futur mbi elementët e fushës së Galois.
PĂ«rse nevojiten fushat e Galois
Duket se Ă«shtĂ« e thjeshtĂ«: ndajmĂ« tĂ« dhĂ«nat nĂ« blloqe, blloqet nĂ« fjalĂ«, me ndihmĂ«n e fjalĂ«ve tĂ« bllokut tĂ« tĂ« dhĂ«nave llogarisim fjalĂ«t e bllokut tĂ« kodit tĂ« tepĂ«rt â marrim blloqe kodesh tĂ« tepĂ«rta. NĂ« pĂ«rgjithĂ«si, kĂ«shtu funksionon, por djalli Ă«shtĂ« nĂ« detaje:
- Siç u tha më sipër, madhësia e fjalës është fikse, në shembullin tonë, 16 bit. Formulat e mësipërme për kodet e Reed-Solomon janë të tilla që përdorimi i numrave të zakonshëm të plotë, rezultati i llogaritjes p mund të mos paraqitet me një fjalë të madhësisë së pranueshme.
- Gjatë rikuperimit të të dhënave, 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ë lindë nevoja për të kryer ndarje të numrave të plotë ndaj njëri-tjetrit, rezultat i të cilit do të jetë një numër real që nuk mund të paraqitet saktësisht në memorien e kompjuterit.
Këto probleme nuk lejojnë përdorimin e numrave të plotë për kodet e Reid-Solomonit. Zgjidhja e problemit është origjinale dhe mund të përshkruhet si më poshtë: le të shpikim numra specialë, të cilët mund të përfaqësohen me fjalë të gjatë të nevojshme (p.sh., 16 bit), dhe rezultati i ekzekutimit të të gjitha operacioneve mbi ta (shtimi, zbritja, shumëzimi, ndarja) gjithashtu do të përfaqësohet në memorien e kompjuterit me fjalë të gjatë të nevojshme.
Këto numra "specialë" janë studiuar prej kohësh nga matematika dhe quhen fusha. Një fushë është një sasi elementesh me operacione të caktuara për ta, si shtimi, zbritja, shumëzimi dhe ndarja.
Fushat Galois* janë fushat për të cilat ekziston një dhe vetëm një rezultat për secilën operacion (+, -, *, /) për çdo dy elemente të fushës. Fushat Galois mund të ndërtohen për numra që janë fuqi të 2: 2, 4, 8, 16 etj. (në të vërtetë fuqi e çdo numri të thjeshtë p, por në praktikë na interesojnë vetëm fuqitë e 2). Për shembull, për fjalë me madhësi 16 bit, kjo fushë përmban 65,536 elemente, për çdo çift, ku mund të gjenden rezultatet e çdo operacioni (+, -, *, /). Vlerat x, p, alfa, beta, gama, delta nga ekuacionet e mësipërme për llogaritjet do të konsiderohen si elemente të fushës Galois.
kështu, ne kemi një sistem ekuacionesh, përmes të cilave mund të ndërtojmë blloqe kodi të tepërt, duke shkruar një program kompjuterik të përshtatshëm. Me këtë sistem ekuacionesh mund të kryhet gjithashtu rinovimi i të dhënave.
* Kjo nuk është një përkufizim i saktë, më shumë një përshkrim.
Si të rikuperoni të dhënat
Rivitalizimi është i nevojshëm kur nga n + m blloqe, disa blloqe mungojnë. Këto mund të jenë si blloqe të dhënash ashtu dhe blloqe të kodit të tepërt. Mungesa e blloqeve të dhënash dhe/ose e blloqeve të kodit të tepërt do të thotë se në ekuacionet e mësipërme, variablat përkatës x dhe/ose p janë të panjohura.
Ekuacionet për kodet Reed-Solomon mund të trajtohen si një sistem ekuacionesh, ku të gjitha vlerat alfa, beta, gamma, delta - janë konstanta, të gjitha x dhe p, përkatëse blloqeve të disponueshëm, - janë variabla të njohur, ndërsa x dhe p të tjerat - janë të panjohur.
Për shembull, le të supozojmë se blloqet e të dhënave 1, 2, 3 dhe blloku i kodit të tepërt 2 nuk janë të disponueshme, atëherë për grupin e fjalëve i do të kemi sistemin e mëposhtëm të ekuacioneve (të panjohurat shënohen me të kuqe):
Ne kemi një sistem prej 4 ekuacionesh me 4 të panjohura, kështu që mund ta zgjidhim atë dhe të rivitalizojmë të dhënat!
Nga ky sistem ekuacionesh, rrjedhin disa përfundime në lidhje me rivitalizimin e të dhënave për kodet Reed-Solomon (n blloqe të dhënash, m blloqe të kodit të tepërt):
- Të dhënat mund të rikuperohen në rastin e humbjes së çdo m blokesh ose më pak. Në rastin e humbjes së m+1 dhe më shumë blokesh, të dhënat nuk mund të rikuperohen: nuk është e mundur të zgjidhet një sistem me m ekuacione me m + 1 të panjohura.
- Për të rikuperuar edhe një block të dhënash, nevojitet të përdoren ndonjë n nga bloket e mbetura, për këtë qëllim është e mundur të përdoren të gjitha kodet e tepërt.
ĂfarĂ« tjetĂ«r duhet tĂ« dish
Në përshkrimin e mësipërm kaloj përparësisht shumë çështje të rëndësishme, për shqyrtimin e të cilave duhen përqendruar më thellë në matematikë. Në veçanti, nuk thashë asgjë për të following:
- Sistemi i ekuacioneve për kodet e Reed-Solomon duhet të ketë (zgjidhje unike) për çdo kombinim të njohurave (jo më shumë se m të panjohura). Nga ky kërkesë përcaktohen vlerat e alfa, beta, gamma dhe delta.
- Duhet të dish të ndërtohet automatikisht sistemi i ekuacioneve (në varësi të bllokimeve të caktuara) dhe ta zgjidhësh atë.
- Duhet të ndërtohet një fushë Galois: për një madhësi të caktuar duhet të jesh në gjendje të gjesh rezultatin e çdo operacioni (+, -, *, /) për çdo dy elemente.
Në fund të artikullit janë lidhje me literaturën për këto çështje të rëndësishme.
Zgjedhja e n dhe m
Si praktikisht të zgjidhni n dhe m? Në praktikë, në sistemet e ruajtjes së të dhënave, kode të tepricës përdoren për të kursyer hapësirë, prandaj m gjithmonë zgjidhet më i vogël se n. Vlerat e tyre konkrete varen nga një mori faktorësh, përfshirë:
- Besueshmëria e ruajtjes së të dhënave. Sa më shumë të jetë m, aq më shumë dështime disku mund të mbijetojnë, domethënë më e lartë besueshmëria.
- Teprica e ruajtjes. Sa më e lartë të jetë raporti m/n, aq më e lartë do të jetë teprica e ruajtjes dhe aq më shtrenjtë do të kushtojë sistemi.
- Koha e përpunimit të kërkesave. Sa më e madhe të jetë shuma n + m, aq më gjatë do të jetë koha e përgjigjes për kërkesat. Pasi për të lexuar të dhënat (gjatë rikuperimit) nevojitet të lexohen n blloqe që ruhen në n disqe të ndryshme, koha e leximit do të përcaktohet nga disku më të ngadalshëm.
Përveç kësaj, ruajtja e të dhënave në disa DCs vendos kufizime të tjera në zgjedhjen e n dhe m: në rastin e çaktivizimit të 1 DC, të dhënat duhet ende të jenë të lexueshme. Për shembull, kur të dhënat ruhen në 3 DCs, duhet të përmbushet kushti: m >= n/2, përndryshe mund të ndodhë një situatë kur të dhënat nuk janë të lexueshme në rastin e çaktivizimit të 1 DC.
3. LRC â Kodi i Rikonstruksionit Lokal
Për të rikuperuar të dhënat me kodet Reed-Solomon, është e nevojshme të përdoren n blloqe të rastit të të dhënave. Kjo është një disavantazh shumë i rëndësishëm për sistemet e shpërndara të ruajtjes së të dhënave, sepse për të rikuperuar të dhënat nga një hard disk të prishur, duhet të lexoni të dhënat nga shumicë e të tjerëve, duke krijuar një ngarkesë të madhe shtesë në hard disk dhe rrjet.
Gabimet më të zakonshme janë pamundësia për të aksesuar një bllok të dhënash për shkak të prishjes ose ngarkesës së tepruar të një disku. A është e mundur të zvogëloni ngarkesën e tepruar për rikuperimin e të dhënave në një rast të tillë (më të zakonshmet)? Duket se është e mundur: për këtë arsye ekzistojnë kodet e të dhënave LRC.
LRC (Kodet e Rikonstruksionit Lokal) â kode shtesĂ« tĂ« krijuara nga Microsoft pĂ«r t'u aplikuar nĂ« Windows Azure Storage. Ideja e LRC Ă«shtĂ« shumĂ« e thjeshtĂ«: tĂ« ndahen tĂ« gjitha blloqet e tĂ« dhĂ«nave nĂ« dy (ose mĂ« shumĂ«) grupe dhe tĂ« llogariten disa blloqe kode shtesĂ« pĂ«r secilĂ«n grup nĂ« mĂ«nyrĂ« tĂ« veçantĂ«. KĂ«shtu, disa blloqe kode shtesĂ« do tĂ« llogariten duke pĂ«rdorur tĂ« gjitha blloqet e tĂ« dhĂ«nave (nĂ« LRC ato quhen kode globale tĂ« rikonstruksionit), ndĂ«rsa disa â duke pĂ«rdorur njĂ«rin nga dy grupet e blloqeve tĂ« tĂ« dhĂ«nave (ato quhen kode lokale tĂ« rikonstruksionit).
LRC pĂ«rshkruhet me tre numra: n-r-l, ku n Ă«shtĂ« numri i blloqeve tĂ« tĂ« dhĂ«nave, r Ă«shtĂ« numri i blloqeve globale tĂ« kodeve tĂ« rikonstruksionit, l Ă«shtĂ« numri i blloqeve lokale tĂ« kodeve tĂ« rikonstruksionit. PĂ«r tĂ« lexuar tĂ« dhĂ«nat kur njĂ« bllok i tĂ« dhĂ«nave nuk Ă«shtĂ« i disponueshĂ«m, Ă«shtĂ« e nevojshme tĂ« lexoni vetĂ«m n/l blloqe â kjo Ă«shtĂ« l herĂ« mĂ« pak se sa nĂ« kodet e Reed-Solomon.
Si njĂ« shembull, le tĂ« shqyrtojmĂ« skemĂ«n LRC 6-2-2. X1âX6 janĂ« 6 blloqe tĂ« tĂ« dhĂ«nave, P1, P2 janĂ« 2 blloqe globale tĂ« rikonstruksionit, P3, P4 janĂ« 2 blloqe lokale tĂ« rikonstruksionit.
Blloket e kodit tĂ« tepĂ«rt P1, P2 llogariten me tĂ« gjitha blloqet e tĂ« dhĂ«nave. Blloku i kodit tĂ« tepĂ«rt P3 â me blloqet e tĂ« dhĂ«nave X1âX3, blloku i kodit tĂ« tepĂ«rt P4 â me blloqet e tĂ« dhĂ«nave X4âX6.
E gjitha ndodh në LRC, në përputhje me kodet e Reed-Solomon. Barazimet për llogaritjen e fjalëve të bllokut të kodit të tepërt do të jenë si më poshtë:
Për të përcaktuar numrat alfa, beta, gamma, delta duhen zbatuar një sërë kushtesh që garantojnë mundësinë e rikuperimit të të dhënave (domethënë zgjidhjen e sistemit të barazimeve). Më shumë rreth tyre mund të lexoni në .
Gjithashtu, në praktikë për llogaritjen e kodit lokal të tepërt P3, P4 përdoret operacioni XOR.
Nga sistemi i barazimeve për LRC ndahen disa përfundime:
- Për të rikuperuar çdo 1 bllok të dhënash, mjafton të lexoni n/l blloqe (n/2 në shembullin tonë).
- NĂ«se nuk janĂ« tĂ« disponueshme r + l blloqe, dhe tĂ« gjitha blloqet pĂ«rfshihen nĂ« njĂ« grup, atĂ«herĂ« tĂ« dhĂ«nat nuk mund tĂ« rikuperohen. Kjo Ă«shtĂ« e lehtĂ« pĂ«r t'u shpjeguar me njĂ« shembull. Le tĂ« themi se blloqet X1âX3 dhe P3 nuk janĂ« tĂ« disponueshme: kĂ«to janĂ« r + l blloqe nga njĂ« grup, 4 nĂ« rastin tonĂ«. KĂ«shtu kemi njĂ« sistem me 3 barazime dhe 4 tĂ« panjohura, tĂ« cilin nuk mund ta zgjidhim.
- Në të gjitha rastet e tjera të pamundësisë së blloqeve r + l (kur nga çdo grup është i disponueshëm të paktën një bllok), informacioni në LRC mund të rikuperohet.
Kështu, LRC kalon kodet e Reed-Solomon në rikuperimin e të dhënave pas gabimeve të vetme. Në kodet e Reed-Solomon, për të rikuperuar edhe një bllok të dhënash, duhet të përdoren n blloqe, ndërsa në LRC për rikuperimin e një blloku të dhënash, mjafton të përdoren n/l blloqe (n/2 në shembullin tonë). Nga ana tjetër, LRC dështon përballë kodit të Reed-Solomon në numrin maksimal të gabimeve të lejueshme. Në shembujt e mësipërm, kodet e Reed-Solomon mund të rikuperojnë të dhënat në çdo rast me 4 gabime, ndërsa për LRC ekzistojnë 2 kombinime nga 4 gabime, kur të dhënat nuk mund të rikuperohen.
ĂfarĂ« Ă«shtĂ« mĂ« e rĂ«ndĂ«sishme - varet nga situata e veçantĂ«, por shpesh herĂ«, kursimi i ngarkesĂ«s sĂ« tepĂ«rt qĂ« ofron LRC peshon mĂ« shumĂ« se qĂ«ndrueshmĂ«ria pak mĂ« e ulĂ«t e ruajtjes.
4. Kodet e tjera të tepërt
Përveç kodeve të Reed-Solomon dhe LRC, ka shumë kode të tjera të tepërt. Kode të ndryshme të tepërt përdorin matematikë të ndryshme. Ja disa kode të tjera të tepërt:
- Kodi i tepërt me operatorin XOR. Operacioni XOR kryhet mbi n blloqe të dhënash, duke rezultuar në 1 bllok kodesh të tepërt, pra skema n+1 (n blloqe të dhënash, 1 kod i tepërt). Përdoret në , ku blloqet e të dhënave dhe kodet e tepërt regjistrohen ciklikisht në të gjitha diskët e grupit.
- Algoritmi even-odd, i bazuar në operacionin XOR. Lejon ndërtimin e 2 bllokëve të kodit të tepërt, pra skema n+2.
- Algoritmi STAR, i bazuar në operacionin XOR. Lejon ndërtimin e 3 bllokëve të kodit të tepërt, pra skema n+3.
- Pyramid kodi â disa kode tĂ« tjera tĂ« tepĂ«rt nga Microsoft.
5. Përdorimi në Yandex
Një sërë projektesh infrastrukturore të Yandex përdorin kode të tepërt për ruajtjen e besueshme të të dhënave. Ja disa shembuj:
- Depozita e brendshme objektesh MDS, për të cilën kam shkruar në fillim të artikullit.
- â Sistemi MapReduce i Yandex.
- (Yandex DataBase) â baza e tĂ« dhĂ«nave tĂ« shpĂ«rndara newSQL.
Në MDS përdoren kodet e tepërt LRC, skema 8-2-2. Të dhënat me kodet e tepërt shkruhen në 12 disqe të ndryshme në serverë të ndryshëm në 3 DC të ndryshme: 4 serverë në çdo DC. Më shumë rreth kësaj lexoni në .
Në YT përdoren si kodet e Ridhit - Solomon (schema 6-3), të cilat janë zbatuar të parat, ashtu si dhe kodet e tepricës LRC (schema 12-2-2), ku LRC është mënyra e preferuar e ruajtjes.
Në YDB përdoren kodet e tepricës, të bazuara në even-odd (schema 4-2). Për kodet e tepricës në YDB tashmë .
PĂ«rdorimi i skemave tĂ« ndryshme tĂ« kodit tĂ« tepricĂ«s Ă«shtĂ« i kushtĂ«zuar nga kĂ«rkesat e ndryshme qĂ« i bĂ«hen sistemeve. PĂ«r shembull, nĂ« MDS, tĂ« dhĂ«nat e ruajtura me LRC janĂ« vendosur menjĂ«herĂ« nĂ« 3 DC. ĂshtĂ« e rĂ«ndĂ«sishme pĂ«r ne qĂ« tĂ« dhĂ«nat tĂ« mbeten tĂ« qasshme pĂ«r t'u lexuar kur dĂ«shtojnĂ« 1 nga çdo DC, kĂ«shtu qĂ« blloqet duhet tĂ« shpĂ«rndahen nĂ« DC nĂ« mĂ«nyrĂ« qĂ« kur njĂ« DC tĂ« jetĂ« i paqasshĂ«m, numri i blloqeve tĂ« paqasshĂ«m tĂ« mos jetĂ« mĂ« i madh se sa i lejuar. NĂ« skemĂ«n 8-2-2 mund tĂ« vendosen 4 blloqe nĂ« çdo DC, kĂ«shtu qĂ« kur çaktivizohet çdo DC do tĂ« jenĂ« tĂ« paqasshĂ«m 4 blloqe, dhe tĂ« dhĂ«nat do tĂ« mund tĂ« lexohen. Ădo skemĂ« qĂ« zgjidhim pĂ«r shpĂ«rndarjen nĂ« 3 DC, duhet tĂ« ketĂ« (r + l) / n >= 0,5, domethĂ«nĂ« teprica e ruajtjes do tĂ« jetĂ« sĂ« paku 50%.
Në YT situata është ndryshe: çdo klaster YT ndodhet plotësisht në 1 Qendër të Dëgjimit (qendra të ndryshme në Qendra të ndryshme), prandaj nuk ka një kufizim të tillë. Schematika 12-2-2 ofron një tepricë prej 33%, që do të thotë se ruajtja e të dhënave bëhet më e përballueshme, ndërkohë që ato gjithashtu mund të përballojnë deri në 4 është dhe largime të diskëve, ashtu si skema në MDS.
Ekzistojnë gjithashtu shumë veçori të tjera në përdorimin e kodave të tepricës në sistemet e ruajtjes dhe përpunimit të të dhënave: nuanca të rikuperimit të të dhënave, ndikimi i rikuperimit në kohën e realizimit të kërkesave, veçoritë e shkruarjes së të dhënave dhe të tjera. Kam për të treguar veçmas për këto dhe veçori të tjera të aplikimit të kodave të tepricës në praktikë, nëse tema do të jetë interesante.
6. Lidhjet
- Seria e artikujve mbi kodet e Ridhit â Solomon dhe fushat e Galois:
Në to shqiptohet matematikisht më thellësisht në një gjuhë të këndshme. - Artikulli nga Microsoft mbi LRC:
Në seksionin 2 shpjegohet shkurtimisht teoria, pastaj shqyrtohet përvoja e aplikimit të LRC në praktikë. - Skema even-odd:
- Skema STAR:
- Kodet Piramida:
- Kodet e tepricës në MDS:
- Kodet e tepricës në YT:
- Kodet e tepricës në YDB:
Burimi: habr.com
