Menggunakan faiss untuk mencari ruang multidimensi

Halo! Nama saya Vladimir Olokhtonov, saya adalah pengembang senior di tim moderasi otomatis Avito. Pada musim gugur 2019, kami meluncurkan layanan pencarian untuk gambar yang serupa berdasarkan perpustakaan faiss. Ini membantu kami memahami bahwa foto sudah terlihat di iklan lain, meskipun cukup terdistorsi: buram, terpotong, dan sejenisnya. Inilah cara kami mengidentifikasi publikasi yang berpotensi palsu.

Saya ingin berbicara tentang masalah yang kami temui dalam proses menciptakan layanan ini, dan pendekatan kami untuk menyelesaikannya.

Artikel ini mengasumsikan bahwa pembaca setidaknya sedikit akrab dengan topik pencarian dalam ruang multidimensi, karena selanjutnya kita akan membahas terutama detail teknis. Jika tidak, saya sarankan untuk membaca artikel dasar di blog Mail.ru terlebih dahulu .

Pernyataan masalah dan deskripsi sistem kami

Hal pertama yang saya pikirkan ketika saya ditugaskan membuat sistem pencarian gambar adalah persyaratan dan batasan:

1. Jumlah entri. Kami memiliki sekitar 150 juta vektor pada awalnya, sekarang sudah ada lebih dari 240 juta.
2. Batas waktu pencarian. Dalam kasus kami, sekitar 300 ms untuk 95 persentil.
3. Batas memori. Diperlukan bahwa indeks ditempatkan pada server biasa, dengan mempertimbangkan pertumbuhan akun selama 2 tahun ke depan.
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,   .