Как хранятся и вычисляются истории контроля версий?

Рассмотрим этот простой код python, который демонстрирует очень простой вариант управления версиями для диктатора:

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)

Обратите внимание, что с помощью списка истории вы можете восстановить текущий словарь в любом состоянии, которое оно когда-то существовало. Я считаю это "форвардной сборкой" (из-за отсутствия лучшего термина), потому что для создания текущего словаря нужно начинать с самого начала и обрабатывать весь список истории. Я считаю это наиболее очевидным и прямым способом.

Как я уже слышал, ранние системы управления версиями использовали этот процесс "прямой сборки", но они не были оптимальными, поскольку большинство пользователей больше заботятся о последних версиях сборки. Кроме того, пользователи не хотят загружать всю историю, когда они только заботятся о том, чтобы увидеть последнюю сборку.

Тогда мой вопрос, какие существуют другие подходы для хранения историй в системе управления версиями? Возможно, можно использовать "обратную сборку"? Это может позволить пользователям загружать только последние версии, не требуя всей истории. Я также видел несколько разных форматов для хранения истории, а именно: изменения, моментальные снимки и патчи. Каковы различия между наборами изменений, моментальными снимками и патчами?

Из современных популярных доступных элементов управления версиями, как они хранят свои истории и каковы преимущества их различных конструкций?

Ответы

Ответ 1

Вы упомянули эти 3 метода хранения (файла) -истории:

  • патч: патч - это (как правило, текстовые, но двоичные патчи также возможны) представление разницы между двумя файлами. Это вывод команды unix diff и может применяться с помощью патча unix. Многие системы управления версиями используют патчи для хранения истории файлов (например, SVN, CVS, GIT..). Иногда эти патчи технически называют "дельта" как греческое письмо "Δ" , описывающее различие двух вещей.
  • changeet: набор изменений - это термин, который объединяет изменения, "относящиеся друг к другу" к разным файлам в одном объекте. Не все системы управления версиями поддерживают изменения (наиболее заметные CVS и SourceSafe). Разработчик использует набор изменений, чтобы избежать сломанных сборок (например: изменить подпись метода в одном файле, изменить вызов во втором файле. Для запуска программы необходимо иметь как изменения, в противном случае вы получите сообщение об ошибке). См. также разницу между набором изменений и патчем.
  • моментальные снимки: это полные копии состояния этого файла/файловой системы до этого момента. Они обычно довольно большие, и их использование зависит от характеристик производительности. Снимок всегда избыточен для списка патчей, однако для более быстрой загрузки информации, иногда системы управления версиями смешивают или объединяют патчи и снимки.

Subversion использует репозитории вперед (aka patches) в репозиториях FSFS и обратные дельта в репозиториях BDB. Обратите внимание, что эти реализации имеют разные характеристики:

  • передовые дельта быстро фиксируются, но медленны при проверках (как "текущая" версия должна быть восстановлена)

  • Дельты назад быстро проверяются, но медленны при фиксации как новые Дельты должны быть построены для построения нового тока и переписать предыдущий "ток" как кучу дельт

Также обратите внимание, что FSFS использует алгоритм "skipping delta" , который минимизирует переходы для восстановления конкретной версии. Однако эта пропускная способность не оптимизирована по размеру как снимки ртути; он просто сводит к минимуму количество "ревизий", необходимых для создания полной версии независимо от общего размера.

Здесь небольшое искусство ascii (скопированное из спецификации) файла с 9 версиями:

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

где "0 < - 1" означает, что дельта-база для ревизии 1 является версией 0.

Число переходов не превышает log (N) для N ревизий.

Также очень хороший эффект для FSFS заключается в том, что более старая версия будет написана только один раз, после чего они будут прочитаны только дальнейшими действиями. Поэтому репозитории subversion очень стабильны: до тех пор, пока у вас нет HW-сбоя на вашем жестком диске, вы должны иметь возможность получить рабочий репозиторий, даже если в последнем коммите произошел некоторый коррупционный: у вас все еще есть старые версии.

