Kështu duket redundantësia
Kodet e redundantësisë* 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 kodet e redundantësisë në vend të replikimit në magazinën tonë të brendshme të objekteve kursen miliona pa ulur besueshmërinë. Por, pavarësisht përhapjes së gjerë, përshkrimi i qartë i mënyrës se si funksionojnë kodet e redundantësisë është shumë i rrallë. Ata që duan të kuptojnë përballen me diçka të tillë (nga ):
Emri im është Vadim, në Yandex merrem me zhvillimin e magazinës së brendshme të objekteve MDS. Në këtë artikull, do ta përshkruaj me fjalë të thjeshta teorinë e kodet e redundantësisë (kodet e Reed-Solomon dhe LRC). Do të flas për mënyrën se si funksionon, pa matematikë të komplikuar dhe terminologji të rrallë. Në fund do të jap shembuj të përdorimit të kodet e redundantësisë në Yandex.
Nuk do t'i shqyrtoj në detaje disa aspekte matematikore, por do të ofroj lidhje për ata që duan të thellohen më shumë. Gjithashtu do të vë në dukje se disa përkufizime matematikore mund të mos jenë të rrepta, pasi artikulli është i destinuar për inxhinierë që duan të kuptojnë thelbin e çështjes.
* Në literaturën anglisht folëse, kodet e redundantësisë shpesh quhen erasure codes.
1. Thelbi i kodet e redundantësisë
Thelbi i të gjithë kodet e redundantësisë është mjaft i thjeshtë: të ruash (apo të transmetosh) të dhëna në mënyrë që ato të mos humbasin në rast të gabimeve (thyerjeve të disqeve, gabimeve në transmetimin e të dhënave etj.).
Në shumicën* e kodet e redundantësisë, të dhënat ndahen në n blloqe të dhënash, për to llogariten m blloqe kodesh redundantësie, gjithsej ndodhin n + m blloqe. Kodet e redundantësisë ndërtohen në mënyrë që të jetë e mundur rikuperimi i n blloqeve të dhënash duke përdorur vetëm një pjesë nga n + m blloqet. Më poshtë do të shqyrtojmë vetëm kodet e bllokut të redundantësisë, domethënë ato në të cilat të dhënat ndahen në blloqe.
Për të rikuperuar të gjithë n blloqet e të dhënave, nevojitet të paktën n nga n + m blloqet, pasi nuk mund të marrësh n blloqe duke pasur vetëm n-1 bllok (në këtë rast do të duhej të merrnim 1 bllok 'nga ajri'). A janë të mjaftueshëm n blloqe të rastësishme nga n + m blloqet për rikuperimin e të dhënave të gjitha? Kjo varet nga lloji i kodit të tepricës, për shembull, kodet e Reed-Solomon lejojnë rikuperimin e të dhënave me n blloqe të rastësishme, ndërsa kodet e tepricës LRC - jo gjithmonë.
Ruajtja e të dhënave
Në sistemet e ruajtjes së të dhënave, zakonisht secili nga blloqet e të dhënave dhe blloqet e kodit të tepricës shkruhen në një disk të veçantë. Atëherë, në rastin e dështimit të ndonjë disku, të dhënat fillestare mund të rivendosen dhe të lexohen ende. Të dhënat mund të rivendosen edhe kur disa disqe dështojnë njëkohësisht.
Transmetimi i të dhënave
Kodat e tepricë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 tepricës. Të dhënat dhe blloqet e kodet e tepricës transmetohen përmes rrjetit. Në rast të gabimeve në blloqe të rastësishme (deri në një numër të caktuar blloqesh), të dhënat ende mund të transmetohen 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 dhe në komunikimin satelitor.
* Ka gjithashtu kode teprice, në të cilat të dhënat nuk ndahen në blloqe, për shembull, kodet Hamming dhe kodet CRC, të cilat janë gjerësisht të aplikuara për transmetimin e të dhënave në rrjetet Ethernet. Këto janë kode për kodimin e qëndrueshëm ndaj shqetësimeve, të destinuara për zbuluar gabimet, por jo për t'i korigjuar ato (kode Hamming gjithashtu lejon korrigjimin e pjesshëm të gabimeve).
2. Kodat e Reed-Solomon
Kodat e Reed-Solomon janë disa nga kodet e tepricës më të përdorura, të shpikura që në vitet 1960 dhe që filluan të përdoren gjerësisht në vitet 1980 për prodhimin serik të disqeve të kompakt.
Dy pyetje kyçe për të kuptuar kodet e Reed-Solomon janë: 1) si të krijojmë blloqet e kodit të tepricës; 2) si të rikuperojmë të dhënat duke përdorur blloqet e kodit të tepricës. Të gjejmë përgjigjet për to.
Për thjeshtësimin e mëtejshëm, do të supozojmë që n=6 dhe m=4. Skemat e tjera shqyrtohen me analogji.
Si të krijojmë blloqet e kodit të tepricës
Ădo blok kodi tĂ« tepricĂ«s llogaritet nĂ« mĂ«nyrĂ« tĂ« pavarur nga tĂ« tjerĂ«t. PĂ«r tĂ« llogaritur çdo blok pĂ«rdoren tĂ« gjithĂ« n bloket e tĂ« dhĂ«nave. NĂ« diagramin mĂ« poshtĂ«, X1-X6 janĂ« bloket e tĂ« dhĂ«nave, P1âP4 janĂ« bloket e kodeve tĂ« tepricĂ«s.
Të gjitha bloket e të dhënave duhet të kenë të njëjtën madhësi, dhe për rreshtimin mund të përdoren bitër 0. Bloket e marra të kodeve të tepricës do të kenë të njëjtën madhësi si bloket e të dhënave. Të gjitha bloket e të dhënave ndahen në fjalë (p.sh., nga 16 bit). Supozoni se i kemi ndarë bloket e të dhënave në k fjalë. Atëherë të gjitha bloket e kodeve të tepricës gjithashtu do të ndahen në k fjalë.
Për llogaritjen e fjalës i-të të secilit blok të tepricës do të përdoren fjalët i-ta të të gjithë bloket e të dhënave. Ato do të llogariten sipas formulës së mëposhtme:
Këtu vlerat x janë fjalët e bloket e të dhënave, p janë fjalët e bloket e kodeve të tepricës, të gjitha alfa, beta, gamma dhe delta janë numra të veçantë të zgjedhur, të njëjtë për të gjithë i. Menjëherë duhet të thuhet se të gjitha këto vlera nuk janë numra të zakonshëm, por elemente të fushës së Galuas, operacionet +, -, *, / janë jo operacionet e njohura për ne, por operacione speciale të futur mbi elementet e fushës së Galuas.
PĂ«rse nevojiten fushat e Galuas
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ë kodeve të tepricës, kështu marrim blloqet e kodeve të tepricës. Në përgjithësi, kështu funksionon, por djalli është në detaje:
- Siç u tha më sipër, madhësia e fjalës është e fiksuar, në shembullin tonë 16 bit. Formulat e mësipërme për kodet e Reed-Solomon janë të tilla, që duke përdorur numra të zakonshëm të plotë rezultati i llogaritjes p mund të mos paraqitet me një fjalë të pranueshme të madhësisë.
- Në procesin e rikthimit të të dhënave, formulat e mësipërme do të trajtohen si një sistem ekuacionesh që duhet zgjidhur për të rikuperuar të dhënat. Në procesin e zgjidhjes mund të ndodhë që të nevojitet të kryhet ndarja e numrave të plotë nga njëri-tjetri, rezultati i së cilës do të jetë një numër real, i cili 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 ReedâSolomon. Zgjidhja e problemeve Ă«shtĂ« origjinale dhe mund tĂ« pĂ«rshkruhet nĂ« kĂ«tĂ« mĂ«nyrĂ«: le tĂ« shpikim numra tĂ« veçantĂ«, tĂ« cilĂ«t mund tĂ« paraqiten me fjalĂ« tĂ« gjatĂ« (p.sh., 16 bit), dhe rezultati i tĂ« gjitha operacioneve mbi ta (shtimi, zbritja, shumĂ«zimi, ndarja) gjithashtu do tĂ« pĂ«rfaqĂ«sohet nĂ« memorien e kompjuterit me fjalĂ« tĂ« nevojshme gjatĂ«si.
Numrat e tillë "të veçantë" janë studiuar prej një kohë të gjatë nga matematika, dhe ata quhen fushë. Një fushë është një shumësi elementesh me operacione të caktuara për to të shtimit, zbritjes, shumëzimit dhe ndarjes.
Fushat e Galois* janë fusha për të cilat ekziston dhe është unik rezultati i çdo operacioni (+, -, *, /) për çdo dy elemente të fushës. Fushat e Galois mund të ndërtohen për numra që janë fuqia e 2: 2, 4, 8, 16 etj. (në të vërtetë fuqia 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 të cilëve mund të gjendet rezultati i çdo operacioni (+, -, *, /). Vlerat x, p, alpha, beta, gamma, delta nga ekuacionet më lart për llogaritjet do të konsiderohen elemente të fushës Galois.
Kështu, ne kemi një sistem ekuacionesh, me ndihmën e të cilave mund të ndërtojmë blloqe kodesh mbivendësimi, duke shkruar një program kompjuterik përkatës. Me këtë sistem ekuacionesh, gjithashtu mund të kryhet rikuperimi i të dhënave.
* Këto nuk janë një përkufizim strik, përkundrazi një përshkrim.
Si të rikuperoni të dhënat
Rikuperimi është i nevojshëm kur nga blloqet n + m, një pjesë e blloqeve mungon. Këto mund të jenë si blloqe të dhënash ashtu edhe blloqe kodesh mbivendësimi. Mungesa e blloqeve të dhënash dhe/ose blloqeve të kodit mbivendësim do të nënkuptojë se në ekuacionet më lart, variablat përkatëse x dhe/ose p janë të panjohura.
Ekuacionet pĂ«r kodet ReedâSolomon mund tĂ« merren si njĂ« sistem ekuacionesh, ku tĂ« gjitha vlerat alpha, beta, gamma, delta janĂ« konstanta, tĂ« gjitha x dhe p, pĂ«rkatĂ«sisht blloqeve tĂ« disponueshme, janĂ« variabla tĂ« njohur, dhe x dhe p tĂ« tjerĂ«t janĂ« tĂ« panjohur.
Për shembull, le të supozojmë se blloqet e dhënash 1, 2, 3 dhe blloku i kodit mbivendësim 2 nuk janë të aksesueshëm, atëherë për grupin e fjalëve i do të ketë sistemin e mëposhtëm të ekuacioneve (të panjohurat e shënuara me të kuqe):
Ne kemi një sistem me 4 ekuacione dhe 4 të panjohura, pra mund ta zgjidhim dhe të rikuperojmë të dhënat!
Nga ky sistem ekuacionesh ndodhin disa përfundime për rikuperimin e të dhënave për kodet e Reed-Solomon (n blloqe të dhënash, m blloqe të kodit të tepërt):
- Të dhënat mund të rikuperohen me humbjen e çdo m blloqesh ose më pak. Me humbjen e m+1 ose më shumë blloqesh, të dhënat nuk mund të rikuperohen: nuk mund të zgjidhen një sistem me m ekuacione dhe m + 1 të panjohura.
- Për të rikuperuar edhe një bllok të dhënash, është e nevojshme të përdoren çdo n nga blloqet e mbetura, ndërkohë që mund të përdoren çdo nga kodet e tepërt.
ĂfarĂ« tjetĂ«r duhet tĂ« dihet
Në përshkrimin e mësipërm, unë kaloj disa çështje të rëndësishme, për t'i shqyrtuar ato, është e nevojshme të thellohemi më tepër në matematikë. Në veçanti, nuk flas për si vijon:
- Sistemi i ekuacioneve për kodet e Reed-Solomon duhet të ketë (zgjidhjen e vetme) për çdo kombinim të të panjohurave (jo më shumë se m të panjohura). Në bazë të kësaj kërkese, përcaktohen vlerat e alfas, betas, gamas dhe deltas.
- Sistemi i ekuacioneve duhet të dijë si të ndërtohet automatikisht (në varësi të bllokëve që nuk janë të aksesueshëm) dhe si të zgjidhet.
- Duhet të ndërtohet një fushë Galois: për një madhësi të caktuar fjalë, të dihet si të gjejë rezultatin e çdo operacioni (+, -, *, /) për çdo dy elemente.
Në fund të artikullit ka lidhje me literaturën për këto çështje të rëndësishme.
Zgjedhja e n dhe m
Si të zgjidhni praktikisht n dhe m? Në praktikë, në sistemet e ruajtjes së të dhënave, kodet e tepërt përdoren për të kursyer hapësirë, prandaj m zgjidhet gjithmonë më i vogël se n. Vlerat e tyre specifike varen nga disa faktorë, duke përfshirë:
- Besueshmëria e ruajtjes së të dhënave. Sa më e madhe të jetë m, aq më shumë dështime të disqeve mund të përballohen, pra më e lartë është 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ë jetë sistemi.
- Koha e përpunimit të kërkesave. Sa më e madhe të jetë shuma n + m, aq më e gjatë do të jetë koha e përgjigjes për kërkesat. Pasi gjatë leximit të të dhënave (në kohën e rikuperimit) duhet të lexohen n blloqe, të ruajtura në n disqe të ndryshëm, koha e leximit do të përcaktohet nga disku më të ngadalshëm.
Për më tepër, ruajtja e të dhënave në disa Qendra të të Dhënave vendos kufizime të tjera në zgjedhjen e n dhe m: kur ndalon një Qendër të të Dhënave, të dhënat duhet të jenë ende të aksesueshme për lexim. Për shembull, kur ruajmë të dhënat në 3 Qendra të të Dhënave, duhet të përmbushet kushti: m >= n/2, ndryshe mund të ndodhi një situatë kur të dhënat nuk janë të aksesueshme për lexim kur një Qendër e të Dhënave është ndaluar.
3. LRC â Kodet e Rekonstruksionit Vendor
Për të rikuperuar të dhënat me kodet e Reed-Solomon, duhet të përdoren n blloqe të rastësishme 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, pasi për të rikuperuar të dhënat në një disk të prishur do të duhet të lexojmë të dhënat nga shumica e blloqeve të tjera, duke krijuar një ngarkesë të madhe shtesë mbi disqet dhe rrjetin.
Gabimet më të zakonshme janë mungesa e një blloku të dhënash për shkak të dështimit ose mbingarkesës së një disku. A është e mundur të reduktohet ndonjëherë ngarkesa e tepërt për rikuperimin e të dhënave në një rast të tillë (më të zakonshëm)? Duket se është e mundur: për këtë ekzistojnë kodet e tepërt LRC.
LRC (Kodet e Rekonstruksionit Vendor) â janĂ« kode tĂ« tepĂ«rt tĂ« konceptuara nga Microsoft pĂ«r t'u pĂ«rdorur nĂ« Windows Azure Storage. Ideeja e LRC Ă«shtĂ« shumĂ« e thjeshtĂ«: tĂ« ndajmĂ« tĂ« gjithĂ« blloqet e tĂ« dhĂ«nave nĂ« dy (ose mĂ« shumĂ«) grupe dhe tĂ« llogarisim njĂ« pjesĂ« tĂ« blloqeve tĂ« kodit tĂ« tepĂ«rt pĂ«r secilĂ«n grup tĂ« veçantĂ«. KĂ«shtu, njĂ« pjesĂ« e blloqeve tĂ« kodit tĂ« tepĂ«rt do tĂ« llogaritet duke pĂ«rdorur tĂ« gjitha blloqet e tĂ« dhĂ«nave (nĂ« LRC ato quhen kode globale tĂ« tepĂ«rt), dhe njĂ« pjesĂ« â duke pĂ«rdorur njĂ« nga dy grupet e blloqeve tĂ« tĂ« dhĂ«nave (ato quhen kode lokale tĂ« tepĂ«rt).
LRC shprehet me tre numra: n-r-l, ku n Ă«shtĂ« numri i blloqeve tĂ« tĂ« dhĂ«nave, r Ă«shtĂ« numri i blloqeve globale tĂ« kodit tĂ« tepĂ«rt, l Ă«shtĂ« numri i blloqeve lokale tĂ« kodit tĂ« tepĂ«rt. PĂ«r tĂ« lexuar tĂ« dhĂ«nat kur mungon njĂ« bllok tĂ« dhĂ«nash, duhet tĂ« lexojmĂ« vetĂ«m n/l blloqe â kjo Ă«shtĂ« l herĂ« mĂ« pak sesa nĂ« kodet e Reed-Solomon.
PĂ«r 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Ă« tepĂ«rt, P3, P4 janĂ« 2 blloqe lokale tĂ« tepĂ«rt.
Blloqet e kodit tĂ« tepĂ«rt P1, P2 llogariten duke pĂ«rdorur 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.
Të tjerat bëhen në LRC duke ndjekur kodet e Ridhardit - Solomonit. Ekuacionet për llogaritjen e fjalëve të blloqeve të kodit të tepërt do të jenë këto:
Për të përcaktuar numrat alfa, beta, gamma, delta, duhet të përmbushen disa kushte që garantojnë mundësinë e rikuperimit të të dhënave (dmth, zgjidhja e sistemit të ekuacioneve). Më shumë rreth tyre mund të lexoni në .
Po ashtu, në praktikë për llogaritjen e kodeve lokale te tepërt P3, P4 përdoret operacioni XOR.
Nga sistemi i ekuacioneve për LRC nxirren disa përfundime:
- Për të rikuperuar çdo 1 bllok të dhënash është e mjaftueshme të lexoni n/l blloqe (n/2 në shembullin tonë).
- NĂ«se nuk janĂ« tĂ« arritshĂ«m r + l blloqe, dhe tĂ« gjitha blloqet pĂ«rfshihen nĂ« njĂ« grup, atĂ«herĂ« tĂ« dhĂ«nat nuk mund tĂ« rikuperohen. Kjo mund tĂ« shpjegohet lehtĂ« me njĂ« shembull. Le tĂ« themi se blloqet X1âX3 dhe P3 nuk janĂ« tĂ« arritshme: kĂ«to janĂ« r + l blloqe nga njĂ« grup, 4 nĂ« rastin tonĂ«. AtĂ«herĂ« kemi njĂ« sistem tĂ« 3 ekuacioneve me 4 tĂ« panjohura, tĂ« cilin nuk mund ta zgjidhim.
- Në të gjitha rastet e tjera të paprekshmërisë r + l blloqe (kur nga çdo grup është i arritshëm të paktën një bllok), të dhënat në LRC mund të rikuperohen.
Prandaj, LRC është më i mirë se kodet Ridhard - Solomon në rikuperimin e të dhënave pas gabimeve të vetme. Në kodet Ridhard - Solomon, për të rikuperuar edhe një bllok të dhënash duhet të përdoren n blloqe, ndërsa në LRC për të rikuperuar një bllok të dhënash është e mjaftueshme të përdoren n/l blloqe (n/2 në shembullin tonë). Nga ana tjetër, LRC humbet përpara kodeve Ridhard - Solomon në numrin maksimal të gabimeve të lejuara. Në shembujt e mësipërm, kodet Ridhard - Solomon mund të rikuperojnë të dhënat për çdo 4 gabim, ndërsa për LRC ka 2 kombinime nga 4 gabime, kur të dhënat nuk mund të rikuperohen.
ĂfarĂ« Ă«shtĂ« mĂ« e rĂ«ndĂ«sishme - varet nga situata specifike, por shpesh kursimi i ngarkesĂ«s sĂ« tepĂ«rt qĂ« ofron LRC e kalon disi besueshmĂ«rinĂ« e pakĂ«t tĂ« ruajtjes.
4. Kodet e tjera të tepërt
Përveç kodeve Ridhard - 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 anë të operatorit XOR. Operacioni XOR kryhet mbi n blloqe të dhënash dhe rezulton në 1 bllok kode të tepërt, dmth, skema n+1 (n blloqe të dhënash, 1 kod të tepërt). Përdoret në , ku blloqet e të dhënave dhe të kodit të tepërt shkruhen 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, që do të thotë skema n+2.
- Algoritmi STAR, i bazuar në operacionin XOR. Lejon ndërtimin e 3 bllokëve të kodit të tepërt, që do të thotë skema n+3.
- Kodet Pyramide â njĂ« tjetĂ«r kod i tepĂ«rt nga Microsoft.
5. Përdorimi në Yandex
Një numër projektesh infrastrukturore të Yandex përdorin kode të tepërta për ruajtjen e besueshme të të dhënave. Ja disa shembuj:
- Sistemi i brendshëm të ruajtjes së objektit MDS, për të cilin kam shkruar në fillim të artikullit.
- â Sistemi MapReduce i Yandex.
- (Yandex DataBase) â njĂ« bazĂ« tĂ« dhĂ«nash distribuate newSQL.
Në MDS përdoren kode të tepërta LRC, skema 8-2-2. Të dhënat me kode të tepërta shkruhen në 12 diska të ndryshëm në servera të ndryshëm në 3 DC të ndryshme: 4 servera në çdo DC. Më shumë rreth kësaj lexoni në .
Në YT përdoren si kodet e Reed-Solomon (skema 6-3), të cilat u implementuan të parat, ashtu edhe kode të tepërta LRC (skema 12-2-2), përkatësisht LRC është mënyra e preferuar e ruajtjes.
Në YDB përdoren kode të tepërta, të bazuara në even-odd (skema 4-2). Rreth kodeve të tepërta në YDB është diskutohet tashmë .
PĂ«rdorimi i skemave tĂ« ndryshme tĂ« kodeve tĂ« tepĂ«rta Ă«shtĂ« i justifikuar nga kĂ«rkesat e ndryshme qĂ« u vendosen sistemeve. PĂ«r shembull, nĂ« MDS, tĂ« dhĂ«nat e ruajtura me LRC vendosen menjĂ«herĂ« nĂ« 3 DC. Na intereson qĂ« tĂ« dhĂ«nat tĂ« qĂ«ndrojnĂ« tĂ« aksesueshme pĂ«r lexim gjatĂ« dĂ«shtimit tĂ« ndonjĂ« DC, prandaj blloqet duhet tĂ« jenĂ« tĂ« shpĂ«rndara nĂ« DC nĂ« mĂ«nyrĂ« qĂ«, nĂ« rastin e mungesĂ«s sĂ« ndonjĂ« DC, numri i blloqeve tĂ« papĂ«rdorshme tĂ« mos kalojĂ« nivelin e pranueshĂ«m. NĂ« skemĂ«n 8-2-2 mund tĂ« vendosen 4 blloqe nĂ« çdo DC, kĂ«shtu qĂ« me ndalimin e ndonjĂ« DC, do tĂ« ketĂ« 4 blloqe tĂ« papĂ«rdorshme, dhe tĂ« dhĂ«nat mund tĂ« lexohen. Ădo skemĂ« qĂ« zgjidhim pĂ«r vendosjen nĂ« 3 DC, nĂ« çdo rast, duhet tĂ« jetĂ« (r + l) / n >= 0,5, qĂ« do tĂ« thotĂ« se tepĂ«rsia e ruajtjes do tĂ« jetĂ« tĂ« paktĂ«n 50%.
Në YT situata është e ndryshme: çdo klaster YT vendoset plotësisht në 1 DC (klastere të ndryshme në DC të ndryshme), prandaj atje nuk ka një kufizim të tillë. Skema 12-2-2 ofron tepërsinë 33%, që do të thotë se ruajtja e të dhënave është më e lirë, dhe gjithashtu mund të përballojnë deri në 4 ndalime të disqeve në të njëjtën kohë, ashtu si skema në MDS.
Ka janë shumë veçori të tjera të përdorimit të kodit të tepërt në sistemet e ruajtjes dhe përpunimit të të dhënave: detaje të rikuperimit të të dhënave, ndikimi i rikuperimit në kohën e ekzekutimit të kërkesave, veçoritë e shkruarjes së të dhënave etj. Unë kam ndërmend të flas veçmas për këto dhe veçori të tjera të përdorimit të kodit të tepërt në praktikë, nëse tema do të jetë interesante.
6. Lidhjet
- Seria e artikujve mbi kodet e Ridh-Salomoni dhe fushat e Galois:
Në to shqyrtohet matematika më thellë në një gjuhë të aksesueshme. - Artikulli nga Microsoft mbi LRC:
Në seksionin 2 shpjegohet shkurtimisht teoria, më pas shqyrtohet përvoja e aplikimit të LRC në praktikë. - Sistemi even-odd:
- Sistemi STAR:
- Pyramid codes:
- Kodet e tepërt në MDS:
- Kodet e tepërt në YT:
- Kodet e tepërt në YDB:
Burimi: habr.com
