Исследования Ant Financial ZSearch по поиску векторов

На снимке показана прямая трансляция лидера инфраструктуры ZSearch Ten Times 2019 Elastic Dev Day.

введение

ElasticSearch (сокращенно ES) — очень популярная распределенная система полнотекстового поиска, которая часто используется в анализе данных, поиске, многомерной фильтрации и других сценариях. Ant Financial начала предоставлять услуги ElasticSearch внутренним бизнес-партнерам в 2017 году. Мы обобщили большой опыт финансового уровня Ant Financial. На этот раз мы в основном делимся нашими исследованиями векторного поиска.

Болевые точки ElasticSearch

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

• как управлять кластером;
• Как облегчить доступ пользователей и управление пользователями;
• Как поддерживать различные персонализированные потребности пользователей;
• ...

Чтобы устранить эти болевые точки, мы разработали универсальную поисковую платформу ZSearch:

• Основываясь на базе K8S, быстро создавать компоненты ZSearch, быструю эксплуатацию и обслуживание и автоматическую замену неисправных машин;
• Репликация между машинными залами, высокий уровень безопасности для важных деловых сторон;
• Платформа подключаемых модулей, определяемая пользователем горячая загрузка подключаемых модулей;
• SmartSearch упрощает поиск пользователей без дополнительных настроек;
• Маршрутизатор сотрудничает с внутренним многопользовательским подключаемым модулем ES для улучшения использования ресурсов;

Требования к векторному поиску

Общая поисковая платформа ZSearch, основанная на ElasticSearch, становится все более совершенной, с большим количеством пользователей и более богатыми сценариями.

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

Чтобы решить эту проблему, мы добавим механизм векторного поиска или расширим возможности Elasticsearch для поддержки векторного поиска?

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

Далее я познакомлю вас с основными понятиями векторного поиска и нашей практикой в ​​этом.

Основные понятия векторного поиска

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

• Евклидово расстояние:
  • Реальное расстояние между двумя точками, значение тем меньше, чем короче расстояние;
• Косинусное расстояние:
  • Это значение косинуса угла между двумя векторами. Чем больше значение косинуса, тем больше сходство;
• Расстояние Хэмминга:
  • Обычно применяемая к бинаризованным векторам, бинаризация означает, что каждый столбец вектора имеет только два значения 0 или 1.
  • Значение расстояния Хэмминга представляет собой сумму XOR значений каждого столбца двух векторов.Чем меньше значение, тем больше оно похоже.Обычно используется для распознавания изображений;
• Коэффициент подобия Джаффара:
  • Вектор как множество, поэтому это могут быть не только числительные, но могут быть и другие коды, например слова, чем больше значение, тем больше сходство, обычно используемое для идентификации похожих утверждений;

Поскольку все векторы сцены векторного поиска имеют большую размерность, например 256, 512 бит и т. д., объем вычислений очень велик, поэтому затем вводится соответствующий алгоритм для реализации отзыва подобия topN.

Алгоритм векторного поиска

Алгоритм KNN

Алгоритм KNN представляет вектор точного отзыва topK, Здесь есть два основных алгоритма: один KDTtree, а другой — Brute Force. Сначала мы проанализировали алгоритм KDTree и обнаружили, что KDTree не подходит для вызова многомерных векторов, поэтому мы внедрили подключаемый модуль ES Brute Force и использовали некоторые навыки работы с Java для ускорения операции.

Алгоритм KDTree

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

построить дерево

Возьмем множество двумерных плоских точек (x,y) (2,3), (5,4), (9,6), (4,7), (8,1), (7,2) как пример:

Источник изображения:blog.CSDN.net/Richard9006…

• Отсортируйте по x, определите среднее значение 7 и разделите остальные координаты на две стороны;
• Второй слой отсортирован по y, упорядочивая третий слой в соответствии с x;
• И поддерживать максимальные и минимальные и минимальные максимальные значения X и Y и минимальные четыре значения в каждом узле во время конструкции;

Найдите ближайшую точку

Источник изображения:blog.CSDN.net/Richard9006…

Найдите ближайшего соседа (3,5):

• Расстояние до корневого узла равно 5;
• Переходя к правому узлу (9,6), обнаруживается, что ось x всего правого поддерева имеет минимальное значение 8, поэтому расстояние между узлами правого поддерева и узлом запроса должно быть больше 8 -3 = 5, поэтому все правые поддеревья должны быть больше 8-3 = 5. Узлы дерева не нужно обходить;
• Точно так же в левом поддереве по сравнению с узлом (5,4) исключается (7,2);
• После обхода (2,3),(4,7) возвращается ближайшая точка (5,4);

в заключении

BKDTree реализован в Lucene, что можно понимать как блок KDTree, а MAX_DIMS = 8 видно из исходного кода, потому что сложность запроса KDTree составляет O(kn^((k-1)/k)), k представляет измерение , n представляет количество данных. Он показывает, что чем больше k, тем ближе сложность к линейной, поэтому он не подходит для многомерного векторного вызова.

Brute Force

