tag - ¿Está estandarizado el algoritmo de diferencias bit git(almacenamiento delta)?

¿para qué nos sirve el sha-1 cuando creamos tags?

Question

Git usa una compresión delta para almacenar objetos que son similares entre sí.

¿Este algoritmo está estandarizado y se usa en otras herramientas también? ¿Hay documentación que describa el formato? ¿Es compatible con xdelta / VCDIFF / RFC 3284?

Answer 1

¿Este algoritmo está estandarizado y se usa en otras herramientas también?

El formato del paquete forma parte de una API pública: los protocolos de transferencia utilizados para las operaciones de inserción y recuperación lo utilizan para enviar menos datos a través de la red.

Se implementan en al menos otras dos implementaciones principales de Git además de la referencia: JGit y libgit2 .

Por lo tanto, es muy poco probable que haya cambios hacia atrás incompatibles con el formato, y se puede considerar que está "estandarizado" en ese sentido.

Este sorprendente archivo de los documentos describe la heurística utilizada en el algoritmo del paquete como un comentario divertido en un correo electrónico de Linus: https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt

Answer 2

Creo que el diff algo usado para los archivos del paquete estaba vinculado a una de las codificaciones delta : inicialmente (2005) xdelta , y luego libXDiff .
Pero luego, como se detalla a continuación, cambió a una implementación personalizada.

De todos modos, como se menciona aquí :

Git realiza la delificación solo en paquetes.
Pero cuando presionas a través de SSH, git generará un archivo de paquete con confirmaciones que el otro lado no tiene, y esos paquetes son delgados, por lo que también tienen deltas ... pero el lado remoto agrega bases a esos paquetes delgados que los hacen ser único.

(Nota: la creación de muchos archivos de paquetes, o la recuperación de información en un enorme archivo de paquete es costosa , y explica por qué git no maneja bien los archivos grandes o los grandes repositorios.
Ver más en " git con archivos grandes "

Este hilo también nos recuerda:

En realidad, los archivos packfiles y la deltificación ( LibXDiff, no xdelta ) eran, originalmente , por el ancho de banda de la red (que es mucho más costoso que el espacio en disco) y el rendimiento de E / S al usar un solo archivo mmapped en lugar de un gran número de objetos sueltos.

LibXDiff se menciona en este hilo de 2008 .

Sin embargo, desde entonces, el algoritmo ha evolucionado, probablemente en uno personalizado, como lo ilustra este hilo de 2011 , y como lo señala el encabezado de diff-delta.c :

Entonces, estrictamente hablando, el código actual en Git no guarda ningún parecido con el código libxdiff.
Sin embargo, el algoritmo básico detrás de ambas implementaciones es el mismo .
Estudiar la versión de libxdiff es probablemente más fácil para entender cómo funciona esto.

/*
 * 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 <[email protected]>, (C) 2005-2007
 */

Más sobre los archivos de paquetes del Libro de Git :

Git 2.18 agrega a la descripción del delta en esta nueva sección de documentación , que ahora (Q2 2018) establece:

Tipos de objetos

Los tipos de objetos válidos son:

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

Tipo 5 está reservado para futuras expansiones. El tipo 0 no es válido.

Representación deltificada

Conceptualmente solo hay cuatro tipos de objetos: commit, tree, tag y blob.
Sin embargo, para ahorrar espacio, un objeto podría almacenarse como un "delta" de otro objeto "base".
A estas representaciones se les asignan nuevos tipos de-delta y ref-delta, que solo son válidos en un archivo de paquete.

Ambos ofs-delta y ref-delta almacenan el "delta" que se aplicará a otro objeto (llamado ''objeto base'') para reconstruir el objeto.
La diferencia entre ellos es

• ref-delta codifica directamente el nombre del objeto base de 20 bytes.
  • Si el objeto base está en el mismo paquete, ofs-delta codifica el desplazamiento del objeto base en el paquete en su lugar.

El objeto base también podría ser deltificado si está en el mismo paquete.
Ref-delta también puede referirse a un objeto fuera del paquete (es decir, el denominado "paquete delgado") . Sin embargo, cuando se almacena en el disco, el paquete debe ser independiente para evitar la dependencia cíclica.

Los datos delta son una secuencia de instrucciones para reconstruir un objeto desde el objeto base.
Si el objeto base está desdificado, primero se debe convertir a forma canónica. Cada instrucción agrega cada vez más datos al objeto de destino hasta que esté completo.
Hay dos instrucciones compatibles hasta el momento:

• uno para copiar un rango de bytes desde el objeto fuente y
• uno para insertar nuevos datos incrustados en la instrucción en sí.

Cada instrucción tiene longitud variable. El tipo de instrucción está determinado por el séptimo bit del primer octeto. Los siguientes diagramas siguen la convención en RFC 1951 (Deflate comprimed data format).

Answer 3

La codificación Git delta está basada en copiar / insertar.

Esto significa que el archivo derivado está codificado como una secuencia de códigos de operación que pueden representar instrucciones de copia (por ejemplo: copia del archivo base y bytes comenzando desde el desplazamiento x en el búfer de destino) o insertar instrucciones (por ej .: inserte los siguientes x bytes en el buffer de destino).

Como un ejemplo muy simple (tomado del documento ''Soporte del sistema de archivos para Delta Compression''), considere que queremos crear un buffer delta para transformar el texto "proxy cache" en "cache proxy". Las instrucciones resultantes deberían ser:

1. Copie 5 bytes del desplazamiento 7 (copie ''caché'' del buffer base)
2. Inserta dos espacios
3. Copie 5 bytes del desplazamiento 0 (copie ''proxy'' del buffer base)

Lo que se traduce a la codificación de git se convierte en:

(Los bytes 1-3 representan la primera instrucción)

• 0x91 (10010001), que se divide en
  • 0x80 (10000000) (el conjunto de bits más significativo hace de esto una instrucción ''copia desde la base hasta la salida'')
  • 0x01 (00000001) (significa ''avanzar un byte y usarlo como el desplazamiento base)
  • 0x10 (00010000) (avance un byte y úselo como longitud)
• 0x07 (desplazamiento)
• 0x05 (longitud)

(Los bytes 4-6 representan la segunda instrucción)

• 0x02 (dado que el MSB no está configurado, esto significa ''insertar los siguientes dos bytes en la salida'')
• 0x20 (espacio)
• 0x20 (espacio)

(Los bytes 7-8 representan la última instrucción)

• 0x90 (10010000), que se divide en
  • 0x80 (10000000) (significa ''copia'')
  • 0x10 (00010000) (avance un byte y úselo como longitud)
• 0x05 (longitud)

Observe que en la última copia, las instrucciones no especifican un desplazamiento, lo que significa compensación 0. Otros bits en el código de operación de copia también se pueden establecer cuando se necesitan desplazamientos / longitudes mayores.

El búfer de delta resultante tiene en este ejemplo 8 bytes, lo cual no es mucha compresión ya que el búfer de destino tiene 12 bytes, pero cuando esta codificación se aplica a archivos de texto de gran tamaño, puede hacer una gran diferencia.

Recientemente he enviado una biblioteca node.js a github que implementa ambas funciones diff / patch usando la codificación git delta. El code debería ser más legible y comentado que el que está en la fuente de git, que está muy optimizado.

También he escrito algunas tests que explican los códigos de operación de salida utilizados en cada ejemplo con un formato similar al anterior.