Voici à quoi ressemble la redondance
Les codes de redondance* sont largement utilisés dans les systèmes informatiques pour augmenter la fiabilité du stockage des données. Dans Yandex, ils sont utilisés dans de nombreux projets. Par exemple, l'utilisation de codes de redondance au lieu de la réplication dans notre stockage d'objets interne permet d'économiser des millions sans sacrifier la fiabilité. Mais malgré leur utilisation répandue, les descriptions claires du fonctionnement des codes de redondance sont très rares. Ceux qui veulent comprendre se trouvent confrontés à peu près à ce qui suit (de ):
Je m'appelle Vadim, chez Yandex, je développe un MDS de stockage d'objets interne. Dans cet article, je décrirai avec des mots simples les fondements théoriques des codes de redondance (codes Reed-Solomon et LRC). Je vais vous expliquer comment cela fonctionne, sans mathématiques complexes ni termes rares. À la fin, je donnerai des exemples d'utilisation de codes de redondance dans Yandex.
Je n'examinerai pas un certain nombre de détails mathématiques en détail, mais je fournirai des liens pour ceux qui souhaitent approfondir. Je noterai également que certaines définitions mathématiques peuvent ne pas être strictes, puisque l'article n'est pas destiné aux mathématiciens, mais aux ingénieurs qui souhaitent comprendre l'essence du problème.
* Dans la littérature anglophone, les codes de redondance sont souvent appelés codes d'effacement.
1. L'essence des codes de licenciement
L'essence de tous les codes de redondance est extrêmement simple : stocker (ou transmettre) les données afin qu'elles ne soient pas perdues en cas d'erreurs (pannes de disque, erreurs de transfert de données, etc.).
Dans la plupart des* codes de redondance, les données sont divisées en n blocs de données, pour lesquels m blocs de codes de redondance sont comptés, ce qui donne un total de n + m blocs. Les codes de redondance sont construits de telle manière que n blocs de données peuvent être récupérés en utilisant seulement une partie de n + m blocs. Ensuite, nous ne considérerons que les codes de redondance de blocs, c'est-à-dire ceux dans lesquels les données sont divisées en blocs.
Pour récupérer les n blocs de données, vous devez avoir au moins n blocs sur n + m, car vous ne pouvez pas obtenir n blocs en ayant seulement n-1 bloc (dans ce cas, vous devrez prendre 1 bloc « dans un bloc mince). air"). N blocs aléatoires de n + m blocs sont-ils suffisants pour récupérer toutes les données ? Cela dépend du type de codes de redondance, par exemple, les codes Reed-Solomon vous permettent de récupérer toutes les données en utilisant n blocs arbitraires, mais les codes de redondance LRC ne le font pas toujours.
Stockage de données
Dans les systèmes de stockage de données, en règle générale, chacun des blocs de données et blocs de codes de redondance est écrit sur un disque séparé. Ensuite, si un disque arbitraire tombe en panne, les données originales peuvent toujours être restaurées et lues. Les données peuvent être récupérées même si plusieurs disques tombent en panne en même temps.
Transfert de données
Les codes de redondance peuvent être utilisés pour transmettre des données de manière fiable sur un réseau peu fiable. Les données transmises sont divisées en blocs et des codes de redondance sont calculés pour eux. Les blocs de données et les blocs de codes de redondance sont transmis sur le réseau. Si des erreurs se produisent dans des blocs arbitraires (jusqu'à un certain nombre de blocs), les données peuvent toujours être transmises sur le réseau sans erreur. Les codes Reed-Solomon, par exemple, sont utilisés pour transmettre des données sur des lignes de communication optiques et dans les communications par satellite.
* Il existe également des codes de redondance dans lesquels les données ne sont pas divisées en blocs, tels que les codes de Hamming et les codes CRC, largement utilisés pour la transmission de données dans les réseaux Ethernet. Ce sont des codes de codage correcteur d'erreurs, ils sont conçus pour détecter les erreurs, et non pour les corriger (le code de Hamming permet également une correction partielle des erreurs).
2. Codes Reed-Salomon
Les codes Reed-Solomon sont l'un des codes de redondance les plus utilisés, inventés dans les années 1960 et largement utilisés pour la première fois dans les années 1980 pour la production en série de disques compacts.
Il y a deux questions clés pour comprendre les codes de Reed-Solomon : 1) comment créer des blocs de codes de redondance ; 2) comment récupérer des données à l'aide de blocs de code de redondance. Trouvons des réponses à ces questions.
Par souci de simplicité, nous supposerons en outre que n=6 et m=4. D'autres schémas sont considérés par analogie.
Comment créer des blocs de code de redondance
Chaque bloc de codes de redondance est compté indépendamment des autres. Les n blocs de données sont utilisés pour compter chaque bloc. Dans le diagramme ci-dessous, X1-X6 sont des blocs de données, P1-P4 sont des blocs de codes de redondance.
Tous les blocs de données doivent avoir la même taille et zéro bit peut être utilisé pour l'alignement. Les blocs de code de redondance résultants auront la même taille que les blocs de données. Tous les blocs de données sont divisés en mots (par exemple 16 bits). Disons que nous divisons les blocs de données en k mots. Ensuite, tous les blocs de codes de redondance seront également divisés en k mots.
Pour compter le ième mot de chaque bloc de redondance, les ième mots de tous les blocs de données seront utilisés. Ils seront calculés selon la formule suivante :
Ici, les valeurs x sont les mots des blocs de données, p sont les mots des blocs de codes de redondance, tous les alpha, bêta, gamma et delta sont des nombres spécialement sélectionnés qui sont les mêmes pour tous les i. Il faut dire d'emblée que toutes ces valeurs ne sont pas des nombres ordinaires, mais des éléments du corps de Galois ; les opérations +, -, *, / ne sont pas des opérations familières à tous, mais des opérations spéciales introduites sur des éléments du corps de Galois. champ.
Pourquoi les champs de Galois sont-ils nécessaires ?
Il semblerait que tout soit simple : on divise les données en blocs, les blocs en mots, en utilisant les mots des blocs de données on compte les mots des blocs de code de redondance - on obtient des blocs de code de redondance. En général, voici comment cela fonctionne, mais le diable se cache dans les détails :
- Comme indiqué ci-dessus, la taille des mots est fixe, dans notre exemple 16 bits. Les formules ci-dessus pour les codes de Reed-Solomon sont telles que lors de l'utilisation d'entiers ordinaires, le résultat du calcul de p peut ne pas être représentable à l'aide d'un mot de taille valide.
- Lors de la récupération des données, les formules ci-dessus seront considérées comme un système d'équations qui doivent être résolues afin de récupérer les données. Au cours du processus de résolution, il peut être nécessaire de diviser des nombres entiers les uns par les autres, ce qui donne lieu à un nombre réel qui ne peut pas être représenté avec précision dans la mémoire de l'ordinateur.
Ces problèmes empêchent l'utilisation d'entiers pour les codes de Reed-Solomon. La solution au problème est originale, elle peut être décrite ainsi : imaginons des nombres spéciaux qui peuvent être représentés à l'aide de mots de la longueur requise (par exemple, 16 bits), et le résultat de l'exécution de toutes les opérations sur lesquelles (addition , soustraction, multiplication, division) seront également présentés dans la mémoire de l'ordinateur à l'aide de mots de la longueur requise.
Ces nombres « spéciaux » sont étudiés depuis longtemps par les mathématiques : ils sont appelés champs. Un champ est un ensemble d'éléments pour lesquels sont définies des opérations d'addition, de soustraction, de multiplication et de division.
Les champs de Galois* sont des champs pour lesquels il existe un résultat unique de chaque opération (+, -, *, /) pour deux éléments quelconques du champ. Les champs de Galois peuvent être construits pour des nombres qui sont des puissances de 2 : 2, 4, 8, 16, etc. (en fait des puissances de n'importe quel nombre premier p, mais en pratique nous ne nous intéressons qu'aux puissances de 2). Par exemple, pour des mots de 16 bits, il s'agit d'un champ contenant 65 536 éléments, pour chaque paire dont vous pouvez retrouver le résultat de n'importe quelle opération (+, -, *, /). Les valeurs x, p, alpha, bêta, gamma, delta des équations ci-dessus seront considérées comme des éléments du champ de Galois pour les calculs.
Ainsi, nous disposons d’un système d’équations avec lequel nous pouvons construire des blocs de codes de redondance en écrivant un programme informatique approprié. En utilisant le même système d'équations, vous pouvez effectuer une récupération de données.
* Ceci n'est pas une définition stricte, mais plutôt une description.
Comment récupérer des données
La restauration est nécessaire lorsque certains des n + m blocs sont manquants. Il peut s'agir à la fois de blocs de données et de blocs de codes de redondance. L'absence de blocs de données et/ou de blocs de codes de redondance signifiera que les variables x et/ou p correspondantes sont inconnues dans les équations ci-dessus.
Les équations des codes de Reed-Solomon peuvent être considérées comme un système d'équations dans lequel toutes les valeurs alpha, bêta, gamma, delta sont des constantes, tous les x et p correspondant aux blocs disponibles sont des variables connues et les x et p restants sont inconnus.
Par exemple, si les blocs de données 1, 2, 3 et le bloc de code de redondance 2 ne sont pas disponibles, alors pour le i-ème groupe de mots, il y aura le système d'équations suivant (les inconnues sont marquées en rouge) :
Nous avons un système de 4 équations à 4 inconnues, ce qui signifie que nous pouvons le résoudre et restaurer les données !
De ce système d'équations découlent un certain nombre de conclusions sur la récupération de données pour les codes de Reed-Solomon (n blocs de données, m blocs de codes de redondance) :
- Les données peuvent être récupérées si m blocs ou moins sont perdus. Si m+1 blocs ou plus sont perdus, les données ne peuvent pas être restaurées : il est impossible de résoudre un système de m équations avec m + 1 inconnues.
- Pour récupérer ne serait-ce qu'un seul bloc de données, vous devez utiliser n'importe lequel des n blocs restants et vous pouvez utiliser n'importe lequel des codes de redondance.
Que dois-je savoir d'autre?
Dans la description ci-dessus, j'évite un certain nombre de questions importantes qui nécessitent une analyse plus approfondie des mathématiques. En particulier, je ne dis rien sur les points suivants :
- Le système d'équations des codes de Reed-Solomon doit avoir une solution (unique) pour toute combinaison d'inconnues (pas plus de m inconnues). Sur la base de cette exigence, les valeurs alpha, bêta, gamma et delta sont sélectionnées.
- Un système d’équations doit pouvoir être automatiquement construit (en fonction des blocs indisponibles) et résolu.
- Nous devons construire un champ de Galois : pour une taille de mot donnée, être capable de trouver le résultat de n'importe quelle opération (+, -, *, /) pour deux éléments quelconques.
À la fin de l’article se trouvent des références à la littérature sur ces questions importantes.
Choix de n et m
Comment choisir n et m en pratique ? En pratique, dans les systèmes de stockage de données, des codes de redondance sont utilisés pour économiser de l'espace, donc m est toujours choisi inférieur à n. Leurs valeurs spécifiques dépendent d'un certain nombre de facteurs, notamment :
- Fiabilité du stockage des données. Plus m est grand, plus le nombre de pannes de disque pouvant être survécu est élevé, c'est-à-dire plus la fiabilité est élevée.
- Stockage redondant. Plus le rapport m/n est élevé, plus la redondance du stockage sera élevée et plus le système sera cher.
- Délai de traitement de la demande. Plus la somme n + m est grande, plus le temps de réponse aux requêtes sera long. Puisque la lecture des données (lors de la récupération) nécessite la lecture de n blocs stockés sur n disques différents, le temps de lecture sera déterminé par le disque le plus lent.
De plus, le stockage des données dans plusieurs DC impose des restrictions supplémentaires sur le choix de n et m : si 1 DC est éteint, les données doivent toujours être disponibles en lecture. Par exemple, lors du stockage de données dans 3 DC, la condition suivante doit être remplie : m >= n/2, sinon il peut y avoir une situation où les données ne sont pas disponibles pour la lecture lorsqu'1 DC est éteint.
3. LRC - Codes de reconstruction locaux
Pour récupérer des données à l'aide des codes Reed-Solomon, vous devez utiliser n blocs de données arbitraires. Il s'agit d'un inconvénient très important pour les systèmes de stockage de données distribués, car pour restaurer les données sur un disque cassé, vous devrez lire les données de la plupart des autres, créant une charge supplémentaire importante sur les disques et le réseau.
Les erreurs les plus courantes sont l'inaccessibilité d'un bloc de données en raison d'une panne ou d'une surcharge d'un disque. Est-il possible de réduire d'une manière ou d'une autre la charge excessive pour la récupération de données dans ce cas (le plus courant) ? Il s'avère que c'est possible : il existe des codes de redondance LRC spécialement prévus à cet effet.
Les LRC (Local Reconstruction Codes) sont des codes de redondance inventés par Microsoft pour être utilisés dans Windows Azure Storage. L'idée de LRC est aussi simple que possible : divisez tous les blocs de données en deux (ou plus) groupes et lisez une partie des blocs de code de redondance pour chaque groupe séparément. Ensuite, certains blocs de codes de redondance seront comptés en utilisant tous les blocs de données (dans LRC, ils sont appelés codes de redondance globaux), et certains - en utilisant l'un des deux groupes de blocs de données (ils sont appelés codes de redondance locaux).
LRC est désigné par trois nombres : nrl, où n est le nombre de blocs de données, r est le nombre de blocs de codes de redondance globale, l est le nombre de blocs de codes de redondance locale. Pour lire des données lorsqu'un bloc de données n'est pas disponible, vous devez lire uniquement n/l blocs - c'est l fois moins que dans les codes Reed-Solomon.
Par exemple, considérons le schéma LRC 6-2-2. X1–X6 — 6 blocs de données, P1, P2 — 2 blocs de redondance globale, P3, P4 — 2 blocs de redondance locale.
Les blocs de code de redondance P1, P2 sont comptés en utilisant tous les blocs de données. Bloc de code de redondance P3 - utilisant les blocs de données X1-X3, bloc de code de redondance P4 - utilisant les blocs de données X4-X6.
Le reste se fait en LRC par analogie avec les codes de Reed-Solomon. Les équations de comptage des mots des blocs de codes de redondance seront :
Pour sélectionner les nombres alpha, bêta, gamma, delta, un certain nombre de conditions doivent être remplies pour garantir la possibilité de récupération des données (c'est-à-dire la résolution du système d'équations). Vous pouvez en savoir plus à leur sujet dans .
En pratique également, l'opération XOR est utilisée pour calculer les codes de redondance locaux P3, P4.
Un certain nombre de conclusions découlent du système d'équations pour LRC :
- Pour récupérer 1 bloc de données, il suffit de lire n/l blocs (n/2 dans notre exemple).
- Si les blocs r + l ne sont pas disponibles et que tous les blocs sont inclus dans un groupe, les données ne peuvent pas être restaurées. C'est facile à expliquer avec un exemple. Supposons que les blocs X1 à X3 et P3 soient indisponibles : ce sont des blocs r + l du même groupe, 4 dans notre cas. Nous avons alors un système de 3 équations à 4 inconnues qui ne peuvent être résolues.
- Dans tous les autres cas d'indisponibilité des blocs r + l (lorsqu'au moins un bloc est disponible dans chaque groupe), les données du LRC peuvent être restaurées.
Ainsi, LRC surpasse les codes Reed-Solomon en matière de récupération de données après des erreurs uniques. Dans les codes Reed-Solomon, pour récupérer ne serait-ce qu'un bloc de données, il faut utiliser n blocs, et dans LRC, pour récupérer un bloc de données, il suffit d'utiliser n/l blocs (n/2 dans notre exemple). D'autre part, LRC est inférieur aux codes de Reed-Solomon en termes de nombre maximum d'erreurs tolérées. Dans les exemples ci-dessus, les codes Reed-Solomon peuvent récupérer des données pour 4 erreurs quelconques, et pour LRC, il existe 2 combinaisons de 4 erreurs lorsque les données ne peuvent pas être récupérées.
Ce qui est le plus important dépend de la situation spécifique, mais souvent les économies de charge excédentaire réalisées par le LRC l'emportent sur le stockage légèrement moins fiable.
4. Autres codes de redondance
Outre les codes Reed-Solomon et LRC, il existe de nombreux autres codes de redondance. Différents codes de redondance utilisent des mathématiques différentes. Voici quelques autres codes de redondance :
- Code de redondance utilisant l'opérateur XOR. L'opération XOR est effectuée sur n blocs de données et 1 bloc de codes de redondance est obtenu, c'est-à-dire un schéma n+1 (n blocs de données, 1 code de redondance). Utilisé dans , où les blocs de données et les codes de redondance sont écrits cycliquement sur tous les disques de la baie.
- Algorithme pair-impair basé sur l'opération XOR. Permet de construire 2 blocs de codes de redondance, c'est-à-dire le schéma n+2.
- Algorithme STAR basé sur l'opération XOR. Permet de construire 3 blocs de codes de redondance, c'est-à-dire le schéma n+3.
- Les codes Pyramide sont un autre code de redondance de Microsoft.
5. Utiliser dans Yandex
Un certain nombre de projets d'infrastructure Yandex utilisent des codes de redondance pour un stockage fiable des données. Voici quelques exemples:
- Stockage d'objets interne MDS, dont j'ai parlé au début de l'article.
- — Système MapReduce de Yandex.
- (Yandex DataBase) - nouvelle base de données distribuée SQL.
MDS utilise les codes de redondance LRC, schéma 8-2-2. Les données avec des codes de redondance sont écrites sur 12 disques différents dans différents serveurs dans 3 contrôleurs de domaine différents : 4 serveurs dans chaque contrôleur de domaine. En savoir plus à ce sujet dans .
YT utilise à la fois les codes Reed-Solomon (schéma 6-3), qui ont été les premiers à implémenter, et les codes de redondance LRC (schéma 12-2-2), LRC étant la méthode de stockage préférée.
YDB utilise des codes de redondance pairs et impairs (Figure 4-2). À propos des codes de redondance dans YDB déjà .
L'utilisation de différents schémas de codes de redondance est due aux différentes exigences des systèmes. Par exemple, dans MDS, les données stockées à l'aide de LRC sont placées dans 3 DC à la fois. Il est important pour nous que les données restent disponibles pour la lecture si l'un des contrôleurs de domaine tombe en panne. Par conséquent, les blocs doivent être répartis entre les contrôleurs de domaine de sorte que si un contrôleur de domaine n'est pas disponible, le nombre de blocs inaccessibles ne dépasse pas celui autorisé. Dans le schéma 1-8-2, vous pouvez placer 2 blocs dans chaque DC, puis lorsqu'un DC est désactivé, 4 blocs seront indisponibles et les données pourront être lues. Quel que soit le schéma que nous choisissons en le plaçant dans 4 DC, il devrait dans tous les cas y avoir (r + l) / n >= 3, c'est-à-dire que la redondance du stockage sera d'au moins 0,5 %.
Dans YT, la situation est différente : chaque cluster YT est entièrement situé dans 1 DC (différents clusters dans différents DC), il n'y a donc pas de telle restriction. Le schéma 12-2-2 offre une redondance de 33 %, c'est-à-dire que le stockage des données est moins cher et peut également survivre jusqu'à 4 pannes de disque simultanées, tout comme le schéma MDS.
Il existe de nombreuses autres fonctionnalités liées à l'utilisation de codes de redondance dans les systèmes de stockage et de traitement de données : nuances de récupération de données, impact de la récupération sur le temps d'exécution des requêtes, fonctionnalités d'enregistrement de données, etc. Je vais parler séparément de ces fonctionnalités et d'autres. de l'utilisation des codes de licenciement dans la pratique, si le sujet est intéressant.
6. Liens
- Une série d'articles sur les codes de Reed-Solomon et les champs de Galois :
Ils examinent plus en profondeur les mathématiques dans un langage accessible. - Article de Microsoft sur LRC :
La section 2 explique brièvement la théorie, puis discute des expériences pratiques avec le LRC. - Schéma pair-impair :
- Schéma STAR :
- Codes pyramidaux :
- Codes de redondance dans MDS :
- Codes de redondance dans YT :
- Codes de redondance dans YDB :
Source: habr.com