Verwenden von faiss zum Durchsuchen mehrdimensionaler Räume

Hallo! Mein Name ist Vladimir Olokhtonov, ich bin ein leitender Entwickler im Avito-Team für automatische Moderation. Im Herbst 2019 haben wir einen Suchdienst für ähnliche Bilder basierend auf der Faiss-Bibliothek gestartet. Es hilft uns zu verstehen, dass die Fotos bereits in einer anderen Anzeige gesehen wurden, auch wenn sie stark genug verzerrt sind: verschwommen, beschnitten und dergleichen. Auf diese Weise identifizieren wir potenziell gefälschte Veröffentlichungen.

Ich möchte über die Probleme sprechen, auf die wir bei der Erstellung dieses Dienstes gestoßen sind, und über unsere Lösungsansätze.

Der Artikel geht davon aus, dass der Leser mit dem Thema Suchen in mehrdimensionalen Räumen zumindest ein wenig vertraut ist, da wir uns im Folgenden hauptsächlich auf technische Details konzentrieren werden. Wenn dies nicht der Fall ist, empfehle ich, zuerst den Basisartikel im Mail.ru-Blog zu lesen .

Erklärung des Problems und Beschreibung unseres Systems

Das erste, woran ich dachte, als ich mit der Erstellung eines Suchsystems für Bilder beauftragt wurde, waren Anforderungen und Einschränkungen:

1. Die Anzahl der Einträge. Wir hatten zu Beginn ungefähr 150 Millionen Vektoren, jetzt gibt es bereits mehr als 240 Millionen.
2. Suchzeitlimits. In unserem Fall ca. 300 ms für 95 Perzentile.
3. Speicherlimit. Es ist notwendig, dass der Index auf normalen Servern platziert wird, um das Wachstum für die nächsten 2 Jahre zu berücksichtigen.
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,   .