- 13,579
- 20
- 8 Ноя 2022
Инженер GitHub рассказал, как система добилась индексирования поиска со скоростью около 120 000 документов в секунду.
Инженер GitHub Тимоти Клем Для просмотра ссылки Войди
Для перемещения по такому количеству строк кода требуется что-то более мощное, чем 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 часов для повторного индексирования, поскольку дельта-индексация (изменение) сокращает количество документов, которые необходимо сканировать.
- Источник новости
- www.securitylab.ru
