Архітектура Mercurial

Creative Commons. Переклад був зроблений у відповідність до ліцензії Creative Commons. З українським варіантом ліцензії можна ознайомитись тут.

Mercurial - це сучасна розподілена система контролю версій (VCS), написана головним чином на Python і частково на C (там, де критична продуктивність). У цьому розділі я розповім про деякі рішення, які були прийняті при написанні алгоритмів та структур даних Mercurial. Спочатку дозвольте мені коротко описати історію систем контролю версій, щоб було зрозуміло обстановка, в якій з'явився Mercurial.

12.1. Коротка історія контролю версій

Незважаючи на те, що цей текст переважно присвячений архітектурі Mercurial, багато описуваних у ньому концепції схожі на інші системи контролю версій. Для плідної розповіді про Mercurial я хотів би описати деякі такі концепції, що застосовуються в інших системах. Для створення спільної перспективи я наведу коротку історію цих програм.

Системи контролю версій були винайдені для допомоги розробникам у роботі над проектами без необхідності ручного відстеження змін у файлах і передачі повних копій проекту. У даному тексті я вестиму мову не про вихідний код проекту, а взагалі довільне файлове дерево. Однією з головних функцій програм контролю версій є передача змін такого дерева. Звичайний цикл роботи при цьому виглядає так:

Отримання останньої версії структури файлів від когось.
Робота над цією версією структури, створення набору змінених файлів.
Публікація цих змін, щоб інші могли їх використати.

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: Спрямований ациклічний граф версій

Зверніть увагу, що модель даного графа допомагає вирішити деякі проблеми, які викликають складнощі у централізованих системах:версії, що об'єднують, використовуються для запису інформації про знову об'єднані гілки графа. Граф, що виходить в результаті, може також корисно зображати велику групу паралельних гілок, з'єднаних в менші групи, які врешті-решт будуть з'єднані в одну спеціальну гілку, що вважається канонічної.

Все це може бути досить складним для людей, які насамперед користувалися лише централізованими VCS: немає одного цілого числа для позначення версії, лише 40-символьний шістнадцятирічний рядок. Крім того, більше немає глобального сортування, лише локальне; замість глобального лінійного сортування є лише спрямований упорядкований граф. Випадкове створення нового напрямку розробки при відправленні зміни до батьківської версії, яка вже має один напрямок-нащадок, може здивувати, якщо ви звикли отримувати попередження від системи контролю версій, коли подібна ситуація відбувалася раніше.

На щастя, існують інструменти для підтримки візуалізації дерева, і Mercurial надає можливість використання коротких версій хеша, а також чисел для ідентифікації локальних змін. В останньому випадку використовується ціле число, що збільшується, яке відображає порядок, в якому зміни були додані в копію. Оскільки цей порядок може бути різним від копії до копії, його не можна використовувати у нелокальних операціях.