Внутреннее устройство Git: хранение данных и merge

В процессе перехода с SVN на Git мы столкнулись с необходимостью переписывания наших внутренних инструментов, связанных с развёртыванием кода, которые ориентировались на существование линейной истории правок (и разработку в trunk). На Хабре уже публиковались возможные решения этой проблемы через Git-SVN, но мы пошли другим путём. Нам нужна поддержка таких возможностей Git, как branching и merge, поэтому мы решили разобраться в основах, как же работает Git и каким способом должна осуществляться интеграция с ним.

О статье

Материал ориентирован прежде всего на читателей, умеющих работать с Git на уровне обычного пользователя и знающих основные концепции работы с ним. Возможно, статья не будет содержать ничего нового для разработчиков систем контроля версий, поддерживающих легкое создание веток и их надежное слияние. Вся информация взята из открытых источников, в том числе из исходных текстов Git (2d242fb3fc19fc9ba046accdd9210be8b9913f64).

Хранение данных: объекты

Информация основана на последней главе Pro Git (http://git-scm.com/book/en/Git-Internals).

В Git единицей хранения данных является объект (англ. object), который однозначно определяется 40-символьным хешем sha1. В объектах Git хранит почти всё: коммиты, содержимое файлов, их иерархию. Сначала объекты представляют из себя обычные файлы в папке .git/objects, а после git gc упаковываются в .pack-файлы, о которых будет рассказано чуть ниже. Для экономии дискового пространства содержимое всех объектов дополнительно сжимается с помощью zlib.

Узнать тип объекта можно, набрав git cat-file -t <sha1>. Основные типы объектов:

BLOB (содержимое файла).

В объектах типа BLOB содержится длина содержимого файла и само содержимое. Ничего больше: ни имени файла, ни прав доступа там нет.

Из того, что в BLOB складывается содержимое файла целиком, а не дифф, вытекает много следствий. Например, если у нас есть большой файл на 100 000 строк и в него вносятся небольшие изменения, мы получим копии этого файла в репозитории:

$ git init
Initialized empty Git repository in test/.git/
$ for((i=0;i<=100000;i++)); do echo $i; done >test.txt
$ ls -lh
575K	test.txt
$ git add test.txt
$ git commit -m "First commit"
[master (root-commit) b3061d2] First commit
 1 file changed, 100001 insertions(+)
 create mode 100644 test.txt
$ find .git/objects -type f | xargs ls -lh
204K	.git/objects/97/578648a76227f183339438512ad99a383b48cc # наш файл
...
$ echo 10001 >> test.txt
$ git commit -m "Added another line" test.txt
[master 0361e3c] Added another line
 1 file changed, 1 insertion(+)  # Git говорит, что добавилась 1 строка
$ find .git/objects -type f | xargs ls -lh
204K	.git/objects/59/e434385635dccf949e66353f7a74a077357438 # новая версия
204K	.git/objects/97/578648a76227f183339438512ad99a383b48cc # наш старый файл
...

Также хранение объектов целиком позволяет делать надежное слияние веток с разрешением конфликтов. Но об этом чуть позже.

Tree (иерархия ФС)

объекте типа дерево (англ. tree) хранится список записей, который соответствует иерархии файловой системы. Одна запись представляет из себя следующее:

<права файла> <тип объекта> <sha1 объекта> <имя файла>

Права файла в Git могут иметь лишь очень ограниченный набор значений:

040000 — директория;
100644 — обычный файл;
100755 — файл с правами исполнения;
120000 — символическая ссылка.

Тип объекта — это BLOB или tree, для файла и директории соответственно. То есть в объекте типа tree для корневой директории хранится вся иерархия файловой системы, поскольку внутри одного дерева могут быть ссылки на другие деревья.

Commit

В Git один коммит (англ. сommit) представляет из себя ссылку на объект tree, соответствующий корневой директории, и ссылку на родительский коммит (кроме самого первого коммита в репозитории). Также в коммите есть информация об авторе и UNIX timestamp от времени создания.

Если коммит является простым merge (git merge <имя ветки>), то у него будет 2 родителя: текущий HEAD и коммит, на который указывает <имя ветки>. Git также поддерживает стратегию слияния «осьминог» (англ. octopus), при котором он может выполнять merge более двух веток. Для таких коммитов количество родителей будет больше двух.

$ git cat-file -p 0361e3c6d16fb3bbbcac8faa4e673667ea6fe20b
tree ce9f2ced0ebb4346676879c7b12b92628378477f
parent b3061d23da6f1a62dbc8f97b2a06e10e1aee2afa
author Yuriy Nasretdinov <...> 1354450065 +0400
committer Yuriy Nasretdinov <...> 1354450065 +0400

Added another line

Pack-файлы

Если бы Git действительно хранил все объекты целиком (хоть и сжатые), папка .git представляла бы из себя огромный набор файлов, причем их бы было гораздо больше, чем в рабочей копии. Тем не менее этого не происходит, а появляются загадочные pack-файлы, в которые упакованы объекты. Как ни странно, но в интернете мало информации о том, как Git хранит данные в этих файлах, поэтому приведем отрывок из электронного письма Линуса Торвальдса, в котором дается некоторое пояснение насчёт этих загадочных файлов (источник: gcc.gnu.org/ml/gcc/2007-12/msg00165.html):

Если кратко, то в pack-файлах объекты группируются по схожести (например, тип и размер), после чего они сохраняются в виде «цепочек». Первый элемент цепочки представляет из себя самую новую версию объекта, а следующий за ним являются диффом к предыдущему. Самые новые версии объекта считаются наиболее запрашиваемыми, поэтому они хранятся выше в цепочке.

Таким образом, Git всё же хранит диффы, но только на уровне непосредственного хранения данных. С точки зрения любого API уровнем выше, Git оперирует объектами целиком, что позволяет реализовывать различные стратегии слияния и легко разрешать конфликты.

Хранение истории

В Git нет отдельного хранилища истории. Всю историю можно развернуть, но лишь пройдя по ссылкам на родителя из нужного вам коммита. Если необходимо просмотреть историю только по одному файлу (или по поддиректории), Git всё равно должен проделать то же самое, но он будет возвращать отфильтрованные результаты. Стоит иметь это ввиду, когда вы делаете интеграцию с Git, и не заставлять Git делать полный просмотр истории на каждый файл.

К тому же, как вы могли заметить, Git не хранит информацию о переименовании файлов. Если нужно понять, переименован файл или нет, Git произвдит анализ содержимого хранящихся у него объектов и с некоторым (настраиваемым) допуском считает, что файл был переименован.

Merge: трехстороннее слияние (стратегия resolve)

Если нужно выполнить слияние двух веток, то git по умолчанию использует стратегию recursive, но о ней чуть позже. До того, как появилась эта стратегия, использовалась стратегия resolve, которая представляет из себя трехстороннее слияние. Для того, чтобы выполнить такое слияние, нужно иметь 3 версии: общий родитель, версия из одной ветки и версия из другой ветки. Если вы выполняете слияние файлов, то такое трехсторонее слияние может выполняться утилитой diff3, которая входит в стандартный пакет diffutils. Эта скромная и редко упоминаемая утилита, так или иначе, делает всю «грязную работу» по слиянию в большинстве существующих систем контроля версий, включая RCS, CVS, SVN и, конечно же, Git.

Помимо использования аналога diff3 (конкретная реализация, используемая в Git — это LibXDiff), Git также «на лету» вычисляет переименования файлов и использует эту информацию для слияния tree-объектов. Слияние иерархий директорий не представляет из себя ничего принципиально сложного по сравнению с тем, чтобы выполнить слияние файлов, но порождает очень много различных видов конфликтов.

Небольшая иллюстрация того, как Git выполняет трехстороннее слияние в простом случае (взято из man git-merge):

Предположим, у нас есть такая история и текущая ветка — master:

      A---B---C topic
     /
D---E---F---G master

Тогда git merge topic повторит изменения, сделанные в topic начиная с коммита, когда история разветвилась (коммит E), и создаст новый коммит H, у которого будет два родителя, и сообщение коммита, которое предоставит пользователь.

      A---B---C topic
     /         
D---E---F---G---H master

Тем не менее разработка в ветках topic и master может быть продолжена, и тогда слияние уже не будет выглядеть так просто: у нас может быть больше, чем один коммит, который подходит под определение «общий предок»:

      A---B---C---K---L---M topic
     /         
D---E---F---G---H---N---O---P master

Если мы будем использовать стратегию resolve, то будет выбран самый старый общий предок (коммит E). Если в результате выполнения merge были конфликты, разрешённые в коммите H, нам всё равно нужно будет разрешать их ещё раз.

Для выполнения слияния с помощью стратегии resolve Git возьмет коммит E в качестве общего предка и коммиты M и P в качестве двух новых версий. Если в коммите C был конфликт, то конфликтующие изменения можно откатить с помощью git revert (например, это проделано в коммите K), тогда конечное состояние M уже не будет содержать в себе конфликта, и при слиянии конфликтов тоже не будет.

Merge made by the 'recursive' strategy

Представим себе такую историю:

      A---B---C---K---L---M topic
     /              /
D---E---F---G---H---N---O---P master

Теперь нам нужно выполнить git merge topic, находясь в ветке master. Мы могли бы выбрать коммит E как общего предка, но Git со стратегией recursive делает иначе. В интернете можно найти одну хорошую статью, которая достаточно подробно описывает эту стратегию: codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html. В статье описан алгоритм, который сводится к следующему:

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

Результатом выполнения этой операции будет виртуальный коммит, который представляет из себя «смерженное» состояние всех общих предков в правильном порядке — разрешение конфликтов тоже попадет в этот коммит, причем более свежие коммиты будут иметь приоритет. Когда мы получили общего предка, выполняется трехсторонее слияние, описанное выше.

Выдержка из merge-recursive.c:

int merge_recursive(...) {
<...>
	if (!ca) {
		ca = get_merge_bases(h1, h2, 1);
		ca = reverse_commit_list(ca);
	}
<...>
	merged_common_ancestors = pop_commit(&ca);
<...>
	for (iter = ca; iter; iter = iter->next) {
<...>
		merge_recursive(o, merged_common_ancestors, iter->item,
				NULL, &merged_common_ancestors);
<…>
	}
<...>
	clean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree, &mrtree);
<...>
	return clean;
}

