¿Cómo se almacenan y calculan los historiales de control de versiones?

Question

consideran este código Python sencilla, lo que demuestra un diseño muy simple de control de versiones para un Dictonary:

def build_current(history): 
    current = {} 
    for action, key, value in history: 
     assert action in ('set', 'del') 
     if action == 'set': 
      current[key] = value 
     elif action == 'del': 
      del current[key] 
    return current 

history = [] 
history.append(('set', '1', 'one')) 
history.append(('set', '2', 'two')) 
history.append(('set', '3', 'three')) 
print build_current(history) 
history.append(('del', '2', None)) 
history.append(('set', '1', 'uno')) 
history.append(('set', '4', 'four')) 
print build_current(history) 
for action, key, value in history: 
    if key == '2': 
     print '(%s, %s, %s)' % (action, key, value) 

en cuenta que mediante el uso de la lista del historial se puede reconstruir el diccionario actual en cualquier estado que existió una vez. Considero que esto es una "creación progresiva" (por falta de un término mejor) porque para construir el diccionario actual uno debe comenzar desde el principio y procesar toda la lista de historial. Considero que este es el enfoque más obvio y directo.

Como he escuchado, los primeros sistemas de control de versiones usaban este proceso de "construcción directa", pero no eran óptimos porque a la mayoría de los usuarios les interesan más las versiones recientes de una compilación. Además, los usuarios no desean descargar todo el historial cuando solo les interesa ver la última compilación.

Mi pregunta es, ¿qué otros enfoques existen para almacenar historiales en un sistema de control de versiones? ¿Tal vez podría usarse una "construcción hacia atrás"? Eso podría permitir a los usuarios descargar solo revisiones recientes sin necesitar todo el historial. También tengo seen algunos formatos diferentes para almacenar el historial, a saber: conjuntos de cambios, instantáneas y parches. ¿Cuáles son las diferencias entre changesets, snapshots y parches?

De los modernos controles de versión popular disponibles, ¿cómo almacenan sus historias y cuáles son las ventajas de sus diversos diseños?

Answer 1

Usted mencionó estos 3 métodos de almacenamiento (archivo) -Historia:

1. parche: un parche es el (normalmente textual, pero los parches binarios son también posibles) la representación de la diferencia entre los dos archivos. Es la salida del comando de Unix diff y se puede aplicar con el comando de Unix parche. Muchos sistemas de control de versiones están usando parches para almacenar el historial de archivos (por ejemplo, SVN, CVS, GIT ...). A veces, estos parches se llaman técnicamente "delta" como la carta griega "Δ" que describe la diferencia de dos cosas.
2. changeset: un conjunto de cambios es un término para combinar los cambios "que pertenecen" a diferentes archivos en una sola entidad. No todos los sistemas de versiones admiten conjuntos de cambios (CVS y SourceSafe más notables). Los desarrolladores están usando conjuntos de cambios para evitar compilaciones rotas (por ejemplo: cambiar la firma de un método en un archivo, cambiar la llamada en un segundo archivo. Debe tener ambos cambios en su lugar para ejecutar el programa, de lo contrario, obtendrá un error). See also here for the difference between changeset and patch.
3. instantáneas: son copias completas del estado de este archivo/sistema de archivos en este momento. Por lo general, son bastante grandes y su uso depende de las características de rendimiento. La instantánea es siempre redundante para una lista de parches, sin embargo para recuperar la información más rápido, a veces de versiones de los sistemas de mezclar o combinar los parches y las instantáneas

Subversion usa hacia adelante deltas (también conocidos como parches) en repositorios FSFS y deltas hacia atrás en BDB Repositories. Tenga en cuenta que estas implementaciones tienen diferentes características de rendimiento:

• deltas hacia adelante son rápidos en la comisión, pero lento en las cajas (como la versión "actual" debe ser reconstruido)

• deltas atrasadas son rápidos en el registro de salida pero lento en cometer como nuevos deltas deben ser construidos para construir la nueva corriente y reescribir el anterior "actual" como un montón de deltas

También tenga en cuenta que FSFS utiliza un algoritmo "skipping delta" que minimiza los saltos para reconstruir una versión específica. Sin embargo, este delta omitido no se optimiza en tamaño como instantáneas mercuriales; solo minimiza la cantidad de "revisiones" que necesita para crear una versión completa, independientemente del tamaño general.

Aquí una pequeña arte ascii (copiado de la especificación) de un archivo con 9 revisiones:

0 <- 1 2 <- 3 4 <- 5 6 <- 7 
0 <------ 2   4 <------ 6 
0 <---------------- 4 
0 <------------------------------------ 8 <- 9 

donde "0 < - 1" significa que la base delta de revisión 1 es la revisión 0.

