# Ускоренное построение KNN-индексов в Manticore

Теперь Manticore может строить KNN-индексы параллельно: при сохранении и слиянии чанков, а также при пересборке KNN-данных. На машине с 16 ядрами время построения KNN-индекса для 1 млн векторов сократилось с 8 минут до 39 секунд.

### Кратко

Раньше построение KNN-индекса было самым медленным этапом при сохранении и слиянии чанков в таблицах с векторными атрибутами. Начиная с [v27.1.5](/blog/manticore-search-27-1-5/), Manticore может задействовать несколько ядер CPU при сохранении чанков, слияниях через `OPTIMIZE`, авто-оптимизации и `ALTER TABLE ... REBUILD KNN`. На 16-ядерном Ryzen 9 5950X построение KNN-индекса для 1 миллиона 1536-мерных векторов сократилось с 8 минут до 39 секунд.

## Почему скорость построения HNSW важна

Manticore использует графы HNSW для KNN-поиска по атрибутам `float_vector`. Граф HNSW можно представить как карту, которая помогает Manticore быстро находить векторы, близкие к вектору запроса.

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

Это особенно важно после массовых вставок и при обслуживании таблиц. Новые данные сохраняются из оперативной памяти в дисковые чанки. Затем существующие чанки сливаются через `OPTIMIZE` или авто-оптимизацию. Для каждого сохранённого или слитого чанка нужен свой граф HNSW, поэтому более быстрое построение графа сокращает ожидание после bulk-загрузки, ускоряет фоновую оптимизацию и сокращает время выполнения операций обслуживания.

