Est-ce que l'algorithme de différenciation binaire git (stockage delta) est normalisé ?

Question

Git utilise une compression delta pour stocker des objets qui sont similaires les uns aux autres.

Cet algorithme est-il normalisé et utilisé dans d'autres outils également? Y a-t-il une documentation décrivant le format? Est-il compatible avec xdelta/VCDIFF/RFC 3284?

Answer 1

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

Quoi qu'il en soit, comme mentionné ici:

Git effectue la deltification seulement dans les fichiers pack.
Mais lorsque vous poussez via SSH, git génère un fichier pack avec des commits que l'autre côté n'a pas, et ces packs sont des thin packs, donc ils ont aussi des deltas... mais le côté distant ajoute ensuite des bases à ces thin packs les rendant autonomes.

(note : créer de nombreux fichiers pack, ou récupérer des informations dans un énorme fichier pack est coûteux, et explique pourquoi git ne gère pas bien les fichiers volumineux ou les gros dépôts.
Voir plus sur "git avec de gros fichiers")

Ce fil de discussion nous rappelle également :

En fait, les fichiers pack et la deltification (LibXDiff, pas xdelta) étaient, d'après ce dont je me souviens et que je comprends, initialement à cause de la bande passante réseau (qui est bien plus coûteuse que l'espace disque), et de la performance E/S d'utilisation d'un seul fichier mmappé au lieu d'un très grand nombre d'objets lâches.

LibXDiff est mentionné dans ce fil de discussion de 2008.

Cependant, depuis lors, l'algo a évolué, probablement vers une version personnalisée, comme le montre ce fil de discussion de 2011, et comme l'en-tête de diff-delta.c le souligne :

Donc, en termes stricts, 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.
Étudier la version libxdiff est probablement plus simple pour comprendre comment cela fonctionne.

/*
 * diff-delta.c: génère un delta entre deux tampons
 *
 * Ce code a été grandement inspiré par certaines parties de LibXDiff de Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Réécrit pour GIT par Nicolas Pitre , (C) 2005-2007
 */

Plus sur les fichiers pack dans le livre Git:

---

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

Types d'objets

Les types d'objets valides sont :

• 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é pour une expansion future. Le type 0 est invalide.

Représentation delta

Conceptuellement, il n'y a que quatre types d'objets : commit, arbre, tag et blob.
Cependant, pour économiser de l'espace, un objet peut être stocké sous forme de "delta" d'un autre objet "de base".
Ces représentations se voient attribuer de nouveaux types ofs-delta et ref-delta, qui sont valides uniquement dans un fichier pack.

À la fois ofs-delta et ref-delta stockent le "delta" à appliquer à un autre objet (appelé 'objet de base') pour reconstruire l'objet.
La différence entre eux est,

• ref-delta encode directement le nom de 20 bytes de l'objet de base.
  • Si l'objet de base est dans le même pack, ofs-delta encode l'offset de l'objet de base dans le pack à la place.

L'objet de base pourrait également être deltifié s'il est dans le même pack.
Ref-delta peut également se référer à un objet hors du pack (c'est-à-dire le "thin pack" en question). Cependant, lorsqu'il est stocké sur disque, le pack doit être autonome pour éviter une dépendance cyclique.

Les données delta sont une séquence d'instructions pour reconstruire un objet à partir de l'objet de base.
Si l'objet de base est deltifié, il doit d'abord être converti en forme canonique. Chaque instruction ajoute de plus en plus de données à l'objet cible jusqu'à ce qu'il soit complet.
Jusqu'à présent, deux instructions sont prises en charge :

• une pour copier une plage d'octets à partir de l'objet source et
• une pour insérer de nouvelles données intégrées à l'instruction elle-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 de données compressées Deflate).

Answer 2

L'encodage delta Git est basé sur la copie/l'insertion.

Cela signifie que le fichier dérivé est encodé sous forme d'une séquence d'opcodes pouvant représenter des instructions de copie (par exemple : copier à partir du fichier de base y octets à partir du décalage x dans le tampon cible) ou des instructions d'insertion (par exemple : insérer les x octets suivants dans le tampon cible).

Comme exemple très simple (issu de l'article "File System Support for Delta Compression"), considérons que nous voulons créer un tampon delta pour transformer le texte "proxy cache" en "cache proxy". Les instructions résultantes devraient être :

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

Ce qui, une fois traduit en encodage 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éfini fait de cette instruction une 'copie du base vers la sortie')
  • 0x01 (00000001) (signifie 'avance d'un octet et l'utilise en tant que décalage de base')
  • 0x10 (00010000) (avance d'un octet et l'utilise comme longueur)
• 0x07 (décalage)
• 0x05 (longueur)

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

• 0x02 (comme 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) (avance d'un octet et l'utilise comme longueur)
• 0x05 (longueur)

Remarquez que dans la dernière instruction de copie, aucun décalage n'est spécifié, ce qui signifie le décalage 0. D'autres bits dans l'opcode de copie peuvent également être définis en cas de besoins en termes de plus grands décalages/longueurs.

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

Récemment, j'ai publié une bibliothèque node.js sur github qui implémente à la fois les fonctions de différence et de patch en utilisant l'encodage delta git. Le code devrait être plus lisible et commenté que celui de la source git, 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.

Answer 3

Est-ce que cet algorithme est normalisé et utilisé dans d'autres outils également ?

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

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

Par conséquent, il est très peu probable qu'il y ait des changements incompatibles avec les anciennes versions du format, et peut être considéré comme "normalisé" en ce sens.

Ce fichier étonnant de la documentation décrit les heuristiques utilisées dans l'algorithme de pack comme un commentaire amusant sur un email de Linus : https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt