Оптимизация NVIDIA CAGRA в Milvus: гибридный подход GPU-CPU к ускоренному индексированию и более дешевым запросам

По мере того как системы искусственного интеллекта переходят от экспериментов к производственной инфраструктуре, векторные базы данных перестают справляться с миллионами вкраплений. Миллиарды стали обычным делом, а десятки миллиардов - все более распространенным. При таких масштабах выбор алгоритма влияет не только на производительность и запоминание, но и непосредственно на стоимость инфраструктуры.

В связи с этим возникает основной вопрос для крупномасштабных развертываний: как выбрать правильный индекс, который обеспечит приемлемую отзывчивость и задержку и при этом не выведет использование вычислительных ресурсов из-под контроля?

Наиболее распространенным ответом стали индексы на основе графиков, такие как NSW, HNSW, CAGRA и Vamana. Благодаря навигации по заранее построенным графам соседей эти индексы обеспечивают быстрый поиск ближайших соседей в миллиардных масштабах, позволяя избежать грубого сканирования и сравнения каждого вектора с запросом.

Однако стоимость такого подхода неравномерна. Запрос графа относительно дешев, а его построение - нет. Построение высококачественного графа требует масштабных вычислений расстояний и итеративного уточнения по всему набору данных - нагрузка, с которой традиционные CPU не справляются по мере роста данных.

NVIDIA CAGRA решает эту проблему, используя GPU для ускорения построения графов за счет массивного параллелизма. Хотя это значительно сокращает время сборки, использование GPU для построения индексов и обслуживания запросов приводит к увеличению стоимости и ограничений масштабируемости в производственных средах.

Чтобы сбалансировать эти компромиссы, в Milvus 2.6.1 используется гибридный дизайн для индексов GPU_CAGRA: GPU используются только для построения графов, а выполнение запросов происходит на CPU. Это позволяет сохранить качественные преимущества графов, построенных на GPU, а также масштабируемость и экономическую эффективность обслуживания запросов, что особенно хорошо подходит для рабочих нагрузок с нечастыми обновлениями данных, большими объемами запросов и строгой чувствительностью к стоимости.

Что такое CAGRA и как она работает?

Векторные индексы на основе графов обычно делятся на две основные категории:

• Итеративное построение графов, представленное CAGRA (уже поддерживается в Milvus).

• Построение графов на основе вставки, представленное Vamana (в настоящее время разрабатывается в Milvus).

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

NVIDIA CAGRA (CUDA ANN Graph-based) - это нативный GPU-алгоритм для приблизительного поиска ближайших соседей (ANN), предназначенный для эффективного построения и запроса крупномасштабных графов близости. Используя параллелизм GPU, CAGRA значительно ускоряет построение графов и обеспечивает высокую производительность запросов по сравнению с подходами на базе CPU, такими как HNSW.

CAGRA построен на алгоритме NN-Descent (Nearest Neighbor Descent), который строит граф k-nearest-neighbor (kNN) путем итеративного уточнения. На каждой итерации оцениваются и обновляются соседи-кандидаты, постепенно сходясь к более качественным отношениям между соседями по всему набору данных.

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

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

Шаг 1: Построение исходного графа с помощью NN-Descent

NN-Descent основан на простом, но действенном наблюдении: если узел u является соседом v, а узел w - соседом u, то с большой вероятностью w также является соседом v. Это переходное свойство позволяет алгоритму эффективно находить истинных ближайших соседей без исчерпывающего сравнения каждой пары векторов.

В качестве основного алгоритма построения графов CAGRA использует NN-Descent. Процесс происходит следующим образом:

1. Случайная инициализация: Каждый узел начинает работу с небольшим набором случайно выбранных соседей, формируя грубый начальный граф.

2. Расширение круга соседей: На каждой итерации узел собирает своих текущих соседей и их соседей, чтобы сформировать список кандидатов. Алгоритм вычисляет сходство между узлом и всеми кандидатами. Поскольку список кандидатов каждого узла независим, эти вычисления могут быть назначены отдельным блокам потоков GPU и выполняться параллельно в огромных масштабах.

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

4. Проверка сходимости: По мере выполнения итераций происходит все меньше обновлений соседей. Как только количество обновленных связей опускается ниже заданного порога, алгоритм останавливается, указывая на то, что граф фактически стабилизировался.

Поскольку расширение соседей и вычисление сходства для разных узлов полностью независимы, CAGRA передает рабочую нагрузку NN-Descent для каждого узла в выделенный блок потоков GPU. Такая конструкция обеспечивает массивный параллелизм и позволяет строить графы на порядки быстрее, чем традиционные методы на базе CPU.

Шаг 2: обрезка графа с помощью 2-ходовых обходов

После завершения работы NN-Descent полученный граф является точным, но слишком плотным. NN-Descent намеренно сохраняет лишних соседей-кандидатов, а случайная фаза инициализации вносит множество слабых или неактуальных ребер. В результате каждый узел часто оказывается со степенью, в два раза или даже в несколько раз превышающей целевую степень.

