В этой статье мы расскажем о том, как GitLab выявил и устранил «бутылочное горлышко» производительности в 15-летней функции Git, что повысило эффективность, обеспечив возможность применения более надёжных стратегий резервного копирования и снижения рисков.

Резервные копии репозиториев — важнейший компонент надёжной любой стратегии восстановления после сбоев. Однако с увеличением размеров репозиториев процесс создания надёжных бэкапов становится всё сложнее. Для резервного копирования нашего собственного репозитория Rails нам требовалось 48 часов. Это заставило нас искать невозможные компромиссы между частотой резервного копирования и производительностью системы. Мы хотели найти собственное внутреннее решение для наших клиентов и пользователей.

В конечном итоге, мы нашли источник проблемы в 15-летней функции Git со сложностью O(N²) и устранили его, внеся изменения в алгоритм, что экспоненциально уменьшило время резервного копирования. В результате мы обеспечили снижение затрат, уменьшение рисков и возможность создания стратегий резервного копирования, которые хорошо масштабируются месте с нашей кодовой базой.

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

Резервное копирование в крупных масштабах

Для начала давайте разберёмся в нашей проблеме. В процессе роста организаций их репозитории и резервные копии становятся всё более сложными. При этом они могут столкнуться со следующими трудностями:

• Длительные процессы бэкапа: создание резервной копии крупного репозитория может занимать до нескольких часов, из-за чего планирование регулярных бэкапов становится проблематичным.

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

• Окна резервного копирования: для команд, чьи рабочие процессы происходят в режиме 24/7, такие длительные операции усложняют поиск подходящих окон технического обслуживания.

• Повышение риска сбоев: длительные процессы больше подвержены прерываниям, вызванным сетевыми проблемами, перезапуском серверов и системными ошибками. Это может вынудить команды заново перезапускать весь очень долгий процесс резервного копирования.

• Состояния гонки: так как для создания бэкапа требуется много времени, репозиторий за этот период может сильно измениться, что потенциально может создать недопустимый бэкап или прервать процесс резервного копирования из-за отсутствия требуемых объектов.

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

Теперь давайте поговорим о том, как мы выявили узкое место производительности, нашли решение и развернули его, чтобы снизить время создания бэкапов.

Технические трудности

В основе функциональности резервного копирования репозиториев GitLab лежит команда git bundle create, создающая полный снэпшот репозитория, в том числе всех объектов и ссылок (веток и тэгов). Этот бандл используется как точка восстановления для воссоздания точной копии состояния репозитория.

Однако реализация этой команды была несовершенной из-за плохой масштабируемости, связанной с подсчётом ссылок, что создавало «бутылочное горлышко» производительности. С накапливанием в репозиториях количества ссылок время обработки возрастало экспоненциально. Самые большие наши репозитории содержат миллионы ссылок, поэтому операции резервного копирования растягивались на 48 с лишним часов.

Анализ первопричин

Чтобы выявить первопричину этого узкого места, мы проанализировали flame-график команды во время её выполнения.

На flame-графике показан путь выполнения кода программы через трассировку её стека. Каждая строка соответствует функции кода, а ширина строки определяет, сколько времени команда потратила на выполнение внутри этой функции.

При изучении flame-графика команды git bundle create, запущенной для репозитория с 10 тысячами ссылок, оказалось, что приблизительно 80% времени выполнения потребляла функция object_array_remove_duplicates(). Эта функция была добавлена в Git в коммите b2a6d1c686 («bundle: allow the same ref to be given more than once, 2009-01-17»).

Чтобы понять это изменение, важно знать, что git bundle create позволяет пользователем указывать, какие ссылки будут включены в бандл. Для полных бандлов репозиториев флаг --all упаковывает все ссылки.

Коммит решал проблему, возникавшую, когда пользователи указывали в командной строке дублирующиеся ссылки. Например, git bundle create main.bundle main main создаст бандл без правильной обработки дублированной ссылки на main. При развёртывании этого бандла в репозитории Git он может поломаться, потому что попытается выполнить запись одной и той же ссылки дважды. Код, позволяющий избежать дублирования, использует вложенные циклы for для итеративного обхода всех ссылок и выявления дубликатов. Этот алгоритм O(N²) стал серьёзным узким местом производительности в репозиториях с большим количеством ссылок, занимая большую долю времени обработки.

Решение: от O(N²) к эффективному mapping

Для устранения этой проблемы производительности мы внесли в Git upstream-исправление, заменяющее вложенные циклы структурой данных map. В map добавляется каждая ссылка, и это гарантирует, что для обработки останется только одна копия каждой ссылки.

Это изменение существенно повысило производительность git bundle create и обеспечило гораздо более высокую масштабируемость в репозиториях с большим количеством ссылок. Тестирование бенчмарка репозитория с 10 тысячами ссылок продемонстрировало повышение производительности в шесть раз.

Benchmark 1: bundle (refcount = 100000, revision = master)
  Time (mean ± σ): 	14.653 s ±  0.203 s	[User: 13.940 s, System: 0.762 s]
  Range (min … max):   14.237 s … 14.920 s	10 runs

Benchmark 2: bundle (refcount = 100000, revision = HEAD)
  Time (mean ± σ):  	2.394 s ±  0.023 s	[User: 1.684 s, System: 0.798 s]
  Range (min … max):	2.364 s …  2.425 s	10 runs

Summary
  bundle (refcount = 100000, revision = HEAD) ran
	6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)

Патч был принят и смерджен в upstream Git. Внутри GitLab мы сразу выполнили обратное портирование исправления, чтобы наши клиенты могли воспользоваться им, не ожидая следующего релиза Git.

Результат: значительное снижение времени создания бэкапов

Рост производительности, вызванный этим улучшением, вполне можно назвать революционным:

• С 48 часов до 41 минуты: создание бэкапа самого нашего крупного репозитория (gitlab-org/gitlab) теперь занимает всего 1,4% от изначального времени.

• Стабильная производительность: это улучшение надёжно масштабируется для репозиториев любого размера.

• Эффективное использование ресурсов: мы существенно снизили нагрузку на серверы во время операций резервного копирования.

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

Что это значит для клиентов GitLab

Это улучшение приносит непосредственные и осязаемые преимущества в планировании резервного копирования репозиториев и восстановления после аварий:

• Более совершенные стратегии создания бэкапов

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

  • Теперь команды могут беспроблемно выполнять запланированное резервное копирование по ночам без необходимости длительных выделенных процессов.

• Повышение бесперебойности работы

  • Благодаря тому, что время создания бэкапов сократилось с дней до минут, организации существенно минимизировали их recovery point objective (RPO). Это приводит к снижению рисков для бизнеса — в случае аварий клиентам потенциально нужно будет восстанавливать работу за считанные часы, а не за дни.

• Снижение эксплуатационных затрат

  • Сниженное потребление ресурсов серверов и уменьшение окон технического обслуживания.

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

• Инфраструктура, обеспечивающая возможность будущего роста

  • Рост объёмов репозиториев теперь не заставляет делать сложный выбор между частотой создания бэкапов и производительностью системы.

  • С расширением кодовой базы может параллельно масштабироваться и стратегия резервного копирования.

Теперь организации могут внедрять более надёжные стратегии резервного копирования без ущерба для производительности или полноты бэкапов. То, что когда-то было сложным поиском компромисса, становится простой эксплуатационной практикой.

Начиная с релиза GitLab 18.0 все клиенты GitLab, вне зависимости от уровня лицензии, могут использовать эти преимущества для планирования и реализации своей стратегии резервного копирования. Дополнительных изменений в конфигурации не требуется.