Git usa una compresión delta para almacenar objetos que son similares entre sí.¿Está estandarizado el algoritmo de diferencias bit git (almacenamiento delta)?
¿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?
creo que el algo diff utilizado para pack files estaba vinculado a uno de los delta encoding por ahí: initially (2005) xdelta, y luego libXDiff.
Pero luego, como se detalla a continuación, cambió a una implementación personalizada.
De todos modos, como mentioned here:
Git hace deltificación solamente en packfiles.
Pero al presionar a través de SSH, git generaría 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 los delgados paquetes que los hacen independientes.
(nota:. Packfiles la creación de muchos, o la recuperación de información en gran PACKFILE es costosa, y explicar por qué git no maneja bien archivos de gran tamaño o gran repo
Ver más en "git with large files")
This thread también nos recuerda:
packfiles realidad y deltificación (LibXDiff, no xdelta) era, por lo que recuerdo yu nderstand, originalmente debido al ancho de banda de la red (que es mucho más costoso que el espacio en disco) y E/S rendimiento de utilizar un solo archivo mmapped en lugar de una gran cantidad de objetos sueltos.
Se menciona LibXDiff en este 2008 thread.
Sin embargo, desde entonces, el algo ha evolucionado, probablemente en uno personalizado, ya que esto 2011 thread illustrates, y como el encabezado de diff-delta.c señala:
Por lo tanto, en sentido estricto, el código actual en Git no tiene ningún parecido con el código libxdiff en absoluto. Sin embargo, el algoritmo básico detrás de ambas implementaciones es el mismo.
Probablemente sea más fácil estudiar la versión de libxdiff 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 el packfiles the Git Book:
Git delta codificación es copia/inserto basado.
Esto significa que el archivo derivado se codifica como una secuencia de códigos de operación que pueden representar copia instrucciones (por ejemplo: copia del archivo de base de Y bytes a partir de desplazamiento x en la memoria intermedia de destino) instrucciones de inserción o (por ejemplo: inserto los siguientes x bytes en el buffer de destino).
Como un ejemplo muy sencillo (tomado de la 'Soporte del sistema de archivos para Delta Compresión' papel), consideramos que queremos crear un buffer delta para transformar el texto "proxy de caché" en "caché de proxy ". Las instrucciones resultantes deben ser:
que se tradujo en la codificación de gIT se convierte en:
(1-3 bytes representan la primera instrucción)
(bytes 4-6 representan la segunda instrucción)
(7-8 bytes representan la última instrucción)
en cuenta que en la última instrucción de copia no especifica un desplazamiento que implica el desplazamiento 0. Otros bits de en el código de operación de copia también se puede establecer cuando/se necesitan grandes longitudes compensaciones.
búfer deltaEl resultado tiene en este ejemplo tiene 8 bytes, que no es mucho de una compresión desde el buffer de destino tiene 12 bytes, pero cuando esto se aplica a la codificación de texto archivos de gran tamaño que puede hacer una gran diferencia.
He enviado recientemente un node.js library a github que implementa ambas funciones de 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 git, que está muy optimizado.
También he escrito unos cuantos tests que explican los códigos de operación de salida utilizados en cada ejemplo con un formato similar a la anterior.
El siguiente artículo también contiene información útil: http://stefan.saasen.me/articles/git-clone-in-haskell-from-the-bottom-up/#pack_file_format –
¿Este algoritmo está estandarizado y se usa en otras herramientas también?
El formato de paquete es 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 incompatibles hacia atrás en el formato, y se puede considerar como "estandarizado" en ese sentido.
Este archivo increíble de la documentación describe las heurísticas utilizadas en el algoritmo de compresión como un comentario divertido en un correo electrónico por Linus: https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt
Buen punto (y más actual que mi " histórico "respuesta"). +1 – VonC
@VonC ¡Gracias! Esta pregunta es bastante abierta, y tu respuesta y la de Thiago también contienen información útil. Me hace feliz solo tener una respuesta al lado de la de otros grandes programadores como ustedes. :) –
El algo final podría ser uno personalizado, cuando leí un hilo 2011 como http: //git.661346.n2.nabble.com/diff-ing-files-td6446460.html – VonC
En 2008, aparentemente se utilizó libXDiff: http://git.661346.n2.nabble.com/libxdiff-and-patience- diff-td1452272.html – VonC
Ese hilo de 2011 es un buen enlace. Opción cita: "Así que, estrictamente hablando, el código actual en Git no tiene ningún parecido con el código libxdiff en absoluto. Sin embargo, el algoritmo básico detrás de ambas implementaciones es el mismo". – Thilo