Привет, Хабр! Меня зовут Владимир Бобров, я разработчик в Yandex Infrastructure. Занимаюсь навигацией и поиском по коду на нашей платформе для полного цикла разработки IT-продуктов — SourceCraft.
Все мы сталкивались с классическими алгоритмами на курсах, олимпиадах или собеседованиях и, куда более редко, на практике. Но даже в реальной разработке возникают ситуации, когда готового решения нет, а простое не подходит.
Сегодня расскажу как раз о такой задаче, над которой работала наша команда, — поиск по коду относительно произвольного коммита. Покажу, как много вариантов мы перебрали, что в итоге выбрали и почему.
Зачем нужен поиск по коду относительно произвольного коммита
Сначала немного разберёмся, как работает наша платформа. SourceCraft предназначен для работы с Git-репозиториями. Чтобы было удобно читать код прямо из браузера, мы добавили некоторые IDE-функции:
полнотекстовый поиск по коду;
go to declaration;
find usages;
quick info.
Важно, что навигация работает не только при просмотре файлов с кодом, но и в процессе код-ревью, в контексте конкретных PR (pull requests). Это означает, что отвечать на запросы нужно не для одного состояния репозитория, а для целого множества, то есть для разных коммитов.
Кроме того, это множество не ограничивается последними коммитами веток репозитория. Например, PR может состоять из нескольких итераций, и для каждой нужна навигация. А бывает и так: пока разработчик читает код, в репозитории происходят изменения, и просматриваемая им версия перестаёт быть актуальной, но навигация по ней должна всё так же работать.
Ещё один важный момент: функции навигации по коду и поиска по коду тесно взаимосвязаны. Чтобы пользоваться навигацией было комфортно, она должна быть отзывчивой, что оказывается невозможным без очень быстрого текстового поиска по коду. Значит, скоростной текстовый поиск — фактическая необходимость, и простые решения этой задачи могут нам не подойти.
Почему без текстового поиска для работы навигации для того же коммита не обойтись, рассказывала моя коллега Ольга Лукьянова, а подробнее о навигации написал другой мой коллега Павел Таланов. Я же сконцентрируюсь именно на задаче полнотекстового поиска.
Какую задачу мы решали
История репозитория в Git является ориентированным ациклическим графом, где вершины — коммиты. Обычно мы думаем о коммите как о наборе изменений, но можно сказать точнее: коммит задаёт конкретное состояние репозитория, то есть набор файлов в определённых версиях.
Получается, наша задача звучала так: для Git-репозитория нужно построить индекс, который по хешу любого коммита умеет находить вхождения искомой строки в файлах этого коммита.
Чтобы сравнивать и оценивать разные решения, мы выделили три характеристики:
Скорость поиска — самый важный аспект. Чтобы пользоваться навигацией было комфортно, поиск должен быть практически моментальным.
Скорость индексации. Прежде чем искать, нужно проиндексировать коммит — этот процесс не должен занимать много времени.
Размер индекса. Чем больше индекс, тем дороже его хранить.
От чего мы отталкивались
Редкая разработка начинается с нуля. И у нас тоже уже была готовая технология — сервис CodeSearch, который основан на триграммном индексе и предназначен для быстрого поиска по большим объёмам кода.
Однако CodeSearch позволял осуществлять поиск только по одной, текущей версии кодовой базы, а значит, нам предстояло научить его искать более чем по одному состоянию репозитория. Далее я расскажу о тех вариантах, между которыми нам пришлось выбирать, и чем мы руководствовались при поиске и сравнении.
Подход №0. Наивное решение
Первое, что сразу приходит в голову, — просто перебрать все файлы во всех коммитах, построить по индексу для каждого отдельного коммита (как если бы это были разные репозитории). А затем осуществлять поиск по нужному индексу для каждого конкретного запроса. Для маленьких репозиториев такое решение действительно сработает: скорость поиска будет нормальной.
Проблема в том, что с ростом репозитория будут расти и размер индекса, и время на индексацию: примерно пропорционально произведению числа коммитов на число файлов в репозитории. Даже для репозитория с несколькими тысячами файлов и коммитов размер индекса составит гигабайты, что уже очень много.
Подход №1. Дельты и снапшоты
Попробуем улучшить описанное выше решение. Ключевое наблюдение: два соседних коммита (с точки зрения графа) отличаются друг от друга не сильно, то есть основная часть файлов в них одинаковая. Это наводит нас на мысль: вместо того чтобы индексировать каждый коммит целиком, проиндексируем только дельту — набор изменившихся файлов. А чтобы получить итог поиска, объединим результаты для предыдущего коммита и для дельты, при этом исключим удалённые или модифицированные между коммитами файлы.
В целом так же можно поступить со всеми коммитами и получить набор индексов для дельт. Но возникает проблема: поиск по отдельным дельтам и объединение результатов занимает огромное количество времени, если репозиторий большой.
Попробуем найти золотую середину: в графе коммитов выбираем несколько вершин и строим для них снапшоты — полные индексы соответствующих состояний репозитория. Для остальных вершин строится индекс дельты до одного из соседних коммитов. Дельты выбираются так, чтобы по цепочке из них можно было добраться до какого-либо из снапшотов от любого коммита. Время поиска в этом случае примерно пропорционально длине цепочки.
Это решение лучше предыдущего, но у него всё ещё есть минусы.
Допустим, мы хотим сделать время поиска предсказуемым и ограничиваем длину цепочки фиксированной величиной. Тогда число снапшотов становится в худшем случае линейно зависящим от числа коммитов, ведь, например, для репозитория с линейной историей каждый снапшот может покрыть не более 2 × T + 1 коммитов, где T — допустимая длина цепочки дельт. Значит, потребуется не менее N / (2 × T + 1) снапшотов, где N — число коммитов в репозитории. Размер индекса снова растёт квадратично, хоть и почти в (2 × T + 1) раз меньше, чем в предыдущем подходе.
Если регулировать значение T, можно искать компромисс между размером индекса и временем поиска. Но остаётся и ряд проблем, и самая важная из них — дублирование файлов в индексе.
Полный поиск с фильтрацией результатов
На этом этапе мы хотим решить проблему дублирования и построить индекс, в котором каждая версия каждого файла будет встречаться примерно один раз. Чтобы понять, как это сделать, предлагаю погрузиться в процесс текстового поиска в CodeSearch:
Определяется список файлов-кандидатов, которые могут содержать искомую строку.
Файлы отфильтровываются в соответствии с некоторым набором эвристик.
Для каждого из оставшихся кандидатов происходит точная (сравнительно длительная) проверка наличия искомой строки.
Эта схема подсказывает новый подход к поиску: вместо того чтобы создавать несколько отдельных индексов, построим один общий со всеми версиями всех файлов, этот индекс будет рассматриваться как основной. А к нему добавим дополнительный индекс, который позволит отфильтровывать результаты поиска.
Почему это может сработать? Поскольку фильтрация происходит ещё до финальной проверки, даже большое число ошибочных кандидатов (например, других версий файла) можно отсеять за приемлемое время, но саму проверку необходимо сделать достаточно быстрой.
Дерево коммитов
Чтобы понять, нужно ли отфильтровывать найденную версию файла, необходимо сопоставить её с графом коммитов. Но граф может быть устроен сложно, поэтому предварительно упростим его до дерева. Для большинства случаев это то же самое, что выделить остовное дерево:
Если у коммита несколько родителей — выберем одного. Например, того, с кем у него меньше всего различий (минимальная по числу файлов дельта).
Для коммитов без родителей заведём общий виртуальный «пустой» коммит и назначим его родителем.
Назовём такую структуру деревом коммитов.
Как это работает
Теперь каждому реальному коммиту однозначно соответствует родитель и, как следствие, набор изменённых в нём файлов — дельта между коммитом и его родителем (удаление и добавление тоже считаем изменениями). Поскольку коммиты в Git не удаляются и не модифицируются, мы можем строить дерево инкрементально, запуская при каждой итерации индексации обход графа из вершин, соответствующих веткам репозитория.
Индексация очередного коммита выглядит просто: добавляем в индекс изменённые файлы и помечаем, что они появились именно в этом коммите. Так как каждый файл из любого коммита возникает (в соответствующей версии) в каком-то из его предков, можно говорить о коммите появления файла и называть его состоянием файла.
Что дальше
Процесс поиска всегда происходит относительно одного конкретного коммита (далее обозначим его как B). При этом на вход к фильтру поступают файлы-кандидаты, и для каждого из них (из основного индекса) известны имя (здесь и далее — включая путь) A и коммит появления C.
Тогда для осуществления фильтрации необходимо научиться, например, для заданных имени файла и коммита определять состояние этого файла. Или же (что является более простой задачей) научиться отвечать на подобные вопросы: «Верно ли, что файл с именем A в коммите B находится в состоянии C?».
Подход №2. Индекс коммитов через снапшоты и дельты
Всё, что нам осталось, — определить устройство индекса, который сможет отвечать на один из описанных выше вопросов.
Хранить содержимое всех коммитов, как в подходе №0, мы уже не хотим, поэтому сразу возьмём за основу идею дельт и снапшотов. Для коммитов, которые мы выбрали как снапшоты, храним полные метаданные: имена всех файлов и их состояния (по хешу). Для остальных коммитов храним только дельту — имена и состояния файлов, изменившихся относительно родителя.
Тогда, переходя по рёбрам дерева к родительским коммитам, для любого коммита и файла мы сможем определить (в худшем случае — дойдя до снапшота) его состояние. Конечно, чтобы такой подход работал эффективно, нужен подходящий алгоритм расстановки снапшотов. При этом желательно, чтобы он удовлетворял следующим требованиям:
не больше T переходов от любого коммита до снапшота для предсказуемого времени поиска;
снапшоты должны строиться инкрементально: при появлении новых коммитов хочется избежать перемещений уже построенных снапшотов, чтобы не замедлять индексацию;
число снапшотов должно быть близким к минимальному, чтобы сократить размер индекса и время индексации.
Оказывается, такой алгоритм существует, и вот как он выглядит:
Первый снапшот поставим в виртуальном начальном коммите.
Для каждого коммита будем поддерживать информацию о значении расстояния до ближайшего снапшота. В частности, при добавлении нового коммита без построений снапшотов искомое значение для него ровно на единицу больше, чем уже известное для родителя.
При появлении коммита на расстоянии T + 1 от ближайшего снапшота сделаем (округлённое вниз) T / 2 шагов «назад», то есть к корню дерева, и добавим снапшот в этом месте. Затем пересчитаем расстояния до снапшотов для всех коммитов.
Выполнение первых двух требований очевидно по построению. Для последнего пункта воспользуемся следующим рассуждением. Мысленно раскрасим все вершины в два цвета: в красный (вершины с расстоянием до ближайшего снапшота ≤ T / 2) и в синий — те, для которых это расстояние больше T / 2.
Тогда, с одной стороны, вершина, ставшая красной, никогда не меняет свой цвет, с другой — постановка снапшота всегда приводит к тому, что как минимум T / 2 синих вершин становятся красными. Таким образом, число снапшотов не превосходит N / (T / 2), что всего лишь примерно вдвое хуже, чем оптимальное число снапшотов для неудачных случаев репозиториев из N коммитов. Например, для линейного репозитория потребуется не менее чем примерно N / T снапшотов.
Плюсы и минусы
Решение получилось заметно лучше предыдущих: квадратично растёт только индекс с именами и состояниями файлов, а не с их содержимым. Но для больших репозиториев это всё ещё может быть проблемой: если выбрать большое T, поиск замедлится из-за многократных обращений к индексу коммитов.
Подход №3. Индекс коммитов через персистентное дерево
Чтобы решить проблему квадратичного размера индекса, мы подсмотрели новый подход в Git: информация о содержимом коммита в нём хранится в персистентном дереве. Вот как может быть устроен наш индекс:
Состояние репозитория описывается деревом, где листовые вершины соответствуют файлам, а остальные некорневые — директориям. Причём содержимое директории соответствует её «детям» в дереве.
При изменении набора файлов мы не трогаем вершины, а создаём их копии, включая новый корень («метод копирования пути»). Например, поменяли один файл, значит, создаём новые копии для всех директорий на пути от этого файла до корня.
Каждый корень дерева соответствует некоторому состоянию репозитория, то есть для каждого коммита достаточно знать соответствующий ему корень, чтобы затем дойти до искомой листовой вершины, где хранится информация о состоянии этого файла.
Подход выглядит перспективно: он уходит от квадратичной сложности и даёт хорошие асимптотические оценки. Но проблемы остаются:
ряд неудачных частных случаев — например, директории с очень большим числом файлов;
время поиска всё ещё не оптимально, потому что приходится спускаться по персистентному дереву.
Делаем шаг назад: линейная история
Чтобы подобраться к новому подходу, представим, что история репозитория — линейная. В таком случае наша задача может быть решена достаточно просто и очень быстро:
Пронумеруем все коммиты числами от 1 до N.
Для каждого файла в дельте каждого коммита сохраним информацию о номере коммита, где этот файл изменяется в следующий раз.
Чтобы понять, верно ли, что файл с именем A в коммите B находится в состоянии C, возьмём номер следующего изменения этого файла после коммита C (обозначим его как C') и сравним его с B. Ответ «да» будет тогда и только тогда, когда C ≤ B < C'.
Таким образом, проверка во время поиска происходит всего за один шаг. Можно ли обобщить этот подход на дерево? Давайте попробуем.
Подход №4. Обход в глубину
Запустим обход дерева коммитов в глубину, начнём из его корня. При этом будем поддерживать счётчик логического времени, увеличивая его на 1 при каждом переходе по ребру.
Зафиксируем время входа и время выхода для каждой вершины.
Определим для каждого файла в каждом коммите ближайшего предка в дереве, изменяющего тот же файл.
Зафиксируем для каждого файла каждого такого предка список времён входа и выхода во все коммиты, для которых текущий коммит является ближайшим предком в смысле п. 3 (или альтернативная формулировка: все коммиты с изменением в том же файле такие, что, во-первых, они являются потомками рассматриваемого коммита, и, во-вторых, на простом пути к рассматриваемому коммиту нет других коммитов, изменяющих тот же файл). Заметим, что такой список содержит набор непересекающихся отрезков.
Чтобы понять, верно ли, что файл с именем A в коммите B находится в состоянии C, запустим бинарный поиск значения времени (например, входа) коммита B по списку времён потомков из п. 4 для файла A в коммите C. Для утвердительного ответа необходимо, чтобы, с одной стороны, отрезок времени B был вложенным по отношению к C (что отражает условие, что B — потомок C), а с другой — чтобы он не был вложенным по отношению ко всем потомкам из списка, причём в силу того, что отрезки в списке не пересекаются, достаточно проверить не более одного кандидата, определяемого при помощи бинарного поиска.
Таким образом, для каждого файла в индекс записывается список времён потомков для каждого коммита, где этот файл изменялся.
Пункты 1–4 можно выполнить за один обход дерева. И хотя этот обход приходится повторять при каждой индексации, её время остаётся приемлемым. Даже для репозитория из сотен тысяч или более чем миллиона коммитов (вроде ядра Linux) всё дерево коммитов легко умещается в память.
Время поиска в этом случае нас тоже устраивает, ведь достаточно сделать один бинарный поиск по довольно короткому списку. Небольшим минусом является то, что, в отличие от предыдущих решений, такая структура индекса не позволяет быстро определить состояние файла по известным имени и коммиту.
Этот подход устраивал нас по всем параметрам и имел все шансы быть реализованным, но в последний момент нам пришло ещё одно решение. Почти такое же быстрое, но куда более простое, наглядное и красивое.
Подход №5. Линеаризация истории
Снова вернёмся к упрощённой задаче с линейной историей. На этот раз сразу научимся определять состояние файла по известным имени и коммиту:
Снова пронумеруем все коммиты числами от 1 до N.
Выпишем для каждого файла в порядке возрастания номера всех коммитов, в которых этот файл изменялся.
Научимся узнавать состояние файла в некотором коммите. Для решения такой задачи произведём бинарный поиск по соответствующему этому файлу списку номеров: последний коммит с номером, не превосходящим номер интересующего нас коммита, и определит это состояние.
Поскольку список версий файла обычно длиннее, чем список коммитов из предыдущего подхода, такое решение будет более медленным. Однако благодаря логарифмическому времени работы бинарного поиска это различие для нас несущественное.
Но всё ещё остаётся вопрос, как применить данный подход к дереву. Оказывается, для этого достаточно посмотреть на уже описанное решение немного под другим углом и воспользоваться идеей Эйлерова обхода дерева.
Построим новую, линейную историю репозитория, добавив нашему обходу в глубину определённый смысл: будем считать, что каждый переход по ребру соответствует созданию нового коммита. При этом, если переход идёт «вниз» (от корня), дельта переносится без изменений, а если «вверх» — инвертируется, то есть мы берём дельту обратного изменения. Тогда после обхода всего дерева коммитов мы получим линейную историю изменений, содержащую все состояния (пусть и вдвое длиннее), а значит, к ней применим описанный выше подход.
Отдельно можно отметить, что вычисляемые времена вершин оказываются номерами коммитов в новой истории.
Ограничение истории
Внимательный читатель мог заметить, что построение индекса для всех коммитов хоть и возможно, но часто избыточно. Обычно нас интересует лишь некоторое предсказуемое подмножество: например, несколько последних коммитов во всех ветках репозитория — их можно найти поиском в ширину.
Оказывается, описанный выше подход легко обобщается на такую задачу, причём даже для самого широкого её варианта. А именно: пусть задан произвольный набор коммитов, и для каждого из них нужно уметь осуществлять поиск. Проделаем следующую модификацию алгоритма индексации:
При каждом переходе по ребру будем записывать в промежуточный буфер информацию об изменившихся файлах (имя и текущее состояние).
При посещении вершины, которая отмечена для индексации, добавим в целевой список индексации все изменившиеся файлы в их текущих состояниях и очистим буфер.
В результате обхода дерева коммитов получаем список всех состояний файлов, которые нужно проиндексировать. Сравнив его с аналогичным списком с предыдущей итерации индексации (если она была), понимаем, как изменить основной индекс: какие версии файлов добавить, а какие убрать. Так мы поддерживаем в индексе минимально необходимый набор файлов и при этом минимизируем изменения самого индекса.
Мы реализовали подход с линеаризацией истории более года назад, и с тех пор он успешно работает. Пользователи SourceCraft могут осуществлять быстрый поиск по веткам и навигацию по репозиторию.
Для меня эта история оказалась увлекательным примером того, как классические алгоритмы во всём своём многообразии помогают решать вполне практические задачи. И я с удовольствием поделился этим опытом. А какие алгоритмические задачи встречались вам? Давайте обсудим в комментариях!