Svona lítur offramboð út
Offramboðskóðar* eru mikið notaðir í tölvukerfum til að auka áreiðanleika gagnageymslu. Í Yandex eru þau notuð í mörgum verkefnum. Til dæmis, að nota offramboðskóða í stað afritunar í innri hlutageymslu okkar sparar milljónir án þess að fórna áreiðanleika. En þrátt fyrir útbreidda notkun þeirra eru skýrar lýsingar á því hvernig offramboðskóðar virka mjög sjaldgæfar. Þeir sem vilja skilja standa frammi fyrir um það bil eftirfarandi (frá ):
Ég heiti Vadim, hjá Yandex er ég að þróa MDS fyrir innri hlutageymslu. Í þessari grein mun ég lýsa í einföldum orðum fræðilegum grunni offramboðskóða (Reed-Solomon og LRC kóða). Ég skal segja þér hvernig það virkar, án flókinnar stærðfræði og sjaldgæfra hugtaka. Í lokin mun ég gefa dæmi um notkun offramboðskóða í Yandex.
Ég mun ekki íhuga fjölda stærðfræðilegra smáatriða í smáatriðum, en ég mun útvega tengla fyrir þá sem vilja kafa dýpra. Ég tek líka fram að sumar stærðfræðilegar skilgreiningar eru kannski ekki strangar þar sem greinin er ekki ætluð stærðfræðingum heldur verkfræðingum sem vilja skilja kjarna málsins.
* Í bókmenntum á ensku eru offramboðskóðar oft kallaðir eyðingarkóðar.
1. Kjarni offramboðskóða
Kjarninn í öllum offramboðskóðum er afar einfaldur: geymdu (eða sendu) gögn þannig að þau glatist ekki þegar villur eiga sér stað (bilanir á diskum, gagnaflutningsvillur osfrv.).
Í flestum* offramboðskóðum er gögnunum skipt í n gagnablokka, þar sem m blokkir af offramboðskóðum eru taldir, sem leiðir til alls n + m blokka. Offramboðskóðar eru smíðaðir á þann hátt að hægt er að endurheimta n blokkir af gögnum með því að nota aðeins hluta af n + m blokkum. Næst munum við aðeins líta á offramboðskóða fyrir blokkir, það er þá þar sem gögnunum er skipt í blokkir.
Til að endurheimta allar n blokkir af gögnum þarftu að hafa að minnsta kosti n af n + m blokkum, þar sem þú getur ekki fengið n blokkir með því að hafa aðeins n-1 blokk (í þessu tilfelli þarftu að taka 1 blokk „úr þunnu“ loft“). Eru n handahófskenndir kubbar af n + m kubbum nóg til að endurheimta öll gögnin? Þetta fer eftir tegund offramboðskóða, til dæmis, Reed-Solomon kóðar leyfa þér að endurheimta öll gögn með því að nota handahófskenndar n blokkir, en LRC offramboðskóðar gera það ekki alltaf.
Gagnageymsla
Í gagnageymslukerfum er hver gagnablokk og offramboðskóða að jafnaði skrifað á sérstakan disk. Síðan, ef handahófskenndur diskur bilar, er samt hægt að endurheimta upprunalegu gögnin og lesa þau. Hægt er að endurheimta gögn jafnvel þótt nokkrir diskar bili á sama tíma.
Gagnaflutningur
Hægt er að nota offramboðskóða til að senda gögn á áreiðanlegan hátt um óáreiðanlegt net. Sendu gögnunum er skipt í blokkir og offramboðskóðar eru reiknaðir fyrir þá. Bæði gagnablokkir og offramboðskóðablokkir eru sendar yfir netið. Ef villur eiga sér stað í handahófskenndum blokkum (allt að ákveðnum fjölda blokka) er samt hægt að senda gögn yfir netið án villu. Reed-Solomon kóðar eru til dæmis notaðir til að senda gögn yfir sjónrænar samskiptalínur og í gervihnattasamskiptum.
* Það eru líka til offramboðskóðar þar sem gögnunum er ekki skipt í blokkir, eins og Hamming kóðar og CRC kóðar, sem eru mikið notaðir fyrir gagnaflutning í Ethernet netkerfum. Þetta eru kóðar til að leiðrétta villur, þeir eru hannaðir til að greina villur, en ekki til að leiðrétta þær (Hamming kóðinn leyfir einnig leiðréttingu á villum að hluta).
2. Reed-Solomon kóðar
Reed-Solomon kóðar eru einn mest notaði offramboðskóðinn, fundinn upp á sjöunda áratugnum og fyrst mikið notaður á níunda áratugnum til fjöldaframleiðslu á geisladiskum.
Það eru tvær lykilspurningar til að skilja Reed-Solomon kóða: 1) hvernig á að búa til blokkir af offramboðskóðum; 2) hvernig á að endurheimta gögn með því að nota offramboðskóðablokkir. Við skulum finna svör við þeim.
Til einföldunar munum við frekar gera ráð fyrir að n=6 og m=4. Önnur kerfi eru talin með hliðstæðum hætti.
Hvernig á að búa til offramboðskóðablokkir
Hver blokk af offramboðskóðum er talin óháð hinum. Allir n gagnakubbar eru notaðir til að telja hvern blokk. Á skýringarmyndinni hér að neðan eru X1-X6 gagnablokkir, P1-P4 eru offramboðskóðablokkir.
Allir gagnablokkir verða að vera jafnstórir og hægt er að nota núllbita til að stilla. Offramboðskóðablokkirnar sem myndast verða af sömu stærð og gagnablokkirnar. Öllum gagnablokkum er skipt í orð (til dæmis 16 bita). Segjum að við skiptum gagnablokkunum í k orð. Þá verður öllum kubbum af offramboðskóðum einnig skipt í k orð.
Til að telja i-ta orðið í hverri offramboðsblokk verða i-ta orðin allra gagnakubba notuð. Þau verða reiknuð út samkvæmt eftirfarandi formúlu:
Hér eru gildin x orð gagnablokka, p eru orð offramboðskóðablokka, öll alfa, beta, gamma og delta eru sérstaklega valdar tölur sem eru eins fyrir alla i. Það verður að segjast strax að öll þessi gildi eru ekki venjulegar tölur, heldur þættir í Galois sviðinu; aðgerðirnar +, -, *, / eru ekki aðgerðir sem við öll kannast, heldur sérstakar aðgerðir kynntar á þáttum Galois sviði.
Af hverju er þörf á Galois-reitum?
Það virðist sem allt sé einfalt: við skiptum gögnunum í kubba, kubbunum í orð, með því að nota orð gagnablokkanna teljum við orðin í offramboðskóðablokkunum - við fáum offramboðskóðakubba. Almennt séð er þetta hvernig þetta virkar, en djöfullinn er í smáatriðunum:
- Eins og fram kemur hér að ofan er orðastærðin föst, í okkar dæmi 16 bitar. Formúlurnar hér að ofan fyrir Reed-Solomon kóða eru þannig að þegar venjulegar heilar tölur eru notaðar getur verið að niðurstaðan af útreikningi p sé ekki táknræn með því að nota orð af gildri stærð.
- Þegar gögn eru endurheimt verður litið á formúlurnar hér að ofan sem jöfnukerfi sem þarf að leysa til að endurheimta gögnin. Meðan á lausnarferlinu stendur gæti verið nauðsynlegt að deila heiltölum hver með annarri, sem leiðir til rauntölu sem ekki er hægt að sýna nákvæmlega í tölvuminni.
Þessi vandamál koma í veg fyrir notkun heiltalna fyrir Reed-Solomon kóða. Lausnin á vandamálinu er frumleg, því má lýsa á eftirfarandi hátt: við skulum koma með sérstakar tölur sem hægt er að tákna með því að nota orð af nauðsynlegri lengd (til dæmis 16 bita), og niðurstöðuna af því að framkvæma allar aðgerðir sem (viðbót) , frádráttur, margföldun, deiling) verður einnig sett fram í tölvuminni með því að nota orð af tilskildri lengd.
Slíkar „sérstök“ tölur hafa verið rannsakaðar af stærðfræði í langan tíma; þær eru kallaðar svið. Reitur er safn af þáttum með samlagningar-, frádráttar-, margföldunar- og deilingaraðgerðum skilgreindar fyrir þær.
Galois* reitir eru reitir þar sem það er einstök niðurstaða fyrir hverja aðgerð (+, -, *, /) fyrir hvaða tvo þætti reitsins sem er. Galois-reitir geta verið smíðaðir fyrir tölur sem eru 2: 2, 4, 8, 16 o.s.frv. (í raun veldi hvaða frumtölu p sem er, en í reynd höfum við aðeins áhuga á 2 veldum). Til dæmis, fyrir 16 bita orð, er þetta reitur sem inniheldur 65 þætti, fyrir hvert par sem þú getur fundið niðurstöðu hvaða aðgerð sem er (+, -, *, /). Gildin á x, p, alfa, beta, gamma, delta úr jöfnunum hér að ofan verða talin þættir í Galois sviðinu fyrir útreikninga.
Þannig höfum við jöfnukerfi sem við getum smíðað kubba af offramboðskóðum með því að skrifa viðeigandi tölvuforrit. Með því að nota sama jöfnukerfið geturðu framkvæmt endurheimt gagna.
* Þetta er ekki ströng skilgreining, heldur lýsing.
Hvernig á að endurheimta gögn
Endurreisnar er þörf þegar einhverja af n + m kubbunum vantar. Þetta geta verið bæði gagnablokkir og offramboðskóðablokkir. Skortur á gagnablokkum og/eða offramboðskóðablokkum mun þýða að samsvarandi x og/eða p breytur eru óþekktar í jöfnunum hér að ofan.
Hægt er að skoða jöfnurnar fyrir Reed-Solomon kóða sem jöfnukerfi þar sem öll alfa, beta, gamma, delta gildi eru fastar, allir x og p sem samsvara tiltækum blokkum eru þekktar breytur og x og p sem eftir eru. eru óþekkt.
Til dæmis, láttu gagnakubba 1, 2, 3 og offramboðskóðablokk 2 vera ótiltæka, þá verður eftirfarandi jöfnukerfi fyrir i-ta orðaflokkinn (óþekktir eru merktir með rauðu):
Við höfum kerfi af 4 jöfnum með 4 óþekktum, sem þýðir að við getum leyst það og endurheimt gögnin!
Frá þessu jöfnukerfi fylgja nokkrar ályktanir um endurheimt gagna fyrir Reed-Solomon kóða (n gagnablokkir, m offramboðskóðablokkir):
- Hægt er að endurheimta gögn ef einhverjar m blokkir eða færri glatast. Ef m+1 eða fleiri blokkir tapast er ekki hægt að endurheimta gögnin: það er ómögulegt að leysa kerfi m jöfnur með m + 1 óþekkt.
- Til að endurheimta jafnvel eina gagnablokk þarftu að nota hvaða n sem er af kubbunum sem eftir eru og þú getur notað hvaða offramboðskóða sem er.
Hvað þarf ég meira að vita?
Í lýsingunni hér að ofan forðast ég nokkur mikilvæg atriði sem þarfnast dýpri kafa í stærðfræði til að íhuga. Sérstaklega er ég ekki að segja neitt um eftirfarandi:
- Jöfnukerfið fyrir Reed-Solomon kóða verður að hafa (einstaka) lausn fyrir hvaða samsetningu óþekkts sem er (ekki meira en m óþekkt). Byggt á þessari kröfu eru gildi alfa, beta, gamma og delta valin.
- Jöfnukerfi verður að vera hægt að smíða sjálfkrafa (fer eftir því hvaða blokkir eru ekki tiltækar) og leysa það.
- Við þurfum að byggja upp Galois reit: fyrir tiltekna orðastærð, geta fundið niðurstöðu hvaða aðgerð sem er (+, -, *, /) fyrir hvaða tvo þætti sem er.
Í lok greinarinnar er vísað í bókmenntir um þessi mikilvægu málefni.
Val á n og m
Hvernig á að velja n og m í reynd? Í reynd, í gagnageymslukerfum, eru offramboðskóðar notaðir til að spara pláss, þannig að m er alltaf valið minna en n. Sérstök gildi þeirra eru háð fjölda þátta, þar á meðal:
- Áreiðanleiki gagnageymslu. Því stærri m, því meiri fjöldi diskbilana sem hægt er að lifa af, það er, því meiri er áreiðanleikinn.
- Óþarfi geymsla. Því hærra sem m/n hlutfallið er, því meiri verður offramboð á geymslum og því dýrara verður kerfið.
- Óska eftir afgreiðslutíma. Því stærri sem summan er n + m, því lengri verður svartími við beiðnum. Þar sem lestur gagna (meðan á endurheimt stendur) krefst þess að lesa n kubba sem eru geymdar á n mismunandi diskum, mun lestrartíminn ákvarðast af hægasta disknum.
Að auki, geymsla gagna í nokkrum DCs setur viðbótartakmarkanir á vali á n og m: ef slökkt er á 1 DC verða gögnin samt að vera tiltæk til lestrar. Til dæmis, þegar gögn eru geymd í 3 DC, þarf að uppfylla eftirfarandi skilyrði: m >= n/2, annars getur komið upp sú staða að gögnin séu ekki tiltæk til aflestrar þegar slökkt er á 1 DC.
3. LRC - Local Reconstruction Codes
Til að endurheimta gögn með Reed-Solomon kóða þarftu að nota n handahófskennda gagnablokka. Þetta er mjög verulegur ókostur fyrir dreifð gagnageymslukerfi, því til að endurheimta gögn á einum biluðum diski þarftu að lesa gögn frá flestum hinum, sem skapar mikið viðbótarálag á diskana og netið.
Algengustu villurnar eru óaðgengi eins gagnablokkar vegna bilunar eða ofhleðslu á einum diski. Er hægt að draga úr umframálagi fyrir endurheimt gagna á einhvern hátt í þessu (algengasta) tilviki? Það kemur í ljós að þú getur: það eru LRC offramboðskóðar sérstaklega í þessum tilgangi.
LRC (Local Reconstruction Codes) eru offramboðskóðar sem Microsoft hefur fundið upp til notkunar í Windows Azure Storage. Hugmyndin um LRC er eins einföld og mögulegt er: skiptu öllum gagnablokkum í tvo (eða fleiri) hópa og lestu hluta af offramboðskóðablokkunum fyrir hvern hóp fyrir sig. Þá verða sumir offramboðskóðablokkir taldir með því að nota alla gagnakubba (í LRC eru þeir kallaðir alþjóðlegir offramboðskóðar), og sumir - með því að nota annan af tveimur hópum gagnakubba (þeir eru kallaðir staðbundnir offramboðskóðar).
LRC er táknað með þremur tölustöfum: nrl, þar sem n er fjöldi gagnablokka, r er fjöldi alþjóðlegra offramboðskóðablokka, l er fjöldi staðbundinna offramboðskóðablokka. Til að lesa gögn þegar einn gagnablokk er ekki tiltækur þarftu að lesa aðeins n/l blokkir - þetta er l sinnum minna en í Reed-Solomon kóða.
Skoðaðu til dæmis LRC 6-2-2 kerfið. X1–X6 — 6 gagnablokkir, P1, P2 — 2 alþjóðlegar offramboðsblokkir, P3, P4 — 2 staðbundnar offramboðsblokkir.
Offramboðskóðablokkir P1, P2 eru taldir með því að nota alla gagnakubba. Offramboðskóðareitur P3 - notar gagnakubba X1-X3, offramboðskóðablokk P4 - notar gagnakubba X4-X6.
Afgangurinn er gerður í LRC á hliðstæðan hátt við Reed-Solomon kóða. Jöfnurnar fyrir talningu orða offramboðskóðablokka verða:
Til að velja tölurnar alfa, beta, gamma, delta þarf að uppfylla fjölda skilyrða til að tryggja möguleika á endurheimt gagna (það er að leysa jöfnukerfið). Þú getur lesið meira um þá í .
Einnig í reynd er XOR aðgerðin notuð til að reikna staðbundna offramboðskóða P3, P4.
Fjöldi ályktana leiðir af jöfnukerfinu fyrir LRC:
- Til að endurheimta 1 gagnablokk er nóg að lesa n/l blokkir (n/2 í dæminu okkar).
- Ef r + l blokkir eru ekki tiltækar og allir blokkir eru með í einum hópi, þá er ekki hægt að endurheimta gögnin. Þetta er auðvelt að útskýra með dæmi. Láttu blokkir X1–X3 og P3 vera ótiltækar: þetta eru r + l blokkir úr sama hópi, 4 í okkar tilviki. Þá höfum við kerfi af 3 jöfnum með 4 óþekktum sem ekki er hægt að leysa.
- Í öllum öðrum tilvikum þar sem r + l blokkir eru ekki tiltækar (þegar að minnsta kosti einn blokkur er tiltækur úr hverjum hópi), er hægt að endurheimta gögnin í LRC.
Þannig er LRC betri en Reed-Solomon kóðar við að endurheimta gögn eftir stakar villur. Í Reed-Solomon kóða, til að endurheimta jafnvel eina blokk af gögnum, þarftu að nota n blokkir, og í LRC, til að endurheimta einn blokk af gögnum, er nóg að nota n/l blokkir (n/2 í okkar dæmi). Aftur á móti er LRC lakari en Reed-Solomon kóðar hvað varðar hámarksfjölda leyfilegra villna. Í dæmunum hér að ofan geta Reed-Solomon kóðar endurheimt gögn fyrir hvaða 4 villur sem er, og fyrir LRC eru 2 samsetningar af 4 villum þegar ekki er hægt að endurheimta gögn.
Það sem er mikilvægara fer eftir sérstökum aðstæðum, en oft vegur sparnaðurinn í umframálagi sem LRC veitir þyngra en aðeins óáreiðanlegri geymslu.
4. Aðrir offramboðskóðar
Fyrir utan Reed-Solomon og LRC kóða eru margir aðrir offramboðskóðar. Mismunandi offramboðskóðar nota mismunandi stærðfræði. Hér eru nokkrir aðrir offramboðskóðar:
- Offramboðskóði með XOR símafyrirtækinu. XOR aðgerðin er framkvæmd á n gagnablokkum og 1 blokk af offramboðskóðum fæst, það er n+1 kerfi (n gagnablokkir, 1 offramboðskóði). Notað í , þar sem gagnablokkir og offramboðskóðar eru skrifaðir í hringrás á alla diska fylkisins.
- Jafnt stakt reiknirit byggt á XOR aðgerðinni. Gerir þér kleift að smíða 2 blokkir af offramboðskóðum, það er n+2 kerfið.
- STAR reiknirit byggt á XOR aðgerðinni. Gerir þér kleift að smíða 3 blokkir af offramboðskóðum, það er n+3 kerfinu.
- Pyramide kóðar eru aðrir offramboðskóðar frá Microsoft.
5. Notaðu í Yandex
Fjöldi Yandex innviðaverkefna notar offramboðskóða fyrir áreiðanlega gagnageymslu. Hér eru nokkur dæmi:
- MDS innri hlutageymsla, sem ég skrifaði um í upphafi greinarinnar.
- — MapReduce kerfi Yandex.
- (Yandex DataBase) - newSQL dreifður gagnagrunnur.
MDS notar LRC offramboðskóða, 8-2-2 kerfi. Gögn með offramboðskóðum eru skrifuð á 12 mismunandi diska á mismunandi netþjónum í 3 mismunandi DC: 4 netþjóna í hverjum DC. Lestu meira um þetta í .
YT notar bæði Reed-Solomon kóða (Skema 6-3), sem voru fyrstir til að innleiða, og LRC offramboðskóða (Scheme 12-2-2), þar sem LRC er ákjósanlegur geymsluaðferð.
YDB notar offramboðskóða sem byggir á jöfnum stakum (mynd 4-2). Um offramboðskóða í YDB nú þegar .
Notkun mismunandi offramboðskóðakerfa stafar af mismunandi kröfum um kerfi. Til dæmis, í MDS, eru gögn sem eru geymd með LRC sett í 3 DC í einu. Það er mikilvægt fyrir okkur að gögnin séu áfram tiltæk til lestrar ef 1 af einhverjum DCs bilar, þess vegna verður að dreifa kubbunum yfir DCs þannig að ef einhver DC er ekki tiltækur er fjöldi óaðgengilegra blokka ekki meira en leyfilegt. Í 8-2-2 kerfinu er hægt að setja 4 blokkir í hvern DC, síðan þegar slökkt er á hvaða DC sem er, verða 4 blokkir ekki tiltækar og hægt er að lesa gögnin. Hvaða kerfi sem við veljum þegar það er sett í 3 DC, ætti í öllum tilvikum að vera (r + l) / n >= 0,5, það er, geymsluofframboð verður að minnsta kosti 50%.
Í YT er ástandið öðruvísi: hver YT klasi er að öllu leyti staðsettur í 1 DC (mismunandi klasar í mismunandi DC), svo það er engin slík takmörkun. 12-2-2 kerfið veitir 33% offramboð, það er að geyma gögn er ódýrara, og það getur líka lifað af allt að 4 samtímis diskleysi, alveg eins og MDS kerfið.
Það eru miklu fleiri eiginleikar við notkun offramboðskóða í gagnageymslu- og vinnslukerfum: blæbrigði gagnabata, áhrif bata á framkvæmdartíma fyrirspurnar, eiginleika gagnaupptöku o.s.frv. Ég ætla að tala sérstaklega um þessa og aðra eiginleika um notkun offramboðskóða í reynd, ef efnið verður áhugavert.
6. Tenglar
- Röð greina um Reed-Solomon kóða og Galois reiti:
Þeir skoða stærðfræði dýpra á aðgengilegu máli. - Grein frá Microsoft um LRC:
Hluti 2 útskýrir kenninguna stuttlega og síðan er fjallað um reynslu af LRC í framkvæmd. - Jafnt stakt kerfi:
- STAR kerfi:
- Pýramídakóðar:
- Offramboðskóðar í MDS:
- Offramboðskóðar í YT:
- Offramboðskóðar í YDB:
Heimild: www.habr.com