Библиотека сайта rus-linux.net
Архитектура Mercurial
Глава 12 из книги "Архитектура приложений с открытым исходным кодом", том 1.
Оригинал: "Mercurial".
Автор: Dirkjan Ochtman
Дата публикации: 2012 г.
Перевод: Vlad http://vlad8.com/
Дата перевода: 2013 г.
Creative Commons. Перевод был сделан в соответствие с лицензией Creative Commons. С русским вариантом лицензии можно ознакомиться здесь.
Mercurial— это современная распределенная система контроля версий (VCS), написанная главным образом на Python и частично на C (там, где критична производительность). В данной главе я расскажу о некоторых решениях, которые были приняты при написании алгоритмов и структур данных Mercurial. Для начала позвольте мне вкратце описать историю систем контроля версий, чтобы было понятна обстановка, в которой появился Mercurial.
12.1. Краткая история контроля версий
Несмотря на то, что данный текст главным образом посвящен архитектуре Mercurial, многие описываемые в нем концепции схожи с другими системами контроля версий. Для плодотворного рассказа о Mercurial я бы хотел описать некоторые такие концепции, применяемые в других системах. Для создания общей перспективы я также приведу краткую историю этих программ.
Системы контроля версий были изобретены для помощи разработчикам в совместной работе над проектами без необходимости ручного отслеживания изменений в файлах и передачи полных копий проекта. В данном тексте я буду вести речь не об исходном коде проекта, а вообще произвольном файловом дереве. Одной из главных функций программ контроля версий является передача изменений в такое дерево. Обычный цикл работы при этом выглядит следующим образом:
- Получение самой последней версии cтруктуры файлов от кого-то.
- Работа над этой версией структуры, создание набора измененных файлов.
- Публикация этих изменений, чтобы другие могли их использовать.
Первое действие, получение файловой структуры, называется checkout. Хранилище, из которого мы получаем и куда отправляем наши изменения, называется репозиторий, а результат checkout’а называется рабочей директорией или рабочей копией. Обновление рабочей копии последними версиями файлов из репозитория называется просто апдейт; иногда при этом требуется слияние (merge), то есть совмещение изменений от разных пользователей в одном файле. Команда diff позволяет просмотреть различия между двумя версиями структуры или файла, обычно при этом проверяются локальные (неопубликованные) изменения в вашей рабочей копии. Изменения публикуются при помощи комманды commit, которая сохраняет изменения из рабочей директории в репозиторий.
12.1.1. Централизованный контроль версий
Первой системой контроля версий была Source Code Control System, SCCS, появившаяся в 1975 году. Она главным образом выполняла сохранение изменений между файлами кода в отдельные файлы, что было более эффективным, чем просто хранение копий, но не помогала в отправке этих изменений остальным участникам рабочего процесса.
В 1982 году ей на смену пришла Revision Control System, RCS, которая была более развитой и бесплатной альтернативой SCCS (и которая до сих пор поддерживается проектом GNU).
После RCS появилась CVS, Concurrent Versioning System, впервые вышедшая в 1986 году как набор скриптов для работы с файлами версий RCS в группах. Большим нововведением в CVS стало то, что в CVS несколько пользователей могут одновременно редактировать файл, а слияние изменений будет выполнено позже (одновременная правка). Появление такой возможности требовало обработки конфликтов редактирования. Разработчики могут отправлять в репозиторий новую версию какого-либо файла только, если она основана на последней доступной в репозитории версии этого файла. Если в репозитории и в моей рабочей копии есть различия, я должен устранить все конфликты между файлами в них (т.е. от правок, затрагивающих те же самые строки).
CVS также привнесла идею веток (branches), которые позволяют разработчикам работать параллельно над различными частями кода, и тэгов, которые дают возможность согласованного обозначения версий, что позволяет легко на нее ссылаться. Хотя изначально изменения в CVS передавались через репозиторий, расположенный на файловой системе с общим доступом, в какой-то момент в CVS была реализована клиент-серверная архитектура для использования в больших сетях (таких как Интернет).
В 2000 году три разработчика собрались вместе, чтобы написать новую систему контроля версий, лишенную некоторых существенных недостатков CVS. Ее окрестили Subversion. Одним из главных отличий новой системы стало то, что Subversion работает с целыми деревьями за один раз, это означает, что изменения в версиях должны быть атомарными, последовательными, изолированными и долговременными. Рабочие копии Subversion также сохраняют первоначальные копии полученных из репозитория изменений, поэтому обычная операция diff (сравнение локального дерева с исходным) выполняется очень быстро.
Одной из интересных концепций в Subversion стало то, что тэги и ветки являются частью дерева проекта. Проект в Subversion обычно разделен на три части: тэги, ветки и ствол (trunk). Это решение оказалось интуитивно понятным для пользователей, которые не были знакомы с системами контроля версий, хотя гибкость присущая данному дизайну принесла немало проблем для инструментов конвертации, потому что тэги и ветки имеют более структурированное представление в других системах.
Все вышеназванные системы являются централизованными; начиная с CVS, все они знают как обмениваться изменениями между собой, при этом они используют какой-то определенный компьютер, на котором отслеживается история изменений репозитория. Распределенная система контроля версий вместо этого хранит копию всей (или большей части) истории из репозитория на каждом компьютере, у которого есть его рабочая копия.
12.1.2. Распределенный контроль версий
Несмотря на то, что Subversion явно превосходила CVS, у нее все равно был ряд недостатков.
Прежде всего во всех централизованных системах контроля версий фиксирование изменений (операция commit) и их публикация по сути являются одним и тем же, так как история репозитория хранится централизованно в одном месте. Это означает, что отправка изменений без доступа к сети невозможна.
Во-вторых, доступ к репозиториям в централизованных системах всегда требует передачи данных по сети на сервер, что делает такие системы относительно медленными по сравнению с локальным доступом в распределенных системах.
В-третьих, описанные ранее системы имели определенные недостатки при отслеживании слияний (хотя в некоторых из них с тех пор их поддержка улучшилась). Для больших групп разработчиков, работающих одновременно, важно, чтобы система контроля версий записывала, какие изменения были включены в новые версии кода, чтобы ничего не потерялось и последующие слияния могли использовать эту информацию.
В-четвертых, централизация, которая требуется традиционным системами контроля версий, кажется искусственной и выдвигает требование наличие единого пространства для интеграции. Сторонники распределенных системых контроля версий утверждают, что распределенные системы позволяют более органично организовать работу: разработчики могут передавать и интегрировать изменения так, как того требует проект в каждый момент времени.
Для решения описанных выше проблем появилось несколько инструментов. С моей позиции (позиции open-source разработчика) самыми главными на 2011 год стали Git, Mercurial и Bazaar. Проекты Git и Mercurial были начаты в 2005 году, когда разработчики ядра Linux решили больше не использовать проприетарную систему BitKeeper. Обе были начаты разработчиками Linux (Линусом Торвальдсом и Мэттом Маколлом, соответственно) с целью создания систем контроля версий, которые могли бы работать с сотнями тысяч изменений в десятках тысяч файлов (например, с ядром Linux). И на Мэтта, и на Линуса оказала влияние Monotone VCS. Bazaar разрабатывалась отдельно, но стала широко использоваться примерно в это же время, так как была использована компанией Canonical для всех своих проектов.
Создание распределенной системы контроля версий, естественно, представляет определенные сложности, многие из которых присущи всем распределенным системам. Для начала, в то время как в централизованных системах на сервере всегда находилась каноническая версия истории изменений, в распределенных системах такой версии нет. Изменения могут фиксироваться параллельно, что делает невозможным сортировку изменений по времени в каждом отдельно взятом репозитории.
Практически повсеместно для решения этой проблемы используется направленный ациклический граф изменений (DAG) вместо линейного упорядочения (Рисунок 1). То есть добавленное и закоммиченное изменение кода является потомком той версии кода, на основе которой оно было сделано, и никакая версия не может зависеть от самой себя или своих потомков. В этой схеме у нас есть три специальных типа версий кода: корневая версия, которая не имеет предков (репозиторий может иметь несколько корней), объединяющая ревизия (у которой несколько предков) и главная версия, у которой нет потомков. Каждое хранилище начинается с пустой корневой версии кода и далее продолжается от нее по нескольким линиям изменений, заканчиваясь одной или несколькими главными версиями. Если два пользователя независимо друг от друга закоммитили свои изменения, и один их них хочет получить изменения кода от другого, то ему придется явно объединить изменения, внесенные другим пользователем, в новую версию, который он затем коммитит как объединяющую версию.
Рис.12.1: Направленный ациклический граф версий
Обратите внимание, что модель данного графа помогает решить некоторые проблемы, которые вызывают затруднения в централизованных системах: объединяющие версии используются для записи информации о вновь объединенных ветках графа. Получающийся в итоге граф может также полезно изображать большую группу параллельных веток, соединенных в меньшие группы, которые в конце концов будут соединены в одну специальную ветку, считающуюся канонической.
Этот подход требует, чтобы система отслеживала, что является предком каждого изменения в коде. Для облегчения обмена данными между изменениями, каждое из них обычно хранит информацию о своих предках, поэтому каждое изменение обычно имеет идентификатор. Хотя некоторые системы используют UUID или подобные схемы, Git и Mercurial предпочли SHA1-хэши содержимого. При этом дополнительным полезным свойством становится то, что ID может использоваться для верификации самого набора изменений. В действительности, так как информация о предках включается в захэшированные данные, вся история, идущая вплоть до любой версии, может быть проконтролирована при помощи ее хэша. Имена авторов, сообщения при коммите изменений, временные метки и другие метаданные хэшируются также, как и само содержимое файлов новой версии, поэтому они также могут быть верифицированы. А так как временные метки записываются во время фиксации, они также не обязательно идут друг за другом в каждом конкретном репозитории.
Все это может быть довольно сложным для людей, которые прежде пользовались только централизованными VCS: нет одного целого числа для обозначения версии, только 40-символьная шестнадцатиричная строка. Кроме того, больше нет глобальной сортировки, только локальная; вместо глобальной линейной сортировки есть только направленный упорядоченный граф. Случайное создание нового направления разработки при отправке изменения в родительскую версию, у которой уже есть одно направление-потомок, может приводить в недоумение, если вы привыкли получать предупреждение от системы контроля версий, когда подобная ситуация происходила раньше.
К счастью, существуют инструменты для помощи в визуализации дерева, и Mercurial предоставляет возможность использования коротких версий хэша, а также чисел для идентификации локальных изменений. В последнем случае используется увеличивающееся целое число, которое отображает порядок, в котором изменения были добавлены в копию. Так как данный порядок может быть различным от копии к копии, его нельзя использовать в нелокальных операциях.
Продолжение статьи: Структуры данных.