Обработка 15 миллиардов ближайших соседей в Spark
По мере того, как мы приближаемся к выпуску сложного перекоса рекомендательных систем, я рад рассказать о некоторых технических препятствиях, которые мы преодолели, чтобы представить их вам.
Наш характер бизнеса очень мультитенантный. Наш портфель клиентов насчитывает тысячи. Они приносят уникальный набор проблем.
Пока у руля задачи инженерная команда работала над рекомендательной системой.
Основой их по своей сути является алгоритм машинного обучения. Для нас это было легко масштабировать, поскольку существует несколько способов делать выводы на больших наборах данных.
Результатом любой из этих моделей является набор вложений — в нашем случае плотный вектор. Вложения в этом случае нельзя использовать напрямую, но требуется второй компонент — поиск k ближайших соседей в векторном пространстве.
Для создания вложений для всех 60 с лишним миллионов изображений мы использовали Spark и модель, развернутую на AWS Lambda. Задание Spark считывает изображения из S3, вызывает Lambda и сохраняет полученные данные в нашем озере данных Apache Hudi. Альтернативой, которую мы рассматриваем, является использование AWS Sagemaker и коннектора Sagemaker для Spark.
Мы изучили множество альтернатив с открытым исходным кодом, но ни одна из них не подходила:
- Milvus: Многообещающая векторная база данных с открытым исходным кодом для неструктурированных данных. … но поскольку это был скорее альфа-/бета-продукт, мы не хотели вкладываться. Milvus также, кажется, сильно отстает от aNN Benchmarks.
- Elasticsearch: используя Плагин Elasticsearch для поиска ближайших соседей, но без каких-либо реальных тестов производительности, мы не хотели его пробовать.
Несмотря на то, что существует множество алгоритмов k-NN, которые обеспечивают быструю приблизительную (A)NNS, FAISS и Annoy, все они, похоже, не имеют привязок к Java. По результатам aNN Benchmarks остановились на Annoy.
Annoy превзошел большинство приближенных реализаций k-NN и имел API, с которым было довольно просто взаимодействовать и который позволял сохранять индексы на диск с использованием структур mmapped.
Магия внутренних качеств
Annoy реализован на C++. Его зависимость от векторной математики делает C/C++ отличным языком благодаря возможности использовать встроенные функции.
Intel привносит в игру свой набор Расширенных векторных инструкций.
AVX — это расширение набора инструкций x86, позволяющее (весьма резко) ускорить некоторые операции с плавающей запятой.
Нам пришлось перекомпилировать Annoy, чтобы использовать встроенные функции AVX — Annoy использует AVX, AVX2 и AVX512.
Следующим шагом было выяснить, как гидратировать и запрашивать индекс Annoy масштабируемым способом. Это должно быть через Spark.
Apache Spark составляет основу нашей обработки данных в Nosto. Устранив большинство проблем с разделением, Spark сослужил нам хорошую службу и продолжает помогать нам обрабатывать большие объемы данных при горизонтальном масштабировании.
Раздражать в JVM вместо JNA
Есть полезный проект под названием Annoy4S, который взаимодействует с Annoy через JNA (не JNI).
В то время как JNA дает незначительно более низкую производительность по сравнению с JN1, дельта (в этом случае использования) незначительна. Хотя Annoy4 казался решением, оно было довольно устаревшим. Мы помогли стряхнуть пыль с нескольких апстримных пулл-реквестов.
После этого мы перешли к задаче развертывания этого в Spark.
Раздражать в Spark
Чтобы начать использовать Annoy в Spark, нам нужно понять суть Annoy — я не говорю о математике. Annoy использует структуры MMAPd для повышения производительности. Поскольку все они обрабатываются в памяти вне кучи, Spark не может их перемешать.
В то время как Annoy позволяет сохранять индекс MMAP на диске, отсутствие привязок к libHDFS делает это проблемой. Наша реализация опирается исключительно на индексы в памяти и не может перемешиваться.
Мы создали оболочку вокруг Annoy под названием SpartaNN — портманто Spark и приблизительную NN.
Поскольку нам нужно найти «N» ближайших соседей для каждого арендатора, нам нужно использовать mapParititions .
Shuffle — враг Spark! Операции над разделом будут делать именно это. Вы должны убедиться, что ваши операции с красной картой практически не приводят к перетасовке.
mapPartitions перемешивает и объединяет все записи из раздела и возвращает новый СДР, применяя функцию к каждому разделу этого СДР. Использование mapPartitions гарантирует, что каждый раздел оценивается только одним исполнителем. Это предотвращает любые проблемы сериализации с индексом Annoy в памяти.
Iterator[T] › Раздражать › Iterator[K]
Для получения дополнительной информации об использовании SpartaNN в Spark мы рекомендуем документы.
В нашем производственном наборе данных из 60 миллионов продуктов от тысяч розничных продавцов мы обрабатываем 15 миллиардов точек данных. Поскольку этот процесс был в значительной степени связан с ЦП, мы выбрали семейство инстансов z1d на AWS. Это семейство обеспечивает лучшую в своем классе одноядерную производительность, и мы используем его для наших кластеров Redis. Есть также новое семейство экземпляров M5zn, с которым мы еще не играли.
Ниже приведен профиль ЦП и памяти наших инстансов с кластером из 10 узлов инстансов z1d.xlarge на EMR 6.1.0.
Со всеми оптимизациями мы находимся в головокружительном временном интервале в час, чтобы обработать все 15 миллиардов точек данных.
При обработке набора данных размером в терабайт у нас остается меньше гигабайта в случайном порядке, и большая часть времени тратится на загрузку процессора.
С появлением Java 16 наступает новая эра возможностей, включая JEP 338.
JEP 338 (Vector API) был бы долгожданным дополнением, чтобы увидеть, как такие проблемы могут быть решены в JVM. Посмотрим. 🤞🏽
Каждый сценарий k-NN предлагает свой уникальный набор задач. При таком подходе к обработке данных решения редко подходят 1:1. Я надеюсь, что вы сможете учиться, вносить свой вклад (и каннибализировать) и использовать полученные знания.
