{"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\/da\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Redundanskoder: en simpel forklaring p\u00e5, hvordan man p\u00e5lideligt og billigt opbevarer data","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Redundanskoder:<\/p>\n

<\/p>\n

S\u00e5dan ser redundans ud<\/em><\/p>\n

<\/p>\n

Redundanskoder* anvendes i vid udstr\u00e6kning i computersystemer for at \u00f8ge p\u00e5lideligheden af datalagring. I Yandex anvendes de i mange projekter. For eksempel sparer brugen af redundanskoder i stedet for replikation i vores interne objektlagersystem millioner uden at mindske p\u00e5lideligheden. Men p\u00e5 trods af den brede anvendelse er en forst\u00e5elig beskrivelse af, hvordan redundanskoder fungerer, meget sj\u00e6lden. Dem, der \u00f8nsker at forst\u00e5 det, st\u00f8der ofte p\u00e5 f\u00f8lgende (fra Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

Mit navn er Vadim, og i Yandex arbejder jeg med udviklingen af det interne objektlagersystem MDS. I denne artikel vil jeg med enkle ord beskrive de teoretiske grundlag for redundanskoder (Reed-Solomon koder og LRC). Jeg vil forklare, hvordan det fungerer, uden kompliceret matematik og sj\u00e6ldne termer. Til sidst vil jeg give eksempler p\u00e5 brugen af redundanskoder i Yandex.<\/p>\n

<\/p>\n

Jeg vil ikke g\u00e5 i dybden med en r\u00e6kke matematiske detaljer, men jeg vil give links til dem, der \u00f8nsker at dykke dybere ned i emnet. Jeg bem\u00e6rker ogs\u00e5, at nogle matematiske definitioner muligvis ikke er strenge, da artiklen ikke er beregnet til matematikere, men til ingeni\u00f8rer, der \u00f8nsker at forst\u00e5 essensen af sp\u00f8rgsm\u00e5let.<\/p>\n

<\/p>\n

* I den engelsksprogede litteratur kaldes redundanskoder ofte erasure codes.<\/p>\n

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

1. Essence af redundanskoder<\/h1>\n

<\/p>\n

Essensen af alle redundanskoder er ekstremt simpel: at lagre (eller overf\u00f8re) data p\u00e5 en m\u00e5de, s\u00e5 de ikke g\u00e5r tabt ved fejl (diskfejl, dataoverf\u00f8rselsfejl osv.). <\/p>\n

<\/p>\n

I de fleste* redundanskoder opdeles data i n datablokke, hvortil der genereres m redundansblokke, hvilket i alt giver n + m blokke. Redundanskoderne konstrueres, s\u00e5 det er muligt at genskabe n datablokke ved kun at bruge en del af n + m blokke. Her vil vi kun se p\u00e5 blok redundanskoder, det vil sige dem, hvor data opdeles i blokke.<\/p>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

For recovering all n data blocks, you need at least n out of n + m blocks, as you cannot obtain n blocks with only n-1 block (in this case, you would have to take 1 block \"out of thin air\"). Are n arbitrary blocks from n + m blocks sufficient for recovering all data? This depends on the type of redundancy codes; for instance, Reed-Solomon codes allow recovering all data with arbitrary n blocks, while LRC redundancy codes do not always do so.<\/p>\n

<\/p>\n

Dataopbevaring<\/h3>\n

<\/p>\n

In data storage systems, typically each of the data blocks and the redundancy code blocks is written to a separate disk. Thus, if any disk fails, the original data can still be recovered and read. Data can be recovered even in the case of simultaneous failures of multiple disks.<\/p>\n

<\/p>\n

Overf\u00f8rsel af data<\/h3>\n

<\/p>\n

Redundancy codes can be used for reliable data transmission over unreliable networks. The transmitted data is divided into blocks, for which redundancy codes are calculated. Both data blocks and redundancy code blocks are transmitted over the network. In case of errors in arbitrary blocks (up to a certain number of blocks), the data can still be transmitted reliably over the network. Reed-Solomon codes, for example, are used for data transmission over optical communication lines and in satellite communication.<\/p>\n

<\/p>\n

* There are also redundancy codes in which data is not divided into blocks, such as Hamming codes and CRC codes, widely used for data transmission in Ethernet networks. These are codes for error-resistant encoding, intended for error detection rather than correction (Hamming code also allows partial error correction).<\/p>\n

<\/p>\n

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

<\/p>\n

Reed-Solomon codes are among the most widely used redundancy codes, invented back in the 1960s and first widely applied in the 1980s for mass production of compact discs.<\/p>\n

<\/p>\n

There are two key questions for understanding Reed-Solomon codes: 1) how to create redundancy code blocks; 2) how to recover data using redundancy code blocks. Let's find the answers to them.
\nFor simplicity, we will assume that n=6 and m=4. Other schemes are considered by analogy.<\/p>\n

<\/p>\n

How to create redundancy code blocks<\/h3>\n

<\/p>\n

Hver blok af redundant kode betragtes uafh\u00e6ngigt af de andre. For at t\u00e6lle hver blok anvendes alle n datablokke. P\u00e5 diagrammet herunder er X1-X6 datablokke, P1\u2013P4 er blokke af redundant kode.<\/p>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

Alle datablokke skal have samme st\u00f8rrelse, skal nul-fyldte bits bruges til at justere. De resulterende blokke af redundant kode vil have samme st\u00f8rrelse som datablokkene. Alle datablokke opdeles i ord (f.eks. 16 bit). Antag, at vi opdeler datablokke i k ord. S\u00e5 vil alle blokke af redundant kode ogs\u00e5 blive opdelt i k ord.<\/p>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

For at beregne det i'te ord i hver blok af redundant kode vil de i'te ord fra alle datablokke blive anvendt. De vil blive beregnet ved hj\u00e6lp af f\u00f8lgende formel:<\/p>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

Her er v\u00e6rdierne x \u2013 ord fra datablokkene, p \u2013 ord fra blokke af redundant kode, alle alfa, beta, gamma og delta er specifikt udvalgte tal, der er ens for alle i. Det skal straks siges, at alle disse v\u00e6rdier ikke er almindelige tal, men elementer i Galois-feltet, operationerne +, -, *, \/ er ikke de velkendte operationer, men specielle operationer defineret over elementerne i Galois-feltet.<\/p>\n

<\/p>\n

Hvorfor er Galois-felter n\u00f8dvendige<\/h3>\n

<\/p>\n

\"Redundanskoder:<\/p>\n

<\/p>\n

Det synes at v\u00e6re enkelt: opdelt data i blokke, blokke i ord, ved hj\u00e6lp af ord fra datablokkene beregner vi ord fra blokke af redundant kode \u2013 vi f\u00e5r blokke af redundant kode. Generelt fungerer det s\u00e5dan, men detaljerne kan v\u00e6re komplicerede:<\/p>\n

<\/p>\n

    \n
  1. Som n\u00e6vnt er st\u00f8rrelsen af et ord fast, i vores eksempel 16 bit. Formlerne ovenfor for Reed-Solomon-koder er s\u00e5dan, at ved brug af almindelige heltal kan resultatet af beregningen p muligvis ikke repr\u00e6senteres med et ord af en tilladt st\u00f8rrelse.<\/li>\n
  2. Ved genopretning af data vil formlerne ovenfor blive betragtet som et system af ligninger, der skal l\u00f8ses for at genoprette data. Under l\u00f8sningen kan det v\u00e6re n\u00f8dvendigt at udf\u00f8re division af heltal, hvilket resulterer i et reelt tal, som ikke kan repr\u00e6senteres pr\u00e6cist i computerens hukommelse.<\/li>\n<\/ol>\n

    <\/p>\n

    Disse problemer forhindrer brugen af heltal til Reed-Solomon-koder. L\u00f8sningen p\u00e5 problemet er original og kan beskrives s\u00e5ledes: lad os finde specielle tal, der kan repr\u00e6senteres ved hj\u00e6lp af ord af den n\u00f8dvendige l\u00e6ngde (f.eks. 16 bit), og resultatet af alle operationer (addition, subtraktion, multiplikation, division) udf\u00f8rt p\u00e5 dem ogs\u00e5 vil blive repr\u00e6senteret i computeren med ord af den n\u00f8dvendige l\u00e6ngde.<\/p>\n

    <\/p>\n

    S\u00e5danne \"specielle\" tal er blevet studeret af matematik i lang tid, og de kaldes felter. Et felt er en samling af elementer med bestemte operationer for dem, s\u00e5som addition, subtraktion, multiplikation og division.<\/p>\n

    <\/p>\n

    Galois-felter* er de felter, for hvilke der eksisterer en entydig udfald for hver operation (+, -, *, \/) for enhver to elementer i feltet. Galois-felter kan konstrueres for tal, der er en potens af 2: 2, 4, 8, 16 osv. (faktisk en potens af ethvert primtal p, men i praksis er vi kun interesseret i potenser af 2). For eksempel, for ord med en st\u00f8rrelse p\u00e5 16 bit, er dette feltet, der indeholder 65.536 elementer, for hvilket der for hvert par kan findes resultatet af enhver operation (+, -, *, \/). V\u00e6rdierne x, p, alfa, beta, gamma, delta fra de ovenst\u00e5ende ligninger vil blive betragtet som elementer i Galois-feltet til beregninger.<\/p>\n

    <\/p>\n

    Dermed har vi et system af ligninger, som kan bruges til at konstruere redundanskoder, ved hj\u00e6lp af et passende computerprogram. Med det samme system af ligninger kan data ogs\u00e5 genskabes.<\/p>\n

    <\/p>\n

    * Dette er ikke en striks definition, snarere en beskrivelse.<\/p>\n

    <\/p>\n

    Hvordan man genskaber data<\/h3>\n

    <\/p>\n

    Genskabelse er n\u00f8dvendig, n\u00e5r en del af blokke fra n + m blokke mangler. Dette kan v\u00e6re b\u00e5de datablokke og redundansblokke. Manglende datablokke og\/eller redundansblokke vil betyde, at de tilsvarende variable x og\/eller p i de ovenst\u00e5ende ligninger er ukendte.<\/p>\n

    <\/p>\n

    Ligningerne for Reed-Solomon-koder kan betragtes som et system af ligninger, hvor alle v\u00e6rdier alfa, beta, gamma, delta er konstanter, alle x og p, der svarer til tilg\u00e6ngelige blokke, er kendte variable, mens de \u00f8vrige x og p er ukendte.<\/p>\n

    <\/p>\n

    For eksempel, lad os sige, at datablokkene 1, 2, 3, og redundansblokken 2 er utilg\u00e6ngelige, s\u00e5 for den i'te gruppe ord vil f\u00f8lgende system af ligninger v\u00e6re (ukendte markeret med r\u00f8dt):<\/p>\n

    <\/p>\n

    \"Redundanskoder:<\/p>\n

    <\/p>\n

    Vi har et system best\u00e5ende af 4 ligninger med 4 ubekendte, hvilket betyder, at vi kan l\u00f8se det og genoprette dataene!<\/p>\n

    <\/p>\n

    Fra dette system af ligninger f\u00f8lger en r\u00e6kke konklusioner om genopretning af data for Reed-Solomon-koder (n datablokke, m redundansblokke):<\/p>\n

    <\/p>\n