Sådan ser redundans ud
Redundanskoder* bruges i vid udstrækning i computersystemer for at øge pålideligheden af datalagring. I Yandex bruges de i mange projekter. Brug af redundanskoder i stedet for replikering i vores interne objektlager sparer for eksempel millioner uden at ofre pålideligheden. Men på trods af deres udbredte brug, er klare beskrivelser af, hvordan redundanskoder fungerer, meget sjældne. De, der ønsker at forstå, står over for omtrent følgende (fra ):
Mit navn er Vadim, hos Yandex er jeg ved at udvikle MDS til intern objektlagring. I denne artikel vil jeg i enkle ord beskrive det teoretiske grundlag for redundanskoder (Reed-Solomon og LRC-koder). Jeg vil fortælle dig, hvordan det fungerer, uden kompleks matematik og sjældne udtryk. Til sidst vil jeg give eksempler på brug af redundanskoder i Yandex.
Jeg vil ikke overveje en række matematiske detaljer i detaljer, men jeg vil give links til dem, der ønsker at dykke dybere. Jeg vil også bemærke, at nogle matematiske definitioner måske ikke er strenge, da artiklen ikke er beregnet til matematikere, men til ingeniører, der ønsker at forstå essensen af problemet.
* I engelsksproget litteratur kaldes redundanskoder ofte for slettekoder.
1. Essensen af redundanskoder
Essensen af alle redundanskoder er ekstremt enkel: Gem (eller overfør) data, så de ikke går tabt, når der opstår fejl (diskfejl, dataoverførselsfejl osv.).
I de fleste* redundanskoder er dataene opdelt i n datablokke, for hvilke der tælles m blokke af redundanskoder, hvilket resulterer i i alt n + m blokke. Redundanskoder er konstrueret på en sådan måde, at n blokke af data kan gendannes ved kun at bruge en del af n + m blokke. Dernæst vil vi kun overveje blokredundanskoder, det vil sige dem, hvor dataene er opdelt i blokke.
For at gendanne alle n blokke af data skal du have mindst n af n + m blokke, da du ikke kan få n blokke ved kun at have n-1 blok (i dette tilfælde skal du tage 1 blok "ud af tynde" luft"). Er n tilfældige blokke af n + m blokke nok til at gendanne alle data? Dette afhænger af typen af redundanskoder, for eksempel giver Reed-Solomon-koder dig mulighed for at gendanne alle data ved hjælp af vilkårlige n blokke, men LRC-redundanskoder gør det ikke altid.
Data opbevaring
I datalagringssystemer bliver hver af datablokkene og redundanskodeblokkene som regel skrevet til en separat disk. Så, hvis en vilkårlig disk fejler, kan de originale data stadig gendannes og læses. Data kan gendannes, selvom flere diske fejler på samme tid.
Dataoverførsel
Redundanskoder kan bruges til pålideligt at overføre data over et upålideligt netværk. De transmitterede data er opdelt i blokke, og redundanskoder beregnes for dem. Både datablokke og redundanskodeblokke transmitteres over netværket. Hvis der opstår fejl i vilkårlige blokke (op til et vist antal blokke), kan data stadig sendes over netværket uden fejl. Reed-Solomon-koder bruges for eksempel til at transmittere data over optiske kommunikationslinjer og i satellitkommunikation.
* Der er også redundanskoder, hvor dataene ikke er opdelt i blokke, såsom Hamming-koder og CRC-koder, som er meget brugt til datatransmission i Ethernet-netværk. Dette er koder til fejlkorrigerende kodning, de er designet til at opdage fejl og ikke til at rette dem (Hamming-koden tillader også delvis korrektion af fejl).
2. Reed-Solomon-koder
Reed-Solomon-koder er en af de mest udbredte redundanskoder, opfundet tilbage i 1960'erne og først meget brugt i 1980'erne til masseproduktion af cd'er.
Der er to nøglespørgsmål for at forstå Reed-Solomon-koder: 1) hvordan man opretter blokke af redundanskoder; 2) hvordan man gendanner data ved hjælp af redundanskodeblokke. Lad os finde svar på dem.
For nemheds skyld vil vi yderligere antage, at n=6 og m=4. Andre ordninger betragtes analogt.
Sådan opretter du redundanskodeblokke
Hver blok af redundanskoder tælles uafhængigt af de andre. Alle n datablokke bruges til at tælle hver blok. I diagrammet nedenfor er X1-X6 datablokke, P1-P4 er redundanskodeblokke.
Alle datablokke skal have samme størrelse, og nul bit kan bruges til justering. De resulterende redundanskodeblokke vil have samme størrelse som datablokkene. Alle datablokke er opdelt i ord (for eksempel 16 bit). Lad os sige, at vi deler datablokkene op i k ord. Så vil alle blokke af redundanskoder også blive opdelt i k ord.
For at tælle det i'te ord i hver redundansblok, vil de i'te ord i alle datablokke blive brugt. De vil blive beregnet efter følgende formel:
Her er værdierne x ordene fra datablokke, p er ordene fra redundanskodeblokke, alle alfa, beta, gamma og delta er specielt udvalgte tal, der er ens for alle i. Det skal siges med det samme, at alle disse værdier ikke er almindelige tal, men elementer af Galois-feltet; operationerne +, -, *, / er ikke operationer, vi alle kender, men specielle operationer introduceret på elementer af Galois Mark.
Hvorfor er der brug for Galois-felter?
Det ser ud til, at alt er enkelt: vi opdeler dataene i blokke, blokkene i ord, ved at bruge ordene fra datablokkene tæller vi ordene fra redundanskodeblokkene - vi får redundanskodeblokke. Generelt er det sådan, det fungerer, men djævelen er i detaljerne:
- Som nævnt ovenfor er ordstørrelsen fast, i vores eksempel 16 bit. Formlerne ovenfor for Reed-Solomon-koder er sådan, at når du bruger almindelige heltal, kan resultatet af beregningen af p muligvis ikke repræsenteres ved brug af et ord af gyldig størrelse.
- Ved gendannelse af data vil formlerne ovenfor blive betragtet som et system af ligninger, der skal løses for at genskabe dataene. Under løsningsprocessen kan det være nødvendigt at dividere heltal med hinanden, hvilket resulterer i et reelt tal, der ikke kan repræsenteres nøjagtigt i computerens hukommelse.
Disse problemer forhindrer brugen af heltal til Reed-Solomon-koder. Løsningen på problemet er original, det kan beskrives som følger: lad os komme med specielle tal, der kan repræsenteres ved hjælp af ord med den nødvendige længde (for eksempel 16 bit), og resultatet af at udføre alle operationer, som (tilføjelse) , subtraktion, multiplikation, division) vil også blive præsenteret i computerens hukommelse ved hjælp af ord af den nødvendige længde.
Sådanne "særlige" tal er blevet studeret af matematik i lang tid; de kaldes felter. Et felt er et sæt af elementer med operationer med addition, subtraktion, multiplikation og division defineret for dem.
Galois*-felter er felter, for hvilke der er et unikt resultat af hver operation (+, -, *, /) for alle to elementer i feltet. Galois-felter kan konstrueres for tal, der er potenser af 2: 2, 4, 8, 16 osv. (faktisk potenser af ethvert primtal p, men i praksis er vi kun interesserede i potenser af 2). For eksempel, for 16-bit ord er dette et felt, der indeholder 65 elementer, for hvert par af hvilke du kan finde resultatet af enhver operation (+, -, *, /). Værdierne af x, p, alfa, beta, gamma, delta fra ligningerne ovenfor vil blive betragtet som elementer i Galois-feltet til beregninger.
Vi har således et ligningssystem, hvormed vi kan konstruere blokke af redundanskoder ved at skrive et passende computerprogram. Ved at bruge det samme system af ligninger, kan du udføre datagendannelse.
* Dette er ikke en streng definition, men snarere en beskrivelse.
Sådan gendannes data
Restaurering er nødvendig, når nogle af n + m blokkene mangler. Disse kan både være datablokke og redundanskodeblokke. Fraværet af datablokke og/eller redundanskodeblokke vil betyde, at de tilsvarende x- og/eller p-variable er ukendte i ligningerne ovenfor.
Ligningerne for Reed-Solomon-koder kan ses som et ligningssystem, hvor alle alfa-, beta-, gamma-, delta-værdier er konstanter, alle x og p svarende til de tilgængelige blokke er kendte variable, og de resterende x og p er ukendte.
Lad for eksempel datablokke 1, 2, 3 og redundanskodeblok 2 være utilgængelige, så vil der for den i-te gruppe af ord være følgende ligningssystem (ukendte er markeret med rødt):
Vi har et system med 4 ligninger med 4 ubekendte, hvilket betyder at vi kan løse det og gendanne dataene!
Fra dette ligningssystem følger en række konklusioner om datagendannelse for Reed-Solomon-koder (n datablokke, m redundanskodeblokke):
- Data kan gendannes, hvis nogen m blokke eller færre går tabt. Hvis m+1 eller flere blokke går tabt, kan dataene ikke gendannes: det er umuligt at løse et system af m ligninger med m + 1 ukendte.
- For at gendanne blot én datablok, skal du bruge et hvilket som helst n af de resterende blokke, og du kan bruge enhver af redundanskoderne.
Hvad skal jeg vide mere?
I beskrivelsen ovenfor undgår jeg en række vigtige spørgsmål, som kræver et dybere dyk ned i matematik at overveje. Specielt siger jeg ikke noget om følgende:
- Ligningssystemet for Reed-Solomon-koder skal have en (unik) løsning for enhver kombination af ukendte (ikke mere end m ukendte). Baseret på dette krav vælges værdierne for alfa, beta, gamma og delta.
- Et ligningssystem skal kunne konstrueres automatisk (afhængig af hvilke blokke der ikke er tilgængelige) og løses.
- Vi skal bygge et Galois-felt: for en given ordstørrelse skal du være i stand til at finde resultatet af enhver operation (+, -, *, /) for alle to elementer.
Sidst i artiklen er der henvisninger til litteratur om disse vigtige spørgsmål.
Valg af n og m
Hvordan vælger man n og m i praksis? I praksis bruges redundanskoder i datalagringssystemer for at spare plads, så m vælges altid mindre end n. Deres specifikke værdier afhænger af en række faktorer, herunder:
- Pålidelighed af datalagring. Jo større m, jo større er antallet af diskfejl, der kan overleves, det vil sige, jo højere pålidelighed.
- Redundant opbevaring. Jo højere m/n-forholdet er, desto højere bliver lagerredundansen, og jo dyrere bliver systemet.
- Anmod om behandlingstid. Jo større summen n + m, jo længere vil responstiden på anmodninger være. Da læsning af data (under gendannelse) kræver læsning af n blokke gemt på n forskellige diske, vil læsetiden blive bestemt af den langsomste disk.
Derudover pålægger lagring af data i flere DC'er yderligere begrænsninger for valget af n og m: Hvis 1 DC er slået fra, skal dataene stadig være tilgængelige for læsning. Ved f.eks. lagring af data i 3 DC'er skal følgende betingelse være opfyldt: m >= n/2, ellers kan der opstå en situation, hvor dataene ikke er tilgængelige til aflæsning, når 1 DC er slukket.
3. LRC - Local Reconstruction Codes
For at gendanne data ved hjælp af Reed-Solomon-koder, skal du bruge n vilkårlige datablokke. Dette er en meget betydelig ulempe for distribuerede datalagringssystemer, fordi for at gendanne data på en ødelagt disk skal du læse data fra de fleste af de andre, hvilket skaber en stor ekstra belastning på diskene og netværket.
De mest almindelige fejl er utilgængeligheden af en blok af data på grund af en fejl eller overbelastning af en disk. Er det muligt på en eller anden måde at reducere den overskydende belastning for datagendannelse i dette (mest almindelige) tilfælde? Det viser sig, at du kan: Der er LRC-redundanskoder specifikt til dette formål.
LRC (Local Reconstruction Codes) er redundanskoder opfundet af Microsoft til brug i Windows Azure Storage. Ideen med LRC er så enkel som muligt: opdel alle datablokke i to (eller flere) grupper og læs en del af redundanskodeblokkene for hver gruppe separat. Så vil nogle redundanskodeblokke blive talt ved hjælp af alle datablokke (i LRC kaldes de globale redundanskoder), og nogle - ved at bruge en af to grupper af datablokke (de kaldes lokale redundanskoder).
LRC er angivet med tre tal: nrl, hvor n er antallet af datablokke, r er antallet af globale redundanskodeblokke, l er antallet af lokale redundanskodeblokke. For at læse data, når en datablok ikke er tilgængelig, skal du kun læse n/l blokke - dette er l gange mindre end i Reed-Solomon-koder.
Overvej for eksempel LRC 6-2-2-ordningen. X1–X6 — 6 datablokke, P1, P2 — 2 globale redundansblokke, P3, P4 — 2 lokale redundansblokke.
Redundanskodeblokke P1, P2 tælles ved brug af alle datablokke. Redundanskodeblok P3 - ved hjælp af datablokke X1-X3, redundanskodeblok P4 - ved hjælp af datablokke X4-X6.
Resten udføres i LRC i analogi med Reed-Solomon-koder. Ligningerne for at tælle ordene i redundanskodeblokke vil være:
For at vælge tallene alfa, beta, gamma, delta skal en række betingelser være opfyldt for at garantere muligheden for datagendannelse (det vil sige løsning af ligningssystemet). Du kan læse mere om dem i .
Også i praksis bruges XOR-operationen til at beregne lokale redundanskoder P3, P4.
En række konklusioner følger af ligningssystemet for LRC:
- For at gendanne 1 datablok er det nok at læse n/l blokke (n/2 i vores eksempel).
- Hvis r + l blokke ikke er tilgængelige, og alle blokke er inkluderet i én gruppe, kan dataene ikke gendannes. Dette er let at forklare med et eksempel. Lad blokke X1–X3 og P3 være utilgængelige: disse er r + l blokke fra samme gruppe, 4 i vores tilfælde. Så har vi et system med 3 ligninger med 4 ubekendte, der ikke kan løses.
- I alle andre tilfælde af utilgængelighed af r + l blokke (når mindst én blok er tilgængelig fra hver gruppe), kan dataene i LRC gendannes.
Således udkonkurrerer LRC Reed-Solomon-koder med at gendanne data efter enkelte fejl. I Reed-Solomon-koder skal du bruge n blokke for at gendanne blot en datablok, og i LRC er det nok at bruge n/l blokke for at gendanne en datablok (n/2 i vores eksempel). På den anden side er LRC ringere end Reed-Solomon-koder med hensyn til det maksimale antal tilladte fejl. I eksemplerne ovenfor kan Reed-Solomon-koder gendanne data for alle 4 fejl, og for LRC er der 2 kombinationer af 4 fejl, når data ikke kan gendannes.
Hvad der er vigtigere afhænger af den konkrete situation, men ofte opvejer de besparelser i overbelastning, som LRC giver, den lidt mindre pålidelige opbevaring.
4. Andre redundanskoder
Udover Reed-Solomon og LRC-koder, er der mange andre redundanskoder. Forskellige redundanskoder bruger forskellig matematik. Her er nogle andre redundanskoder:
- Redundanskode ved hjælp af XOR-operatøren. XOR-operationen udføres på n datablokke, og 1 blok af redundanskoder opnås, det vil sige et n+1-skema (n datablokke, 1 redundanskode). Brugt i , hvor blokke af data og redundanskoder skrives cyklisk til alle diske i arrayet.
- Lige-ulige algoritme baseret på XOR-operationen. Giver dig mulighed for at bygge 2 blokke af redundanskoder, det vil sige n+2-skemaet.
- STAR-algoritme baseret på XOR-operationen. Giver dig mulighed for at bygge 3 blokke af redundanskoder, det vil sige n+3-skemaet.
- Pyramidkoder er en anden redundanskode fra Microsoft.
5. Brug i Yandex
En række Yandex-infrastrukturprojekter bruger redundanskoder til pålidelig datalagring. Her er nogle eksempler:
- MDS intern objektlagring, som jeg skrev om i begyndelsen af artiklen.
- — MapReduce-system af Yandex.
- (Yandex DataBase) - newSQL distribueret database.
MDS bruger LRC redundanskoder, 8-2-2 skema. Data med redundanskoder skrives til 12 forskellige diske i forskellige servere i 3 forskellige DC'er: 4 servere i hver DC. Læs mere om dette i .
YT bruger både Reed-Solomon-koder (skema 6-3), som var de første til at implementere, og LRC-redundanskoder (skema 12-2-2), hvor LRC er den foretrukne lagringsmetode.
YDB bruger lige-ulige baserede redundanskoder (Figur 4-2). Om redundanskoder i YDB allerede .
Brugen af forskellige redundanskodeskemaer skyldes forskellige krav til systemer. For eksempel, i MDS, er data gemt ved hjælp af LRC placeret i 3 DC'er på én gang. Det er vigtigt for os, at dataene forbliver tilgængelige til aflæsning, hvis 1 af nogen DC'er fejler, derfor skal blokkene fordeles på tværs af DC'erne, så hvis nogen DC er utilgængelig, er antallet af utilgængelige blokke ikke mere end tilladt. I 8-2-2-skemaet kan du placere 4 blokke i hver DC, så når enhver DC er slukket, vil 4 blokke være utilgængelige, og dataene kan læses. Uanset hvilken ordning vi vælger, når vi placerer den i 3 DC'er, skal der under alle omstændigheder være (r + l) / n >= 0,5, det vil sige, lagerredundans vil være mindst 50%.
I YT er situationen anderledes: hver YT-klynge er helt placeret i 1 DC (forskellige klynger i forskellige DC'er), så der er ingen sådan begrænsning der. 12-2-2-ordningen giver 33% redundans, det vil sige, at lagring af data er billigere, og den kan også overleve op til 4 samtidige diskudfald ligesom MDS-ordningen.
Der er mange flere funktioner ved brugen af redundanskoder i datalagrings- og databehandlingssystemer: nuancer af datagendannelse, indvirkningen af gendannelse på forespørgselsudførelsestid, funktioner ved dataoptagelse osv. Jeg vil tale separat om disse og andre funktioner. af brugen af redundanskoder i praksis, hvis emnet vil være interessant.
6. Links
- En række artikler om Reed-Solomon-koder og Galois-felter:
De kigger dybere på matematik i et tilgængeligt sprog. - Artikel fra Microsoft om LRC:
Afsnit 2 forklarer kort teorien og diskuterer derefter erfaringer med LRC i praksis. - Lige-ulige skema:
- STAR-skema:
- Pyramidekoder:
- Redundanskoder i MDS:
- Redundanskoder i YT:
- Redundanskoder i YDB:
Kilde: www.habr.com