5 сложных проблем векторного поиска и как мы их решили в Apache Cassandra

Векторный поиск является важнейшим компонентом инструментов генеративного искусственного интеллекта, поскольку технология дополненной генерации (RAG) ВСПЫШКА помогает LLM включать актуальную, индивидуализированную информацию, избегая при этом галлюцинаций . В то же время векторный поиск — это функция, а не продукт: вам нужно запрашивать векторы так, как они связаны с остальными данными, а не изолированно, и вам не нужно создавать конвейер для синхронизации остальной части ваших данных. данные с векторным хранилищем для этого.

В 2023 году произошел взрывной рост количества продуктов и проектов векторного поиска, поэтому выбор среди них требует серьезных усилий. Изучая варианты, вам нужно будет рассмотреть следующие сложные проблемы и различные подходы к их решению. Здесь я расскажу вам об этих проблемах и опишу, как DataStax решил их при реализации векторного поиска для DataStax Astra DB и Apache Cassandra.

Обзор контента

• Проклятие размерности
• Проблема 1: масштабирование
• Проблема 2: Эффективный сбор мусора
• Боковая панель: Рабочие нагрузки облачных приложений
• Проблема 3: Параллелизм
• Проблема 4: Эффективное использование диска
• Проблема 5: Компонуемость
• Заворачивать

Проклятие размерности

В основе этих сложных проблем лежит то, что исследователи называют « проклятие размерности ». На практике это означает, что алгоритмы, которые работают для точного поиска векторов в двумерных или трехмерных пространствах, например кд деревья , развалится, когда вы доберетесь до 10, 100 или 1000 размеров в ваших векторах. В результате не существует ярлыка для точного поиска по сходству с многомерными векторами; Чтобы получить результаты в логарифмическом времени, нам нужно использовать алгоритмы приближенного ближайшего соседа (ANN), что создает проблемы в следующих областях.

Проблема 1: масштабирование

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

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

Для нас это было несложно: масштабируемая репликация — это хлеб с маслом Cassandra, и объединение ее с новым SAI в Cassandra-5.0 (индексирование с подключением к хранилищу — см. КООС-7 о том, как это работает, и документация ВОФК о том, как его использовать) бесплатно предоставили нашей реализации векторного поиска мощные возможности горизонтального масштабирования.

Проблема 2: Эффективный сбор мусора

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

Ключевая проблема заключается в том, что все известные нам алгоритмы, которые обеспечивают как поиск с малой задержкой, так и результаты с высокой запоминаемостью, основаны на графах. Доступно множество других алгоритмов индексации векторов: ФАИСС реализует многие из них, но все они либо слишком медленны для создания, либо слишком медленны для поиска, либо предлагают слишком низкую полноту (а иногда и все три!), чтобы быть универсальным решением. Вот почему каждая известная мне база данных производственных векторов использует индекс на основе графов, самым простым из которых является HNSW. Иерархические графики «Маленький мир навигации» были представлено Юрием Малковым и др. в 2016 г. ; Статья вполне читабельна, и я очень рекомендую ее. Подробнее о HNSW ниже.

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

Итак, в какой-то момент вам придется перестроить индексы, чтобы выполнить эту сборку мусора, но когда и как ее организовать? Если вы всегда перестраиваете все при внесении изменений, вы значительно увеличиваете количество выполняемых физических операций записи; это называется усилением записи. С другой стороны, если вы никогда не перестраиваете, вам придется выполнять дополнительную работу по фильтрации устаревших строк во время запроса («усиление чтения»).

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

Боковая панель: Рабочие нагрузки облачных приложений

DataStax Astra DB построен на основе Apache Cassandra и предоставляет платформу для рабочих нагрузок облачных приложений.

Это означает, что рабочие нагрузки:

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

  
  

• Больше, чем память Если ваш набор данных умещается в памяти на одном компьютере, практически не имеет значения, какие инструменты вы используете. Sqlite, MongoDB, MySQL — все они будут работать нормально. Когда это не так, ситуация усложняется — и плохая новость заключается в том, что векторные вложения обычно занимают несколько КБ, или примерно на порядок больше, чем типичные документы базы данных, поэтому вы относительно быстро доберетесь до размеров, превышающих объем памяти.

  
  

• Ядро приложения Если вас не волнует, потеряете ли вы свои данные, либо потому, что это не так важно, либо потому, что вы можете восстановить их из фактического источника записи, то опять же не имеет значения, какие инструменты вы используете. Такие базы данных, как Cassandra и Astra DB, созданы для того, чтобы ваши данные оставались доступными и надежными, несмотря ни на что.

Проблема 3: Параллелизм

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

Связанная с этим проблема заключается в том, что ann-benchmarks одновременно выполняет только один тип операций: сначала он создает индекс, затем запрашивает его. Работа с обновлениями, чередующимися с поиском, не является обязательной и, вероятно, даже помехой; если вы знаете, что вам не нужно иметь дело с обновлениями, вы можете сделать множество упрощающих предположений, которые хорошо смотрятся на искусственных тестах.

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

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

Однако даже в категории индексов графов все еще существуют важные детали реализации. Например, сначала мы думали, что сможем сэкономить время, используя реализацию индекса HNSW от Lucene, как это делают MongoDB Elastic и Solr. Но мы быстро поняли, что Lucene предлагает только однопоточное непараллельное построение индексов. То есть вы не можете ни запрашивать ее во время ее построения (что должно быть одной из основных причин использования этой структуры данных!), ни позволять нескольким потокам создавать ее одновременно.

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

JVector линейно масштабирует одновременные обновления как минимум до 32 потоков. Этот график имеет логарифмическое масштабирование по осям X и Y, показывая, что удвоение числа потоков сокращает время сборки вдвое.

