🚀 Попробуйте Zilliz Cloud, полностью управляемый Milvus, бесплатно — ощутите 10-кратное увеличение производительности! Попробовать сейчас>

milvus-logo
LFAI
  • Home
  • Blog
  • Справочная информация

Справочная информация

  • Engineering
March 03, 2020
milvus

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

Справочная информация

Из книги Managing Data in Massive-Scale Vector Search Engine мы знаем, что векторный поиск сходства осуществляется по расстоянию между двумя векторами в высокоразмерном пространстве. Цель векторного поиска - найти K векторов, которые наиболее близки к целевому вектору.

Существует множество способов измерения векторного расстояния, например евклидово расстояние:

1-euclidean-distance.png 1-euclidean-distance.png

где x и y - два вектора. n - размерность векторов.

Для того чтобы найти K ближайших векторов в наборе данных, необходимо вычислить евклидово расстояние между целевым вектором и всеми векторами в наборе данных, по которым ведется поиск. Затем векторы сортируются по расстоянию, чтобы получить K ближайших векторов. Вычислительная работа прямо пропорциональна размеру набора данных. Чем больше набор данных, тем больше вычислительной работы требует запрос. Графический процессор, специализированный для обработки графов, обладает большим количеством ядер, чтобы обеспечить необходимую вычислительную мощность. Таким образом, поддержка нескольких GPU также учитывается при реализации Milvus.

Основные понятия

Блок данных(TableFile)

Чтобы улучшить поддержку поиска данных в больших объемах, мы оптимизировали хранение данных в Milvus. Milvus разбивает данные в таблице по размеру на несколько блоков данных. Во время векторного поиска Milvus ищет векторы в каждом блоке данных и объединяет результаты. Одна операция векторного поиска состоит из N независимых операций векторного поиска (N - количество блоков данных) и N-1 операций слияния результатов.

Очередь задач(TaskTable)

Каждый ресурс имеет массив задач, в который записываются задачи, принадлежащие данному ресурсу. Каждая задача имеет различные состояния, включая Start, Loading, Loaded, Executing и Executed. Загрузчик и исполнитель на вычислительном устройстве используют одну и ту же очередь задач.

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

2-query-scheduling.png 2-query-scheduling.png

  1. Когда сервер Milvus запускается, Milvus запускает соответствующий ресурс GpuResource через параметры gpu_resource_config в конфигурационном файле server_config.yaml. DiskResource и CpuResource по-прежнему нельзя редактировать в server_config.yaml. GpuResource представляет собой комбинацию search_resources и build_index_resources и в следующем примере обозначается как {gpu0, gpu1}:

3-sample-code.png 3-sample-code.png

3-example.png 3-example.png

  1. Milvus получает запрос. Метаданные таблицы хранятся во внешней базе данных, в качестве которой выступают SQLite или MySQl для однохостовых систем и MySQL для распределенных. Получив запрос на поиск, Milvus проверяет, существует ли таблица и соответствует ли размерность. Затем Milvus считывает список TableFile таблицы.

4-milvus-reads-tablefile-list.png 4-milvus-reads-tablefile-list.png

  1. Milvus создает задачу SearchTask. Поскольку вычисление каждого TableFile выполняется независимо, Milvus создает SearchTask для каждого TableFile. Как основная единица планирования задач, SearchTask содержит целевые векторы, параметры поиска и имена файлов TableFile.

5-table-file-list-task-creator.png 5-table-file-list-task-creator.png

  1. Milvus выбирает вычислительное устройство. Устройство, на котором выполняется вычисление в SearchTask, зависит от предполагаемого времени завершения для каждого устройства. Расчетное время завершения определяет предполагаемый интервал между текущим временем и предполагаемым временем завершения вычислений.

Например, когда блок данных задачи SearchTask загружается в память CPU, следующая задача SearchTask ожидает в очереди вычислительных задач CPU, а очередь вычислительных задач GPU простаивает. Расчетное время завершения для CPU равно сумме расчетных временных затрат предыдущей SearchTask и текущей SearchTask. Расчетное время завершения для GPU равно сумме времени загрузки блоков данных на GPU и расчетной временной стоимости текущей задачи SearchTask. Расчетное время выполнения задачи поиска в ресурсе равно среднему времени выполнения всех задач поиска в ресурсе. Затем Milvus выбирает устройство с наименьшим расчетным временем выполнения и назначает SearchTask на это устройство.

