Come vengono memorizzate e calcolate le cronologie dei controlli delle versioni?

Question

Considerate questo codice python semplice, che dimostra un design molto semplice controllo di versione per 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) 

Si noti che utilizzando l'elenco la storia si può ricostruire il dizionario corrente in qualsiasi stato che una volta esisteva. Considero questo un "forward build" (per mancanza di un termine migliore) perché per costruire il dizionario corrente bisogna iniziare dall'inizio e elaborare l'intero elenco cronologico. Considero questo l'approccio più ovvio e diretto.

Come ho sentito, i primi sistemi di controllo delle versioni utilizzavano questo processo di "forward build", ma non erano ottimali perché la maggior parte degli utenti si preoccupa di più delle versioni recenti di una build. Inoltre, gli utenti non vogliono scaricare l'intera cronologia quando si preoccupano solo di vedere l'ultima build.

La mia domanda è, quali altri approcci esistono per memorizzare le storie in un sistema di controllo di versione? Forse si potrebbe usare una "backwards build"? Ciò potrebbe consentire agli utenti di scaricare solo le revisioni recenti senza aver bisogno dell'intera cronologia. Ho anche seen alcuni formati diversi per la memorizzazione della cronologia, vale a dire: changeset, istantanee e patch. Quali sono le differenze tra changeset, istantanee e patch?

Dei moderni controlli di versione popolare disponibili, come archiviano le loro storie e quali sono i vantaggi dei loro vari progetti?

Answer 1

Lei ha parlato di questi 3 metodi di memorizzazione (file) -Storia:

1. cerotto: una patch è il (di solito testuale, ma patch binarie sono possibili anche) la rappresentazione della differenza tra due file. È l'output del comando unix diff e può essere applicato dal comando unix patch. Un sacco di sistemi di versioning utilizzano patch per memorizzare la cronologia dei file (ad esempio SVN, CVS, GIT ..). A volte queste patch sono tecnicamente chiamate "delta" come la lettera greca "Δ" che descrive la differenza di due cose.
2. changeset: un changeset è un termine per combinare le modifiche "che appartengono insieme" a file diversi in una singola entità. Non tutti i sistemi di controllo delle versioni supportano i changeset (i più importanti CVS e SourceSafe). Gli sviluppatori utilizzano i changeset per evitare build danneggiati (esempio: modifica della firma di un metodo in un file, modifica la chiamata in un secondo file. È necessario avere entrambe le modifiche in atto per eseguire il programma, altrimenti si verifica un errore). See also here for the difference between changeset and patch.
3. istantanee: sono copie complete dello stato di questo file/file system a questo punto del tempo. Di solito sono piuttosto grandi e il loro utilizzo dipende dalle caratteristiche delle prestazioni. L'istantanea è sempre ridondante a un elenco di patch, ma per recuperare le informazioni più velocemente, a volte delle versioni Sistemi mescolare o combinare le patch e le istantanee

Subversion utilizza avanti delta (aka patch) in repository FSFS e delta arretrate nei repository BDB. Si noti che queste implementazioni hanno differenti caratteristiche prestazionali:

• delta avanti sono veloci nel commettere, ma lenta su casse (come la versione "corrente" deve essere ricostruita)

• delta arretrati sono veloci in controllando ma lento compiere come nuovi delta devono essere costruite per costruire la nuova corrente e riscrivere la precedente "di" come un gruppo di delta

Si noti inoltre che FSFS utilizza un algoritmo "skipping delta" che riduce al minimo i salti per ricostruire una versione specifica. Questo delta saltante tuttavia non è ottimizzato per dimensioni come snapshot di mercurial; minimizza solo il numero di "revisioni" necessarie per creare una versione completa indipendentemente dalle dimensioni complessive.

Ecco un piccolo ascii art (copiato dalla specifica) di un file con 9 revisioni:

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

dove "0 <-1" significa che la base per la revisione del delta 1 è la revisione 0.

Il numero di salti è al massimo il log (N) per le revisioni N.

Anche un effetto molto carino su FSFS è che la revisione precedente verrà scritta solo una volta e dopo questa verrà letta solo da ulteriori azioni. Ecco perché i repository di subversion sono molto stabili: finché non si verifica un errore HW sul disco rigido, si dovrebbe essere in grado di ottenere un repository funzionante anche se si è verificata qualche corruzione nell'ultimo commit: si hanno ancora tutte le versioni precedenti.