В BDB Backend вы постоянно переписываете текущую версию проверок/коммитов, что делает этот процесс подверженным повреждению данных. Кроме того, поскольку вы сохраняете полный текст только в текущей версии, развращение данных о фиксации, скорее всего, уничтожит большие части вашей истории.

Ответ 2

Я думаю, что подрывная деятельность сделала несколько попыток назад. Но я могу объяснить, что я знаю лучше: Меркуриальные снимки.

Mercurial использует схему форвардной сборки. Но для того, чтобы каждая ревизия была легко перестраиваемой, есть точки повторной синхронизации: каждый раз, когда размер всех дельт, необходимых для перестройки ревизии, больше, чем в два раза больше текста, сохраняется полная текстовая версия (сжатый снимок) и все последующие дельта вычисляются относительно этого нового моментального снимка.

Это означает, что вам никогда не нужно читать более чем в 3 раза больше размера текста для получения любой версии.

Вы можете найти более подробную информацию в Hg Book.

Ответ 3

Как более общий ответ, вам нужно отличить CVCS (централизованные VCS, такие как CVS, SVN, Perforce, ClearCase,...) от DVCS (Распределенные VCS, например Git или Mercurial).
Они включают различные рабочие процессы и использование.

В частности, обмен данными между клиентом CVCS и его сервером будет более важным, чем с DVCS (которому действительно нужно дельта при нажатии или вытягивании всего репо)

Вот почему дельта очень важна для большинства операций в CVCS, что важно только для определенных операций и по разным причинам в DVCS.

Дельты описаны в книге Эрика Сник двумя книгами:

Репозиторий = Файловая система * Время

Дерево - это иерархия папок и файлов. Дельта - это разница между двумя деревьями. Теоретически эти два дерева не обязательно должны быть связаны. Однако на практике единственная причина, по которой мы вычисляем разницу между ними, состоит в том, что одна из них получена из другой. Некоторые разработчики начали с дерева N и сделали одно или несколько изменений, в результате чего дерево N + 1.

Мы можем думать о дельте как о наборе изменений. Фактически, многие инструменты SCM используют термин "набор изменений" именно для этой цели. Набор изменений - это просто список изменений, которые выражают разницу между двумя деревьями.

Значение дельта важно (см. этот поток): дельта треугольника или обратная дельта.

Некоторые инструменты SCM используют какой-то компромиссный дизайн. В одном подходе вместо хранения всего одного полного дерева и представления любого другого дерева в виде дельта мы покроем еще несколько полных деревьев на этом пути.

Вы можете увидеть эволюцию для "старого" VCS в Эрик Раймонд Понимание систем контроля версий.

Многие современные средства управления версиями используют двоичные дельта файлы для хранения хранилища.
Один популярный дельта-алгоритм файла называется vcdiff.
Он выводит список диапазонов байтов, которые были изменены. Это означает, что он может обрабатывать любые файлы, двоичные файлы или текст. В качестве вспомогательного преимущества алгоритм vcdiff сжимает данные одновременно.

Не забывайте, что управление треугольником также влияет на Directed Acyclic Graphs (DAGs), созданный для представления истории (см. Направление стрелок в книге ProGit "и неудобно позади DAG).

вы можете найти спецификацию о управлении треугольником для:

Veracity поддерживает два типа DAG:

  • Дерево DAG хранит историю версий структуры каталогов из файловой системы. Каждый node из DAG представляет одну версию всего дерева.

  • В базе данных (или "db" ) DAG хранится история версий базы данных или список записей. Каждый node DAG представляет одно состояние полной базы данных.

Эти последние точки иллюстрируют, что третье (четвертое?) поколение VCS должно иметь дело с распределением не только файлов (дерева), но и баз данных (для различных целей)