Apa yang Mendukung Pencarian Kemiripan di Basis Data Vektor Milvus?

gambar sampul

Artikel ini ditulis oleh Yudong Cai dan diterjemahkan oleh Angela Ni.

Sebagai mesin eksekusi vektor inti, Knowhere untuk Milvus adalah seperti mesin untuk mobil sport. Artikel ini memperkenalkan apa itu Knowhere, apa bedanya dengan Faiss, dan bagaimana kode Knowhere disusun.

Langsung ke:

• Konsep Knowhere
• Knowhere dalam arsitektur Milvus
• Knowhere Vs Faiss
• Memahami kode Knowhere
• Menambahkan indeks ke Knowhere

Konsep Knowhere

Secara sempit, Knowhere adalah antarmuka operasi untuk mengakses layanan di lapisan atas sistem dan pustaka pencarian kemiripan vektor seperti Faiss, Hnswlib, Annoy di lapisan bawah sistem. Selain itu, Knowhere juga bertanggung jawab atas komputasi heterogen. Lebih khusus lagi, Knowhere mengontrol perangkat keras mana (mis. CPU atau GPU) yang akan mengeksekusi pembuatan indeks dan permintaan pencarian. Inilah bagaimana Knowhere mendapatkan namanya - mengetahui di mana harus menjalankan operasi. Lebih banyak jenis perangkat keras termasuk DPU dan TPU akan didukung dalam rilis mendatang.

Dalam pengertian yang lebih luas, Knowhere juga menggabungkan pustaka indeks pihak ketiga lainnya seperti Faiss. Oleh karena itu, secara keseluruhan, Knowhere diakui sebagai mesin komputasi vektor inti dalam basis data vektor Milvus.

Dari konsep Knowhere, kita dapat melihat bahwa Knowhere hanya memproses tugas-tugas komputasi data, sedangkan tugas-tugas seperti sharding, load balance, pemulihan bencana berada di luar cakupan kerja Knowhere.

Mulai dari Milvus 2.0.1, Knowhere (dalam arti yang lebih luas) menjadi independen dari proyek Milvus.

Knowhere dalam arsitektur Milvus

arsitektur knowhere

Komputasi dalam Milvus terutama melibatkan operasi vektor dan skalar. Knowhere hanya menangani operasi-operasi pada vektor di Milvus. Gambar di atas mengilustrasikan arsitektur Knowhere di Milvus.

Lapisan paling bawah adalah perangkat keras sistem. Pustaka indeks pihak ketiga berada di atas perangkat keras. Kemudian Knowhere berinteraksi dengan simpul indeks dan simpul kueri di bagian atas melalui CGO.

Artikel ini membahas tentang Knowhere dalam arti yang lebih luas, seperti yang ditandai dalam bingkai biru pada ilustrasi arsitektur.

Knowhere Vs Faiss

Knowhere tidak hanya memperluas fungsi Faiss tetapi juga mengoptimalkan kinerjanya. Secara lebih spesifik, Knowhere memiliki beberapa keunggulan sebagai berikut.

1. Dukungan untuk BitsetView

Awalnya, bitset diperkenalkan di Milvus untuk tujuan "penghapusan lunak". Vektor yang dihapus secara lunak masih ada dalam database tetapi tidak akan dihitung selama pencarian atau kueri kemiripan vektor. Setiap bit dalam bitset berhubungan dengan vektor yang diindeks. Jika sebuah vektor ditandai sebagai "1" dalam bitset, itu berarti vektor ini telah dihapus dan tidak akan dilibatkan selama pencarian vektor.

Parameter bitset ditambahkan ke semua API kueri indeks Faiss yang terbuka di Knowhere, termasuk indeks CPU dan GPU.

Pelajari lebih lanjut tentang bagaimana bitset memungkinkan keserbagunaan pencarian vektor.

2. Dukungan untuk lebih banyak metrik kemiripan untuk mengindeks vektor biner

Selain Hamming, Knowhere juga mendukung Jaccard, Tanimoto, Superstruktur, Substruktur. Jaccard dan Tanimoto dapat digunakan untuk mengukur kemiripan antara dua set sampel sementara Superstruktur dan Substruktur dapat digunakan untuk mengukur kemiripan struktur kimia.

3. Dukungan untuk set instruksi AVX512