Низкоуровневые команды Git

Если вы работали какое-то время с Git, то вы наверняка знаете о командах checkout, branch, pull, push, rebase, commit и некоторых других. Но изначально Git создавался не как полноценная система контроля версий, а как фреймворк для её создания. Поэтому в Git есть очень богатый набор встроенных команд, которые работают на низком уровне. Приведем некоторые из них, весьма полезные, на наш взгляд:

git rev-parse <revision>

Эта команда является очень простой: она возвращает хеш коммита для указанной ревизии. Например, git rev-parse HEAD вернет хеш коммита, на который указывает HEAD.

git rev-list <commit>...

Команда выводит список хешей коммитов по указанному запросу и может использоваться как более быстрая альтернатива git log. Например, git rev-list branch ^origin/branch ^origin/master выведет все коммиты из ветки branch, которые ещё не были запушены (при условии, что origin/branch и origin/master являются свежими, например перед этим был сделан git fetch).

Подводные камни: Что касается запросов вида branch ^other_branch, Git может неправильно вывести результаты, если у коммитов стоит неправильное время. Например, в выводе могут быть пропущены коммиты, которые «произошли в будущем» по сравнению с merge ветки.

git diff-index

Показывает разницу между рабочей копией и индексом (.git/index). В индексе Git хранит кеш lstat() от всех файлов, о которых он знает.

Подводные камни: если перенести файлы с одного сервера на другой (или сделать копию папки), то git diff-index покажет множество изменений, хотя их на самом деле нет. Это связано именно с тем, что в .git/index хранятся почти все поля lstat, включая inode, а содержимое файлов diff-index не анализирует. Поэтому нужно дополнительно делать git update-index, или использовать обычный git diff, который делает это автоматически. Подробнее о .git/index: www.kernel.org/pub/software/scm/git/docs/v1.6.5/technical/racy-git.txt

git cat-file <object>

Эта команда уже встречалась в статье, но её всё же стоит упомянуть ещё раз. Она позволяет получить содержимое коммита и любого другого объекта Git.

git ls-tree <object>

Выводит содержимое tree-объекта в приемлемом виде.

git ls-remote <repository>

Выводит информацию о ветках и тегах (вместе с хешами коммитов) из указанного удаленного репозитория.

GIT_SSH

Если вы писали скрипты, которые делают git pull, то скорее всего сталкивались с тем, что SSH запрашивает подтверждение «аутентичности» удаленного репозитория, причём делает это интерактивно. Решение этой проблемы не столь изящное, потому что GIT_SSH должен быть путем к исполняемому файлу (а не опции SSH):

echo '#!/bin/sh
exec ssh -o BatchMode=yes -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null "$@"' >/tmp/gitssh;
chmod +x /tmp/gitssh;
# делаем git pull:
GIT_SSH=/tmp/gitssh git pull …

Заключение

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

Надеемся, данный материал оказался интересным для вас и позволил понять, почему Git работает именно так, а не иначе. Полагаем, что статья будет также полезной для разработчиков различных интерфейсов к Git, приводя к более глубокому пониманию того, что же происходит «под капотом».

Юрий Насретдинов, разработчик Badoo

Автор: youROCK

Источник