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

Эффективное использование потоковой передачи данных для тестирования векторных баз данных

Почему статическая нагрузка недостаточна и чего я узнал, сравнивая HNSWLIB и DiskANN с использованием потоковой нагрузки

Изображение от DALLE-3

Векторные базы данных созданы для извлечения векторов с высокой размерностью. Сегодня многие векторы представляют собой вложения, созданные глубокими нейронными сетями, такими как GPTы и CLIP, чтобы представлять данные, такие как текстовые фрагменты, изображения или звуковые дорожки. Вложения используются во многих приложениях, таких как поисковые системы, рекомендательные системы и чат-боты. Вы можете индексировать вложения в векторной базе данных, которая использует индекс ближайших соседей (ANN) для быстрого извлечения лучших соседей с использованием функции расстояния, такой как косинусное или евклидово. Задержка составляет от 2 до 10 миллисекунд для индекса из 1 миллиона векторов и масштабируется сублинейно (т.е. O(log n)) в отношении размера индекса.

В этом посте я указываю на несколько проблем с оценкой индексов ANN, используемых в настоящее время, и предлагаю новый тип оценки. В этом посте фокусировка идет на индексах ANN для векторов вложения, области, которая недавно привлекла много внимания: стартапы векторных баз данных, такие как Pinecone, Zilliz, Qdrant и Weaviate предлагают индексирование и извлечение вложений в качестве своей основной услуги.

1. Статический нагрузочный тест недостаточен.

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

Статический нагрузочный тест. Изображение от автора.

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

Иллюстрация из ANN Benchmarks (11/25/2023). MIT Лицензия.

На приведенном выше графике сравниваются различные индексы ANN с использованием статического нагрузочного теста под названием glove-100-angular, который содержит вложения слов.

Этот подход к оценке стал популярным благодаря проекту ann-benchmarks, который был запущен 5 лет назад. Многие векторные базы данных сейчас измеряют свою производительность, используя этот подход в своих технических блогах. См. бенчмарк Qdrant и бенчмарк Timescale.

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

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

Отражение производительности индексации.

Производительность индексации измеряет, насколько быстро индекс ANN способен принимать новые данные. Она обычно обратно коррелирует с точностью повторного вызова. Например, на графике ниже показана зависимость между производительностью индексации и повторным вызовом индексов HNSWLIB и DiskANN Vamana.

Точность повторного вызова против производительности индексации HNSWLIB и DiskANN Vamana на наборе данных OpenAI 1М. Изображение автора.

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

Многие индексы ANN поддерживают API массовой индексации, которая может быть намного более оптимизирована, чем индексация точек (то есть добавление векторов один за другим), и могут создавать более точный индекс. Например, индексы ANN, основанные на кластерах, создают кластеры всех векторов пакетно. Статический бенчмарк-тестирование разделяет работу индексации и выполнение запросов, поэтому оно поощряет массовую индексацию, которая может быть не реалистичной.

Еще одной проблемой, связанной с индексацией, является квантование продукта (PQ). Многие индексы ANN используют PQ или другие формы сжатия векторов для ускорения вычислений. Статический бенчмарк-тестирование позволяет индексам ANN создавать оптимизированный кодбук перед фазой запроса, однако подобный оптимальный кодбук может быть недостижим на практике.

Важно использование памяти.

Большинство популярных индексов ANN находятся в памяти, то есть их основная структура данных хранится в переходящей памяти (DRAM), из которой выполняются запросы. Поэтому важно измерять эффективность использования памяти и ее компромисс с производительностью и точностью повторного вызова. Например, в этой научной статье авторы измерили использование памяти у HNSW с 1 миллиардом точек в размере 490 ГБ, в то время как NSG в размере 303 ГБ, но с точки зрения производительности и повторного вызова HNSW лишь незначительно превосходит NSG. Такой компромисс должен быть в центре внимания при проведении бенчмарков для индексов ANN.

Тем не менее, с помощью только статического бенчмарка сложно получить реалистичное представление об эффективности использования памяти по нескольким причинам. Во-первых, алгоритм индекса ANN может создать индекс, оптимизированный для операций чтения, который очень компактен за счет последующей производительности индексации. Во-вторых, рабочая нагрузка только фиксирует чистую индексацию или чистый запрос, но не их смесь, что более вероятно в реальном сценарии, например, как в системах Q&A или чат-ботах, когда поступают постоянно новые данные.

Распределение данных меняется со временем.

В статическом бенчмарк-тестировании наборы данных и запросов не меняются. Но это не реалистично, так как данные и запросы определяются интересами конечных пользователей, которые меняются со временем. Если наборы данных и запросов всегда остаются неизменными, то лучший индекс – это кэш, который запоминает результат каждого запроса. Недавно в исследованиях по индексам ANN (например, FreshDiskANN) стали использовать оценку производительности запросов, которые выходят за пределы распределения данных — это положительный шаг вперед.

Что насчет удалений?

API удаления стало стандартом для индексов ANN, но ни один статический бенчмарк не измеряет это. Возможность обработки удалений важна, так как в новых сценариях, связанных с искусственным интеллектом, например, в чат-ботах, используется индекс ANN в качестве операционного хранилища, которое напоминает онлайн-транзакционные обработки (OLTP), потому что данные постоянно добавляются и изменяются.

2. Потоковая нагрузка дает вам намного больше информации.

Если индекс ANN поддерживает следующие API:

  • Insert(ID, вектор)
  • Query(вектор)
  • Delete(ID)

и если сценарий использования отличается от статических данных и запросов (как во всех сценариях?), то потоковый тестовый набор может дать вам больше информации о характеристиках индексов ANN и о том, насколько они хорошо работают в вашем конкретном сценарии использования.