Faiss sendiri mendukung beberapa set instruksi termasuk AArch64, SSE4.2, AVX2. Knowhere lebih lanjut memperluas set instruksi yang didukung dengan menambahkan AVX512, yang dapat meningkatkan kinerja pembangunan indeks dan kueri sebesar 20% hingga 30% dibandingkan dengan AVX2.

4. Pemilihan instruksi SIMD otomatis

Knowhere dirancang untuk bekerja dengan baik pada spektrum prosesor CPU yang luas (baik di lokasi maupun platform cloud) dengan instruksi SIMD yang berbeda (misalnya, SIMD SSE, AVX, AVX2, dan AVX512). Jadi tantangannya adalah, dengan adanya satu perangkat lunak biner (misalnya, Milvus), bagaimana cara membuatnya secara otomatis memanggil instruksi SIMD yang sesuai pada prosesor CPU apa pun? Faiss tidak mendukung pemilihan instruksi SIMD secara otomatis dan pengguna harus menentukan flag SIMD secara manual (misalnya, "-msse4") selama kompilasi. Namun, Knowhere dibangun dengan melakukan refactoring pada basis kode Faiss. Fungsi-fungsi umum (misalnya, komputasi kesamaan) yang mengandalkan akselerasi SIMD telah diperhitungkan. Kemudian untuk setiap fungsi, empat versi (yaitu, SSE, AVX, AVX2, AVX512) diimplementasikan dan masing-masing dimasukkan ke dalam file sumber yang terpisah. Kemudian file sumber selanjutnya dikompilasi secara individual dengan bendera SIMD yang sesuai. Oleh karena itu, pada saat runtime, Knowhere dapat secara otomatis memilih instruksi SIMD yang paling sesuai berdasarkan flag CPU saat ini dan kemudian menghubungkan penunjuk fungsi yang tepat menggunakan pengait.

5. Optimalisasi kinerja lainnya

Baca Milvus: Sistem Manajemen Data Vektor yang Dibangun Khusus untuk mengetahui lebih lanjut tentang pengoptimalan kinerja Knowhere.

Memahami kode Knowhere

Seperti yang disebutkan di bagian pertama, Knowhere hanya menangani operasi pencarian vektor. Oleh karena itu, Knowhere hanya memproses bidang vektor dari sebuah entitas (saat ini, hanya satu bidang vektor untuk entitas dalam sebuah koleksi yang didukung). Pembuatan indeks dan pencarian kesamaan vektor juga ditargetkan pada bidang vektor dalam sebuah segmen. Untuk memiliki pemahaman yang lebih baik mengenai model data, baca blognya di sini.

bidang entitas

Indeks

Indeks adalah jenis struktur data yang terpisah dari data vektor asli. Pengindeksan membutuhkan empat langkah: membuat indeks, melatih data, menyisipkan data, dan membangun indeks.

Untuk beberapa aplikasi AI, pelatihan dataset merupakan proses terpisah dari pencarian vektor. Pada jenis aplikasi ini, data dari dataset dilatih terlebih dahulu dan kemudian dimasukkan ke dalam basis data vektor seperti Milvus untuk pencarian kemiripan. Dataset terbuka seperti sift1M dan sift1B menyediakan data untuk pelatihan dan pengujian. Namun, di Knowhere, data untuk pelatihan dan pencarian dicampur bersama. Dengan kata lain, Knowhere melatih semua data dalam sebuah segmen dan kemudian memasukkan semua data yang telah dilatih dan membangun indeks untuk mereka.

Struktur kode Knowhere

DataObj adalah kelas dasar dari semua struktur data di Knowhere. Size() adalah satu-satunya metode virtual di DataObj. Kelas Index diwarisi dari DataObj dengan sebuah field bernama "size_". Kelas Index juga memiliki dua metode virtual - Serialize() dan Load(). Kelas VecIndex yang diturunkan dari Index adalah kelas dasar virtual untuk semua indeks vektor. VecIndex menyediakan metode-metode termasuk Train(), Query(), GetStatistics(), dan ClearStatistics().

kelas dasar

Jenis indeks lainnya tercantum di sebelah kanan pada gambar di atas.

