{"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\/fr\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Codes de redondance : en termes simples, comment stocker des donn\u00e9es de mani\u00e8re fiable et \u00e9conomique","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Codes<\/p>\n

<\/p>\n

Voici \u00e0 quoi ressemble la redondance<\/em><\/p>\n

<\/p>\n

Les codes de redondance* sont largement utilis\u00e9s dans les syst\u00e8mes informatiques pour am\u00e9liorer la fiabilit\u00e9 du stockage des donn\u00e9es. Chez Yandex, ils sont utilis\u00e9s dans de nombreux projets. Par exemple, l'utilisation de codes de redondance \u00e0 la place de la r\u00e9plication dans notre syst\u00e8me de stockage d'objets interne permet d'\u00e9conomiser des millions sans diminuer la fiabilit\u00e9. Mais malgr\u00e9 leur large utilisation, une description claire de leur fonctionnement est rare. Ceux qui souhaitent comprendre se heurtent g\u00e9n\u00e9ralement \u00e0 ce qui suit (voir Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

Je m'appelle Vadim, et chez Yandex, je travaille sur le d\u00e9veloppement du syst\u00e8me de stockage d'objets interne MDS. Dans cet article, je vais expliquer les principes th\u00e9oriques des codes de redondance (codes de Reed-Solomon et LRC) en des termes simples. Je vais d\u00e9crire leur fonctionnement sans math\u00e9matiques complexes ni termes rares. \u00c0 la fin, je donnerai des exemples d'utilisation des codes de redondance chez Yandex.<\/p>\n

<\/p>\n

Je ne vais pas aborder en d\u00e9tail certains aspects math\u00e9matiques, mais je fournirai des liens pour ceux qui souhaitent approfondir. Je souligne \u00e9galement que certaines d\u00e9finitions math\u00e9matiques peuvent ne pas \u00eatre strictes, car l'article s'adresse non pas \u00e0 des math\u00e9maticiens mais \u00e0 des ing\u00e9nieurs d\u00e9sireux de comprendre le c\u0153ur du sujet.<\/p>\n

<\/p>\n

* Dans la litt\u00e9rature anglophone, les codes de redondance sont souvent appel\u00e9s erasure codes.<\/p>\n

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

1. La nature des codes de redondance<\/h1>\n

<\/p>\n

La nature de tous les codes de redondance est extr\u00eamement simple : stocker (ou transmettre) des donn\u00e9es de mani\u00e8re \u00e0 ce qu'elles ne soient pas perdues en cas d'erreurs (pannes de disque, erreurs de transmission des donn\u00e9es, etc.). <\/p>\n

<\/p>\n

Dans la plupart des* codes de redondance, les donn\u00e9es sont divis\u00e9es en n blocs de donn\u00e9es, et m blocs de codes de redondance sont g\u00e9n\u00e9r\u00e9s, ce qui donne un total de n + m blocs. Les codes de redondance sont construits de mani\u00e8re \u00e0 ce que l'on puisse r\u00e9cup\u00e9rer n blocs de donn\u00e9es en n'utilisant qu'une partie des n + m blocs. Nous allons ici examiner uniquement les codes de redondance bloqu\u00e9s, c'est-\u00e0-dire ceux dans lesquels les donn\u00e9es sont divis\u00e9es en blocs.<\/p>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

Pour r\u00e9cup\u00e9rer tous les n blocs de donn\u00e9es, il faut au minimum n des n + m blocs, car il est impossible d'obtenir n blocs avec seulement n-1 bloc (dans ce cas, il faudrait prendre 1 bloc \u00ab dans l'air \u00bb). Suffit-il d'avoir n blocs al\u00e9atoires parmi n + m blocs pour restaurer toutes les donn\u00e9es ? Cela d\u00e9pend du type de codes dRedondance, par exemple les codes de Reed-Solomon permettent de r\u00e9cup\u00e9rer toutes les donn\u00e9es avec des blocs al\u00e9atoires n, tandis que les codes de redondance LRC ne le permettent pas toujours.<\/p>\n