Потоковый тестовый набор состоит из двух потоков: потока данных, который соответствует последовательности вызовов API Insert и Delete, и потока запросов для последовательности вызовов API Query. Его можно реализовать с использованием фактической потоковой системы, такой как Kafka, или более просто с использованием задания с последовательностями указателей на набор данных и набор запросов, аналогичных использованным в статическом тестовом наборе.

Простой потоковый тестовый набор, использующий задание. Изображение автора.

Вышеуказанная диаграмма иллюстрирует потоковый тестовый набор, используемый в Заданиях Big ANN NeurIPS 23′. Конкретно, каждый шаг в задании соответствует пакету векторов, поэтому операции могут выполняться параллельно. У этого подхода есть следующие преимущества:

  1. Гибкость: образцы рабочей нагрузки и смещения распределения данных могут быть моделированы как различные потоковые тестовые наборы, которые затем компилируются в разные задания.
  2. Реалистичность: индексация и запросы выполняются взаимно, поэтому индекс ANN должен учитывать будущие вставки. Кроме того, профиль памяти более точно отражает реальную нагрузку.
  3. Простой анализ: производительность может быть описана с использованием общей пропускной способности вместо пропускной способности индексации по сравнению с запросной пропускной способностью, поэтому компромисс между recall и производительностью можно легко визуализировать.
  4. Полнота: также оцениваются операции вставки и удаления.

В этом блоге я углублюсь в (4) вышеперечисленное и покажу вам новое открытие, которое я сделал с использованием потокового тестового набора.

Сравнение устойчивости recall: HNSW против Vamana

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

Я измерил устойчивость recall для Vamana из DiskANN и различных реализаций HNSW в потоковом тестовом наборе, заданном окончательным заданием в Заданиях Big ANN NeurIPS 23′.

Немного информации о Vamana и HNSW: они оба являются графовыми индексами ANN и особенно хорошо работают с эмбеддингами. В графовом индексе ANN каждый вектор является узлом, и запрос выполняется как обход графа. Направленные ребра строятся с выборочным подходом для ограничения использования памяти, при этом гарантируется быстрый обход от любого узла к любому узлу. Во время удаления “на месте” в графовых индексах ANN выполняется ремонт ребер для поддержания направленной структуры графа для каждого входящего соседнего узла удаленного узла.

Первая реализация HNSW, которую мы используем, основана на HNSWLIB и имеет реализованный API Delete с использованием алгоритма ремонта, называемого repairConnectionsForUpdate, который уже является частью исходного кода HNSWLIB. Идея заключается в выполнении “повторной вставки” восстановления узла и обновлении его исходящих соседей на всех уровнях. Ниже показана устойчивость recall для Vamana и HNSW.

Устойчивость recall DiskANN's Vamana и реализация HNSW, основанная на HNSWLIB. Вызовы API Delete обозначены как «X». Изображение автора.

Обратите внимание, что я настроил параметр максимальной степени Vamana на 40 (R = 40), а также максимальную степень основного слоя HNSW на 40 (M = 20, M0 = 40). Таким образом, они должны использовать примерно одинаковое количество памяти.

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

Вторая реализация HNSW, которую мы используем, заменяет алгоритм восстановления ребер HNSWLIB на алгоритм Vamana, который является весьма отличным. Идея, стоящая за алгоритмом восстановления ребер Vamana, заключается в соединении каждого входящего соседа удаленного узла с исходящими соседями удаленного узла с применением этапа обрезки для поддержания ограничения максимальной степени. В этом случае мы используем оригинальный алгоритм обрезки HNSW. Он реализован в HNSWLIB в функции под названием getNeighborsByHeuristic2.

Устойчивость полноты DiskANN’s Vamana и реализации HNSW, использующей алгоритм восстановления ребер Vamana для обработки удаления. Изображение авторов.

При сохранении всех параметров в исходном состоянии замена алгоритма восстановления ребер HNSWLIB на алгоритм Vamana сразу же улучшила устойчивость полноты HNSW.

Давайте пройдем еще дальше и заменим алгоритм обрезки ребер HNSW на алгоритм Vamana. Теперь индекс HNSW практически совпадает с Vamana за исключением наличия нескольких слоев. Мы называем этот индекс “Мульти-слойный Vamana”.

Устойчивость полноты DiskANN’s Vamana и реализации HNSW, использующей алгоритм восстановления и обрезки ребер Vamana - «мульти-слойный Vamana». Изображение авторов.

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

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

3. Заключение

В заключение этого блог-поста, я указал на то, что статические тестовые нагрузки недостаточны для реалистичной оценки индексов ANN, и описал тестовую нагрузку в режиме потоковых данных, которая, по моему мнению, является лучшей заменой. Я также использовал конкретную тестовую нагрузку в режиме потоковых данных, чтобы открыть новое сравнение между индексами HNSW и Vamana. Огромное спасибо команде за 23′ Big ANN Benchmarks на конференции NeurIPS! Они опубликовали в открытом доступе тестовую нагрузку в режиме потоковых данных, которую я использовал в этом блог-посте.

Нам нужны TPC-C и TPC-H для векторных баз данных.

В области тестирования все еще много работы. Индекс ANN является основной функцией векторных баз данных, и на их разработку было собрано более 350 миллионов долларов. Однако многие из них все еще используют устаревший подход к измерению производительности, который уже не отражает реальных сценариев использования. Базы данных прошли аналогичный этап в 90-х и начале 2000-х годов. Тогда были созданы стандартные бенчмарки, такие как TPC-C и TPC-H, которые по-прежнему используются сегодня. У нас должно быть что-то подобное для векторных баз данных.