Brevet FR2767937A1 — publié le 19990305

La présente invention concerne un procédé de duplication de données réduisant les volumes à transférer. Habituellement, les données sont stockées dans des fichiers, qui représentent l'unité de stockage élémentaire. On s'intéresse ici à des fichiers de taille importante, dont seule une petite portion à la fois change. C'est typiquement le cas des bases de données utilisées dans les systèmes de traitement de l'information, ou le simple fait d'ouvrir puis refermer la base suffit à marquer le fichier comme modifié par le système d'exploitation. n est souvent nécessaire de maintenir à jour des copies de ces fichiers, qui peuvent tre de provenance hétérogène, à des fins de sauvegarde ou de diffusion par exemple. Cependant, si l'on reste au niveau du système d'exploitation, dés qu'un fichier est modifié, il est nécessaire de recopier celuici entièrement, mme si seule une petite portion de celui-ci a changé. ll est important de minimiser le volume des données à transférer, en particulier car les réseaux de transmission ont une bande passante limitée, que leur tarification est souvent au volume, et que le transfert prend du temps et consomme des ressources. Traditionnellement, si l'on veut faire une approche plus fine, il est nécessaire de créer un outil spécifique de l'application qui a crée le fichier, ce qui représente un travail important, non généralisable, et souvent non faisable. De plus, comme cet outil fait appel à des fonctionnalités internes de l'application, il doit tre modifié à chaque nouvelle version de celui-ci. La présente invention décrit un procédé permettant de ne transférer que les parties modifiées d'un fichier, et ce quelque soit la nature du fichier, sans connaître l'application qui l'a généré. Pour cela, on considère le fichier comme formé d'un ensemble de pages. Une page représente une portion du fichier, petite par rapport à sa taille. Les pages peuvent tre de taille fixe ou variable, adaptée ou non à la nature du fichier. Lors de la première recopie, toutes les pages sont recopiées. Ensuite une signature de chaque page est calculée. La signature est caractérisée par le fait que la probabilité que 2 pages différentes possèdent la mme signature est arbitrairement faible, et que la taille de la signature est petite par rapport à la taille de la page. La signature d'une version d'un fichier est donc le vecteur des signatures de toutes les pages. La signature d'une page peut tre calculée par des algorithmes de type CRC (somme de contrôle cyclique), ou exclusif, ou plus évolués au sens cryptologique comme le MD5 par exemple. Le vecteur de signatures peut tre calculé du coté fichier original, et donc stocké en local, ou du coté fichier dupliqué, soit lors de la recopie, soit lors d'une mise à jour. Lors des mises à jour ulténeures, le vecteur de signatures de la version précédente du fichier est récupéré coté original, le vecteur des signatures de la nouvelle version est calculé. Les 2 vecteurs sont comparés, et seules les pages dont les 2 signatures diffèrent sont transmises. Ainsi ne sont transmises que les modifications. La nouvelle version dupliquée est reconstruite à partir de l'ancienne version dupliquée et de la liste des pages modifiées. Dans certaines applications, comme par exemple la sauvegarde ou l'archivage, il n'est pas nécessaire de reconstruire systématiquement la duplication; dans ce cas, seules les pages modifiées sont stockées. I1 est possible de reconstruire à la demande le fichier par exemple en rejouant dans l'ordre dans lequel elles ont été stockées les pages modifiées. A titre d'exemple non limitatif, le procédé peut tre employé dans un système de sauvegarde en réseau pour sauvegarder des tables d'un système de gestion de bases de données (SGBD). La figure 1 montre l'architecture d'un tel système. Un réseau à faible débit E relie un ordinateur C contenant un SGBD dont les données sont stockées sur le disque D, et un ordinateur A relié à un dérouleur de bande B et à un disque local F. Les données sont supposées contenues dans un fichier de 4 Megaoctets inscrit dans D. L'ordinateur A contient le logiciel de sauvegarde en réseau qui communique avec un agent logiciel installé sur C. La figure 2 représente ce fichier avant et après l'enregistrement d'une transaction dans ce fichier par le SGBD. Lors de la première sauvegarde (état 1), l'agent considère ce fichier comme formé de 1000 pages de 4 Kilo-octets. Comme aucun vecteur de signatures n'existe, il envoie à A les 1000 pages, soit 4 Mega-octets qui transitent sur le réseau. A recopie sur bande les 1000 pages, et stocke sur F le vecteur formé de 1000 signatures, la signature étant calculée par l'algorithme CRC32 défini par le CCITT, soit 4 Kilo-octets au total. Puis le SGBD enregistre une transaction qui modifie la page 2. Lors de la sauvegarde suivante, A renvoie à l'agent sur C le vecteur V1. L'agent calcule le nouveau vecteur du fichier dans l'état 2, et constate que seule les signatures de la deuxième page sont différentes. L'agent retourne à A uniquement la deuxième page, qui est stockée sur B, et sa signature sur F. Dans ce cas, seuls 4 Kilo-octets ont transité sur le réseau au lieu de 4000 Kilo-octets. Ce procédé est donc particulièrement adapté pour les opérations de sauvegarde, archivage et duplication de données. REVENDICATIONS Procédé de duplication de données caractérisé par le fait que les données sont découpées en pages de taille petite par rapport à la donnée, que pour chaque page une signature est calculée à partir des données de cette page et que seules les pages dont la signature est différente de la signature de la page de la version précédente de la donnée est transmise et que la donnée dupliquée est reconstituée en modifiant la copie précédente avec les pages transmises. Procédé selon la revendication 1 caractérisé par le fait que les pages sont de taille fixe. Procédé selon la revendication I caractérisé par le fait que les pages sont de taille variable. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que la signature est calculée par un algorithme qui combine les données de la page pour créer une signature de taille inférieure à la page et que la taille de la signature est choisie pour que la probabilité que deux pages possèdent la mme signature soit inférieure à une valeur prédéfmie. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que la signature de la page est calculée par un algorithme cryptologiquement fort. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que le vecteur de signatures d'une version est stocké au mme endroit que les données originales. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que le vecteur de signatures d'une version est stocké au mme endroit que la donnée dupliquée. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que le vecteur de signatures de la version précédente est calculé à la demande à partir de la donnée dupliquée précédente. Procédé selon l'une quelconque des revendications précédentes caractérisé par le fait que la donnée dupliquée n'est pas reconstituée systématiquement, mais uniquement à la demande.