باستخدام faiss للبحث عن مسافات متعددة الأبعاد

مرحبا! اسمي فلاديمير Olokhtonov ، وأنا مطور أول في فريق Avito للاعتدال التلقائي. في خريف 2019 ، أطلقنا خدمة بحث عن صور مشابهة استنادًا إلى مكتبة faiss. يساعدنا ذلك على فهم أن الصور قد تمت رؤيتها بالفعل في إعلان آخر ، حتى إذا كانت مشوهة بشكل كافٍ: مشوشة ومقصودة وما شابه ذلك. هذه هي الطريقة التي نحدد بها المنشورات المزيفة المحتملة.

أود أن أتحدث عن المشاكل التي واجهتنا في عملية إنشاء هذه الخدمة وأساليبنا في حلها.

تفترض المقالة أن القارئ على الأقل على دراية بموضوع البحث في المساحات متعددة الأبعاد ، حيث سنركز فيما يلي بشكل أساسي على التفاصيل الفنية. إذا لم يكن الأمر كذلك ، فإنني أوصي بقراءة المقالة الأساسية على مدونة Mail.ru أولاً .

بيان المشكلة ووصف نظامنا

أول شيء فكرت فيه عندما تم تكليفي بإنشاء نظام بحث للصور كان المتطلبات والقيود:

1. عدد الإدخالات. كان لدينا حوالي 150 مليون متجه في البداية ، والآن يوجد بالفعل أكثر من 240 مليون متجه.
2. حدود وقت البحث. في حالتنا ، حوالي 300 مللي ثانية لـ 95 بالمائة.
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,   .