L’algorithme de diff binary git (stockage delta) est-il normalisé?

Je pense que l’algorithme diff utilisé pour les fichiers pack était lié à l’un des encodages delta disponibles : Initialement (2005) xdelta , puis libXDiff .
Mais alors, comme détaillé ci-dessous, il est passé à une implémentation personnalisée.

En tout cas, comme mentionné ici :

Git effectue la deltification uniquement dans les fichiers packfiles.
Mais lorsque vous passez par SSH, git génère un fichier pack avec des commits de l’autre côté, et ces packs sont des packs minces, donc ils ont aussi des deltas … mais le côté distant ajoute alors des bases à ces packs minces les rendant autonome.

(Remarque: la création de nombreux fichiers de package ou la récupération d’informations dans un énorme fichier de pack est coûteuse , et explique pourquoi git ne gère pas bien les fichiers volumineux ou les référentiels volumineux.
Voir plus sur ” git with large files “)

Ce fil nous rappelle également:

En fait, les fichiers de paquetage et la deltification ( LibXDiff, pas xdelta ) étaient, d’après mes souvenirs, à l’ origine de la bande passante réseau (beaucoup plus coûteuse que l’espace disque) et des performances d’E / S d’objects en vrac.

LibXDiff est mentionné dans cette discussion de 2008 .

Cependant, depuis lors, l’algo a évolué, probablement dans un diff-delta.c personnalisé, comme l’ illustre ce thread de 2011 , et comme l’ diff-delta.c tête de diff-delta.c :

Donc, à proprement parler, le code actuel de Git ne ressemble en rien au code libxdiff.
Cependant, l’algorithme de base derrière les deux implémentations est le même .
L’étude de la version de libxdiff est probablement plus facile pour comprendre comment cela fonctionne.

 /* * diff-delta.c: generate a delta between two buffers * * This code was greatly inspired by parts of LibXDiff from Davide Libenzi * http://www.xmailserver.org/xdiff-lib.html * * Rewritten for GIT by Nicolas Pitre , (C) 2005-2007 */ 

Plus sur les packfiles du Git Book :

Git 2.18 ajoute à la description du delta dans cette nouvelle section de documentation , qui maintenant (T2 2018) indique:

Types d’object

Les types d’object valides sont les suivants:

• OBJ_COMMIT (1)
• OBJ_TREE (2)
• OBJ_BLOB (3)
• OBJ_TAG (4)
• OBJ_OFS_DELTA (6)
• OBJ_REF_DELTA (7)

Le type 5 est réservé à une future expansion. Le type 0 n’est pas valide.

Représentation Deltified

Conceptuellement, il n’y a que quatre types d’objects: commit, tree, tag et blob.
Cependant, pour économiser de l’espace, un object pourrait être stocké en tant que “delta” d’un autre object “base”.
Ces représentations se voient atsortingbuer de nouveaux types de delta et de ref-delta, qui ne sont valides que dans un fichier pack.

Les deux ofs-delta et ref-delta stockent le “delta” à appliquer à un autre object (appelé “object de base”) pour reconstruire l’object.
La différence entre eux est,

• ref-delta code directement le nom d’object de base de 20 octets.
  • Si l’object de base se trouve dans le même pack, ofs-delta code à la place le décalage de l’object de base dans le pack.

L’object de base pourrait également être défini s’il se trouve dans le même pack.
Ref-delta peut également faire référence à un object en dehors du pack (c’est-à-dire le soi-disant “pack léger”) . Lorsqu’il est stocké sur le disque, le pack doit être autonome pour éviter toute dépendance cyclique.

Les données delta sont une séquence d’instructions permettant de reconstruire un object à partir de l’object de base.
Si l’object de base est délimité, il doit d’abord être converti en forme canonique. Chaque instruction ajoute de plus en plus de données à l’object cible jusqu’à ce qu’il soit complet.
Il existe deux instructions sockets en charge jusqu’à présent:

• un pour copier une plage d’octets à partir de l’object source et
• un pour insérer de nouvelles données incorporées dans l’instruction même.

Chaque instruction a une longueur variable. Le type d’instruction est déterminé par le septième bit du premier octet. Les schémas suivants suivent la convention de la RFC 1951 (format des données compressées à déflater).

Le codage Git delta est basé sur copie / insertion.

Cela signifie que le fichier dérivé est codé comme une suite de codes d’opération pouvant représenter des instructions de copie (ex: copie du fichier de base y octets à partir du décalage x dans le tampon cible) ou insérer des instructions (par exemple: insérer les x octets suivants dans le tampon) tampon cible).

À titre d’exemple très simple (tiré du document «File System Support for Delta Compression»), considérez que nous voulons créer un tampon delta pour transformer le texte «proxy cache» en «cache proxy». Les instructions résultantes doivent être:

1. Copier 5 octets du décalage 7 (copier le “cache” du tampon de base)
2. Insérer deux espaces
3. Copie 5 octets à partir du décalage 0 (copie du proxy à partir du tampon de base)

La traduction en git devient:

(les octets 1 à 3 représentent la première instruction)

• 0x91 (10010001), qui est divisé en
  • 0x80 (10000000) (le bit le plus significatif définit cette instruction comme une copie de la base vers la sortie)
  • 0x01 (00000001) (signifie ‘avancer d’un octet et l’utiliser comme décalage de base)
  • 0x10 (00010000) (avancez un octet et utilisez-le comme longueur)
• 0x07 (offset)
• 0x05 (longueur)

(les octets 4-6 représentent la deuxième instruction)

• 0x02 (puisque le MSB n’est pas défini, cela signifie “insérer les deux octets suivants dans la sortie”)
• 0x20 (espace)
• 0x20 (espace)

(les octets 7 à 8 représentent la dernière instruction)

• 0x90 (10010000), qui est divisé en
  • 0x80 (10000000) (signifie «copie»)
  • 0x10 (00010000) (avancez un octet et utilisez-le comme longueur)
• 0x05 (longueur)

Notez que dans la dernière copie, l’instruction ne spécifie pas de décalage, ce qui signifie un décalage de 0. Les autres bits du code opération de copie peuvent également être définis lorsque des décalages / longueurs plus importants sont nécessaires.

Le tampon delta de résultat a dans cet exemple 8 octets, ce qui ne représente pas une compression importante puisque le tampon cible a 12 octets, mais lorsque cet encodage est appliqué à de gros fichiers texte, il peut faire une énorme différence.

J’ai récemment poussé une bibliothèque node.js vers github qui implémente les deux fonctions diff / patch en utilisant l’encodage git delta. Le code doit être plus lisible et commenté que celui de git source, qui est fortement optimisé.

J’ai également écrit quelques tests qui expliquent les opcodes de sortie utilisés dans chaque exemple avec un format similaire à celui ci-dessus.

Cet algorithme est-il standardisé et utilisé dans d’autres outils également?

Le format de pack fait partie d’une API publique: les protocoles de transfert utilisés pour les opérations Push et Fetch l’utilisent pour envoyer moins de données sur le réseau.

Ils sont implémentés dans au moins deux autres implémentations majeures de Git en plus de la référence: JGit et libgit2 .

Par conséquent, il est très improbable qu’il y ait des modifications incompatibles avec le format, et peuvent être considérées comme “normalisées” en ce sens.

Ce fichier étonnant de la documentation décrit les heuristiques utilisées dans l’algorithme du pack en tant que commentaire amusant sur un courrier électronique de Linus: https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics. SMS