<\/p>\n

Stockage des donn\u00e9es<\/h3>\n

<\/p>\n

Dans les syst\u00e8mes de stockage de donn\u00e9es, en r\u00e8gle g\u00e9n\u00e9rale, chacun des blocs de donn\u00e9es et des blocs de codes de redondance est enregistr\u00e9 sur un disque distinct. Ainsi, en cas de panne d'un disque al\u00e9atoire, les donn\u00e9es d'origine pourront toujours \u00eatre restaur\u00e9es et lues. Les donn\u00e9es pourront \u00eatre restaur\u00e9es m\u00eame en cas de panne simultan\u00e9e de plusieurs disques.<\/p>\n

<\/p>\n

Transmission de donn\u00e9es<\/h3>\n

<\/p>\n

Les codes de redondance peuvent \u00eatre utilis\u00e9s pour une transmission fiable des donn\u00e9es sur un r\u00e9seau peu fiable. Les donn\u00e9es transmises sont divis\u00e9es en blocs, pour lesquels des codes de redondance sont calcul\u00e9s. Tant les blocs de donn\u00e9es que les blocs de codes de redondance sont transmis sur le r\u00e9seau. En cas d'erreurs dans des blocs al\u00e9atoires (jusqu'\u00e0 un certain nombre de blocs), les donn\u00e9es peuvent tout de m\u00eame \u00eatre transmises sans erreur sur le r\u00e9seau. Les codes de Reed-Solomon, par exemple, sont utilis\u00e9s pour la transmission de donn\u00e9es sur des lignes de communication optique et dans les communications par satellite.<\/p>\n

<\/p>\n

* Il existe \u00e9galement des codes de redondance dans lesquels les donn\u00e9es ne sont pas divis\u00e9es en blocs, comme les codes de Hamming et les codes CRC, largement utilis\u00e9s pour la transmission de donn\u00e9es dans les r\u00e9seaux Ethernet. Ce sont des codes de codage \u00e0 \u00e9preuve d'erreurs, destin\u00e9s \u00e0 la d\u00e9tection des erreurs plut\u00f4t qu'\u00e0 leur correction (le code de Hamming permet \u00e9galement de corriger partiellement les erreurs).<\/p>\n

<\/p>\n

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

<\/p>\n

Les codes de Reed-Solomon sont parmi les codes de redondance les plus largement utilis\u00e9s, invent\u00e9s dans les ann\u00e9es 1960 et qui ont d'abord \u00e9t\u00e9 largement appliqu\u00e9s dans les ann\u00e9es 1980 pour la production en s\u00e9rie de disques compacts.<\/p>\n

<\/p>\n

Deux questions cl\u00e9s pour comprendre les codes de Reed-Solomon sont : 1) comment cr\u00e9er des blocs de codes de redondance ; 2) comment restaurer les donn\u00e9es \u00e0 l'aide de blocs de codes de redondance. Trouvons les r\u00e9ponses \u00e0 ces questions.
\nPour simplifier, nous allons consid\u00e9rer que n=6 et m=4. D'autres sch\u00e9mas peuvent \u00eatre examin\u00e9s par analogie.<\/p>\n

<\/p>\n

Comment cr\u00e9er des blocs de codes de redondance<\/h3>\n

<\/p>\n

Chaque bloc de codes d'erreur est compt\u00e9 ind\u00e9pendamment des autres. Pour le calcul de chaque bloc, tous les n blocs de donn\u00e9es sont utilis\u00e9s. Dans le sch\u00e9ma ci-dessous, X1-X6 repr\u00e9sentent les blocs de donn\u00e9es, P1\u2013P4 les blocs de codes d'erreur.<\/p>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

