Journal zpaq : backup incrémental avec déduplication

Posté par  . Licence CC By‑SA.
45
2
mai
2016

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  . É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  . É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  . É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  . Évalué à 7.

    Comme alternative, j'utilise un peu attic mais j'aurais du mal à dire les différences avec zpaq.

  • # Collision

    Posté par  . É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  . É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  . É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  . É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  . Évalué à 1.

            On peut donc supposer que ces systèmes n'ont pas d'ECC

            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  . É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  . Évalué à 1.

        mais du SHA256 par défaut et qu'il y a d'autres indicateurs qui évitent pas mal de collisions

        Tu es en train de dire que par défaut SHA256 produit pas mal de collisions ?

        • [^] # Re: Collision

          Posté par  . Évalué à 1.

          Tu es en train de dire que par défaut SHA256 […]

          Tu es en train de dire qu'il y a un SHA256 par défaut et un autre ?

          SHA256 produit pas mal de collisions

          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  . Évalué à 1.

            Les algorithmes plus récents tentent de réduire cette probabilité en étant plus malin et surtout en allongeant la taille du hash.

            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.

            Le "pas mal" n'étant pas mesurable

            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  . Évalué à 3.

              la probabilité de collisions est gouvernée par le paradoxe des anniversaires : elle est dans ce cas ridiculement faible.

              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  . É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  (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%:

    • ddar, qui n'a pas l'air d'avoir beaucoup bougé mais qui a priori marche. L'auteur a choisi d'utiliser SQLite pour stocker les métadonnées, ce qui peut s'avérer intéressant pour le futur (supprimer des blocs est par exemple
    • attic, déja mentionné
    • restic, encore une autre implémentation des mêmes idées
    • zbackup, qui contient quelques liens vers la fin
    • [^] # Re: Alternatives

      Posté par  . É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  . Évalué à 7.

        Ce commentaire a été supprimé par l’équipe de modération.

        • [^] # Re: Alternatives

          Posté par  . Évalué à 2. Dernière modification le 09 mai 2016 à 11:52.

          Comme déjà mentionné

          Ou comment s'auto-sourcer…

          si tu trouves une collision dans une hash crypto

          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  (site web personnel) . Évalué à 2.

      Il y a aussi http://obnam.org/

      • [^] # Re: Alternatives

        Posté par  . É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  . Évalué à 3.

      à savoir content-defined chunking

      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  (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:

        • 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.

        ____________________________________________________________________________________________________
                      |                                                   [     ]|
        ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
                    limite                                               fenêtre  limite
        

        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  . É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  . É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  . É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  (site web personnel) . Évalué à 3.

      L'utilitaire cpio a été standardisé par la norme POSIX.1-1988. Il a été abandonné par des versions ultérieures de la norme à partir de POSIX.1-2001, en raison de sa limitation aux fichiers de 8 GB. L'outil standard POSIX pax peut être utilisé pour lire et écrire des archives cpio.

      • [^] # Re: cpio

        Posté par  . É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  (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  . Évalué à 2.

    Un nouveau venu en Rust : https://github.com/dpc/rdedup

  • # remote : rsync + dedup ?

    Posté par  . É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  (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  . É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  (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  . É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  . Évalué à 3.

        Ça vient :

        Q. Are you going to do inline data deduplication?
        A. Yes, in burp 2.

        Mais ce n'est qu'un ébauche

        Do not expect Burp 2, and the backups that it makes, to be compatible with future releases of Burp 2.

        • [^] # Re: remote : rsync + dedup ?

          Posté par  . É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…

          Do not expect Burp 2, and the backups that it makes, to be compatible with future releases of Burp 2.

          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  (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  . É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  (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 serveur de backup garde une zone "staging" avec la hiérarchie à backuper
          • Le serveur de prod rsync ses données vers la zone de staging, ne transférant ainsi qu'une partie des données
          • Le serveur de backup déduplique via bup, de son côté, une fois que le transfert est fini

          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  . É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.