Nel backend BDB si riscrive costantemente la revisione corrente su check-in/commit, rendendo questo processo soggetto a corruzione dei dati. Anche se si memorizza il testo completo solo nella revisione corrente, la corruzione dei dati sul commit probabilmente distruggerà grandi parti della cronologia.

Answer 2

Penso che la sovversione abbia fatto alcuni tentativi di costruire all'indietro. Ma posso spiegare quello che so meglio: istantanee Mercurial.

Mercurial utilizza uno schema di costruzione in avanti. Ma affinché ogni revisione sia facilmente ricostruibile, ci sono dei punti di risincronizzazione: ogni volta che la dimensione di tutti i delta necessari per ricostruire una revisione è maggiore di due volte il testo completo, viene memorizzata una versione full text (un'istantanea compressa) e tutti i delta successivi sono calcolati rispetto a questa nuova istantanea.

Ciò significa che non è mai necessario leggere più di 3 volte la dimensione del testo per recuperare qualsiasi revisione.

Potete trovare ulteriori dettagli in the Hg Book.

Answer 3

Come risposta più generica, è necessario differenziare CVCS (VCS centralizzato, come CVS, SVN, Perforce, ClearCase, ...) da DVCS (Distributed VCS, like Git or Mercurial).
Sono compresi different workflows and usage.

In particolare, lo scambio di dati tra un CVCS cliente e il suo assistente sarà più importante che con un DVCS (che ha davvero bisogno delta quando spingere o tirare il tutto pronti contro termine)

Questo è il motivo delta sono molto importante per la maggior parte delle operazioni in un CVC, un aspetto importante solo per determinate operazioni e per diversi motivi in ​​un DVCS.

Delta sono descritte in Eric Sink due libri:

• Source Control HOWTO, capitolo Chapter 4: Repositories:

Repository = File System * Tempo

Un albero è una gerarchia di cartelle e File. Un delta è la differenza tra due alberi. In teoria, questi due alberi non hanno bisogno di essere correlati. Tuttavia, in pratica, l'unica ragione per cui calcoliamo la differenza tra di loro è perché uno di essi è derivato dall'altro. Alcuni sviluppatori hanno iniziato con l'albero N e hanno apportato una o più modifiche, risultando nella struttura N + 1.

Possiamo pensare al delta come a una serie di modifiche. In effetti, molti strumenti SCM usano il termine "changeset" esattamente per questo scopo. Un changeset è semplicemente un elenco dei cambiamenti che esprimono la differenza tra due alberi.

Il senso di delta è importante (vedere this thread): delta avanti o delta inverso.

Alcuni strumenti SCM utilizzano una sorta di design di compromesso. Con un solo approccio, invece di memorizzare solo un albero intero e rappresentare ogni altro albero come un delta, cospargiamo alcuni alberi pieni lungo il percorso.

È possibile visualizzare l'evoluzione del "vecchio" VCS in Eric Raymond's Understanding Version-Control Systems.

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

Molti strumenti di controllo delle versioni moderne Utilizzare i delta dei file binari per la conservazione repository.
Un algoritmo delta file popolare è chiamato vcdiff.
Emette un elenco di intervalli di byte che sono stati modificati. Ciò significa che può gestire qualsiasi tipo di file, binario o testo. Come vantaggio accessorio, l'algoritmo vcdiff comprime i dati allo stesso tempo.

non dimenticare che la gestione del delta ha anche un'influenza sul Directed Acyclic Graphs (DAGs) creato per rappresentare la storia (vedi "Arrows direction in ProGit book" e il inconvenient behind DAG).

si possono trovare specifiche sulla gestione delta per:

• Git: "Is the git binary diff algorithm (delta storage) standardized?"
• Mercurial: "Mercurial: Repository Structure"
• Veracity (che combina sia l'approccio): "Veracity: DAGs and Data"

Veracity supporta due tipi di DAG:

• Un albero DAG mantiene la cronologia delle versioni di una struttura di directory da un file system. Ogni nodo del DAG rappresenta una versione dell'intero albero.

• Un database (o "db") DAG mantiene la cronologia delle versioni di un database o un elenco di record. Ogni nodo del DAG rappresenta uno stato del database completo.

Questo ultimo punto illustra che la terza generazione (quarta?) Di VCS deve fare i conti con la distribuzione non solo dei file (albero), ma anche database (per vari scopi)