Как следует из названия, это жестокое сравнение расстояния каждого вектора.Мы используем BinaryDocValues ​​для реализации плагина BF на ES. Идя еще дальше, мы хотим ускорить расчет, поэтому используем JAVA Vector API. JAVA Vector API находится в проекте openJDK Panama и использует оптимизацию инструкций SIMD.

в заключении

Используя оптимизацию инструкций avx2, 100w 256-мерный вектор, односрезовое сравнение, RT составляет 260 мс, что составляет 1/6 от обычного BF. ElasticSearch официально выпустил функцию поиска векторов в версии 7.3.Нижний уровень также основан на BinaryDocValues ​​от Lucene, и он также интегрирован в простой синтаксис, что делает его более гибким в использовании.

Алгоритм ИНС

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

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

• LSH на основе хэша;
• IVFPQ на основе кода;
• HNSW на основе графа;

ZSearch также разработала подключаемый модуль ANN (адаптированный к поисковой системе proxima vector Академии DAMO) в соответствии со своими бизнес-сценариями.Алгоритм HNSW).

Алгоритм LSH

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

Алгоритм IVF-PQ

PQ — это своего рода кодирование, такое как 128-мерный вектор на рисунке, сначала разделите вектор на 4 части, сделайте кластеризацию kmeans для каждой части данных, и каждый кластер имеет 256 кластерных центров, так что исходный вектор может использовать кластеризацию Номер центра класса перекодирован.Видно, что теперь он представляет собой вектор и занимает всего 4 байта. Затем, разумеется, записывается вектор центров кластеров, который называется кодовой книгой.

Источник изображения:Навсегда. Тогда /blog/vector…

После кодирования и сжатия PQ для достижения хороших результатов объем запроса все еще очень велик, поэтому можно добавить слой грубой фильтрации впереди, как показано на рисунке, вектор сначала кластеризуется в 1024 центра классов с использованием kmeans для формирования инвертированный индекс и рассчитывается. После остатка каждого исходного вектора и его центра выполняется PQ-квантование этого остаточного набора данных. Причина обработки остатков с помощью PQ, а не исходных данных, заключается в том, что энергия дисперсии остатков меньше энергии дисперсии исходных данных.

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

Источник изображения:Навсегда. Тогда /blog/vector…

Алгоритм HNSW

Прежде чем говорить об алгоритме HNSW, давайте сначала поговорим об алгоритме NSW, как показано на рисунке ниже, который представляет собой последовательную диаграмму построения:

• Например, процесс построения точки D в 5-й раз;
• При построении мы договорились, что при каждом добавлении узла подключается только 3 ребра, чтобы граф не становился больше, при реальном использовании необходимо передавать свои данные;
• Случайный узел, такой как A, сохраняет расстояние от A, а затем проходит по ребру A, точка E является ближайшей, и ребро соединено. Затем повторите поиск, его нельзя повторить, пока не будет добавлено 3 ребра;

Процесс поиска включен в процесс вставки, точно так же, но без построения ребер, результаты возвращаются напрямую.

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

Вышеупомянутые три типа алгоритмов реализуются плагинами ElasticSearch:

| | LSH-плагин | Плагин IVSPQ

Плагин HNSW
Обзор
Образец данных передается при создании индекса, и вычисляется хеш-функция. Увеличьте поле хеш-функции при записи. Recall использует Minimum_should_match для управления объемом вычислений.
преимущество
1. Простота реализации и высокая производительность

2. Не нужно полагаться на другие библиотеки lib 3. Не нужно думать о памяти | 1. Высокая производительность 2. Высокая скорость отзыва> 90%

3. Не нужно учитывать память 1. Высочайшая производительность запросов 2. Самый высокий показатель отзыва> 95% | |Недостатки |1. Скорость отзыва хуже, чем у двух других алгоритмов, около 85% 2. На скорость отзыва влияют исходные данные выборки. 3. ES имеет много метаданных | 1. Его нужно заранее обучить такими инструментами, как faiss 2. Метаданные ES очень велики | 1. При построении операция слияния сегментов будет потреблять огромное количество ресурсов ЦП 2. Производительность запроса будет хуже при использовании нескольких сегментов. 3. Полная память |

Плагин ZSearch HNSW

Согласно нашему собственному сценарию (сценарий облегченного вывода), мы выбрали реализацию плагина HNSW на ES. Поскольку все наши пользователи — это новые данные, и их больше беспокоят 10 лучших векторов, мы используем метод присоединения к механизму поиска векторов через seqNo, чтобы уменьшить потребление ЦП и накладные расходы на избыточные DocValues.

Стыковка с платформой векторного поиска Porxima: **

• Proxima — это общая структура механизма поиска векторов, разработанная внутренним Институтом Дхармы Али, похожая на faiss с открытым исходным кодом facebook;
• Поддержка различных алгоритмов поиска векторов;
• Унифицированный метод и архитектура, удобная для адаптации пользователями;
• Поддержка гетерогенных вычислений, GPU;

**

Достичь Proximaengine.

Процесс записи расширяет сам InternalEngine ElasticSearch. После написания Lucene сначала напишите фреймворк Proxima. Данные фреймворка Proxima будут напрямую сброшены на диск через mmap. В конце запроса Translog сбрасывается на диск. Это полный запрос на запись. Что касается сегментов в памяти, ElasticSearch асинхронно достигает состояния, при котором данные сбрасываются на диск.

