DISTRIBUÉ

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 = 10 ¹⁵ 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 nœud de stockage peut être composé d’un (112) ou d’une pluralité d’équipements de stockage (110, 114). Chaque équipement de stockage d’un nœud qui en comporte plusieurs est lui-même désigné comme un nœud 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 nœuds, 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). Or, il n’est pas rare que des disques, des équipements ou des nœuds de stockage tombent en panne, et il est courant que pour des milliers de nœuds, 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 ou plusieurs nœuds 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.

II 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 nœuds de stockage. Généralement, un même bloc de données est stocké dans n nœuds différents, ce qui permet de tolérer n-1 pannes. En pratique, chaque bloc de données est stocké dans trois nœuds 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 nœuds.

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 nœuds différents, où k nœuds stockent les k blocs originaux et r nœuds 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 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 nœuds de redondance, puis leur transfert dans le réseau depuis ces nœuds fournisseurs de données, aussi appelés « providers » en anglais, dans un nouveau nœud de stockage, aussi appelé « newcomer » en anglais. Même si en cas de panne d’un seul nœud, 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), 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. 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 », 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 nœud 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 nœud fournisseur est alors plus faible que celle stockée dans chaque nœud, 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 nœud 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.

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 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 régénérateur exact nécessite de lire toutes les données stockées dans tous les nœuds. 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 l’article « Hierarchical codes: How to make erasure codes attractive for peer-to- peer storage Systems », Alessandro Duminuco and Ernst Biersack, R2RΌ8, 8th IEEE International Conférence 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 Hiérarchique (k,r) a besoin de lk/r-1J (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.

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 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 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.

Les références suivantes proposent des méthodes de codage de données pour réduire la bande passante :

Cheng Huang et al. : « Erasure Coding in Windows Azuré Storage », USENIX,, 11 avril 2013 (2013-04-11 ), pages 1 -12, XP061013941. Cette méthode LRC (k, I, r) est basée sur la génération de fonctions de parité locales stockées dans des noeuds de stockage ; Cependant, les codes LRC introduisent un sur- coût de stockage dû au stockage supplémentaire des fonctions de parité locales. Cheng Huang et al. : « Pyramia Codes : Flexible Schemes to Trade Spaces for Access Efficiency in Reliable Data Storage Systems”, Proc. Sixth IEEE International Symposium on Network Computing and Applications 2007, IEEE, 1 juillet 2007 (2007-0è-0&), pages 79-86, XP031119281 , ISBN: 978-0- 7695-2922-6. Cette méthode présente une alternative à la méthode LRC. Ce pendant, les codes Pyramid, comme les codes LRC, introduisent un surcoût de stockage comparé à un code d’effacement classique et au code Babylon.

Ces approches ne permettent pas une même efficacité de stockage qu’un code d’effacement classique, contrairement aux codes Hithchicker, aux codes régénérateurs et aux codes hiérarchiques qui permettent de réduire la bande passante tout en maintenant la même efficacité de stockage qu’un code d’effacement classique.

Contrairement aux méthodes décrites précédemment basées sur la définition d’un nouveau code d’effacement, la solution proposée dans la demande de brevet US 2016/211869 A1 de Blaum Mario et al. propose un système de stockage dynamique intégrant plusieurs codes d’effacement, capable de basculer entre différents codes en fonction de l’objectif. Le système décide soit de réduire la bande passante de réparation, soit de réduire le surcoût de stockage en fonction de la popularité du fichier. Le système supporte en particulier les deux codes : LRC (cité précédemment) et le « Product Code » (PC).

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 d’entrées/sorties disque, tout en maintenant la même efficacité de stockage que les codes d’effacement classiques.

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 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 a’un système de stockage, suite à une panne.

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 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 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 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 S, de blocs données ;

-générer pour chaque sous-ensemble S, une fonction linéaire g _j (a) définie comme une combinaison linéaire des blocs de données assignés audit sous- bloc S _j ; et

- générer r fonctions de parité comprenant une fonction de parité primaire f ₀ (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 _j (a) étant définie comme la somme de la fonction de parité primaire f ₀ (a) et d’une fonction linéaire 9j(a).

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 l’article « Hierarchical codes: How to make erasure codes attractive for peer-to- peer storage Systems », Alessandro Duminuco and Ernst Biersack, R2RΌ8, 8th IEEE International Conférence 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 Hiérarchique (k,r) a besoin de lk/r-1J ^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.

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 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 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.

Les références suivantes proposent des méthodes de codage de données pour réduire la bande passante :

Cheng Huang et al. : « Erasure Coding in Windows Azuré Storage », USENIX,, 11 avril 2013 (2013-04-11 ), pages 1 -12, XP061013941. Cette méthode LRC (k, I, r) est basée sur la génération de fonctions de parité locales stockées dans des noeuds de stockage ; Cependant, les codes LRC introduisent un sur coût de stockage dû au stockage supplémentaire des fonctions de parité locales.

Cheng Huang et al. : « Pyramid Codes : Flexible Schemes to Trade Spaces for Access Efficiency in Reliable Data Storage Systems”, Proc. Sixth IEEE International Symposium on Network Computing and Applications 2007, IEEE, 1 juillet 2007 (2007-0è-0&), pages 79-86, XP031119281 , ISBN: 978-0- 7695-2922-6. Cette méthode présente une alternative à la méthode LRC. Ce pendant, les codes Pyramid, comme les codes LRC, introduisent un surcoût de stockage comparé à un code d’effacement classique et au code Babylon.

Ces approches ne permettant pas une même efficacité de stockage qu’un code d’effacement classique comrairement aux codes Hithchicker, aux codes régénérateurs et aux codes hiérarchiques qui permettent de réduire la bande passante tout en maintenant la même efficacité de stockage qu’un code d’effacement classique.

Contrairement aux méthodes décrites précédemment basées sur la définition d’un nouveau code d’effacement, la solution proposée dans la demande de brevet US 2016/211869 A1 de Blaum Mario et al. propose un système de stockage dynamique intégrant plusieurs codes d’effacement, capable de basculer entre différents codes en fonction de l’objectif. Le système décide soit de réduire la bande passante de réparation, soit de réduire le surcoût de stockage en fonction de la popularité du fichier. Le système supporte en particulier les deux codes : LRC (cité précédemment) et le « Product Code » (PC).

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 d’entrées/sorties disque, tout en maintenant la même efficacité de stockage que les codes d’effacement classiques.

Selon des modes de réalisation alternatifs ou combinés de la méthode de 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 C ₀ composé de k coefficients d’encodage primaires c _0,i à c _0,k ; et

- r-1 vecteurs d’encodage secondaires C, (1 <=j<=r-1 ), chaque vecteur d’encodage secondaire étant composé de k coefficients d’encodage secondaires C _{j |} a C _{j k}

- chaque coefficient d’encodage primaire c ₀ ,i correspond à un nombre aléatoire non nul, et un coefficient d’encodage secondaire CJ 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, ;

- l’étape de générer une fonction linéaire g _j (a) consiste à générer une combinaison linéaire des k blocs de données (ai , a _k ) et du vecteur d’encodage secondaire C, ;

- k=10 et r= 4.

La méthode de codage de données de la présente invention est particulièrement adaptée pour distribuée des données sur des équipements de stockage en prévision de reconstruire des données perdues suite à une panne d’un équipement de stockage. Il est aussi revendiqué une 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 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 revendiquée.

L’invention couvre aussi un dispositif de codage de données comprenant des moyens pour mettre en oeuvre les étapes de la méthode de codage de données telle que revendiquée.

Un autre objet de la présente invention est relatif à une méthode de reconstruction ou duplication du contenu d’un équipement qui stocke des données codées selon la méthode de codage revendiquée. En particulier, il est revendiqué une 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 équipements de stockage systématique N,, ie {1 , .., k}, et r fonctions de parité f _j (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 à:

- 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 S _{j 5} le bloc de données 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 _j (a) associée au sous-ensemble S, ;

- récupérer les blocs de données du sous-ensemble S, à l’exception du bloc a, ; et

- reconstruire le contenu dudit équipement de stockage systématique Ni, 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 ;

- si l’index i est égal à k+1 :

^■ récupérer la fonction de parité secondaire fi (a) stockée dans 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 Si et décoder la fonction de parité primaire f ₀ (a) ; et

^■ 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 f ₀ (a) stockée dans l’équipement de stockage de parité d’index i=k+1 et les blocs de données a, du sous-ensemble S- _{k+i ;}

^■ calculer la fonction linéaire g _ _k+i (a) associée au sous- ensemble S _i-k+1 et décoder la fonction de parité secondaire f, k _+i (a) ; et

^■ reconstruire le contenu dudit équipement de parité d’index i>k+1

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 é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 données des équipements de stockage correspondants vers un équipement collecteur de données ;

- l’étape de calculer la fonction linéaire g _j (a) associée au sous-ensemble S, pour la reconstruction d’un nœud systématique i tel que ie {1 , k}, consiste à soustraire la fonction de parité primaire stockée dans l’équipement de stockage N _k+1 de la fonction de parité secondaire stockée dans l’équipement de stockage

N _k +1 +j ,

- l’étape de calculer la fonction linéaire g _! (a) associée au sous-ensemble Si pour la reconstruction d’un nœud de parité i æl que i=k+1 , consiste à générer une combinaison linéaire à partir des blocs de données du sous-ensemble Si et du vecteur d’encodage Ci ;

- l’étape de calculer la fonction linéaire g _j (a) associée au sous-ensemble S, pour la reconstruction d’un nœud 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 S _j et du vecteur d’encodage C _j ;

- 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 _j (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 ;

- 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 données a, dans k équipements de stockage systématique N,, ie {1 , k}, et r fonctions de parité f _j (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 œuvre les étapes de la méthode de reconstruction du contenu d’un équipement de stockage revendiquée.

La présente invention peut être intégrée à des éléments matériel et/ou 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 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 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 nœuds de stockage de données aptes à stocker des données codées selon la méthode de codage revendiquée.

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.

Description des figures Différents aspects et avantages de l’invention vont apparaître 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 :

La figure 1 illustre un environnement de système distribué permettant de mettre en œuvre l’invention dans un mode de réalisation ;

La figure 2 montre une représentation du stockage des données dans un mode 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 ;

La figure 4 illustre la génération d’un vecteur d’encodage primaire, selon les principes de l’invention ;

La figure 5 illustre la génération d’un vecteur d’encodage secondaire, selon les principes de l’invention ;

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 nœuds systématiques et de parité selon les principes de l’invention ; La figure 8 est un tableau comparatif des performances de différents codes. Description détainee de l’invention

Pour la suite de la description, l’expression ‘nœud 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 nœud. 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 d’environnement permettant de mettre en œuvre 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 « 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 nœud de stockage qui stocke des données issues de la donnée initiale est désigné « nœud systématique » et un nœud de stockage qui stocke une fonction de parité est désigné « nœud 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).

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 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 (a _{1 ;} ..., a ₁₀ ), notés a,, i e {1 , .., 10}, auxquels sont ajoutés r=4 blocs de parité ou fonctions de parité f ₀ , fi , f ₂ et f ₃ , qui sont des combinaisons linéaires des données (a _{1 ;} ..., ai ₀ ) et notées dans la suite f ₀ (a), f 1 (a), f ₂ (a), f ₃ (a) ou f ₀ (a) et f _j (a) , j e {1 , 2, 3}. La fonction de parité f ₀ (a) est désignée comme fonction de parité primaire, et les fonctions de parité f _j (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 nœuds de stockage (204).

Les blocs de données systématiques a- _\ à ai ₀ sont stockés sur 10 nœuds de stockage systématiques correspondants (206), notés (Ni à N ₁₀ ), et les fonctions de parité primaire f ₀ (a) et secondaires f 1 (a), f ₂ (a), f ₃ (a) sont stockées sur 4 nœuds de stockage de parité correspondants (208), notés Nu à N ₁₄ .

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 (a _{1 ;} ..., a ₁₀ ), puis dans une étape suivante (304) de créer 3 sous- ensembles de données (S _{1 ;} S ₂ , S ₃ ). Chaque sous-ensemble de données regroupe des blocs de données différents parmi les 10 blocs créés. Dans un mode de réalisation, deux sous-ensembles (S _{1 ;} S ₂ ) sont composés chacun de 3 blocs de données et le troisième sous-bloc (S ₃ ) est composé de 4 blocs de données. Le premier sous-ensemble Si est composé des trois premiers blocs

(ai , a ₂ , a ₃ ) issus de la donnée initiale, le second sous-ensemble S ₂ est composé des trois blocs suivants (a ₄ , a ₅ , a ₆ ), et le dernier sous-ensemble S ₃ est composé des quatre derniers blocs restants (a ₇ , a ₈ , a _9, ai ₀ ).

Dans une étape suivante (306), le procédé permet de générer 4 vecteurs d’encodage de longueur (k=10), correspondants aux 4 nœuds de parité. Les vecteurs d’encodage notés C ₀ à C ₄ , correspondent à un vecteur d’encodage primaire C ₀ et 3 vecteurs d’encodage secondaires Ci , C ₂ , C ₃

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 C ₀ (400) dans un mode réalisation. Le vecteur d’encodage primaire C ₀ est composé de 10 coefficients d’encodage primaires c _0,i à c _0,i o où chaque coefficient d’encodage primaire c ₀ ,i (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 <=j<=3) dans un mode de réalisation (500). Chaque vecteur d’encodage secondaire C, est composé de 10 coefficients d’encodage secondaires C _j,i à ^c j,i o - Pour générer un vecteur C _j , le procédé vérifie (504-i) pour chaque bloc a,, si le bloc a, appartient au sous-ensemble S,. Si c’est le cas (branche oui), le procédé permet d’associer aux coefficiems CJ des nombres aléatoires non nuis (506-i). Si les blocs a, n’appartiennent pas au sous-ensemble S, (branche non), le procédé permet d’associer aux coefficients C _j, , des nombres aléatoires nuis (508-i).

Par exemple, pour générer le vecteur d’encodage C _{1 ;} le procédé vérifie, pour chaque bloc de données ai , a ₂ , ..ai ₀ , s’il appartient au sous-ensemble Si . Comme les blocs de données a _{1 ;} a ₂ , a ₃ appartiennent au sous-ensemble S _{1 ;} le procédé génère donc des nombres aléatoires non nuis pour les coefficients c^ , c _{1 2} et Ci _{, 3} . Comme les blocs de données a ₄ , ..., a ₁₀ n’appartiennent pas à S _{1 ;} le procédé génère des nombres aléatoires nuis associés aux coefficients c _{1 4} ...

C1,10·

Ainsi, pour le sous-ensemble S _{1 ;} le procédé permet de générer un vecteur d’encodage Ci égal à (o _u , c _{1 2} , c _{1 3} , 0, 0, 0, 0, 0, 0, 0) où o _u , c _{1 2} et c _{1 3} sont des nombres aléatoires non nuis.

Pour le sous-ensemble S ₂ , le procédé permet de générer un vecteur d’encodage C ₂ égal à (0, 0, 0, c _2,4 , c _2,5 , c _2,6 , 0, 0, 0, 0) où c _2,4 , c _2,5 et c _2,6 sont des nombres aléatoires non nuis.

Pour le sous-ensemble S ₃ , le procédé permet de générer un vecteur d’encodage C ₃ égal à (0, 0, 0, 0, 0, 0, c _3,7 , c _3,8 , c _3,9 , c _{3,i 0} ) où c _3,7 , c _3,8 , c _3,9 et c _{3,i 0} sont des nombres aléatoires non nuis.

Revenant à la figure 3, après l’étape de génération des vecteurs d’encodage, le procédé permet de générer (308) 4 fonctions de parité comme des combinaisons linéaires des blocs de données (a _{1 ;} ..., ai ₀ ) comprenant une fonction de parité primaire f ₀ (a),et 3 fonctions de parité secondaires fi (a), f ₂ (a) et fs (a).

La figure 6 détaille la génération de la fonction de parité primaire f ₀ (a), et les fonctions de parité secondaires f _j (a) j e {1 , 2, 3} selon les principes de l’invention. La fonction de parité primaire (602) est une combinaison linéaire des 10 blocs de données (a _{1 ;} ..., ai ₀ ) et est stockée dans le nœud de parité Nu . A chaque bloc de données a, est associé le coefficient d’encodage c ₀ ,i du vecteur d’encodage primaire C ₀ (400). La fonction de parité primaire f ₀ (a) peut s’écrire selon l’équation suivante:

où les coefficients c _0,i , Co _, 2, , c _0,i o sont des nombres aléatoires non nuis. Comme illustré sur la figure 6, pour générer les 3 fonctions de parité secondaires f _j (a) (1 <=j<=3) (604), le procédé génère d’abord 3 fonctions linéaires g _j (a) (1 <=j<=3) (606). Chaque fonction linéaire g _j (a) est une combinaison linéaire des 1 0 blocs de données (a _{1 ;} ai ₀ ) et des vecteurs d’encodage C, (1 <=j<=3) (500).

La fonction linéaire gi (a) est obtenue par combinaison linéaire des 10 blocs de données (a _{1 ;} ..., a ₁₀ ) et du vecteur d’encodage C _{1 ;} elle peut alors s’écrire:

- gi (a) = ci _,i ^* ai + Ci _,2 ^* a ₂ + Ci _,3 ^* a ₃ .

La fonction linéaire g ₂ (a) est obtenue par combinaison linéaire des 10 blocs de données (a _{1 ;} ..., a ₁₀ ) et du vecteur d’encodage C ₂ , elle peut alors s’écrire:

92(e) = C ₂₄ ^* a ₄ + C ₂ 5 ^* 35 + C ₂ e ^* &6·

De même, la fonction linéaire g ₃ (a) est obtenue par combinaison linéaire des 10 blocs de données (a _{1 ;} ..., a ₁₀ ) et du vecteur d’encodage C ₃ , et peut s’écrire:

93(e) = C ₃₇ ^* 87 + C ₃ 8 ^* as + C ₃ 9 ^* 3g+ C _3, 10 ^* 3io-

Une fois les fonctions g _j (a) (1 <=j<=3) générées, le procédé permet de créer les fonctions de parité secondaires fi (a), f ₂ (a) et f ₃ (a). La fonction de parité secondaire fi (a), est obtenue par la somme de la fonction de parité primaire f ₀ (e) et de la fonction linéaire gi (a). Elle peut être représentée comme ci-après:

- f 1 (a) = f ₀ (e) + gi (a)

De manière similaire, la fonction de parité secondaire f ₂ (a), est obtenue par la somme de la fonction de parité primaire f ₀ (e) et de la fonction linéaire g ₂ (a). Elle peut être représentée comme ci-après:

- f ₂ (a) = f ₀ (e) + g ₂ (a)

De même, la fonction de parité secondaire f ₃ (a), est obtenue par la somme de la fonction de parité primaire f ₀ (e) et de la fonction linéaire g ₃ (a). Elle peut être représentée comme ci-après:

- f ₃ (a) = f ₀ (e) + g ₃ (a)

Les fonctions de parité secondaires fi (a), f ₂ (a), f ₃ (a) sont stockées respectivement dans les noeuds de parité N ₁₂ , N _{1 3} et N _{1 4} (208). Avantageusement, les fonctions linéaires gi (a), g ₂ (a), g ₃ (a) et la fonction de parité primaire f ₀ (e) sont générées de façon à être linéairement indépendantes entre elles. Par ailleurs, la somme de deux de ces fonctions quelconques est également linéairement indépendante des autres fonctions. Enfin, avantageusement, tous les blocs de données étant linéairement indépendants, le code Babylon maintient les mêmes propriétés qu’un code RS.

Les figures 7a à 7c illustrent les étapes de détection de pannes et de reconstruction du contenu de noeuds systématiques et de noeuds de parité selon les principes de l’invention.

Comme illustré sur la figure 7a, le procédé est initié (702) quand une information relative à la détection d’une panne dans le système de stockage est disponible indiquant le nombre de pannes (704). Pour les cas où le nombre de pannes est supérieur ou égal à cinq, le procédé de réparation ne peut être opérant et le système est considéré comme défectueux (706). Pour les cas où le nombre de pannes est compris entre deux et quatre pannes, les deux, trois ou quatre noeuds en panne peuvent être reconstruits selon des méthodes de réparation connues (708), de type Erasure Code ou Reed Solomon.

Le procédé revendiqué selon le code Babylon opère pour les cas où un seul nœud de stockage dans un système de stockage local ou distribué est en panne. Les étapes de réparation vont permettre de retrouver dans les autres nœuds de stockage les données perdues qui étaient contenues dans le nœud en panne et de reconstruire un nouveau nœud de stockage avec les mêmes données. Après qu’une panne est détectée, le procédé détermine la nature du nœud qui est en panne (710), à savoir s’il s’agit d’un nœud systématique ou d’un nœud de parité.

Afin de faciliter la compréhension des principes de l’invention et non par limitation, la méthode de reconstruction 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).

Description de la méthode de décodage de l’invention sur l’exemple d’un système de stockage avec un code (10, 4) :

Si la panne concerne un nœud systématique N,, i e {1 , .., 10}, c’est-à-dire un nœud stockant des blocs de données a,, la reconstruction (712) se fait selon les étapes du procédé décrit en figure 7b.

Si la panne concerne un nœud de parité N,, i e {11 , .., 14}, c’est-à-dire un nœud stockant des fonctions de parité, la reconstruction (714) se fait selon les étapes du procédé décrit en figure 7c. La figure 7b illustre les étapes de reconstruction d’un nœud systématique selon la présente invention.

Pour illustrer le procédé, il est supposé que le bloc a _! se trouvant dans le nœud Ni est perdu, et qu’il faut le reconstruire. Dans une première étape (716), le procédé permet de déterminer à quel sous-ensemble de données S,, j e [1 ,2,3], appartient la donnée a, du nœud N, en panne. Dans l’exemple, le bloc de données a-i appartient au sous-ensemble Si , qui contient les données (ai , a ₂ , a ₃ ). Dans une étape suivante (718), le procédé permet de récupérer les données de la fonction de parité primaire f ₀ (a) qui sont stockées dans le nœud Nu et de récupérer les données de la fonction de parité secondaire f (a) correspondant à l’indice du sous-bloc Si identifié, qui sont stockées dans le nœud N ₁₂ . L’expression « récupérer les données » est utilisée pour désigner des opérations de transfert des données d’un nœud de stockage vers un dispositif collecteur de données. Le dispositif collecteur de données peut être intégré à un contrôleur du système de stockage général, où peut être mis en œuvre le procédé de reconstruction de nœuds. La récupération des données inclut également les opérations de lecture/écriture de/dans des éléments de mémorisation des nœuds de stockage et du dispositif collecteur de données.

Après l’étape de collecte de données, le procédé permet (720) à partir des données récupérées, de calculer la fonction linéaire g _! (a) associée au sous- ensemble de données Dans un mode de réalisation, la fonction linéaire g, (a) est obtenue par soustraction de la fonction de parité primaire f ₀ (a) se trouvant dans le nœud Nu à la fonction de parité secondaire f (a) se trouvant dans le nœud N ₁₂ .

Dans une étape suivante (722), le procédé permet de charger les blocs de données (a2, a3) du sous-ensemble Si à l’exception du bloc ai qui est perdu. En soustrayant ces données de la fonction linéaire gi (a), la donnée ai est retrouvée et le nœud N-i de stockage primaire pour le bloc de données perdu ai est reconstruit (724).

La reconstruction du nœud pour ai , n’a nécessité l’utilisation que de 4 blocs de données {a ₂ , a ₃ , f ₀ (a), f (a)} contrairement à un code RS classique qui aurait nécessité 10 blocs, soit une économie de 60%. De manière similaire, la reconstruction d’un nœud systématique pour tout bloc de données a, pour i e {1 , 2, 3}, ne requière que 4 blocs, en utilisant les blocs de données ayant l’index i e {1 , 2, 3}\{i}, c’est-à-dire sauf le bloc de données d’index i correspondant au nœud N, en panne, et en utilisant les blocs de données des fonctions de parité primaire f ₀ (a) et de parité secondaire fi (a).

La reconstruction d’un nœud systématique pour tout bloc de données a, pour i e {4, 5, 6} requière 4 blocs, en utilisant les blocs de données ayant l’index i e {4, 5, 6}\{i} et en utilisant les blocs de données des fonctions de parité primaire f ₀ (a) et de parité secondaire f ₂ (a).

La reconstruction d’un nœud systématique pour tout bloc de données a, pour i e {7, 8, 9, 10} requière 5 blocs, en utilisant les blocs de données ayant l’index i e {7, 8, 9, 10}\{i} et en utilisant les blocs de données des fonctions de parité primaire f ₀ (a) et de parité secondaire f ₃ (a).

La figure 7c illustre les étapes de reconstruction d’un nœud de parité selon la présente invention.

Les nœuds N,, i e [11 ,14] contiennent les fonctions de parité primaire f ₀ (a) et secondaires fi (a), f ₂ (a), f ₃ (a). Le procédé détermine (726) tout d’abord si le nœud à réparer est le Nu qui contient la fonction de parité primaire f ₀ (a). Si oui, le procédé permet de transférer (728) les données fi (a) et celles du sous- ensemble Si contenant a _{1 ;} a ₂ et a ₃ des nœuds N _12, N^ N _{2 et} N ₃ . Dans une étape suivante (730), le procédé permet de générer la fonction linéaire g _! (a) à l’aide des données a _{1 ;} a ₂ et a ₃ , puis de décoder la fonction de parité primaire f ₀ (a) en soustrayant la fonction linéaire g _! (a) de la fonction de parité fi (a). Le procédé permet ensuite de reconstruire le nœud Nu .

De façon similaire que les nœuds i, i e {1 , 10}, la réparation de Nu ne nécessite que 4 blocs de données (fi (a), a _! , a ₂ et a ₃ ). Revenant à l’étape (726), si le nœud à réparer est un nœud_de parité N, tel que i e [12,14], le procédé permet de charger (734) les données du nœud Nu qui contient la fonction de parité f ₀ (a), et charger les données des sous- ensembles S ₁ . Dans une étape suivante (736), le procédé permet de générer la fonction linéaire gi-n (a) à l’aide des données des sous-ensembles S.-n et de décoder la fonction de parité fi-n (a) en effectuant la somme de la fonction de parité primaire f ₀ (a) et de la fonction linéaire gi-n (a). Le procédé permet ensuite de reconstruire (738) le nœud N,, i e [12,14]

Ainsi, pour la reconstruction du nœud N ₁₂ contenant la fonction de parité secondaire fi (a), le procédé permet de charger la fonction de parité f ₀ (a) du nœud Nu et les données du sous-ensemble Si (ai du nœud N _{1 ;} a ₂ du nœud N ₂ et a ₃ du nœud N ₃ .). Dans un premier temps, la fonction de parité g _! (a) est générée à l’aide des données ai , a ₂ ei a ₃ du sous-ensemble Si . Ensuite, la fonction de parité secondaire fi (a) est décodée en effectuant la somme de f ₀ (a) et g _! (a) et le nœud N ₁₂ est reconstruit.

De même, pour la reconstruction du nœud N ₁₃ contenant la fonction de parité secondaire f ₂ (a), le procédé permet de charger les données du nœud Nu qui contient la fonction de parité f ₀ (a) et les données du sous-ensemble S ₂ . Dans un premier temps, la fonction de parité g ₂ (a) est générée à l’aide des données a ₄ , a ₅ et a ₆ du sous-ensemble S ₂ . Ensuite, la fonction de parité secondaire f ₂ (a) est décodée en effectuant la somme de f ₀ (a) et g ₂ (a) et le nœud N ₁₃ est reconstruit.

Enfin, pour la reconstruction du nœud N ₁₄ contenant la fonction de parité secondaire f ₃ (a), le procédé permet de charger la fonction de parité f ₀ (a) contenue dans le nœud Nu et les données du sous-ensemble S ₃ . Dans un premier temps, la fonction de parité g ₃ (a) est générée à l’aide des données a ₇ , a ₈ , a ₉ , et a ₁₀ du sous-ensemble S ₃ . Ensuite, la fonction de parité secondaire f ₃ (a) est décodée en effectuant la somme de f ₀ (a) et g ₃ (a) et le nœud N ₁₄ est reconstruit.

Il est à noter que la réparation des nœuds N ₁₂ , et N ₁₃ ne nécessite que le transfert de 4 blocs de données, respectivement (f ₀ (a), a _{1 ;} a ₂ et a ₃ } et (f ₀ (a), a ₄ , a ₅ et a ₆ }, et que la réparation du nœud N ₁₄ nécessite le transfert de 5 blocs de données {f ₀ (a), a ₇ , a ₈ , a ₉ , ai ₀ }.

Ainsi avantageusement, le procédé de reconstruction revendiqué ne nécessite que 4 ou 5 blocs de données pour la reconstruction d’un nœud quelconque i e {1 , .., 14}. Il permet de réduire la bande-passante et les entrées/sorties de 50% à 60% par rapport à un code RS.

Il est maintenant décrit le principe général de la méthode de codage de l’invention pour un code quelconque (k, r) :

Partant d’une donnée a en entrée de taille M, le principe général de l’invention consiste à diviser la donnée en k blocs de données (ai , ..., a _k ), chaque bloc ayant une taille M/k. Chaque bloc de données a, stocké dans le nœud N, est de taille fixe m=M/k.

Les notations suivantes sont convenues pour la suite de la description:

[ X J exprime la partie entière de X ; et

[ X} exprime la partie entière par excès de X.

La méthode de codage Babylon commence par une étape de division des k blocs de données (ai , ..., a _k ) en ^r- 1 ) sous-ensembles (Si , S ₂ , .., S _r-i ), notés Sj , 1 < j < r -1 . Si k est un multiple de r-1 , les sous-ensembles ont une même taille k/r-1 . Si k n’est pas un multiple de r-1 , chacun des r-1 -q premiers sous-ensembles est composé de t _f blocs de données, et les q sous-ensembles suivants contiennent t _c blocs de données avec : tf =[ k /r-lj, te =[ k /r-1], q = k mod(r-l)

Le premier sous-ensemble Si est composé de blocs de données appartenant à (a _{1 ;} a _tf ). Le j ^eme sous-ensemble S _j est composé de blocs de données appartenant à (a _(j.1)tf+1 , a _jtf ), pour (1 < j <r -1 ).

La deuxième étape du procédé consiste à générer r vecteurs d’encodage comprenant un vecteur d’encodage primaire C ₀ et r-1 vecteurs d’encodage secondaires C _j (1 <=j<=r-1 ).

Le vecteur d’encodage primaire C ₀ est composé de k coefficients d’encodage c _0,i à c ₀ ,k où chaque coefficient d’encodage primaire c ₀ ,i correspond à un nombre aléatoire non nul.

Un vecteur d’encodage secondaire C _j est composé de k coefficients d’encodage Cj,i à Cj, _k . Pour générer un vecteur d’encodage secondaire C _j , le procédé vérifie, pour chaque bloc a,, si le bloc a, appartient au sous-ensemble Sj . Si c’est le cas, alors le procédé permet d’associer aux coefficients C _j, , des nombres aléatoires non nuis, et si le bloc a, n’appartient pas au sous-ensemble S _j alors le procédé permet d’associer aux coefficients C _j, , des nombres aléatoires nuis.

La structure des vecteurs d’encodage C ₀ à C _r-i est représentée ci-après :

^C 0 =[ ^C 0,1 > ^C 0,2’"’ ^C 0,k]

c ₂ =[0,..,0,c _{2 tf+1} ,..,c ₂ 0,..,0] c r-q =[0,..,0,c r-q,(r-q-1)tf+1 _. ,..,c r-q,(r-q)tc ,0,..,0] c r-q+1 =[ ^L 0,..,0,c r-q+1,(r-q)tc+1 ,..,c r-q+1,(r-q)tc ,0,..,01 ^{J C} r-1 =[0,.. ,.. , .. ,0,C _r _i _{rtc+ i} , .. ,C _r _i _k ]·

Après l’étape de génération des vecteurs d’encodage, le procédé permet de générer r fonctions de parité, combinaisons linéaires des données (ai , a _k ) et composées d’une fonction de parité primaire f ₀ (a) et de r-1 fonctions de parité secondaires fi (a), f _r _i (a).

La fonction de parité primaire est une combinaison linéaire des k blocs de données (a _{1 ;} a _k ) et est stockée dans le nœud de parité d’index k+1 , N _k+1 . A chaque bloc de données a, est associé le coefficient d’encodage c ₀ ,i du vecteur d’encodage primaire C ₀ . La fonction de parité primaire f ₀ (a) peut s’écrire selon l’équation suivante:

- f ₀ (a)=c _0,i ^* 3. \ + Co _: 2* &2 + . + Co _,k ^* a _k

où les coefficients c _0,i , Co _, 2, , c _0,k sont des nombres aléatoires non nuis.

Pour générer les r-1 fonctions de parité secondaires f _j (a) (1 <=j<=r-1 ), le procédé permet de générer d’abord r-1 fonctions linéaires g _j (a) (1 <=j<=r-1 ). Chaque fonction linéaire g _j (a) est une combinaison linéaire des k blocs de données (a _{1 ;} a _k ) et des vecteurs d’encodage C _j (1 <=j<=r-1 ). Une fois les fonctions linéaires g _j (a) (1 <=j<=r-1 ) générées, le procédé permet de créer les fonctions de parité secondaires fi (a), f ₂ (a), ... f _r _i (a) tel qu’une fonction de parité secondaire f _j (a), 1 < j< r - 1 , est obtenue en additionnant la fonction de parité primaire f ₀ (a) à une fonction linéaire g _j (a) :

- f _j (a)= f ₀ (a) + g _j (a).

Les blocs de données et les fonctions de parité générées selon le codage de l’invention sont stockés dans des nœuds de stockage d’un système de stockage local ou distribué. Les k blocs de données (a _{1 ;} ..., a _k ) sont stockés dans k nœuds systématiques N,, i e {1 , .., k}, et chacun des r blocs de parité obtenu par une fonction de parité est stocké dans un nœud de parité N,, i e {k+1 , .., k+r}, comme illustré sur la table ci-dessous :

Node 1

Node k

Node k+1

Node k+2

Node k+r

Avantageusement, les fonctions linéaires g, (a), 1 < j< r-1 et la fonction de parité primaire f ₀ (a) sont générées de façon à être linéairement indépendantes entre elles. Par ailleurs, la somme de deux de ces fonctions quelconques est également linéairement indépendante des autres fonctions. Enfin, avantageusement, tous les blocs de données étant linéairement indépendants, le code Babylon maintient les mêmes propriétés qu’un code RS.

Il est maintenant décrit le principe général de la méthode de reconstruction de l’invention pour un code quelconque (k, r). Le procédé de reconstruction est initié quand une information relative à la détection d’une panne dans le système de stockage est disponible. Le procédé peut être initié pour dupliquer le contenu d’un nœud. Le procédé de reconstruction en cas de panne opère pour les cas où un seul nœud de stockage dans un système de stockage local ou distribué est en panne. Les étapes de réparation vont permettre de retrouver dans les autres nœuds de stockage les données perdues qui étaient contenues dans le nœud en panne et de reconstruire un nouveau nœud de stockage avec les mêmes données.

Lorsqu’une panne est détectée, le procédé détermine la nature du nœud qui est en panne, à savoir s’il s’agit d’un nœud systématique ou d’un nœud de parité systématique.

Si la panne concerne un nœud systématique N,, i e {1 , .., k}, c’est-à-dire un nœud stockant des blocs de données a,, la reconstruction se fait selon le cas 1 décrit ci-après.

Si la panne concerne un nœud de parité N,, i e {k+1 , .., k+r}, c’est-à-dire un nœud stockant des fonctions de parité, la reconstruction se fait selon le cas 2 décrit ci-après.

- Cas 1 : Reconstruction des nœuds N,, ie {1 , .., k}

En considérant une réparation de la donnée a, stockée dans un nœud N, tel que (1 < i < k) avec a, e S, et (1 < j < r), le procédé permet initialement de transférer les données contenues dans les nœuds d’index k+1 , N _{(k+1 )} et d’index k+1 +j , N _{(k+i +j)} . Ensuite, la donnée fo(s), stockée dans le nœud d index k+1 , N _{(k+1 )} , est soustraite de la donnée f _j (a) stockée dans le nœud d’index k+1 +j, N _(k+1+j) pour récupérer la fonction linéaire g, (a) associée au sous-ensemble S _j . Le procédé permet ensuite de transférer les données du sous-ensemble S _j \{ai} (c’est-à-dire à l’exception du bloc de aonnées a,). L’utilisation de la fonction linéaire g _j (a) permet de décoder la donnée perdue a,. Le nombre de blocs de données nécessaires pour reconstruire a, est donc (t _f + 1 ) si i appartient aux (r- 1 -q) premiers sous-blocs. Si i appartient aux q derniers sous-blocs, le nombre total de blocs de données requis est (t _c + 1 ).

- Cas 2 : Reconstruction des nœuds N,, i e {k+1 , k+r}

Comme dans le cas précédent, pour la reconstruction du nœud N, tel que k + 1 < i < k + r, le procédé permet de transférer la donnée f ₀ (a) stockée dans le nœud d’index k+1 , N _{(k+1 )} , et les données se trouvant dans le sous-ensemble S, _k+i . La fonction linéaire gi- _k+i (a) est obtenue à partir des données du sous ensemble S _i-k+i . Ensuite, le décodage est réalisé en utilisant la fonction primaire f ₀ (a) et la fonction linéaire gi- _k+i (a) pour retrouver la fonction secondaire fi- _k+i (a) (en effet, f i_ _k+i (a) = f ₀ (a) + gi- _k+i (a)). Il est à noter que si (i - k + 1 ) appartient aux (r-1 -q) premiers blocs, la réparation requière (t _f +1 ) blocs de données. Si

(i-k+1 ) e {r— q,..,r-1 }, alors la réparation nécessite (t _c +1 ) blocs.

Pour le cas particulier du nœud d’index k+1 , N _k+i contenant la fonction de parité primaire f ₀ (a), le procédé permet de transférer le premier sous-ensemble Si pour générer la fonction linéaire gi (a). Le procédé permet ensuite de transférer les données du nœud d’index k+2, N _k+2 contenant la fonction de parité secondaire f 1 (a). En soustrayant la fonction linéaire gi (a) de la fonction de parité secondaire fi (a), la fonction de parité primaire f ₀ (a) est décodée (en effet, f ₀ (a) = fi (a) - gi (a)). La donnée du nœud d’index k+1 , N _k+i contenant la fonction de parité primaire f ₀ (a) est retrouvée en utilisant (t _f + 1 ) blocs de données.

De manière générale, la valeur moyenne des données transférées et lues pour la reconstruction/réparation, quelque soit le type de nœud, est donnée par l’équation suivante : II est à noter que la description prend exemple pour une valeur de r >=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 Si et S ₂ , où Si est composé des t _s premiers blocs et S ₂ contient les k-t _s derniers blocs, où t _s =|k /rj. Avantageusement, le procédé ae 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 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 nœud de stockage de remplacement du nœud 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 matrices où l’ensemble des blocs de données des k nœuds 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 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).

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 pourcentages dans le tableau sont calculés en tenant en compte de la réparation des nœuds systématiques et des nœuds 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 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 une seule panne les codes régénérateurs nécessitent la lecture de toutes les données stockées dans les nœuds 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 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 à 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 nœuds.

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 œuvre par ordinateur. Il est décrit un produit 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 œuvre de l’invention comprend un support de stockage lisible par ordinateur (RAM, ROM, mémoire flash ou une autre technologie de mémoire, par exemple support à disque ou un autre support de stockage non transitoire lisible par ordinateur) codé avec un 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 œuvre l'invention, un dispositif peut comporter un 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 œuvre de l'invention; une mémoire vive 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 « Input/ouput » en anglais) adaptée à transmettre et à recevoir des données. Dans le cas où l'invention est 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 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 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 des interfaces de programmation API) qui peut être utilisé pour programmer un ou plusieurs processeurs pour mettre en œuvre 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 n'importe quel processeur approprié (par exemple, un microprocesseur) ou cœur de processeur ou un ensemble de processeurs, qu'ils soient prévus dans un 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, etc) peuvent être utilisées.