company_banner

Использование faiss для поиска по многомерным пространствам

Привет! Меня зовут Владимир Олохтонов, я старший разработчик в команде автоматической модерации Авито. Осенью 2019 мы запустили сервис поиска похожих изображений на основе библиотеки faiss. Он помогает нам понимать, что фотографии уже встречались в другом объявлении, даже если они достаточно серьёзно искажены: размыты, обрезаны и тому подобное. Так мы определяем потенциально фейковые публикации.


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



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


Постановка задачи и описание нашей системы


Первое, о чём я задумался, когда мне поставили задачу сделать систему поиска по картинкам — это требования и ограничения:


  1. Число записей. У нас было около 150 миллионов векторов на старте, сейчас уже больше 240 миллионов.
  2. Ограничения на время поиска. В нашем случае — порядка 300 ms для 95 перцентили.
  3. Ограничение по памяти. Нужно, чтобы индекс помещался на обычные сервера с учётом роста на ближайшие 2 года.
  4. Удобство эксплуатации. Поскольку все наши сервисы живут на Kubernetes, делать систему, нуждающуюся в запуске на железе, очень не хотелось.
  5. Картинки могут добавляться, но они не удаляются и не модифицируются.

Из требований вытекают основные свойства будущей системы:


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


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


Остаётся только обеспечить горизонтальное масштабирование. Самый простой способ в наших условиях — это одинаковые eventually consistent индексы. Тогда инстансы сервиса смогут не знать про существование друг друга, а единственной точкой синхронизации станет база данных.


Наш сервис написан на Python3.7, в качестве базы для хранения векторов используется PostgreSQL, хранилище — MinIO. В главной роли библиотеки для индексации выступает faiss.



Для взаимодействия с внешним миром используется http-фреймворк avio, это наша внутренняя обёртка вокруг aiohttp.


Поскольку asyncio плохо сочетается с вызовами fork, которые нужны нам для бэкапов, да и вызов долгих блокирующих операций в асинхронном сервисе — моветон, то вся работа с индексом вынесена в отдельный процесс, взаимодействие с которым реализовано через multiprocessing.Pipe.


Выбор структуры индекса


Для сжатия мы решили использовать Product Quantization. Этот подход позволяет сжать исходный вектор до 64 байт.


image
Product Quantization позволяет разбить векторы на части и построить независимые кластеризации. Схемы взяты из статьи Криса МакКормика


Для ускорения поиска мы выбрали смешанный подход на основе Inverted File и HNSW.



В итоге мы получили структуру индекса, которая в терминах faiss описывается вот такой загадочной строкой: IVF262144_HNSW32,PQ64. Это означает, что мы делаем Inverted File на 262144 кластера, отбирать ближайшие из которых мы будем с помощью HNSW с 32 соседями, а все векторы сжимаются до 64 байт методом Product Quantization.


Вот ссылки на гайдлайн по выбору индекса от авторов faiss и бенчмарк.


На что стоит обратить внимание, глядя на результаты бенчмарка:


  1. В индекс делается один запрос на поиск 10 000 векторов, а тайминги приведены в пересчёте на 1 вектор.
  2. Время указано для 16 OpenMP-потоков. Если искать на одном ядре, то время будет примерно в 16 раз выше, поскольку параллелизм обеспечивается с помощью #pragma omp parallel for.

Расчёт памяти


Корректнее всего оценивать затраты памяти в относительных величинах — в байтах на вектор. Это позволяет замечать утечки памяти, если они появляются, и легко отличать их от органического роста из-за вставок.


Память тратится в первую очередь на хранение векторов, в случае IVF262144_HNSW32,PQ64 это 80 байт на вектор:


  • 64 байта на хранение кодов, описывающих вектор;
  • 8 байт на хранение id (они хранятся в int64);
  • 8 байт на хранение указателя на вектор внутри кластера.

Относительные затраты памяти можно посчитать по формуле:


int(faiss.get_mem_usage_kb() * 1024 / index.ntotal)

Также память может уходить на предвычисленную таблицу расстояний, но она перестаёт автоматически вычисляться при превышении рассчётного размера в 2Gb. Её размер считается как nlist × pq.M × pq.ksub × float. То есть в нашем случае 262144 × 64 × 256 × 4 ≈ 17G, где pq.M — это число компонент Product Quantization, а pq.ksub — 256, поскольку именно столько кластеров можно описать одним байтом.


На что стоит обратить внимание при расчёте памяти. Данные выше приведены только для статического индекса: если вы добавляете и удаляете элементы, то потребление памяти стоит умножить минимум на 2. У меня есть предположение, что это связано с динамической аллокацией памяти для векторов в Inverted File, но конкретного подтверждения я пока не нашёл. Если у вас есть ответ — расскажите в комментариях к статье.