Процесс запроса

При запросе через VectorQueryPlugin сначала найдите вектор topN в механизме поиска проксимальных векторов, получите seqNo и сходство, а затем присоединитесь к другим операторам запроса, создав FunctionScoreQuery из newSetQuery.

Цифровой NEWSETQUERY, лежащий в основе здесь, является результатом обхода BKDTree, и производительность по-прежнему очень эффективна.

Отказоустойчивый процесс

Конечно, нам также приходится иметь дело с различными сценариями Failover:

• Когда данные копируются с удаленного конца:
  • Мы перехватили действие восстановления ElasticSearch;
  • Затем создайте снимок индекса Proxima.В это время вам нужно предотвратить запись данных через блокировку записи.Поскольку создание снимка происходит в памяти, на самом деле это очень быстро;
  • Скопируйте снимок Proxima в место назначения;
  • Затем перейдите к другим собственным процессам ElasticSearch;

• Когда данные будут восстановлены из локального транслога, мы запишем LocalCheckPoint снимка.Если текущий CheckPoint меньше или равен LocalCheckPoint, его можно пропустить напрямую, в противном случае мы проверим поисковый механизм Proxima, чтобы предотвратить данные от повторной попытки;
• В настоящее время все еще существует ситуация, когда данные будут дублироваться, то есть когда первичный и вторичный шарды все зависли, транслог не сброшен, а данные могли быть записаны на Proxima.

В сравнении

просеять-128-евклидов набор данных 100 Вт (GitHub.com/Эрик Берн/Пресс…)

	Плагин HNSW	Плагин ZSearch-HNSW
запись данных
(1000 массовых операций записи на поток)	1. Начальная запись

5 мин, 25 сегментов, макс. ЦП 300%; 2. Объединить в 1 сегмент 5мин, максимальная загрузка ЦП 700% (локальный максимум); | Сборка индекса 15 минут, потому что один поток, поэтому максимальная загрузка ЦП 100% | |Запрос|1. Верх 10, скорость отзыва составляет 98%; 2.рт 20 мс , после объединения в 1 сегмент, 5мс; | 1. 10 лучших с коэффициентом отзыва 98%; 2. рт 6 мс | |Преимущества |Совместимость с отказоустойчивостью |Низкое потребление ЦП, отсутствие дополнительного хранилища | |Недостатки |Высокая загрузка ЦП, производительность запросов связана с сегментами |При полном зависании основного и вторичного шардов будет небольшое дублирование данных |

Суммировать

Рекомендации по настройке параметров ES

• 100 Вт 256-мерного вектора занимают пространство, около 0,95 ГБ, что относительно большое:
  • Таким образом, для кэша страниц выделяется больший объем памяти вне кучи;
  • Например, для машины 8C32G для JVM установлено значение 8 ГБ, а остальные 24 ГБ зарезервированы для системы и кэша страниц;
• Установите max_concurrent_shard_requests:
  • 6.x по умолчанию равно количеству узлов * 5. Если на одном узле больше ЦП, вы можете установить более крупные сегменты и увеличить этот параметр;
• Алгоритм BF использует ЦП, поддерживающий AVX2, который в основном поддерживается ECS Alibaba Cloud;

Краткое описание алгоритма

• KNN подходит для сценариев:

  • Небольшое количество данных (менее 100 Вт на оскорбление);
  • Сначала отфильтруйте другие условия, осталось только небольшое количество данных, а затем вспомните сцену вектора;
  • Скорость отзыва составляет 100%;

• Сценарий ИНС:

  • Большой объем данных (более десятков миллионов);
  • Сначала векторная фильтрация, а затем другая фильтрация;
  • Скорость отзыва не обязательно должна быть 100%;
  • Алгоритм LSH: требования к скорости отзыва не высоки, требуется небольшое количество добавлений и удалений;
  • Алгоритм IVFPQ: требования к производительности с высокой скоростью отзыва, большой объем данных (десятки миллионов), небольшое количество добавлений и удалений необходимо построить заранее;
  • Алгоритм HNSW: требования к производительности отзыва высокие, объем данных умеренный (менее 10 миллионов), индекс полностью хранится в памяти, и памяти достаточно;

будущий план

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

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

об авторе

Лу Лян (имя цветка: десять раз), 2017 Присоединившиеся муравьев Золотые сервисные данные промежуточное программное обеспечение, Универсальная поисковая платформа ZSearch Инфраструктурная головка, ответственная за приземление компонентов ZSearch в высокопроизводительном платежем запросе K8S и ESS, для регулировки производительности ES Отличный опыт.

Приложение

• Плагин быстрого косинуса:GitHub.com/оставайтесь со смыслом/…
• Обзор векторных алгоритмов:Навсегда. Тогда /blog/vector…
• Инфраструктура тестирования производительности ANN:GitHub.com/Эрик Берн/Пресс…

Официальная учетная запись: распределенная архитектура финансового уровня (Antfin_SOFA)