बहुआयामी रिक्त स्थान खोजने के लिए faiss का उपयोग करना

नमस्कार! मेरा नाम व्लादिमीर ओलोखटनोव है, मैं एविटो स्वचालित मॉडरेशन टीम में एक वरिष्ठ डेवलपर हूं। शरद ऋतु 2019 में, हमने समान पुस्तकालय के आधार पर समान छवियों के लिए एक खोज सेवा शुरू की। यह समझने में हमारी मदद करता है कि फ़ोटो पहले से ही किसी अन्य विज्ञापन में देखी जा चुकी हैं, भले ही वे गंभीरता से विकृत हों: धुंधली, फसली और जैसी। यह है कि हम संभावित नकली प्रकाशनों की पहचान कैसे करते हैं।

मैं उन समस्याओं के बारे में बात करना चाहूंगा, जिन्हें हमने इस सेवा को बनाने की प्रक्रिया में सामना किया था, और उन्हें हल करने के लिए हमारे दृष्टिकोण।

लेख मानता है कि पाठक कम से कम बहुआयामी स्थानों में खोज के विषय से परिचित हैं, इसके बाद से हम मुख्य रूप से तकनीकी विवरणों पर चर्चा करेंगे। यदि यह मामला नहीं है, तो मैं पहले Mail.ru ब्लॉग पर मूल लेख पढ़ने की सलाह देता हूं ।

हमारी प्रणाली की समस्या और विवरण का विवरण

जब मुझे चित्रों के लिए एक खोज प्रणाली बनाने का काम सौंपा गया था, उसके बारे में सबसे पहले मैंने सोचा था:

1. प्रविष्टियों की संख्या। हमारे पास शुरुआत में लगभग 150 मिलियन वैक्टर थे, अब पहले से ही 240 मिलियन से अधिक हैं।
2. समय सीमा खोजें। हमारे मामले में, 95 प्रतिशत के लिए लगभग 300 एमएस।
3. मेमोरी की सीमा। यह आवश्यक है कि सूचकांक को सामान्य सर्वर पर रखा जाए, अगले 2 वर्षों के लिए विकास को ध्यान में रखा जाए।
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,   .