La technique d’Erasure Coding pour les systèmes distribués
(transactional.blog)- L’Erasure Coding est une technique de compromis entre efficacité de stockage et tolérance aux pannes, qui découpe les données en fragments et en parités afin de résister aux défaillances avec moins d’espace qu’une réplication complète
- Le modèle de base est k+m=n : k est le nombre de fragments de données nécessaires à la reconstruction, m le nombre de fragments de parité et donc le nombre de pannes tolérables, et n le nombre total de fragments
- Dans les stockages d’objets et de blobs, on peut utiliser une configuration comme 10+5 au lieu d’une triple réplication complète, pour répartir de petits fragments sur davantage de serveurs et réduire le volume stocké
- Les systèmes à quorum ne peuvent pas beaucoup réduire le stockage avec une simple règle de majorité, et des approches comme HRaft qui basculent entre 3+2, 2+2, 1+2 selon le nombre de réplicas disponibles introduisent des coûts de réencodage et de provisionnement de capacité
- En production, il faut vérifier à la fois la variation du coût de décodage selon la combinaison de fragments reçus, et les différences d’exigences en matière de métadonnées et d’alignement entre Jerasure, ISA-L et liberasurecode
Le compromis fondamental entre efficacité de stockage et tolérance aux pannes
- Il existe deux approches extrêmes pour stocker un fichier sur N serveurs
- si l’on place une copie complète du fichier sur chaque serveur, le fichier n’est pas perdu même si N-1 serveurs disparaissent, mais le coût de stockage est maximal
- si l’on découpe le fichier en N fragments de taille identique et qu’on en stocke un sur chaque serveur, l’efficacité de stockage est optimale, mais il faut lire les N fragments pour reconstituer le fichier
- L’Erasure Coding permet d’ajuster le compromis entre efficacité de stockage et tolérance aux pannes entre ces deux extrêmes
- on peut construire un code répondant à l’objectif suivant : « découper le fichier en N fragments, tout en permettant la reconstruction même si M fragments sont détruits »
- il fournit les fragments de taille minimale nécessaires pour atteindre cet objectif
- L’intuition la plus simple est l’exemple où, parmi 3 serveurs, la lecture de n’importe lesquels des 2 suffit à récupérer le fichier complet
- on découpe le fichier en deux fragments A et B
- on crée un troisième fragment C égal à A ⊕ B
- si l’on lit A et B, on les concatène directement ; si l’on lit A et C, ou B et C, on reconstruit le fragment manquant via XOR
- Tous les Erasure Codes généralisent ce schéma en séparant fragments de données et fragments de parité
Le modèle k+m=n et le surcoût de stockage
- Une configuration d’Erasure Code s’exprime sous la forme k + m = n
- k : nombre de fragments dans lesquels les données sont découpées ; il faut lire au moins k fragments pour reconstruire la valeur
- m : nombre de fragments de parité générés ; c’est aussi le nombre de lectures incomplètes ou de pannes que le système peut tolérer
- n : nombre total de fragments produits
- La taille d’un fragment résultant est en général de 1/k de la taille du fichier d’origine
- Un Erasure Code est généralement désigné par le tuple
k+m- selon les publications, les noms de variables ne sont pas toujours cohérents
x+ydésigne x fragments de données et y fragments de parité
- Cette approche attire les fournisseurs de stockage, car elle offre de la tolérance aux pannes avec un faible surcoût de stockage
- Backblaze B2 utilise 17+3 et tolère 3 pannes avec un coût de stockage de 1,18x
- OVH Cloud utilise un code 8+4 et tolère 4 pannes avec un coût de stockage de 1,5x
- Scaleway utilise un code 6+3 et tolère 3 pannes avec un coût de stockage de 1,5x
- Le principal coût est l’échange entre réduction de l’espace de stockage et augmentation du nombre de requêtes de lecture
- au lieu de lire l’équivalent de la taille du fichier sur un seul disque, on envoie des requêtes à k+m disques
- les systèmes de stockage destinés à des données peu consultées sont bien adaptés : la charge IOPS supplémentaire reste relativement faible, tandis que les gains sur le stockage sont importants
Portée des algorithmes et codes MDS
- « Erasure Coding » ne désigne pas un algorithme unique, mais une famille d’algorithmes
- Les codes de Reed-Solomon peuvent généralement être utilisés pour implémenter des Erasure Codes avec des configurations arbitraires k+m
- Il existe aussi une correspondance avec le RAID
- RAID-0 correspond à un Erasure Coding k+0
- RAID-1 correspond à un Erasure Coding 1+m
- RAID-4 et RAID-5 correspondent à des formes légèrement différentes de k+1 Erasure Coding
- RAID-6 correspond à un Erasure Coding k+2
- Le périmètre de cet article est celui des Erasure Codes MDS (Minimum Distance Separable)
- les codes MDS offrent une propriété proche d’un quorum, en tolérant la perte de n’importe quels m fragments
- d’autres familles d’Erasure Codes peuvent permettre, selon certaines combinaisons, une reconstruction avec moins de m fragments perdus, mais en exiger davantage dans d’autres cas
- Si l’on connaît les schémas de panne attendus, il peut être avantageux d’utiliser des codes qui reconstruisent les défaillances fréquentes avec moins de fragments, et les cas exceptionnels avec davantage
- les Local Reconstruction Codes et les SD Codes d’Azure Storage sont cités comme exemples dans cette direction
Applications au stockage objet et aux caches
- Le cas d’usage le plus direct consiste à réduire les coûts de stockage et augmenter la durabilité dans des systèmes avec un ensemble fixe de réplicas
- exemples : stockage de blobs, stockage objet ou stockage NFS
- un service de métadonnées associe un chemin de fichier aux serveurs qui stockent ce fichier
- Au lieu de 3 réplicas contenant chacun le fichier complet, 15 réplicas peuvent stocker les fragments d’un fichier encodé en 10+5
- le volume total stocké est divisé par deux
- la tolérance aux pannes est plus que doublée
- Un schéma plus général consiste à « stocker les données sur X+m réplicas avec un Erasure Code X+m au lieu de les stocker sur X serveurs »
- L’exemple de système de cache de Marc Brooker applique ce schéma au cache
- au lieu de choisir un serveur de cache parmi k via consistent hashing, on utilise un Erasure Code k+m sur k+m serveurs de cache
- il n’est pas nécessaire d’attendre les m réponses les plus lentes
- on peut améliorer à la fois l’espace de stockage et la latence en queue de distribution
- Ces gains ont pour contrepartie une augmentation des IOPS/QPS ou de la charge CPU
- cela suppose que la ressource limitante du système soit la capacité de stockage, avec une marge côté CPU
- sur un système déjà proche de sa limite CPU, ce n’est pas forcément une idée d’optimisation des coûts
Les limites des systèmes à quorum et HRaft
- Dans un quorum de majorité simple avec 5 réplicas, où lectures et écritures exigent au moins 3 réponses, le modèle s’aligne bien côté lecture avec un Erasure Code 3+2
- en effet, n’importe quel ensemble de 3 réplicas suffit à terminer la lecture
- Comme une écriture peut être validée dès que 3 réplicas quelconques l’ont reçue, un Erasure Code fixe ne peut utiliser qu’un code 1+2
- 1+2 équivaut à 3 copies complètes du fichier
- il n’y a donc aucun gain de stockage avec une application naïve
- RS-Paxos estime que l’application d’Erasure Codes à Paxos n’est avantageuse que lorsque l’intersection entre deux quorums dépasse 1 réplica
- par exemple, avec 7 réplicas où lecture et écriture exigent toutes deux au moins 5 réponses, on peut appliquer un code 3+2 tout en tolérant 2 pannes
- plus généralement, pour N réplicas et une tolérance aux pannes souhaitée f, le meilleur schéma possible en Erasure Coding fixe est (N-2f)+f
- HRaft ajuste le codage en fonction du nombre de réplicas disponibles, même avec un quorum de majorité simple
- si les 5 sont disponibles : 3+2
- si 4 sont disponibles : 2+2
- si 3 sont disponibles : 1+2
- Cette approche adaptative offre un potentiel d’amélioration, mais avec de fortes contraintes opérationnelles
- chaque écriture estime de manière optimiste le nombre de réplicas actuellement disponibles
- si un réplica ne valide pas l’écriture de manière inattendue, il faut réencoder l’écriture puis la renvoyer à tous les réplicas
- même après deux pannes, lorsqu’on fonctionne en 1+2, il faut avoir provisionné une configuration de réplicas capable de stocker la valeur complète, afin qu’un manque d’espace disque ou de débit ne casse pas la disponibilité
- si les pannes sont rares et rapidement réparées, l’encodage adaptatif de HRaft peut apporter des gains importants
Bibliothèques et exemples d’usage
- Pour les calculs d’Erasure Coding, il existe la bibliothèque standard mature Jerasure
- Sur les processeurs Intel récents, la Intelligent Storage Acceleration Library d’Intel est une bibliothèque optimisée SIMD, régulièrement bien classée dans les benchmarks
- En Python, on peut accéder à des implémentations d’Erasure Coding via pyeclib
- l’exemple utilise le driver
liberasurecode_rs_vand - chaque fragment est préfixé par des métadonnées permettant d’identifier sa position
- quelques octets supplémentaires sont également présents
- l’exemple utilise le driver
- Les résultats d’exemple de HRaft selon le nombre de réplicas disponibles sont les suivants
- 3+2, original de 10000 octets : 5 fragments, 3355 octets par fragment, 16775 octets réels au total, efficacité de 59,61 %
- 2+2, original de 10000 octets : 4 fragments, 5021 octets par fragment, 20084 octets réels au total, efficacité de 49,79 %
- 1+2, original de 10000 octets : 3 fragments, 10021 octets par fragment, 30063 octets réels au total, efficacité de 33,26 %
- Un encodage Erasure 1+2 équivaut à 3 copies complètes des données, donc au même résultat que sans Erasure Encoding
Coût du décodage et différences entre implémentations
- Les performances du décodage varient selon le nombre de fragments de données à reconstruire
- décoder un code 3+2 à partir de 3 fragments de données est presque trivial d’un point de vue calculatoire
- décoder le même fichier à partir de 2 fragments de données et 1 fragment de parité demande de résoudre un système d’équations linéaires par élimination de Gauss
- plus le nombre de fragments de parité nécessaires augmente, plus le coût de calcul augmente
- Dans un système à quorum utilisant l’Erasure Coding, le coût CPU peut donc varier selon les réplicas qui ont effectivement répondu
- liberasurecode abstrait plusieurs bibliothèques d’implémentation courantes, mais cela ne signifie pas que leurs comportements sont équivalents
- deux codes notés 3+2 ne sont pas nécessairement construits avec les mêmes mathématiques
- liberasurecode ajoute des métadonnées nécessaires non seulement aux opérations d’algèbre linéaire, mais aussi à la configuration et à l’utilisation du décodeur
- ces métadonnées ne peuvent pas être désactivées ni modifiées
- En utilisant directement Jerasure ou ISA-L, on peut ne manipuler que les données encodées
- toutefois, l’API exige de préciser pour chaque fragment s’il s’agit du Nième fragment de données ou de parité ; l’index doit donc être conservé comme métadonnée d’une manière ou d’une autre
- Jerasure et ISA-L diffèrent aussi sur les exigences d’alignement
- Jerasure applique une permutation à la sortie attendue de l’algèbre linéaire
- Jerasure ne permet pas de lire dans le désordre un sous-ensemble ou un sur-ensemble de ce qui a été encodé
- ISA-L n’applique pas cette permutation, ce qui permet de décoder des sous-ensembles ou sur-ensembles non ordonnés
- D’autres implémentations sont également possibles
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- si cela devient un goulot d’étranglement, on peut chercher une bibliothèque mieux optimisée pour un cas d’usage donné, mais ISA-L est généralement largement suffisante
Choix d’algorithme et construction mathématique
- En pratique, on peut utiliser un Erasure Code comme une fonction magique qui transforme un fichier en n fragments puis permet de le reconstruire
- Une configuration en n fragments repose en général sur de l’algèbre linéaire sur des corps de Galois
- il n’est pas nécessaire de comprendre ces mathématiques pour utiliser l’Erasure Coding efficacement en production
- La plupart des codes MDS se calculent par multiplication matricielle
- les additions sont remplacées par des XOR
- les multiplications sont remplacées par des multiplications plus coûteuses dans GF(256)
- Pour les cas particuliers avec 1 à 3 fragments de parité, il existe des algorithmes spécialisés fondés uniquement sur XOR plutôt que sur Reed-Solomon
- m=1 : un unique fragment de parité égal au XOR de tous les fragments de données
- m=2 : équivalent à RAID-6 ; sont mentionnés Liberation codes, HDP codes, EVENODD et X-Codes
- m=3 : possible avec STAR coding
- Dans le cas général, on utilise des familles de Reed-Solomon
- des constructions à base de matrices de Vandermonde ou de Cauchy sont employées
- l’objectif est que le bloc supérieur k×k soit la matrice identité afin de préserver chaque fragment de données, tout en garantissant qu’après suppression de m lignes, la matrice reste inversible
- l’encodage consiste à multiplier par cette matrice ; le décodage consiste à supprimer les lignes correspondant aux fragments effacés, puis à résoudre le système d’équations linéaires
- L’élimination de Gauss utilisée par ISA-L est la méthode de décodage la plus simple, mais aussi la plus lente
- avec des matrices de Cauchy, on peut faire mieux, ce qu’utilise catid/cm256
- la méthode la plus rapide à l’heure actuelle semble être celle implémentée dans catid/leopard, qui utilise la Fast Fourier Transform pour l’encodage comme pour le décodage
Étapes d’optimisation des implémentations
- Il existe plusieurs niveaux pour accélérer une implémentation d’Erasure Code compatible avec des configurations arbitraires k+m
- La première étape consiste à implémenter l’algorithme en C et à s’appuyer sur l’auto-vectorisation du compilateur
- c’est l’approche la plus simple et la plus portable
- l’usage de
restrictet de drapeaux de compilation spécifiques à l’architecture comme-march=nativeest important
- La deuxième consiste à abstraire les détails de la plateforme via des bibliothèques de vectorisation ou des intrinsics compilateur
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- les builtins d’extension vectorielle de GCC
- Le cœur de l’encodage et du décodage repose sur les multiplications et additions dans les corps de Galois
- parmi les bibliothèques optimisées citées figurent catid/gf256 et James Plank’s Fast Galois Field Arithmetic Library
- La troisième étape consiste à écrire directement en vectorisé les fonctions critiques d’encodage et de décodage
- le projet PARPAR décrit des opérations rapides sur GF(256) dans fast-gf-multiplication et xor_depends work
- il y est résumé qu’un consensus existe selon lequel la multiplication GF fondée uniquement sur XOR est plus rapide que la multiplication par tables
- On peut aller plus loin en spécialisant le code pour une configuration k+m donnée
- on cherche des matrices d’encodage optimales et des plannings XOR adaptés à un polynôme GF spécifique et à une matrice d’encodage donnée
- on applique des optimisations sur les opérations, la mémoire et le cache
- on explore par programme les meilleurs ordonnancements d’instructions pour une architecture donnée
- Parmi les implémentations et ressources liées sont cités yuezato/xorslp_ec, Thesys-lab/tvm-ec et "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"
Pour aller plus loin
- Pour une introduction à l’algèbre linéaire derrière l’Erasure Coding, les ressources suivantes sont recommandées
- l’introduction de base de Backblaze
- "A Gentle Introduction to Erasure Codes" de Fred Akalin
- "Reed-Solomon Error Correcting Codes from the Bottom Up"
- le Tutorial on Reed-Solomon Error Correction Coding de la NASA
- Pour approfondir de manière plus large, il est proposé de commencer par les publications de James S. Plank
1 commentaires
Commentaires Hacker News
Je suis surpris que les codes fontaine à taux sans limite ne soient pas mentionnés. Si ce sujet vous intéresse, le Luby Transform Code devrait vous plaire : https://en.wikipedia.org/wiki/Luby_transform_code
Cet article offre aussi une vue d’ensemble plus détaillée : https://switzernet.com/people/emin-gabrielyan/060112-capilla...
Les codes LT sont utilisés comme code externe dans l’encodage RaptorQ en temps linéaire spécifié par la RFC6330 : https://www.rfc-editor.org/rfc/rfc6330
Ensuite, l’algorithme se divise en fait en deux parties : la seconde, la génération de blocs de récupération, est linéaire, mais la première prend un temps cubique par rapport au nombre de messages regroupés dans un bloc. Cela revient presque à une élimination gaussienne de matrices
On peut mettre en cache une partie de l’encodage et du décodage, mais l’encodage en temps linéaire de RaptorQ relève en pratique surtout du marketing
Il y a quelque temps, quelqu’un avait proposé un petit algorithme de code d’effacement mignon qui ne s’appuyait pas sur des disques rotatifs, mais sur le réseau multi-chemin
Je crois que cela s’appelait du codage réseau : l’idée était que, dans un réseau avec plusieurs chemins, au lieu d’attendre le fichier complet depuis le serveur principal, on pouvait recevoir depuis un upstream deux parties d’un fichier, ou un code d’effacement mélangeant deux fichiers, afin d’obtenir le fichier plus rapidement
J’imagine qu’il y a beaucoup de choses de ce genre derrière S3 ou d’autres systèmes de stockage cloud, surtout dans les niveaux de stockage peu fréquemment consultés. Cela dit, je ne connais pas réellement les systèmes internes d’AWS ou de GCP
À titre de référence, Freenet utilise au moins des fichiers codés avec FEC, ce qui donne de la flexibilité sur les fragments à recevoir et réduit le risque qu’un fichier entier soit corrompu parce qu’un seul fragment a disparu
Le codage d’effacement existe depuis très longtemps. Vous vous souvenez des fichiers PAR2 sur Usenet ? https://en.wikipedia.org/wiki/Parchive
Si le codage d’effacement vous intéresse, il vaut aussi la peine d’examiner de plus grands cas multidimensionnels. Il ne s’agit pas seulement d’encoder sur plusieurs disques, mais aussi de prendre en compte d’autres domaines de panne comme les racks, les salles, les datacenters ou les régions
L’objectif est de tolérer non seulement les défaillances de composants communs, mais aussi des pannes ou partitions système de plus grande ampleur. Bon article d’introduction : https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Si le câble optique transocéanique ne fait que 1 Tbps, déplacer toutes les données peut prendre plus de 6 mois
Je me demande si quelqu’un a déjà utilisé Wirehair dans un projet : https://github.com/catid/wirehair
Je me demande s’il est suffisamment bien défini pour servir de base standard à un projet d’archivage de gros fichiers / récupération de données que j’ai en tête depuis près de dix ans. Même si ce n’est pas un standard officiel, j’aimerais savoir s’il peut être utilisé comme un standard de facto.
Parmi les codes d’effacement pour grands blocs que j’ai trouvés jusqu’ici, c’est le seul qui combine des performances algorithmiques idéales ou presque idéales avec une API tout aussi adaptée. Pour mon usage, c’est donc une bonne boîte noire, contrairement à RaptorQ, où de petits détails fuient un peu partout et augmentent la complexité et la rigidité du reste de la pile.
Cela dit, Wirehair n’est pas une spécification mais l’implémentation d’une idée, et ressemble aussi à une implémentation expérimentale. Il paraît stable, mais tant que je n’aurai pas écrit moi-même une deuxième implémentation, ou qu’il ne sera pas assez largement utilisé pour que les angles morts de l’algorithme apparaissent, je crains qu’il ne soit pas facile de s’appuyer sur une spécification fiable ou de le porter vers une seconde implémentation.
Qualcomm pourrait toutefois prétendre qu’il tombe sous le coup des brevets RaptorQ, car les concepts sont liés. Les plus anciens de ces brevets devraient bientôt expirer, ou sont peut-être déjà expirés, mais je n’ai pas vérifié les enveloppes de fichiers récentes. Qualcomm a pris certains engagements de ne pas appliquer les brevets RaptorQ en dehors du sans-fil, mais je ne me souviens plus si cela ne concernait que les implémentations conformes.
Pour l’utiliser dans le protocole Bitcoin lui-même, il faudrait une spécification, et j’avais regardé ce que cela impliquerait. Moi-même et quelques développeurs Bitcoin sommes assez à l’aise avec la théorie des nombres et les codes correcteurs d’erreurs, mais ce travail ne nous attirait pas particulièrement. La structure de Wirehair comporte pas mal de détails ad hoc, et vu notre tempérament, nous risquerions de tomber dans un piège en essayant de l’améliorer.
L’intérêt pour un usage plus large des codes fontaine côté Bitcoin pourrait revenir, donc avec un peu d’attente, quelqu’un finira peut-être par rédiger une spécification.
Selon l’usage exact, https://github.com/catid/fecal peut aussi être intéressant. Si le nombre d’effacements attendu est très faible, il peut être plus rapide que Wirehair.
Leopard, mentionné dans l’article, n’est pas un code fontaine, mais sa taille de bloc est assez grande. C’est un avantage côté spécification : comme il s’agit simplement d’une implémentation très rapide d’un bon vieux code de Reed-Solomon, il suffirait peut-être de documenter le choix du corps et du générateur dans la spécification.
Exact. C’est la technologie clé derrière les pools Erasure Code de Ceph : https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Mais ce n’est pas sans contrepartie. On ne peut pas modifier après coup les paramètres de codage k, m ; il faut donc être sûr que ces valeurs resteront adaptées longtemps, ou bien repartir de zéro.
À cause de cette rigidité, la réplication reste le choix dominant pour le stockage de données à haute disponibilité et tolérant aux pannes.
Il se contente d’utiliser
--forceet laisse derrière lui un système de fichiers corrompu.C’est sans doute seulement le genre de drôle où « il fallait y être pour rire, et mieux valait que ce ne soit pas moi ».
Est-ce que les données produites en situation de panne, où seulement M éléments sur N sont disponibles, sont codées différemment de celles produites quand les N éléments sont disponibles ? Si oui, il faudrait sans doute un drapeau binaire indiquant « réencodage nécessaire quand N sera rétabli ».
Sinon, on se retrouve avec des fichiers dont la résilience n’est pas très bonne en cas de pertes arbitraires dans l’ensemble N.
Tout système de stockage distribué a besoin d’une sorte de bibliothécaire chargé de vérifier les stripes et de les remettre en ordre pour les sortir de l’état à risque.
Cela me fait aussi penser à l’algorithme de dispersion de l’information de Rabin, décrit dans cet article :
https://dl.acm.org/doi/10.1145/62044.62050
En pratique, est-ce seulement viable pour des charges de travail en lecture seule, ou avec énormément de lectures ?