Usar faiss para buscar espacios multidimensionales

¡Hola! Mi nombre es Vladimir Olokhtonov, soy un desarrollador sénior en el equipo de moderación automática de Avito. En otoño de 2019, lanzamos un servicio de búsqueda de imágenes similares basado en la biblioteca falsa. Nos ayuda a comprender que las fotos ya se han visto en otro anuncio, incluso si están lo suficientemente distorsionadas: borrosas, recortadas y similares. Así es como identificamos publicaciones potencialmente falsas.

Me gustaría hablar sobre los problemas que encontramos en el proceso de creación de este servicio, y nuestros enfoques para resolverlos.

El artículo asume que el lector está al menos un poco familiarizado con el tema de búsqueda en espacios multidimensionales, ya que en adelante discutiremos principalmente detalles técnicos. Si este no es el caso, recomiendo la lectura del básica artículo sobre el Mail.ru primer blog .

Declaración del problema y descripción de nuestro sistema.

Lo primero en lo que pensé cuando me encargaron hacer un sistema de búsqueda de imágenes fue requisitos y limitaciones:

1. El número de entradas. Teníamos unos 150 millones de vectores al principio, ahora ya hay más de 240 millones.
2. Buscar límites de tiempo. En nuestro caso, unos 300 ms para 95 percentiles.
3. Limite de memoria. Es necesario que el índice se coloque en servidores normales, teniendo en cuenta el crecimiento durante los próximos 2 años.
4. .  Kubernetes, ,    , .
5. , .

  :

  ,   — ,   . , .

 ,      .   , , .

. — 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 .

, :

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,   .