Схождение bytes per vector после выкатки сервиса:



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


Распараллеливание запросов


Несмотря на использование OpenMP внутри faiss, любой долгий запрос, попавший в большие кластеры, может на существенное время заблокировать индекс. Чтобы это не мешало системе корректно работать, мы используем ThreadPoolExecutor (faiss дружелюбный и отпускает GIL).



Для того, чтобы faiss корректно работал в многопоточной среде, нужно сделать две вещи. Во-первых, не допускать параллельного выполнения модифицирующих операций (add, remove) с какими-либо другими. Во-вторых, лимитировать число OpenMP-тредов во время выполнения читающих запросов таким образом, чтобы общее число тредов не превышало заданное ограничение на ядра, иначе неизбежна потеря производительности.


Для отделения пишущей нагрузки от читающей удобнее всего использовать RWLock, который позволяет заходить в критическую секцию множеству читателей, но только одному писателю. Для Python я рекомендую этот пакет. Число запущенных OpenMP-тредов можно регулировать с помощью функции faiss.omp_set_num_threads.


Для получения оптимальной производительности имеет смысл подбирать размер батча на один тред таким образом, чтобы максимизировать query-per-second. У нас размер батча равен 5.


Стоит обратить внимание, что при использовании многопоточности несколько возрастает потребление памяти. Похоже, что это баг, вот соответствующий issue.


Больше информации о поддержке многопоточности можно найти в статье на вики faiss.


Пропускная способность и тайминги операций


Вставка новых векторов происходит в базу, из которой они раз в 5 секунд вычитываются каждым инстансом независимо и вставляются в индекс батчами по 10 000 штук (ну или сколько накопилось с последнего апдейта). Скорость вставки в индекс достаточная для того, чтобы бутылочным горлышком стала база: порядка 800 тысяч векторов в минуту.


Один инстанс на 20 ядрах способен обработать до 150 rps поисков 20 ближайших соседей для одной картинки при оптимизации latency или около 500 картинок в секунду при оптимизации throughput. Масштабирование по нагрузке очень простое: достаточно просто сделать больше инстансов, поскольку они ничего не знают друг про друга.


Бэкапы индекса


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


Самый удобный способ — сделать fork и с помощью Copy-on-Write получить почти бесплатную в плане потребления памяти и влияния на время операций копию индекса. Затем этот индекс нужно сохранить на диск и перекинуть в хранилище. Здесь стоит исходить из объёма статического индекса — в нашем случае порядка 80 байт на вектор.


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


Использование GPU


Мы пока не используем поиск на GPU в проде, но я провёл замеры для понимания соотношения времён операций.


Данные: SIFT1M, размерность 128.
Запрос: ищем 100 ближайших соседей для 10 000 векторов с разными значениями nprobe.



На что стоит обратить внимание:


  1. Индекс должен целиком помещаться в память GPU. Хотя способы использовать несколько GPU для поиска и существуют, однако, на мой взгляд, подход несёт с собой минусы, связанные со сложностью эксплуатации такого решения.
  2. Flat-индексы заметно быстрее работают на GPU, однако они применимы только при относительно небольшом количестве данных (максимум десятки миллионов векторов при размерности 128).
  3. При использовании PQ64-индекса преимущество GPU проявляется только при опросе очень большого числа кластеров.

Напоследок


Faiss — это наверное лучший на сегодня open source инструмент для приближённого поиска, но как и любой сложный инструмент он требует привыкания к своим особенностям.


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


Если вы собираетесь разворачивать такого рода систему на заранее определённом множестве машин, то могу порекомендовать посмотреть на систему vearch от JD.com. Они сделали большую часть грязной работы и выложили своё решение в open source, хотя с документацией всё пока довольно печально.

Авито
У нас живут ваши объявления