Что еще более важно, неблокирующий параллелизм JVector способствует более реалистичным рабочим нагрузкам за счет сочетания поиска с обновлениями. Вот сравнение производительности Astra DB (с использованием JVector) по сравнению с Pinecone в разных наборах данных. Хотя Astra DB примерно на 10% быстрее, чем Pinecone, для статического набора данных, она в 8–15 раз быстрее, а также индексирует новые данные. Мы выбрали лучший доступный уровень модулей с Pinecone (тип модуля: p2 и размер модуля: x8, с 2 модулями на реплику), основываясь на их рекомендациях по более высокой пропускной способности и меньшей задержке. Сосновая шишка не раскрывает, каким физическим ресурсам это соответствует. Что касается Astra DB, мы выбрали модель развертывания PAYG по умолчанию, и нам не пришлось беспокоиться о выборе ресурсов, поскольку она бессерверная. Испытания проводились с использованием NoSQLBench .

Astra DB делает это, сохраняя при этом более высокую полноту и точность ( F1 — это сочетание отзыва и точности ) :

Проблема 4: Эффективное использование диска

Мы начали с Алгоритм индексации графа HNSW потому что индекс быстро создается, быстро запрашивается, отличается высокой точностью и простотой реализации. Однако у него есть известный недостаток: он требует много памяти.

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

Однако такая конструкция означает, что (как и во всех индексах графа) вам не сойдет с рук фраза: «Дисковый кеш нас спасет», потому что, в отличие от обычных рабочих нагрузок запросов к базе данных, каждый вектор в графе имеет почти равную вероятность быть релевантным для поиска. (Исключением являются верхние уровни, которые мы можем и кэшируем.)

Вот как выглядел профиль обслуживания 100-мегабайтного набора векторных данных фрагментов статей Википедии (около 120 ГБ на диске) на моем настольном компьютере с 64 ГБ ОЗУ, когда мы использовали Lucene:

Кассандра почти все время проводит в ожидании чтения векторов с диска.

Чтобы решить эту проблему, мы реализовали более продвинутый алгоритм под названием DiskANN и открыли его исходный код как отдельную встроенную векторную поисковую систему. JВектор . (В частности, JVector реализует инкрементальную версию DiskANN, описанную в разделе ФрешДискАНН Вкратце, DiskANN использует одноуровневый граф с более длинными ребрами, чем HNSW, и оптимизированное расположение векторов и соседей для уменьшения количества операций ввода-вывода в секунду на диске, а также сохраняет сжатое представление векторов в памяти для ускорения вычислений сходства. Это приводит к утроению пропускной способности рабочей нагрузки Википедии.

Вот как выглядит сравнение HNSW и DiskANN в чисто встроенном сценарии без компонентов клиент/сервер. Это измеряет скорость поиска в наборе данных Deep100M с помощью Lucene (HNSW) и JVector (DiskANN). Индекс Lucene составляет 55 ГБ, включая индекс и необработанные векторы. Индекс JVector составляет 64 ГБ. Поиск проводился на моем MacBook емкостью 24 ГБ, объем памяти которого составляет примерно одну треть от объема, необходимого для хранения индекса в оперативной памяти.

Проблема 5: Компонуемость

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

Рассмотрим простой чат-бот с искусственным интеллектом пример приложения для Astra DB. Это примерно такое же чистое приложение RAG, как и вы, с использованием векторного поиска для предоставления LLM соответствующей документации для ответа на вопросы пользователей. Однако даже такая простая демонстрация все равно требует выполнения «обычных», невекторных запросов к Astra DB для получения истории разговоров, которую также необходимо включать в каждый запрос к LLM, чтобы она могла «запомнить» то, что уже было выполнено. состоялось. Итак, ключевые запросы включают в себя:

1. Найдите наиболее релевантные документы (или фрагменты документов) по вопросу пользователя.
2. Получить последние двадцать сообщений из разговора пользователя.

В более реалистичном варианте использования один из наших инженеров по решениям недавно работал с компанией в Азии, которая хотела добавить семантический поиск в свой каталог продуктов, но также хотела включить сопоставление на основе терминов. Например, если пользователь ищет [шаровой кран «красный»], то он хочет ограничить поиск элементами, описание которых соответствует термину «красный», независимо от того, насколько семантически схожи векторные вложения. Тогда ключевой новый запрос (помимо классических функций, таких как управление сеансами, история заказов и обновления корзины покупок) заключается в следующем: Ограничить продукты теми, которые содержат все цитируемые термины, а затем найти наиболее похожий на поиск пользователя.

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

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

В Astra DB мы создали (и открыли исходный код) лучшее решение на базе Cassandra SAI. Поскольку SAI позволяет создавать собственные типы индексов, которые привязаны к стабильному жизненному циклу Cassandra и жизненному циклу сжатия, Astra DB легко позволяет разработчикам смешивать и сопоставлять логические предикаты, поиск на основе терминов и векторный поиск без каких-либо дополнительных затрат. управление и синхронизация отдельных систем. Это дает разработчикам, создающим генеративные приложения искусственного интеллекта, более сложные возможности запросов, которые повышают производительность и ускоряют выход на рынок.

Заворачивать

Векторные поисковые системы — это важная новая функция базы данных, имеющая множество архитектурных проблем, включая масштабирование, сборку мусора, параллелизм, эффективное использование диска и возможность компоновки. Я считаю, что при создании векторного поиска для Astra DB мы смогли использовать возможности Cassandra, чтобы предоставить лучшие в своем классе возможности для разработчиков генеративных приложений искусственного интеллекта. Узнайте больше об Astra DB здесь. , или если вы хотите поближе познакомиться с алгоритмами векторного поиска, посетите JВектор .

- Джонатан Эллис, DataStax