Slik ser redundans ut

Redundanskoder* brukes mye i datasystemer for å øke påliteligheten til datalagring. Hos Yandex brukes de i mange prosjekter. For eksempel sparer bruk av redundanskoder i stedet for replikering i vår interne objektlagring millioner uten at det går på bekostning av påliteligheten. Men til tross for deres utbredte bruk, er en klar beskrivelse av hvordan redundanskoder fungerer svært sjelden. De som ønsker å forstå dem, står overfor noe som ligner på følgende (fra Wikipedia):

Mitt navn er Vadim, og jeg utvikler Yandex sin interne MDS-objektlagring. I denne artikkelen vil jeg beskrive de teoretiske grunnlagene for redundansekoder (Reed-Solomon- og LRC-koder) på en enkel måte. Jeg vil forklare hvordan de fungerer, uten kompleks matematikk eller uvanlig sjargong. Til slutt vil jeg gi eksempler på hvordan redundansekoder brukes hos Yandex.

Jeg vil ikke gå i detalj om noen av de matematiske detaljene, men jeg vil gi lenker for de som ønsker å gå dypere inn i saken. Jeg vil også bemerke at noen av de matematiske definisjonene kan være vage, ettersom denne artikkelen er ment for ingeniører, ikke matematikere, som ønsker å forstå de underliggende konseptene.

* I engelskspråklig litteratur kalles redundanskoder ofte slettekoder.

1. Essensen av redundansekoder

Essensen i all redundanskode er ekstremt enkel: å lagre (eller overføre) data slik at de ikke går tapt når det oppstår feil (diskfeil, dataoverføringsfeil osv.).

I de fleste* redundanskoder er data delt inn i n datablokker, hvor m redundanskodeblokker vurderes, for totalt n + m blokker. Redundanskoder er konstruert på en slik måte at n datablokker kan rekonstrueres ved å bruke bare en del av de n + m blokkene. I det følgende vil vi bare vurdere blokkredundanskoder, det vil si de der data er delt inn i blokker.

For å gjenopprette alle n datablokker trenger du minst n av n + m blokker, siden du ikke kan få n blokker fra bare n - 1 blokk (i så fall må du plukke én blokk "ut av løse luften"). Er n vilkårlige blokker fra n + m blokker tilstrekkelige til å gjenopprette alle dataene? Dette avhenger av typen redundanskoder. For eksempel lar Reed-Solomon-koder deg gjenopprette alle dataene ved hjelp av vilkårlige n blokker, mens LRC-redundanskoder ikke alltid gjør dette.

Datalagring

I datalagringssystemer skrives vanligvis hver datablokk og redundanskodeblokk til en separat disk. Dette sikrer at hvis en disk svikter, kan de opprinnelige dataene fortsatt gjenopprettes og leses. Data kan gjenopprettes selv om flere disker svikter samtidig.

Dataoverføring

Redundanskoder kan brukes til å overføre data pålitelig over et upålitelig nettverk. De overførte dataene deles inn i blokker, og redundanskoder beregnes for disse blokkene. Både datablokkene og redundanskodeblokkene overføres over nettverket. Selv om det oppstår feil i vilkårlige blokker (opptil et visst antall blokker), kan dataene fortsatt overføres feilfritt over nettverket. Reed-Solomon-koder brukes for eksempel til å overføre data over optiske kommunikasjonslinjer og i satellittkommunikasjon.

* Det finnes også redundansekoder som ikke deler data inn i blokker, for eksempel Hamming-koder og CRC-koder, som er mye brukt for dataoverføring i Ethernet-nettverk. Disse kodene er feilrettingskoder som er utformet for å oppdage feil i stedet for å korrigere dem (Hamming-koder tillater også delvis feilretting).

2. Reed-Solomon-koder

Reed-Solomon-koder er en av de mest brukte redundanskodene, oppfunnet på 1960-tallet og først mye brukt på 1980-tallet for masseproduksjon av kompakte plater.

Det er to viktige spørsmål for å forstå Reed-Solomon-koder: 1) hvordan lage redundanskodeblokker; 2) hvordan gjenopprette data ved hjelp av redundanskodeblokker. La oss finne svarene.
For enkelhets skyld antar vi at n=6 og m=4. Andre skjemaer vurderes analogt.

Slik lager du redundanskodeblokker

Hver redundanskodeblokk beregnes uavhengig av de andre. Alle n datablokker brukes til å beregne hver blokk. I diagrammet nedenfor er X1–X6 datablokker, og P1–P4 er redundanskodeblokker.