Комментарии 22

    0
    Не знаю стал ли я жертвой этой функции, или чего-то еще…
    но когда продавал два разных велоколеса, то одно из объявлений было забанено как дублирующее, хотя там в описании параметры товара указывал и они разные, да и фото конкретно так были НЕ похожи друг на друга.
      0
      Вопрос конечно совсем не по теме статьи :)
      Скорее всего ваше объявление было забанено по какой-то другой причине, раз вы говорите, что фотки разные.
        0
        Я написал в поддержку тогда и его в итоге разбанили, извинившись.

        а статья мощная, но оооочень технически ориентированная. Реально я думаю понятна будет ничтожному проценту людей, тем кто конкретно такую же штуку запиливал. И то вопросы останутся. А остальным только впечатлиться «до чего техника дошла» :)
          0
          Можно спрашивать детали, я постараюсь ответить :)
      0
      Это означает, что мы делаем Inverted File на 262144 кластера

      Зачем такое гигантское количество кластеров?
        0
        Если в двух словах, то на вырост. Разработчики faiss рекомендуют брать столько и даже больше для индексации миллиарда векторов.
        image

        На данном этапе развитии системы в этом действительно нет необходимости, мы проводили эксперименты с 65536 кластерами и это тоже было вполне нормально.
          +1
          При таком кол-ве кластеров — 2.5М на 240М векторов, должна значительно понизиться точность поиска. Прежде всего я имею ввиду новые записи — они будут попадать, практически, в случайные кластеры. Или вы nprob тоже в 2.5М выставляете?
            0
            Но ведь можно регулировать точность параметром nprobe, чтобы опрашивать большее число ближайших кластеров. У нас он выставлен в 256 и точность вполне приличная. К сожалению по нашей системе конкретные числа не достану, но могу показать замеры на BigANN 1B:

            R@1 R@10 R@100 time (ms/query)
            nprobe=16,efSearch=128,ht=246 0.6546 0.8006 0.8006 4.231
            nprobe=32,efSearch=128,ht=246 0.7107 0.8818 0.8818 7.783
            nprobe=64,efSearch=128,ht=246 0.7435 0.9343 0.9346 14.691
            nprobe=128,efSearch=128,ht=246 0.7653 0.9687 0.9692 28.326
            nprobe=256,efSearch=128,ht=246 0.7726 0.9829 0.9834 55.375


            Всё таки у нас не 2.5 миллиона кластеров, а 262 тысячи.
              0
              Да, прошу прощения, 262К, не 2.5М :) Тем не менее, посоветовал бы тщательно протестировать поиск на новых векторах.
                0
                Спасибо за совет, обязательно проверим.
                UPD: навскидку покидал запросики, картинки находит правильные.
                Вот например
                опорная
                image

                ближайший сосед сразу за опорной
                image

          0
          Года три назад пытался снять квартиру в Краснодаре через Авито — обнаружил целый рассадник мошенников, в центре 9 из 10 квартир просто не существовали и были опубликованы одной из 3 мошеннических контор (на вскидку 500+ объявлений для каждой конторы). Для блокировки этих мошенников даже не нужны нейронные сети, простых решений на основе fingerprints было бы достаточно, но антиспам-фильтром на Авито в тот момент даже не пахло, либо он легко обходился. Хочется верить, что за 3 года ситуация изменилась, хотя верится слабо.
            0
            Поскольку все наши сервисы живут на Kubernetes

            А как в этом контексте, развернуть несколько индексов в одном поде? Если он будет достаточно жирным то его деплой приведет к перебалансировке остальных?

              0

              Мы сейчас выбрали подход 1 индекс на под, это позволяет более гибко планировать поды, всё-таки они довольно толстые.


              Горизонтальное масштабирование достигается увеличением числа подов.

              0
              Спасибо за статью.
              1. Было бы интересно узнать, что вы используете для получения самих векторов.
              2. А какой практический смысл в том, что вектора можно только добавлять? Может быть изображения, добавленные, скажем, 5 лет назад уже можно удалять? Это бы позволило немного замедлить рост размера индекса. Если с этмими изображениями начнут спамить, то они добавятся в индекс. Или я что-то упускаю?
                0
                1. Я попрошу коллегу, которая занималась нейросетью рассказать об этом в отдельной статье.
                2. Нам нужно уметь искать по всему архиву изображений, поскольку мошенники зачастую берут фотографии из старых, уже закрытых объявлений.
                  0
                  А закрытые объявления видны каким-то простым способом? Или нужно знать полный адрес объявления?
                    0

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

                0
                В общем, всё по классике инфопоиска.

                Можете посоветовать литературу по классике?
                0
                Отличная статья, спасибо!

                1. Я так понял, «train» фазу IVF вы сделали только один раз, при самом первом построении индекса? Не сказывается ли это на точности?
                2. Бэкап индекса происходит только с одного инстанса индекса, или сразу со всех? Если с одного, то как вы определяетсе «мастера», который производит бекап?
                  +1
                  1. Да, мы делаем тренировку один раз для каждой порождающей данные модели. На точность существенного влияния мы не заметили, но тут всё зависит от того, насколько распределение на тренировочной выборке соответствует реальному.
                  2. Пока что бекапы делаются со всех инстансов, мы немного троттлим чтение файла, чтобы не забивать сеть в полку.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое