使用faiss搜索多维空间

你好！我叫Vladimir Olokhtonov，我是Avito自动审核小组的高级开发人员。在2019年秋季，我们基于faiss库启动了针对类似图像的搜索服务。它可以帮助我们了解，即使照片严重变形（模糊，裁剪等），也已经在其他广告中看到过。这就是我们识别潜在假冒出版物的方式。

我想谈谈我们在创建此服务的过程中遇到的问题，以及解决这些问题的方法。

本文假定读者至少对多维空间中的搜索主题有所了解，因为在下文中，我们将主要关注技术细节。如果不是这种情况，建议您先阅读Mail.ru博客上的基本文章。

问题说明和系统说明

当我被要求制作图片搜索系统时，我想到的第一件事是要求和限制：

1. 条目数。一开始我们有大约1.5亿个向量，现在已经超过2.4亿。
2. 搜索时间限制。在我们的情况下，对于95个百分位数，大约需要300毫秒。
3. 内存限制。考虑到未来两年的增长，必须将索引放在普通服务器上。
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,   .