Как Milvus планирует задачи запросов
В этой статье мы обсудим, как Milvus планирует задачи запросов. Мы также поговорим о проблемах, решениях и будущих направлениях реализации планирования в Milvus.
Предыстория
Из Managing Data in Massive-Scale Vector Search Engine мы знаем, что поиск по векторному сходству реализуется через расстояние между двумя векторами в многомерном пространстве. Цель векторного поиска — найти K векторов, наиболее близких к целевому вектору.
Существует множество способов измерения расстояния между векторами, например евклидово расстояние:
Евклидово расстояние.
где x и y — два вектора. n — размерность векторов.
Чтобы найти K ближайших векторов в наборе данных, необходимо вычислить евклидово расстояние между целевым вектором и всеми векторами в наборе данных, в котором выполняется поиск. Затем векторы сортируются по расстоянию, чтобы получить K ближайших векторов. Объем вычислительной работы прямо пропорционален размеру набора данных. Чем больше набор данных, тем больше вычислительной работы требуется для запроса. GPU, специализированный для обработки графики, как раз имеет множество ядер, обеспечивающих необходимую вычислительную мощность. Поэтому поддержка нескольких GPU также учитывается при реализации Milvus.
Основные понятия
Блок данных（TableFile）
Чтобы улучшить поддержку поиска по данным массивного масштаба, мы оптимизировали хранение данных в Milvus. Milvus разделяет данные в таблице по размеру на несколько блоков данных. Во время векторного поиска Milvus ищет векторы в каждом блоке данных и объединяет результаты. Одна операция векторного поиска состоит из N независимых операций векторного поиска (N — количество блоков данных) и N-1 операций объединения результатов.
Очередь задач（TaskTable）
У каждого Resource есть массив задач, в котором записываются задачи, принадлежащие этому Resource. У каждой задачи есть разные состояния, включая Start, Loading, Loaded, Executing и Executed. Loader и Executor на вычислительном устройстве используют одну и ту же очередь задач.
Планирование запросов
Планирование запросов.
- Когда сервер Milvus запускается, Milvus запускает соответствующий GpuResource через параметры
gpu_resource_configв конфигурационном файлеserver_config.yaml. DiskResource и CpuResource по-прежнему нельзя редактировать вserver_config.yaml. GpuResource представляет собой комбинациюsearch_resourcesиbuild_index_resourcesи в следующем примере обозначается как{gpu0, gpu1}:
Пример кода.
Пример.
- Milvus получает запрос. Метаданные таблицы хранятся во внешней базе данных: SQLite или MySQl для одного хоста и MySQL для распределенного режима. После получения поискового запроса Milvus проверяет, существует ли таблица и совпадает ли размерность. Затем Milvus считывает список TableFile таблицы.
Milvus считывает список tablefile.
- Milvus создает SearchTask. Поскольку вычисление для каждого TableFile выполняется независимо, Milvus создает SearchTask для каждого TableFile. Будучи базовой единицей планирования задач, SearchTask содержит целевые векторы, параметры поиска и имена файлов TableFile.
Создатель задач списка файлов таблицы.
- Milvus выбирает вычислительное устройство. Устройство, на котором SearchTask выполняет вычисление, зависит от оценочного времени завершения для каждого устройства. Оценочное время завершения указывает предполагаемый интервал между текущим временем и предполагаемым моментом завершения вычисления.
Например, когда блок данных SearchTask загружается в память CPU, следующая SearchTask ожидает в очереди задач вычислений CPU, а очередь задач вычислений GPU простаивает. Расчетное время завершения для CPU равно сумме расчетной временной стоимости предыдущей SearchTask и текущей SearchTask. Расчетное время завершения для GPU равно сумме времени загрузки блоков данных в GPU и расчетной временной стоимости текущей SearchTask. Расчетное время завершения для SearchTask в Resource равно среднему времени выполнения всех SearchTasks в Resource. Затем Milvus выбирает устройство с наименьшим расчетным временем завершения и назначает SearchTask этому устройству.
Здесь мы предполагаем, что расчетное время завершения для GPU1 меньше.
GPU1 shorter estimated completion time.
Milvus добавляет SearchTask в очередь задач DiskResource.
Milvus перемещает SearchTask в очередь задач CpuResource. Поток загрузки в CpuResource последовательно загружает каждую задачу из очереди задач. CpuResource считывает соответствующие блоки данных в память CPU.
Milvus перемещает SearchTask в GpuResource. Поток загрузки в GpuResource копирует данные из памяти CPU в память GPU. GpuResource считывает соответствующие блоки данных в память GPU.
Milvus выполняет SearchTask в GpuResource. Поскольку результат SearchTask относительно мал, результат напрямую возвращается в память CPU.
Scheduler.
- Milvus объединяет результат SearchTask с общим результатом поиска.
Milvus merges search task results.
После завершения всех SearchTasks Milvus возвращает общий результат поиска клиенту.
Построение индекса
Построение индекса в основном аналогично процессу поиска, но без процесса объединения. Мы не будем подробно говорить об этом.
Оптимизация производительности
Кэш
Как упоминалось ранее, блоки данных необходимо загрузить на соответствующие устройства хранения, такие как память CPU или память GPU, перед вычислением. Чтобы избежать повторной загрузки данных, Milvus вводит кэш LRU (Least Recently Used). Когда кэш заполнен, новые блоки данных вытесняют старые блоки данных. Вы можете настроить размер кэша с помощью файла конфигурации на основе текущего размера памяти. Для эффективной экономии времени загрузки данных и повышения производительности поиска рекомендуется использовать большой кэш для хранения поисковых данных.
Перекрытие загрузки данных и вычислений
Кэш не может удовлетворить наши потребности в более высокой производительности поиска. Данные необходимо перезагружать, когда памяти недостаточно или размер набора данных слишком велик. Нам нужно уменьшить влияние загрузки данных на производительность поиска. Загрузка данных, будь то с диска в память CPU или из памяти CPU в память GPU, относится к операциям ввода-вывода и почти не требует вычислительной работы от процессоров. Поэтому мы рассматриваем возможность параллельного выполнения загрузки данных и вычислений для лучшего использования ресурсов.
Мы разделяем вычисление на блоке данных на 3 этапа (загрузка с диска в память CPU, вычисление CPU, объединение результатов) или 4 этапа (загрузка с диска в память CPU, загрузка из памяти CPU в память GPU, вычисление GPU и получение результатов, а также объединение результатов). Рассмотрим в качестве примера 3-этапное вычисление: мы можем запустить 3 потока, отвечающих за 3 этапа, чтобы они функционировали как конвейер команд. Поскольку наборы результатов в основном малы, объединение результатов не занимает много времени. В некоторых случаях перекрытие загрузки данных и вычислений может сократить время поиска на 1/2.
Sequential overlapping load Milvus.
Проблемы и решения
Разные скорости передачи
Ранее Milvus использовал стратегию Round Robin для планирования задач на нескольких GPU. Эта стратегия отлично работала на нашем сервере с 4 GPU, и производительность поиска была в 4 раза выше. Однако для наших хостов с 2 GPU производительность не была в 2 раза выше. Мы провели несколько экспериментов и обнаружили, что скорость копирования данных для одного GPU составляла 11 ГБ/с. Однако для другого GPU она составляла 3 ГБ/с. Обратившись к документации материнской платы, мы подтвердили, что материнская плата была подключена к одному GPU через PCIe x16, а к другому GPU — через PCIe x4. Иными словами, эти GPU имеют разную скорость копирования. Позже мы добавили время копирования для определения оптимального устройства для каждой SearchTask.
Планы на будущее
Аппаратная среда с возросшей сложностью
В реальных условиях аппаратная среда может быть более сложной. Для аппаратных сред с несколькими CPU, памятью с архитектурой NUMA, NVLink и NVSwitch взаимодействие между CPU/GPU предоставляет множество возможностей для оптимизации.
Оптимизация запросов
В ходе экспериментов мы обнаружили некоторые возможности для повышения производительности. Например, когда сервер получает несколько запросов к одной и той же таблице, при определенных условиях эти запросы можно объединить. Используя локальность данных, мы можем повысить производительность. Эти оптимизации будут реализованы в ходе нашей будущей разработки. Теперь мы уже знаем, как запросы планируются и выполняются в сценарии с одним хостом и несколькими GPU. В следующих статьях мы продолжим рассказывать о внутренних механизмах Milvus.
Читать далее
Zilliz Cloud Delivers Better Performance and Lower Costs with Arm Neoverse-based AWS Graviton
Zilliz Cloud adopts Arm-based AWS Graviton3 CPUs to cut costs, speed up AI vector search, and power billion-scale RAG and semantic search workloads.
What Exactly Are AI Agents? Why OpenAI and LangChain Are Fighting Over Their Definition?
AI agents are software programs powered by AI that can perceive their environment, make decisions, and take actions to achieve a goal—often autonomously.
VidTok: Rethinking Video Processing with Compact Tokenization
VidTok tokenizes videos to reduce redundancy while preserving spatial and temporal details for efficient processing.