Le mieux reste encore d'aller voire la page DESIGN de bup que j'ai pointée plus haut. Pour faire simple, l’idée est la suivante:
Rolling checksum
Deja tu prends un algorithme qui te permet de calculer des rolling checksum; c'est une checksum qui permet de calculer efficacement une somme de contrôle a partir de n'importe quel offset du fichier. Imagine une fenêtre de calcul qui donne la valeur de l'octet N a l'octet M. Tu veux calculer la somme de l'octet N+1 a l'octet M+1, c'est a dire décaler la fenêtre d'un octet vers la droite. Avec une somme de contrôle "standard", il faudra tout recalculer octet par octet. Avec une rolling checksum pour calculer cette nouvelle valeur tout ce dont tu as besoin c'est:
la valeur precedente, c'est-a-dire de l'octet N a l'octet M
l'octet que tu rajoute, a M+1
l'octet que tu enlèves, a N
En pratique, il y a adler32, créée par Mark Adler (le créateur de rsync, qui a mis au point cette checksum justement pour rsync vu son fonctionnement particulier) et Rabin-Karp, du même nom que l'algorithme de recherche de string dans une string (justement parce que l'algorithme a besoin d'une rolling checksum)
Trouver une limite aux chunks
Une fois que tu as une rolling checksum, tu peux calculer la somme de contrôle "a chaque octet", c'est a dire que tu calcules de 0 a W, de 1 a W+1, etc...
A chaque somme tu appliques une petite heuristique, du style "est-ce que les 13 premiers bits sont a 1". Une telle heuristique a une probabilité de 1 / 213; dit autrement, la réponse devrait être oui si tu calcules cette somme 213 = 8192, c'est-a-dire que après avoir avancé de 8192 octets tu devrais avoir un oui. Comme c'est juste une probabilité, en pratique tu te retrouves avec des valeurs différentes, mais en gros tous les ~8kio tu es capable de définir une limite; a partir de la, un bloc est l'ensemble des octets entre deux limites (qui devrait donc avoir une taille moyenne de 8kio, donc).
La ou il faut bien faire la différence, c'est que la rolling checksum est calcule sur une petite fenêtre, typiquement 128 octets. Si tu as trouve une limite, on dira qu'elle correspond au dernier octet de la fenêtre. Par contre tu peux être certain que la limite précédente est en-dehors de la fenêtre. Voici un schéma fait a l'arrache, dans lequel les octets sont alignes, tu vois la limite precedente, la fenêtre ou la valeur est calculée, et comme la rolling checksum matche la condition, on met une limite a la fin de la fenêtre.
Et voila, tu peux calculer une somme de contrôle forte (type SHA-1, SHA-256) sur chaque bloc, qui lui donnera une identité, et ne le stocker qu'une seule et unique fois; si le même bloc se retrouve dans un autre fichier ou dans une version ultérieure du même fichier (qui n'est qu'un cas particulier d'un autre fichier, après tout), il existera déjà, pas besoin de le stocker une 2nde fois.
(note: la valeur exacte de la première somme de contrôle ne sert a rien; tout ce qu'on regarde c'est si elle passe le test des x premiers bits)
Pourquoi c'est top
Dit comme ça on ne voit pas vraiment l'avantage par rapport a, par exemple, du chunking statique tous les X octets. La ou ça fait la différence c'est si tu modifies le fichier, par exemple en plein milieu. En refaisant passer la moulinette, bien entendu le début suivra exactement la même procédure, et tu te retrouveras avec les même blocs. Par contre a l'endroit ou il y a eu une modification le contenu a change, donc la rolling checksum va changer, et la limite se retrouvera a un autre endroit. Le truc c'est que après la modification le contenu n'a pas changé, donc la rolling checksum donnera la même valeur qu'avant, et ce jusqu’à la fin du fichier. Du coup tu te retrouves avec les mêmes blocs avant et après la modification, et seule la modification crée de nouveaux blocs, le tout sans même avoir besoin de faire un traitement spécial. La grosse différence par rapport a un diff classique c'est que les deux versions sont totalement indépendantes; tu peux tout a fait supprimer les blocs uniques a une version donnée sans pour autant affecter les autres versions, a la différence des rdiff-backup et autre duplicity, ou tu as une longe chaine de backups "incrémentaux" qui se suivent tous les uns les autres depuis un backup "full". Dans les backups qui utilisent du content-defined chunking, il n'y a plus de "full" et d’"incrémentaux", tous les backups sont considérés comme full et c'est le stockage derrière qui fait de la magie.
[^] # Re: Alternatives
Posté par rakoo (site web personnel) . En réponse au journal zpaq : backup incrémental avec déduplication. Évalué à 6.
Le mieux reste encore d'aller voire la page DESIGN de bup que j'ai pointée plus haut. Pour faire simple, l’idée est la suivante:
Rolling checksum
Deja tu prends un algorithme qui te permet de calculer des rolling checksum; c'est une checksum qui permet de calculer efficacement une somme de contrôle a partir de n'importe quel offset du fichier. Imagine une fenêtre de calcul qui donne la valeur de l'octet N a l'octet M. Tu veux calculer la somme de l'octet N+1 a l'octet M+1, c'est a dire décaler la fenêtre d'un octet vers la droite. Avec une somme de contrôle "standard", il faudra tout recalculer octet par octet. Avec une rolling checksum pour calculer cette nouvelle valeur tout ce dont tu as besoin c'est:
En pratique, il y a adler32, créée par Mark Adler (le créateur de rsync, qui a mis au point cette checksum justement pour rsync vu son fonctionnement particulier) et Rabin-Karp, du même nom que l'algorithme de recherche de string dans une string (justement parce que l'algorithme a besoin d'une rolling checksum)
Trouver une limite aux chunks
Une fois que tu as une rolling checksum, tu peux calculer la somme de contrôle "a chaque octet", c'est a dire que tu calcules de 0 a W, de 1 a W+1, etc...
A chaque somme tu appliques une petite heuristique, du style "est-ce que les 13 premiers bits sont a 1". Une telle heuristique a une probabilité de 1 / 213; dit autrement, la réponse devrait être oui si tu calcules cette somme 213 = 8192, c'est-a-dire que après avoir avancé de 8192 octets tu devrais avoir un oui. Comme c'est juste une probabilité, en pratique tu te retrouves avec des valeurs différentes, mais en gros tous les ~8kio tu es capable de définir une limite; a partir de la, un bloc est l'ensemble des octets entre deux limites (qui devrait donc avoir une taille moyenne de 8kio, donc).
La ou il faut bien faire la différence, c'est que la rolling checksum est calcule sur une petite fenêtre, typiquement 128 octets. Si tu as trouve une limite, on dira qu'elle correspond au dernier octet de la fenêtre. Par contre tu peux être certain que la limite précédente est en-dehors de la fenêtre. Voici un schéma fait a l'arrache, dans lequel les octets sont alignes, tu vois la limite precedente, la fenêtre ou la valeur est calculée, et comme la rolling checksum matche la condition, on met une limite a la fin de la fenêtre.
Et voila, tu peux calculer une somme de contrôle forte (type SHA-1, SHA-256) sur chaque bloc, qui lui donnera une identité, et ne le stocker qu'une seule et unique fois; si le même bloc se retrouve dans un autre fichier ou dans une version ultérieure du même fichier (qui n'est qu'un cas particulier d'un autre fichier, après tout), il existera déjà, pas besoin de le stocker une 2nde fois.
(note: la valeur exacte de la première somme de contrôle ne sert a rien; tout ce qu'on regarde c'est si elle passe le test des x premiers bits)
Pourquoi c'est top
Dit comme ça on ne voit pas vraiment l'avantage par rapport a, par exemple, du chunking statique tous les X octets. La ou ça fait la différence c'est si tu modifies le fichier, par exemple en plein milieu. En refaisant passer la moulinette, bien entendu le début suivra exactement la même procédure, et tu te retrouveras avec les même blocs. Par contre a l'endroit ou il y a eu une modification le contenu a change, donc la rolling checksum va changer, et la limite se retrouvera a un autre endroit. Le truc c'est que après la modification le contenu n'a pas changé, donc la rolling checksum donnera la même valeur qu'avant, et ce jusqu’à la fin du fichier. Du coup tu te retrouves avec les mêmes blocs avant et après la modification, et seule la modification crée de nouveaux blocs, le tout sans même avoir besoin de faire un traitement spécial. La grosse différence par rapport a un diff classique c'est que les deux versions sont totalement indépendantes; tu peux tout a fait supprimer les blocs uniques a une version donnée sans pour autant affecter les autres versions, a la différence des
rdiff-backupet autreduplicity, ou tu as une longe chaine de backups "incrémentaux" qui se suivent tous les uns les autres depuis un backup "full". Dans les backups qui utilisent du content-defined chunking, il n'y a plus de "full" et d’"incrémentaux", tous les backups sont considérés comme full et c'est le stockage derrière qui fait de la magie.