Brevet FR3045857A1 — publié le 20170623

Arrière-plan de l'invention L'invention se rapporte au domaine général du traitement automatisé de données par un système informatique. Elle concerne plus particulièrement un procédé de classement par un dispositif informatique d'un ensemble d'éléments représentatifs de données (ex. données numériques). Aucune limitation n'est attachée au type de données considérées, il peut s'agir aussi bien de données collectées par des capteurs, par des applications (ex. réseaux sociaux, etc.), par des medias, etc. On assiste aujourd'hui à une explosion quantitative des données créées, échangées et stockées à travers le monde : on serait ainsi passé d'un volume de données proche de 1.2 zettaoctets par an en 2010 (1 zettaoctet désignant un milliard de téraoctets), à 1.8 zettaoctets en 2011, puis 2.8 zettaoctects en 2012 tandis que les prévisions pour 2020 seraient de 40 zettaoctets. Ces ensembles de données, aussi couramment désignés par l'appellation « Big Data » en anglais, sont tellement volumineux qu'ils rendent en pratique inappropriés et inefficaces les outils de gestion classiques de bases de données ou de gestion de l'information. Les perspectives de traitement de ces données sont pourtant très importantes et prometteuses. On envisage notamment de nouvelles possibilités d'exploration de l'information diffusée par les medias, de connaissance et d'analyse tendancielle et prospective, notamment en matière climatique, environnementale ou encore sociopolitique, de gestion des risques, etc. La société actuelle et les entreprises plus particulièrement ont pris conscience de l'intérêt d'exploiter ces données. Le phénomène de Big Data s'accompagne ainsi du développement de diverses applications à visée analytique notamment, destinées à permettre de traiter ces données et d'en extraire des informations. Ces applications s'appuient sur une répartition des données et une parallélisation massive sur un cluster (ensemble) de machines ou de dispositifs informatiques des traitements qui sont appliqués à ces données en vue de réduire le temps nécessaire à leur analyse. La gestion du temps constitue aujourd'hui l'un des principaux enjeux dans le contexte des Big Data. Une phase cruciale de cette parallélisation massive est de router au même endroit les données qui doivent être analysées ensemble, idéalement de façon contigüe pour des raisons évidentes de gain de mémoire et de rapidité d'exécution. Pour cela, il est commun que les applications Big Data associent à chaque donnée élémentaire un élément constitué d'une clé (dite de classement dans la suite de ce document) et d'une valeur de la donnée, et trient les données selon cette clé. Cette phase de tri est une des phases les plus coûteuses en temps parmi les traitements appliqués aux données. En effet, alors que les autres phases de traitement Big Data ont un temps d'exécution qui croit linéairement avec le nombre n de données à analyser par chaque instance de traitement (i.e. par chaque machine du cluster de machines sur lesquelles sont distribués et effectués les traitements des données), la phase de tri croît quant à elle en n log(n). 3045857 2 A titre d'exemple, l'une des applications les plus utilisées aujourd'hui pour les traitements BigData est le traitement MapReduce proposé par Google permettant de manipuler de très grandes quantités de données en les distribuant sur un cluster de machines pour les traiter. Ce traitement est décrit notamment dans le document US 7 650 331, et illustré schématiquement à la 5 figure 1. Il s'appuie sur la mise en oeuvre deux fonctions « map » et « reduce ». Plus précisément, en référence à la figure 1, les données stockées 1 à traiter sont découpées en blocs 2 de données élémentaires non triées, distribués ensuite à une pluralité d'instances « map » 3 pour un traitement parallèle. Chaque instance « map » 3 applique sur le bloc de données 2 qui lui est transmis un premier traitement 3-1 dit « M-Process » produisant à 10 partir des données élémentaires des éléments se présentant sous la forme de couples ou de paires (clé,valeur). Puis une fonction de tri « Sort » 3-2 produit à partir de ces éléments un fichier de sortie trié et découpé en un nombre de partitions égal au nombre d'instances « reduce » 4 considérées pour traiter les données élémentaires du bloc 2. Chaque partition contient une liste d'éléments (clé,valeur) destinée à une instance « reduce » 4 distincte. Chaque fichier de sortie est 15 stocké dans un fichier intermédiaire par une fonction de stockage « Store/Merge » 3-3. Puis, chaque instance « reduce » 4 récupère auprès des instances « map » concernées les partitions qui lui correspondent dans les fichiers intermédiaires ainsi stockés. Ces partitions, dont chaque contenu est trié, sont alors triées entre elles par l'instance « reduce » 4 lors d'une phase « Shuffle/Merge » 4-1. Ce tri permet de s'assurer que toutes les paires correspondant à des 20 clés identiques se suivent pour un traitement « R-process » 4-2 efficace des données par l'instance « reduce » 4. Le tri effectué par la fonction de tri « sort » de l'instance « map » 3 requiert comme mentionné précédemment, en s'appuyant sur les algorithmes de tri connus actuellement, un temps d'exécution en nlog(n) où n désigne le nombre d'éléments informatiques de type (clé, valeur) à 25 trier et produits par le traitement « M-process ». Cette phase de tri peut occuper à titre illustratif entre 30% et 40% du temps d'exécution du traitement MapReduce. Le tri effectué lors de la phase «Shuffle/Merge » par l'instance « reduce » 4 demande un temps d'exécution linéaire en n car il s'applique à des fichiers eux-mêmes déjà triés. Bien qu'étudiés depuis de nombreuses années, il n'existe malheureusement aucun 30 algorithme de tri connu actuellement qui permette d'obtenir un temps d'exécution inférieur à nlog(n). Cela signifie que le temps de traitement des données augmente plus rapidement que le volume de données à traiter dans les blocs de données élémentaires, ce qui constitue une sérieuse limite pour les traitements de type Big Data. 35 Objet et résumé de l'invention L'invention vient notamment palier cet inconvénient en proposant un procédé de classement , par un dispositif informatique dit de classement, d'un ensemble d'éléments stockés 3045857 3 dans un espace de stockage, chaque élément comprenant une clé de classement associée à une valeur de donnée, ce procédé de classement comprenant : une première étape de classement dans une structure de données informatique de pointeurs vers les éléments stockés dans l'espace de stockage, cette première étape de classement 5 comprenant, pour chaque élément : o une étape d'obtention d'une valeur de hachage en appliquant une fonction de hachage à la clé de classement de l'élément; o une étape de détermination, à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément 10 dans la structure de données informatique ; et o une étape d'insertion de ce pointeur dans la structure de données informatique à l'indice de position ainsi déterminé ; et une deuxième étape de classement comprenant, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, un classement de ces pointeurs 15 entre eux en appliquant une première relation d'ordre prédéfinie aux clés de classement des éléments informatiques vers lesquels pointent ces pointeurs. Corrélativement, l'invention vise aussi un dispositif informatique de classement d'un ensemble d'éléments stockés dans un espace de stockage, chaque élément comprenant une clé de classement associée à une valeur de donnée, ce dispositif de classement comprenant : 20 un premier module de classement, configuré pour classer dans une structure de données informatique des pointeurs vers lesdits éléments stockés dans l'espace de stockage, ce premier module de classement comprenant une pluralité de modules activés pour chaque élément et comprenant : o un module d'obtention, configuré pour obtenir une valeur de hachage en appliquant 25 une fonction de hachage à la clé de classement de l'élément; o un module de détermination, configuré pour déterminer à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément dans la structure de données informatique ; et o un module d'insertion, configuré pour inséré ledit pointeur dans la structure de 30 données informatique à l'indice de position ainsi déterminé ; et un deuxième module de classement configuré pour, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, classer ces pointeurs entre eux en appliquant une première relation d'ordre prédéfinie aux clés de classement des éléments informatiques vers lesquels pointent ces pointeurs. 35 Par structure de données informatique, on entend tout type de structure permettant de stocker des éléments informatiques et de les trier. De telles structures sont bien connues en informatique ; il s'agit par exemple de bases de données, de tableaux dont les éléments sont des arbres binaires triés ou des listes chaînées, etc. 3045857 4 Par ailleurs, on entend par pointeur au sens de l'invention, une variable liée de façon univoque à l'élément sur lequel elle pointe. Dans une variante privilégiée de réalisation, une telle variable contient une adresse mémoire correspondant à la case mémoire occupée par l'élément dans l'espace de stockage (tel un pointeur informatique). En stockant dans la structure de données 5 les adresses mémoire des éléments plutôt que les éléments à proprement parler, on peut limiter la taille de la structure de données requise pour mettre en oeuvre l'invention. Dans une autre variante, cette variable peut contenir l'élément directement. Ainsi l'invention propose, comme dans l'état de la technique, un tri des éléments qui lui sont fournis sous une forme (clé de classement, valeur de donnée) en considérant comme critère 10 de classement la clé de classement de chacun des éléments. Toutefois, contrairement à l'état de la technique, l'invention ne s'emploie pas à trier tous les éléments entre eux selon un unique et même ordre que l'on pourrait qualifier de « naturel », par exemple selon un ordre alphabétique, ou de manière plus générale selon toute relation d'ordre au sens mathématique du terme, transitive, réflexive et asymétrique, et qui serait définie pour le traitement envisagé des données. 15 Au contraire, l'invention tire profit du fait que ce qui importe dans un contexte Big Data notamment, c'est que tous les éléments associés à une même clé soient rassemblés, pour ensuite pouvoir être regroupés entre plusieurs dispositifs de classement et le cas échéant triés entre eux. L'invention utilise avantageusement cette souplesse pour proposer un classement plus rapide et moins complexe que celui de l'état de la technique. 20 A cet effet, l'invention procède en deux temps et utilise de façon surprenante, pour réaliser un classement des éléments qui lui sont fournis en entrée, une fonction de hachage connue pour son aptitude à mélanger les données sur lesquelles elle est appliquée afin de générer un résultat aléatoire. En effet, de façon connue, une fonction de hachage est une fonction déterministe qui appliquée sur une valeur d'entrée produit un entier de longueur prédéfinie (ex. 32 25 bits ou 64 bits), aussi appelé valeur de hachage, qui semble aléatoire, c'est-à-dire que deux valeurs d'entrée proches produisent des valeurs de hachage statistiquement décorrélées. De telles fonctions sont connues et classiquement utilisées en informatique ou dans le domaine de la cryptographie. Plus précisément dans un premier temps, via l'application lors de la première étape de 30 classement d'une telle fonction de hachage sur les clés des éléments à classer, l'invention conduit, du fait des propriétés inhérentes de cette fonction, à une répartition aléatoire et relativement uniforme des éléments (ou de façon équivalente, des pointeurs vers ces éléments) sur la structure de données informatique considérée. Cette structure de données est par exemple un tableau à deux dimensions, dont une des dimensions correspond aux indices de position et l'autre dimension 35 correspond, pour chaque indice de position, à une liste chaînée comprenant les pointeurs des éléments informatiques associés à cet indice de position. Grâce aux propriétés de la fonction de hachage et à l'utilisation de m bits de la valeur de hachage pour déterminer un indice de position du pointeur dans la structure de données, on a 3045857 5 une utilisation quasi optimale de cette structure de données : à l'issue de la première étape de classement, si le nombre m est bien dimensionné par rapport au nombre d'éléments à classer, peu de positions dans cette structure ne sont pas remplies, et peu de positions sont occupées par un nombre élevé de pointeurs. On note que l'application d'une fonction de hachage et l'extraction de 5 m bits de chaque valeur de hachage obtenue sont des opérations classiques en soi, de faible complexité. Il en résulte qu'à l'issue de la première étape de classement, les éléments informatiques sont en grande partie déjà « pré-triés » dans la structure informatique par l'intermédiaire de leurs pointeurs. Ce pré-tri est certes imparfait, et ne correspond pas à une 10 relation d'ordre à proprement parler entre les clés puisque ce sont les valeurs de hachage aléatoires (ou plus précisément m bits de ces valeurs de hachage) qui sont utilisées pour classer les pointeurs dans la structure de données. Toutefois, chaque clé est associée dans la structure de données informatique à un entier mathématique aléatoire et reproductible qui désigne sa position dans la structure de données informatique. Ainsi, les éléments associés via leurs pointeurs à un 15 indice de position I+1 sont a priori supérieurs, au moins selon leur classement dans la structure de données, aux éléments associés à un indice de position I et ce pour tout indice I. Par conséquent, ces éléments correspondant à des indices de position différents dans la structure de données n'ont pas besoin d'être triés entre eux. Grâce à ce pré-tri conduisant à une répartition uniforme ou quasi uniforme des 20 pointeurs des éléments informatiques dans la structure de données, l'invention permet de limiter la complexité du tri effectué dans un deuxième temps lors de la deuxième étape de classement. Le tri effectué lors de cette deuxième étape de classement se borne à ordonner entre eux les éléments dont les pointeurs sont positionnés au même endroit dans la structure, c'est-à-dire associés au même indice de position. On note que des pointeurs peuvent être positionnés au même endroit 25 dans la structure pour diverses raisons. Ainsi par exemple, la fonction de hachage appliquée sur les clés correspondant aux éléments sur lesquels pointent ces pointeurs peut donner des valeurs de hachage identiques (phénomène de collision), ou les m bits consécutifs extraits des valeurs de hachage sont identiques bien que les valeurs de hachage soient différentes, ou encore les clés associés aux éléments sur lesquels pointent ces pointeurs sont identiques. 30 On se limite ainsi lors de cette deuxième étape de classement à un tri entre voisins. Le but de cette deuxième étape de classement est de rendre contigus les pointeurs sur les éléments dont les clés de classement sont égales entre elles. Ce tri certes nécessite toujours un temps d'exécution en klog(k) où k désigne le nombre d'éléments à trier, mais contrairement à l'état de la technique, k n'est plus égal au nombre total d'éléments à trier mais à un nombre fortement réduit 35 égal au nombre d'éléments associés à un même indice de position dans la structure informatique. Pendant la deuxième étape de classement en outre, les pointeurs associés à une même position dans la structure de données peuvent être triés en parallèle pour réduire le temps d'exécution du tri réalisé. 3045857 6 L'invention permet de cette sorte d'atteindre une complexité quasi linéaire en fonction du nombre total d'éléments informatiques à trier. Il convient de noter que le recours à une fonction de hachage permet avantageusement de garantir une répartition uniforme des éléments (et notamment des clés de 5 classement de ces éléments) sur l'ensemble de la structure de données sans avoir d'information a priori sur la composition (ex. entiers, flottants au sens informatique, textes, vidéos, images, sons, etc.), la statistique (distribution des valeurs) ou encore les valeurs de ces éléments ni de celles des clés de classement qui leur sont associées. L'absence de connaissance de telles informations est courante dans un contexte Big Data et cruciale à prendre en compte, car contrairement aux 10 applications de bases de données classiques, les traitements de données de type Big Data s'appliquent à des données de toute nature. Selon la fonction de hachage choisie, il peut bien entendu y avoir des collisions comme indiqué précédemment, c'est-à-dire que des pointeurs sur des éléments associés à des clés de classement distinctes peuvent malgré tout être positionnés à un même indice de position dans la 15 structure de données. Toutefois, d'une part ces collisions sont rares. Et d'autre part, la fonction de hachage assure une répartition quasi uniforme des éléments sur la structure de données de sorte que si collision il y a, le nombre d'éléments à trier résultant de ces collisions reste limité. L'invention permet donc un classement rapide et efficace d'éléments de type paire (clé, valeur). Elle a ainsi une application privilégiée dans un contexte Big Data et notamment, dans 20 une application de type MapReduce dans laquelle elle peut être aisément intégrée au niveau de chaque instance de traitement « Map » pour réaliser le tri « Sort » décrit précédemment en référence à la figure 1. A cet effet, dans un mode de réalisation particulier, le procédé de classement peut comprendre en outre une troisième étape de classement des éléments dans un fichier informatique 25 en parcourant séquentiellement la structure de données informatique. Corrélativement, le dispositif informatique peut comprend en outre un troisième module de classement configuré pour classer dans un fichier informatique lesdits éléments en parcourant séquentiellement ladite structure de données informatique. Le procédé de classement peut également comprendre une étape de transmission de 30 ce fichier à au moins un dispositif de traitement des éléments. Ces modes de réalisation permettent une intégration facile de l'invention dans un traitement de type MapReduce tel que décrit précédemment. L'invention permet donc, dans un contexte Big Data, de limiter le temps d'attente permettant l'exploitation des données et de réduire les coûts d'investissement dans les plateformes 35 de traitement en proposant un procédé de classement de complexité moindre. Dans un mode particulier de réalisation, les m bits extraits de chaque valeur de hachage correspondent aux m bits de poids forts de la valeur de hachage. Ce mode de réalisation simplifie la mise en oeuvre de l'invention. 3045857 7 Le nombre entier m peut être choisi en fonction de divers paramètres. Il résulte en général d'un compromis entre d'une part, la taille de la structure de données (égale à r) et donc incidemment la place que cette structure de données occupe en mémoire au niveau du dispositif informatique de classement, et d'autre part, le temps d'exécution 5 de la deuxième étape de classement, lui-même directement lié au taux de collision d'indices dans la structure (ce taux de collision étant par définition égal à la probabilité que deux clés distinctes sont associées au même indice dans la structure). En effet, plus la structure de données a une grande taille (et donc m est grand), plus elle va être longue à parcourir pour classer les éléments dans un fichier informatique, et plus elle risque de comprendre des emplacements vides selon le 10 nombre d'éléments informatiques à classer. Inversement, plus la structure de données est de petite taille (et donc m est petit), plus il risque d'y avoir des collisions, autrement dit des éléments associés à des clés de classement différentes qui se trouvent classés à une position identique dans la structure de données et qu'il faut alors trier lors de la deuxième étape de classement. Dans un mode particulier de réalisation, le nombre m dépend de la taille de l'espace de 15 stockage dans lequel sont stockés les éléments à classer. Par exemple, le nombre m est choisi de sorte que la structure de données occupe un certain pourcentage de la taille de l'espace dédié au stockage des éléments (ex. 5% ou 16%). Ceci permet de prendre aisément en compte le volume des données que l'on envisage de trier. La taille de la structure informatique ou de façon équivalente le nombre m n'a 20 préférentiellement aucune incidence sur la première relation d'ordre utilisée pour le classement des éléments au moyen de la structure de données. Le nombre m peut donc être choisi de façon indépendante pour chaque dispositif de classement (ex. pour chaque instance de traitement « map » mettant en oeuvre le procédé de traitement). En outre, ce nombre m peut être modifié dynamiquement en cours de traitement, par exemple lorsque les m bits extraits sont les bits de 25 poids forts, en le multipliant ou en le divisant par deux sans que cela n'ait d'incidence sur le classement. Dans un autre mode de réalisation, la première relation d'ordre prédéfinie vérifie les règles suivantes : - une clé de classement A est strictement inférieure à une clé de classement B si la valeur de 30 hachage de la clé de classement A est strictement inférieure à la valeur de hachage de la clé de classement B ; - si les valeurs de hachage de la clé de classement A et de la clé de classement B sont égales, la clé de classement A est strictement inférieure à la clé de classement B si la clé de classement A est strictement inférieure à la clé de classement B conformément à une deuxième relation 35 d'ordre prédéfinie ; - la clé de classement A est égale à la clé de classement B si et seulement si les clés de classement A et B sont égales conformément à la deuxième relation d'ordre. 3045857 8 Ce mode de réalisation définit une première relation d'ordre distincte de la deuxième relation d'ordre bien que s'appuyant sur celle-ci, et particulièrement bien adaptée à la mise en oeuvre de l'invention. La deuxième relation d'ordre prédéfinie est par exemple la relation d'ordre naturel 5 classiquement considérée lors du traitement des données et à laquelle il était fait référence précédemment. Cette relation d'ordre naturel peut consister en un critère de comparaison entre deux éléments qui définit une relation d'ordre au sens mathématique du terme, et qui est en particulier transitif, réflexif et asymétrique. Elle peut dépendre du type de traitement de données dans lequel s'inscrit le classement effectué selon l'invention, autrement dit, dans un contexte Big 10 Data, du type de traitement Big Data envisagé et qui est effectué sur une infrastructure parallélisée composée d'un grand nombre d'ordinateurs incluant le dispositif de traitement selon l'invention. Une telle relation d'ordre peut être définie avantageusement pour tout type de données à traiter. Ainsi, à titre d'exemple, les objets dans le langage de programmation Java possèdent un tel ordre. Les traitements mis en oeuvre dans les applications de type MapReduce 15 présupposent également l'existence d'une telle relation d'ordre qui n'est pas nécessairement celle du langage de programmation sous-jacent utilisé pour programmer l'application, et peut dépendre du traitement Big Data envisagé. En utilisant l'ordre naturel considéré par les applications faisant usage des éléments triés, on s'assure de rendre contigus les pointeurs sur les éléments dont les clés sont égales entre elles suivant l'ordre naturel de ces applications. 20 La première relation d'ordre ainsi définie dans ce mode de réalisation permet en outre à un dispositif de traitement, par exemple à une instance de traitement de type « reduce », qui reçoit de plusieurs dispositifs de classement, des éléments triés et stockés dans des structures informatiques conformément à l'invention et associés aux clés gérées par le dispositif de traitement, de traiter ces éléments au fil de l'eau conformément par exemple à un traitement « R- 25 process » tel que mentionné précédemment en référence à la figure 1. Ce dispositif de traitement n'a pas besoin de connaître le nombre m utilisé par les dispositifs de traitement lors de la première étape de classement mais a seulement besoin d'appliquer la première relation d'ordre pour trier les éléments informatiques non triés provenant de dispositifs de classement distincts. L'invention propose ainsi une solution compatible avec le mode de fonctionnement des instances de traitement 30 de type « reduce » de l'état de la technique. Dans un autre mode de réalisation, l'étape d'application d'une fonction de hachage comprend : - l'application d'une première fonction de hachage à la clé de classement résultant en un entier codé sur un nombre prédéterminé n de bits ; puis 35 - l'application d'une seconde fonction de hachage audit entier résultant en la valeur de hachage. Une telle fonction de hachage « composée » permet d'améliorer la répartition quasi uniforme des éléments informatiques dans la structure informatique de données. 3045857 9 Dans un mode particulier de réalisation, la deuxième étape de classement est mise en oeuvre : après insertion d'un pointeur dans la structure de données informatique à un indice de position déjà associé à au moins un autre pointeur précédemment inséré ; ou 5 après avoir inséré dans la structure de données tous les pointeurs vers les éléments stockés dans l'espace de stockage ; ou périodiquement. Le recours à l'une ou l'autre de ces alternatives résulte d'un choix d'implémentation. Dans un mode particulier de réalisation, les différentes étapes du procédé de 10 classement sont déterminées par des instructions de programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en oeuvre dans un dispositif de classement ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en oeuvre des étapes d'un procédé de classement tel que décrit ci-dessus. 15 Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. 20 Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un 25 signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution 30 du procédé en question. Dispositif informatique de traitement d'éléments comprenant chacun une clé de classement et une valeur de donnée, ledit dispositif informatique de traitement comprenant : - un module d'obtention configuré pour obtenir en provenance d'une pluralité de dispositifs de classement selon l'invention, une pluralité de fichiers informatiques comprenant des éléments 35 classés ; - un module de regroupement configuré pour extraire et regrouper les éléments classés dans chaque fichier informatique comprenant une même clé de classement destinée à être traitée par le dispositif informatique de traitement, en utilisant une fonction de hachage identique à la 3045857 10 fonction de hachage et la première relation d'ordre prédéfinie utilisées par chacun des dispositifs de classement. L'invention vise aussi un système informatique comprenant : une pluralité de dispositifs informatiques de classement selon l'invention aptes à classer des 5 ensembles d'éléments distincts ; et des dispositifs informatiques de traitement selon l'invention aptes à traiter ces ensembles d'éléments. Dans un mode particulier de réalisation, les premiers modules de classement d'au moins deux dispositifs informatiques de classement utilisent des nombres m distincts. 10 Le dispositif de traitement et le système informatique selon l'invention bénéficient d'avantages similaires au procédé et au dispositif de classement selon l'invention. On peut également envisager, dans d'autres modes de réalisation, que le procédé de classement, le dispositif de classement, le dispositif de traitement et le système informatique selon l'invention présentent en combinaison tout ou partie des caractéristiques précitées. 15 Brève description des dessins D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures : 20 la figure 1, déjà décrite, illustre un système informatique de l'état de la technique apte à mettre en oeuvre une application MapReduce pour traiter des données dans un contexte Big Data ; la figure 2 représente, sous forme schématique, un système informatique conforme à l'invention dans un mode particulier de réalisation ; 25 les figures 3 et 4 illustrent de façon schématique, l'architecture matérielle d'un dispositif de classement et d'un dispositif de traitement du système informatique de la figure 2, dans un mode particulier de réalisation ; la figure 5 représente, sous forme d'ordinogramme, les principales étapes d'un procédé de classement selon l'invention tel que mis en oeuvre par un dispositif de classement du système 30 informatique de la figure 2, dans un mode particulier de réalisation ; la figure 6 représente les règles définissant une relation d'ordre utilisée par le procédé de classement illustré à la figure 5 ; et la figure 7 représente, sous forme d'ordinogramme, les principales étapes mises en oeuvre par un dispositif de traitement du système informatique de la figure 2, dans un mode particulier de 35 réalisation. Description détaillée de l'invention 3045857 11 La figure 2 représente, dans son environnement, un système informatique 100 conforme à l'invention, dans un mode particulier de réalisation. Dans l'exemple envisagé à la figure 2, le système informatique 100 est apte à réaliser un traitement de données dans un contexte Big Data. Il s'appuie à cet effet sur une pluralité 5 d'instances de traitement pouvant s'exécuter en parallèle sur un grand nombre d'ordinateurs reliés entre eux via un réseau filaire ou sans fil de sorte à rendre possible l'analyse de gros volumes de données en un temps limité. Aucune limitation n'est attachée au type de données traitées par le système informatique 100, il peut s'agir de données récoltées par des réseaux sociaux, des capteurs, des objets connectés, des applications, etc. 10 Le système informatique 100 comprend plus précisément ici : une pluralité de dispositifs informatiques de classement, 101, conformes à l'invention ; ainsi qu'une pluralité de dispositifs informatiques de traitement, 102, conformes à l'invention et aptes à communiquer avec la pluralité de dispositifs de classement 101. Il convient de noter que tout ou partie des dispositifs de classement 101 et/ou tout ou 15 partie des dispositifs de traitement 102 peuvent être des instances (applications) logicielles colocalisées sur une même machine (i.e. sur un même ordinateur) ou être réparties sur une ou plusieurs machines distinctes. Autrement dit, par dispositif informatique, on entend ici aussi bien un dispositif logiciel tel une application installée sur un ordinateur et s'appuyant sur les éléments physiques et matériel de cet ordinateur, qu'un dispositif matériel et physique tel un ordinateur ou 20 toute autre entité physique ayant une architecture similaire à celle d'un ordinateur. Dans l'exemple envisagé à la figure 2, le système informatique 100 met en oeuvre pour le traitement des données qui lui sont confiées, un traitement de type « MapReduce ». Plus précisément, selon cet exemple, les dispositifs de classement 101 mettent en oeuvre la phase « Map » et les dispositifs de traitement 102 mettent en oeuvre la phase « Reduce ». Les données 25 élémentaires destinées à être traitées par le système informatique 100 sont stockées dans un espace de stockage 103 (disque, mémoire, etc.) avant traitement, sous forme de blocs de données 104, puis après traitement dans un espace de stockage 105 (disque, mémoire, etc.). Toutefois ces hypothèses ne sont pas limitatives en soi de l'invention. En effet, bien que particulièrement bien adaptée à la mise en oeuvre de cet type de traitement, l'invention peut 30 s'appliquer dans d'autres contextes dès lors qu'il s'agit de trier un ensemble d'éléments informatiques en fonction d'une clé de classement comme dans le traitement MapReduce. En outre, une répartition différente des deux phases peut être envisagée, i.e. d'autres dispositifs peuvent participer à la mise en oeuvre de ce traitement. Dans le mode de réalisation décrit ici, chaque dispositif de classement 101 a 35 l'architecture matérielle d'un ordinateur, telle que représentée à la figure 3. Il comprend notamment un processeur 106, une mémoire vive 107, une mémoire morte 108, une mémoire non volatile 109 ainsi qu'un module de communication 110 permettant au dispositif de classement 101 3045857 12 de communiquer notamment, via un réseau filaire ou sans fil ou simplement via des bus de données numériques, avec les dispositifs de traitement 102 et l'espace de stockage 103. La mémoire morte 108 du dispositif de classement 101 constitue un support d'enregistrement conforme à l'invention, lisible par le processeur 106 et sur lequel est enregistré 5 un programme d'ordinateur PROG conforme à l'invention, comportant des instructions pour l'exécution des étapes d'un procédé de classement conforme à l'invention. Ce programme d'ordinateur définit de façon équivalente des modules fonctionnels (et logiciels ici) configurés pour mettre en oeuvre les étapes du procédé de classement selon l'invention, ainsi que dans le mode de réalisation décrit ici, d'autres étapes requises dans la phase 10 Map d'un traitement MapReduce. Ces modules fonctionnels s'appuient ou commandent les éléments physiques matériels 106-110 du dispositif de classement 101 décrits précédemment. Ils comprennent ainsi ici : un module 101A configuré pour mettre en oeuvre un traitement de type « M-process » tel que décrit précédemment en référence à la figure 1 et qui consiste à transformer les données 15 élémentaires fournies au dispositif de classement 101 en éléments informatiques de type paires (clé (de classement), valeur) ; un premier module de classement 101B (comprenant un module d'obtention 101B-1, un module de détermination 101B-2 et un module d'insertion 101B-3), un deuxième module de classement 101C et un troisième module de classement 101D, configurés pour classer 20 conformément à l'invention les éléments fournis par le module 101A ; et un module 101E de stockage dans des fichiers intermédiaires des éléments ainsi classés avant leur transmission pour traitement vers les dispositifs de traitement 102. Les fonctions de ces modules sont décrites plus en détail ultérieurement en référence à la figure 5. 25 Dans le mode de réalisation décrit ici, chaque dispositif de traitement 102 a également l'architecture matérielle d'un ordinateur, telle que représentée à la figure 4. Il comprend notamment un processeur 111, une mémoire vive 112, une mémoire morte 113, une mémoire non volatile 114 ainsi qu'un module de communication 115 permettant au dispositif de traitement 102 de communiquer notamment, via un réseau filaire ou sans fil ou simplement via des 30 bus de données numériques, avec les dispositifs de classement 101 et l'espace de stockage 105. La mémoire morte 113 du dispositif de traitement 102 constitue un support d'enregistrement, lisible par le processeur 111 et sur lequel est enregistré un programme d'ordinateur comportant des instructions pour l'exécution des étapes d'un procédé de traitement de type Reduce. 35 Ce programme d'ordinateur définit de façon équivalente des modules fonctionnels (et logiciels ici) configurés pour mettre en oeuvre les étapes du procédé de traitement Reduce comprenant ici : 3045857 13 - un module 102A d'obtention, configuré pour obtenir des fichiers informatiques contenant des éléments classés par les dispositifs de classement 101 ; - un module 102B de regroupement des éléments classés dans ces fichiers en fonction de leur clé de classement ; et 5 - un module 102C de traitement des éléments regroupés selon un traitement R-process. Les fonctions de ces modules sont décrites plus en détail ultérieurement en référence à la figure 7. Nous allons maintenant décrire, en référence aux figures 5 à 7, les différents traitements mis en oeuvre par le système informatique 100, respectivement par chacun des 10 dispositifs de classement 101 et chacun des dispositifs de traitement 102, pour traiter des données stockées dans l'espace de stockage 103 sous la forme de blocs de données 104. La figure 5 représente les principales étapes mises en oeuvre par chacun des dispositifs de classement 101 de la figure 2, dans un mode particulier de réalisation. Ces étapes comprennent en particulier les étapes d'un procédé de classement selon l'invention. 15 On suppose qu'un dispositif de classement 101 reçoive, via son module de communication 110, un bloc de données élémentaires 104 à trier (étape E10). Ce bloc de données élémentaires 104 est fourni par le module de communication 110 au module 101A du dispositif de classement 101. Le bloc de données élémentaires 104 est transformé par le module 101A via un 20 traitement « M-process » en un ensemble E d'éléments (informatiques), chaque élément Ei de l'ensemble E comprenant ici une paire (clé de classement Ki, valeur de donnée VALi) notée dans la suite de la description de façon plus simple (Ki,VALi), i=1,...,N où N est un entier désignant le nombre d'éléments dans l'ensemble E (étape E20). Chaque clé de classement Ki est une donnée informatique codée sur plusieurs octets, telle que par exemple une chaîne textuelle, numérique, 25 alphanumérique, une image, un objet Java, etc. Les clés de classement Ki, i=1,...,N peuvent être de longueur fixe ou variable. Aucune limitation n'est attaché au type de traitement « M-process » considéré. Il peut s'agir d'un traitement quelconque. On suppose ici, par souci de simplification, que l'ensemble E contient des éléments 30 associés à des clés de classement destinées à être traitées par un unique dispositif de traitement 102. Toutefois, l'invention ne se limite pas à cette hypothèse simplificatrice. En variante, le bloc de données 104 peut comprendre des données destinées à être traitées par plusieurs dispositifs de traitement distincts 102. Dans cette variante, le procédé de classement comprend une étape supplémentaire qui consiste à répartir dans des ensembles E distincts les éléments associés aux 35 clés destinées à être traitées par chacun des dispositifs de traitement 102 concernés par le bloc de données 104. Autrement dit, à l'issue de cette étape, on a un ensemble E par dispositif de traitement 102 concerné par les données contenues dans le bloc 104. Les étapes décrites ci-après sont alors appliquées successivement ou en parallèle à chacun de ces ensembles E. 3045857 14 L'ensemble E ainsi obtenu est stocké par le module 101 en mémoire, par exemple dans la mémoire non volatile 109 du dispositif de traitement 101 : chaque élément Ei de l'ensemble E est stocké dans une case mémoire de la mémoire 109, ayant pour adresse Ai. L'adresse Ai est un pointeur sur l'élément Ei au sens de l'invention. L'ensemble A des adresses Ai 5 est également stocké par le module 101A dans la mémoire non volatile 109. Puis, le dispositif de classement 101 procède, via son premier module de classement 101B, à une première étape de classement de toutes les adresses contenues dans l'ensemble A dans une structure de données informatique S (étape E30). Dans le mode de réalisation décrit ici, la structure de données informatique S est un 10 tableau de listes chaînées L(k), k=1,...,M où M désigne la taille du tableau S (i.e. nombre de positions possibles dans le tableau, chaque position indexée par k contenant une liste chaînée L(k)). Toutefois, tout autre type de structure de données permettant de stocker des éléments au sens général du terme de façon ordonnée peut être utilisée en variante, telle que par exemple une base de données, un tableau d'arbres binaires triés, etc. 15 En variante, le premier module de classement 101B peut opéré directement sur l'ensemble E des éléments, ou sur une autre variable reliée de manière univoque aux éléments de l'ensemble E. Au sens de l'invention, un élément Ei et son adresse mémoire Ai constituent l'un comme l'autre des pointeurs sur l'élément Ei. Plus précisément, lors de l'étape E30, pour chaque élément Ei de l'ensemble E (étape 20 d'incrémentation E31), i désignant un compteur initialisé à zéro à l'étape E20, le module d'obtention 101B-1 du premier module de classement 101B calcule tout d'abord une valeur de hachage associée à l'élément Ei en appliquant sur la clé de classement Ki de l'élément Ei une fonction de hachage HASH (étape E32). Une telle fonction de hachage est connue dans le domaine informatique et 25 cryptographique et n'est pas décrite très en détail ici. Dans le mode de réalisation décrit ici, l'application de la fonction de hachage HASH sur la clé de classement Ki est réalisée comme suit : le module 101B-1 applique tout d'abord sur les octets de la clé de classement Ki une première fonction de hachage HASH1 qui lui permet d'obtenir un entier. La fonction HASH1 est par 30 exemple la fonction de hachage utilisée dans le projet logiciel Hadoop® développé par la Communauté Apache" et qui utilise l'application MapReduce pour le traitement de données Big Data ; puis le module 101B-1 applique sur l'entier obtenu une seconde fonction de hachage entière HASH2, conduisant à une valeur de hachage Hi. Une telle fonction est connue de l'homme du 35 métier et non décrite ici. On note que la fonction HASH est choisie de sorte à garantir que deux clés égales produisent des valeurs de hachage égales. On s'assure ainsi que deux clés égales sont classées ensemble. 3045857 15 Le module de détermination 101B-2 du premier module de classement 1016 extrait ensuite de la valeur de hachage Hi un nombre prédéterminé m de bits consécutifs (étape E33). Dans l'exemple envisagé ici, les m bits extraits sont les m bits de poids fort de la valeur de hachage Hi. Les m bits extraits sont utilisés par le module de détermination 101B-2 pour 5 déterminer un indice INDi d'une position où insérer le pointeur Ai sur l'élément Ei dans la structure de données informatique S (étape E34). Cet indice INDi est ici donné directement par l'entier constitué des m bits de poids fort extraits. Dans le mode de réalisation décrit ici, le nombre m de bits de poids fort extraits de la valeur de hachage est choisi en fonction d'un pourcentage prédéterminé de l'espace occupé dans 10 la mémoire non volatile 109 pour stocker les éléments de l'ensemble E. Plus précisément, on choisit l'entier m pour que la structure de données informatique S occupe un pourcentage donné (ex. 16%) du volume mémoire M occupé pour stocker les éléments de E dans la mémoire non volatile 109. Si les pointeurs Ai destinés à être stocker dans la structure S occupent par exemple 32 bits, soit 4 octets, le nombre de positions possibles dans la structure S est donné par 2m= 15 (M(octets)/4) x 16%, où M(octets) est le volume mémoire exprimé en octets. Il convient de noter que le nombre m n'est pas nécessairement constant lors de l'exécution du procédé de classement selon l'invention. Il peut varier dynamiquement, par exemple être multiplié ou divisé par deux au cours de cette exécution. Par ailleurs, il peut varier d'un dispositif de classement 101 à un autre. En revanche, la fonction de hachage HASH est la même 20 pour tous les dispositifs de classement 101 amenés à opérer sur des clés de classement identiques. Le module d'insertion 101B-3 du premier module de classement 1016 insère alors l'adresse Ai de l'élément Ei dans la structure de données S dans la liste chaînée L(INDi) se trouvant à la position identifiée par l'indice INDi (étape E35). Dans le mode de réalisation décrit ici, si lors de l'étape d'insertion E35, le module 25 d'insertion 101B-3 détecte qu'une ou plusieurs adresses Aj, avec j*i, ont déjà été insérés dans la liste chaînée L(INDi) se trouvant dans la structure S à la position indexée par l'indice INDi (réponse oui à l'étape test E36), une deuxième étape de classement de ces adresses au sein de la liste chaînée L(INDi) est mise en oeuvre (étape E40). Sinon, le compteur i est incrémenté (étape E31) et l'adresse Ai d'un nouvel élément Ei 30 de l'ensemble E est classée dans la structure S conformément aux étapes E31 à E35 décrites précédemment. La deuxième étape de classement E40 est réalisée par le deuxième module de classement 101C du dispositif de traitement 101. Elle consiste ici à classer entre elles les différentes adresses Aj contenues dans la liste chaînée L(INDi) se trouvant à la position indexée 35 par l'indice INDi de l'adresse Ai (on note J l'ensemble des indices j correspondant aux adresses Aj contenues dans cette liste et qui sont donc associées au même indice de position que l'adresse Ai). 3045857 16 Le module de classement 101C utilise à cet effet un critère de tri basé sur la relation d'ordre 0 prédéfinie à partir des règles suivantes, et appliquée sur les clés des éléments Ej pointés par les adresses Aj, avec j appartenant à J : une clé de classement A est strictement inférieure à une clé de classement B (noté A REVENDICATIONS1. Procédé de classement, par un dispositif informatique dit de classement (101), d'un ensemble (E) d'éléments stockés dans un espace de stockage, chaque élément comprenant une 5 clé de classement (Ki) associée à une valeur de donnée (VALI), ledit procédé de classement comprenant : - une première étape de classement (E30) dans une structure (S) de données informatique de pointeurs vers lesdits éléments stockés dans l'espace de stockage, cette première étape de classement comprenant pour chaque élément : 10 o une étape d'obtention (E32) d'une valeur de hachage en appliquant une fonction de hachage à la dé de classement de l'élément; o une étape de détermination (E33), à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément dans la structure de données informatique ; et 15 o une étape d'insertion (E34) dudit pointeur dans la structure de données informatique à l'indice de position ainsi déterminé ; et - une deuxième étape de classement (E40) comprenant, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, un classement de ces pointeurs entre eux en appliquant une première relation d'ordre prédéfinie aux clés de 20 classement des éléments informatiques vers lesquels pointent ces pointeurs. 2. Procédé de classement selon la revendication 1 dans lequel les m bits consécutifs extraits de la valeur de hachage correspondent aux m bits de poids forts de cette valeur de hachage. 25 3. Procédé de classement selon la revendication 1 ou 2 dans lequel la première relation d'ordre prédéfinie (0) appliquée aux clés de classement vérifie les règles suivantes : - une clé de classement A est strictement inférieure à une clé de classement B si la valeur de hachage de la dé de classement A est strictement inférieure à la valeur de hachage de la clé 30 de classement B ; si les valeurs de hachage de la clé de classement A et de la clé de classement B sont égales, la clé de classement A est strictement inférieure à la clé de classement B si la clé de classement A est strictement inférieure à la clé de classement B conformément à une deuxième relation d'ordre prédéfinie ; 35 - la clé de classement A est égale à la clé de classement B si et seulement si les clés de classement A et B sont égales conformément à la deuxième relation d'ordre. 3045857 21 4. Procédé de classement selon l'une quelconque des revendications 1 à 3 dans lequel l'étape d'application (E32) d'une fonction de hachage à la clé de classement comprend : - l'application d'une première fonction de hachage à la clé de classement résultant en un entier codé sur un nombre prédéterminé n de bits ; puis - l'application d'une seconde fonction de hachage audit entier résultant en la valeur de hachage. 5. Procédé de classement selon l'une quelconque des revendications 1 à 4 comprenant en outre une troisième étape de classement (E60) des éléments dans un fichier informatique (F) en parcourant séquentiellement la structure de données informatique. 6. Procédé de classement selon l'une quelconque des revendications 1 à 5 dans lequel le nombre m dépend de la taille de l'espace de stockage dans lequel sont stockés lesdits éléments. 7. Procédé de classement selon l'une quelconque des revendications 1 à 6 dans lequel 15 le nombre m est modifié dynamiquement au cours du procédé de classement. 8. Procédé de classement selon l'une quelconque des revendications 1 à 7 dans lequel la deuxième étape de classement est mise en oeuvre : - après insertion d'un pointeur dans la structure de données informatique à un indice de position 20 déjà associé à au moins un autre pointeur précédemment inséré ; ou - après avoir inséré dans la structure de données tous les pointeurs vers les éléments stockés dans l'espace de stockage ; ou - périodiquement. 25 9. Programme d'ordinateur comportant des instructions pour l'exécution des étapes du procédé de classement selon l'une quelconque des revendications 1 à 8 lorsque ledit programme est exécuté par un ordinateur. 10. Support d'enregistrement lisible par un ordinateur sur lequel est enregistré un 30 programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé de classement selon l'une quelconque des revendications 1 à 8. 11. Dispositif informatique de classement (101) d'un ensemble d'éléments stockés dans un espace de stockage, chaque élément comprenant une clé de classement associée à une 35 valeur de donnée, ledit dispositif de classement comprenant : - un premier module de classement (101B), configuré pour classer dans une structure de données informatique des pointeurs vers lesdits éléments stockés dans l'espace de stockage, 3045857 22 ce premier module de classement comprenant une pluralité de modules activés pour chaque élément et comprenant : o un module d'obtention (101B-1), configuré pour obtenir une valeur de hachage en appliquant une fonction de hachage à la clé de classement de l'élément; 5 o un module de détermination (101B-2), configuré pour déterminer à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément dans la structure de données informatique ; et o un module d'insertion (101B-3), configuré pour inséré ledit pointeur dans la structure de données informatique à l'indice de position ainsi déterminé ; et 10 - un deuxième module de classement (101C) configuré pour, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, classer ces pointeurs entre eux en appliquant une première relation d'ordre prédéfinie aux clés de classement des éléments informatiques vers lesquels pointent ces pointeurs. 12. Dispositif informatique de classement selon la revendication 11 comprenant en outre un troisième module de classement (101D) configuré pour classer dans un fichier informatique lesdits éléments en parcourant séquentiellement ladite structure de données informatique. 13. Dispositif informatique de traitement (102) d'éléments comprenant chacun une clé de classement et une valeur de donnée, ledit dispositif informatique de traitement comprenant : - un module d'obtention (102A) configuré pour obtenir en provenance d'une pluralité de dispositifs de classement selon la revendication 12, une pluralité de fichiers informatiques comprenant des éléments classés ; - un module de regroupement (102B) configuré pour extraire et regrouper les éléments classés dans chaque fichier informatique comprenant une même clé de classement destinée à être traitée par le dispositif informatique de traitement, en utilisant une fonction de hachage identique à la fonction de hachage et la première relation d'ordre prédéfinie utilisées par chacun des dispositifs de classement. 14. Système informatique (100) comprenant : - une pluralité de dispositifs informatiques de classement (101) selon la revendication 12 aptes à classer des ensembles d'éléments distincts ; et - des dispositifs informatiques de traitement (102) selon la revendication 13 aptes à traiter ces ensembles d'éléments. 3045857 23 15. Système informatique selon la revendication 14 dans lequel les premiers modules de classement d'au moins deux dispositifs informatiques de classement utilisent des nombres m distincts. 5