Tous les blocs de donn\u00e9es doivent \u00eatre de la m\u00eame taille. Des bits nuls peuvent \u00eatre utilis\u00e9s pour l'alignement. Les blocs de codes d'erreur obtenus auront la m\u00eame taille que les blocs de donn\u00e9es. Tous les blocs de donn\u00e9es sont divis\u00e9s en mots (par exemple, de 16 bits). Supposons que nous avons divis\u00e9 les blocs de donn\u00e9es en k mots. Alors, tous les blocs de codes d'erreur seront \u00e9galement divis\u00e9s en k mots.<\/p>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

Pour le calcul du i\u00e8me mot de chaque bloc de codes d'erreur, les i\u00e8mes mots de tous les blocs de donn\u00e9es seront utilis\u00e9s. Ils seront calcul\u00e9s selon la formule suivante :<\/p>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

Ici, les valeurs x repr\u00e9sentent les mots des blocs de donn\u00e9es, p les mots des blocs de codes d'erreur, et tous les alpha, beta, gamma et delta sont des nombres sp\u00e9cifiquement choisis, identiques pour tous les i. Il faut pr\u00e9ciser que toutes ces valeurs ne sont pas des nombres ordinaires, mais des \u00e9l\u00e9ments du corps de Galois, avec des op\u00e9rations +, -, *, \/ qui ne sont pas les op\u00e9rations habituelles, mais des op\u00e9rations sp\u00e9ciales d\u00e9finies sur les \u00e9l\u00e9ments du corps de Galois.<\/p>\n

<\/p>\n

Pourquoi les corps de Galois sont-ils n\u00e9cessaires ?<\/h3>\n

<\/p>\n

\"Codes<\/p>\n

<\/p>\n

\u00c0 premi\u00e8re vue, cela semble simple : nous divisons les donn\u00e9es en blocs, les blocs en mots, et avec les mots des blocs de donn\u00e9es, nous calculons les mots des blocs de codes d'erreur, et nous obtenons les blocs de codes d'erreur. En g\u00e9n\u00e9ral, c'est ainsi que cela fonctionne, mais le diable est dans les d\u00e9tails :<\/p>\n

