Поиск среди 10000 GitHub репозиториев на Postgres (используя только MacBook)

Привет. Это вольный перевод интересной статьи Postgres regex search over 10,000 GitHub repositories (using only a Macbook). Перевод опубликован с согласия автора.

Так же можете подписаться на очередной канал разработчика в телеграмм.

В этой статье мы поделимся результатами своего эксперимента по использованию Postgres для индексирования и последующего поиска среди 10.000 GitHub репозиториев с использованием pg_trgm только на MacBook.

Это продолжение “Postgres Trigram search learnings”, в которой мы поделились некоторыми фишками и подводными камнями при использовании триграмм индексов в Postgres как альтернатива для гугловому Zoekt.

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

TL;DR

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

Цели

Мы хотим получить эмпирические измерения о том, насколько Postgres подходит для поиска по документам с помощью regexp, в качестве альтернативы гугловому Zoekt. А конкретно:

• Сколько репозиториев можно проиндексировать на одном MacBook Pro 2019 года ?
• На сколько быстрым будет поиск по корпусу данных с помощью различных регулярных выражений ?
• Какая конфигурация Postgres 13 дает наилучший результат ?
• Какие посторонние эффекты нужно учитывать для того, чтобы рассматривать Postgres как бекенд поисковой системы на регулярных выражениях ?
• Какую схему базы данных лучше всего использовать ?

Железо

Все тесты запускаются на единственном MacBook Pro 2019 в конфигурации:

• 2.3 GHz 8-Core Intel Core i9
• 16 GB 2667 MHz DDR4 Во время выполнения тестов другие приложения почти не использовались, так что их эффектом на потребление CPU можно пренебречь и считать, что весь CPU/RAM были отданы для Postgres.

Корпус

Мы собрали списки 1000 лучших репозиториев с GitHub, отсортированных по количеству звездочек для каждого из следующих языков (всего получилось примерно 20500 репозиториев):

• C++, C#, CSS, Go, HTML, Java, JavaScript, MatLab, ObjC, Perl, PHP, Python, Ruby, Rust, Shell, Solidity, Swift, TypeScript, VB .NET и Zig. Клонирование всех 20500 репозиториев заняло примерно 14 часов с около 100Мб/с соединением до серверов GitHub.

Уменьшение размера датасета

Я обнаружил, что объем дискового пространства требуемого для git clone --depth 1 всего для 12148 репозиториев составляет примерно 412Гб, поэтому было принято решение использовать пару приемов для уменьшения размера набора данных примерно на 66%:

• Удаление директории .git дало снижение на 30% (412Гб -> 290Гб, для 12148 репозиториев)
• Удаление файлов > 1Мб дало снижение еще на 51% (290Гб -> 142Гб, для 12148 репозиториев - GitHub, кстати, не индексирует файлы размером больше 384Кб)

Вставка данных

Вставка производилась конкурентно в Postgres со следующей схемой:

CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE TABLE IF NOT EXISTS files (
    id bigserial PRIMARY KEY,
    contents text NOT NULL,
    filepath text NOT NULL
);

Заняло это примерно 8 часов, а на диске Postgres занял 101Гб.

Создание индекса

Я трижды пытался проиндексировать набор данных используя GIN индекс:

CREATE INDEX IF NOT EXISTS files_contents_trgm_idx ON files USING GIN (contents gin_trgm_ops);

• В первый раз я поймал OOM после 11 с половиной часов индексирования. Это было связано с резким всплеском потребления памяти в самом конце индексирования. Это не было неожиданностью, так как использовалась достаточно агрессивная конфигурация Postgres с очень большим максимальным размером WAL.
• Во второй раз после 27 часов индексирования закончилось место на диске. Потребление дискового пространства также резко увеличилось к концу индексирования, то есть это не было постепенным увеличением потребления свободного места на SSD. Для этой попытки использовался прекрасный инструмент pgtune для уменьшения конфигурации Postgres из первой попытки:

shared_buffers = 4GB → 2560MB
effective_cache_size = 12GB → 7680MB
maintenance_work_mem = 16GB → 1280MB
default_statistics_target = 100 → 500
work_mem = 5242kB → 16MB
min_wal_size = 50GB → 4GB
max_wal_size = 4GB → 16GB
max_parallel_workers_per_gather = 8 → 4
max_parallel_maintenance_workers = 8 → 4

• В третий и последний раз, датасет был обрезан на половину и индексирование заняло примерно 22 часа. А конкретно была удалена половина файлов (с 19441820 файлов / 178Гб до 9720910 файлов / 82Гб). Конфигурация Postgres была аналогична той, что использовалась во второй попытке.

Потребление памяти