• Indeks Faiss memiliki dua sub kelas: FaissBaseIndex untuk semua indeks pada vektor titik float, dan FaissBaseBinaryIndex untuk semua indeks pada vektor biner.
• GPUIndex adalah kelas dasar untuk semua indeks GPU Faiss.
• OffsetBaseIndex adalah kelas dasar untuk semua indeks yang dikembangkan sendiri. Hanya ID vektor yang disimpan dalam file indeks. Hasilnya, ukuran file indeks untuk vektor 128 dimensi dapat dikurangi hingga 2 kali lipat. Kami merekomendasikan untuk mempertimbangkan vektor asli juga ketika menggunakan jenis indeks ini untuk pencarian kemiripan vektor.

IDMAP

Secara teknis, IDMAP bukanlah sebuah indeks, melainkan digunakan untuk pencarian brute-force. Ketika vektor dimasukkan ke dalam basis data vektor, tidak ada pelatihan data dan pembuatan indeks yang diperlukan. Pencarian akan dilakukan secara langsung pada data vektor yang dimasukkan.

Namun, demi konsistensi kode, IDMAP juga mewarisi kelas VecIndex dengan semua antarmuka virtualnya. Penggunaan IDMAP sama dengan indeks-indeks lainnya.

IVF

Indeks IVF (inverted file) adalah indeks yang paling sering digunakan. Kelas IVF diturunkan dari VecIndex dan FaissBaseIndex, dan selanjutnya diperluas ke IVFSQ dan IVFPQ. GPUIVF diturunkan dari GPUIndex dan IVF. Kemudian GPUIVF diperluas menjadi GPUIVFSQ dan GPUIVFPQ.

IVFSQHybrid adalah kelas untuk indeks hybrid yang dikembangkan sendiri yang dieksekusi oleh coarse quantize pada GPU. Dan pencarian di dalam bucket dieksekusi di CPU. Jenis indeks ini dapat mengurangi terjadinya penyalinan memori antara CPU dan GPU dengan memanfaatkan kekuatan komputasi GPU. IVFSQHybrid memiliki tingkat recall yang sama dengan GPUIVFSQ tetapi hadir dengan kinerja yang lebih baik.

Struktur kelas dasar untuk indeks biner relatif lebih sederhana. BinaryIDMAP dan BinaryIVF diturunkan dari FaissBaseBinaryIndex dan VecIndex.

Indeks pihak ketiga

Saat ini, hanya ada dua jenis indeks pihak ketiga yang didukung selain Faiss: indeks berbasis pohon Annoy, dan indeks berbasis grafik HNSW. Kedua indeks pihak ketiga yang umum dan sering digunakan ini berasal dari VecIndex.

Menambahkan indeks ke Knowhere

Jika Anda ingin menambahkan indeks baru ke Knowhere, Anda dapat merujuk ke indeks yang sudah ada terlebih dahulu:

• Untuk menambahkan indeks berbasis kuantisasi, lihat IVF_FLAT.
• Untuk menambahkan indeks berbasis grafik, lihat HNSW.
• Untuk menambahkan indeks berbasis pohon, lihat Annoy.

Setelah merujuk ke indeks yang ada, Anda dapat mengikuti langkah-langkah di bawah ini untuk menambahkan indeks baru ke Knowhere.

1. Tambahkan nama indeks baru di IndexEnum. Tipe data adalah string.
2. Tambahkan pemeriksaan validasi data pada indeks baru di file ConfAdapter.cpp. Pemeriksaan validasi terutama untuk memvalidasi parameter untuk pelatihan data dan kueri.
3. Buat file baru untuk indeks baru. Kelas dasar dari indeks baru harus menyertakan VecIndex, dan antarmuka virtual yang diperlukan dari VecIndex.
4. Tambahkan logika pembangunan indeks untuk indeks baru di VecIndexFactory::CreateVecIndex().
5. Tambahkan unit test di bawah direktori unittest.

Tentang Seri Deep Dive

Dengan pengumuman resmi ketersediaan umum Milvus 2.0, kami menyusun seri blog Milvus Deep Dive ini untuk memberikan interpretasi mendalam tentang arsitektur dan kode sumber Milvus. Topik-topik yang dibahas dalam seri blog ini meliputi:

• Gambaran umum arsitektur Milvus
• API dan SDK Python
• Pemrosesan data
• Manajemen data
• Kueri waktu nyata
• Mesin eksekusi skalar
• Sistem QA
• Mesin eksekusi vektor