salut! Je m'appelle Vladimir Olokhtonov, je suis développeur senior dans l'équipe de modération automatique Avito. À l'automne 2019, nous avons lancé un service de recherche d'images similaires basé sur la bibliothèque faiss. Cela nous aide à comprendre que des photos ont déjà été vues dans une autre annonce, même si elles sont suffisamment sérieusement déformées: floues, recadrées, etc. C'est ainsi que nous identifions les publications potentiellement fausses.
Je voudrais parler des problèmes que nous avons rencontrés lors de la création de ce service et de nos approches pour les résoudre.
L'article suppose que le lecteur connaît au moins un peu le sujet de la recherche dans les espaces multidimensionnels, car nous nous concentrerons ci-après principalement sur les détails techniques. Si ce n'est pas le cas, je recommande la lecture de la base article sur le Mail.ru premier blog .
Énoncé du problème et description de notre système
La première chose à laquelle j'ai pensé lorsque j'ai été chargé de créer un système de recherche d'images était les exigences et les limitations:
- Le nombre d'entrées. Nous avions environ 150 millions de vecteurs au départ, maintenant il y en a déjà plus de 240 millions.
- Limites de temps de recherche. Dans notre cas, environ 300 ms pour 95 centiles.
- Limite de mémoire. Il est nécessaire que l'indice soit placé sur des serveurs ordinaires, en tenant compte de la croissance pour les 2 prochaines années.
- . Kubernetes, , , .
- , .
:
, — , . , .
, . , , .
. — eventually consistent . , .
Python3.7, PostgreSQL, — MinIO. faiss.
http- avio, aiohttp.
asyncio fork, , — , , multiprocessing.Pipe.
Product Quantization. 64 .
Product Quantization .
Inverted File HNSW.
, faiss : IVF262144_HNSW32,PQ64. , Inverted File 262144 , HNSW 32 , 64 Product Quantization.
faiss .
, :
- 10 000 , 1 .
- 16 OpenMP-. , 16 , #pragma omp parallel for.
— . , , - .
, IVF262144_HNSW32,PQ64 80 :
:
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.
:
- GPU. GPU , , , , .
- Flat- GPU, ( 128).
- PQ64- GPU .
Faiss — open source , .
, , faiss . issues, .
, vearch JD.com. open source, .