company_banner

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

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

    О статье


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

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


    Информация основана на последней главе Pro Git.

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

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

    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):
    Скрытый текст
    «...It's worth explaining (you are probably aware of it, but
    let me go through the basics anyway) how git delta-chains work, and how
    they are so different from most other systems.

    In other SCM's, a delta-chain is generally fixed. It might be "forwards"
    or "backwards", and it might evolve a bit as you work with the repository,
    but generally it's a chain of changes to a single file represented as some
    kind of single SCM entity. In CVS, it's obviously the *,v file, and a lot
    of other systems do rather similar things.

    Git also does delta-chains, but it does them a lot more "loosely". There
    is no fixed entity. Delta's are generated against any random other version
    that git deems to be a good delta candidate (with various fairly
    successful heursitics), and there are absolutely no hard grouping rules.

    This is generally a very good thing. It's good for various conceptual
    reasons (ie git internally never really even needs to care about the whole
    revision chain - it doesn't really think in terms of deltas at all), but
    it's also great because getting rid of the inflexible delta rules means
    that git doesn't have any problems at all with merging two files together,
    for example - there simply are no arbitrary *,v "revision files" that have
    some hidden meaning.

    It also means that the choice of deltas is a much more open-ended
    question. If you limit the delta chain to just one file, you really don't
    have a lot of choices on what to do about deltas, but in git, it really
    can be a totally different issue».


    Если кратко, то в 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
    Badoo
    436.46
    Big Dating
    Share post

    Comments 10

      +2
      Спасибо за полезную информацию. Никогда толком не мог понять, какой именно коммит принимается за Base, а информация на эту тему достаточно расплывчата.
        +6
        Не знал, что git делался как фреймворк. Это многое объясняет :) Мне кажется, что git цепляет людей именно своей гибкостью и низкоуровневостью. Мне иногда сложно объяснить людям почему стоит использовать git а не svn к примеру, но чисто субъективно после длительной работы с git-ом, все остальное кажется крайне неудобным, хотя вроде бы позволяет настроить вполне нормальный workflow, но чего-то всегда не хватает.
          +2
          Можно начать, например, с распределенности… Или, например, с того, что у git есть github и bitbucket, а у svn есть менее популярные (в силу меньшей дружественности) сервисы.

          А можно говорить, мол, используйте, а «что» и «почему» поймете потом сами.
            0
            Не знал, что git делался как фреймворк.

            Аналогично. После этих слов в статье даже зазудило где-то внутри: «ты должен создать свой, самый правильный VCS на основе этого фреймворка». К счастью, от этого зуда удалось избавиться.
              0
              К счастью, от этого зуда удалось избавиться.

              Расскажите, пожалуйста, как. Я пока не могу.
                0
                Волевым усилием. Тут главное — регулярная практика!
                  +3
                  Я тоже практикую подобную методику и, практически, достиг мастерства… Методика называется Ле Нь…

                  +1
                  • для разработки обёрток над git (и уж тем более git-based vcs) больше подходит libgit2, как бы говорят нам сотрудники Github
                  • git уже (давно) не фреймворк, а один здоровенный бинарник, как бы говорит нам find /usr/lib/git-core -lname git
              0
              А все же чем вас git-svn не устроил? Он ведь поддерживает ветвление. Да и работает достаточно шустро даже для больших svn-репозиториев. Я им конвертировал репозиторий с двенадцатилетней историей и все замечательно отработало.
                +3
                Я пришел на работу, когда от git svn уже почти ничего не осталось, но я постараюсь вам ответить то, что знаю :). Основная проблема с git-svn в том, что он является прослойкой между git и SVN, по сути являясь переносчиком коммитов между системами контроля версий. Вы должны иметь 2 системы контроля версий и понимать, что вы делаете, причём SVN является явно лишней и менее гибкой. Поскольку для поддержки ветвления всё равно нужно переписывать всю систему выкладки, мы переписали её, избавившись от SVN совсем (и от его «наследия» в виде отсутствия возможности ветвления). По сути, с новой системой необходимость в SVN полностью отпала, поэтому git-svn тоже был выпилен.

              Only users with full accounts can post comments. Log in, please.