<\/p>\n

    \n
  1. Comme mentionn\u00e9 ci-dessus, la taille du mot est fixe, dans notre exemple 16 bits. Les formules ci-dessus pour les codes de Reed-Solomon sont telles que, lorsque des entiers ordinaires sont utilis\u00e9s, le r\u00e9sultat du calcul de p peut ne pas \u00eatre repr\u00e9sentable par un mot de taille admissible.<\/li>\n
  2. Lors de la r\u00e9cup\u00e9ration des donn\u00e9es, les formules ci-dessus seront consid\u00e9r\u00e9es comme un syst\u00e8me d'\u00e9quations \u00e0 r\u00e9soudre pour r\u00e9cup\u00e9rer les donn\u00e9es. Dans le processus de r\u00e9solution, il peut \u00eatre n\u00e9cessaire de diviser des entiers les uns par les autres, ce qui aboutira \u00e0 un nombre r\u00e9el qui ne peut pas \u00eatre repr\u00e9sent\u00e9 avec pr\u00e9cision en m\u00e9moire informatique.<\/li>\n<\/ol>\n

    <\/p>\n

    Ces probl\u00e8mes emp\u00eachent d'utiliser des entiers pour les codes de Reed-Solomon. La solution est originale et peut \u00eatre d\u00e9crite comme suit : inventons des nombres sp\u00e9ciaux qui peuvent \u00eatre repr\u00e9sent\u00e9s par des mots de longueur appropri\u00e9e (par exemple, 16 bits), et le r\u00e9sultat de toutes les op\u00e9rations sur eux (addition, soustraction, multiplication, division) sera \u00e9galement repr\u00e9sent\u00e9 en m\u00e9moire de l'ordinateur par des mots de la m\u00eame longueur.<\/p>\n

    <\/p>\n

    Ces \u00ab nombres sp\u00e9ciaux \u00bb sont \u00e9tudi\u00e9s depuis longtemps par les math\u00e9maticiens, et on les appelle des corps. Un corps est un ensemble d'\u00e9l\u00e9ments avec des op\u00e9rations de addition, soustraction, multiplication et division d\u00e9finies.<\/p>\n

    <\/p>\n

    Les corps de Galois* sont des corps pour lesquels il existe un et un seul r\u00e9sultat pour chaque op\u00e9ration (+, -, *, \/) pour n'importe quelle paire d'\u00e9l\u00e9ments du corps. Des corps de Galois peuvent \u00eatre construits pour des nombres qui sont des puissances de 2 : 2, 4, 8, 16, etc. (en r\u00e9alit\u00e9, toute puissance d'un nombre premier p, mais en pratique, nous nous int\u00e9ressons uniquement aux puissances de 2). Par exemple, pour des mots de taille 16 bits, ce corps contient 65 536 \u00e9l\u00e9ments, pour chaque paire desquels il est possible de trouver le r\u00e9sultat de toute op\u00e9ration (+, -, *, \/). Les valeurs x, p, alpha, beta, gamma, delta des \u00e9quations ci-dessus seront consid\u00e9r\u00e9es comme des \u00e9l\u00e9ments du corps de Galois lors des calculs.<\/p>\n

    <\/p>\n

    Ainsi, nous avons un syst\u00e8me d'\u00e9quations qui permet de construire des blocs de codes de redondance en \u00e9crivant un programme informatique ad\u00e9quat. Ce m\u00eame syst\u00e8me d'\u00e9quations peut \u00eatre utilis\u00e9 pour r\u00e9cup\u00e9rer des donn\u00e9es.<\/p>\n

    <\/p>\n

    * Ce n'est pas une d\u00e9finition stricte, plut\u00f4t une description.<\/p>\n

    <\/p>\n

    Comment r\u00e9cup\u00e9rer des donn\u00e9es<\/h3>\n

    <\/p>\n

    La r\u00e9cup\u00e9ration est n\u00e9cessaire lorsque, dans n + m blocs, une partie des blocs est manquante. Cela peut concerner \u00e0 la fois des blocs de donn\u00e9es et des blocs de codes de redondance. L'absence de blocs de donn\u00e9es et\/ou de blocs de codes de redondance signifie que dans les \u00e9quations ci-dessus, les variables correspondantes x et\/ou p sont inconnues.<\/p>\n

    <\/p>\n

    Les \u00e9quations pour les codes de Reed-Solomon peuvent \u00eatre consid\u00e9r\u00e9es comme un syst\u00e8me d'\u00e9quations dans lequel toutes les valeurs alpha, beta, gamma, delta sont des constantes, tous les x et p correspondant aux blocs disponibles sont des variables connues, tandis que les autres x et p sont inconnus.<\/p>\n

    <\/p>\n

    Par exemple, supposons que les blocs de donn\u00e9es 1, 2, 3 et le bloc de codes de redondance 2 soient indisponibles, alors pour le i\u00e8me groupe de mots, le syst\u00e8me d'\u00e9quations suivant sera le suivant (les inconnues sont marqu\u00e9es en rouge) :<\/p>\n

    <\/p>\n

    \"Codes<\/p>\n

    <\/p>\n

    Nous avons un syst\u00e8me de 4 \u00e9quations avec 4 inconnues, ce qui signifie que nous pouvons le r\u00e9soudre et r\u00e9cup\u00e9rer les donn\u00e9es !<\/p>\n

    <\/p>\n

    De ce syst\u00e8me d'\u00e9quations d\u00e9coulent plusieurs conclusions sur la restauration des donn\u00e9es pour les codes de Reed-Solomon (n blocs de donn\u00e9es, m blocs de codes de redondance) :<\/p>\n

    <\/p>\n