El número de saltos es a lo sumo log (N) para N revisiones.

También un efecto muy bonito en FSFS es que la revisión anterior se escribirá solo una vez y después de esto solo se leerán mediante otras acciones. Es por eso que los repositorios de subversión son muy estables: siempre que no tenga una falla HW en su disco duro, debería poder obtener un repositorio operativo incluso si se produjo algún daño en la última confirmación: todavía tiene todas las revisiones anteriores.

En BDB Backend ha reescrito constantemente la revisión actual en checkins/commits, lo que hace que este proceso sea propenso a daños en los datos. Además, a medida que almacena el texto completo solo en la revisión actual, corromper los datos en la confirmación probablemente destruirá grandes partes de su historial.

Answer 2

Creo que la subversión hizo algunos intentos de construir hacia atrás. Pero puedo explicar lo que sé mejor: instantáneas mercuriales.

Mercurial utiliza un esquema de compilación progresiva. Pero para que cada revisión sea fácilmente reconstruible, existen puntos de resincronización: cada vez que el tamaño de todos los deltas necesarios para reconstruir una revisión es más de dos veces el texto completo, se almacena una versión de texto completo (una instantánea comprimida) y todos los delta posteriores se calculan en relación con esta nueva instantánea.

Esto significa que nunca necesita leer más de 3 veces el tamaño del texto para recuperar cualquier revisión.

Puede encontrar más detalles in the Hg Book.

Answer 3

Como una respuesta más genérica, debe diferenciar CVCS (VCS centralizado, como CVS, SVN, Perforce, ClearCase, ...) de DVCS (Distributed VCS, like Git or Mercurial).
Incluyen different workflows and usage.

En particular, el intercambio de datos entre un CVC cliente y su servidor va a ser más importante que con un DVCS (que realmente necesita delta al empujar o tirar del todo repo)

Esa es la razón por delta son muy importante para la mayoría de las operaciones en un CVCS, una función importante solo para ciertas operaciones y por diferentes motivos en un DVCS.

Deltas se describen en Eric Sink dos libros:

• Source Control HOWTO, capítulo Chapter 4: Repositories:

Repositorio = Sistema de archivos * Tiempo

Un árbol es una jerarquía de carpetas y archivos. Un delta es la diferencia entre dos árboles. En teoría, esos dos árboles no necesitan estar relacionados. Sin embargo, en la práctica, la única razón por la que calculamos la diferencia entre ellos es porque uno de ellos se deriva del otro. Algunos desarrolladores comenzaron con el árbol N e hicieron uno o más cambios, lo que dio como resultado el árbol N + 1.

podemos pensar en el delta como un conjunto de cambios. De hecho, muchas herramientas de SCM usan el término "conjunto de cambios" para exactamente este propósito. Un conjunto de cambios es simplemente una lista de los cambios que expresan la diferencia entre dos árboles.

El sentido delta es importante (ver this thread): delta hacia adelante o hacia atrás.

Algunas herramientas SCM utilizan algún tipo de diseño de compromiso. En un enfoque, en lugar de almacenar solo un árbol completo y representar cada otro árbol como un delta, rociamos algunos árboles más en el camino.

Puede ver la evolución de la "vieja" VCS en Eric Raymond's Understanding Version-Control Systems.

• Version Control by Example, Chapter 12. DVCS Internals:

Muchas herramientas de control de versiones modernas utilizan los deltas de archivos binarios para el almacenamiento repositorio.
Un algoritmo de delta de archivo popular se llama vcdiff.
Muestra una lista de rangos de bytes que se han cambiado. Esto significa que puede manejar cualquier tipo de archivo, binario o texto. Como beneficio secundario, el algoritmo vcdiff comprime los datos al mismo tiempo.

no se olvide que la gestión de Delta también tiene una influencia en la Directed Acyclic Graphs (DAGs) creado para la representación de la historia (ver "Arrows direction in ProGit book" y el inconvenient behind DAG).

puede encontrar detalles sobre el manejo de delta para:

• Git: "Is the git binary diff algorithm (delta storage) standardized?"
• Mercurial: "Mercurial: Repository Structure"
• veracidad (que combina enfoque): "Veracity: DAGs and Data"

Veracity admite dos tipos de DAG:

• Un árbol DAG mantiene el historial de versiones de una estructura de directorios de un sistema de archivos. Cada nodo del DAG representa una versión del árbol completo.

• Una base de datos (o "db") DAG guarda el historial de versiones de una base de datos, o una lista de registros. Cada nodo del DAG representa un estado de la base de datos completa.

Ese último punto ilustra que la tercera generación (cuarta?) De VCS debe ocuparse de la distribución no sólo de los archivos (árbol), sino también bases de datos (para diversos fines)