Alle datablokker må ha samme størrelse; null bits kan brukes til justering. De resulterende redundanskodeblokkene vil ha samme størrelse som datablokkene. Alle datablokker er delt inn i ord (f.eks. 16 bits hver). Anta at vi deler datablokkene inn i k ord. Da vil alle redundanskodeblokker også bli delt inn i k ord.

For å beregne det i-te ordet i hver redundansblokk, vil det i-te ordet i alle datablokkene bli brukt. De vil bli beregnet ved hjelp av følgende formel:

Her er x-verdiene ordene i datablokkene, p er ordene i redundanskodeblokkene, og alle alfa-, beta-, gamma- og delta-verdiene er spesielt utvalgte tall som er like for alle i-er. Det bør bemerkes med en gang at alle disse verdiene ikke er vanlige tall, men elementer i et Galois-felt. Operasjonene +, -, *, / er ikke operasjonene vi alle er kjent med, men spesielle operasjoner introdusert på elementer i et Galois-felt.

Hvorfor trengs Galois-felt?

Det virker enkelt: vi deler dataene inn i blokker, blokkene inn i ord, og bruker deretter ordene i datablokkene til å beregne ordene i redundanskodeblokkene, noe som resulterer i redundanskodeblokker. Det er slik det fungerer, men djevelen ligger i detaljene:

Som nevnt ovenfor er ordstørrelsen fast, 16 bit i vårt eksempel. Formlene ovenfor for Reed-Solomon-koder er slik at når man bruker vanlige heltall, kan resultatet av beregning av p kanskje ikke representeres med et ord av akseptabel størrelse.
Ved gjenoppretting av data vil formlene ovenfor bli behandlet 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 hindrer bruk av heltall for Reed-Solomon-koder. Løsningen på dette problemet er genial og kan beskrives som følger: la oss finne opp spesielle tall som kan representeres ved hjelp av ord med ønsket lengde (for eksempel 16 bit), og resultatene av alle operasjoner på disse tallene (addisjon, subtraksjon, multiplikasjon, divisjon) vil også bli representert i datamaskinens minne ved hjelp av ord med ønsket lengde.

Slike «spesielle» tall har lenge blitt studert av matematikere; de kalles felt. Et felt er et sett med elementer med spesifikke operasjoner for addisjon, subtraksjon, multiplikasjon og divisjon.

Galois-felt* er felt der resultatet av hver operasjon (+, -, *, /) for to elementer i feltet eksisterer og er unikt. Galois-felt kan konstrueres for tall som er potenser av 2: 2, 4, 8, 16 og så videre (faktisk potenser av et hvilket som helst primtall p, men i praksis er vi bare interessert i potenser av 2). For eksempel, for 16-bits ord er dette et felt som inneholder 65 536 elementer, der resultatet av en hvilken som helst operasjon (+, -, *, /) kan finnes for hvert par. Verdiene x, p, alfa, beta, gamma og delta fra ligningene ovenfor vil bli betraktet som elementer i Galois-feltet for beregninger.

Dermed har vi et ligningssystem som kan brukes til å konstruere redundanskodeblokker ved å skrive et tilsvarende dataprogram. Det samme ligningsystemet kan også brukes til å utføre datagjenoppretting.

*Dette er ikke en streng definisjon, men snarere en beskrivelse.

Slik gjenoppretter du data

Gjenoppretting er nødvendig når noen av n + m-blokkene mangler. Disse kan enten være datablokker eller redundanskodeblokker. Manglende datablokker og/eller redundanskodeblokker vil bety at de tilsvarende variablene x og/eller p i ligningene ovenfor er ukjente.

Ligningene for Reed-Solomon-koder kan sees på som et system av ligninger der alle alfa-, beta-, gamma- og delta-verdier er konstanter, alle x og p som tilsvarer de tilgjengelige blokkene er kjente variabler, og de resterende x og p er ukjente.

Hvis for eksempel datablokkene 1, 2, 3 og redundanskodeblokk 2 ikke er tilgjengelige, vil det for den i-te gruppen av ord være følgende ligningssystem (ukjente er markert med rødt):

Vi har et system med 4 ligninger med 4 ukjente, 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 m eller færre blokker går tapt. Hvis m+1 eller flere blokker går tapt, kan ikke data gjenopprettes: et system av m ligninger med m+1 ukjente kan ikke løses.
For å gjenopprette bare én datablokk, må hvilken som helst n av de gjenværende blokkene brukes, og hvilken som helst av redundanskodene kan brukes.

Hva annet trenger jeg å vite?

I beskrivelsen ovenfor har jeg ignorert en rekke viktige problemstillinger som krever et dypere dykk i matematikk. Spesielt har jeg ikke diskutert følgende:

