Hau da erredundantziaren itxura
Erredundantzia-kodeak* asko erabiltzen dira sistema informatikoetan, datuak biltegiratzeko fidagarritasuna areagotzeko. Yandex-en proiektu askotan erabiltzen dira. Adibidez, erredundantzia kodeak gure barneko objektuen biltegian errepikatu ordez erabiltzeak milioika aurrezten ditu fidagarritasunari uko egin gabe. Baina erabilera zabala duten arren, oso arraroak dira erredundantzia-kodeen funtzionamenduaren deskribapen argiak. Ulertu nahi dutenek, gutxi gorabehera, honako hauen aurrean daude (tik ):
Nire izena Vadim da, Yandex-en barne objektuen biltegiratze MDS garatzen ari naiz. Artikulu honetan, hitz errazekin deskribatuko ditut erredundantzia-kodeen oinarri teorikoak (Reed-Solomon eta LRC kodeak). Nola funtzionatzen duen esango dizut, matematika konplexurik eta termino arrarorik gabe. Amaieran Yandex-en erredundantzia kodeak erabiltzeko adibideak emango ditut.
Ez ditut zehatz-mehatz matematikako xehetasun batzuk kontuan hartuko, baina estekak jarriko ditut sakondu nahi dutenentzat. Era berean, ohartuko naiz definizio matematiko batzuk agian ez direla zorrotzak izan, artikulua ez baita matematikarientzat pentsatua, gaiaren funtsa ulertu nahi duten ingeniarientzat baizik.
* Ingelesezko literaturan, erredundantzia kodeak ezabatzeko kodeak deitzen dira sarritan.
1. Erredundantzia-kodeen funtsa
Erredundantzia-kode guztien funtsa oso sinplea da: datuak gorde (edo transmititu), akatsak gertatzen direnean gal ez daitezen (diskoaren hutsegiteak, datuak transferitzeko akatsak, etab.).
Erredundantzia-kode gehienetan*, datuak n datu-bloketan banatzen dira, eta, horretarako, erredundantzia-kodeen m bloke zenbatzen dira, guztira n + m bloke sortzen dira. Erredundantzia kodeak n + m blokeen zati bat soilik erabiliz n datu-bloke berreskuratu daitezkeen moduan eraikitzen dira. Jarraian, blokeen erredundantzia-kodeak soilik hartuko ditugu kontuan, hau da, datuak blokeetan banatuta daudenak.
n datu-bloke guztiak berreskuratzeko, gutxienez n + m blokeko n izan behar dituzu, ezin baita n bloke lortu n-1 bloke soilik edukita (kasu honetan, bloke 1 "mehetik atera beharko zenuke". aireaβ). Nahikoa al dira n + m blokeko ausazko n bloke datu guztiak berreskuratzeko? Hau erredundantzia-kode motaren araberakoa da, adibidez, Reed-Solomon kodeak datu guztiak berreskuratzeko aukera ematen du n bloke arbitrarioak erabiliz, baina LRC erredundantzia-kodeek ez dute beti egiten.
Datuak biltegiratzea
Datuak biltegiratzeko sistemetan, oro har, datu-bloke eta erredundantzia-kode-bloke bakoitza disko batean idazten da. Orduan, disko arbitrario batek huts egiten badu, jatorrizko datuak berreskuratu eta irakur daitezke oraindik. Datuak berreskura daitezke, nahiz eta hainbat diskok aldi berean huts egin.
Datuen transferentzia
Erredundantzia kodeak erabil daitezke datuak fidagarritasunez transmititzeko sare fidagarri batean. Igorritako datuak blokeetan banatzen dira, eta horientzako erredundantzia kodeak kalkulatzen dira. Datu-blokeak eta erredundantzia-kode-blokeak sarean transmititzen dira. Bloke arbitrarioetan akatsak gertatzen badira (bloke kopuru jakin batera arte), datuak sarean zehar igor daitezke oraindik errorerik gabe. Reed-Solomon kodeak, adibidez, komunikazio-lerro optikoen bidez eta satelite bidezko komunikazioetan datuak transmititzeko erabiltzen dira.
* Datuak blokeetan banatzen ez diren erredundantzia kodeak ere badaude, hala nola Hamming kodeak eta CRC kodeak, Ethernet sareetan datu-transmisiorako oso erabiliak direnak. Akatsak zuzentzeko kodeak dira, akatsak detektatzeko diseinatuta daude, eta ez zuzentzeko (Hamming kodeak ere akatsak partzialki zuzentzeko aukera ematen du).
2. Reed-Solomon kodeak
Reed-Solomon kodeak erredundantzia-koderik erabilienetako bat dira, 1960ko hamarkadan asmatutakoa eta 1980ko hamarkadan lehen aldiz disko trinkoen ekoizpen masiborako erabilia.
Bi galdera daude Reed-Solomon kodeak ulertzeko: 1) nola sortu erredundantzia-kodeen blokeak; 2) nola berreskuratu datuak erredundantzia-kode blokeak erabiliz. Aurki ditzagun erantzunak.
Sinpletasunerako, n=6 eta m=4 direla suposatuko dugu. Beste eskemak analogiaz hartzen dira kontuan.
Nola sortu erredundantzia-kode blokeak
Erredundantzia-kodeen bloke bakoitza besteekiko independentean zenbatzen da. N datu-bloke guztiak bloke bakoitza zenbatzeko erabiltzen dira. Beheko diagraman, X1-X6 datu-blokeak dira, P1-P4 erredundantzia-kode blokeak dira.
Datu-bloke guztiek tamaina berdina izan behar dute, eta zero bit erabil daitezke lerrokatzeko. Sortzen diren erredundantzia-kode-blokeak datu-blokeen tamaina berekoak izango dira. Datu-bloke guztiak hitzetan banatzen dira (adibidez, 16 bit). Demagun datu-blokeak k hitzetan zatitzen ditugula. Ondoren, erredundantzia-kodeen bloke guztiak ere k hitzetan banatuko dira.
Erredundantzia-bloke bakoitzaren i-garren hitza zenbatzeko, datu-bloke guztietako i-garren hitzak erabiliko dira. Formula honen arabera kalkulatuko dira:
Hemen x balioak datu-blokeen hitzak dira, p erredundantzia-kode blokeen hitzak dira, alfa, beta, gamma eta delta guztiak bereziki hautatutako zenbakiak dira, i guztientzako berdinak. Berehala esan behar da balio hauek guztiak ez direla zenbaki arruntak, Galois eremuko elementuak baizik; +, -, *, / eragiketak ez dira guztiok ezagutzen ditugun eragiketak, Galois-eko elementuetan sartutako eragiketa bereziak baizik. eremua.
Zergatik behar dira Galois-eko zelaiak?
Badirudi dena sinplea dela: datuak blokeetan banatzen ditugu, blokeak hitzetan, datu-blokeen hitzak erabiliz erredundantzia-kode blokeen hitzak zenbatzen ditugu -erredundantzia-kode blokeak lortzen ditugu. Orokorrean horrela funtzionatzen du, baina deabrua xehetasunetan dago:
- Goian esan bezala, hitzaren tamaina finkoa da, gure adibidean 16 bit. Reed-Solomon kodeetarako goiko formulak zenbaki oso arruntak erabiltzean baliteke p kalkulatzearen emaitza baliozko tamainako hitz bat erabiliz irudikagarria ez izatea.
- Datuak berreskuratzean, goiko formulak datuak berreskuratzeko ebatzi beharreko ekuazio-sistematzat hartuko dira. Ebazpen prozesuan zehar, baliteke zenbaki osoak elkarren artean zatitzea beharrezkoa izatea, ordenagailuaren memorian zehaztasunez irudikatu ezin den zenbaki erreal bat lortuz.
Arazo hauek Reed-Solomon kodeetarako zenbaki osoak erabiltzea eragozten dute. Arazoaren irtenbidea jatorrizkoa da, honela deskriba daiteke: asma ditzagun zenbaki bereziak behar den luzera duten hitzak erabiliz (adibidez, 16 bit) irudika daitezkeen eta horren gainean eragiketa guztiak egitearen emaitza (baketa , kenketa, biderketa, zatiketa) ordenagailuaren memorian ere aurkeztuko dira behar den luzera duten hitzak erabiliz.
Zenbaki "bereziak" horiek matematikak aspalditik aztertu ditu; eremu deitzen zaie. Eremu bat batuketa, kenketa, biderketa eta zatiketa eragiketak definitutako elementu multzo bat da.
Galois* eremuak eragiketa bakoitzaren emaitza bakarra (+, -, *, /) eremuko edozein elementutarako eremuak dira. Galois-eko eremuak 2-ren potentziak diren zenbakietarako eraiki daitezke: 2, 4, 8, 16, etab. (benetan p edozein zenbaki lehenen potentziak, baina praktikan 2-ren potentziak bakarrik interesatzen zaizkigu). Adibidez, 16 biteko hitzetarako, 65 elementu dituen eremu bat da, eta horietako bikote bakoitzeko edozein eragiketen emaitza aurki dezakezu (+, -, *, /). Goiko ekuazioetako x, p, alfa, beta, gamma, delta balioak Galois eremuko elementutzat hartuko dira kalkuluetarako.
Horrela, ekuazio-sistema bat dugu, zeinekin erredundantzia-kodeen blokeak eraiki ditzakegun programa informatiko egoki bat idatziz. Ekuazio-sistema bera erabiliz, datuak berreskuratu ditzakezu.
* Hau ez da definizio zorrotza, deskribapen bat baizik.
Nola berreskuratu datuak
Zaharberritzea beharrezkoa da n + m bloke batzuk falta direnean. Hauek datu-blokeak eta erredundantzia-kode blokeak izan daitezke. Datu-blokerik eta/edo erredundantzia-kode-blokerik ez egoteak goiko ekuazioetan dagozkion x eta/edo p aldagaiak ezezagunak direla esan nahi du.
Reed-Solomon kodeen ekuazioak alfa, beta, gamma, delta balio guztiak konstanteak diren ekuazio-sistema gisa ikus daitezke, eskuragarri dauden blokeei dagozkien x eta p guztiak aldagai ezagunak diren eta gainerako x eta p. ezezagunak dira.
Adibidez, utzi 1, 2, 3 datu-blokeak eta erredundantzia-kode-blokea 2 ez erabilgarri egon, orduan i-garren hitzen talderako honako ekuazio-sistema hau egongo da (ezezagunak gorriz markatuta daude):
4 ezezagun dituen 4 ekuazioko sistema dugu, hau da, ebatzi eta datuak berreskura ditzakegula!
Ekuazio-sistema honetatik hainbat ondorio ateratzen dira Reed-Solomon kodeen datuen berreskurapenari buruz (n datu-blokeak, m erredundantzia-kode-blokeak):
- Datuak berreskura daitezke m bloke edo gutxiago galtzen badira. m+1 bloke edo gehiago galtzen badira, datuak ezin dira berreskuratu: ezinezkoa da m + 1 ezezagun dituen m ekuazio-sistema ebaztea.
- Datu bloke bat ere berreskuratzeko, gainerako blokeetatik n edozein erabili behar duzu, eta erredundantzia-kodeetako edozein erabil dezakezu.
Zer gehiago jakin behar duzu
Goiko deskribapenean, kontuan hartu beharreko matematikan sakontzea eskatzen duten hainbat gai garrantzitsu saihesten ditut. Bereziki, ez dut ezer esaten honako hauei buruz:
- Reed-Solomon kodeen ekuazio-sistemak soluzio (bakarra) izan behar du ezezagunen edozein konbinaziorako (m ezezagun baino gehiago). Baldintza horren arabera, alfa, beta, gamma eta delta balioak hautatzen dira.
- Ekuazio-sistema automatikoki eraikitzeko gai izan behar da (erabilgarri ez dauden blokeen arabera) eta ebatzi.
- Galois eremu bat eraiki behar dugu: hitz-tamaina jakin baterako, edozein eragiketaren (+, -, *, /) edozein elementuren emaitza aurkitzeko gai izan.
Artikuluaren amaieran gai garrantzitsu horiei buruzko literaturari buruzko erreferentziak daude.
n eta m aukeraketa
Nola aukeratu n eta m praktikan? Praktikan, datuak biltegiratzeko sistemetan, erredundantzia kodeak erabiltzen dira espazioa aurrezteko, beraz, m beti n baino gutxiago aukeratzen da. Haien balio zehatzak faktore batzuen araberakoak dira, besteak beste:
- Datuak biltegiratzeko fidagarritasuna. Zenbat eta m handiagoa, orduan eta handiagoa izango da bizirik iraun dezaketen disko-hutsen kopurua, hau da, orduan eta fidagarritasun handiagoa.
- Biltegiratze erredundantea. Zenbat eta m/n erlazio handiagoa izan, orduan eta handiagoa izango da biltegiratze-erredundantzia, eta orduan eta garestiagoa izango da sistema.
- Eskaerak prozesatzeko denbora. Zenbat eta n + m batura handiagoa izan, orduan eta luzeagoa izango da eskaerei erantzuteko denbora. Datuak irakurtzeak (berreskuratzean) n disko ezberdinetan gordetako n bloke irakurtzea eskatzen duenez, irakurtzeko denbora disko motelenak zehaztuko du.
Horrez gain, datuak hainbat DCtan gordetzeak murrizketa gehigarriak ezartzen ditu n eta m aukeraketan: DC 1 desaktibatuta badago, datuak irakurtzeko eskuragarri egon behar dira oraindik. Adibidez, datuak 3 DC-tan gordetzean, baldintza hau bete behar da: m >= n/2, bestela 1 DC itzalita dagoenean datuak irakurtzeko erabilgarri ez dauden egoera egon daiteke.
3. LRC - Tokiko Berreraikuntza Kodeak
Reed-Solomon kodeak erabiliz datuak berreskuratzeko, n datu-bloke arbitrarioak erabili behar dituzu. Hau oso desabantaila nabarmena da banatutako datuak biltegiratzeko sistementzat, izan ere, hautsitako disko batean datuak berreskuratzeko, beste gehienen datuak irakurri beharko dituzu, diskoetan eta sarean karga gehigarri handia sortuz.
Akats ohikoenak datu-bloke baten eskuraezintasuna dira disko baten hutsegite edo gainkargaren ondorioz. Posible al da kasu (ohikoena) honetan datuak berreskuratzeko gehiegizko karga nolabait murriztea? Posible dela ematen du: LRC erredundantzia-kodeak daude horretarako bereziki.
LRC (Local Reconstruction Codes) Microsoft-ek Windows Azure biltegian erabiltzeko asmatutako erredundantzia kodeak dira. LRC-ren ideia ahalik eta sinpleena da: zatitu datu-bloke guztiak bi taldetan (edo gehiagotan) eta irakurri talde bakoitzeko erredundantzia-kode blokeen zati bat bereizita. Ondoren, erredundantzia-kode-bloke batzuk datu-bloke guztiak erabiliz zenbatuko dira (LRCn erredundantzia-kode globalak deitzen dira), eta beste batzuk, datu-blokeen bi taldeetako bat erabiliz (erredundantzia-kode lokalak deitzen zaie).
LRC hiru zenbakiz adierazten da: nrl, non n datu-blokeen kopurua den, r erredundantzia-kode-bloke globalen kopurua, l erredundantzia-kode-bloke lokalen kopurua. Datu-bloke bat erabilgarri ez dagoenean datuak irakurtzeko, n/l bloke bakarrik irakurri behar dituzu - hau Reed-Solomon kodeetan baino l aldiz gutxiago da.
Adibidez, kontuan hartu LRC 6-2-2 eskema. X1βX6 β 6 datu-bloke, P1, P2 β 2 erredundantzia-bloke global, P3, P4 β 2 tokiko erredundantzia-bloke.
P1, P2 erredundantzia-kode blokeak datu-bloke guztiak erabiliz zenbatzen dira. Erredundantzia-kode-blokea P3 - X1-X3 datu-blokeak erabiliz, erredundantzia-kode-blokea P4 - X4-X6 datu-blokeak erabiliz.
Gainerakoa LRCn egiten da Reed-Solomon kodeekin analogia eginez. Erredundantzia-kode blokeen hitzak zenbatzeko ekuazioak hauek izango dira:
Alfa, beta, gamma, delta zenbakiak hautatzeko, hainbat baldintza bete behar dira datuak berreskuratzeko aukera bermatzeko (hau da, ekuazio-sistema ebaztea). Hemen irakurri dezakezu haiei buruz .
Praktikan ere, XOR eragiketa P3, P4 erredundantzia-kode lokalak kalkulatzeko erabiltzen da.
LRCrako ekuazio-sistematik hainbat ondorio ateratzen dira:
- Edozein datu-bloke berreskuratzeko, nahikoa da n/l bloke irakurtzea (n/1 gure adibidean).
- r + l blokeak ez badaude erabilgarri eta bloke guztiak talde batean sartzen badira, orduan datuak ezin dira leheneratu. Hau erraz azaltzen da adibide batekin. Izan bedi X1βX3 eta P3 blokeak erabilgarri: talde bereko r + l blokeak dira, 4 gure kasuan. Orduan ebatzi ezin diren 3 ezezagun dituen 4 ekuazioko sistema dugu.
- R + l blokeen erabilgarritasunik ez dagoen beste kasu guztietan (talde bakoitzetik gutxienez bloke bat eskuragarri dagoenean), LRCko datuak leheneratu daitezke.
Horrela, LRC-k Reed-Solomon kodeak gainditzen ditu akats bakarren ondoren datuak berreskuratzerakoan. Reed-Solomon kodeetan, datu bloke bat ere berreskuratzeko, n bloke erabili behar dituzu, eta LRCn, datu bloke bat berreskuratzeko, nahikoa da n/l bloke erabiltzea (n/2 gure adibidean). Bestalde, LRC Reed-Solomon kodeak baino txikiagoa da onartzen diren akatsen gehienezko kopuruari dagokionez. Goiko adibideetan, Reed-Solomon kodeek 4 akatsen datuak berreskura ditzakete, eta LRCrako 2 akatsen 4 konbinazio daude datuak berreskuratu ezin direnean.
Garrantzitsuagoa dena egoera zehatzaren araberakoa da, baina askotan LRCk eskaintzen duen gehiegizko kargaren aurrezkiak biltegiratze apur bat fidagarriagoa dena baino handiagoa da.
4. Beste erredundantzia-kode batzuk
Reed-Solomon eta LRC kodeaz gain, beste erredundantzia kode asko daude. Erredundantzia-kode ezberdinek matematika desberdinak erabiltzen dituzte. Hona hemen beste erredundantzia-kode batzuk:
- Erredundantzia kodea XOR operadorea erabiliz. XOR eragiketa n datu-bloketan egiten da, eta erredundantzia-kodeen bloke 1 lortzen da, hau da, n+1 eskema (n datu-bloke, 1 erredundantzia-kode). urtean erabilia , non datu-blokeak eta erredundantzia-kodeak ziklikoki idazten diren matrizeko disko guztietan.
- XOR eragiketan oinarritutako algoritmo bikoiti-bakoitia. Erredundantzia-kodeen 2 bloke eraikitzeko aukera ematen du, hau da, n+2 eskema.
- XOR eragiketan oinarritutako STAR algoritmoa. Erredundantzia-kodeen 3 bloke eraikitzeko aukera ematen du, hau da, n+3 eskema.
- Pyramide kodeak Microsoft-en beste erredundantzia-kode batzuk dira.
5. Erabili Yandex-en
Yandex-eko azpiegitura-proiektu batzuek erredundantzia-kodeak erabiltzen dituzte datu fidagarriak biltegiratzeko. Hona hemen adibide batzuk:
- MDS barneko objektuen biltegiratzea, artikuluaren hasieran idatzi nuena.
- - Yandex-en MapReduce sistema.
- (Yandex DataBase) - newSQL banatutako datu-basea.
MDS-k LRC erredundantzia kodeak erabiltzen ditu, 8-2-2 eskema. Erredundantzia kodeak dituzten datuak 12 disko ezberdinetan idazten dira zerbitzari desberdinetan 3 DC ezberdinetan: 4 zerbitzari DC bakoitzean. Irakurri gehiago honi buruz .
YT-k biak erabiltzen ditu Reed-Solomon kodeak (6-3 eskema), inplementatu ziren lehenak, eta LRC erredundantzia kodeak (12-2-2 eskema), LRC biltegiratze-metodo hobetsia izanik.
YDB-k bikoiti-bakoitietan oinarritutako erredundantzia-kodeak erabiltzen ditu (4-2 irudia). Erredundantzia-kodeei buruz dagoeneko YDBn .
Erredundantzia-kode eskema desberdinak erabiltzea sistemen eskakizun desberdinengatik da. Adibidez, MDSn, LRC erabiliz biltegiratutako datuak 3 DCtan jartzen dira aldi berean. Guretzat garrantzitsua da datuak irakurtzeko eskuragarri egotea edozein DCren batek huts egiten badu; beraz, blokeak DCetan banatu behar dira, DCren bat erabilgarri ez badago, eskuraezin diren blokeen kopurua zilegi baino ez da izan. 1-8-2 eskeman, DC bakoitzean 2 bloke jar ditzakezu, gero edozein DC itzalita dagoenean, 4 bloke ez dira erabilgarri egongo eta datuak irakurri ahal izango dira. 4 DCtan jartzean aukeratzen dugun eskema edozein dela ere, nolanahi ere (r + l) / n >= 3 egon beharko luke, hau da, biltegiratze erredundantzia gutxienez % 0,5ekoa izango da.
YTn egoera ezberdina da: YT kluster bakoitza DC 1ean dago guztiz (kluster desberdinak DC ezberdinetan), beraz, ez dago murrizketarik. 12-2-2 eskemak % 33ko erredundantzia eskaintzen du, hau da, datuak gordetzea merkeagoa da, eta aldi berean 4 disko etenaldira arte ere iraun dezake, MDS eskemak bezala.
Datuak biltegiratzeko eta prozesatzeko sistemetan erredundantzia-kodeen erabileraren ezaugarri askoz gehiago daude: datuak berreskuratzeko Γ±abardurak, berreskuratzeak kontsultak egiteko denboran duen eragina, datuak grabatzeko ezaugarriak, etab. Ezaugarri horiei eta beste batzuei buruz aparte hitz egingo dut. Erredundantzia-kodeen erabilera praktikan, gaia interesgarria izango bada.
6. Estekak
- Reed-Solomon kodeak eta Galois eremuei buruzko artikulu sorta bat:
Matematika hizkuntza eskuragarrian sakontzen dute. - Microsoft-en artikulua LRCri buruz:
2. atalean teoria laburki azaltzen da eta ondoren LRCrekin praktikan izandako esperientziak eztabaidatzen dira. - Eskema bikoiti-bakoitia:
- STAR eskema:
- Piramideen kodeak:
- Erredundantzia kodeak MDSn:
- Erredundantzia kodeak YT-n:
- Erredundantzia kodeak YDBn:
Iturria: www.habr.com