Здесь мы предполагаем, что расчетное время завершения для GPU1 короче.

6-GPU1-shorter-estimated-completion-time.png 6-GPU1-shorter-estimated-completion-time.png

  1. Milvus добавляет SearchTask в очередь задач DiskResource.

  2. Milvus перемещает SearchTask в очередь задач CpuResource. Поток загрузки в CpuResource последовательно загружает каждую задачу из очереди задач. CpuResource считывает соответствующие блоки данных в память процессора.

  3. Milvus перемещает SearchTask в GpuResource. Загрузочный поток в GpuResource копирует данные из памяти CPU в память GPU. GpuResource считывает соответствующие блоки данных в память GPU.

  4. Milvus выполняет SearchTask в GpuResource. Поскольку результат выполнения SearchTask относительно невелик, он возвращается непосредственно в память CPU.

7-scheduler.png 7-scheduler.png

  1. Milvus объединяет результат выполнения SearchTask с результатом поиска в целом.

8-milvus-merges-searchtast-result.png 8-milvus-merges-searchtast-result.png

После завершения всех SearchTasks Milvus возвращает клиенту весь результат поиска.

Построение индексов

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

Оптимизация производительности

Кэш

Как уже упоминалось, перед вычислениями блоки данных необходимо загружать на соответствующие устройства хранения, такие как память CPU или GPU. Чтобы избежать повторной загрузки данных, Milvus вводит кэш LRU (Least Recently Used). Когда кэш заполняется, новые блоки данных вытесняют старые. Размер кэша можно настроить в конфигурационном файле в зависимости от текущего объема памяти. Рекомендуется использовать большой кэш для хранения данных поиска, чтобы эффективно сократить время загрузки данных и повысить производительность поиска.

Дублирование загрузки данных и вычислений

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

Мы разбиваем вычисления над блоком данных на 3 этапа (загрузка с диска в память CPU, вычисления CPU, объединение результатов) или 4 этапа (загрузка с диска в память CPU, загрузка из памяти CPU в память GPU, вычисления и получение результатов на GPU, объединение результатов). Если взять в качестве примера трехэтапные вычисления, то мы можем запустить 3 потока, отвечающих за 3 этапа, чтобы обеспечить конвейеризацию инструкций. Поскольку наборы результатов в основном невелики, объединение результатов не занимает много времени. В некоторых случаях перекрытие загрузки данных и вычислений может сократить время поиска на 1/2.

9-sequential-overlapping-load-milvus.png 9-sequential-overlapping-load-milvus.png

Проблемы и решения

Разные скорости передачи данных

Ранее Milvus использовал стратегию Round Robin для планирования задач на нескольких GPU. Эта стратегия отлично работала на нашем 4-GPU сервере, и производительность поиска была в 4 раза выше. Однако на наших хостах с 2 GPU производительность была не в 2 раза выше. Мы провели несколько экспериментов и обнаружили, что скорость копирования данных для одного GPU составляет 11 ГБ/с. Однако для другого GPU она составляла 3 ГБ/с. Обратившись к документации на материнскую плату, мы убедились, что она подключена к одному GPU через PCIe x16, а к другому - через PCIe x4. То есть эти GPU имеют разную скорость копирования. Позже мы добавили время копирования, чтобы определить оптимальное устройство для каждой задачи SearchTask.

Будущая работа

Аппаратное окружение повышенной сложности

В реальных условиях аппаратная среда может быть более сложной. В аппаратных средах с несколькими CPU, памятью с архитектурой NUMA, NVLink и NVSwitch взаимодействие между CPU/GPU открывает широкие возможности для оптимизации.

Оптимизация запросов

В ходе экспериментов мы обнаружили несколько возможностей для повышения производительности. Например, когда сервер получает несколько запросов к одной и той же таблице, при определенных условиях их можно объединить. Используя локальность данных, мы можем повысить производительность. Эти оптимизации будут реализованы в наших будущих разработках. Сейчас мы уже знаем, как планируются и выполняются запросы для сценария с одним хостом и несколькими GPU. Мы продолжим знакомить вас с внутренними механизмами Milvus в следующих статьях.

Like the article? Spread the word

Продолжить чтение