Ligningssystemet for Reed-Solomon-koder må ha en unik løsning for enhver kombinasjon av ukjente (ikke mer enn m ukjente). Verdiene for alfa, beta, gamma og delta velges basert på dette kravet.
Det er nødvendig å kunne konstruere et ligningssystem automatisk (avhengig av hvilke blokker som er utilgjengelige) og løse det.
Vi må konstruere et Galois-felt: for en gitt ordstørrelse må vi kunne finne resultatet av en hvilken som helst operasjon (+, -, *, /) for to elementer.

På slutten av artikkelen finner du lenker til litteratur om disse viktige problemstillingene.

Valg av n og m

Hvordan velger man n og m i praksis? I datalagringssystemer brukes redundanskoder for å spare plass, så m velges alltid til å være mindre enn n. De spesifikke verdiene deres avhenger av en rekke faktorer, inkludert:

Pålitelighet av datalagring. Jo større m, desto flere diskfeil kan tolereres, noe som betyr høyere pålitelighet.
Lagringsredundans. Jo høyere m/n-forhold, desto større lagringsredundans og desto dyrere er systemet.
Behandlingstid for spørringen. Jo større summen av n + m er, desto lengre er responstiden for spørringen. Siden lesing av data (under gjenoppretting) krever lesing av n blokker lagret på n forskjellige disker, vil lesetiden bli bestemt av den tregeste disken.

Videre medfører lagring av data på tvers av flere datasentre ytterligere begrensninger for valget av n og m: hvis ett datasenter er frakoblet, må dataene fortsatt være lesbare. For eksempel, når data lagres på tvers av tre datasentre, må betingelsen m >= n/2 være oppfylt; ellers kan dataene bli uleselige hvis ett datasenter er frakoblet.

3. LRC - Lokale rekonstruksjonsforskrifter

Gjenoppretting av data ved hjelp av Reed-Solomon-koder krever bruk av n tilfeldige datablokker. Dette er en betydelig ulempe for distribuerte lagringssystemer, ettersom gjenoppretting av data fra én defekt disk krever lesing av data fra de fleste av de andre, noe som skaper en betydelig ekstra belastning på diskene og nettverket.

Den vanligste feilen er utilgjengeligheten til en enkelt datablokk på grunn av en defekt eller overbelastet disk. Er det mulig å redusere den overskytende belastningen på datagjenoppretting i dette (vanligste) tilfellet? Det viser seg at det er det: LRC-redundanskoder finnes spesifikt for dette formålet.

LRC (Local Reconstruction Codes) er redundansekoder utviklet av Microsoft for bruk i Windows Azure Storage. Ideen bak LRC er veldig enkel: del alle datablokkene inn i to (eller flere) grupper og beregn en del av redundanskodeblokkene for hver gruppe separat. Deretter vil noen av redundanskodeblokkene bli beregnet ved hjelp av alle datablokkene (i LRC kalles disse globale redundanskoder), og noen vil bli beregnet ved hjelp av en av de to gruppene med datablokker (disse kalles lokale redundanskoder).

LRC er betegnet med tre tall: nrl, hvor n er antall datablokker, r er antall globale redundanskodeblokker og l er antall lokale redundanskodeblokker. For å lese data når én datablokk ikke er tilgjengelig, trenger bare n/l blokker å leses – dette er l ganger færre enn i Reed-Solomon-koder.

Som et eksempel, la oss se på LRC 6-2-2-skjemaet. X1–X6 er 6 datablokker, P1, P2 er 2 globale redundansblokker, P3, P4 er 2 lokale redundansblokker.

Redundanskodeblokkene P1 og P2 beregnes ved hjelp av alle datablokkene. Redundanskodeblokk P3 beregnes ved hjelp av datablokkene X1–X3, og redundanskodeblokk P4 beregnes ved hjelp av datablokkene X4–X6.

Resten av arbeidet i LRC gjøres på samme måte som i Reed-Solomon-koder. Ligningene for å telle ordene i redundanskodeblokker er som følger:

For å velge alfa-, beta-, gamma- og delta-tallene må en rekke betingelser oppfylles for å sikre muligheten for datagjenoppretting (dvs. løsning av ligningssystemet). Du kan lese mer om dem i artikkel.
I praksis brukes også XOR-operasjonen til å beregne lokale redundanskoder P3, P4.

En rekke konklusjoner følger av ligningssystemet for LRC:

