Описаны подробности о поисковой системе исходного кода GitHub

Инженер GitHub Тимоти Клем подробно рассказал о технологии, используемой для поисковой системы исходного кода из репозиториев GitHub под названием Blackbird. Поисковик исходного кода разработан на Rust и пока охватывает почти 45 млн. репозиториев GitHub, которые вместе составляют 115 ТБ кода и 15,5 млрд. документов. GitHub Code Search в настоящее время находится в стадии бета-тестирования .

Для перемещения по такому количеству строк кода требуется что-то более мощное, чем grep, обычный инструмент командной строки в Unix-подобных системах для поиска в текстовых данных. Клем объяснил, что использование ripgrep на 8-ядерном процессоре Intel для выполнения исчерпывающего запроса регулярного выражения к файлу размером 13 ГБ в памяти занимает около 2,769 секунды или 0,6 ГБ/с на ядро.

«Это не сработает для большого объема данных, которые у нас есть», — сказал он. «Поиск кода работает на 64 ядрах, 32 машинных кластерах. Даже если нам удастся поместить 115 ТБ кода в память и предположить, что мы можем идеально распараллелить работу, мы собираемся насытить 2048 ядер ЦП на 96 секунд для обслуживания одного запроса! Только этот запрос может быть выполнен. Все остальные должны встать в очередь», - объяснил Клем.

При скорости 0,01 запроса в секунду grep был невозможен. Поэтому GitHub переложил большую часть работы на предварительно вычисленные поисковые индексы. По сути, это карты пар ключ-значение. Такой подход снижает вычислительные затраты при поиске характеристик документа, таких как язык программирования или последовательности слов, с использованием числового ключа, а не текстовой строки.

Тем не менее, эти индексы слишком велики, чтобы поместиться в памяти, поэтому GitHub построил итераторы для каждого индекса, к которому ему нужно было получить доступ. Они возвращают отсортированные идентификаторы документов, которые соответствуют критериям запроса.

Чтобы сохранить управляемость поискового индекса, GitHub полагается на сегментирование — разбиение данных на несколько частей с использованием схемы хеширования с адресацией содержимого Git и на дельта-кодирование — сохранение различий данных (дельта) для сокращения данных и метаданных, которые необходимо сканировать. Это хорошо работает, потому что GitHub имеет много избыточных данных (например, ответвлений) — его 115 ТБ данных можно сократить до 25 ТБ с помощью методов дедупликации данных.

Получившаяся система работает намного быстрее, чем grep — 640 запросов в секунду по сравнению с 0,01 запроса в секунду. И индексирование происходит со скоростью около 120 000 документов в секунду, поэтому обработка 15,5 млрд. документов занимает около 36 часов, или 18 часов для повторного индексирования, поскольку дельта-индексация (изменение) сокращает количество документов, которые необходимо сканировать.