¿Está estandarizado el algorithm de diferencias bit git (almacenamiento delta)?

Git usa una compression delta para almacenar objects que son similares entre sí.

¿Este algorithm está estandarizado y se usa en otras herramientas también? ¿Hay documentation que describa el formatting? ¿Es compatible con xdelta / VCDIFF / RFC 3284?

Creo que el diff algo usado para los files del package 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 packages.
Pero cuando presionas a través de SSH, git generará un file de package con confirmaciones que el otro lado no tiene, y esos packages son delgados, por lo que también tienen deltas … pero el lado remoto agrega bases a esos packages delgados que los hacen ser único.

(Nota: la creación de muchos files de packages, o la recuperación de información en un enorme file de package es costosa , y explica por qué git no maneja bien los files grandes o los grandes repositorys.
Ver más en " git con files grandes "

Este hilo también nos restring:

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

LibXDiff se menciona en este hilo de 2008 .

Sin embargo, desde entonces, el algorithm 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 algorithm 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 inspinetworking by parts of LibXDiff from Davide Libenzi * http://www.xmailserver.org/xdiff-lib.html * * Rewritten for GIT by Niqueues Pitre <nico@fluxnic.net>, (C) 2005-2007 */ 

Más sobre los files de packages del Libro de Git :

formato de archivo de paquete

La encoding Git delta está basada en copyr / insert.

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

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

  1. Copie 5 bytes del desplazamiento 7 (copie 'caching' 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 encoding de git se convierte en:

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

  • 0x91 (10010001), que se divide en
    • 0x80 (10000000) (el set de bits más significativo hace de esto una instrucción 'copy 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 'insert 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 'copy')
    • 0x10 (00010000) (avance un byte y úselo como longitud)
  • 0x05 (longitud)

Observe que en la última copy, las instrucciones no especifican un desplazamiento, lo que significa compensación 0. Otros bits en el código de operación de copy 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 compression ya que el búfer de destino tiene 12 bytes, pero cuando esta encoding se aplica a files de text 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 encoding git delta. El código 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 testings que explican los códigos de operación de salida utilizados en cada ejemplo con un formatting similar al anterior.

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

El formatting del package 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 less datos a través de la networking.

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

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

Este sorprendente file de los documentos describe la heurística utilizada en el algorithm del package 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

    Intereting Posts