В первой попытке, контейнер с Postgres использовал целых 12Гб (если верить docker stats):

Во второй и третьей попытке использование памяти сильно упало (примерно до 1.6Гб):

Потребление CPU

Построение GIN индекса в Postgres похоже однопоточно (по крайней мере при индексировании одной таблицы, несколько таблиц будут протестированы позже).

В первой попытке использования CPU не превышало 156% (одно + половина виртуального ядра CPU):

Во второй попытке потребление CPU в среднем было 150-200%:

В третьей попытке потребление CPU было примерно таким же и составляло 150-200%, с небольшим всплеском до 350% к концу:

IO

Операции ввода-вывода для диска в процессе индексирования варьировались около 250Мб/с для чтения (голубой цвет) и записи (красный). Бенчмарки диска установленного в тестовый MacBook показывают, что он способен достичь скорости в примерно 860Мб/с на чтение/запись с <5% утилизацией CPU.

Примечание: Postgres вне контейнера показывает лучшую производительность при индексировании.

Дисковое пространство

База данных содержит 9720910 файлов общий размер которых 82.07Гб.

postgres=# select count(filepath) from files;
  count
---------
 9720910
(1 row)

postgres=# select SUM(octet_length(contents)) from files;
     sum
-------------
 88123563320
(1 row)

До индексирования Postgres занимал 54Гб:

$ du -sh .postgres/
 54G	.postgres/

После CREATE INDEX:

$ du -sh .postgres/
 73G	.postgres/

Таким образом, размер индекса для 82Гб текста составляет 19Гб (или 23% от объема данных).

Время запуска базы данных

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

Запросы

В общей сложности мы выполнили 19936 поисковых запросов к индексу. Мы выбрали запросы, которые, по нашим ожиданиям, дают достаточно разное покрытие триграммного индекса (то есть запросы, триграммы которых с большей или меньшей вероятностью встречаются во многих файлах):

Производительность запросов

В общей сложности мы выполнили 19 936 поисковых запросов к базе данных (линейно, не параллельно), которые завершились за следующее время:

Реальная производительность vs. планировщик

Приведенный ниже график отражает, что 79% запросов выполнялись менее чем за 3 секунды (ось Y в миллисекундах), в то время как планировщик запросов Postgres планировал их выполнение за 100-250 миллисекунд (ось X):

Если мы расширим график таким образом, чтобы в него помещались все запросы, то увидим, насколько оставшиеся 21% запросов выбиваются от остальных (обратите внимание, что небольшой блок точек в левом нижнем углу представляет собой ту же диаграмму, показанную выше):

Потребление CPU/RAM

Следующие графики показывают:

• верхний — время запроса в миллисекундах
• средний — процент использования ЦП (например, 801% означает, что используется 8 из 16 виртуальных ядер)
• нижний — потребление памяти в мегабайтах

Из этого можно сделать следующие выводы:

• Значительное увеличение использования ресурсов к концу — это когда мы начали выполнять запросы без LIMIT.
• Использование CPU не превышает 138%, до всплеска в конце.
• Потребление памяти не превышает 42Мб, до всплеска в конце.

Есть подозрение, что pg_trgm является однопоточным в пределах одной таблицы, но также предполагаем, что лучшего параллелизма (и следовательно лучших результатов) можно добиться при партиционировании (разбиением данных на несколько таблиц).

Исследование медленных запросов

Если построить график зависимости количества повторных проверок индекса (ось X) от времени выполнения (ось Y), то можно увидеть, что одним из значимых аспектов замедления выполнения запроса является большее количество повторных проверок индекса:

И если мы взглянем на EXPLAIN ANALYZE одного из таких запросов, то сможем подтвердить, что Parallel Bitmap Heap Scan работает медленно из-за Rows Removed by Index Recheck.

Партиционирование

Разделение на несколько небольших таблиц кажется очевидным подходом к тому, чтобы заставить pg_trgm использовать несколько ядер процессора. Мы попробовали это сделать, взяв тот же набор данных и разделив его на 200 таблиц, и обнаружили многочисленные преимущества.

№1: Инкрементальное индексирование

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

№2: Параллельное индексирование

В отличии от нашего первого подхода, который показал, что при построении индекса использовались всего 1.5-2 виртуальных ядра CPU, то с несколькими таблицами мы смогли утилизировать 8-9 ядер CPU:

№3: Индексирование на 84% быстрее

В отличии от первого подхода, индексирование в котором занимало 22 часа, параллельное индексирование завершилось всего за 3 час 27 минут.

№4: Индексирование потребляет на 69% меньше RAM

В подходе с одной таблицей мы видели, что пиковое значение потребление памяти составляло 12Гб. С такой же конфигурацией Postgres, мы можем рассчитывать на пиковое значение потребления памяти всего в 3.7Гб:

№5: Параллельная обработка запросов

Ранее мы наблюдали загрузку процессора всего на 138% (1.3 виртуальных ядра CPU), а с разделением таблиц мы видим загрузку процессора во время запросов на 1600% (16 виртуальных ядер CPU), что показывает, что мы выполняем работу полностью параллельно:

Аналогичным образом дело обстоит и с потреблением памяти. Среднее значение потребления памяти увеличилось до 380Мб, в отличии от 42Мб в подходе с одной таблицей:

№6: Производительность запросов

Мы повторно выполнили тот же набор поисковых запросов, но меньшее количество раз (350 запросов вместо 19.9 тыс., что, по нашему мнению, является достаточно представительной выборкой). Как мы можем видеть ниже, разделение таблиц в целом привело к улучшению времени выполнения запросов на 200-300% для более тяжелых запросов, которые раньше занимали 20-30 секунд, а теперь занимают всего 7-15 секунд благодаря параллельному выполнению запросов (верхний график - до, нижний - после, оба в миллисекундах):

Мы также сгруппировали запросы на основе LIMIT, указанного в запросе, и распределили их по временным интервалам (“сколько запросов завершилось менее чем за 50 мс?”) - сравнение этих двух показателей дает понять, что менее сложные запросы и/или запросы с меньшим количеством результатов пострадали незначительно, в то время как более крупные запросы получили существенный прирост в производительности:

Docker vs. нативный Postgres

Сначала мы не думали о влиянии производительности при запуске Postgres в Docker. Этот вопрос был поднят Thorsten Ball, как потенциальный источник разницы в производительности IO операций.

Все тесты выше были произведены на запущенном в Docker Postgres с использованием драйвера osxfs, а не экспериментального драйвера FUSE gRPC.

Мы дополнительно прогнали те же тесты на собственном сервере Postgres и обнаружили следующие ключевые изменения.

Потребление CPU/RAM

Потребление CPU и памяти было похожим на то, что мы наблюдали с Postgres в Docker.

Индексирование стало на 88% быстрее

Разбиение одной большой таблицы на несколько маленьких происходило следующим образом:

CREATE TABLE files_000 AS SELECT * FROM files WHERE id > 0 AND id < 50000;
CREATE TABLE files_001 AS SELECT * FROM files WHERE id > 50000 AND id < 100000;
...

Процесс разбиения был куда быстрее в нативно запущенном Postgres. На построение каждой таблицы уходило от 2 до 8 секунд, тогда как при запуске в Docker на это уходило 20-40 секунд.

Параллельное создание триграмм индексов CREATE INDEX IF NOT EXISTS files_000_contents_trgm_idx ON files USING GIN (contents gin_trgm_ops); также было быстрым, всего 23 минуты вместо примерно 3 часов в Docker.

Скорость обработки запросов увеличилась на 12-99%

Мы запустили те же 350 запросов с нашего прошлого теста и обнаружили несколько существенных улучшений:

• Запросы, которые ранее выполнялись очень медленно, улучшились на ~12%. Вероятно, это связано с операциями ввода-вывода, необходимыми при взаимодействии с 200 отдельными таблицами.
• Для средних по времени выполнения запросов, прирост составил примерно 5%.
• Запросы, которые ранее были очень быстрыми (вероятнее всего поиск осуществлялся по одной-двум таблицам), улучшились на 16-99%.

Выводы

Мы считаем, что наиболее важными являются следующие выводы:

• Директория .git , даже с клонированием --depth=1, составляет 30% от размера репозитория на диске (по крайней мере, в 10000 лучших репозиториев GitHub).
• Файлы более 1Мб (часто бинарный файлы) составляют другие 51% от объема данных на диске.
• Используя только MacBook, возможно построить GIN индексы Postgres по 10000 репозиториев GitHub и выполнять большинство разумных запросов менее чем за 5 секунд и, конечно, гораздо быстрее при использовании более мощного железа.
• pg_trgm выполняет индексирование и поиск однопоточной, если не разделить данные на несколько таблиц.
• По умолчанию, Postgres сжимает колонки с типом text, что в результате приводит к уменьшение размера на 23%.
• pg_trgm индексы занимают около 26% размера данных на диске. Таким образом, если индексируется 1Гб необработанного текста, то можно ожидать, что Postgres потребует для хранения данных примерно 827Мб, а для индекса около 279Мб.
• Разделять данные на несколько таблиц при использовании pg_trgm это однозначно то, что следует делать. Такой подход позволяет уменьшить время на построение индекса (в нашем случае с 22 часов до 4).
• Bind mount довольная медленная технология за пределами хост-окружения Linux.