[Количество дисковых чанков](https://manual.manticoresearch.com/Creating_a_table/Local_tables/Plain_and_real-time_table_settings#Important-notes-about-RAM-chunks) важно и для поиска. Manticore хранит RT-таблицы как дисковые чанки, и у каждого чанка есть свой граф HNSW. KNN-запрос проходит по каждому чанку и объединяет результаты, поэтому чем меньше чанков, тем обычно быстрее KNN-запросы. Чаще всего самый быстрый вариант — один чанк с одним графом.

[Авто-оптимизация](https://manual.manticoresearch.com/Server_settings/Searchd#auto_optimize) по умолчанию не доводит таблицу до одного чанка. Она сливает чанки в фоне, но останавливается, когда таблица достигает целевого числа чанков. Для обычных таблиц целевое значение равно `2 * num_logical_cpus`; для таблиц с KNN-атрибутом оно ниже: `num_physical_cpus / 2`. На хосте с 32 потоками / 16 ядрами это означает 8 чанков для KNN-таблицы вместо 64 для обычной. Целевое число для KNN ниже, потому что лишние чанки сильнее ухудшают время ответа KNN-поиска, но дефолт всё равно оставляет больше одного графа. Чтобы авто-оптимизация доводила таблицу до одного чанка, можно задать [optimize_cutoff](https://manual.manticoresearch.com/Server_settings/Searchd#optimize_cutoff) равным `1` на уровне сервера, для отдельной таблицы или на лету через `SET GLOBAL optimize_cutoff = 1`. То же можно сделать вручную с помощью [OPTIMIZE TABLE ... OPTION cutoff = 1](https://manual.manticoresearch.com/Securing_and_compacting_a_table/Compacting_a_table).

## Как было раньше

Новые документы сначала накапливаются в RAM-чанке. Когда RAM-чанк достигает [rt_mem_limit](https://manual.manticoresearch.com/Creating_a_table/Local_tables/Plain_and_real-time_table_settings#rt_mem_limit), который по умолчанию равен 128 МБ, Manticore сохраняет его как новый дисковый чанк. Для таблицы с KNN-атрибутом такое сохранение включает построение нового графа HNSW по векторам из RAM-чанка.

Такой же граф HNSW строится при слиянии дисковых чанков. `OPTIMIZE TABLE` и авто-оптимизация читают живые строки из существующих чанков, записывают новый слитый чанк и строят новый граф HNSW для получившегося чанка. `ALTER TABLE ... REBUILD KNN`, а также операции ALTER, которые добавляют или удаляют столбец `float_vector`, тоже пересобирают граф.

До этого изменения этап работы с HNSW в каждом отдельном сохранении, слиянии или пересборке выполнялся **одним воркером**:

- При сохранении RAM-чанка в дисковый чанк Manticore по одной обходил все живые строки из сегментов RAM-чанка и вставлял их векторы в один граф HNSW.
- При слиянии чанков Manticore по одной обходил все живые строки из входных дисковых чанков и вставлял их векторы в новый граф.
- `ALTER TABLE ... REBUILD KNN` пересобирал каждый граф одним воркером.

У Manticore уже была параллельность на уровне этих операций. Одновременно могут выполняться до двух сохранений RAM-чанков. Оптимизатор также может запускать несколько слияний чанков одновременно; это регулируется параметром [parallel_chunk_merges](https://manual.manticoresearch.com/Server_settings/Searchd#parallel_chunk_merges). По умолчанию значение равно `2`, если на хосте достаточно ядер CPU. Но внутри каждого отдельного сохранения или слияния построение KNN-графа всё ещё выполнялось одним воркером. Для таблиц с большим объёмом KNN-данных именно этот воркер часто определял длительность всей операции.

## Что изменилось

Теперь Manticore распределяет построение одного KNN-графа между несколькими воркерами. Каждый воркер получает свою часть строк, вставляет их векторы в один общий граф и завершает работу независимо. Библиотека построения графа координирует параллельные вставки так, чтобы граф оставался корректным.

Точное разбиение зависит от операции:

- Во время сохранения RAM-чанка в дисковый чанк воркеры забирают сегменты RAM-чанка из общей очереди, пока все сегменты не будут обработаны.
- Во время слияния чанков и `ALTER TABLE ... REBUILD KNN` Manticore делит живые строки на диапазоны примерно одинакового размера, чтобы нагрузка распределялась равномерно.

### Улучшения режима с одним воркером

В этом же релизе улучшен и режим с одним воркером. Даже при `knn_parallel_build = 1` бенчмарк ниже показывает улучшение на 10% ещё до включения параллелизма. Это результат трёх изменений:

1. **Двухпроходная обработка соседей.** При вставке вектора алгоритм проходит по кандидатам-соседям и вычисляет до них расстояния. Новый код делит это на два прохода: первый проходит по списку соседей и заранее подгружает данные векторов, а второй вычисляет расстояния. Это даёт процессору время загрузить векторы в кэш до того, как они понадобятся.
2. **Два кандидата за раз.** Некоторые вычисления расстояний теперь обрабатывают по два вектора-кандидата одновременно. Это уменьшает повторяющуюся работу во внутреннем цикле, на который приходится большая часть времени построения.
3. **Выбор функции расстояния на этапе компиляции в режиме построения.** Теперь модуль построения один раз выбирает нужный вариант функции расстояния — с учётом метрики (inner product или L2) и типа данных (обычные float-векторы или бинарно квантованные векторы). Благодаря этому не приходится искать функцию через указатель при каждом вычислении расстояния, и компилятор может агрессивнее оптимизировать внутренний цикл.

### Значение по умолчанию и конфигурация

Новая настройка `searchd`, [knn_parallel_build](https://manual.manticoresearch.com/Server_settings/Searchd#knn_parallel_build), управляет тем, сколько воркеров может использовать одно построение KNN-индекса. По умолчанию это `min(4, threads / 4)`, где `threads` — настройка [threads](https://manual.manticoresearch.com/Server_settings/Searchd#threads) в Manticore, то есть размер пула воркеров для запросов и фоновых задач; по умолчанию он равен числу логических ядер CPU на хосте.

На практике это означает один воркер на небольших хостах и до четырёх воркеров по умолчанию на более крупных: хост с 4 потоками получает один воркер, с 8 потоками — два, с 16 потоками — четыре, а при большем числе потоков лимит всё равно остаётся равен четырём. Дефолт выбран консервативно, потому что production-машинам часто нужно одновременно обрабатывать поиск, вставки и фоновые задачи.

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

```sql
SET GLOBAL knn_parallel_build = 16;
```

Установите `1`, если нужно старое поведение с одним воркером:

```sql
SET GLOBAL knn_parallel_build = 1;
```

Значение также можно задать в конфиге `searchd` и проверить через `SHOW VARIABLES`.

### Использование CPU

Одновременно могут выполняться несколько сохранений и слияний, и каждое из них может использовать до `knn_parallel_build` воркеров. Эти воркеры используют существующий пул `threads` Manticore. Они не создают неограниченное число дополнительных потоков ОС; если все потоки пула заняты, оставшаяся работа ждёт в очереди.

Именно поэтому по дефолту остаётся запас. На хосте с 32 потоками по умолчанию используется 4 воркера на каждое построение KNN-индекса. Если два сохранения чанков выполняются одновременно, построение KNN может использовать до 8 воркеров, а остальные потоки пула останутся доступны для других задач.

## Бенчмарк

Стенд:

- AMD Ryzen 9 5950X (16 физических / 32 логических ядра)
- Датасет: [dbpedia-openai-1M](https://storage.googleapis.com/ann-filtered-benchmark/datasets/dbpedia_openai_1M.tgz) — 1 млн векторов размерности 1536, косинусное расстояние (cosine distance)
- Квантизация: 1-битная квантизация (binary)
- Данные вставлены в RT-таблицу, затем выполнен `OPTIMIZE` до одного дискового чанка
- Замер: `ALTER TABLE knn_data REBUILD KNN`, по три запуска для каждого значения; один чанк использовался, чтобы время выполнения было стабильным
- Настройки HNSW: значения по умолчанию

Для измерений использовался `ALTER TABLE ... REBUILD KNN`: он задействует тот же механизм параллельного построения, что и сохранение или слияние чанков, но даёт стабильное время выполнения, которое легко воспроизвести.

![Время выполнения ALTER REBUILD KNN в зависимости от knn_parallel_build](./knn-parallel-build/knn_parallel_build_walltime_chart.svg)

Результаты:

- При одном воркере новый код уже на 10% быстрее старого: 442 секунды вместо 492.
- При 16 воркерах время пересборки сократилось до 39 секунд — примерно в 11 раз быстрее, чем в новом режиме на одном воркере.
- Переход с 16 на 32 воркера дал лишь небольшой прирост: время снизилось с 39 до 36 секунд. На этой машине практический предел близок к 16 физическим ядрам CPU.
- Дефолт рассчитан на production-хосты с общей нагрузкой. Для обслуживания на выделенном хосте `knn_parallel_build` может быть полезно увеличить.

## Миграция

Никаких действий не требуется. Существующие таблицы продолжают работать, а KNN-графы, построенные параллельно, функционально эквивалентны графам, построенным старым способом с одним воркером.

Для строгой воспроизводимости важна одна деталь: параллельные воркеры могут вставлять векторы в другом порядке, поэтому файл KNN-графа Manticore на диске с расширением `.spknn` не гарантированно будет побайтно идентичен графу, построенному одним воркером. Ожидается, что качество поиска и скорость выполнения запросов будут такими же. Если нужна побайтная воспроизводимость, установите `knn_parallel_build = 1`.

## Вывод

Это изменение ускоряет один из самых долгих этапов обслуживания KNN-таблиц. Параллельное построение графа сокращает время сохранения и слияния чанков, а также пересборки KNN-данных; улучшенный режим с одним воркером даёт прирост и на небольших системах. Существующие таблицы продолжают работать без изменений. Если при обслуживании можно задействовать дополнительные ресурсы CPU, `knn_parallel_build` можно увеличить, чтобы быстрее строить KNN-графы.