Jen kiel aspektas redundo
Redundaj kodoj* estas vaste uzataj en komputilaj sistemoj por pliigi la fidindecon de datumstokado. En Yandex ili estas uzataj en multaj projektoj. Ekzemple, uzi redundajn kodojn anstataŭ reproduktadon en nia interna objektostokado ŝparas milionojn sen oferi fidindecon. Sed malgraŭ ilia ĝeneraligita uzo, klaraj priskriboj pri kiel funkcias redundaj kodoj estas tre maloftaj. Tiuj, kiuj volas kompreni, alfrontas proksimume la jenon (de ):
Mi nomiĝas Vadim, ĉe Yandex mi disvolvas internan objektan stokadon MDS. En ĉi tiu artikolo, mi priskribos per simplaj vortoj la teoriajn fundamentojn de redundaj kodoj (Reed-Solomon kaj LRC-kodoj). Mi rakontos al vi kiel ĝi funkcias, sen kompleksa matematiko kaj maloftaj terminoj. Fine mi donos ekzemplojn pri uzado de redundaj kodoj en Yandex.
Mi ne konsideros kelkajn matematikajn detalojn detale, sed mi provizos ligilojn por tiuj, kiuj volas plonĝi pli profunden. Mi ankaŭ rimarkos, ke iuj matematikaj difinoj eble ne estas striktaj, ĉar la artikolo ne estas destinita al matematikistoj, sed al inĝenieroj, kiuj volas kompreni la esencon de la afero.
* En anglalingva literaturo oni ofte nomas redundajn kodojn forviŝkodojn.
1. La esenco de redundaj kodoj
La esenco de ĉiuj redundaj kodoj estas ege simpla: stoki (aŭ transdoni) datumojn, por ke ĝi ne perdiĝu kiam okazas eraroj (diskofiasoj, eraroj pri transdono de datumoj ktp.).
En la plej multaj* redundaj kodoj, la datenoj estas dividitaj en n datumblokojn, por kiuj m-blokoj da redundaj kodoj estas nombritaj, rezultigante entute n + m blokoj. Redundaj kodoj estas konstruitaj tiel ke n blokoj da datenoj povas esti reakiritaj uzante nur parton de n + m blokoj. Poste, ni konsideros nur blokajn redundajn kodojn, tio estas, tiujn en kiuj la datumoj estas dividitaj en blokojn.
Por reakiri ĉiujn n blokojn da datumoj, vi devas havi almenaŭ n el n + m blokoj, ĉar vi ne povas akiri n blokojn havante nur n-1 blokon (en ĉi tiu kazo, vi devus preni 1 blokon "el maldika". aero”). Ĉu n hazardaj blokoj de n + m blokoj sufiĉas por reakiri ĉiujn datumojn? Ĉi tio dependas de la tipo de redundaj kodoj, ekzemple, Reed-Solomon-kodoj permesas reakiri ĉiujn datumojn per arbitra n blokoj, sed LRC-redundokodoj ne ĉiam faras.
Stokado de datumoj
En sistemoj de konservado de datumoj, kiel regulo, ĉiu el la datumblokoj kaj redundaj kodblokoj estas skribitaj al aparta disko. Tiam, se arbitra disko malsukcesas, la originaj datumoj ankoraŭ povas esti restarigitaj kaj legitaj. Datumoj povas esti reakiritaj eĉ se pluraj diskoj malsukcesas samtempe.
Transdono de datumoj
Redundaj kodoj povas esti uzataj por fidinde transdoni datumojn tra nefidinda reto. La transdonitaj datumoj estas dividitaj en blokojn, kaj redundaj kodoj estas kalkulitaj por ili. Kaj datumblokoj kaj redundaj kodblokoj estas elsenditaj tra la reto. Se eraroj okazas en arbitraj blokoj (ĝis certa nombro da blokoj), datumoj ankoraŭ povas esti transdonitaj tra la reto sen eraroj. Reed-Solomon-kodoj, ekzemple, estas utiligitaj por elsendi datenojn super optikaj komunikadlinioj kaj en satelitkomunikadoj.
* Ekzistas ankaŭ redundaj kodoj en kiuj la datumoj ne estas dividitaj en blokojn, kiel Hamming-kodoj kaj CRC-kodoj, kiuj estas vaste uzataj por transdono de datumoj en Ethernet-retoj. Ĉi tiuj estas kodoj por erarkorekta kodigo, ili estas dizajnitaj por detekti erarojn, kaj ne por korekti ilin (la Hamming-kodo ankaŭ permesas partan korektadon de eraroj).
2. Reed-Solomon-kodoj
Reed-Solomon-kodoj estas unu el la plej uzataj redundokodoj, inventitaj reen en la 1960-aj jaroj kaj unue vaste uzataj en la 1980-aj jaroj por amasproduktado de kompaktaj diskoj.
Estas du ŝlosilaj demandoj por kompreni Reed-Solomon-kodojn: 1) kiel krei blokojn de redundaj kodoj; 2) kiel reakiri datumojn uzante redundajn kodblokojn. Ni trovu respondojn al ili.
Por simpleco, ni plu supozos ke n=6 kaj m=4. Aliaj skemoj estas konsiderataj per analogio.
Kiel krei redundajn kodblokojn
Ĉiu bloko de redundkodoj estas nombrita sendepende de la aliaj. Ĉiuj n datumblokoj estas uzataj por nombri ĉiun blokon. En la suba diagramo, X1-X6 estas datumblokoj, P1-P4 estas redundaj kodblokoj.
Ĉiuj datumblokoj devas esti la sama grandeco, kaj nul bitoj povas esti uzitaj por paraleligo. La rezultaj redundaj kodblokoj estos la sama grandeco kiel la datumblokoj. Ĉiuj datumblokoj estas dividitaj en vortojn (ekzemple, 16 bitoj). Ni diru, ke ni disigas la datumblokojn en k vortojn. Tiam ĉiuj blokoj de redundaj kodoj ankaŭ estos dividitaj en k vortojn.
Por kalkuli la i-an vorton de ĉiu redunda bloko, la i-aj vortoj de ĉiuj datumblokoj estos uzataj. Ili estos kalkulitaj laŭ la sekva formulo:
Ĉi tie la valoroj x estas la vortoj de datumblokoj, p estas la vortoj de redundaj kodblokoj, ĉiuj alfa, beta, gama kaj delta estas speciale elektitaj nombroj, kiuj estas samaj por ĉiuj i. Oni devas tuj diri, ke ĉiuj ĉi tiuj valoroj ne estas ordinaraj nombroj, sed elementoj de la kampo de Galois; la operacioj +, -, *, / ne estas operacioj konataj al ni ĉiuj, sed specialaj operacioj enkondukitaj sur elementoj de la Galois. kampo.
Kial estas bezonataj kampoj de Galois?
Ŝajnus, ke ĉio estas simpla: ni dividas la datumojn en blokojn, la blokojn en vortojn, uzante la vortojn de la datumblokoj ni kalkulas la vortojn de la redundaj kodblokoj - ni ricevas redundajn kodblokojn. Ĝenerale tiel funkcias, sed la diablo estas en la detaloj:
- Kiel dirite supre, la vorto grandeco estas fiksita, en nia ekzemplo 16 bitoj. La formuloj supre por Reed-Solomon-kodoj estas tiaj ke dum uzado de ordinaraj entjeroj, la rezulto de kalkulado de p eble ne estas reprezentebla uzante vorton de valida grandeco.
- Kiam oni reakiras datumojn, la supraj formuloj estos konsiderataj kiel sistemo de ekvacioj, kiuj devas esti solvitaj por reakiri la datumojn. Dum la solvprocezo, povas esti necese dividi entjerojn unu de la alia, rezultigante realan nombron kiu ne povas esti precize reprezentita en komputilmemoro.
Tiuj problemoj malhelpas la uzon de entjeroj por Reed-Solomon-kodoj. La solvo de la problemo estas originala, ĝi povas esti priskribita jene: ni elpensu specialajn nombrojn, kiuj povas esti reprezentitaj per vortoj de la bezonata longo (ekzemple, 16 bitoj), kaj la rezulto de plenumi ĉiujn operaciojn sur kiuj (aldono , subtraho, multipliko, divido) ankaŭ estos prezentitaj en komputila memoro uzante vortojn de la bezonata longo.
Tiaj "specialaj" nombroj estas studitaj de matematiko dum longa tempo; ili estas nomitaj kampoj. Kampo estas aro de elementoj kun operacioj de adicio, subtraho, multipliko kaj divido difinitaj por ili.
Galois*-kampoj estas kampoj por kiuj ekzistas unika rezulto de ĉiu operacio (+, -, *, /) por iuj du elementoj de la kampo. Galois-kampoj povas esti konstruitaj por nombroj kiuj estas potencoj de 2: 2, 4, 8, 16, ktp. (fakte potencoj de iu primo p, sed praktike ni interesiĝas nur pri potencoj de 2). Ekzemple, por 16-bitaj vortoj, ĉi tio estas kampo enhavanta 65 536 elementojn, por ĉiu paro de kiuj vi povas trovi la rezulton de iu ajn operacio (+, -, *, /). La valoroj de x, p, alfa, beta, gama, delta el la supraj ekvacioj estos konsiderataj elementoj de la kampo de Galois por kalkuloj.
Tiel, ni havas sistemon de ekvacioj kun kiu ni povas konstrui blokojn de redundaj kodoj skribante taŭgan komputilan programon. Uzante la saman sistemon de ekvacioj, vi povas fari reakiron de datumoj.
* Ĉi tio ne estas strikta difino, sed prefere priskribo.
Kiel reakiri datumojn
Restarigo estas necesa kiam kelkaj el la n + m blokoj mankas. Ĉi tiuj povas esti kaj datumblokoj kaj redundaj kodblokoj. La foresto de datumblokoj kaj/aŭ redundaj kodblokoj signifos ke la ekvivalentaj x kaj/aŭ p variabloj estas nekonataj en la ekvacioj supre.
La ekvacioj por Reed-Solomon-kodoj povas esti rigardataj kiel sistemo de ekvacioj, en kiuj ĉiuj alfa, beta, gama, delta valoroj estas konstantoj, ĉiuj x kaj p respondaj al la disponeblaj blokoj estas konataj variabloj, kaj la ceteraj x kaj p. estas nekonataj.
Ekzemple, lasu datumblokojn 1, 2, 3 kaj redundan kodblokon 2 esti neatingeblaj, tiam por la i-a grupo de vortoj estos la sekva sistemo de ekvacioj (nekonatoj estas markitaj ruĝe):
Ni havas sistemon de 4 ekvacioj kun 4 nekonataj, kio signifas, ke ni povas solvi ĝin kaj restarigi la datumojn!
El tiu sistemo de ekvacioj sekvas kelkaj konkludoj pri datumreakiro por Reed-Solomon-kodoj (n datumblokoj, m redundaj kodblokoj):
- Datumoj povas esti reakiritaj se iuj m blokoj aŭ malpli estas perditaj. Se m+1 aŭ pli da blokoj estas perditaj, la datenoj ne povas esti restarigitaj: estas neeble solvi sistemon de m ekvacioj kun m + 1 nekonataĵoj.
- Por reakiri eĉ unu datumblokon, vi devas uzi iun ajn n el la ceteraj blokoj, kaj vi povas uzi iun ajn el la redundaj kodoj.
Kion alian vi bezonas scii
En la supra priskribo, mi evitas kelkajn gravajn aferojn, kiuj postulas pli profundan plonĝon en matematikon por konsideri. Precipe, mi diras nenion pri la sekvanta:
- La sistemo de ekvacioj por Reed-Solomon-kodoj devas havi (unikan) solvon por iu kombinaĵo de nekonataĵoj (ne pli ol m nekonatoj). Surbaze de ĉi tiu postulo, la valoroj de alfa, beta, gama kaj delta estas elektitaj.
- Sistemo de ekvacioj devas esti aŭtomate konstruita (depende de kiuj blokoj estas neatingeblaj) kaj solvita.
- Ni devas konstrui Galois-kampon: por donita vortogrando, povi trovi la rezulton de iu ajn operacio (+, -, *, /) por iuj du elementoj.
Fine de la artikolo estas referencoj al literaturo pri tiuj gravaj aferoj.
Elekto de n kaj m
Kiel elekti n kaj m praktike? En praktiko, en datumstokaj sistemoj, redundaj kodoj estas uzataj por ŝpari spacon, do m ĉiam estas elektita malpli ol n. Iliaj specifaj valoroj dependas de kelkaj faktoroj, inkluzive de:
- Fidindeco de datumstokado. Ju pli granda m, des pli granda la nombro da diskoj, kiuj povas esti travivitaj, tio estas, des pli alta la fidindeco.
- Redunda stokado. Ju pli alta la m/n-proporcio, des pli alta la stokadredundo estos, kaj des pli multekosta la sistemo estos.
- Petu prilaboran tempon. Ju pli granda la sumo n + m, des pli longa estos la respondtempo al petoj. Ĉar legado de datumoj (dum reakiro) postulas legi n blokojn konservitajn sur n malsamaj diskoj, la legotempo estos determinita de la plej malrapida disko.
Krome, stoki datenojn en pluraj Dc trudas kromajn restriktojn sur la elekto de n kaj m: se 1 Dc estas malŝaltita, la datenoj daŭre devas esti haveblaj por legado. Ekzemple, dum konservado de datumoj en 3 DC-oj, la sekva kondiĉo devas esti plenumita: m >= n/2, alie povas esti situacio kie la datumoj ne estas disponeblaj por legado kiam 1 DC estas malŝaltita.
3. LRC - Lokaj Rekonstruaj Kodoj
Por reakiri datumojn per Reed-Solomon-kodoj, vi devas uzi n arbitrajn datumblokojn. Ĉi tio estas tre grava malavantaĝo por distribuitaj datumstokaj sistemoj, ĉar por restarigi datumojn sur unu rompita disko, vi devos legi datumojn de la plej multaj el la aliaj, kreante grandan plian ŝarĝon sur la diskoj kaj la reto.
La plej oftaj eraroj estas la nealirebleco de unu bloko da datumoj pro malsukceso aŭ troŝarĝo de unu disko. Ĉu eblas iel redukti la troan ŝarĝon por reakiro de datumoj en ĉi tiu (plej ofta) kazo? Rezultas, ke vi povas: ekzistas LRC-redundaj kodoj specife por ĉi tiu celo.
LRC (Lokaj Rekonstruaj Kodoj) estas redundaj kodoj inventitaj de Mikrosofto por uzo en Windows Azure Storage. La ideo de LRC estas kiel eble plej simpla: dividu ĉiujn datumblokojn en du (aŭ pli) grupojn kaj legu parton de la redundaj kodblokoj por ĉiu grupo aparte. Tiam kelkaj redundaj kodblokoj estos kalkulitaj uzante ĉiujn datumblokojn (en LRC ili estas nomitaj tutmondaj redundaj kodoj), kaj kelkaj - uzante unu el du grupoj de datumblokoj (ili estas nomitaj lokaj redundaj kodoj).
LRC estas indikita per tri nombroj: nrl, kie n estas la nombro da datumblokoj, r estas la nombro da tutmondaj redundaj kodblokoj, l estas la nombro da lokaj redundaj kodblokoj. Por legi datumojn kiam unu datumbloko estas neatingebla, vi devas legi nur n/l blokojn - tio estas l fojojn malpli ol en Reed-Solomon-kodoj.
Ekzemple, konsideru la LRC 6-2-2-skemon. X1–X6 — 6 datumblokoj, P1, P2 — 2 tutmondaj redundblokoj, P3, P4 — 2 lokaj redundblokoj.
Redundaj kodblokoj P1, P2 estas nombritaj uzante ĉiujn datumblokojn. Redunda kodbloko P3 - uzante datumblokojn X1-X3, redundanca kodbloko P4 - uzante datumblokojn X4-X6.
La resto estas farita en LRC per analogeco kun Reed-Solomon-kodoj. La ekvacioj por kalkuli la vortojn de redundaj kodblokoj estos:
Por elekti la nombrojn alfa, beta, gama, delta, oni devas plenumi kelkajn kondiĉojn por garantii la eblecon de reakiro de datumoj (tio estas, solvi la ekvacian sistemon). Vi povas legi pli pri ili en .
Ankaŭ en praktiko, la operacio XOR estas uzata por kalkuli lokajn redundajn kodojn P3, P4.
Kelkaj konkludoj sekvas el la sistemo de ekvacioj por LRC:
- Por reakiri ajnan 1 datumblokon, sufiĉas legi n/l blokojn (n/2 en nia ekzemplo).
- Se r + l-blokoj estas neatingeblaj, kaj ĉiuj blokoj estas inkluditaj en unu grupo, tiam la datumoj ne povas esti restarigitaj. Ĉi tio estas facile klarigi per ekzemplo. Estu neatingeblaj blokoj X1–X3 kaj P3: ĉi tiuj estas r + l blokoj de la sama grupo, 4 en nia kazo. Tiam ni havas sistemon de 3 ekvacioj kun 4 nekonatoj kiuj ne povas esti solvitaj.
- En ĉiuj aliaj kazoj de malhavebleco de r + l blokoj (kiam almenaŭ unu bloko estas havebla de ĉiu grupo), la datenoj en la LRC povas esti restarigitaj.
Tiel, LRC superas Reed-Solomon-kodojn en reakiro de datumoj post ununuraj eraroj. En Reed-Solomon-kodoj, por reakiri eĉ unu blokon da datumoj, vi devas uzi n blokojn, kaj en LRC, por reakiri unu blokon da datumoj, sufiĉas uzi n/l blokojn (n/2 en nia ekzemplo). Aliflanke, LRC estas pli malalta ol Reed-Solomon-kodoj laŭ la maksimuma nombro da permeseblaj eraroj. En la supraj ekzemploj, Reed-Solomon-kodoj povas reakiri datumojn por iuj 4 eraroj, kaj por LRC estas 2 kombinaĵoj de 4 eraroj kiam datumoj ne povas esti reakiritaj.
Kio estas pli grava dependas de la specifa situacio, sed ofte la ŝparoj en troa ŝarĝo kiun LRC provizas superpezas la iomete malpli fidindan stokadon.
4. Aliaj redundaj kodoj
Krom Reed-Solomon kaj LRC-kodoj, ekzistas multaj aliaj redundaj kodoj. Malsamaj redundaj kodoj uzas malsaman matematikon. Jen kelkaj aliaj redundaj kodoj:
- Redunda kodo uzante la XOR-funkciigiston. La operacio XOR estas farita sur n datumblokoj, kaj 1 bloko de redundaj kodoj estas akirita, tio estas, n+1 skemo (n datumblokoj, 1 redunda kodo). Uzita en , kie blokoj de datenoj kaj redundokodoj estas cikle skribitaj al ĉiuj diskoj de la tabelo.
- Para-nepara algoritmo bazita sur la XOR-operacio. Permesas al vi konstrui 2 blokojn de redundaj kodoj, tio estas, la skemo n+2.
- STAR-algoritmo bazita sur la operacio XOR. Ebligas al vi konstrui 3 blokojn de redundaj kodoj, tio estas, la skemo n+3.
- Piramidaj kodoj estas aliaj redundaj kodoj de Microsoft.
5. Uzu en Yandex
Kelkaj Yandex-infrastrukturprojektoj uzas redundajn kodojn por fidinda datumstokado. Jen kelkaj ekzemploj:
- MDS interna objektostokado, pri kiu mi skribis komence de la artikolo.
- — MapReduce-sistemo de Yandex.
- (Yandex DataBase) - newSQL distribuita datumbazo.
MDS uzas LRC-redundokodojn, 8-2-2-skemon. Datumoj kun redundaj kodoj estas skribitaj al 12 malsamaj diskoj en malsamaj serviloj en 3 malsamaj DC-oj: 4 serviloj en ĉiu DC. Legu pli pri tio en .
YT uzas kaj Reed-Solomon-kodojn (Skemo 6-3), kiuj estis la unuaj se temas pri efektivigi, kaj LRC-redundokodojn (Skemo 12-2-2), kie LRC estas la preferata stokadmetodo.
YDB uzas para-neparajn bazitajn redundokodojn (Figuro 4-2). Pri redundaj kodoj en YDB jam .
La uzo de malsamaj redundaj kodkabaloj ŝuldiĝas al malsamaj postuloj por sistemoj. Ekzemple, en MDS, datenoj stokitaj uzante LRC estas metitaj en 3 Dc tuj. Gravas por ni, ke la datumoj restas disponeblaj por legado se 1 el iuj DC-oj malsukcesas, tial la blokoj devas esti distribuitaj tra la DC-oj tiel ke se iu DC estas neatingebla, la nombro da nealireblaj blokoj estas ne pli ol permesebla. En la skemo 8-2-2, vi povas meti 4 blokojn en ĉiu DC, tiam kiam iu ajn DC estas malŝaltita, 4 blokoj estos neatingeblaj, kaj la datumoj povas esti legitaj. Kian ajn skemon ni elektas, kiam ni metas ĝin en 3 DC-ojn, ĉiukaze devus esti (r + l) / n >= 0,5, tio estas, stokado-redundo estos almenaŭ 50%.
En YT la situacio estas malsama: ĉiu YT-areto estas tute situanta en 1 DC (malsamaj aretoj en malsamaj DCoj), do ne ekzistas tia limigo. La 12-2-2-skemo provizas 33%-redundon, tio estas, stokado de datumoj estas pli malmultekosta, kaj ĝi ankaŭ povas travivi ĝis 4 samtempajn diskojn, same kiel la MDS-skemo.
Estas multaj pli da funkcioj de la uzo de redundaj kodoj en datumstokado kaj prilaborado de sistemoj: nuancoj de datumoj reakiro, la efiko de reakiro sur demanda ekzekuto tempo, trajtoj de datumregistrado, ktp. Mi parolos aparte pri ĉi tiuj kaj aliaj funkcioj. de la uzo de redundaj kodoj en la praktiko, se la temo estos interesa.
6. Ligiloj
- Serio de artikoloj pri Reed-Solomon-kodoj kaj Galois-kampoj:
Ili pli profunde rigardas matematikon en alirebla lingvo. - Artikolo de Mikrosofto pri LRC:
Sekcio 2 mallonge klarigas la teorion kaj poste diskutas spertojn kun LRC en praktiko. - Eben-nepara skemo:
- STEL-skemo:
- Piramidaj kodoj:
- Redundaj kodoj en MDS:
- Redundaj kodoj en YT:
- Redundaj kodoj en YDB:
fonto: www.habr.com