L'algorithme de comparaison binaire git (stockage delta) est-il standardisé ?

https://stackoverflow.com/questions/9478023

13-11-2019
|

Question

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

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

La solution

Je pense que l'algorithme de comparaison est utilisé pour emballer les fichiers était lié à l'un des codage delta là-bas: initialement (2005) xdelta, et puis libXDiff.
Mais ensuite, comme détaillé ci-dessous, il est passé à une implémentation personnalisée.

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

Git fait la deltification seulement dans les fichiers pack.
Mais lorsque vous poussez via SSH Git générerait un fichier de pack avec Commits, l'autre côté n'a pas, et ces packs sont des packs minces, donc ils ont également des deltas ...mais le côté distant ajoute ensuite des bases à ces packs minces, les rendant ainsi autonomes.

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

Ce fil nous rappelle également :

En fait, packfiles et deltification (LibXDiff, pas xdelta) était, d'après ce dont je me souviens et ce que je comprends, à l'origine à cause de la bande passante du réseau (ce qui coûte beaucoup plus cher que l'espace disque), et Performances d'E/S d'utiliser un seul fichier mmappé au lieu d'un très grand nombre d'objets en vrac.

LibXDiff est mentionné dans ce fil de discussion 2008.

Cependant, depuis lors, l'algorithme a évolué, probablement de manière personnalisée, car Le fil de discussion 2011 illustre, et comme en-tête de diff-delta.c fait remarquer:

Donc, à proprement parler, le code actuel dans Git n'a aucune ressemblance avec le code de libxdiff.
Cependant, l'algorithme de base derrière les deux implémentations est le même..
Étudier la version libxdiff est probablement plus facile afin de 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 <nico@fluxnic.net>, (C) 2005-2007
 */

Plus sur le packfile le Git Book:

packfile format

Git 2.18 ajoute à la description delta dans ce nouveau rubrique documentation, qui indique maintenant (T2 2018) :

Types d'objets

Les types d'objet 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é à une expansion future.Le type 0 n'est pas valide.

Représentation deltifiée

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

Les deux ofs-delta et ref-delta Stockez le "Delta" à appliquer à un autre objet (appelé «objet de base») pour reconstruire l'objet.
La différence entre eux est,

ref-delta code directement le nom de l'objet de base sur 20 octets.

Si l'objet de base se trouve dans le même pack, ofs-delta code à la place le décalage de l'objet de base dans le pack.

L'objet de base peut également être délimité s'il se trouve dans le même pack.
Ref-delta peut également faire référence à un objet extérieur au pack (c'est-à-direle soi-disant "pack mince").Cependant, lorsqu'il est stocké sur le disque, le pack doit être auto-contenu pour éviter la dépendance cyclique.

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

un pour copier une plage d'octets de l'objet source et

un pour insérer de nouvelles données intégrées dans 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 diagrammes suivants suivent la convention dans RFC 1951 (dégonflent le format de données compressé).

Autres conseils

codage delta git est copié / insérer basé sur la copie / insérer.

Cela signifie que le fichier dérivé est codé en tant que séquence d'opcodes pouvant représenter la copie instructions (par exemple: copier à partir du fichier de base y octets à partir de décalage X dans le tampon cible) ou Instructions d'insérer (par exemple: Insérez les octets x suivants dans le tampon cible).

Par exemple très simple (extrait du document "Support du système de fichiers pour la compression Delta '), considérons que nous voulons créer un tampon Delta pour transformer le texte" cache proxy "en "Cache Proxy". Les instructions obtenues devraient être:

Copiez 5 octets de décalage 7 (copiez "Cache" du tampon de base)
Insérez deux espaces
Copiez 5 octets de décalage 0 (copier "proxy" du tampon de base)
qui a traduit le codage de GIT devient:
(octets 1-3 représente la première instruction)
- 0x91 (10010001), qui est divisé en
  - 0x80 (10000000) (le plus important jeu de bits en fait une «copie de la base à la sortie»)
  - 0x01 (00000001) (signifie 'avancer un octet et utilisez-le comme décalage de base)
  - 0x10 (00010000) (avancez un octet et utilisez-le comme longueur)
  - 0x07 (offset)
  - 0x05 (longueur)
    (octets 4-6 représente 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)
      (octets 7-8 représentent la dernière instruction)
      - 0x90 (10010000), qui est divisé en
        
        0x80 (10000000) (Copie ')
        0x10 (00010000) (avancez un octet et utilisez-le comme longueur)
        0x05 (longueur)
        Notez que dans la dernière instruction de copie ne spécifie pas un décalage qui signifie compensé 0. Autres bits Dans la copie opcode peut également être défini lorsque des compensations / longueurs plus grandes sont nécessaires.
        Le tampon Delta résultat a dans cet exemple comporte 8 octets, ce qui n'est pas une grande partie de la compression puisque le tampon cible a 12 octets, mais lorsque cet encodage appliqué aux fichiers texte volumineux, il peut faire une énorme différence.
        J'ai récemment poussé un bibliothèque nœud.js à Github qui implémentent les deux fonctions DIFF / PATCH à l'aide du codage GIT Delta. Le code devrait être plus lisible et commenté que celui de la source GIT, qui est fortement optimisé.
        J'ai aussi écrit quelques-uns tests qui expliquent Les opcodes de sortie utilisés dans chaque exemple avec un format similaire à celui ci-dessus.

Cet algorithme est-il 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 PUSH et FETCH l'utilisent pour envoyer moins de données sur le réseau.
Ils sont mis en œuvre dans au moins deux autres autres implémentations GIT, outre la référence: JGIT et libgit2 .
Par conséquent, il est très peu probable qu'il y aura des modifications incompatibles avec le format, et peut être considérée comme "normalisée" dans ce sens.
Ce fichier étonnant de la DOCS décrit les heuristiques utilisées dans l'algorithme Pack comme commentaire amusant sur un email par Linus: https://github.com/git/git/blob/v2.9.1/documentation/technique/pack-heuristique.txt

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow