Brevet FR3037677A1 — publié le 20161223

APPAREIL ET PROCÉDÉ DE DÉTECTION D'ENTROPIE EN UNE PASSE SUR LE TRANSFERT DE DONNÉES DOMAINE TECHNIQUE [1] La présente invention se rapporte de manière générale au domaine de la technologie de réduction des données. CONTEXTE DE L'INVENTION [2] Les sous-systèmes de mémoire de la catégorie non-volatile à hautes performances sont généralement constitués de composants relativement coûteux. Il est donc fortement souhaitable de maximiser le stockage des données dans de tels systèmes en employant des techniques de réduction des données. La réduction des données désigne les techniques d'auto-compression des données et de déduplication des données visant à réduire la quantité totale d'informations qui sont écrites vers ou lues depuis un système de stockage principal. La réduction des données a pour résultat la transformation des données (d'entrée) de l'utilisateur en une représentation plus compacte qui peut être stockée. Les avantages de la réduction des données comprennent une utilisation améliorée du stockage, une durée de vie accrue (dans le contexte d'un système de stockage intégralement flash) et l'accélération des applications, parmi d'autres avantages. 1003] La compression des données désigne le processus de recherche de redondance au sein d'un même bloc de données et ensuite de codage de ces séquences répétées de manière à réduire la taille globale des données. La déduplication des données désigne le processus de mise en concordance des séquences de données entre de multiples blocs dans un effort visant à trouver les séquences concordantes, même si le bloc individuel comprend des données incompressibles. Les systèmes conventionnels effectuent cependant la compression 3037677 et la déduplication des données en tant qu'étapes distiictes au sein du processus de réduction des données. En effet, ces systèmes conventionnels ne les combinent pas en une seule étape et paient de ce fait des pénalités de latence et de largeur de bande. 5 [004] De plus, les solutions de réduction des données conventionnelle nécessitent de nombreux cycles et beaucoup de puissance pour exécuter les fonctions de compression. Dans un quelconque flux de données d'une application, il existe toujours une forte probabilité pour qu'un ensemble particulier de blocs de données ne présente pas de propriétés d'auto-compression. À la fin d'une étape de compression, les solutions 10 conventionnelles effectuent généralement un contrôle pour s'assurer que le résultat n'est pas plus grand que le bloc original, ce qui est plutôt tard, puisque les ressources ont déjà été utilisées dans la tentative de compression des données. RÉSUMÉ DE L'INVENTION [5] Par conséquent, il existe un besoin pour une solution qui crée un trajet de données 15 unifié qui effectue à la fois la compression et la déduplication de données en une seule passe. Des modes de réalisation de la présente invention combinent les technologies de compression de données et les étendent en les intégrant avec des procédés de déduplication des données. La nature monopasse des modes de réalisation de la présente invention permet de maîtriser les latences du système et aide à réaliser la compression et la déduplication du 20 débit en ligne à des vitesses plus élevées (par exemple d'une manière qui permet d'atteindre les vitesses PCIe Gen3 pour un FPGA donné, ou d'autres exigences ou normes de vitesse). [6] Les modes de réalisation de la présente invention emploient des sous-ensembles de données plus petits, tels que des blocs de données de 4 kilo-octets, pour la compression et 25 peuvent avoir priorité sur les formats à copie de codage de compression pour différencier 3037677 3 une copie auto-référencée d'une copie d'un bloc de référence. Il convient d'apprécier que les modes de réalisation ne sont pas limités aux blocs de données de 4 kilo-octets et que toute taille de bloc ou plage de tailles de bloc peut être utilisée (par exemple 4 ko, 8 ko, 10 ko, plage de taille de blocs de 4 ko à 8 ko, etc.). Les modes de réalisation peuvent créer 5 des structures de tampon de mémoire qui possèdent de multiples tampons d'entrée en parallèle destinés à conserver les blocs de données de référence. De même, les modes de réalisation peuvent inclure un schéma de consultation de table de hachage parallèle dans lequel les recherches correspondant aux données stockées dans les tampons de blocs de données de référence peuvent être effectuées simultanément aux consultations de hachage 10 effectuées pour les données stockées dans les tampons de données d'entrée. [007] De plus, les modes de réalisation peuvent utiliser le temps de remplissage des tampons de données de référence pour calculer et stocker les valeurs de fonction de hachage découpées en tranches des données de référence à des fins d'amélioration des performances de réduction des données. Les modes de réalisation peuvent également créer un verrouillage 15 mutuel entre les calculs de la table de hachage de référence et le démarrage de la compression. Ainsi, lorsque la compression démarre, les recherches peuvent être effectuées dans la table de hachage de référence, dans une table de hachage de compression, ou dans les deux. Les modes de réalisation de la présente invention peuvent utiliser des heuristiques pour déterminer quelle séquence utiliser (le cas échéant) lorsqu'un accès de hachage est 20 détecté dans une ou plusieurs des tables de hachage. De plus, les modes de réalisation de la présente invention peuvent modifier l'interprétation de la référence antérieure soit pour le flux de données d'entrée, soit du tampon de référence d'entrée. [008] En outre, les modes de réalisation de la présente invention peuvent détecter très 3037677 4 tôt et prévoir la compressibilité des blocs afin de réduire au minimum les efforts inutiles et éviter une baisse des performances générales du système. Les modes de réalisation décrits ici peuvent analyser les caractéristiques de compressibilité caractéristiques en vue de prendre une décision d'exécuter des procédures de réduction des données, comme une 5 compression, sur un bloc de données donné. Des opérations de détection d'entropie à faible impact et hautes performances peuvent ainsi être effectuées d'une manière qui permet à un système de réduction des données à hautes performances d'économiser de la puissance et des cycles d'unité de compression lorsque des données incompressibles lui sont fournies. BRÈVE DESCRIPTION DES DESSINS 10 [009] Les dessins joints, qui sont inclus dans la présente spécification et en font partie, et dans lesquels des numéros identiques désignent des éléments identiques, illustrent des modes de réalisation de la présente invention et, conjointement avec la description, servant à expliquer les principes de l'invention. 15 [0010] La Figure lA est un synoptique représentant un exemple de configuration matérielle d'un système de compression et de déduplication en ligne capable de réaliser des doubles procédures de compression et de déduplication en parallèle à des fins de réduction des données conformément à des modes de réalisation de la présente invention. 20 [0011] La Figure 1B est un synoptique représentant des exemples de composants fournis dans la mémoire pour réaliser des procédures de compression et de déduplication en ligne conformément à des modes de réalisation de la présente invention. 25 [0012] La Figure 1C représente un exemple de format compressé de mise en trames des données généré conformément à des modes de réalisation de la présente invention. 3037677 5 [0013] La Figure 1D représente un exemple de schéma de consultation combinée de table de hachage de référence et de table de hachage de compression conformément à des modes de réalisation de la présente invention. 5 [0014] La Figure 2A est schéma de procédé d'une première portion d'un exemple de processus pour la détection d'entropie en une passe conformément à des modes de réalisation de la présente invention. [0015] La Figure 2B est un schéma de procédé d'une deuxième portion d'un 10 exemple de processus pour la détection d'entropie en une passe conformément à des modes de réalisation de la présente invention. [0016] La Figure 3A est un schéma de procédé d'un exemple de processus de déduplication et de compression simultanées des données conformément à des modes de 15 réalisation de la présente invention. [0017] La Figure 3B est schéma de procédé d'un exemple de processus destiné à effectuer des procédures de consultation de table de hachage conformément à des modes de réalisation de la présente invention. 20 DESCRIPTION DÉTAILLÉE [0018] Il sera à présent fait référence en détail aux modes de réalisation préférés de la présente invention dont des exemples sont illustrés dans les dessins joints. Bien que 25 l'invention sera décrite en association avec les modes de réalisation préférés, il sera compris qu'ils n'ont pas vocation à limiter l'invention à ces modes de réalisation. Au contraire, l'invention est destinée à couvrir les variantes, les modifications et les équivalents qui 3037677 6 peuvent être inclus dans l'esprit et le domaine d'application de l'invention tels qu'ils sont définis par les revendications jointes. [0019] En outre, dans la description détaillée ci-après des modes de réalisation de la 5 présente invention, de nombreux détails spécifiques sont exposés afin de fournir une compréhension approfondie de la présente invention. Une personne possédant des compétences courantes dans l'art reconnaîtra cependant que la présente invention peut être mise en application sans ces détails spécifiques. Dans d'autres cas, des procédés, procédures, composants et circuits bien connus n'ont pas été décrits en détail afin de ne pas 10 masquer inutilement des aspects des modes de réalisation de la présente invention. Bien qu'un procédé puisse être décrit sous la forme d'une séquence d'étapes numérotées à des fins de clarté, la numérotation n'impose pas nécessairement l'ordre des étapes. [0020] Il convient de comprendre que certaines des étapes peuvent être sautées, 15 exécutées en parallèle ou exécutées sans qu'il soit absolument nécessaire de maintenir un ordre strict des séquences. Les dessins qui représentent les modes de réalisation de l'invention sont semi-schématiques et ne sont pas à l'échelle, et certaines dimensions sont notamment indiquées pour des raisons de clarté de la présentation et sont représentées exagérées dans les figures du dessin. De même, bien que les vues dans les dessins 20 représentent généralement des orientations similaires pour faciliter la description, cette représentation dans les Figures est pour la plus grande partie arbitraire. De manière générale, l'invention peut fonctionner dans n'importe quelle orientation. NOTATION ET NOMENCLATURE : 25 [0021] Il convient cependant de garder à l'esprit que tous ces termes ainsi que les termes 3037677 7 similaires sont à associer aux quantités physiques appropriées et sont seulement des étiquettes commodes appliquées à ces quantités. Sauf indication spécifique différente ressortant des discussions ci-après, il est considéré que dans le cadre de la présente invention, les discussions employant des termes tels que « réception » ou « sélection » ou 5 « génération » ou « groupement » ou « surveillance » ou similaire font référence à l'action et aux processus d'un système informatique ou d'un dispositif de calcul électronique similaire qui manipule et transforme des données représentées sous la forme de quantités physiques (par exemple électroniques) à l'intérieur des registres et des mémoires du système informatique et d'autres supports lisibles par ordinateur en d'autres données représentées de 10 manière similaire sous la forme de quantités physiques à l'intérieur des mémoires ou des registres du système informatique ou d'autres dispositifs de stockage, de transmission ou d'affichage d'information similaires. Lorsqu'un composant apparaît dans plusieurs modes de réalisation, l'utilisation du même numéro de référence signifie que le composant est le même composant que celui illustré dans le mode de réalisation original. 15 EXEMPLE DE CONFIGURATION DE SYSTÈME DE COMPRESSION ET DE DÉDUPLICATION EN LIGNE 20 [0022] La Figure lA est un synoptique représentant un exemple de configuration matérielle d'un système de compression et de déduplication en ligne (par exemple le système 100) capable d'effectuer des doubles procédures de compression et de déduplication en parallèle à des fins de réduction des données conformément à des modes de 25 réalisation de la présente invention. De cette manière, le système 100 peut effectuer des procédures de réduction des données en une seule passe de telle sorte que les opérations apparentées aux opérations de réduction des données, comme la compression de données et 3037677 la déduplication des données, sont combinées en un seul processus, un seul chemin de traitement ou une seule étape, réduisant ainsi les pénalités de latence et/ou de largeur de bande générales du système. Bien que des composants spécifiques soient divulgués dans la Figure 1A, il convient d'apprécier que lesdits composants sont indiqués à titre d'exemple. 5 Cela veut dire que les modes de réalisation de la présente invention sont bien adaptés pour avoir différents autres composants matériels ou des variantes des composants mentionnés dans la Figure 1A. Il est apprécié que les composants matériels dans la Figure lA peuvent fonctionner avec des composants autres que ceux présentés et que tous les composants matériels décrits dans la Figure lA ne sont pas nécessaires pour atteindre les objectifs de la 10 présente invention. Conformément à certains modes de réalisation, les composants représentés dans la Figure lA peuvent être combinés pour atteindre les objectifs de la présente invention. [0023] Le système 100 peut être mis en oeuvre sous la forme d'un dispositif électronique 15 capable de communiquer avec d'autres dispositifs électroniques par le biais d'un bus de communications de données. Le bus 106, par exemple, représente un tel bus de communications de données. L'exemple de système 100 sur lequel peuvent être mis en oeuvre des modes de réalisation de la présente invention comprend un environnement de système informatique à usage général. Dans sa configuration la plus simple, le système 100 20 comprend habituellement au moins une unité de traitement 101 et une unité de stockage à mémoire. Le support de stockage lisible par ordinateur 104, par exemple, représente une telle unité de stockage à mémoire. Suivant la configuration exacte et le type de dispositif, le support de stockage lisible par ordinateur 104 peut être volatile (comme une RAM), non-volatile (comme une ROM, une mémoire flash) ou une quelconque combinaison des deux. 3037677 9 Des portions du support de stockage lisible par ordinateur 104, lorsqu'elles sont exécutées, facilitent une exécution efficace des opérations de mémoire ou des requêtes pour des groupes de tâches élémentaires. 5 [0024] Dans un mode de réalisation, le processeur 101 peut être un circuit programmable configuré pour effectuer les opérations de compression et de déduplication en ligne décrites ici. Le processeur 101 peut, par exemple, être un contrôleur de FPGA ou un contrôleur de périphérique à mémoire flash. En variante, dans un mode de réalisation, le processeur 101 peut être utilisé pour exécuter un programme de compression et déduplication en ligne stocké 10 dans le support de stockage lisible par ordinateur 104 et configuré pour effectuer les fonctions décrites ici (voir, par exemple, la Figure 1B décrite plus loin). Le système 100 peut également comprendre un système graphique optionnel 105 pour présenter des informations à l'utilisateur de l'ordinateur, par exemple en affichant des informations sur un périphérique d'affichage optionnel 102. Le système 100 comprend également un périphérique optionnel 15 d'entrée/sortie alphanumérique 103. Le périphérique d'entrée/sortie 103 peut inclure un dispositif optionnel de commande ou de guidage du curseur et une ou plusieurs interfaces de communication de signal, comme une carte d'interface de réseau. De plus, le module d'interface 115 inclut une fonctionnalité pour permettre au système 100 de communiquer avec d'autres systèmes informatiques par le biais d'un réseau de communications 20 électronique (par exemple l'Internet, des réseaux de communication filaires, des réseaux de communication sans fil ou des réseaux similaires). [0025] De plus, le système 100 peut également posséder des caractéristiques et des fonctionnalités supplémentaires. Le système 100 peut, par exemple, également inclure des 25 supports de stockage supplémentaires (amovibles et/ou non amovibles), y compris, mais 3037677 10 sans exhaustivité, des disques magnétiques ou optiques ou des bandes. Les supports de stockage d'ordinateur incluent les supports volatiles et non volatiles, amovibles et non amovibles mis en oeuvre dans tout procédé ou toute technologie de stockage d'informations telles que des instructions lisibles par ordinateur, des structures de données, des modules de 5 programme ou d'autres données. [0026] La Figure 113 est un synoptique représentant des exemples de composants fournis dans la mémoire pour effectuer les procédures de compression et de déduplication en ligne conformément à des modes de réalisation de la présente invention. Bien que des composants spécifiques soient divulgués dans la Figure 1B, il convient d'apprécier que lesdits 10 composants de support de stockage informatique sont indiqués à titre d'exemple. Cela veut dire que les modes de réalisation de la présente invention sont bien adaptés pour avoir différents autres composants matériels ou des variantes des composants de support de stockage informatique mentionnés dans la Figure 1B. Il est apprécié que les composants dans la Figure 1B peuvent fonctionner avec des composants autres que ceux présentés, et 15 que tous les composants de support de stockage informatique décrits dans la Figure 1B ne sont pas nécessaires pour atteindre les objectifs de la présente invention. Conformément à certains modes de réalisation, les composants décrits dans la Figure 1B peuvent être combinés pour atteindre les objectifs de la présente invention. De plus, il est apprécié que certains composants matériels décrits dans la Figure lA peuvent fonctionner en 20 combinaison avec certains composants décrits dans la Figure 1B en vue d'atteindre les objectifs de la présente invention. [0027] Comme représenté dans la Figure 1B, le support de stockage lisible par ordinateur 104 comprend un système d'exploitation 107. Le système d'exploitation 107 se charge dans 3037677 11 le processeur 101 lorsque le système 100 est initialisé. De même, lors de l'exécution par le processeur 101, le système d'exploitation 107 peut être configuré pour fournir une interface de programmation au système 100. Le système 100 peut également inclure des mécanismes de communication sans fil. Au travers de tels périphériques, le système 100 peut être 5 connecté de manière communicative à d'autres systèmes informatiques par le biais d'un réseau de communication tel que l'Internet ou un intranet, comme un réseau local. [0028] De plus, comme illustré dans la Figure 1B, le support de stockage lisible par ordinateur 104 comprend un moteur de calcul informatisé d'empreintes digitales 110. Le 10 moteur de calcul informatisé d'empreintes digitales 110 inclut la fonctionnalité de génération d'empreintes digitales en utilisant une séquence d'octets en vue d'effectuer des procédures d'authentification et/ou de consultation. Sur détection de la réception d'un flux de données, le contrôleur de gestion de tampon 112 peut communiquer des signaux au moteur de calcul informatisé d'empreintes digitales 110 afin de traiter les données stockées 15 dans le tampon d'entrée de données 112-1 lors de leur réception. [0029] Les empreintes digitales générées par le moteur de calcul informatisé d'empreintes digitales 110 peuvent être utilisées pour représenter des fichiers plus grands tout en utilisant une fraction de l'espace de stockage qui serait sinon nécessaire pour le 20 stockage de tels fichiers plus grands. Les fichiers plus grands peuvent inclure, par exemple, des pages de contenu ou des fichiers multimédias. Le moteur de calcul informatisé d'empreintes digitales 110 peut employer des procédures conventionnelles mises en oeuvre sur ordinateur, comme les fonctions de hachage, pour réduire les flux de données en bits de données en vue de générer des empreintes digitales, de sorte qu'elles puissent être traitées 25 par les composants du système 100 comme un moteur de calcul informatisé de signature 3037677 12 113. Les calculs informatisés de hachage peuvent être effectués d'une manière cohérente avec la manière dont les autres composants du système 100 calculent les valeurs de hachage, corme un module de table de hachage 111 ou d'une manière différente. [0030] De cette manière, le moteur de calcul informatisé d'empreintes digitales 110 peut 5 être configuré pour générer des empreintes digitales pour un sous-ensemble de données entrantes associées à un flux de données alors qu'il est reçu par le système 100. Le sous-ensemble de données peut être sous la forme d'incréments de 4 kilo-octets, par exemple. Dans un mode de réalisation, le moteur de calcul informatisé d'empreintes digitales 110 peut calculer les empreintes digitales pour un ensemble entrant de 4 kilo-octets associé à un 10 flux de données reçu par le système 100 et stocké dans le tampon d'entrée de données 112-1 généré par le contrôleur de gestion de tampon 112. [0031] Le moteur de calcul informatisé de signature 113 comprend la fonctionnalité de calcul de signatures pour les flux de données reçus par le système 100. Les signatures 15 peuvent être calculées par le moteur de calcul informatisé de signature 113 en se basant sur divers schémas conventionnels de signature à base de hachage, incluant Merkle, Spooky, CRC, MD5, SHA ou des schémas similaires. Le moteur de calcul informatisé de signature 113 peut être configuré pour effectuer des calculs informatisés de signature en utilisant des calculs informatisés de signature de sous-bloc, des calculs informatisés de détection de 20 similarité basés sur la signature de Rabin et/ou d'autres calculs informatisés de signature basés sur la similarité sur les flux de données reçus par le système 100. Conformément à un mode de réalisation, le moteur de calcul informatisé de signature 113 peut utiliser les données d'empreinte digitale générées par le moteur de calcul informatisé d'empreintes digitales 110 pour générer des signatures. Dans un mode de réalisation, sur réception d'un 3037677 13 flux de données, le contrôleur de gestion de tampon 112 peut être configuré pour communiquer des signaux au moteur de calcul informatisé de signature 113 afin de traiter les données stockées dans le tampon d'entrée de données 112-1 lors de leur réception. [0032] Le moteur de calcul informatisé de signature 113 peut être configuré pour calculer 5 de multiples signatures pour des sous-ensembles de données à la fois pour différentes portions d'un flux de données d'entrée. De cette manière, les signatures calculées par le moteur de calcul informatisé de signature 113 pour les sous-ensembles peuvent être communiquées à d'autres composants du système 100 pour un traitement supplémentaire, comme un module d'identification de bloc de référence 114. Les signatures calculées par le 10 moteur de calcul informatisé de signature 113 peuvent inclure, par exemple, des propriétés mathématiques qui leur permettent d'être similaires ou identiques au cas dans lequel elles sont calculées sur des blocs qui sont similaires ou identiques les uns aux autres. En tant que tel, un bloc de référence sélectionné par les composants du système 100, comme un module d'identification de bloc de référence 114, peut être basé sur une signature calculée qui 15 représente le mieux une pluralité de grappes de signatures similaires stockées dans une mémoire résidente sur le système 100. Par conséquent, les composants du système 100 peuvent effectuer des procédures d'identification de bloc de référence en utilisant les signatures calculées par le moteur de calcul informatisé de signature 113. Le module d'identification de bloc de référence 114 peut utiliser, par exemple, des signatures de sous- 20 bloc pour effectuer les procédures d'identification de bloc de référence. [0033] Le module d'identification de bloc de référence 114 comprend la fonctionnalité d'analyse d'une pluralité de grappes de signatures différentes générées par le moteur de calcul informatisé de signature 113 et de sélection des blocs de référence qui peuvent être 3037677 14 traités par les composants du système 100, comme le module de table de hachage 111. Le module d'identification de bloc de référence 114 peut être configuré pour comparer les signatures calculées aux grappes de signatures actuellement stockées par le système 100 et sélectionner en conséquence un bloc de référence qui représente le mieux la signature 5 calculée. Le module d'identification de bloc de référence 114 peut être configuré, par exemple, pour comparer les signatures calculées aux grappes de signatures actuellement stockées dans un tampon généré par le contrôleur de gestion de tampon 112 et sélectionner en conséquence un bloc de référence qui représente le mieux la signature calculée. 10 [0034] Les blocs de référence sélectionnés par le module d'identification de bloc de référence 114 peuvent être stockés à l'intérieur des tampons générés par le contrôleur de gestion de tampon 112, comme un tampon de blocs de référence 112-3, pour un traitement supplémentaire par les composants du système 100. Les blocs de référence peuvent être des blocs de données normaux qui ont été constatés similaires aux données d'entrées par divers 15 procédés. Les blocs de référence peuvent, par exemple, être des blocs de données normaux qui ont été constatés similaires aux données d'entrées en utilisant des signatures de sous-bloc calculées, des mécanismes de détection de similitude, des schémas de détection d'indice d'application ou des schémas similaires. Les blocs de référence peuvent également être des blocs purement synthétiques contenant des séquences de données répétées qui ont 20 été constatées présenter des facteurs de répétition plus élevés. Conformément à un mode de réalisation, le module d'identification de bloc de référence 114 peut être configuré pour identifier les blocs de référence en utilisant la connaissance apriori, la concordance de similarité de contenu, les indices d'application, la reconnaissance de modèle de données ou des moyens similaires. 3037677 15 [0035] De plus, les informations concernant les blocs de référence, comme un bloc de référence stocké à l'intérieur du tampon de blocs de référence 112-3 identifié par le module d'identification de bloc de référence 114, peuvent être stockées dans la portion d'en-tête 5 d'un flux de données. En se référant à la Figure 1C, par exemple, l'identifiant de bloc de référence pour un bloc de référence identifié par le module d'identification de bloc de référence 114 peut être stocké dans la portion d'en-tête 116a du flux de données 116. Comme illustré dans la Figure 1C, les données d'en-tête 116a peuvent être incluses au sein d'un ensemble de grains de données, comme les grains de données 116-1, 116-2 et 116-N, 10 conjointement avec leurs portions de données de charge utile compressées respectives, comme la charge utile compressée 116b. Dans un mode de réalisation, les données d'en-tête 116a peuvent stocker un identifiant de référence 117-1 en plus du vecteur binaire 117-2, du nombre de grains 117-3 et/ou des données de CRC d'en-tête 117-4. 15 [0036] En se référant à la Figure 1B, le module de table de hachage 111 inclut la fonctionnalité de calcul de valeurs de hachage et de génération dynamique de tables de hachage en se basant sur les données associées aux flux de données reçus par le système 100. Sur réception d'un flux de données, le contrôleur de gestion de tampon 112 peut communiquer des signaux au module de table de hachage 111 afin de traiter les données 20 stockées dans le tampon d'entrée de données 112-1 et/ou le tampon de blocs de référence 112-3 à chaque réception de données par le tampon. Le module de table de hachage 111 inclut la fonctionnalité de calcul des valeurs de hachage pour des sous-ensembles de données, tels que des octets de données, associés à un flux de données reçu par le système 100 qui peut être stocké au sein d'une table de hachage générée. Le module de table de 25 hachage 111 peut, par exemple calculer les valeurs de hachage pour les octets de données 3037677 16 associés à un flux de données reçu par le système 100. En tant que tel, le module de table de hachage 111 peut être utilisé par les schémas de compression à hautes performances les plus courants d'une manière qui accélère la recherche de séquences de données répétées. Le module de table de hachage 111 peut être utilisé, par exemple, par les schémas de 5 compression à hautes performances les plus courants dont les schémas de compression Snappy, Lempel-Ziv (LZ), Gzip ou des schémas similaires. [0037] Les sous-ensembles de données peuvent avoir une taille fixe prédéterminée et peuvent être utilisés pour représenter des fichiers plus grands en vue d'effectuer des 10 procédures de déduplication. Le module de table de hachage 111 peut ainsi calculer une valeur de hachage pour chaque octet de données reçu par le système 100. De cette manière, le module de table de hachage 111 peut calculer les valeurs de hachage pour les sous-ensembles de données simultanément avec leur réception et leur stockage au sein d'un tampon généré par le contrôleur de gestion de tampon 112. De plus, les calculs informatisés 15 de hachage peuvent être effectués d'une manière cohérente avec la manière dont d'autres composants du système 100 calculent les valeurs de hachage, comme le moteur de calcul informatisé d'empreintes digitales 110 ou d'une manière différente. [0038] Conformément à un mode de réalisation, le module de table de hachage 111 inclut 20 la fonctionnalité de génération dynamique de la table de hachage de références en se basant sur les blocs de référence de données identifiés par le module d'identification de bloc de référence 130. Une fois sélectionnés par le module d'identification de bloc de référence 114, les blocs de données correspondant aux blocs de référence peuvent être stockés avec eux dans un tampon de blocs de référence, comme le tampon de blocs de référence 112-3. À 25 mesure que les blocs de référence sont stockés, le module de table de hachage 111 peut être 3037677 17 configuré pour calculer les valeurs de hachage découpées en tranches qui correspondent aux blocs de référence. Ainsi, le module de table de hachage 111 peut générer des tables de hachage pré-calculées qui peuvent accélérer les performances des procédures de compression et de déduplication effectuées par le système 100. 5 [0039] En se référant à la Figure 1B, par exemple, lorsqu'un ensemble d'octets est reçu par le système 100 et stocké dans le tampon d'entrée de données 112-1 résident sur le système 100, le module de table de hachage 111 peut calculer les valeurs de hachage pour les blocs de référence déterminés et/ou sélectionnés par le module d'identification de bloc 10 de référence 114 comme correspondant à l'ensemble d'octets reçu. Le module de table de hachage 111 calcule ces valeurs de hachage à mesure que les blocs de référence de données sont stockés dans le tampon de blocs de données de référence 112-3, lequel a été généré dynamiquement par le contrôleur de gestion de tampon 112. De cette manière, le contrôleur de gestion de tampon 112 inclut la fonctionnalité de création de tampons de blocs de 15 données de référence qui peut être parallèle à la fonctionnalité des tampons d'entrée de données résidents sur le système 100, comme le tampon d'entrée de données 112-1. Sous cette forme, ces valeurs de hachage de bloc de référence calculées peuvent ensuite être stockées dans la table de hachage de référence 111-1 générée par le module de table de hachage 111. 20 [0040] Le module de table de hachage 111 inclut la fonctionnalité de génération dynamique de tables de hachage de compression en utilisant un flux de données reçu par le système 100 et/ou stocké dans les tampons d'entrée de données. De plus, le module de table de hachage 111 inclut la fonctionnalité de modification et/ou de génération de données 25 codées qui peuvent être utilisées pour décompresser et/ou reconstruire ensuite les flux de 3037677 18 données traités précédemment par le système 100. De cette manière, le module de table de hachage 111 peut être configuré pour modifier et/ou coder les données d'en-tête lors de l'identification de séquences de données similaires pendant les opérations de compression. Le module de table de hachage 111 peut ainsi générer des données codées contenant un 5 identifiant de références qui correspond aux données stockées identifiées précédemment par le module de table de hachage 111. [0041] Le module de table de hachage 111 peut, par exemple, générer et/ou modifier des données d'en-tête codées qui contiennent le nombre d'octets de données non compressées 10 identifiés par le module de table de hachage 111, comme le nombre de constantes figuratives identifiées, à l'achèvement des procédures de calcul informatisé du hachage. De cette manière, les données codées générées par le module de table de hachage 111 peuvent fournir des instructions concernant la manière dont le module de décompression peut décompresser ou décoder une constante figurative et/ou copier des éléments qui 15 correspondent à un ensemble d'octets associés à un flux de données soumis à des procédures de décompression. Les éléments copiés peuvent inclure les octets à copier (« longueur ») et/ou jusqu'à quel point en arrière se trouvent les données à copier (« décalage »). [0042] Dans un mode de réalisation, par exemple, les données d'en-tête générées et/ou 20 modifiées par le module de table de hachage 111 peuvent inclure une représentation des constantes figuratives identifiées et une séquence de données de constante figurative correspondante. En tant que tel, le module de décompression 108 peut lire les informations d'en-tête codées et/ou modifiées qui fournissent des instructions sur la manière dont le module peut décompresser la séquence de constantes figuratives. De plus, le module de 25 décompression 108 peut être configuré pour effectuer les procédures de décompression en 3037677 19 se basant sur divers schémas de compression comme les schémas de compression Snappy, LZ, Gzip ou des schémas similaires. 10043] Conformément à un mode de réalisation, sous réserve qu'au moins un bloc de référence est sélectionné et désigné pour être stocké dans un tampon de blocs de référence, 5 le module de table de hachage 111 peut envoyer des signaux aux composants du système 100 pour effectuer la consultation de la table de hachage et/ou les procédures de modification de l'en-tête en utilisant la table de hachage de référence et/ou la table de hachage de compression pour un traitement supplémentaire en se basant sur les valeurs de hachage calculées. De cette manière, le module de table de hachage 111 peut créer un 10 verrouillage mutuel entre les calculs informatisés de la table de hachage de référence et le démarrage des procédures de décompression. De plus, les procédures de calcul informatisé du hachage effectuées par le module de table de hachage 111 pour la table de hachage de compression et la table de hachage de référence peuvent être les mêmes procédures ou fonctions mises en oeuvre par ordinateur ou des procédures ou fonctions mises en oeuvre par 15 ordinateur différentes. [0044] Le Tableau I contient un exemple d'ensemble de formats d'en-tête ou de modifications du format de codage avec référence antérieure capables d'être, modifiées par des modes de réalisation de la présente invention. En-tête compressé Signification 00 Constante figurative, longueur max. 60 octets 01 Copie locale, longueur 3 bits, décalage 11 bits 10 Copie locale, longueur 6 bits, décalage 12 bits 11 Copie de référence, longueur 12 bits, décalage 12 bits 20 Tableau I 3037677 20 [0045] Le moteur de balayage et de concordance 109 inclut la fonctionnalité de réalisation des procédures de consultation de la table de hachage de réalisation de comparaisons de valeurs de hachage. Le moteur de balayage et de concordance 109 inclut la 5 fonctionnalité d'émission et/ou de réception de signaux de la part du module de table de hachage 111 en vue d'effectuer des procédures de consultation mises en oeuvre par ordinateur pour comparer les valeurs de hachage calculées pour les sous-ensembles de données aux blocs de référence de données actuellement stockés par le système 100. 10 [0046] Le moteur de balayage et de concordance 109 peut utiliser la logique de consultation de table de hachage pour localiser les valeurs de hachage calculées à l'intérieur des tables de hachage générées par le module de table de hachage 111 et comparer les données. Le module de table de hachage 111 peut, par exemple, générer la table de hachage de référence 111-1 et la table de hachage de compression 111-2 et effectuer des opérations 15 de comparaison. En tant que tel, le moteur de balayage et de concordance 109 peut être configure pour consulter les valeurs de hachage calculées à la recherche d'un sous-ensemble d'octets par rapport aux blocs de référence de données actuellement stockés par le système 100 dans les tampons générées par le contrôleur de gestion de tampon 112, comme le tampon de blocs de référence 112-3. 20 [0047] De cette manière, le moteur de balayage et de concordance 109 peut mener des recherches en parallèle ou simultanées à la fois dans une table de hachage de référence et une table de hachage de compression créée par le module de table de hachage 111. Lorsqu'il effectue de telles procédures de consultation, le moteur de balayage et de concordance 109 peut également effectuer des procédures de comparaison d'un ensemble suivant d'octets 25 reçus par le système 100 au bloc de données de référence stocké et/ou aux valeurs de 3037677 21 hachage de compression qui correspondent aux données identifiées précédemment par le module de table de hachage 111. [0048] En se référant à la Figure 1D, par exemple, lorsque le bloc de référence 118 est 5 identifié par le module d'identification de bloc de référence 114, le module de table de hachage 111 stocke dans la table de hachage de référence 111-1 une valeur de hachage calculée qui correspond à des portions du bloc de référence 118 (par exemple les valeurs des sous-ensembles de données du bloc de référence 118-1, 118-2, 118-3, 118-4, etc.) telle qu'elle est stockée dans un tampon de blocs de référence. De cette manière, le système 100 10 peut utiliser le temps de remplissage du tampon de données de référence pour calculer et stocker les valeurs de la fonction de hachage découpées en tranches des données de référence correspondant au bloc de référence 118, ce qui améliore les performances des procédures de compression et de déduplication effectuées par le système 100. 15 [0049] De plus, comme illustré dans la Figure 1D, le système 100 peut également recevoir des blocs de données d'entrée 120 associés à un flux de données entrant. En tant que tel, le moteur de balayage et de concordance 109 peut utiliser la logique de table de hachage 109-3 pour effectuer des procédures de consultation parallèles en utilisant la table de hachage de référence 111-1 et la table de hachage de compression 111-2 renseignées 20 pour identifier les séquences de données stockées précédemment qui sont similaires aux blocs de données 120 reçus. De cette manière, le moteur de balayage et de concordance 109 peut effectuer des comparaisons octet par octet en utilisant des sous-ensembles plus petits (par exemple le sous-ensemble de données 120-1 du bloc de données) de données et de blocs de référence. 25 [0050] Si le moteur de balayage et de concordance 109 détecte une concordance entre 3037677 22 une entrée dans la table de hachage de référence 111 et/ou la table de hachage de compression 111-2 et la valeur de hachage calculée pour le bloc de données 120, le moteur de balayage et de concordance 109 peut alors envoyer en conséquence des signaux au module de décompression 108 pour décompresser le sous-ensemble de données au sein du 5 tampon de blocs de référence ou du tampon d'entrée de données en utilisant des formats d'en-tête de compression modifiés, comme les modifications du format de codage avec référence antérieure décrit ici. Par conséquent, la sortie décompressée peut ensuite être stockée dans un tampon généré par le contrôleur de gestion de tampon 112, comme le tampon de sortie de données 112-2. 10 [0051] Dans un mode de réalisation, pendant les réalisations des procédures de décompression, le module de décompression 108 peut être configuré pour sélectionner une parmi une pluralité de séquences différentes lorsque le moteur de balayage et de concordance 109 détecte une concordance dans la table de hachage de référence 111-1 et/ou 15 dans la table de hachage de compression 111-2. En se basant sur une heuristique prédéterminée, par exemple, le module de décompression 108 peut être configuré pour décompresser les données sous la forme de constantes figuratives, de copies locales et/ou de copies de référence. De cette manière, à la décompression, le système 100 peut créer des tampons d'entrée de données de référence similaires de sorte que la mise en oeuvre d'une 20 décompression peut être modifiée pour interpréter les références antérieures provenant soit d'un flux de données d'entrée, soit d'un tampon de blocs de référence. [0052] En tant que tel, le module de décompression 108 peut être configuré pour traiter la logique de balayage de constante figurative 109-1 et/ou la logique de balayage de copie 25 locale 109-2 utilisées par le moteur de balayage et de concordance 109. Il convient 3037677 23 d'apprécier que les modes de réalisation de la présente invention ne sont pas limités à l'utilisation d'un bloc de référence unique. Les modes de réalisation peuvent être étendus pour inclure de multiples blocs de référence avec des modifications simples aux trajets de données et structures de trame existants. Les modes de réalisation peuvent, par exemple, être 5 étendus à des comparaisons de multiples blocs de référence effectuées en parallèle. De plus, le module de table de hachage 111 peut être configuré pour générer de multiples tables de hachage de références qui correspondent à un bloc de référence respectif d'un ensemble de blocs de référence différents. En outre, de multiples blocs de référence peuvent être stockés à l'intérieur d'une table de hachage de référence unique générée par le module de table de 10 hachage 111. [0053] De plus, le système 100 peut être configuré pour une détection précoce et une prévision de la compressibilité des blocs avant d'effectuer une opération de réduction des données telle que celle décrite ici afin de réduire au minimum les efforts inutiles et éviter 15 une baisse des performances globales du système. Le module de décompression 108 inclut, par exemple, la fonctionnalité de réalisation de procédures de groupement sur les données reçues par le système 100. En tant que tel, le module de décompression 108 peut inclure une logique de groupement de données 108-1 qui permet au module de décompression 108 de grouper les données entrantes, reçues par le biais du tampon d'entrée de données 112-1, en 20 sous-ensembles d'octets de données ou « tranches » qui peuvent être traités ou opérés en une seule instance. Ainsi, le module de table de hachage 111 peut calculer des valeurs de hachage sur des tranches de données superposées sélectionnées par le module de décompression 108 par le biais de la logique de groupement de données 108-1. De plus, les valeurs de hachage calculées par le module de table de hachage 111 pour les tranches 3037677 24 superposées peuvent être utilisées comme emplacements d'adresse mémoire qui représentent les endroits où sont stockées les valeurs de décalage de tranche au sein des structures de données, comme la table de hachage de compression 111-2 et/ou la mémoire résidente sur le système 100. 5 [0054] De plus, le moteur de balayage et de concordance 109 peut utiliser le module de table de hachage 111 pour localiser les tranches calculées et, en parallèle, effectuer des opérations de comparaison sur les blocs de données à mesure qu'ils sont écrits dans le tampon d'entrée de données 112-1. En utilisant la table de hachage de compression 111-2, 10 par exemple, le moteur de balayage et de concordance 109 peut détecter l'apparition d'un « accès de hachage » s'il détermine qu'une valeur de hachage calculée pour une tranche en rapport avec un ensemble de données entrant partage la même signature qu'une valeur de hachage stockée dans la table de hachage de compression 111-2. De cette manière, le moteur de balayage et de concordance 109 peut détecter l'apparition d'un accès de hachage 15 lorsque deux tranches possèdent des signatures identiques ou similaires calculées par le moteur de calcul informatisé de signature 113. [0055] De plus, le moteur de balayage et de concordance 109 inclut la fonctionnalité d'émission de signaux vers le module de décompression 108 pour incrémenter un compteur 20 de compressibilité, comme le compteur d'accès de hachage 111-3. De cette manière, le compteur d'accès de hachage 111-3 peut être incrémenté à chaque fois que le moteur de balayage et de concordance 109 détecte l'apparition d'un accès de hachage. Le compteur d'accès de hachage 111-3 permet au système 100 de garder une trace des valeurs de hachage qui apparaissent fréquemment au sein d'un ensemble de données entrant reçu par le système 25 100. Par conséquent, à la fin d'un transfert de données dans le tampon d'entrée de données 3037677 25 112-1, le système 100 peut stocker un ensemble de hachages calculés pour un ensemble de données complet. [0056] De plus, le système 100 peut être configuré pour stocker des seuils de 5 concordance de valeur de hachage fréquente, ce qui lui permet de mieux déterminer quels blocs de données tireraient le plus d'avantages à être soumis à des procédures de réduction des données (par exemple procédures de déduplication des données, procédures d'identification de bloc de référence, procédures de compression de données, etc.). De cette manière, le système 100 peut être configuré d'une manière qui lui permet d'interpréter 10 automatiquement les caractéristiques de compressibilité en utilisant des valeurs de seuil prédéterminées et/ou des comptages de compressibilité calculés. À titre d'exemple, avant que le système 100 n'effectue une quelconque procédure de réduction des données, il peut tout d'abord se référer à un comptage de seuil prédéterminé et décider s'il faut effectuer, arrêter et/ou suspendre une opération de réduction des données. 15 [0057] Ainsi, les composants du système 100 comme le module de décompression 108 peuvent générer une instruction ou un ensemble d'instructions qui commandent aux composants du système 100 d'initialiser l'exécution d'une opération de réduction des données (par exemple des procédures de déduplication des données, des procédures 20 d'identification de bloc de référence, des procédures compression de données, etc.) lorsque le compteur de seuil atteint ou dépasse un seuil de concordance de valeur de hachage fréquente. Par conséquent, les composants du système 100 peuvent générer une instruction ou un ensemble d'instructions qui commandent aux composants du système 100 de s'abstenir d'exécuter une opération de réduction des données lorsque le comptage de 25 seuil échoue à atteindre un seuil de concordance de valeur de hachage fréquente. De telles 3037677 26 déterminations par le système 100 permettent non seulement d'économiser des cycles de l'UC hôte, mais permettent également aux données de se déplacer à travers le système sans interrompre d'autres gestionnaires, comme les gestionnaires de l'hôte. 5 [0058] Dans un mode de réalisation, par exemple, si la valeur du compteur d'accès de hachage 111-3 est inférieure à une valeur de seuil prédéterminée, le module de décompression 108 peut déterminer que les blocs de données actuellement analysés présentent de faibles caractéristiques de compressibilité, démontrant ainsi un niveau d'entropie élevé pour au moins une portion du flux de données. Par conséquent, en réponse 10 à cette détermination, le module de décompression 108 peut être configuré pour ne pas exécuter une quelconque opération de décompression. De cette manière, le module de décompression 108 peut être configuré pour envoyer des instructions qui arrêtent et/ou suspendent l'exécution des opérations de décompression. 15 [0059] Toutefois, si la valeur du compteur d'accès de hachage 111-3 est égale ou supérieure à la valeur de seuil prédéterminée, le module de décompression 108 peut déterminer que les blocs de données présentent des caractéristiques de compressibilité élevée, démontrant ainsi un faible niveau d'entropie pour au moins une portion du flux de données. Par conséquent, en réponse à cette détermination, le module de décompression 108 20 peut être configuré pour envoyer des instructions qui initialisent l'exécution d'une opération de décompression. De cette manière, le module de décompression 108 utilise les facteurs de compressibilité pour déterminer s'il faut délivrer des signaux de « compression » ou de « contournement de la compression » aux autres composants du système 100 pour un ensemble donné d'octets en rapport avec un ensemble de données entrant stocké dans le 25 tampon d'entrée de données 112-1. 3037677 27 [0060] De cette manière, le système 100 peut mesurer l'entropie en rapport avec les ensembles de données stockés dans le tampon d'entrée de données 112-1 en se basant sur la fréquence des similarités détectées entre les blocs de données d'un ensemble de données 5 donné. Conformément à un mode de réalisation, le moteur de balayage et de concordance 109 peut calculer la fréquence des accès de hachage en utilisant des représentations des données sous forme d'histogramme. De plus, le compteur d'accès de hachage 111-3 peut être mis en oeuvre par matériel ou logiciel. 10 [0061] En outre, le système 100 peut également être configuré pour ajuster dynamiquement les valeurs de seuil en se basant sur la charge du système et/ou les préférences de l'utilisateur. De cette manière, le seuil pour la compression peut être assoupli en vue d'augmenter le taux de compression au détriment de la puissance et de la latence. De même, des valeurs de seuil plus élevées peuvent être utilisées pour obtenir des latences 15 moyennes plus faibles. [0062] La Figure 2A est un schéma de procédé d'une première portion d'un exemple de processus de détection d'entropie en une passe conformément à des modes de réalisation de la présente invention. 20 [0063] À l'étape 205, un flux de données d'entrée est reçu par le système et stocké dans un tampon d'entrée de données. Sur réception du flux de données, le module de décompression utilise la logique de groupement de données pour grouper une pluralité de sous-ensembles de données trouvés à l'intérieur du flux de données d'entrée. La taille des 25 sous-ensembles peut être prédéterminée et avoir une valeur fixe. [0064] À l'étape 206, en utilisant les données d'empreinte digitale générées par le moteur 3037677 28 de calcul informatisé d'empreintes digitales pour les données stockées dans le tampon d'entrée de données, le moteur de calcul informatisé de signature calcule une première signature pour un premier sous-ensemble groupé de données à l'intérieur du flux de données tel qu'il est stocké pendant l'étape 205. 5 [0065] À l'étape 207, le module de table de hachage calcule une première valeur de hachage pour le premier sous-ensemble groupé de données et compare la valeur de hachage calculée à une valeur de hachage stockée dans la table de hachage afin de détecter une concordance. 10 [0066] À l'étape 208, le module de table de hachage calcule une deuxième valeur de hachage pour un deuxième sous-ensemble de données groupé et compare la valeur de hachage calculée à une valeur de hachage stockée dans une table de hachage afin de détecter une concordance. 15 [0067] À l'étape 209, le module de table de hachage calcule une n" valeur de hachage pour un n' sous-ensemble de données groupé et compare la valeur de hachage calculée à une valeur de hachage stockée dans une table de hachage afin de détecter une concordance. [0068] À l'étape 210, le module de décompression surveille les concordances détectées 20 par le module de table de hachage et incrémente en conséquence un compteur pour chaque concordance détectée. [0069] La Figure 2B est un schéma de procédé d'une deuxième portion d'un exemple de processus de détection d'entropie en une passe conformément à des modes de réalisation de 25 la présente invention. Les détails de l'opération 210 (voir la Figure 2A) sont décrits dans la Figure 2B. 3037677 29 [0070] À l'étape 211, le module de décompression détermine un niveau d'entropie pour une portion du flux de données d'entrée en se basant sur une valeur du compteur par rapport à un seuil de concordance de valeur de hachage fréquente prédéterminé. 5 [0071] À l'étape 212, le module de décompression détermine s'il détecte que le seuil de concordance de valeur de hachage fréquente a été atteint ou dépassé. Si le module de décompression détecte que le seuil de concordance de valeur de hachage fréquente a été atteint ou dépassé, le module de décompression détermine un niveau d'entropie élevé pour 10 une portion du flux de données d'entrée et communique par conséquent des signaux aux composants du système pour initialiser l'exécution des opérations de réduction des données, comme décrit en détail à l'étape 213. Si le module de décompression détecte que le seuil de concordance de valeur de hachage fréquente n'a pas été atteint, le module de décompression détermine un faible niveau d'entropie pour une portion du flux de données d'entrée et 15 communique par conséquent des signaux aux composants du système pour arrêter l'exécution des opérations de réduction des données, comme décrit en détail à l'étape 214. [0072] À l'étape 213, le module de décompression détecte que le seuil de concordance de valeur de hachage fréquente a été atteint ou dépassé et, par conséquent, le module de 20 décompression détermine un niveau d'entropie élevé pour une portion du flux de données d'entrée et communique par conséquent des signaux aux composants du système pour initialiser l'exécution des opérations de réduction des données. [0073] À l'étape 214, le module de décompression détecte que le seuil de concordance de 25 valeur de hachage fréquente n'a pas été atteint et, par conséquent, le module de décompression détermine un faible niveau d'entropie pour une portion du flux de données 3037677 d'entrée et communique par conséquent des signaux aux composants du système pour arrêter l'exécution des opérations de réduction des données. [0074] La Figure 3A est un schéma de procédé d'un exemple de processus de 5 déduplication et de compression simultanées des données conformément à des modes de réalisation de la présente invention. Les détails de l'opération 213 (voir la Figure 2B) sont décrits dans la Figure 3A. [0075] À l'étape 215, le module d'identification de bloc de référence compare une signature calculée pendant l'étape 206 aux grappes de signatures actuellement stockées par 10 le système et sélectionner en conséquence un bloc de référence qui représente le mieux la signature calculée. Le bloc de référence sélectionné par le module d'identification de bloc de référence est stocké dans le tampon de blocs de référence pour un traitement supplémentaire par le système. 15 [0076] À l'étape 216, à mesure que le bloc de référence est stocké à l'étape 215, le module de table de hachage calcule les valeurs de hachage découpées en tranches correspondant au bloc de référence. [0077] À l'étape 217, les valeurs de hachage calculées pendant l'étape 216 sont stockées 20 dans une table de hachage de référence générée par le module de table de hachage, sous réserve que les valeurs de hachage ne sont pas déjà stockées dans la table de hachage de référence. [0078] À l'étape 218, sous réserve qu'au moins un bloc de référence est stocké dans le 25 tampon de blocs de référence, le module de table de hachage envoie des signaux au moteur de balayage et de concordance pour effectuer des procédures de consultation de la table de 3037677 31 hachage et/ou de modification de l'en-tête en utilisant la table de hachage de référence et/ou la table de hachage de compression pour un traitement supplémentaire en se basant sur la valeur de hachage calculée pendant les étapes 207, 208 et/ou 209. 5 [0079] La Figure 3B est un schéma de procédé d'un exemple de processus pour effectuer les procédures de consultation de table de hachage conformément à des modes de réalisation de la présente invention. Les détails de l'opération 218 (voir la Figure 3A) sont décrits dans la Figure 3B. 10 [0080] À l'étape 219, le moteur de balayage et de concordance détermine s'il a ou non détecté une concordance entre une valeur de hachage calculée et une entrée stockée exclusivement dans la table de hachage de référence. Si le moteur de balayage et de concordance détermine qu'une concordance a été détectée, le moteur de balayage et de concordance compare alors octet par octet le sous-ensemble de données associé à la valeur 15 de hachage au bloc de référence stocké dans le tampon de blocs de référence associé à l'entrée concordante, comme décrit en détail à l'étape 220. Si le moteur de balayage et de concordance détermine qu'aucune concordance n'a été détectée, le moteur de balayage et de concordance détermine alors s'il a ou non détecté une concordance entre une valeur de hachage calculée et une entrée stockée exclusivement dans la table de hachage de 20 compression, comme décrit en détail à l'étape 221. [0081] À l'étape 220, le moteur de balayage et de concordance a déterminé qu'une concordance a été détectée et, par conséquent, le moteur de balayage et de concordance compare, octet par octet, le sous-ensemble de données associé à la valeur de hachage au bloc 25 de référence stocké dans le tampon de blocs de référence associé à l'entrée concordante et envoie en conséquence des signaux au module de décompression afin de décompresser le 3037677 32 sous-ensemble de données au sein du tampon de blocs de référence en utilisant un format d'en-tête de compression modifié pour les copies de référence, tel que « 11 ». La sortie décompressée est stockée dans le tampon de données de sortie. [0082] À l'étape 221, le moteur de balayage et de concordance a déterminé qu'aucune 5 concordance n'a été détectée et, par conséquent, le moteur de balayage et de concordance détermine s'il a ou non détecté une concordance entre une valeur de hachage calculée et une entrée stockée exclusivement dans la table de hachage de compression. Si te moteur de balayage et de concordance détermine qu'une concordance a été détectée, le moteur de balayage et de concordance compare alors, octet par octet, le sous-ensemble de données 10 associé à la valeur de hachage aux données actuellement stockées dans le tampon d'entrée de données, comme décrit en détail à l'étape 222. Si le moteur de balayage et de concordance détermine qu'aucune concordance n'a été détectée, le moteur de balayage et de concordance détermine alors s'il a ou non détecté une concordance entre une valeur de hachage calculée et une entrée stockée à la fois dans la table de hachage de référence et la 15 table de hachage de compression, comme décrit en détail à l'étape 223. [0083] À l'étape 222, le moteur de balayage et de concordance a déterminé qu'une concordance a été détectée et, par conséquent, le moteur de balayage et de concordance compare, octet par octet, le sous-ensemble de données associé à la valeur de hachage aux 20 données actuellement stockées dans le tampon d'entrée de données et envoie en conséquence des signaux au module de décompression afin de décompresser le sous-ensemble de données au sein du tampon d'entrée de données en utilisant un format d'en-tête de compression modifié pour les copies locales, tel que « 01 » ou « 10 », en se basant sur la longueur binaire correcte et le décalage. La sortie décompressée est stockée dans le tampon 3037677 33 de sortie de données. [0084] À l'étape 223, le moteur de balayage et de concordance a déterminé qu'aucune concordance n'a été détectée et, par conséquent, le moteur de balayage et de concordance détermine s'il a ou non détecté une concordance entre une valeur de hachage calculée et une 5 entrée stockée à la fois dans la table de hachage de référence et la table de hachage de compression. Si le moteur de balayage et de concordance détermine qu'une concordance a été détectée, le moteur de balayage et de concordance compare alors, octet par octet, le sous-ensemble de données associé à la valeur de hachage aux données actuellement stockées dans le tampon d'entrée de données et envoie en conséquence des signaux au module de 10 décompression pour décompresser le sous-ensemble de données au sein du tampon d'entrée de données en se basant sur les procédures prédéterminées. [0085] À l'étape 224, le moteur de balayage et de concordance a déterminé qu'une concordance a été détectée et, par conséquent, le moteur de balayage et de concordance 15 compare, octet par octet, le sous-ensemble de données associé à la valeur de hachage aux données actuellement stockées dans le tampon d'entrée de données et envoie en conséquence des signaux au module de décompression pour décompresser le sous-ensemble de données au sein du tampon d'entrée de données en se basant sur des procédures prédéterminées. Conformément à un mode de réalisation, les procédures prédéterminées 20 peuvent inclure la configuration du moteur de balayage et de concordance afin de polariser sa sélection des procédures de décompression vers des concordances locales ou des concordances de référence, suivant la longueur de la copie et/ou certaines autres connaissances des données associées au flux de données. [0086] À l'étape 225, le moteur de balayage et de concordance a déterminé qu'aucune 3037677 34 concordance n'a été détectée et, par conséquent, la valeur de hachage calculée est stockée dans la table de hachage de compression générée par le module de table de hachage. [0087] À l'étape 226, le moteur de balayage et de concordance communique des signaux 5 au module de décompression pour décompresser le sous-ensemble de données stocké dans le tampon d'entrée de données en utilisant un format d'en-tête de compression modifié pour les séquences de constantes figuratives, comme « 00 ». La sortie décompressée est stockée dans le tampon de sortie de données. 10 [0088] Bien que certaines modes de réalisation et procédés préférés aient été divulgués ici, il apparaîtra de la divulgation précédente aux personnes compétentes dans l'art que des variantes et des modifications de tels modes de réalisation et procédés peuvent être réalisées sans s'écarter de l'esprit et du domaine d'application de l'invention. 15 [0089] Selon un mode de réalisation, les techniques décrites ici peuvent être mises en oeuvre par un ou plusieurs dispositifs de traitement informatique à usage spécifique. Les dispositifs de traitement informatique à usage spécifique peuvent être en câblage physique pour exécuter les techniques, ou peuvent inclure des dispositifs électroniques numériques tels qu'un ou plusieurs circuits intégrés à application spécifique (ASIC) ou réseaux logiques 20 prédiffusés programmables (FPGA) qui sont programmés à demeure pour exécuter les techniques, ou peuvent inclure un ou plusieurs processeurs physiques à usage général programmés pour exécuter les techniques conformément à des instructions de programme dans un microprogramme, une mémoire, un autre stockage ou une combinaison. De tels dispositifs de traitement informatique à usage spécifique peuvent également combiner une 3037677 logique en câblage physique personnalisée, des ASIC ou des FPGA avec une programmation personnalisée pour accomplir les techniques. Les dispositifs de traitement informatique à usage spécifique peuvent être des serveurs de base de données, des dispositifs de stockage, des systèmes informatiques de bureau, des systèmes informatiques 5 portables, des périphériques portatifs, des périphériques de mise en réseau ou tout autre dispositif qui incorpore une logique en câblage physique et/ou programmable pour mettre en oeuvre les techniques. [0090] Dans la description détaillée précédente de modes de réalisation de la présente 10 invention, de nombreux détails spécifiques ont été présentés en vue de fournir une compréhension approfondie de la présente invention. Une personne possédant des compétences courantes dans l'art reconnaîtra cependant que la présente invention peut être mise en application sans ces détails spécifiques. Dans d'autres circonstances, des procédés, procédures, composants et circuits bien connus n'ont pas été décrits en détail afin de ne pas 15 masquer inutilement des aspects des modes de réalisation de la présente invention. Bien qu'un procédé puisse être décrit sous la forme d'une séquence d'étapes numérotées pour des raisons de clarté, la numérotation n'impose pas nécessairement l'ordre des étapes. Il convient de comprendre que certaines étapes peuvent être sautées, exécutées en parallèle ou exécutées sans qu'il soit absolument nécessaire de maintenir un ordre strict des séquences. 20 Les dessins qui représentent les modes de réalisation de l'invention sont semi-schématiques et ne sont pas à l'échelle, et certaines dimensions sont notamment indiquées pour des raisons de clarté de la présentation et sont représentées exagérées dans les figures du dessin. De même, bien que les vues dans les dessins représentent généralement des orientations 3037677 36 similaires pour faciliter la description, cette représentation dans les Figures est pour la plus grande partie arbitraire. REVENDICATIONS1. Appareil comprenant : une unité de mémoire configurée pour stocker un flux de données ; et un processeur connecté à ladite unité de mémoire, ledit processeur étant configuré pour détecter l'entropie d'un flux de données d'entrée pendant une seule passe, ledit processeur pouvant être utilisé pour grouper une pluralité de sous-ensembles de données issues dudit flux de données d'entrée pour calculer une première valeur de hachage correspondant à un premier sous- ensemble groupé de données, pour détecter une concordance entre ladite première valeur de hachage et une deuxième valeur de hachage stockée dans une table de hachage, pour surveiller une fréquence de concordance de valeur de hachage dudit flux de données d'entrée, ledit processeur pouvant être utilisé pour incrémenter une valeur de compteur en réaction à une détection de ladite concordance et pour déterminer un niveau d'entropie pour une portion dudit flux de données d'entrée en se basant sur ladite valeur de compteur par rapport à un seuil de concordance de valeur de hachage fréquente, et pour générer une instruction destinée soit à initialiser l'exécution d'une opération de compression de données lorsque ladite valeur de compteur atteint ou dépasse ledit seuil de concordance de valeur de hachage fréquente, soit à s'abstenir de ladite exécution de ladite opération de compression de données lorsque ladite valeur de compteur ne réussit pas à atteindre ledit seuil de concordance de valeur de hachage fréquente. 2. Appareil selon la revendication 1, dans lequel ladite instruction d'initialiser ladite exécution de ladite opération de compression de données résulte en une sortie comprenant une portion compressée dudit flux de données d'entrée. 3037677 38 3. Appareil selon la revendication 1, dans lequel ladite instruction de s'abstenir de ladite exécution de ladite opération de compression de données résulte en une sortie comprenant une 5 portion non compressée dudit flux de données d'entrée. 4. Appareil selon la revendication 1, dans lequel ledit processeur peut être utilisé pour générer une instruction de suspendre l'exécution de ladite opération de compression de données lorsque ladite valeur de compteur ne réussit pas à atteindre ledit seuil de concordance de valeur 10 de hachage fréquente. 5. Appareil selon la revendication 1, dans lequel ledit processeur peut être utilisé pour calculer une signature pour chaque sous-ensemble de données de ladite pluralité de sous-ensembles de données, et ladite concordance représente au moins deux sous-ensembles groupés 15 de données en rapport avec ledit flux de données d'entrée ayant une même signature. 6. Appareil selon la revendication 1, dans lequel ledit processeur peut être utilisé pour ajuster ledit seuil de concordance de valeur de hachage fréquente en se basant sur une charge actuelle du système. 20 7. Appareil selon la revendication 1, dans lequel ledit processeur peut être utilisé pour ajuster ledit seuil de concordance de valeur de hachage fréquente en se basant sur la préférence d'un utilisateur. 8. Procédé mis en oeuvre par ordinateur pour détecter l'entropie d'un flux de données 25 d'entrée pendant une seule passe, ledit procédé comprenant : réception d'un flux de données d'entrée ; groupement d'une pluralité de sous-ensembles de données issues dudit flux de 3037677 39 données d'entrée ; calcul d'une première valeur de hachage correspondant à un premier sous-ensemble groupé de données ; détection d'une concordance entre ladite première valeur de hachage et une deuxième 5 valeur de hachage stockée dans une table de hachage et incrémentation d'une valeur de compteur en réaction à la détection de ladite concordance ; surveillance d'une fréquence de concordance de valeur de hachage dudit flux de données d'entrée ; détermination d'un niveau d'entropie pour une portion dudit flux de données d'entrée 10 en se basant sur ladite valeur de compteur par rapport à un seuil de concordance de valeur de hachage fréquente ; et génération d'une instruction destinée soit à initialiser l'exécution d'une opération de compression de données lorsque ladite valeur de compteur atteint ou dépasse ledit seuil de concordance de valeur de hachage fréquente, soit à s'abstenir de ladite exécution de ladite 15 opération de compression de données lorsque ladite valeur de compteur ne réussit pas à atteindre ledit seuil de concordance de valeur de hachage fréquente. 9. Procédé mis en oeuvre par ordinateur selon la revendication 8, dans lequel ladite instruction d'initialiser ladite exécution de ladite opération de compression de données résulte en une sortie comprenant une portion compressée dudit flux de données d'entrée. 20 10. Procédé mis en oeuvre par ordinateur selon la revendication 9, dans lequel ladite instruction de s'abstenir de ladite exécution de ladite opération de compression de données résulte en une sortie comprenant une portion non compressée dudit flux de données d'entrée. 25 11. Procédé mis en oeuvre par ordinateur selon la revendication 8, dans lequel ladite 3037677 40 génération comprend en outre la génération d'une instruction de suspendre l'exécution de ladite opération de compression de données lorsque ladite valeur de compteur ne réussit pas à atteindre ledit seuil de concordance de valeur de hachage fréquente. 5 12. Procédé mis en oeuvre par ordinateur selon la revendication 8; dans lequel ledit groupement comprend en outre le calcul d'une signature pour chaque sous-ensemble de données de ladite pluralité de sous-ensembles de données, et ladite concordance représente au moins deux sous-ensembles groupés de données en rapport avec ledit flux de données d'entrée ayant une même signature. 10 13. Procédé mis en oeuvre par ordinateur selon la revendication 8, comprenant en outre : ajustement dudit seuil de concordance de valeur de hachage fréquente en se basant sur une charge actuelle du système. 15 14. Procédé mis en oeuvre par ordinateur selon la revendication 8, comprenant en outre : ajustement dudit seuil de concordance de valeur de hachage fréquente en se basant sur la préférence d'un utilisateur. 20 15. Appareil comprenant : une unité de mémoire configurée pour stocker un flux de données ; et un processeur connecté à ladite unité de mémoire, ledit processeur étant configuré 25 pour détecter l'entropie d'un flux de données d'entrée pendant une seule passe, ledit processeur pouvant être utilisé pour calculer une signature pour chaque sous-ensemble de données d'une pluralité de sous-ensembles de données issues dudit flux de données d'entrée pour calculer une première valeur de hachage correspondant à un premier sous-ensemble groupé de données, pour détecter une concordance entre ladite première valeur de hachage et une deuxième valeur de 3037677 41 hachage stockée dans une table de hachage, pour surveiller une fréquence de concordance de valeur de hachage dudit flux de données d'entrée, ledit processeur pouvant être utilisé pour incrémenter une valeur de compteur en réaction à une détection de ladite concordance et pour déterminer un niveau d'entropie pour une 5 portion dudit flux de données d'entrée en se basant sur ladite valeur de compteur par rapport à un seuil de concordance de valeur de hachage fréquente, et pour générer une instruction destinée soit à initialiser l'exécution d'une opération de réduction de données lorsque ladite valeur de compteur atteint ou dépasse ledit seuil de concordance de valeur de hachage fréquente, soit à s'abstenir de ladite exécution de ladite opération de réduction de données lorsque ladite valeur de 10 compteur ne réussit pas à atteindre ledit seuil de concordance de valeur de hachage fréquente. 16. Appareil selon la revendication 15, dans lequel ladite instruction d'initialiser ladite exécution de ladite opération de réduction de données résulte en une sortie comprenant une portion compressée dudit flux de données d'entrée. 15 17. Appareil selon la revendication 15, dans lequel ladite instruction de s'abstenir de ladite exécution de ladite opération de réduction de données résulte en une sortie comprenant une portion non compressée dudit flux de données d'entrée. 18. Appareil selon la revendication 15, dans lequel ladite opération de réduction des 20 données est une opération de déduplication des données. 19. Appareil selon la revendication 15, dans lequel ladite opération de réduction des données est une opération de compression des données. 20. Appareil selon la revendication 15, dans lequel ledit processeur peut être utilisé pour 25 ajuster ledit seuil de concordance de valeur de hachage fréquente en se basant sur une charge 3037677 42 actuelle du système. 21. Appareil selon la revendication 15, dans lequel ledit processeur peut être utilisé pour ajuster ledit seuil de concordance de valeur de hachage fréquente en se basant sur la préférence 5 d'un utilisateur.