Je m'intéressait aux techniques de déduplication quand je suis tombé sur cette petite perle.
http://mattmahoney.net/dc/zpaq.html
Un petit outil en ligne de commande qui n'a l'air de rien, écrit par un expert à la retraite dont c'est le passe temps entre deux courses d'ultrarunning…
La déduplication c'est quand on essaye de retrouver des bouts de fichiers communs pour éviter de les stocker à nouveau. zpaq permet de gérer la déduplication au sein de chaque fichier mais également entre les fichiers. Si par exemple un fichier est en double il ne sera stocké qu'une fois. S'il y a été un peu modifié seules les modifications seront stockés.
L'historique est conservé ce qui permet d'extraire la sauvegarde à une date antérieure par exemple. Vu le peu de place que prennent chaque incrément ça permet de conserver une grande plage.
Mes essais sur plusieurs sauvegardes incrémentales (à base de rsync + hard links) que j'ai déjà sont assez bluffants, le gain en place et en temps est énorme.
Le tout avec un outil qui est très simple à l'utilisation et qui a l'air d'avoir fait ses preuves, il a démarré en 2009 et en est à la version 7, toujours maintenu.
Je n'en dis pas plus car je le découvre à peine, étonné de n'en n'avoir jamais entendu parlé avant.
Des inconvénients ? des alternatives ?
# Performances ?
Posté par khivapia . Évalué à 8.
Pour le même sujet, j'avais utilisé lrzip avec backend xz (de Con Kolivas), très pratique pour compresser des projets gérés avec cpold.
Je n'ai pas testé zpaq, mais il a la réputation d'être plus lent. Cela dit, lrzip l'est déjà pas mal sur de grosses archives.
Quelques benchmarks sont disponibles ici http://ck.kolivas.org/apps/lrzip/README.benchmarks
lrzip a l'inconvénient de marcher sur un seul fichier (par exemple une grosse archive tar) et de ne pas fonctionner en pipe (contrairement à gzip, bzip2, xz qui attendent d'avoir un bloc complet pour le compresser indépendamment des blocs précédents). zpaq a l'air prometteur de ce point de vue.
[^] # Re: Performances ?
Posté par vv222 . Évalué à 1.
Petite précision vu que je trouve que ton message ne le laisse pas entendre clairement : lrzip peut utiliser zpaq comme backend.
C’est même comme ça que j’ai découvert zpaq ;)
[^] # Re: Performances ?
Posté par wilk . Évalué à 3.
Vu le gain que je j'ai en terme de volume, jusqu'à diviser par 10 ! Le temps de compression devient insignifiant par rapport au temps de transfert gagné.
# Attic
Posté par Damien Thébault . Évalué à 7.
Comme alternative, j'utilise un peu attic mais j'aurais du mal à dire les différences avec zpaq.
[^] # Re: Attic
Posté par iGor (site web personnel) . Évalué à 5.
Apparement Attic a été prolongé par Borg : https://borgbackup.readthedocs.io
[^] # Re: Attic
Posté par ianux (site web personnel, Mastodon) . Évalué à 2.
Et les deux sont pris en charge par le wrapper atticmatic.
Je cherchais une outils de backup incrémental avec chiffrement pour mettre tout ça dans le nuage et j'ai terminé avec cette solution. J'utilise HubicFuse pour monter le cloud Hubic en espace utilisateur. Borg ne marche pas out of the box avec (il a l'air de bloquer à la création de fichier), donc je sauvegarde et chiffre localement avant de lancer un rsync vers le montage Hubic. Et ça marche pas mal (même si HubicFuse est plutôt lent) !
[^] # Re: Attic
Posté par ghusson (site web personnel) . Évalué à 1.
Peut être que tu peux essayer duplicity dans ton cas ? http://duplicity.nongnu.org/
# Collision
Posté par eingrossfilou . Évalué à 5.
À propos de la déduplication de zpaq, il faut savoir que si deux blocs ont le même hash (SHA1) ils seront considérés comme identiques même en cas de collision (source). Même si c'est très peu probable, l'intégrité des fichiers n'est pas garantie et il n'y a pas d'option pour gérer la collision (pour des raisons de performance, ZFS procède aussi comme ceci quand la déduplication est activée, mais existe un mode de déduplication qui gère les collisions)
Niveau performance, zpaq a beaucoup de marge d'amélioration, en particulier sur le calcul du sha1 (toujours dans le même fil)
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 10. Dernière modification le 02 mai 2016 à 22:39.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Collision
Posté par claudex . Évalué à 3.
J'ai lu en diagonale mais il me semble que ça parle d'erreur correctibles, donc pas d'erreur avec de l'ECC (qui doit être utilisée si tu tiens un poil à tes données).
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 4. Dernière modification le 05 mai 2016 à 11:36.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Collision
Posté par steph1978 . Évalué à 1.
Oui on peut supposer… Ou alors le mettre en hypothèse quand on affirme "Elle l'est autant que sans dé-duplication.". Ce qui aide à comprendre ton premier commentaire.
[^] # Re: Collision
Posté par Kaane . Évalué à 4.
ZFS procède aussi comme ceci quand la déduplication est activée, mais existe un mode de déduplication qui gère les collisions
Oui, enfin sauf que ZFS c'est pas du SHA1 mais du SHA256 par défaut et qu'il y a d'autres indicateurs qui évitent pas mal de collisions même sans verify. Par exemple les deux blocs doivent avoir la même taille (ZFS utilise des blocs de taille variable).
[^] # Re: Collision
Posté par Antoine . Évalué à 1.
Tu es en train de dire que par défaut SHA256 produit pas mal de collisions ?
[^] # Re: Collision
Posté par steph1978 . Évalué à 1.
Tu es en train de dire qu'il y a un SHA256 par défaut et un autre ?
Tout hash produit forcément des collisions puisqu'il réduit l'information. Les algorithmes plus récents tentent de réduire cette probabilité en étant plus malin et surtout en allongeant la taille du hash. Le "pas mal" n'étant pas mesurable,à toi de te faire un idée.
[^] # Re: Collision
Posté par Antoine . Évalué à 1.
Ce n'est pas tant en allongeant la taille du hash qu'ils réduisent cette probabilité, mais en tirant des leçons des algorithmes précédents. Un hash de 160 bits est assez long si l'algorithme est sûr : si SHA1 est en phase de remplacement dans les applications de cryptographie, ce n'est pas parce que le hash est trop court mais parce que l'algo est désormais considéré comme vulnérable.
Il serait idiot de prétendre que SHA256 produit pas mal de collisions si ce n'était pas mesurable. En réalité, si SHA256 est une fonction de hachage cryptographique parfaite, la probabilité de collisions est gouvernée par le paradoxe des anniversaires : elle est dans ce cas ridiculement faible.
C'est pourquoi l'idée d'ajouter des indicateurs pour réduire la probabilité de collisions liée à SHA256 est une affirmation qui, prise au sérieux, sous-entend que SHA256 serait cassé.
PS : à ma connaissance, pas une seule collision de SHA256 n'a été répertoriée pour l'instant…
[^] # Re: Collision
Posté par steph1978 . Évalué à 3.
Tout à fait d'accord.
D'autant qu'il y a une différence entre "casser" qui consiste à provoquer une collision et "rancontrer" une collision qui consiste surtout à "pas de bol".
[^] # Re: Collision
Posté par barmic . Évalué à 4.
J'ajouterais tout de même 2 choses.
Je présume que zfs calcul les checksum sur des blocs soit de taille fixe soit de taille limitée. Si c'est bien le cas, ça réduit encore drastiquement la probabilité de collision (très bêtement tu passe d'une fonction qui projette R dans un entier de 256bits à une fonction qui projette un entier de quelques kbits dans un entier de 256bits). Même sur des fonctions réputées cassées, je ne suis pas sûr qu'on sache le faire…
Si c'est calculé au niveau du fichier, ça peut être intéressant de commencer par comparer la taille. Ça discrimine rapidement.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# Alternatives
Posté par rakoo (site web personnel) . Évalué à 5.
Je suis tombé sur le sujet de la déduplication avec bup, que j'aime beaucoup parce que le code est lisible et la démarche est documentée. Je pense qu'il a plus ou moins engendré les autres qui fonctionnent de la même manière (à savoir content-defined chunking), mais je n'en suis pas sûr à 100%:
[^] # Re: Alternatives
Posté par _dup_ . Évalué à 4.
Je n'ose pas parler d'alternative face aux logiciels qui ont été mentionnés. Il se trouve que je code un logiciel qui fait de la sauvegarde en continu avec de la déduplication globale au fil de l'eau et une empreinte mémoire faible. Pour la déduplication j'utilise SHA256 mais j'ai le même problème que tous les autres logiciels : il n'y a pas de gestion des collisions. Bien évidemment il s'agit d'un logiciel libre (GPL V3 et CC-BY-SA 4 pour les photos - contributions encouragées et bienvenues). Je l'indique ici juste pour info : https://github.com/dupgit/sauvegarde.
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 7.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Alternatives
Posté par steph1978 . Évalué à 2. Dernière modification le 09 mai 2016 à 11:52.
Ou comment s'auto-sourcer…
Mais justement tu ne la trouvera pas si tu n'as pas de gestion de collisions. Tu aura juste un bloc qui prendra la place d'un autre car le système de dédup aura été trompé.
[^] # Re: Alternatives
Posté par Benoît Laurent (site web personnel) . Évalué à 2.
Il y a aussi http://obnam.org/
[^] # Re: Alternatives
Posté par claudex . Évalué à 3.
J'en suis très content mais il est plutôt lent. Cependant, cela devrait s'améliorer cette année avec la sortie du nouveau backend.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Alternatives
Posté par barmic . Évalué à 3.
C'est à dire ?
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: Alternatives
Posté par rakoo (site web personnel) . É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-backup
et 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.[^] # Re: Alternatives
Posté par Anonyme . Évalué à 2. Dernière modification le 03 mai 2016 à 16:20.
Il y a aussi BURP.
Client/serveur de base, TLS intégré dans l’échange, déduplication, rétention paramétrable, basé sur librsync.
[^] # Re: Alternatives
Posté par wilk . Évalué à 3.
J'ai essayé restic qui a l'air plutôt bien parti et dont le développement semble un peu plus "moderne" que zpaq (ce qui n'est pas péjoratif, loin de là). Avec une création d'exécutable multiplateforme grâce au langage Go qui est bien pratique.
Il a l'air bien au fait de ce qui se fait avec un dépôt recensant les alternatives :
https://github.com/restic/others
En fait il y en a une tripotée, je ne me rendais pas compte.
https://camlistore.org/ est prometteur mais en fait peut-être un peu trop ? Je préfère un outil de sauvegarde minimaliste quitte à lui associer d'autres outils.
https://github.com/tsileo/blobsnap est intéressant aussi, il s'appuie sur https://github.com/tsileo/blobstash (du même auteur, Français, cocorico) un stockage clé/valeur avec déduplication
# cpio
Posté par barmic . Évalué à 4.
Il y a des gens qui utilisent cpio ? Je vois très peu de gens s'en servir et je ne comprends pas bien pourquoi.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: cpio
Posté par gnumdk (site web personnel) . Évalué à 3.
[^] # Re: cpio
Posté par barmic . Évalué à 4.
Je parlais du format plus que de l'outil, mais je ne connaissais pas la limite des 8Gio (par contre il gère mieux les liens symboliques que tar je crois).
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: cpio
Posté par myou (site web personnel) . Évalué à 3.
oui cpio est utilisé, mais sans que les utilisateurs le sachent ;o)
Cpio est utilisé dans les paquets RPM et également dans le process initrd.
# rdedup
Posté par wilk . Évalué à 2.
Un nouveau venu en Rust : https://github.com/dpc/rdedup
# remote : rsync + dedup ?
Posté par steph1978 . Évalué à 2.
Est ce qu'il existe une méthode qui tirerait partie de rsync (ou similaire) pour sauvegarder un serveur distant directement dans un format dé-dupliqué ?
Autrement dit, sans avoir à passer par une copie locale (rsync puis bup) ni lire l'ensemble des données par le réseau (RemoteFS + bup) ?
[^] # Re: remote : rsync + dedup ?
Posté par Psychofox (Mastodon) . Évalué à 2. Dernière modification le 10 mai 2016 à 11:29.
Si ton serveur distant utilise ZFS c'est assez facile à coup de snapshots et de la commande zfs send qui permet d'envoyer si on le veut des "deltas" entre deux snapshots.
Sinon on n'appelle pas ça de la déduplication mais ce que tu recherches ne serait-il pas l'équivalent d'un backup incrémental tel que fourni par la plupart des solutions de backups ? En général ça se base sur un "catalogue" et les dates d'accès/modifications des fichiers. C'est fiable tant qu'on ne s'amuse pas à changer ces dates.
Regardes peut-être du côté de Bacula.
[^] # Re: remote : rsync + dedup ?
Posté par steph1978 . Évalué à 1.
Je sais qu'une solution propriétaire comme Networker fait de la déduplication à la source (comme rsync qui envoi les hashs puis les données si la cible n'a pas le contenu du hash) et à la cible (comme bup qui stocke en dédupliqué).
Ce que tu nommes un catalogue - que l'on appellerai plutôt un index car le terme catalogue est plus réserve à l'endroit où l'on (humain ou logiciel de restauration) peut consulter la liste des sauvegarde disponibles à la restauration - n'est pas nécessaire mais peut accélérer l'identification des delta à la source.
Je cherche une solution ouverte qui fasse de même.
Je ne trouve pas de documentation concernant Bacula qui expliquerai qu'il fait de la déduplication, à la source ou à la cible. Alors que bup et rsync sont très explicites là dessus.
[^] # Re: remote : rsync + dedup ?
Posté par Psychofox (Mastodon) . Évalué à 2. Dernière modification le 10 mai 2016 à 15:42.
J'ai effectivement fait un lapsus index/catalogue. Les temps où je gérais une plateforme de backup sont un peu loins.
D'après cette page maintenue par Bacula, il n'y a qu'une dedup "file level" et il n'est pas précisé à quel moment c'est fait. Une dedup block level prévue uniquement dans la version enterprise payante :
http://wiki.bacula.org/doku.php?id=comparisons
[^] # Re: remote : rsync + dedup ?
Posté par Marotte ⛧ . Évalué à 2.
https://linuxfr.org/nodes/108885/comments/1655614
Plus simple que Bacula a mettre en œuvre je trouve.
[^] # Re: remote : rsync + dedup ?
Posté par steph1978 . Évalué à 3.
Ça vient :
Mais ce n'est qu'un ébauche…
[^] # Re: remote : rsync + dedup ?
Posté par Marotte ⛧ . Évalué à 2.
Oui… c’est vrai que Burp 2 est annoncé « pas prêt pour la prod’ » :|
J’avais testé Burp (1 & 2) il y a quelques temps, j’espérais que ça ait évolué dans ce sens…
L’avantage c’est que ça t’oblige à tester la restauration complète quand tu veux passer d’un format à l’autre :) Mais c’est sûr que ça se fait pas comme ça sûr une grosse infra avec un volume de données important.
[^] # Re: remote : rsync + dedup ?
Posté par rakoo (site web personnel) . Évalué à 2.
J'ai pas entièrement compris la question: tu as un serveur distant que tu aimerais backuper sur un autre serveur distant, sans envoyer la totalité des données sur le réseau ?
bup et associés permettent de faire sans en feintant le système: monte le dossier de backup sur la machine à backuper. Seuls les index seront transférés du serveur de stockage vers le serveur à backuper, et dans l'autre sens seuls les blocks complètement nouveaux seront envoyés.
Ou alors j'ai pas tout saisi.
[^] # Re: remote : rsync + dedup ?
Posté par steph1978 . Évalué à 2.
C'est pas bête dans ce sens là. Connecter le serveur/volume de prod sur le serveur de backup est plus souvent pratiqué mais dans l'autre sens, cela répondrait à la minimisation du transfert et du stockage.
Après je préfèrerai une solution avec un agent de backup local car cela évite d'avoir à un moment toutes les données (prod+backup) accessibles sur un même serveur. Ce qui n'est pas très secure et error proof…
[^] # Re: remote : rsync + dedup ?
Posté par rakoo (site web personnel) . Évalué à 2.
Ah oui, tu as raison, je n'avais pas pensé à ça.
Je ne connais pas vraiment les autres solutions donc je ne sais pas si elles pourront t'aider. Pour rester dans ce que je connais et dans les bup et autres restic, une autre solution serait de faire un truc à la rdiff-backup:
Le gros inconvénient c'est que ça demande de la bonne synchronisation pour que les différents processus ne se marchent pas sur les pieds. En plus de ça tu stockeras toutes les données sur la zone de staging en plus du vrai backup dédupliqué. Une solution serait peut-être de faire en sorte que la zone de staging soit en fait un mount FUSE du backup qui pointe vers le dernier backup. Ou, encore plus poussé un server qui fait rsync+ssh+déduplication, qui n'existe pas mais dit comme ça ça a l'air plutôt alléchant.
[^] # Re: remote : rsync + dedup ?
Posté par damaki . Évalué à 0.
Chez moi c'est rsync + dedup btrfs. Les inconvénients de ce setup sont que la déduplication se fait a posteriori et qu'elle est très lente, l'avantage est qu'elle marche parfaitement, sans collision de hash ou quoi que ce soit.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.