Zo ziet redundantie eruit
Redundantiecodes* worden veel gebruikt in computersystemen om de betrouwbaarheid van gegevensopslag te vergroten. In Yandex worden ze in veel projecten gebruikt. Het gebruik van redundantiecodes in plaats van replicatie in onze interne objectopslag bespaart bijvoorbeeld miljoenen zonder dat dit ten koste gaat van de betrouwbaarheid. Maar ondanks het wijdverbreide gebruik ervan zijn duidelijke beschrijvingen van hoe redundantiecodes werken zeer zeldzaam. Degenen die het willen begrijpen, worden geconfronteerd met ongeveer het volgende (vanaf ):
Mijn naam is Vadim, bij Yandex ontwikkel ik interne objectopslag MDS. In dit artikel zal ik in eenvoudige woorden de theoretische grondslagen van redundantiecodes (Reed-Solomon- en LRC-codes) beschrijven. Ik zal je vertellen hoe het werkt, zonder complexe wiskunde en zeldzame termen. Aan het einde zal ik voorbeelden geven van het gebruik van redundantiecodes in Yandex.
Ik zal een aantal wiskundige details niet in detail bespreken, maar ik zal links geven voor degenen die dieper willen duiken. Ik wil ook opmerken dat sommige wiskundige definities misschien niet strikt zijn, aangezien het artikel niet bedoeld is voor wiskundigen, maar voor ingenieurs die de essentie van het probleem willen begrijpen.
* In de Engelstalige literatuur worden redundantiecodes vaak wiscodes genoemd.
1. De essentie van redundantiecodes
De essentie van alle redundantiecodes is uiterst eenvoudig: gegevens opslaan (of verzenden) zodat deze niet verloren gaan als er fouten optreden (schijfstoringen, fouten bij gegevensoverdracht, enz.).
Bij de meeste* redundantiecodes worden de gegevens verdeeld in n datablokken, waarvoor m blokken redundantiecodes worden geteld, wat resulteert in een totaal van n + m blokken. Redundantiecodes zijn zo geconstrueerd dat n gegevensblokken kunnen worden hersteld met slechts een deel van n + m blokken. Vervolgens zullen we alleen blokredundantiecodes beschouwen, dat wil zeggen codes waarin de gegevens in blokken zijn verdeeld.
Om alle n datablokken te herstellen, heb je minimaal n van n+m blokken nodig, aangezien je geen n blokken kunt krijgen door slechts n-1 blok te hebben (in dit geval zou je 1 blok “uit de dunne laag” moeten halen lucht"). Zijn n willekeurige blokken van n+m blokken voldoende om alle gegevens te herstellen? Dit is afhankelijk van het type redundantiecodes. Met Reed-Solomon-codes kunt u bijvoorbeeld alle gegevens herstellen met behulp van willekeurige n-blokken, maar met LRC-redundantiecodes niet altijd.
Data opslag
In gegevensopslagsystemen wordt in de regel elk van de gegevensblokken en redundantiecodeblokken naar een afzonderlijke schijf geschreven. Als een willekeurige schijf defect raakt, kunnen de originele gegevens nog steeds worden hersteld en gelezen. Gegevens kunnen worden hersteld, zelfs als meerdere schijven tegelijkertijd uitvallen.
Gegevensoverdracht
Redundantiecodes kunnen worden gebruikt om gegevens betrouwbaar over een onbetrouwbaar netwerk te verzenden. De verzonden gegevens worden in blokken verdeeld en er worden redundantiecodes voor berekend. Zowel datablokken als redundantiecodeblokken worden via het netwerk verzonden. Als er fouten optreden in willekeurige blokken (tot een bepaald aantal blokken), kunnen gegevens nog steeds foutloos over het netwerk worden verzonden. Reed-Solomon-codes worden bijvoorbeeld gebruikt om gegevens te verzenden via optische communicatielijnen en in satellietcommunicatie.
* Er zijn ook redundantiecodes waarbij de gegevens niet in blokken zijn verdeeld, zoals Hamming-codes en CRC-codes, die veel worden gebruikt voor gegevensoverdracht in Ethernet-netwerken. Dit zijn codes voor foutcorrectiecodering, ze zijn ontworpen om fouten op te sporen, en niet om ze te corrigeren (de Hamming-code maakt ook gedeeltelijke correctie van fouten mogelijk).
2. Reed-Solomon-codes
Reed-Solomon-codes zijn een van de meest gebruikte redundantiecodes, uitgevonden in de jaren zestig en voor het eerst op grote schaal gebruikt in de jaren tachtig voor de massaproductie van compact discs.
Er zijn twee belangrijke vragen om Reed-Solomon-codes te begrijpen: 1) hoe u blokken redundantiecodes kunt maken; 2) hoe u gegevens kunt herstellen met behulp van redundantiecodeblokken. Laten we antwoorden daarop vinden.
Voor de eenvoud zullen we verder aannemen dat n=6 en m=4. Andere schema's worden naar analogie beschouwd.
Hoe u redundantiecodeblokken maakt
Elk blok redundantiecodes wordt onafhankelijk van de andere geteld. Alle n datablokken worden gebruikt om elk blok te tellen. In het onderstaande diagram zijn X1-X6 datablokken en P1-P4 redundantiecodeblokken.
Alle datablokken moeten dezelfde grootte hebben en voor uitlijning kunnen nulbits worden gebruikt. De resulterende redundantiecodeblokken zullen dezelfde grootte hebben als de datablokken. Alle datablokken zijn verdeeld in woorden (bijvoorbeeld 16 bits). Laten we zeggen dat we de datablokken in k woorden splitsen. Vervolgens worden alle blokken redundantiecodes ook in k woorden verdeeld.
Om het i-de woord van elk redundantieblok te tellen, zullen de i-de woorden van alle datablokken worden gebruikt. Ze worden berekend volgens de volgende formule:
Hier zijn de waarden x de woorden van datablokken, p zijn de woorden van redundantiecodeblokken, alle alpha, beta, gamma en delta zijn speciaal geselecteerde getallen die hetzelfde zijn voor alle i. Het moet meteen gezegd worden dat al deze waarden geen gewone getallen zijn, maar elementen van het Galois-veld; de bewerkingen +, -, *, / zijn geen bewerkingen die ons allemaal bekend zijn, maar speciale bewerkingen die zijn geïntroduceerd op elementen van het Galois-veld. veld.
Waarom zijn Galoisvelden nodig?
Het lijkt erop dat alles eenvoudig is: we verdelen de gegevens in blokken, de blokken in woorden, met behulp van de woorden van de datablokken tellen we de woorden van de redundantiecodeblokken - we krijgen redundantiecodeblokken. Over het algemeen werkt het zo, maar de duivel zit in de details:
- Zoals hierboven vermeld, staat de woordgrootte vast, in ons voorbeeld 16 bits. De bovenstaande formules voor Reed-Solomon-codes zijn zodanig dat bij gebruik van gewone gehele getallen het resultaat van de berekening van p mogelijk niet kan worden weergegeven met een woord van geldige grootte.
- Bij het herstellen van gegevens worden de bovenstaande formules beschouwd als een systeem van vergelijkingen dat moet worden opgelost om de gegevens te herstellen. Tijdens het oplossingsproces kan het nodig zijn om gehele getallen door elkaar te delen, wat resulteert in een reëel getal dat niet nauwkeurig kan worden weergegeven in het computergeheugen.
Deze problemen verhinderen het gebruik van gehele getallen voor Reed-Solomon-codes. De oplossing voor het probleem is origineel, het kan als volgt worden beschreven: laten we speciale getallen bedenken die kunnen worden weergegeven met woorden van de vereiste lengte (bijvoorbeeld 16 bits), en het resultaat van het uitvoeren van alle bewerkingen waarop (optelling , aftrekken, vermenigvuldigen, delen) zullen ook in het computergeheugen worden gepresenteerd met behulp van woorden van de vereiste lengte.
Dergelijke ‘speciale’ getallen worden al heel lang door de wiskunde bestudeerd; ze worden velden genoemd. Een veld is een verzameling elementen waarvoor de bewerkingen optellen, aftrekken, vermenigvuldigen en delen zijn gedefinieerd.
Galois*-velden zijn velden waarvoor er een uniek resultaat is van elke bewerking (+, -, *, /) voor twee willekeurige elementen van het veld. Galoisvelden kunnen worden geconstrueerd voor getallen die machten van 2 zijn: 2, 4, 8, 16, etc. (eigenlijk machten van elk priemgetal p, maar in de praktijk zijn we alleen geïnteresseerd in machten van 2). Voor 16-bits woorden is dit bijvoorbeeld een veld dat 65 elementen bevat, voor elk paar waarvan u het resultaat van elke bewerking (+, -, *, /) kunt vinden. De waarden van x, p, alpha, beta, gamma, delta uit de bovenstaande vergelijkingen worden voor berekeningen beschouwd als elementen van het Galois-veld.
We hebben dus een systeem van vergelijkingen waarmee we blokken redundantiecodes kunnen construeren door een geschikt computerprogramma te schrijven. Met hetzelfde systeem van vergelijkingen kunt u gegevensherstel uitvoeren.
*Dit is geen strikte definitie, maar eerder een beschrijving.
Hoe gegevens te herstellen
Restauratie is nodig als enkele van de n+m blokken ontbreken. Dit kunnen zowel datablokken als redundantiecodeblokken zijn. De afwezigheid van datablokken en/of redundantiecodeblokken betekent dat de corresponderende x- en/of p-variabelen onbekend zijn in de bovenstaande vergelijkingen.
De vergelijkingen voor Reed-Solomon-codes kunnen worden gezien als een systeem van vergelijkingen waarin alle alfa-, bèta-, gamma- en deltawaarden constanten zijn, alle x en p die overeenkomen met de beschikbare blokken bekende variabelen zijn, en de resterende x en p zijn niet bekend.
Stel dat datablokken 1, 2, 3 en redundantiecodeblok 2 bijvoorbeeld niet beschikbaar zijn, dan zal er voor de i-de groep woorden het volgende systeem van vergelijkingen zijn (onbekenden zijn rood gemarkeerd):
We hebben een systeem van 4 vergelijkingen met 4 onbekenden, wat betekent dat we het kunnen oplossen en de gegevens kunnen herstellen!
Uit dit stelsel van vergelijkingen volgt een aantal conclusies over dataherstel voor Reed-Solomon-codes (n datablokken, m redundantiecodeblokken):
- Gegevens kunnen worden hersteld als er m blokken of minder verloren gaan. Als m+1 of meer blokken verloren gaan, kunnen de gegevens niet worden hersteld: het is onmogelijk om een systeem van m vergelijkingen met m+1 onbekenden op te lossen.
- Om zelfs maar één datablok te herstellen, moet u een van de resterende blokken gebruiken, en u kunt een van de redundantiecodes gebruiken.
Wat moet ik nog meer weten?
In de bovenstaande beschrijving vermijd ik een aantal belangrijke kwesties die een diepere duik in de wiskunde vereisen om te overwegen. In het bijzonder zeg ik niets over het volgende:
- Het stelsel vergelijkingen voor Reed-Solomon-codes moet voor elke combinatie van onbekenden (maximaal m onbekenden) een (unieke) oplossing hebben. Op basis van deze vereiste worden de waarden alfa, bèta, gamma en delta geselecteerd.
- Een systeem van vergelijkingen moet automatisch kunnen worden geconstrueerd (afhankelijk van welke blokken niet beschikbaar zijn) en opgelost.
- We moeten een Galoisveld bouwen: voor een gegeven woordgrootte moeten we het resultaat kunnen vinden van elke bewerking (+, -, *, /) voor twee willekeurige elementen.
Aan het einde van het artikel vindt u verwijzingen naar literatuur over deze belangrijke kwesties.
Keuze uit n en m
Hoe kies je n en m in de praktijk? In de praktijk worden in gegevensopslagsystemen redundantiecodes gebruikt om ruimte te besparen, dus m wordt altijd kleiner dan n gekozen. Hun specifieke waarden zijn afhankelijk van een aantal factoren, waaronder:
- Betrouwbaarheid van gegevensopslag. Hoe groter m, hoe groter het aantal schijfstoringen dat kan worden overleefd, dat wil zeggen hoe hoger de betrouwbaarheid.
- Redundante opslag. Hoe hoger de m/n-ratio, hoe hoger de opslagredundantie en hoe duurder het systeem zal zijn.
- Verwerkingstijd aanvragen. Hoe groter de som n + m, hoe langer de responstijd op verzoeken zal zijn. Omdat het lezen van gegevens (tijdens herstel) het lezen van n blokken vereist die op n verschillende schijven zijn opgeslagen, wordt de leestijd bepaald door de langzaamste schijf.
Bovendien legt het opslaan van gegevens in meerdere DC's extra beperkingen op aan de keuze tussen n en m: als 1 DC is uitgeschakeld, moeten de gegevens nog steeds beschikbaar zijn om te worden gelezen. Als u bijvoorbeeld gegevens in 3 DC's opslaat, moet aan de volgende voorwaarde worden voldaan: m >= n/2, anders kan er een situatie ontstaan waarin de gegevens niet kunnen worden gelezen wanneer 1 DC is uitgeschakeld.
3. LRC - Lokale wederopbouwcodes
Om gegevens te herstellen met behulp van Reed-Solomon-codes, moet u n willekeurige gegevensblokken gebruiken. Dit is een zeer groot nadeel voor gedistribueerde gegevensopslagsystemen, omdat je, om gegevens op één kapotte schijf te herstellen, gegevens van de meeste andere moet lezen, wat een grote extra belasting op de schijven en het netwerk veroorzaakt.
De meest voorkomende fouten zijn de ontoegankelijkheid van één gegevensblok als gevolg van een storing of overbelasting van één schijf. Is het in dit (meest voorkomende) geval mogelijk om op de een of andere manier de overtollige belasting voor gegevensherstel te verminderen? Het blijkt dat dit kan: er zijn speciaal voor dit doel LRC-redundantiecodes.
LRC (Local Reconstruction Codes) zijn redundantiecodes die door Microsoft zijn uitgevonden voor gebruik in Windows Azure Storage. Het idee van LRC is zo eenvoudig mogelijk: verdeel alle datablokken in twee (of meer) groepen en lees voor elke groep afzonderlijk een deel van de redundantiecodeblokken. Vervolgens worden sommige redundantiecodeblokken geteld met behulp van alle datablokken (in LRC worden ze globale redundantiecodes genoemd), en sommige - met behulp van een van de twee groepen datablokken (ze worden lokale redundantiecodes genoemd).
LRC wordt aangegeven met drie cijfers: nrl, waarbij n het aantal datablokken is, r het aantal globale redundantiecodeblokken is, l het aantal lokale redundantiecodeblokken is. Om gegevens te lezen wanneer één gegevensblok niet beschikbaar is, hoeft u alleen n/l blokken te lezen - dit is l keer minder dan bij Reed-Solomon-codes.
Neem bijvoorbeeld het LRC 6-2-2-schema. X1–X6 — 6 datablokken, P1, P2 — 2 globale redundantieblokken, P3, P4 — 2 lokale redundantieblokken.
Redundantiecodeblokken P1, P2 worden geteld met behulp van alle datablokken. Redundantiecodeblok P3 - gebruikt datablokken X1-X3, redundantiecodeblok P4 - gebruikt datablokken X4-X6.
De rest wordt gedaan in LRC naar analogie met Reed-Solomon-codes. De vergelijkingen voor het tellen van de woorden van redundantiecodeblokken zijn:
Om de getallen alpha, beta, gamma, delta te selecteren, moet aan een aantal voorwaarden worden voldaan om de mogelijkheid van gegevensherstel te garanderen (dat wil zeggen het oplossen van het vergelijkingssysteem). U kunt meer over hen lezen in .
Ook in de praktijk wordt de XOR-bewerking gebruikt om lokale redundantiecodes P3, P4 te berekenen.
Uit het stelsel van vergelijkingen voor LRC volgt een aantal conclusies:
- Om één datablok te herstellen, volstaat het om n/l blokken te lezen (n/1 in ons voorbeeld).
- Als r + l-blokken niet beschikbaar zijn en alle blokken in één groep zijn opgenomen, kunnen de gegevens niet worden hersteld. Dit is eenvoudig uit te leggen met een voorbeeld. Stel dat de blokken X1-X3 en P3 niet beschikbaar zijn: dit zijn r + l-blokken uit dezelfde groep, in ons geval 4. Dan hebben we een stelsel van 3 vergelijkingen met 4 onbekenden die niet kunnen worden opgelost.
- In alle andere gevallen waarin r+l-blokken niet beschikbaar zijn (wanneer er uit elke groep ten minste één blok beschikbaar is), kunnen de gegevens in de LRC worden hersteld.
LRC presteert dus beter dan Reed-Solomon-codes bij het herstellen van gegevens na enkele fouten. In Reed-Solomon-codes moet je, om zelfs maar één gegevensblok te herstellen, n blokken gebruiken, en in LRC, om één blok gegevens te herstellen, is het voldoende om n/l blokken te gebruiken (n/2 in ons voorbeeld). Aan de andere kant is LRC inferieur aan Reed-Solomon-codes wat betreft het maximale aantal toegestane fouten. In de bovenstaande voorbeelden kunnen Reed-Solomon-codes gegevens herstellen voor vier willekeurige fouten, en voor LRC zijn er twee combinaties van vier fouten wanneer gegevens niet kunnen worden hersteld.
Wat belangrijker is, hangt af van de specifieke situatie, maar vaak wegen de besparingen op overbelasting die LRC oplevert zwaarder dan de iets minder betrouwbare opslag.
4. Overige redundantiecodes
Naast Reed-Solomon- en LRC-codes zijn er nog vele andere redundantiecodes. Verschillende redundantiecodes gebruiken verschillende wiskunde. Hier zijn enkele andere redundantiecodes:
- Redundantiecode met behulp van de XOR-operator. De XOR-bewerking wordt uitgevoerd op n datablokken en er wordt 1 blok redundantiecodes verkregen, dat wil zeggen een n+1 schema (n datablokken, 1 redundantiecode). Gebruikt in , waarbij gegevensblokken en redundantiecodes cyclisch naar alle schijven van de array worden geschreven.
- Even-oneven algoritme gebaseerd op de XOR-bewerking. Hiermee kunt u 2 blokken redundantiecodes bouwen, dat wil zeggen het n+2-schema.
- STAR-algoritme gebaseerd op de XOR-bewerking. Hiermee kunt u 3 blokken redundantiecodes bouwen, dat wil zeggen het n+3-schema.
- Pyramide-codes zijn een andere redundantiecode van Microsoft.
5. Gebruik in Yandex
Een aantal Yandex-infrastructuurprojecten gebruiken redundantiecodes voor betrouwbare gegevensopslag. Hier zijn enkele voorbeelden:
- MDS interne objectopslag, waarover ik aan het begin van het artikel schreef.
- - MapReduce-systeem van Yandex.
- (Yandex DataBase) - newSQL gedistribueerde database.
MDS gebruikt LRC-redundantiecodes, 8-2-2-schema. Gegevens met redundantiecodes worden naar 12 verschillende schijven op verschillende servers in 3 verschillende DC's geschreven: 4 servers in elke DC. Lees hierover meer in .
YT gebruikt zowel Reed-Solomon-codes (Schema 6-3), die als eerste werden geïmplementeerd, als LRC-redundantiecodes (Schema 12-2-2), waarbij LRC de voorkeursopslagmethode is.
YDB maakt gebruik van op even en oneven gebaseerde redundantiecodes (Afbeelding 4-2). Over redundantiecodes in YDB al .
Het gebruik van verschillende redundantiecodeschema's is te wijten aan verschillende systeemvereisten. In MDS worden gegevens die zijn opgeslagen met behulp van LRC bijvoorbeeld in 3 DC's tegelijk geplaatst. Voor ons is het belangrijk dat de data beschikbaar blijven om te lezen als 1 van de DC's uitvalt. Daarom moeten de blokken over de DC's worden verdeeld, zodat als er een DC niet beschikbaar is, het aantal ontoegankelijke blokken niet meer dan toelaatbaar is. In het 8-2-2-schema kunt u 4 blokken in elke DC plaatsen. Als een DC wordt uitgeschakeld, zijn er 4 blokken niet beschikbaar en kunnen de gegevens worden gelezen. Welk schema we ook kiezen bij plaatsing in 3 DC's, er moet in ieder geval (r + l) / n >= 0,5 zijn, dat wil zeggen dat de opslagredundantie minimaal 50% zal zijn.
In YT is de situatie anders: elk YT-cluster bevindt zich volledig in 1 DC (verschillende clusters in verschillende DC's), dus een dergelijke beperking bestaat niet. Het 12-2-2-schema biedt 33% redundantie, dat wil zeggen dat het opslaan van gegevens goedkoper is, en het kan ook tot vier gelijktijdige schijfstoringen overleven, net als het MDS-schema.
Er zijn nog veel meer kenmerken van het gebruik van redundantiecodes in systemen voor gegevensopslag en -verwerking: nuances van gegevensherstel, de impact van herstel op de uitvoeringstijd van zoekopdrachten, kenmerken van gegevensregistratie, enz. Over deze en andere kenmerken ga ik apart praten. van het gebruik van redundantiecodes in de praktijk, als het onderwerp interessant zal zijn.
6. Koppelingen
- Een reeks artikelen over Reed-Solomon-codes en Galois-velden:
Ze gaan dieper in op wiskunde in toegankelijke taal. - Artikel van Microsoft over LRC:
In hoofdstuk 2 wordt de theorie kort toegelicht en vervolgens worden ervaringen met LRC in de praktijk besproken. - Even-oneven schema:
- STAR-schema:
- Piramidecodes:
- Redundantiecodes in MDS:
- Redundantiecodes in YT:
- Redundantiecodes in YDB:
Bron: www.habr.com