Чтобы получить компактный и эффективный граф, CAGRA применяет обрезку 2-ходовых обходов.

Идея проста: если узел A может косвенно достичь узла B через общего соседа C (образуя путь A → C → B), и расстояние этого косвенного пути сравнимо с прямым расстоянием между A и B, то прямое ребро A → B считается избыточным и может быть удалено.

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

В результате CAGRA может эффективно обрезать граф на GPU, сокращая накладные расходы на хранение на 40-50 %, сохраняя при этом точность поиска и повышая скорость обхода во время выполнения запроса.

GPU_CAGRA в Milvus: в чем разница?

Хотя GPU обеспечивают значительные преимущества в производительности при построении графов, производственные среды сталкиваются с практической проблемой: Ресурсы GPU гораздо дороже и ограниченнее, чем у CPU. Если построение индексов и выполнение запросов зависят исключительно от GPU, быстро возникает несколько эксплуатационных проблем:

• Низкий уровень использования ресурсов: Трафик запросов часто нерегулярен и скачкообразен, в результате чего GPU простаивают длительное время и расходуют дорогостоящие вычислительные мощности.

• Высокая стоимость развертывания: Назначение GPU каждому экземпляру, обслуживающему запросы, приводит к увеличению стоимости оборудования, даже если большинство запросов не используют производительность GPU в полной мере.

• Ограниченная масштабируемость: Количество доступных GPU напрямую влияет на количество копий сервисов, которые вы можете запустить, что ограничивает ваши возможности по масштабированию в зависимости от спроса.

• Снижение гибкости: Когда построение индексов и формирование запросов зависят от GPU, система становится привязанной к доступности GPU и не может легко перенести рабочую нагрузку на CPU.

Чтобы устранить эти ограничения, в Milvus 2.6.1 появился режим гибкого развертывания индекса GPU_CAGRA с помощью параметра adapt_for_cpu. Этот режим обеспечивает гибридный рабочий процесс: CAGRA использует GPU для построения высококачественного индекса графов, а выполнение запросов происходит на CPU - как правило, с использованием HNSW в качестве алгоритма поиска.

При таком подходе GPU используются там, где они приносят наибольшую пользу - быстрое и высокоточное построение индексов, в то время как CPU справляются с крупномасштабными запросами гораздо более экономичным и масштабируемым способом.

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

• Обновление данных происходит нечасто, поэтому перестройка индексов происходит редко

• Объем запросов высок и требует большого количества недорогих реплик

• Высокая чувствительность к затратам, и использование GPU должно жестко контролироваться.

Понимание adapt_for_cpu

В Milvus параметр adapt_for_cpu управляет тем, как индекс CAGRA сериализуется на диск во время построения индекса и как он десериализуется в память во время загрузки. Изменяя этот параметр во время сборки и во время загрузки, Milvus может гибко переключаться между построением индекса на базе GPU и выполнением запроса на базе CPU.

Различные комбинации adapt_for_cpu во время сборки и во время загрузки приводят к четырем режимам выполнения, каждый из которых предназначен для определенного сценария работы.

Время построения (adapt_for_cpu)	Время загрузки (adapt_for_cpu)	Логика выполнения	Рекомендуемый сценарий
истинный	верно	Сборка на GPU_CAGRA → сериализация в HNSW → десериализация в HNSW → обработка запросов на CPU	Рабочие нагрузки, чувствительные к затратам; крупномасштабное обслуживание запросов
true	ложь	Сборка с GPU_CAGRA → сериализация как HNSW → десериализация как HNSW → обработка запросов на CPU	Последующие запросы возвращаются на CPU при несовпадении параметров
false	true	Построение с помощью GPU_CAGRA → сериализация как CAGRA → десериализация как HNSW → запросы к CPU	Сохранение исходного индекса CAGRA для хранения, обеспечивая временный поиск на CPU
false	false	Построение с помощью GPU_CAGRA → сериализация как CAGRA → десериализация как CAGRA → запросы на GPU	Критичные по производительности рабочие нагрузки, где стоимость имеет второстепенное значение

Примечание: Механизм adapt_for_cpu поддерживает только одностороннее преобразование. Индекс CAGRA может быть преобразован в HNSW, поскольку структура графа CAGRA сохраняет все отношения между соседями, необходимые HNSW. Однако индекс HNSW не может быть преобразован обратно в CAGRA, поскольку в нем отсутствует дополнительная структурная информация, необходимая для запросов на основе GPU. Поэтому настройки времени сборки следует выбирать тщательно, с учетом долгосрочного развертывания и требований к запросам.

Испытание GPU_CAGRA на прочность

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

Экспериментальная установка

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

• ПРОЦЕССОР: Процессор MD EPYC 7R13 (16 процессоров)

• GPU: NVIDIA L4

1. Производительность построения индекса

Мы сравниваем CAGRA, построенный на GPU, с HNSW, построенным на CPU, при одинаковой целевой степени графа 64.

Основные результаты