For å gjenopprette én datablokk er det nok å lese n/l blokker (n/2 i vårt eksempel).
Hvis r + l-blokker ikke er tilgjengelige, og alle blokkene er i samme gruppe, kan ikke dataene gjenopprettes. Dette kan enkelt forklares med et eksempel. La oss si at blokkene X1–X3 og P3 ikke er tilgjengelige: dette er r + l-blokker fra samme gruppe, 4 i vårt tilfelle. Da har vi et system med 3 ligninger med 4 ukjente som ikke kan løses.
I alle andre tilfeller der r + l-blokker ikke er tilgjengelige (når minst én blokk fra hver gruppe er tilgjengelig), kan dataene i LRC gjenopprettes.

Dermed overgår LRC Reed-Solomon-koder i datagjenoppretting etter enkeltfeil. Reed-Solomon-koder krever n blokker for å gjenopprette selv én datablokk, mens LRC krever n/l blokker (n/2 i vårt eksempel) for å gjenopprette én datablokk. 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 med fire feil, mens det for LRC er to kombinasjoner av fire feil som ikke kan gjenopprettes for.

Om dette er viktigere avhenger av den spesifikke situasjonen, men ofte oppveier besparelsene i driftskostnader som LRC gir den litt lavere lagringspåliteligheten.

4. Andre redundansekoder

Foruten Reed-Solomon- og LRC-koder finnes det mange andre redundanskoder. Ulike redundanskoder bruker ulik matematikk. Her er noen andre redundanskoder:

Redundanskode ved bruk av XOR-operatoren. XOR-operasjonen utføres på n datablokker, noe som resulterer i 1 blokk med redundanskoder, dvs. skjemaet n+1 (n datablokker, 1 redundanskode). Den brukes i RAID 5, der datablokker og redundanskoder skrives syklisk til alle disker i arrayet.
En like-oddetallsalgoritme basert på XOR-operasjonen. Den tillater konstruksjon av to blokker med redundanskoder, dvs. et n+2-skjema.
STAR-algoritmen, basert på XOR-operasjonen, tillater konstruksjon av tre redundanskodeblokker, dvs. et n+3-skjema.
Pyramide-koder er en annen redundanskode fra Microsoft.

5. Bruk i Yandex

En rekke Yandex-infrastrukturprosjekter bruker redundansekoder for sikker datalagring. Her er noen eksempler:

Den interne MDS-objektlagringen som jeg skrev om i begynnelsen av artikkelen.
YT — Yandex MapReduce-systemet.
YDB (Yandex DataBase) er en distribuert newSQL-database.

MDS bruker LRC-redundanskoder, et 8-2-2-skjema. Data med redundanskoder skrives til 12 forskjellige disker på forskjellige servere i tre forskjellige datasentre: fire servere i hvert datasenter. Les mer om dette i artikkel.

YT bruker både Reed-Solomon-koder (6-3-skjema), som var de første som ble implementert, og LRC-redundanskoder (12-2-2-skjema), med LRC som den foretrukne lagringsmetoden.

YDB bruker redundanskoder basert på like-oddetall (figur 4-2). Redundanskoder i YDB har allerede blitt diskutert. fortalt på Highload.

Bruken av forskjellige redundanskodeordninger dikteres av forskjellige systemkrav. I MDS plasseres for eksempel data lagret ved hjelp av LRC på tvers av tre datasentre. Det er viktig at dataene forblir tilgjengelige selv om et datasenter svikter, så blokker må fordeles på tvers av datasentrene, slik at hvis et datasenter er utilgjengelig, overstiger ikke antallet utilgjengelige blokker den tillatte grensen. I 8-2-2-ordningen kan fire blokker plasseres i hvert datasenter. Hvis et datasenter svikter, vil fire blokker være utilgjengelige, og dataene vil fortsatt være tilgjengelige. Uansett hvilken ordning som velges for plassering på tvers av tre datasentre, kreves (r + l) / n >= 0,5, noe som betyr at lagringsredundansen vil være minst 50 %.

Situasjonen er annerledes i YT: hver YT-klynge er fullstendig plassert i ett enkelt datasenter (forskjellige klynger i forskjellige datasentre), så det finnes ingen slik begrensning. 12-2-2-designet gir 33 % redundans, noe som betyr at datalagring er billigere, og det kan også overleve opptil fire samtidige diskavbrudd, akkurat som MDS-designet.

Det er mange andre spesifikke aspekter ved bruk av redundansekoder i datalagrings- og behandlingssystemer: nyansene ved datagjenoppretting, virkningen av gjenoppretting på utførelsestid for spørringer, detaljene ved dataregistrering, osv. Jeg planlegger å diskutere disse og andre aspekter ved bruk av redundansekoder i praksis separat, hvis emnet er av interesse.