Из этого материала вы узнаете о том, как работают векторные базы данных, разобравшись с широким диапазоном тем — от основ поиска по сходству, до стратегий индексирования, которые позволяют применять на практике крупномасштабный поиск данных.
Среди вопросов, которые мы здесь рассмотрим, можно отметить следующие:
Как эмбеддинги преобразуют неструктурированные данные в векторы, поддерживающие поиск по сходству.
Как в векторных базах данных организованы поиск ближайших соседей и фильтрация по метаданным, как работают технологии гибридного поиска.
Как применение таких методов индексирования данных, как HNSW, IVF и PQ помогает масштабировать векторный поиск в продакшн-средах.
Введение
Традиционные базы данных предназначены для получения ответов на чётко сформулированные вопросы такого плана: «Существует ли запись, которая соответствует таким вот критериям?». А вот векторные базы данных ищут ответы на вопросы вроде «Какая запись сильнее всего похожа на вот такую запись?». Этот сдвиг чрезвычайно важен из-за того, что в применении к огромному классу современных наборов данных невозможно организовать поиск по точному совпадению критериев. Среди таких данных — документы, изображения, описания особенностей поведения пользователей, аудиозаписи. Поэтому при работе с ними корректным будет не запрос вида «найди это», а запрос «найди то, что к этому близко». Возможность организации именно такого поиска обеспечивают модели эмбеддингов. Они преобразуют исходные данные в наборы векторов, при работе с которыми их геометрическая близость соответствует их семантической схожести.
Основная проблема применения векторных баз данных кроется в масштабах данных, которые хотят с их помощью обрабатывать. В продакшн-средах, где работают с большими наборами данных, сравнение вектора, представляющего собой запрос, с каждым из сохранённых векторов означает необходимость выполнения миллиардов операций на числах с плавающей запятой. Это лишает практической полезности выполнение операций поиска в реальном времени. Векторные базы данных решают данную проблему с использованием алгоритмов приближённого поиска ближайших соседей. Такие алгоритмы отбрасывают подавляющее большинство векторов-кандидатов и при этом возвращают результаты, почти идентичные тем, что получаются при полном переборе вариантов, затрачивая на это гораздо меньше вычислительных ресурсов.
Здесь мы рассматриваем особенности работы векторных баз данных на трёх уровнях технологий. Первый представлен описанием базовой задачи поиска сходства объектов и рассмотрением того, чем в её решении может помочь применение векторов. Второй — это уровень, к которому относятся продакшн-системы, способы хранения эмбеддингов, методы выполнения запросов с применением фильтрации и гибридного поиска. Третий — алгоритмы индексирования и архитектурные решения, которые обеспечивают масштабируемость векторных баз данных.
Уровень 1: о задаче нахождения степени сходства объектов
Традиционные базы данных хранят структурированные данные, вроде целочисленных и строковых значений, организованные по строкам и столбцам. При извлечении информации из баз данных используются точные запросы или запросы, возвращающие заданные диапазоны данных. SQL — это язык, которые позволяет исчерпывающе описывать такие запросы и быстро получать ответы на них. Но множество разновидностей данных, описывающих реальный мир, структурированностью не отличаются. Текстовые документы, изображения, аудиозаписи, логи с данными о действиях пользователей — всё это примеры данных, которые не очень-то хорошо раскладываются по столбцам. При работе с такими данными не подходит поиск по точному совпадению.
Решение проблемы обработки подобных данных заключается в представлении их в виде векторов. Это — массивы фиксированной длины, содержащие числа с плавающей запятой. Модель эмбеддингов, вроде модели OpenAI text-embedding-3-small, или вроде какой-нибудь модели машинного зрения, преобразует исходные данные в векторы, которые отражают семантический смысл этих данных. Из схожих данных получаются схожие векторы. Например — слова «собака» и «щенок», после их преобразования, окажутся геометрически близкими друг к другу в векторном пространстве. То же относится и к изображениям, на одном из которых будет фото кота, а н другом — его рисунок.
Векторная база данных хранит подобные эмбеддинги (векторные представления данных) и позволяет организовывать поиск по их сходству. Например, запрос к подобной системе может выглядеть так: «Найди мне 10 векторов, ближе всего расположенных к заданному вектору». Это и называется «поиском ближайших соседей».
Уровень 2: хранение векторов и выполнения запросов к ним
Эмбеддинги
Прежде чем векторная база данных сможет функционировать, данные нужно преобразовать в векторы. Делается это с помощью моделей эмбеддингов. Это — нейронные сети, отображающие входные данные в плотное векторное пространство, размерность которого обычно варьируется от 256 до 4096, что зависит от используемой модели. Конкретные числа, содержащиеся в векторах, не поддаются прямой интерпретации. Важны лишь их геометрические характеристики: векторы, близкие друг к другу, описывают схожий контент.
Как это выглядит? Мы берём, например, документ, и передаём его модели, выполняющейся либо локально, либо удалённо, доступной через API. В ответ получаем массив чисел с плавающей запятой, который сохраняем вместе с метаданными документа.
Измерение расстояния между векторами
Мера сходства векторов — это геометрическое расстояние между ними. Существуют три наиболее распространённых подхода к измерению этого расстояния:
Косинусное сходство: при вычислении этого показателя измеряют угол между двумя векторами, не обращая внимания на их размеры. Он часто используется при работе с текстовыми эмбеддингами, где направление векторов важнее их размеров.
Евклидово расстояние: этот показатель отражает расстояние, представляющее собой длину отрезка в векторном пространстве. Он применяется в тех случаях, когда важны размеры векторов.
Скалярное произведение: вычисление этого показателя выполняется быстро, он хорошо себя показывает на нормализованных векторах. Многие модели эмбеддингов обучены в расчёте на его использование.
Выбор конкретного показателя должен соответствовать тому, как именно обучалась используемая модель. Применение неудачной метрики снижает качество результатов работы системы.
Задача поиска ближайшего соседа
Точное нахождение ближайших соседей — это, на маленьких наборах данных, задача очень простая. Вычисляем расстояние от вектора, переданного системе в запросе, до всех остальных векторов, далее — сортируем результаты и возвращаем первые K записей. Это — пример применения алгоритма грубой силы — поиска с полным перебором значений, который отличается 100% точностью. Сложность такого поиска линейно зависит от размеров набора данных. Если речь идёт о базе данных с 10 миллионами векторов, каждый из которых имеет 1536 измерений, то поиск с полным перебором значений — это слишком медленное решение для запросов, которые нужно обрабатывать в режиме реального времени.
Решить эту задачу позволяют алгоритмы приближённого поиска ближайших соседей (Approximate Nearest Neighbor, ANN). При их использовании идут на компромисс, немного теряя точность ради значительного увеличения скорости поиска. Реализации этих алгоритмов встроены в векторные базы данных, используемые на практике. Рассматривая технологии следующего уровня, мы поговорим о конкретных ANN-алгоритмах, об их параметрах, и о компромиссах, на которые приходится идти при их использовании.
Фильтрация на основе метаданных
После простого, ничем не ограниченного поиска векторов, мы получаем объекты, взятые из всей совокупности хранимых данных, которые, с семантической точки зрения, ближе всего к заданному. На практике же запросы обычно включают в себя некоторые ограничения. Например — «Найди документы, больше всего похожие на заданный, которые принадлежат этому пользователю и были созданы после этой даты». Это и есть гибридный поиск: поиск векторов по сходству, скомбинированный с фильтрацией по неким атрибутам.
Существуют различные реализации этого механизма. При предфильтрации материалов к данным сначала применяются фильтры, основанные на атрибутах, а потом — с помощью ANN-алгоритмов обрабатывают то, что осталось. При постфильтрации сначала работают ANN-алгоритмы, а потом уже — фильтрация по атрибутам. Предфильтрация позволяет получать более точные результаты, но её использование создаёт большую вычислительную нагрузку на систему при обработке селективных запросов. Большинство баз данных, работающих в продакшне, используют предфильтрацию в комбинации с разумным подходом к индексированию, что позволяет поддерживать высокую скорость поиска.
Гибридный поиск: плотный и разреженный
В ходе простого плотного векторного поиска могут быть упущены детали уровня ключевых слов. Например, запрос вида «дата выпуска GPT-5» может оказаться семантически близок к записям об ИИ, посвящённым общим темам, а не документам, содержащим точную фразу из запроса. В системах гибридного поиска комбинируют плотный ANN-поиск с разреженным поиском (BM25 или TF-IDF), что позволяет добиться и учёта семантики запросов, и точности на уровне ключевых слов.
Стандартный подход к решению этой задачи заключается в параллельном выполнении плотного и разреженного поиска с последующим комбинированием результатов посредством алгоритма RRF (Reciprocal Rank Fusion). Это — алгоритм объединения результатов работы нескольких методов поиска данных, основанный на ранжировании, который не требует нормализации оценок. В наши дни большинство продакшн-систем без дополнительных настроек поддерживают гибридный поиск.
Уровень 3: подходы к индексированию данных, обеспечивающие масштабируемость решений
Алгоритмы приближённого поиска ближайших соседей
Мы рассмотрим три важнейших алгоритма поиска ближайших соседей. Все они находятся в разных точках «пространства компромиссов», описываемого показателями скорости, потребления памяти и полноты поиска объектов.
Алгоритм HNSW (Hierarchical Navigable Small World, иерархический маленький мир) основан на создании многоуровневого графа. Его вершины — это векторы, а рёбра графа соединяют похожие соседние вершины. Более высокие уровни графа разрежены, они обеспечивают быстрый обход графа на большие расстояния. Более низкие уровни графа плотнее, они применяются для точного локального поиска. При выполнении запроса алгоритм перемещается по графу, двигаясь в направлении ближайших соседей. HNSW — это быстрый алгоритм. Он требователен к памяти и отличается очень высокими показателями полноты поиска объектов. Во многих современных системах этот алгоритм используется по умолчанию.
Алгоритм IVF (Inverted File Index, инвертированный индекс) разбивает пространство векторов на кластеры, используя алгоритм кластеризации k-means. Он строит инвертированный индекс, который сопоставляет кластеры с их элементами. При выполнении запроса поиск осуществляется только по ближайшим кластерам. Алгоритм IVF использует меньше памяти, чем HNSW, но часто работает медленнее. Кроме того, его использование предусматривает наличие дополнительного шага обучения системы, на котором осуществляется создание кластеров.
Алгоритм PQ (Product Quantization, квантование произведения) сжимает векторы. Он разбивает их на подвекторы и квантует с применением кодовой книги. Такой подход может привести к сокращению использования памяти в 4-32 раза, что открывает возможность обработки наборов данных, содержащих миллиарды элементов. Алгоритм PQ часто используется в комбинации IVF (называется это IVF-PQ) в системах, наподобие библиотеки Faiss.
Настройка индексирования
При настройке систем индексирования данных, основанных на алгоритме HNSW, интерес представляют два основных параметра — ef_construction и M:
Параметр
ef_constructionуправляет тем, сколько соседних объектов принимается во внимание при создании индекса. Более высокие значения этого параметра обычно улучшают полноту поиска, но замедляют создание индекса.Параметр M управляет количеством двунаправленных связей на вершину графа. Более высокие значения M обычно улучшают полноту поиска, но повышают уровень использования памяти.
Эти параметры настраивают, ориентируясь на требования к полноте поиска и к допустимым задержкам, а так же — на доступный объём памяти.
При выполнении запросов параметр ef_search управляет тем, сколько объектов-кандидатов будет исследовано в ходе поиска. Его увеличение улучшает полноту поиска за счёт роста задержек выполнения запросов. Это — параметр, действующий во время выполнения кода системы, поэтому после его изменения индекс не перестраивается.
В случае с алгоритмом IVF можно отметить параметры nlist и nprobe. Параметр nlist задаёт количество кластеров, а nprobe — то, по скольким кластерам будет производиться поиск во время выполнения запроса. Повышение значения nprobe улучшает полноту поиска, но ухудшает задержки выполнения запросов. Здесь вы можете найти подробности о том, как настраивать параметры IVF (вроде nlist и nprobe) для достижения желаемой полноты поиска и максимального ускорения запросов.
Полнота поиска и задержки выполнения запросов
Алгоритмы ANN живут в пространстве компромиссов. Например, при их использовании всегда можно улучшить полноту поиска, повысив объём материалов индекса, просматриваемых при поиске. Но за это приходится платить ростом задержек выполнения запросов и повышенным потреблением вычислительных ресурсов. Поэтому рекомендуется, подбирая параметры, тестировать их на конкретных наборах данных и на запросах, близких к тем, которые будут использоваться при реальной работе систем. Так, значение показателя recall@10, равное 0,95 может отлично подойти для поисковых приложений, а вот рекомендательной системе может понадобиться значение 0,99.
Масштабирование и шардирование
HNSW-индекс, включающий в себя примерно 50-100 миллионов векторов, может уместиться в память одного компьютера. Конкретные значения зависят от размерности векторов и от объёма доступной памяти. Если нужно работать с более крупными индексами — прибегают к шардированию. Векторное пространство разбивают на фрагменты, которые распределяют по узлам, а запросы выполняют, направляя их к различным шардам, после чего объединяют полученные результаты. Применение шардирования означает дополнительную нагрузку на систему, связанную с координацией действий в распределённой среде, а так же означает необходимость продуманного выбора ключа шардирования для предотвращения перегрузок отдельных узлов. Вот материал, посвящённый этой теме.
Хранилища данных
Векторные данные часто хранят в оперативной памяти, что делается ради ускорения ANN-поиска данных. Метаданные обычно хранятся отдельно, часто — в хранилищах типа «ключ-значение», или в колоночных базах данных. Некоторые системы поддерживают файлы, отображаемые в память. Это позволяет им индексировать наборы данных, размеры которых превышают размеры доступной оперативной памяти, при необходимости сбрасывая некоторые объёмы данных на диск. Такой подход ведёт к возможности работать с более масштабными наборами данных за счёт роста задержек.
Дисковые ANN-индексы, вроде DiskANN (разработан Microsoft), рассчитаны на работу с SSD при минимальном использовании оперативной памяти. Их применение позволяет достичь хороших показателей полноты поиска и пропускной способности системы при работе с очень большими наборами данных, когда возможность работы с такими данными упирается в доступную память.
Способы применения векторных баз данных
Существует три класса систем, позволяющих организовать векторный поиск по данным.
Первый — это специализированные векторные базы данных. Среди них следующие:
Pinecone: полностью управляемая платформа, не требующая операционной поддержки.
Qdrant: опенсорсная система, написанная на Rust, поддерживающая мощные возможности фильтрации данных.
Weaviate: опенсорсный проект со встроенной схемой и с модульной архитектурой.
Milvus: высокопроизводительная опенсорсная векторная СУБД, спроектированная в расчёте на поиск по сходству в больших наборах данных, поддерживающая распределённое развёртывание и видеоускорители.
Второй класс векторных систем — это расширения существующих решений, например — pgvector для Postgres. Это расширение подходит для работы с наборами данных малых и средних размеров.
Третий класс представлен библиотеками:
Faiss — эту библиотеку разработала компания Meta.
Annoy — это — разработка Spotify, оптимизированная в расчёте на сценарии, ориентированные на чтение данных.
Поговорим о применении технологий векторных баз данных в современных приложениях, использующих технологию RAG (Retrieval-Augmented Generation, генерация с дополнением извлечённой информацией). Если речь идёт о работе с наборами данных средних масштабов, то, при условии, что в системе уже используется Postgres, хорошей отправной точкой может стать pgvector. Это позволит минимизировать операционные издержки. Если нужды владельца RAG-приложения растут, в особенности — в плане работы с более крупными наборами данных или в плане более сложных способов фильтрации данных — более интересными вариантами могут стать Qdrant или Weaviate. А тем, кому нужно полностью управляемое решение, не требующее поддержки инфраструктуры, идеально подойдёт Pinecone.
Итоги
Векторные базы данных решают реальную задачу: быстро найти в большом наборе данных то, что по смыслу похоже на искомый объект. Основная идея, лежащая в их основе, проста: представить объекты в виде векторов и осуществлять поиск, ориентируясь расстояние между векторами. Однако, если говорить о практической реализации этой идеи, о системах, рассчитанных на работу с большими объёмами данных, огромное значение приобретают детали, о которых нужно знать. Среди них, например, выбор между алгоритмами HNSW и IFV, настройка параметров, влияющих на полноту поиска, применение гибридного поиска и шардирования.
Вот — несколько полезных материалов, посвящённых разным аспектам векторных баз данных:
What is a Vector Database & How Does it Work? Use Cases + Examples
Top 5 Vector Databases for High-Performance LLM Applications
О, а приходите к нам работать? 🤗 💰
Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.