• GPU CAGRA строит индексы на 12-15× быстрее, чем CPU HNSW. Как на Cohere1M, так и на Gist1M, CAGRA на базе GPU значительно превосходит HNSW на базе CPU, что подчеркивает эффективность параллелизма GPU при построении графов.

• Время построения линейно увеличивается с количеством итераций NN-Descent. По мере увеличения числа итераций время построения растет почти линейно, что отражает итерационную природу NN-Descent и обеспечивает предсказуемый компромисс между стоимостью построения и качеством графа.

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

В этом эксперименте граф CAGRA строится один раз на GPU, а затем запрашивается с использованием двух различных путей выполнения:

• Запрос на CPU: индекс десериализуется в формат HNSW и поиск выполняется на CPU.

• Запрос на GPU: поиск выполняется непосредственно в графе CAGRA с использованием обхода на базе GPU.

Основные результаты

• Пропускная способность поиска на GPU в 5-6 раз выше, чем на CPU. Как в Cohere1M, так и в Gist1M, обход графа на основе GPU обеспечивает значительно более высокий QPS, что подчеркивает эффективность параллельной навигации по графу на GPU.

• Recall увеличивается с числом итераций NN-Descent, а затем достигает плато. По мере роста числа итераций построения запоминание улучшается как для запросов на CPU, так и на GPU. Однако после определенного момента дополнительные итерации дают все меньший выигрыш, указывая на то, что качество графа в основном сходится.

3. Точность запоминания

В этом эксперименте оба графа - CAGRA и HNSW - запрашиваются на CPU, чтобы сравнить точность запоминания при одинаковых условиях запроса.

Основные результаты

CAGRA достигает более высокой точности запоминания, чем HNSW, на обоих наборах данных, показывая, что даже когда индекс CAGRA создается на GPU и десериализуется для поиска на CPU, качество графа хорошо сохраняется.

Что дальше: Масштабирование построения индексов с помощью Vamana

Гибридный GPU-CPU подход Milvus предлагает практичное и экономически эффективное решение для современных крупномасштабных рабочих нагрузок векторного поиска. Построение высококачественных графов CAGRA на GPU и обслуживание запросов на CPU позволяет сочетать быстрое построение индексов с масштабируемым и доступным выполнением запросов, что особеннохорошо подходит для рабочих нагрузок с нечастыми обновлениями, большими объемами запросов и жесткими ограничениями по стоимости.

При еще больших масштабах - десяткиили сотни миллиардов векторов -построениеиндексасамо по себе становится узким местом. Когда полный набор данных уже не помещается в память GPU, индустрия обычно обращается к методам построения графов на основе вставок, таким как Vamana. Вместо того чтобы строить граф сразу, Vamana обрабатывает данные партиями, постепенно вставляя новые векторы, сохраняя при этом глобальную связность.

Конвейер построения графа состоит из трех ключевых этапов:

1. Геометрическое наращивание партий - начиная с небольших партий для формирования скелета графа, затем увеличивая размер партии, чтобы максимизировать параллелизм, и, наконец, используя большие партии для уточнения деталей.

2. Жадная вставка - каждый новый узел вставляется путем навигации от центральной точки входа, итеративно уточняя набор своих соседей.

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

Обрезка интегрирована непосредственно в процесс построения с помощью критерия α-RNG: если сосед-кандидат v уже покрыт существующим соседом p′ (т. е. d(p′, v) < α × d(p, v)), то v обрезается. Параметр α позволяет точно контролировать разреженность и точность. Ускорение на GPU достигается за счет внутрипакетного параллелизма и геометрического масштабирования пакетов, что позволяет найти баланс между качеством индекса и пропускной способностью.

Вместе эти методы позволяют командам справляться с быстрым ростом данных и масштабными обновлениями индексов, не сталкиваясь с ограничениями памяти GPU.

Команда Milvus активно разрабатывает поддержку Vamana и планирует выпустить ее в первой половине 2026 года. Следите за новостями.

У вас есть вопросы или вы хотите получить подробную информацию о любой функции последней версии Milvus? Присоединяйтесь к нашему каналу Discord или создавайте проблемы на GitHub. Вы также можете записаться на 20-минутную индивидуальную сессию, чтобы получить знания, рекомендации и ответы на свои вопросы в Milvus Office Hours.

Подробнее о возможностях Milvus 2.6

• Представляем Milvus 2.6: доступный векторный поиск в миллиардных масштабах

• Представляем функцию встраивания: Как Milvus 2.6 оптимизирует векторизацию и семантический поиск

• Измельчение JSON в Milvus: 88,9-кратное ускорение фильтрации JSON с гибкостью

• Разблокирование истинного поиска на уровне сущностей: Новые возможности Array-of-Structs и MAX_SIM в Milvus

• MinHash LSH в Milvus: секретное оружие для борьбы с дубликатами в обучающих данных LLM

• Доведите векторное сжатие до крайности: как Milvus обслуживает в 3 раза больше запросов с помощью RaBitQ

• Бенчмарки лгут - векторные БД заслуживают реальной проверки

• Мы заменили Kafka/Pulsar на Woodpecker для Milvus