{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Redundantiecodes: eenvoudig gezegd hoe je gegevens betrouwbaar en goedkoop kunt opslaan","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Redundantiecodes:<\/p>\n

<\/p>\n

Zo ziet redundantie eruit<\/em><\/p>\n

<\/p>\n

Redundantiecodes* worden op grote schaal toegepast in computersystemen om de betrouwbaarheid van gegevensopslag te vergroten. Bij Yandex worden ze in veel projecten gebruikt. Bijvoorbeeld, het gebruik van redundantiecodes in plaats van replicatie in onze interne objectopslag bespaart miljoenen zonder de betrouwbaarheid te verlagen. Ondanks de brede toepassing komt een begrijpelijke uitleg van hoe redundantiecodes werken zelden voor. Wie het wil begrijpen, wordt ongeveer geconfronteerd met het volgende (uit Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Mijn naam is Vadim en bij Yandex houd ik me bezig met de ontwikkeling van de interne objectopslag MDS. In dit artikel zal ik de theoretische basis van redundantiecodes (Reed-Solomon codes en LRC) in eenvoudige bewoordingen beschrijven. Ik zal uitleggen hoe het werkt, zonder complexe wiskunde en zeldzame termen. Aan het einde geef ik voorbeelden van het gebruik van redundantiecodes bij Yandex.<\/p>\n

<\/p>\n

Ik zal niet gedetailleerd ingaan op een aantal wiskundige details, maar ik zal verwijzingen geven voor degenen die dieper willen duiken. Ook wil ik opmerken dat sommige wiskundige definities mogelijk niet strikt zijn, aangezien het artikel niet voor wiskundigen, maar voor ingenieurs is bedoeld die de essentie van de kwestie willen begrijpen.<\/p>\n

<\/p>\n

* In Engelstalige literatuur worden redundantiecodes vaak erasure codes genoemd.<\/p>\n

<\/a><\/noindex><\/p>\n

1. De essentie van redundantiecodes<\/h1>\n

<\/p>\n

De essentie van alle redundantiecodes is uiterst eenvoudig: gegevens opslaan (of verzenden) op een manier dat ze niet verloren gaan bij fouten (schijfstoringen, fouten in gegevensoverdracht, enz.). <\/p>\n

<\/p>\n

In de meeste* redundantiecodes worden gegevens opgesplitst in n datablocks, voor hen worden m blokken redundantiecodes berekend, wat in totaal n + m blokken oplevert. Redundantiecodes worden zo opgebouwd dat n datablocks kunnen worden hersteld met slechts een deel van de n + m blokken. Verder zullen we alleen block codes van redundantie beschouwen, dat wil zeggen die waarbij de gegevens in blokken worden verdeeld.<\/p>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Om alle n datablokken te herstellen, heeft u minstens n van de n + m blokken nodig, omdat u n blokken niet kunt verkrijgen met slechts n-1 blok (in dat geval zou u 1 blok uit 'de lucht' moeten halen). Zijn n willekeurige blokken van n + m blokken voldoende om alle gegevens te herstellen? Dit hangt af van het type foutencodes; bijvoorbeeld, Reed-Solomon codes stellen u in staat om alle gegevens te herstellen met willekeurige n blokken, terwijl LRC-foutencodes dat niet altijd doen.<\/p>\n

<\/p>\n

Gegevensopslag<\/h3>\n

<\/p>\n

In opslagsystemen wordt doorgaans elk van de datablokken en de foutencodes op een aparte schijf geschreven. Bij een storing van een willekeurige schijf kunnen de oorspronkelijke gegevens toch worden hersteld en gelezen. Gegevens kunnen zelfs worden hersteld bij een gelijktijdige storing van meerdere schijven.<\/p>\n

<\/p>\n

Gegevensoverdracht<\/h3>\n

<\/p>\n

Foutencodes kunnen worden gebruikt voor betrouwbare gegevensoverdracht in onbetrouwbare netwerken. De over te dragen gegevens worden opgedeeld in blokken, waarvoor foutencodes worden berekend. Zowel de datablokken als de foutencodes worden via het netwerk verzonden. Bij fouten in willekeurige blokken (tot een bepaald aantal blokken), kunnen de gegevens toch foutloos via het netwerk worden overgedragen. Reed-Solomon codes worden bijvoorbeeld gebruikt voor gegevensoverdracht via optische communicatielijnen en in satellietcommunicatie.<\/p>\n

<\/p>\n

* Er zijn ook foutencodes waarbij de gegevens niet in blokken worden verdeeld, zoals Hamming codes en CRC-codes, die veel worden toegepast voor gegevensoverdracht in Ethernet-netwerken. Dit zijn codes voor foutbestendige codering; ze zijn bedoeld voor foutdetectie, niet voor foutcorrectie (de Hamming-code maakt ook gedeeltelijke foutcorrectie mogelijk).<\/p>\n

<\/p>\n

2. Reed-Solomon codes<\/h1>\n

<\/p>\n

Reed-Solomon codes zijn een van de meest wijdverbreide foutencodes, uitgevonden in de jaren '60 en voor het eerst veel gebruikt in de jaren '80 voor de massaproductie van cd's.<\/p>\n

<\/p>\n

Er zijn twee belangrijke vragen voor het begrijpen van Reed-Solomon codes: 1) hoe fouten te genereren; 2) hoe gegevens te herstellen met behulp van foutencodes. Laten we antwoorden op deze vragen vinden.
\nOm te vereenvoudigen, nemen we aan dat n=6 en m=4. Andere schema's worden op dezelfde manier behandeld.<\/p>\n

