Brevet FR3080196A1 — publié le 20191018

METHODES ET DISPOSITIFS DE CODAGE ET DE DECODAGE DE DONNEES Domaine de l'invention L'invention s'inscrit dans le domaine général des systèmes de stockage de données et la gestion des pannes dans ces systèmes. Plus particulièrement, l'invention concerne des méthodes et dispositifs de codage et de décodage de données permettant d'optimiser les opérations de lecture/écriture de données et d'optimiser le volume de données à transférer, nécessaires à la réparation d'un système de stockage suite à une panne. Etat de la Technique Au cours des dernières années, le volume de données numériques a augmenté considérablement, en raison de l'utilisation d'applications comme les réseaux sociaux, les e-mails, le partage de fichiers, de vidéos. Ainsi, les entreprises proposant des services en ligne, doivent gérer des volumes de données de plusieurs dizaines de pétabytes (1 PB = 1015 octets). Ces quantités de données qui ne cessent d'augmenter de façon exponentielle année après année, nécessitent d'être stockées de manière fiable. Les systèmes de stockage distribués ou (DSS) pour « Distributed Storage Systems » sont largement utilisés aujourd'hui pour fournir des solutions de stockage évolutives et fiables. Ces architectures tel qu'illustré sur la figure 1 comprennent de multiples noeuds de stockage (110, 112, 114) où des données sont stockées de manière distribuée. Un noeud de stockage peut être composé d'un (112) ou d'une pluralité d'équipements de stockage (110, 114). Chaque équipement de stockage d'un noeud qui en comporte plusieurs est lui-même désigné comme un noeud de stockage. En général, les équipements de stockage sont des disques de stockage. Un contrôleur (102) permet de gérer les communications de/vers les noeuds, dont les opérations de lecture/écriture disque à partir de requêtes reçues depuis un ordinateur (106) couplé au réseau de communication (104). 2 Or, il n'est pas rare que des disques, des équipements ou des noeuds de stockage tombent en panne, et il est courant que pour des milliers de noeuds, quelques dizaines de pannes en moyenne sont reportées par jour. Un système de stockage distribué doit assurer la protection des données dans le cas où un 5 ou plusieurs noeuds ou équipements de stockage ou disques tombent en pannent. Afin d'assurer la fiabilité et la disponibilité des données, les implémentations standard intègrent des solutions basées sur la redondance des données afin de pouvoir récupérer les données perdues en cas de panne. 10 Il existe plusieurs méthodes, listées ci-après, permettant d'apporter une fiabilité à un système de stockage : La Réplication est une des méthodes les plus répandues. Elle consiste à répliquer un même bloc de données sur plusieurs noeuds de stockage. Généralement, un même bloc de données est stocké dans n noeuds différents, 15 ce qui permet de tolérer n-1 pannes. En pratique, chaque bloc de données est stocké dans trois noeuds différents permettant de tolérer deux pannes. Même si la réplication offre une bonne tolérance aux pannes, elle a le désavantage d'afficher un surcoût de stockage ou « overhead » en anglais, qui peut être évalué à 200% dans les réplications à 3 noeuds. 20 Le Code d'effacement ou « Erasure Code ». Cette approche est basée sur l'utilisation des codes bien connus Reed-Solomon (RS). Chaque fichier de donnée est décomposé en k blocs de données auxquels sont ajoutés r blocs fonctions de parité générant k+r blocs de données, et l'on parle de code RS(k,r). Les k+r blocs de données sont stockés dans k+r noeuds différents, où k noeuds 25 stockent les k blocs originaux et r noeuds de parité stockent les r blocs fonctions de parité. Un code RS(k,r) a deux propriétés de base: n'importe quel bloc k de données parmi les k+r blocs est suffisant pour régénérer la donnée originelle, et r pannes, quelles qu'elles soient, peuvent être tolérées. En pratique, avec un code RS(10,4), chaque fichier de données est décomposé en 10 blocs, et 4 30 blocs fonctions de parité sont générés, permettant de tolérer jusqu'à quatre pannes. Les codes RS offrent une meilleure efficacité de stockage par rapport à la réplication, le surcoût de stockage étant évalué à 40% pour un code RS(10,4). Dans un système de stockage de données, en cas de panne, la reconstruction des données nécessite la lecture des données stockées dans les noeuds de redondance, puis leur transfert dans le réseau depuis ces noeuds 3 fournisseurs de données, aussi appelés « providers » en anglais, dans un nouveau noeud de stockage, aussi appelé « newcomer » en anglais. Même si en cas de panne d'un seul noeud, il n'y a besoin que d'un seul fournisseur dans le cas de la réplication, il faut k fournisseurs dans le cas d'un code RS(k,r), 5 impliquant alors le transfert sur le réseau des données des k fournisseurs. La réparation d'une seule panne peut ainsi nécessiter la lecture et la transmission de centaines de térabytes (TB). Aussi, le coût de la réparation en termes de bande-passante et de lectures/écritures peut être significatif. 10 Certaines solutions listées ci-dessous, s'intéressent à la réduction de la bande-passante requise pendant la phase de réparation ou « bandwidth repair » en anglais. Les codes régénérateurs sont un exemple. L'idée principale telle que décrite dans l'article « Network coding for distributed storage systems », 15 Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kannan Ramchandran, IEEE Transactions on Information Theory, 56(9): 4539-4551, 2010, est que chaque noeud génère une combinaison linéaire de données à partir des blocs de données qui y sont disponibles. La quantité de données à transférer à partir de chaque noeud fournisseur est alors plus faible 20 que celle stockée dans chaque noeud, ce qui réduit la bande-passante nécessaire pour la réparation. Cependant, avec un code régénérateur, l'information récupérée dans le nouveau noeud est une combinaison linéaire des données transférées, et elle peut alors ne pas être forcément égale au bloc de données perdu. 25 Les codes régénérateurs exacts sont proposés pour récupérer exactement le même bloc de données perdu. L'idée principale telle que décrite dans l'article « Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction », Rashmi, Korlakai Vinayak, Nihar B. Shah, and P. Vijay Kumar, IEEE Transactions on Information 30 Theory 57(8): 5227-5239, 2011, consiste à éliminer les blocs de données non désirés en utilisant le concept d'alignement d'interférences. Même si les codes régénérateurs exacts permettent de réduire considérablement la bande passante pour la réparation, le coût des entrées/sorties disque (« I/O overhead ») n'est pas optimisé. En effet, pour réparer une seule panne, un code 35 régénérateur exact nécessite de lire toutes les données stockées dans tous les noeuds. 4 Des solutions sont proposées pour réduire à la fois la bande passante de réparation et le coût des entrées/sorties disque. Par exemple, avec les codes Hiérarchiques tels que présentés dans 5 l'article « Hierarchical codes: How to make erasure codes attractive for peer-to- peer storage systems », Alessandro Duminuco and Ernst Biersack, P2P'08, 8th IEEE International Conference on Peer-to-Peer Computing, pages 89-98, l'idée principale consiste à créer de manière hiérarchique, des fonctions de parité spécifiques à partir de codes plus petits que le code original. Un code 10 Hiérarchique (k,r) a besoin de [k/r-1.1 (partie entière de k/r-1) à k blocs de données lues et téléchargées pour réparer une seule panne. Cependant, le code Hiérarchique ne maintient pas toutes les propriétés d'un code RS classique. En effet, un code Hiérarchique (k,r) ne peut tolérer r pannes quelconques. Il s'avère donc moins fiable à redondance égale. 15 Le code Hitchhicker est un code qui permet de maintenir les mêmes propriétés qu'un code RS et d'offrir une réparation de panne moins coûteuse en termes de bande passante et d'entrées/sorties disque. L'idée principale telle que décrite dans « A hitchhiker's guide to fast and efficient data reconstruction in erasure-coded data centers», KV Rashmi, Nihar B Shah, Dikang Gu, Hairong 20 Kuang, Dhruba Borthakur, and Kannan Ramchandran, ACM SIGCOMM Computer Communication Review, 44(4):331-342, 2015, consiste à réduire le nombre de blocs de données nécessaires pour réparer une seule panne. L'approche Hitchhicker considère deux sous-codes RS ayant la même configuration (k,r). Des fonctions de parités spécifiques qui dépendent du 25 deuxième et du premier code sont créées dans le deuxième sous-code RS. Ces fonctions de parité entrelacées permettent de réduire la quantité de données lues et transférées pour réparer un bloc de données. Un code Hitchhiker (10,4) permet de réduire de 30% à 35% le coût de la bande-passante de réparation et des entrées/sorties disque. 30 Il ressort qu'il existe le besoin d'une solution de codage/décodage de données pour la reconstruction de données perdues ou endommagées lors d'une panne d'un ou plusieurs éléments de stockage de données, qui soit améliorée en termes de coût de bande-passante de réparation et de coût 35 d'entrées/sorties disque. 5 Par ailleurs, avec l'arrivée des disques SSD (Solid State Drive), les éléments de stockage sont de plus en plus rapides, et chaque disque peut générer plusieurs dizaines de Gigabits par seconde en lecture. Le débit des interfaces reliant les éléments de stockage est alors particulièrement critique et 5 devient un goulot d'étranglement des systèmes de stockage. La réduction des flux à échanger en cas de reconstruction est donc particulièrement importante. Il existe ainsi le besoin d'une solution permettant d'optimiser la quantité de données à transférer lors de la réparation d'un système de stockage, suite à une panne. 10 La présente invention répond aux différents besoins précités. Résumé de l'invention La présente invention vise à pallier les limites des techniques connues en 15 proposant des méthodes et dispositifs de codage et de décodage de données permettant d'optimiser la quantité de données transférées, ainsi que les opérations de lecture/écriture nécessaires pour la réparation d'un système de stockage, suite à une panne. Avantageusement, la présente invention permet de réduire à la fois la 20 bande-passante de réparation et les coûts d'entrées/sorties disque tout en maintenant des propriétés d'efficacité de stockage et de fiabilité où toutes les pannes r parmi k+r sont tolérées. Un objet de la présente invention est relatif à une méthode de codage de données. En particulier, il est proposé une méthode de codage (k, r) de données 25 comprenant des étapes consistant à: - diviser une donnée initiale a en k blocs de données a, ; - grouper les k blocs de données en r-1 sous-ensembles SJ de blocs données ; -générer pour chaque sous-ensemble SJ une fonction linéaire g,(a) définie comme une combinaison linéaire des blocs de données assignés audit sous- 30 bloc SJ ; et - générer r fonctions de parité comprenant une fonction de parité primaire f0(a) comme une combinaison linéaire des k blocs de données a,, et r-1 fonctions de parité secondaires, chaque fonction de parité secondaire f,(a) étant définie comme la somme de la fonction de parité primaire f0(a) et d'une fonction linéaire 35 g,(a). Selon des modes de réalisation alternatifs ou combinés de la méthode de 6 codage: - l'étape de générer r fonctions de parité consiste à générer r vecteurs d'encodage comprenant : - un vecteur d'encodage primaire Co composé de k coefficients 5 d'encodage primaires c0,1 à co,k ; et - r-1 vecteurs d'encodage secondaires C, (1 k+1 35 La méthode de reconstruction de contenu est particulièrement adaptée à la reconstruction de contenu pour des données perdues suite à une panne d'un 8 équipement de stockage. Selon des modes de réalisation alternatifs ou combinés de la méthode de reconstruction : - les étapes de récupérer les fonctions de parité consistent à transférer les 5 données des équipements de stockage correspondants vers un équipement collecteur de données ; - l'étape de calculer la fonction linéaire g,(a) associée au sous-ensemble Si pour la reconstruction d'un noeud systématique i tel que iE {1, .., k}, consiste à soustraire la fonction de parité primaire stockée dans l'équipement de stockage 10 Nk±i de la fonction de parité secondaire stockée dans l'équipement de stockage N k+1±J 5 - l'étape de calculer la fonction linéaire g1(a) associée au sous-ensemble Si pour la reconstruction d'un noeud de parité i tel que i=k+1, consiste à générer une combinaison linéaire à partir des blocs de données du sous-ensemble Si et du 15 vecteur d'encodage Cl ; - l'étape de calculer la fonction linéaire g,(a) associée au sous-ensemble Si pour la reconstruction d'un noeud de parité i tel que iE {k+2, k+r}, consiste à générer une combinaison linéaire à partir des blocs de données du sous-ensemble Si et du vecteur d'encodage Ci ; 20 - l'étape de reconstruire le contenu dudit équipement de stockage systématique consiste à décoder le bloc de données a, à partir de la fonction linéaire g,(a) ; - l'étape de reconstruire le contenu dudit équipement de stockage de parité i tel que i=k+1 consiste à décoder la fonction de parité secondaire dudit équipement de parité d'index i=k+1 à partir de la fonction linéaire g1(a) calculée ; 25 - l'étape de reconstruire le contenu dudit équipement de stockage de parité i tel que i>k+1 consiste à décoder la fonction de parité secondaire dudit équipement de parité d'index i>k+1 à partir de la fonction linéaire gi-k+1(a) calculée. L'invention couvre aussi un dispositif de reconstruction du contenu d'un équipement de stockage parmi une pluralité d'équipements stockant k blocs de 30 données a, dans k équipements de stockage systématique N,, iE {1, .., k}, et r fonctions de parité f,(a) dans r équipements de stockage de parité N,, i E {k+1, k+r }, lesdits k blocs de données et r fonctions de parité étant obtenus selon la méthode de codage revendiquée, le dispositif comprenant des moyens pour mettre en oeuvre les étapes de la méthode de reconstruction du contenu d'un 35 équipement de stockage revendiquée. La présente invention peut être intégrée à des éléments matériel et/ou 9 logiciel tels qu'un circuit intégré de type ASIC ou FPGA. L'invention porte aussi sur un programme d'ordinateur qui comporte des instructions de code permettant d'effectuer les étapes de la méthode de codage revendiquée et/ou comprenant des instructions de code permettant d'effectuer 5 les étapes de la méthode de reconstruction de contenu revendiquée, lorsque ledit programme est exécuté sur un ordinateur. L'invention peut être disponible sur un support d'enregistrement lisible par un processeur sur lequel est enregistré un programme comportant des instructions de code pour l'exécution de la méthode de codage et/ou de la 10 méthode de reconstruction de contenu telles que revendiquées. Une utilisation avantageuse de la méthode de reconstruction de contenu revendiquée est dans un système de stockage distribué qui comprend une pluralité de noeuds de stockage de données aptes à stocker des données codées selon la méthode de codage revendiquée. 15 Une autre utilisation avantageuse de la méthode de reconstruction de contenu revendiquée est dans un système de stockage local qui comprend des disques de stockage de données aptes à stocker des données codées selon la méthode de codage revendiquées. 20 Description des figures Différents aspects et avantages de l'invention vont apparaitre en appui de la description d'un mode préféré d'implémentation de l'invention mais non limitatif, avec référence aux figures ci-dessous : 25 La figure 1 illustre un environnement de système distribué permettant de mettre en oeuvre l'invention dans un mode de réalisation ; La figure 2 montre une représentation du stockage des données dans un mode 30 de réalisation de l'invention ; La figure 3 illustre les étapes du procédé de codage de l'invention dans un mode de réalisation ; 35 La figure 4 illustre la génération d'un vecteur d'encodage primaire, selon les principes de l'invention ; 10 La figure 5 illustre la génération d'un vecteur d'encodage secondaire, selon les principes de l'invention ; 5 La figure 6 illustre la génération d'une fonction de parité primaire et d'une fonction de parité secondaire, selon les principes de l'invention ; Les figures 7a à 7c illustrent les étapes de reconstruction de noeuds systématiques et de parité selon les principes de l'invention ; 10 La figure 8 est un tableau comparatif des performances de différents codes. Description détaillée de l'invention 15 Pour la suite de la description, l'expression 'noeud de stockage' est utilisée au sens générique et désigne une entité de stockage, que ce soit un disque unique ou un groupement d'équipements de stockage formant un noeud. Les modes de réalisation de l'invention décrits s'appliquent à toute variante de système de stockage distribué illustré sur la figure 1, qui n'est qu'un exemple 20 d'environnement permettant de mettre en oeuvre l'invention. Ainsi cet exemple n'est pas limitatif et les principes décrits peuvent être appliqués pour tout autre environnement intégrant un système de stockage, distribué ou non, comme les systèmes en nuage ou « Cloud Systems » en anglais, les centres de données ou « Data Centers » en anglais, les systèmes de fichiers distribués ou 25 « Distributed File Systems » en anglais, qu'ils soient basés sur des fichiers ou à objets. L'invention peut également s'appliquer à des systèmes de stockage non distribués comme les « Disk Arrays ». Par ailleurs, un noeud de stockage qui stocke des données issues de la donnée initiale est désigné « noeud systématique » et un noeud de stockage qui stocke une fonction de parité est 30 désigné « noeud de parité ». Afin de faciliter la compréhension des principes de l'invention, la méthode de codage est d'abord décrite sur un exemple particulier d'un code (k=10, r=4), puis est généralisée pour tout code (k, r). 35 11 Description de la méthode de codage sur l'exemple d'un code (10, 4) : La figure 2 illustre une représentation du stockage de données par application de la méthode de codage de l'invention, sur l'exemple d'un code k=10 et r=4. Dans la suite de la description, les étapes de codage de la présente 5 invention peuvent être désignées par l'expression « code Babylon » ou « codage Babylon ». Une donnée initiale a est divisée en k=10 morceaux (200) ou blocs de données (a1, a10), notés a,, i e {1, .., 10}, auxquels sont ajoutés r=4 blocs de parité ou fonctions de parité fo, fl, f2 et f3, qui sont des combinaisons linéaires des données (a1, a10) et notées dans la suite fo(a), f1 (a), f2(a), f3(a) ou f 0(a) 10 et f,(a), j e {1, 2, 3}. La fonction de parité fo(a) est désignée comme fonction de parité primaire, et les fonctions de parité f,(a) sont désignées comme fonctions de parité secondaires. Les fonctions de parité primaire et secondaires sont générées selon le codage Babylon (202) de l'invention et stockées sur des noeuds de stockage (204). 15 Les blocs de données systématiques a1 à a10 sont stockés sur 10 noeuds de stockage systématiques correspondants (206), notés (N1 à N10), et les fonctions de parité primaire fo(a) et secondaires fl(a), f2(a), f3(a) sont stockées sur 4 noeuds de stockage de parité correspondants (208), notés N11 à N14. 20 La figure 3 illustre les étapes du procédé de codage (300) de l'invention dans un mode de réalisation d'un code (k=10, r=4). Dans une première étape (302), le procédé permet de diviser une donnée initiale a en 10 blocs de données (a1, a10), puis dans une étape suivante (304) de créer 3 sous- ensembles de données (S1, S2, S3). Chaque sous-ensemble de données 25 regroupe des blocs de données différents parmi les 10 blocs créés. Dans un mode de réalisation, deux sous-ensembles (S1, S2) sont composés chacun de 3 blocs de données et le troisième sous-bloc (S3) est composé de 4 blocs de données. Le premier sous-ensemble 51 est composé des trois premiers blocs (a1, a2, a3) issus de la donnée initiale, le second sous-ensemble S2 est composé 30 des trois blocs suivants (a4, a5, a6), et le dernier sous-ensemble S3 est composé des quatre derniers blocs restants (a7, a5, a0, a10). Dans une étape suivante (306), le procédé permet de générer 4 vecteurs d'encodage de longueur (k=10), correspondants aux 4 noeuds de parité. Les vecteurs d'encodage notés Co à C4, correspondent à un vecteur d'encodage 35 primaire Co et 3 vecteurs d'encodage secondaires Cl, C2, C3. 12 Les figures 4 et 5 détaillent les étapes de génération des vecteurs d'encodage selon les principes de l'invention. La figure 4 illustre la génération du vecteur d'encodage primaire Co (400) dans un mode réalisation. Le vecteur d'encodage primaire Co est composé de 5 10 coefficients d'encodage primaires c0,1 à C0,10 où chaque coefficient d'encodage primaire co,, (402-i) correspond à un nombre aléatoire non nul (404- i). La figure 5 illustre la génération des vecteurs d'encodage secondaires C, (1 =3. Pour une valeur r=1, le code Babylon agit comme un code RS classique. Pour une valeur r=2, les données sont divisées en deux sous-ensembles S1 et S2, où 10 S1 est composé des ts premiers blocs et S2 contient les k-te derniers blocs, où t,=[k /r]. Avantageusement, le procédé de l'invention permet de ne pas utiliser tous les noeuds dans le processus de reconstruction. Par ailleurs, les noeuds contribuant à la reconstruction n'ont pas à effectuer de calculs, mais ils n'ont 15 juste qu'à transférer leur contenu vers un collecteur de données où vont s'effectuer les opérations de décodage. Le collecteur de données peut être le nouveau noeud de stockage de remplacement du noeud en panne. Toujours avantageusement, grâce au procédé de codage Babylon, le temps de reconstruction est diminué par rapport à des méthodes à base de 20 matrices où l'ensemble des blocs de données des k noeuds est nécessaire à la reconstruction. La figure 8 est un tableau comparatif des performances comparant les résultats de différents codes connus avec ceux obtenus par le code Babylon de 25 la présente invention. Dans la table (800), la première colonne liste les codes comparés : RS ; Régénérateurs ; Régénérateurs exacts ; Hiérarchique ; Hitchhicker ; et Babylon. Il a été considéré pour tous les codes un fichier de même taille de M octets codés en utilisant une configuration (k=10, r=4). 30 L'évaluation a été faite pour chaque code pour une même efficacité de stockage (71%) colonne (804) sur différents paramètres : la bande passante moyenne requise pour la réparation (806), les entrées/ sorties disques (808) et la tolérance aux pannes 810). La bande passante et les entrées /sorties disques sont exprimées en pourcentage par rapport à la taille M du fichier original. Les 23 pourcentages dans le tableau sont calculés en tenant en compte de la réparation des noeuds systématiques et des noeuds de parité. Les résultats sont les suivants : - Pour un code RS, la réparation d'une seule panne nécessite la lecture et le 5 transfert de M octets. Ceci est équivalent à 100% de la taille originale du fichier. - Pour la même efficacité de stockage, on calcule la bande passante requise par les codes régénérateurs et les codes régénérateurs exacts. La bande passante utilisée pour la réparation d'une panne est en moyenne égale à 32.5%. Cependant, les entrées/ sorties disques ne sont pas optimisées. Pour réparer 10 une seule panne les codes régénérateurs nécessitent la lecture de toutes les données stockées dans les noeuds avant de les transférer. - Le code Hiérarchique optimise à la fois la bande passante et les entrées/sorties disques. La quantité des données lues et transférées dans le réseau est égale 33,57%. Cependant, le code Hiérarchique ne maintient pas la 15 même tolérance aux pannes que les codes RS. En effet, on ne peut tolérer 4 pannes quelconques en utilisant le code Hiérarchique. - Le code Hitchhicker permet à la fois d'optimiser la bande passante et les entrées/sorties disques en maintenant la même tolérance aux pannes que le code RS. Dans ce cas, la quantité des données lues et transférées est égale à 20 76,42%. - Le code Babylon nécessite en moyenne 43.57% de la taille du fichier original pour réparer une seule panne en termes de bande passante et d'entrées/sorties disques. Il permet aussi de tolérer 4 pannes quelconques parmi les 14 noeuds. 25 La présente invention peut s'implémenter à partir d'éléments matériel et/ou logiciel. Elle peut être disponible en tant que produit programme d'ordinateur sur un support lisible par ordinateur. Le support peut être électronique, magnétique, optique ou électromagnétique. Dans un mode de réalisation, la méthode est mise en oeuvre par ordinateur. Il est décrit un produit 30 programme d'ordinateur, ledit programme d'ordinateur comprenant des instructions de code permettant d'effectuer une ou plusieurs des étapes de la méthode, lorsque ledit programme est exécuté sur un ordinateur. Dans un mode de réalisation, le dispositif pour la mise en oeuvre de l'invention comprend un support de stockage lisible par ordinateur (RAM, ROM, mémoire flash ou une 35 autre technologie de mémoire, par exemple support à disque ou un autre support de stockage non transitoire lisible par ordinateur) codé avec un 24 programme d'ordinateur (c'est-à-dire plusieurs instructions exécutables) qui, lorsqu'il est exécuté sur un ou plusieurs processeurs, effectue les fonctions des modes de réalisation décrits précédemment. A titre d'exemple d'architecture matérielle adaptée à mettre en oeuvre l'invention, un dispositif peut comporter un 5 bus de communication auquel sont reliés une unité centrale de traitement ou microprocesseur (CPU, acronyme de « Central Processing Unit » en anglais), lequel processeur peut être "multi-core" ou "many-core"; une mémoire morte (ROM, acronyme de « Read Only Memory » en anglais) pouvant comporter les programmes nécessaires à la mise en oeuvre de l'invention; une mémoire vive 10 ou mémoire cache (RAM, acronyme de « Random Access Memory » en anglais) comportant des registres adaptés à enregistrer des variables et paramètres créés et modifiés au cours de l'exécution des programmes précités ; et une interface de communication ou E/S (I/O acronyme de « lnput/ouput » en anglais) adaptée à transmettre et à recevoir des données. Dans le cas où l'invention est 15 implantée sur une machine de calcul reprogrammable (par exemple un circuit FPGA), le programme correspondant (c'est-à-dire la séquence d'instructions) peut être stocké dans ou sur un médium de stockage amovible (par exemple une carte SD, ou un stockage de masse tel qu'un disque dur e.g. un SSD) ou non-amovible, volatile ou non-volatile, ce médium de stockage étant lisible 20 partiellement ou totalement par un ordinateur ou un processeur. Le support lisible par ordinateur peut être transportable ou communicable ou mobile ou transmissible (i.e. par un réseau de télécommunication 2G, 3G, 4G, Wifi, BLE, fibre optique ou autre). La référence à un programme d'ordinateur qui, lorsqu'il est exécuté, effectue l'une quelconque des fonctions décrites précédemment, ne 25 se limite pas à un programme d'application s'exécutant sur un ordinateur hôte unique. Au contraire, les termes programme d'ordinateur et logiciel sont utilisés ici dans un sens général pour faire référence à tout type de code informatique (par exemple, un logiciel d'application, un micro logiciel, un microcode, ou toute autre forme d'instruction d'ordinateur, comme des web services ou SOA ou via 30 des interfaces de programmation API) qui peut être utilisé pour programmer un ou plusieurs processeurs pour mettre en oeuvre des aspects des techniques décrites ici. Les moyens ou ressources informatiques peuvent notamment être distribués ("Cloud computing"), éventuellement avec ou selon des technologies de pair-à-pair et/ou de virtualisation. Le code logiciel peut être exécuté sur 35 n'importe quel processeur approprié (par exemple, un microprocesseur) ou coeur de processeur ou un ensemble de processeurs, qu'ils soient prévus dans un 25 dispositif de calcul unique ou répartis entre plusieurs dispositifs de calcul (éventuellement accessibles dans l'environnement du dispositif). Des technologies de sécurisation (crypto-processeurs, authentification, chiffrement, carte à puce, REVENDICATIONS1. Méthode de codage (k, r) de données comprenant des étapes consistant à: - diviser une donnée initiale a en k blocs de données a, ; - grouper les k blocs de données en r-1 sous-ensembles SJ de blocs données ; - générer pour chaque sous-ensemble SJ une fonction linéaire g,(a) définie comme une combinaison linéaire des blocs de données assignés audit sous-bloc SJ ; et - générer r fonctions de parité comprenant une fonction de parité primaire fo(a) comme une combinaison linéaire des k blocs de données a,, et r-1 fonctions de parité secondaires, chaque fonction de parité secondaire f,(a) étant définie comme la somme de la fonction de parité primaire fo(a) et d'une fonction linéaire g,(a). 2. La méthode selon la revendication 1 dans laquelle l'étape de générer r fonctions de parité consiste à générer r vecteurs d'encodage comprenant : - un vecteur d'encodage primaire Co composé de k coefficients d'encodage primaires c0,1 à co,k ; et - r-1 vecteurs d'encodage secondaires C, (1 3. La méthode selon la revendication 2 dans laquelle chaque coefficient d'encodage primaire co,, correspond à un nombre aléatoire non nul, et un coefficient d'encodage secondaire ch, correspond à un nombre aléatoire non nul ou nul selon que le bloc de données a, appartient ou n'appartient pas au sous-ensemble S. 4. La méthode selon la revendication 3 dans laquelle l'étape de générer une fonction linéaire g,(a) consiste à générer une combinaison linéaire des k blocs de données (al, ..., ak) et du vecteur d'encodage secondaire C. 5. La méthode selon l'une quelconque des revendications 1 à 4 dans laquelle k=10 et r=4. 27 6. Méthode de stockage de k+r données comprenant au moins une étape consistant à stocker dans k équipements de stockage systématique N,, iE {1, k}, k blocs de données a,, et à stocker dans r équipements de stockage de 5 parité N,, i e {k+1, k+r}, r fonctions de parité, les r fonctions de parité étant obtenues selon la méthode de codage de données de l'une quelconque des revendications 1 à 5. 7. Dispositif de codage de données comprenant des moyens pour mettre en 10 oeuvre les étapes de la méthode de codage de données selon l'une quelconque des revendications 1 à 5. 8. Méthode de reconstruction du contenu d'un équipement de stockage parmi une pluralité d'équipements stockant k blocs de données a, dans k 15 équipements de stockage systématique N,, iE {1, .., k}, et r fonctions de parité f,(a) dans r équipements de stockage de parité N,, i E {k+1, k+r }, les dits k blocs de données et r fonctions de parité étant obtenus selon la méthode de l'une quelconque des revendications 1 à 5, la méthode de reconstruction comprenant au moins des étapes consistant à: 20 déterminer si l'équipement de stockage pour lequel reconstruire le contenu est un équipement de stockage systématique ou de parité; - si ledit équipement est un équipement de stockage systématique N,, iE {1, .., k} : - déterminer à quel sous-ensemble de données SJ, le bloc de données 25 dudit équipement appartient ; - récupérer les fonctions de parité primaire et secondaire stockées dans les équipements de stockage de parité k+1 et k+1+j ; - calculer la fonction linéaire g,(a) associée au sous-ensemble S; ; - récupérer les blocs de données du sous-ensemble SJ à l'exception du 30 bloc a, ; et - reconstruire le contenu dudit équipement de stockage systématique N,, ie {1, .., k} ; - si ledit équipement est un équipement de stockage de parité N,, i E {k+1, k+r}, déterminer l'index i identifiant ledit équipement de stockage ; 35 - si l'index i est égal à k+1 : ^ récupérer la fonction de parité secondaire fl (a) stockée dans 28 l'équipement de stockage de parité d'index i=k+2 et les blocs de données a, du sous-ensemble Si; ^ calculer la fonction linéaire g, (a) associée au sous-ensemble S1 et décoder la fonction de parité primaire fo(a) ; et 5 ^ reconstruire le contenu dudit équipement de parité d'index i=k+1; - si l'index i est supérieur à k+1 : ^ récupérer la fonction de parité primaire fo(a) stockée dans l'équipement de stockage de parité d'index i=k+1 et les blocs 10 de données a, du sous-ensemble Si-k+1 , ^ calculer la fonction linéaire g,_k_o (a) associée au sous-ensemble Si-k+1 et décoder la fonction de parité secondaire f k+1(a) ; et ^ reconstruire le contenu dudit équipement de parité d'index 15 i>k+1 9. La méthode selon la revendication 8 dans laquelle les étapes de récupérer les fonctions de parité consistent à transférer les données des équipements de stockage correspondants vers un équipement collecteur de données. 20 10. La méthode selon la revendication 8 ou 9 dans laquelle l'étape de calculer la fonction linéaire g,(a) associée au sous-ensemble SJ pour la reconstruction d'un noeud systématique i tel que iE {1, .., k}, consiste à soustraire la fonction de parité primaire stockée dans l'équipement de stockage Nk±i de la fonction 25 de parité secondaire stockée dans l'équipement de stockage Nk±i±J. 11. La méthode selon l'une quelconque des revendications 8 à 10 dans laquelle l'étape de calculer la fonction linéaire g (a) associée au sous-ensemble Si pour la reconstruction d'un noeud de parité i tel que i=k+1, consiste à 30 générer une combinaison linéaire à partir des blocs de données du sous- ensemble Si et du vecteur d'encodage C,, et l'étape de calculer la fonction linéaire g,(a) associée au sous-ensemble SJ pour la reconstruction d'un noeud de parité i tel que iE {k+2, k+r}, consiste à générer une combinaison linéaire à partir des blocs de données du sous-ensemble SJ et du vecteur 35 d'encodage C . 29 12. La méthode selon l'une quelconque des revendications 8 à 11 dans laquelle l'étape de reconstruire le contenu dudit équipement de stockage systématique consiste à décoder le bloc de données a, à partir de la fonction linéaire g,(a). 5 13. La méthode selon l'une quelconque des revendications 8 à 11 dans laquelle l'étape de reconstruire le contenu dudit équipement de stockage de parité i tel que i=k+1 consiste à décoder la fonction de parité secondaire dudit équipement de parité d'index i=k+1 à partir de la fonction linéaire g (a) 10 calculée, et l'étape de reconstruire le contenu dudit équipement de stockage de parité i tel que i>k+1 consiste à décoder la fonction de parité secondaire dudit équipement de parité d'index i>k+1 à partir de la fonction linéaire g,_ k+1(a) calculée. 15 14. Dispositif de reconstruction du contenu d'un équipement de stockage parmi une pluralité d'équipements stockant k blocs de données a, dans k équipements de stockage systématique N,, iE {1, .., k}, et r fonctions de parité f,(a) dans r équipements de stockage de parité N,, i e {k+1, k+r }, les 20 dits k blocs de données et r fonctions de parité étant obtenus selon la méthode de l'une quelconque des revendications 1 à 5, le dispositif comprenant des moyens pour mettre en oeuvre les étapes de la méthode de reconstruction du contenu d'un équipement de stockage selon l'une quelconque des revendications 8 à 13. 25 15. Produit programme d'ordinateur comprenant un programme, ledit programme comprenant des instructions de code permettant d'effectuer les étapes de la méthode selon l'une quelconque des revendications 1 à 5 et/ou comprenant des instructions de code permettant d'effectuer les étapes de la 30 méthode selon l'une quelconque des revendications 8 à 13, lorsque ledit programme est exécuté sur un ordinateur. 16. Circuit intégré de type ASIC ou FPGA comprenant au moins un dispositif selon la revendication 7 et/ou selon la revendication 14. 35 17. Utilisation de la méthode de reconstruction de contenu selon l'une quelconque des revendications 8 à 13 dans un système de stockage 30 distribué, ledit système de stockage distribué comprenant une pluralité de noeuds de stockage de données aptes à stocker des données codées selon la méthode de codage de l'une quelconque des revendications 1 à 5. 5 18. Utilisation de la méthode de reconstruction de contenu selon l'une quelconque des revendications 8 à 13 dans un système de stockage local, ledit système de stockage local comprenant des disques de stockage de données aptes à stocker des données codées selon la méthode de codage de l'une quelconque des revendications 1 à 5. 10