Usando faiss para pesquisar espaços multidimensionais

Olá! Meu nome é Vladimir Olokhtonov, sou desenvolvedor sênior da equipe de moderação automática do Avito. No outono de 2019, lançamos um serviço de pesquisa de imagens semelhantes com base na biblioteca faiss. Isso nos ajuda a entender que as fotos já foram vistas em outro anúncio, mesmo que sejam suficientemente distorcidas: desfocadas, cortadas e similares. É assim que identificamos publicações potencialmente falsas.

Gostaria de falar sobre os problemas que encontramos no processo de criação deste serviço e nossas abordagens para resolvê-los.

O artigo pressupõe que o leitor esteja pelo menos um pouco familiarizado com o tema da pesquisa em espaços multidimensionais, pois a partir de agora iremos nos concentrar principalmente em detalhes técnicos. Se este não for o caso, eu recomendo a leitura do básico artigo sobre a Mail.ru blogue primeiro .

Declaração do problema e descrição do nosso sistema

A primeira coisa em que pensei quando fui incumbida de criar um sistema de pesquisa de imagens foram os requisitos e limitações:

1. O número de entradas. Tínhamos cerca de 150 milhões de vetores no início, agora já existem mais de 240 milhões.
2. Limites de tempo de pesquisa. No nosso caso, cerca de 300 ms para 95 percentis.
3. Limite de memória. É necessário que o índice seja colocado em servidores comuns, levando em consideração o crescimento pelos próximos 2 anos.
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,   .