<\/p>\n

Hoe foutencodes te genereren<\/h3>\n

<\/p>\n

Elke foutencodering wordt onafhankelijk van andere foutencoderingen berekend. Voor het berekenen van elke foutencodering worden alle n datablocks gebruikt. In de onderstaande afbeelding zijn X1-X6 datablocks, P1\u2013P4 foutencoderingblocks.<\/p>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Alle datablocks moeten dezelfde grootte hebben; voor uitlijning kunnen nulbits worden gebruikt. De verkregen foutencoderingblocks zullen dezelfde grootte hebben als de datablocks. Alle datablocks worden in woorden (bijvoorbeeld 16 bits per woord) verdeeld. Laten we aannemen dat we de datablocks in k woorden hebben verdeeld. Dan zullen alle foutencoderingblocks ook in k woorden worden verdeeld.<\/p>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Voor het berekenen van het i-de woord van elke foutencodering zal het i-de woord van alle datablocks worden gebruikt. Ze worden berekend volgens de volgende formule:<\/p>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Hier zijn de waarden x de woorden van de datablocks, p de woorden van de foutencoderingblocks, en alfa, beta, gamma en delta zijn speciaal gekozen getallen die gelijk zijn voor alle i. Het moet meteen worden gezegd dat al deze waarden geen gewone getallen zijn, maar elementen van een Galois-veld. De operaties +, -, *, \/ zijn geen gebruikelijke operaties, maar speciale operaties die zijn gedefinieerd voor elementen van een Galois-veld.<\/p>\n

<\/p>\n

Waarom zijn Galois-velden nodig?<\/h3>\n

<\/p>\n

\"Redundantiecodes:<\/p>\n

<\/p>\n

Het lijkt eenvoudig: we verdelen gegevens in blokken, de blokken in woorden en met behulp van de woorden van de datablocks berekenen we de woorden van de foutencoderingblocks \u2014 zo krijgen we de foutencoderingblocks. Over het algemeen werkt het zo, maar het kwaad zit in de details:<\/p>\n

