Slik ser redundans ut
Redundanskoder* er mye brukt i datasystemer for å øke påliteligheten til datalagring. I Yandex brukes de i mange prosjekter. Hvis du for eksempel bruker redundanskoder i stedet for replikering i den interne objektlagringen vår, sparer du millioner uten å ofre påliteligheten. Men til tross for utbredt bruk, er klare beskrivelser av hvordan redundanskoder fungerer svært sjeldne. De som ønsker å forstå, står overfor omtrent følgende (fra ):
Mitt navn er Vadim, hos Yandex utvikler jeg MDS for intern objektlagring. I denne artikkelen vil jeg i enkle ord beskrive det teoretiske grunnlaget for redundanskoder (Reed-Solomon og LRC-koder). Jeg skal fortelle deg hvordan det fungerer, uten kompleks matematikk og sjeldne termer. Til slutt vil jeg gi eksempler på bruk av redundanskoder i Yandex.
Jeg vil ikke vurdere en rekke matematiske detaljer i detalj, men jeg vil gi lenker for de som ønsker å dykke dypere. Jeg vil også merke meg at noen matematiske definisjoner kanskje ikke er strenge, siden artikkelen ikke er ment for matematikere, men for ingeniører som ønsker å forstå essensen av problemet.
* I engelskspråklig litteratur kalles redundanskoder ofte slettekoder.
1. Essensen av redundanskoder
Essensen av alle redundanskoder er ekstremt enkel: lagre (eller overfør) data slik at de ikke går tapt når feil oppstår (diskfeil, dataoverføringsfeil, etc.).
I de fleste* redundanskoder er dataene delt inn i n datablokker, for hvilke m blokker med redundanskoder telles, noe som resulterer i totalt n + m blokker. Redundanskoder er konstruert på en slik måte at n blokker med data kan gjenopprettes ved å bruke bare en del av n + m blokker. Deretter vil vi kun vurdere blokkredundanskoder, det vil si de der dataene er delt inn i blokker.
For å gjenopprette alle n blokker med data, må du ha minst n av n + m blokker, siden du ikke kan få n blokker ved å ha bare n-1 blokk (i dette tilfellet må du ta 1 blokk "ut av tynne" luft"). Er n tilfeldige blokker med n + m blokker nok til å gjenopprette alle dataene? Dette avhenger av typen redundanskoder, for eksempel lar Reed-Solomon-koder deg gjenopprette alle data ved å bruke vilkårlige n blokker, men LRC-redundanskoder gjør det ikke alltid.
Datalagring
I datalagringssystemer skrives som regel hver av datablokkene og redundanskodeblokkene til en separat disk. Deretter, hvis en vilkårlig disk feiler, kan de opprinnelige dataene fortsatt gjenopprettes og leses. Data kan gjenopprettes selv om flere disker feiler samtidig.
Dataoverføring
Redundanskoder kan brukes til å overføre data pålitelig over et upålitelig nettverk. De overførte dataene er delt inn i blokker, og redundanskoder beregnes for dem. Både datablokker og redundanskodeblokker overføres over nettverket. Hvis det oppstår feil i vilkårlige blokker (opptil et visst antall blokker), kan data fortsatt overføres over nettverket uten feil. Reed-Solomon-koder brukes for eksempel til å overføre data over optiske kommunikasjonslinjer og i satellittkommunikasjon.
* Det finnes også redundanskoder der dataene ikke er delt inn i blokker, som Hamming-koder og CRC-koder, som er mye brukt for dataoverføring i Ethernet-nettverk. Dette er koder for feilkorrigerende koding, de er laget for å oppdage feil, og ikke for å rette dem (Hamming-koden tillater også delvis korrigering av feil).
2. Reed-Solomon-koder
Reed-Solomon-koder er en av de mest brukte redundanskodene, oppfunnet tilbake på 1960-tallet og først mye brukt på 1980-tallet for masseproduksjon av CD-plater.
Det er to nøkkelspørsmål for å forstå Reed-Solomon-koder: 1) hvordan lage blokker med redundanskoder; 2) hvordan gjenopprette data ved hjelp av redundanskodeblokker. La oss finne svar på dem.
For enkelhets skyld vil vi videre anta at n=6 og m=4. Andre ordninger vurderes analogt.
Hvordan lage redundanskodeblokker
Hver blokk med redundanskoder telles uavhengig av de andre. Alle n datablokker brukes til å telle hver blokk. I diagrammet nedenfor er X1-X6 datablokker, P1-P4 er redundanskodeblokker.
Alle datablokker må ha samme størrelse, og null biter kan brukes for justering. De resulterende redundanskodeblokkene vil ha samme størrelse som datablokkene. Alle datablokker er delt inn i ord (for eksempel 16 biter). La oss si at vi deler datablokkene i k ord. Da vil også alle blokker med redundanskoder deles inn i k ord.
For å telle det i-te ordet i hver redundansblokk, vil de i-te ordene til alle datablokkene bli brukt. De vil bli beregnet i henhold til følgende formel:
Her er verdiene x ordene til datablokker, p er ordene til redundanskodeblokker, alle alfa, beta, gamma og delta er spesielt utvalgte tall som er like for alle i. Det må sies med en gang at alle disse verdiene ikke er vanlige tall, men elementer i Galois-feltet; operasjonene +, -, *, / er ikke operasjoner kjent for oss alle, men spesielle operasjoner introdusert på elementer av Galois felt.
Hvorfor trengs Galois-felt?
Det ser ut til at alt er enkelt: vi deler dataene inn i blokker, blokkene i ord, ved å bruke ordene til datablokkene teller vi ordene til redundanskodeblokkene - vi får redundanskodeblokker. Generelt er det slik det fungerer, men djevelen er i detaljene:
- Som nevnt ovenfor er ordstørrelsen fast, i vårt eksempel 16 bits. Formlene ovenfor for Reed-Solomon-koder er slik at når du bruker vanlige heltall, kan det hende at resultatet av å beregne p ikke kan representeres ved å bruke et ord med gyldig størrelse.
- Ved gjenoppretting av data vil formlene ovenfor betraktes som et system av ligninger som må løses for å gjenopprette dataene. Under løsningsprosessen kan det være nødvendig å dele heltall med hverandre, noe som resulterer i et reelt tall som ikke kan representeres nøyaktig i datamaskinens minne.
Disse problemene forhindrer bruk av heltall for Reed-Solomon-koder. Løsningen på problemet er original, den kan beskrives som følger: la oss komme opp med spesielle tall som kan representeres ved hjelp av ord med ønsket lengde (for eksempel 16 biter), og resultatet av å utføre alle operasjoner som (tillegg) , subtraksjon, multiplikasjon, divisjon) vil også bli presentert i datamaskinens minne ved å bruke ord med ønsket lengde.
Slike "spesielle" tall har blitt studert av matematikk i lang tid; de kalles felt. Et felt er et sett med elementer med operasjoner med addisjon, subtraksjon, multiplikasjon og divisjon definert for dem.
Galois*-felt er felt der det er et unikt resultat av hver operasjon (+, -, *, /) for alle to elementer i feltet. Galois-felt kan konstrueres for tall som er potenser av 2: 2, 4, 8, 16 osv. (egentlig potenser av et hvilket som helst primtall p, men i praksis er vi kun interessert i potenser av 2). For eksempel, for 16-bits ord, er dette et felt som inneholder 65 536 elementer, for hvert par kan du finne resultatet av enhver operasjon (+, -, *, /). Verdiene av x, p, alfa, beta, gamma, delta fra ligningene ovenfor vil bli betraktet som elementer i Galois-feltet for beregninger.
Dermed har vi et ligningssystem som vi kan konstruere blokker med redundanskoder med ved å skrive et passende dataprogram. Ved å bruke samme system av ligninger kan du utføre datagjenoppretting.
* Dette er ikke en streng definisjon, men snarere en beskrivelse.
Hvordan gjenopprette data
Restaurering er nødvendig når noen av n + m blokkene mangler. Disse kan være både datablokker og redundanskodeblokker. Fraværet av datablokker og/eller redundanskodeblokker vil bety at de tilsvarende x- og/eller p-variablene er ukjente i ligningene ovenfor.
Ligningene for Reed-Solomon-koder kan sees på som et ligningssystem der alle alfa-, beta-, gamma-, delta-verdier er konstanter, alle x og p som tilsvarer de tilgjengelige blokkene er kjente variabler, og de resterende x og p er ukjente.
La for eksempel datablokkene 1, 2, 3 og redundanskodeblokk 2 være utilgjengelige, så for den i-te gruppen av ord vil det være følgende ligningssystem (ukjente er markert med rødt):
Vi har et system med 4 ligninger med 4 ukjente, noe som betyr at vi kan løse det og gjenopprette dataene!
Fra dette ligningssystemet følger en rekke konklusjoner om datagjenoppretting for Reed-Solomon-koder (n datablokker, m redundanskodeblokker):
- Data kan gjenopprettes hvis noen m blokker eller færre går tapt. Hvis m+1 eller flere blokker går tapt, kan ikke dataene gjenopprettes: det er umulig å løse et system av m likninger med m + 1 ukjente.
- For å gjenopprette enda en datablokk, må du bruke hvilken som helst n av de gjenværende blokkene, og du kan bruke hvilken som helst av redundanskodene.
Hva annet trenger jeg å vite?
I beskrivelsen ovenfor unngår jeg en rekke viktige problemstillinger som krever et dypere dykk i matematikk å vurdere. Spesielt sier jeg ikke noe om følgende:
- Ligningssystemet for Reed-Solomon-koder må ha en (unik) løsning for enhver kombinasjon av ukjente (ikke mer enn m ukjente). Basert på dette kravet velges verdiene for alfa, beta, gamma og delta.
- Et ligningssystem må kunne konstrueres automatisk (avhengig av hvilke blokker som er utilgjengelige) og løses.
- Vi må bygge et Galois-felt: for en gitt ordstørrelse, være i stand til å finne resultatet av enhver operasjon (+, -, *, /) for alle to elementer.
På slutten av artikkelen er det referanser til litteratur om disse viktige spørsmålene.
Valg av n og m
Hvordan velge n og m i praksis? I praksis, i datalagringssystemer, brukes redundanskoder for å spare plass, slik at m alltid velges mindre enn n. Deres spesifikke verdier avhenger av en rekke faktorer, inkludert:
- Pålitelighet av datalagring. Jo større m, jo større antall diskfeil som kan overleves, det vil si jo høyere pålitelighet.
- Redundant lagring. Jo høyere m/n-forhold, jo høyere blir lagringsredundansen, og jo dyrere blir systemet.
- Be om behandlingstid. Jo større sum n + m, jo lengre vil responstiden på forespørsler være. Siden lesing av data (under gjenoppretting) krever lesing av n blokker lagret på n forskjellige disker, vil lesetiden bli bestemt av den tregeste disken.
I tillegg legger lagring av data i flere DC-er ytterligere begrensninger på valg av n og m: hvis 1 DC er slått av, må dataene fortsatt være tilgjengelige for lesing. For eksempel, ved lagring av data i 3 DC-er, må følgende betingelse være oppfylt: m >= n/2, ellers kan det oppstå en situasjon hvor dataene er utilgjengelige for lesing når 1 DC er slått av.
3. LRC - Local Reconstruction Codes
For å gjenopprette data ved hjelp av Reed-Solomon-koder, må du bruke n vilkårlige datablokker. Dette er en veldig betydelig ulempe for distribuerte datalagringssystemer, fordi for å gjenopprette data på en ødelagt disk, må du lese data fra de fleste av de andre, noe som skaper en stor ekstra belastning på diskene og nettverket.
De vanligste feilene er utilgjengelighet av én blokk med data på grunn av feil eller overbelastning av én disk. Er det mulig å på en eller annen måte redusere overflødig belastning for datagjenoppretting i dette (vanligste) tilfellet? Det viser seg at du kan: det er LRC-redundanskoder spesielt for dette formålet.
LRC (Local Reconstruction Codes) er redundanskoder oppfunnet av Microsoft for bruk i Windows Azure Storage. Ideen med LRC er så enkel som mulig: del alle datablokker i to (eller flere) grupper og les deler av redundanskodeblokkene for hver gruppe separat. Deretter vil noen redundanskodeblokker telles ved bruk av alle datablokker (i LRC kalles de globale redundanskoder), og noen - ved å bruke en av to grupper av datablokker (de kalles lokale redundanskoder).
LRC er angitt med tre tall: nrl, hvor n er antall datablokker, r er antall globale redundanskodeblokker, l er antall lokale redundanskodeblokker. For å lese data når én datablokk er utilgjengelig, må du kun lese n/l blokker - dette er l ganger mindre enn i Reed-Solomon-koder.
Vurder for eksempel LRC 6-2-2-ordningen. X1–X6 — 6 datablokker, P1, P2 — 2 globale redundansblokker, P3, P4 — 2 lokale redundansblokker.
Redundanskodeblokker P1, P2 telles ved bruk av alle datablokker. Redundanskodeblokk P3 - ved bruk av datablokker X1-X3, redundanskodeblokk P4 - ved bruk av datablokker X4-X6.
Resten gjøres i LRC i analogi med Reed-Solomon-koder. Ligningene for å telle ordene i redundanskodeblokker vil være:
For å velge tallene alfa, beta, gamma, delta, må en rekke betingelser være oppfylt for å garantere muligheten for datagjenoppretting (det vil si å løse ligningssystemet). Du kan lese mer om dem i .
Også i praksis brukes XOR-operasjonen til å beregne lokale redundanskoder P3, P4.
En rekke konklusjoner følger av ligningssystemet for LRC:
- For å gjenopprette en datablokk er det nok å lese n/l blokker (n/1 i vårt eksempel).
- Hvis r + l-blokker ikke er tilgjengelige, og alle blokker er inkludert i én gruppe, kan ikke dataene gjenopprettes. Dette er enkelt å forklare med et eksempel. La blokkene X1–X3 og P3 være utilgjengelige: dette er r + l blokker fra samme gruppe, 4 i vårt tilfelle. Da har vi et system med 3 likninger med 4 ukjente som ikke kan løses.
- I alle andre tilfeller av utilgjengelighet av r + l blokker (når minst én blokk er tilgjengelig fra hver gruppe), kan dataene i LRC gjenopprettes.
Dermed overgår LRC Reed-Solomon-koder når det gjelder å gjenopprette data etter enkeltfeil. I Reed-Solomon-koder, for å gjenopprette enda en blokk med data, må du bruke n blokker, og i LRC, for å gjenopprette en blokk med data, er det nok å bruke n/l blokker (n/2 i vårt eksempel). På den annen side er LRC dårligere enn Reed-Solomon-koder når det gjelder maksimalt antall tillatte feil. I eksemplene ovenfor kan Reed-Solomon-koder gjenopprette data for 4 feil, og for LRC er det 2 kombinasjoner av 4 feil når data ikke kan gjenopprettes.
Hva som er viktigere avhenger av den spesifikke situasjonen, men ofte oppveier besparelsene i overbelastning som LRC gir den litt mindre pålitelige lagringen.
4. Andre redundanskoder
Foruten Reed-Solomon og LRC-koder, er det mange andre redundanskoder. Ulike redundanskoder bruker forskjellig matematikk. Her er noen andre redundanskoder:
- Redundanskode ved hjelp av XOR-operatøren. XOR-operasjonen utføres på n datablokker, og 1 blokk med redundanskoder oppnås, det vil si et n+1-skjema (n datablokker, 1 redundanskode). Brukt i , der blokker med data og redundanskoder skrives syklisk til alle diskene i arrayet.
- Even-odd-algoritme basert på XOR-operasjonen. Lar deg bygge 2 blokker med redundanskoder, det vil si n+2-skjemaet.
- STAR-algoritme basert på XOR-operasjonen. Lar deg bygge 3 blokker med redundanskoder, det vil si n+3-skjemaet.
- Pyramidkoder er en annen redundanskode fra Microsoft.
5. Bruk i Yandex
En rekke Yandex-infrastrukturprosjekter bruker redundanskoder for pålitelig datalagring. Her er noen eksempler:
- MDS intern objektlagring, som jeg skrev om i begynnelsen av artikkelen.
- — MapReduce-systemet til Yandex.
- (Yandex DataBase) - newSQL distribuert database.
MDS bruker LRC redundanskoder, 8-2-2-skjema. Data med redundanskoder skrives til 12 forskjellige disker på forskjellige servere i 3 forskjellige DC-er: 4 servere i hver DC. Les mer om dette i .
YT bruker både Reed-Solomon-koder (skjema 6-3), som var de første som implementerte, og LRC-redundanskoder (skjema 12-2-2), med LRC som den foretrukne lagringsmetoden.
YDB bruker oddetallsbaserte redundanskoder (Figur 4-2). Om redundanskoder i YDB allerede .
Bruken av ulike redundanskodeordninger skyldes ulike krav til systemer. For eksempel, i MDS, blir data lagret ved hjelp av LRC plassert i 3 DC-er samtidig. Det er viktig for oss at dataene forblir tilgjengelige for lesing hvis 1 av noen DC-er svikter, derfor må blokkene fordeles over DC-ene slik at hvis noen DC er utilgjengelig, er antallet utilgjengelige blokker ikke mer enn tillatt. I 8-2-2-skjemaet kan du plassere 4 blokker i hver DC, så når en DC er slått av, vil 4 blokker være utilgjengelige, og dataene kan leses. Uansett hvilken ordning vi velger når vi plasserer den i 3 DC-er, bør det i alle fall være (r + l) / n >= 0,5, det vil si at lagringsredundansen vil være minst 50%.
I YT er situasjonen forskjellig: hver YT-klynge er helt lokalisert i 1 DC (forskjellige klynger i forskjellige DC-er), så det er ingen slik begrensning. 12-2-2-ordningen gir 33 % redundans, det vil si at lagring av data er billigere, og den kan også overleve opptil 4 samtidige diskbrudd, akkurat som MDS-ordningen.
Det er mange flere funksjoner ved bruk av redundanskoder i datalagrings- og prosesseringssystemer: nyanser av datagjenoppretting, innvirkningen av gjenoppretting på utføringstid for spørringer, funksjoner ved dataregistrering, etc. Jeg skal snakke separat om disse og andre funksjoner av bruken av redundanskoder i praksis, dersom temaet vil være interessant.
6. Lenker
- En serie artikler om Reed-Solomon-koder og Galois-felt:
De tar en dypere titt på matematikk i et tilgjengelig språk. - Artikkel fra Microsoft om LRC:
Del 2 forklarer kort teorien og diskuterer deretter erfaringer med LRC i praksis. - Even-odde-opplegg:
- STAR-skjema:
- Pyramidekoder:
- Redundanskoder i MDS:
- Redundanskoder i YT:
- Redundanskoder i YDB:
Kilde: www.habr.com