<\/p>\n

    \n
  1. Zoals eerder vermeld is de grootte van een woord vast, in ons voorbeeld 16 bits. De bovenstaande formules voor Reed-Solomon-coderingen zijn zodanig dat bij het gebruik van gewone gehele getallen het resultaat van de berekening p mogelijk niet kan worden weergegeven met een woord van toegestaan formaat.<\/li>\n
  2. Bij het herstellen van gegevens zullen de bovenstaande formules worden gezien als een systeem van vergelijkingen dat moet worden opgelost om de gegevens te herstellen. Tijdens het oplossen kan het nodig zijn om gehele getallen door elkaar te delen, wat resulteert in een re\u00ebel getal dat niet nauwkeurig in het geheugen van de computer kan worden weergegeven.<\/li>\n<\/ol>\n

    <\/p>\n

    Deze problemen maken het onmogelijk om gehele getallen te gebruiken voor Reed-Solomon codes. De oplossing voor het probleem is origineel en kan als volgt worden beschreven: laten we speciale getallen bedenken die kunnen worden weergegeven met woorden van de juiste lengte (bijvoorbeeld 16 bits), en het resultaat van alle bewerkingen op deze getallen (optellen, aftrekken, vermenigvuldigen, delen) zal ook in het geheugen van de computer worden weergegeven met woorden van de juiste lengte.<\/p>\n

    <\/p>\n

    Dergelijke 'speciale' getallen worden al lange tijd bestudeerd door de wiskunde en worden velden genoemd. Een veld is een verzameling elementen met bepaalde operaties zoals optelling, aftrekking, vermenigvuldigen en delen.<\/p>\n

    <\/p>\n

    Galoisvelden* zijn velden waarvoor er een unieke uitkomst bestaat voor elke bewerking (+, -, *, \/) voor elke twee elementen van het veld. Galoisvelden kunnen worden opgebouwd voor getallen die een macht van 2 zijn: 2, 4, 8, 16, enzovoorts (in feite voor elke macht van een priemgetal p, maar in de praktijk zijn alleen de machten van 2 voor ons interessant). Bijvoorbeeld, voor woorden van 16 bits is dit veld dat 65.536 elementen bevat, waarvoor voor elk paar een resultaat kan worden gevonden voor elke operatie (+, -, *, \/). De waarden x, p, alfa, beta, gamma, delta in de bovenstaande vergelijkingen worden als elementen van het Galoisveld beschouwd voor de berekeningen.<\/p>\n

    <\/p>\n

    Zo hebben we een systeem van vergelijkingen waarmee we blokken van redundantiecodes kunnen opbouwen door een bijbehorende computerprogramma te schrijven. Met behulp van ditzelfde systeem van vergelijkingen kunnen we gegevensherstel uitvoeren.<\/p>\n

    <\/p>\n

    * Dit is geen strikte definitie, eerder een beschrijving.<\/p>\n

    <\/p>\n

    Hoe gegevens te herstellen<\/h3>\n

    <\/p>\n

    Herstel is nodig wanneer een deel van de n + m blokken ontbreekt. Dit kunnen zowel datablocks zijn als blokken van redundantiecodes. Het ontbreken van datablocks en\/of blokken van redundantiecodes betekent dat in de bovenstaande vergelijkingen de bijbehorende variabelen x en\/of p onbekend zijn.<\/p>\n

    <\/p>\n

    De vergelijkingen voor Reed-Solomon codes kunnen worden gezien als een systeem van vergelijkingen waarin alle waarden alfa, beta, gamma, delta constanten zijn, alle x en p die overeenkomen met de beschikbare blokken zijn bekende variabelen, en de andere x en p zijn onbekend.<\/p>\n

    <\/p>\n

    Bijvoorbeeld, stel dat de datablocks 1, 2, 3 en de blokken van redundantiecodes 2 onbeschikbaar zijn, dan zal de volgende set van vergelijkingen voor de i-de groep woorden gelden (onbekenden gemarkeerd in het rood):<\/p>\n

    <\/p>\n

    \"Redundantiecodes:<\/p>\n

    <\/p>\n

    We have a system of 4 equations with 4 unknowns, so we can solve it and recover the data!<\/p>\n

    <\/p>\n

    This system of equations leads to several conclusions about data recovery for Reed-Solomon codes (n blocks of data, m redundancy blocks):<\/p>\n

    <\/p>\n