DISKANN

Dalam skenario berskala besar, di mana kumpulan data dapat mencakup miliaran atau bahkan triliunan vektor, metode pengindeksan dalam memori standar (misalnya, HNSW, IVF_FLAT) sering kali tidak dapat mengimbangi karena keterbatasan memori. DISKANN menawarkan pendekatan berbasis disk yang mengatasi tantangan ini dengan mempertahankan akurasi dan kecepatan pencarian yang tinggi ketika ukuran dataset melebihi RAM yang tersedia.

Gambaran Umum

DISKANN menggabungkan dua teknik utama untuk pencarian vektor yang efisien:

• Vamana Graph - Indeks berbasis disk, berbasis grafik yang menghubungkan titik data (atau vektor) untuk navigasi yang efisien selama pencarian.

• Product Quantization (PQ ) - Metode kompresi dalam memori yang mengurangi ukuran vektor, sehingga memungkinkan penghitungan perkiraan jarak antar vektor dengan cepat.

Konstruksi indeks

Grafik Vamana

Grafik Vamana adalah pusat dari strategi berbasis disk DISKANN. Grafik ini dapat menangani kumpulan data yang sangat besar karena tidak perlu sepenuhnya berada di memori selama atau setelah konstruksi.

Gambar berikut ini menunjukkan bagaimana graf Vamana dibangun.

Diskann

1. Koneksi-koneksi acak awal: Setiap titik data (vektor) direpresentasikan sebagai sebuah simpul dalam graf. Node-node ini pada awalnya terhubung secara acak, membentuk sebuah jaringan yang padat. Biasanya, sebuah simpul dimulai dengan sekitar 500 sisi (atau koneksi) untuk konektivitas yang luas.

2. Pemurnian untuk efisiensi: Graf acak awal mengalami proses optimasi untuk membuatnya lebih efisien untuk pencarian. Hal ini melibatkan dua langkah utama:

   • Memangkas sisi yang berlebihan: Algoritme membuang koneksi yang tidak perlu berdasarkan jarak antar simpul. Langkah ini memprioritaskan sisi-sisi yang berkualitas lebih tinggi.

     Parameter max_degree membatasi jumlah maksimum sisi per node. max_degree yang lebih tinggi menghasilkan graf yang lebih padat, berpotensi menemukan lebih banyak tetangga yang relevan (daya ingat yang lebih tinggi) tetapi juga meningkatkan penggunaan memori dan waktu pencarian.

   • Menambahkan jalan pintas strategis: Vamana memperkenalkan sisi-sisi jarak jauh, menghubungkan titik-titik data yang berjauhan dalam ruang vektor. Jalan pintas ini memungkinkan pencarian dengan cepat melompati grafik, melewati simpul perantara dan secara signifikan mempercepat navigasi.

     Parameter search_list_size menentukan luasnya proses penyempurnaan graf. search_list_size yang lebih tinggi akan memperluas pencarian tetangga selama konstruksi dan dapat meningkatkan akurasi akhir, tetapi meningkatkan waktu pembuatan indeks.

Untuk mempelajari lebih lanjut tentang penyetelan parameter, lihat parameter DISKANN.

PQ

DISKANN menggunakan PQ untuk memampatkan vektor berdimensi tinggi ke dalam representasi yang lebih kecil(kode PQ), yang disimpan di memori untuk perhitungan perkiraan jarak yang cepat.

Parameter pq_code_budget_gb_ratio mengelola jejak memori yang didedikasikan untuk menyimpan kode-kode PQ ini. Parameter ini merepresentasikan rasio antara ukuran total vektor (dalam gigabyte) dan ruang yang dialokasikan untuk menyimpan kode PQ. Anda dapat menghitung anggaran kode PQ yang sebenarnya (dalam gigabyte) dengan rumus ini:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

di mana

• vec_field_size_gb adalah ukuran total vektor (dalam gigabyte).

• pq_code_budget_gb_ratio adalah rasio yang ditentukan pengguna, yang mewakili sebagian kecil dari total ukuran data yang dicadangkan untuk kode PQ. Parameter ini memungkinkan pertukaran antara akurasi pencarian dan sumber daya memori. Untuk informasi lebih lanjut tentang penyetelan parameter, lihat konfigurasi DISKANN.

Untuk rincian teknis tentang metode PQ yang mendasari, lihat IVF_PQ.

Proses pencarian

Setelah indeks (grafik Vamana pada disk dan kode PQ dalam memori) dibangun, DISKANN melakukan pencarian ANN sebagai berikut:

Diskann 2

1. Kueri dan titik masuk: Sebuah vektor kueri disediakan untuk menemukan tetangga terdekat. DISKANN dimulai dari titik masuk yang dipilih dalam grafik Vamana, biasanya sebuah simpul di dekat pusat global dataset. Pusat global mewakili rata-rata dari semua vektor, yang membantu meminimalkan jarak penjelajahan melalui graf untuk menemukan tetangga yang diinginkan.

2. Eksplorasi lingkungan: Algoritme ini mengumpulkan calon tetangga potensial (lingkaran berwarna merah pada gambar) dari tepi-tepi simpul saat ini, dengan memanfaatkan kode PQ dalam memori untuk memperkirakan jarak antara calon-calon tetangga ini dan vektor kueri. Kandidat tetangga potensial ini adalah node-node yang terhubung langsung ke titik masuk yang dipilih melalui sisi-sisi dalam graf Vamana.

3. Memilih node untuk perhitungan jarak yang akurat: Dari hasil perkiraan, subset dari tetangga yang paling menjanjikan (lingkaran berwarna hijau pada gambar) dipilih untuk evaluasi jarak yang tepat menggunakan vektor aslinya yang tidak dikompresi. Hal ini membutuhkan pembacaan data dari disk, yang dapat memakan waktu. DISKANN menggunakan dua parameter untuk mengontrol keseimbangan antara akurasi dan kecepatan:

   • beam_width_ratio: Rasio yang mengontrol luasnya pencarian, menentukan berapa banyak kandidat tetangga yang dipilih secara paralel untuk mengeksplorasi tetangga mereka. beam_width_ratio yang lebih besar menghasilkan eksplorasi yang lebih luas, yang berpotensi menghasilkan akurasi yang lebih tinggi tetapi juga meningkatkan biaya komputasi dan I/O disk. Lebar berkas, atau jumlah node yang dipilih, ditentukan dengan menggunakan rumus: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: Proporsi memori yang dialokasikan untuk caching data disk yang sering diakses. Caching ini membantu meminimalkan I/O disk, sehingga pencarian berulang menjadi lebih cepat karena data sudah ada di dalam memori.

   Untuk mempelajari lebih lanjut tentang penyetelan parameter, lihat konfigurasi DISKANN.

4. Eksplorasi berulang: Pencarian secara iteratif menyempurnakan himpunan kandidat, berulang kali melakukan evaluasi perkiraan (menggunakan PQ) diikuti dengan pemeriksaan yang tepat (menggunakan vektor asli dari disk) hingga jumlah tetangga yang cukup ditemukan.

Mengaktifkan DISKANN di Milvus

Secara default, DISKANN dinonaktifkan pada Milvus untuk memprioritaskan kecepatan indeks dalam memori untuk dataset yang muat dalam RAM. Namun, jika Anda bekerja dengan kumpulan data yang sangat besar atau ingin memanfaatkan skalabilitas DISKANN dan pengoptimalan SSD, Anda dapat dengan mudah mengaktifkannya.

Berikut ini cara mengaktifkan DISKANN di Milvus:

1. Perbarui File Konfigurasi Milvus

   1. Cari file konfigurasi Milvus Anda. (Lihat dokumentasi Milvus tentang Konfigurasi untuk detail cara menemukan file ini).

   2. Temukan parameter queryNode.enableDisk dan atur nilainya ke true:

       queryNode:
           enableDisk: true # Enables query nodes to load and search using the on-disk index
      

2. Mengoptimalkan Penyimpanan untuk DISKANN

Untuk memastikan performa terbaik dengan DISKANN, disarankan untuk menyimpan data Milvus Anda di SSD NVMe yang cepat. Berikut ini adalah cara melakukan hal tersebut untuk penerapan Milvus Standalone dan Cluster:

• Milvus Standalone

  • Pasang direktori data Milvus ke SSD NVMe di dalam container Milvus. Anda dapat melakukan ini di file docker-compose.yml atau menggunakan alat manajemen kontainer lainnya.

  • Misalnya, jika SSD NVMe Anda dipasang di /mnt/nvme, Anda akan memperbarui bagian volumespada docker-compose.yml seperti ini:

   volumes:
        - /mnt/nvme/volumes/milvus:/var/lib/milvus
  

• Milvus Cluster

  • Pasang direktori data Milvus ke SSD NVMe di wadah QueryNode dan IndexNode. Anda dapat melakukannya melalui pengaturan orkestrasi kontainer Anda.

  • Dengan memasang data pada SSD NVMe di kedua jenis node, Anda memastikan kecepatan baca dan tulis yang cepat untuk operasi pencarian dan pengindeksan.

Setelah Anda melakukan perubahan ini, mulai ulang instans Milvus Anda agar pengaturan dapat diterapkan. Sekarang, Milvus akan memanfaatkan kemampuan DISKANN untuk menangani kumpulan data besar, menghadirkan pencarian vektor yang efisien dan dapat diskalakan.

Mengkonfigurasi DISKANN

Parameter terkait DISKANN hanya dapat dikonfigurasi melalui file konfigurasi Milvus Anda (milvus.yaml):

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

Untuk detail tentang deskripsi parameter, lihat DISKANN params.

Parameter DISKANN

Menyempurnakan parameter DISKANN memungkinkan Anda menyesuaikan perilakunya dengan kumpulan data spesifik dan beban kerja pencarian Anda, mencapai keseimbangan yang tepat antara kecepatan, akurasi, dan penggunaan memori.

Parameter pembuatan indeks

Parameter-parameter ini mempengaruhi bagaimana indeks DISKANN dibangun. Menyesuaikannya dapat memengaruhi ukuran indeks, waktu pembuatan, dan kualitas pencarian.

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
Vamana	MaxDegree	Mengontrol jumlah maksimum koneksi (sisi) yang dapat dimiliki setiap titik data dalam grafik Vamana.	Jenis: Rentang Bilangan Bulat: [1, 512] Nilai default: 56	Nilai yang lebih tinggi akan membuat grafik yang lebih padat, berpotensi meningkatkan pemanggilan (menemukan hasil yang lebih relevan) tetapi juga meningkatkan penggunaan memori dan waktu pembuatan. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [10, 100].
	SearchListSize	Selama pembangunan indeks, parameter ini mendefinisikan ukuran kumpulan kandidat yang digunakan ketika mencari tetangga terdekat untuk setiap node. Untuk setiap simpul yang ditambahkan ke dalam graf, algoritme ini menyimpan daftar search_list_size kandidat terbaik yang ditemukan sejauh ini. Pencarian tetangga berhenti ketika daftar ini tidak lagi dapat ditingkatkan. Dari kumpulan kandidat akhir ini, max_degree node teratas dipilih untuk membentuk sisi akhir.	Tipe: Bilangan bulat Rentang: [1, int_max] Nilai default: 100	search_list_size yang lebih besar meningkatkan kemungkinan menemukan tetangga terdekat yang sebenarnya untuk setiap simpul, yang dapat menghasilkan grafik berkualitas lebih tinggi dan kinerja pencarian yang lebih baik (recall). Namun, hal ini harus dibayar dengan waktu pembuatan indeks yang jauh lebih lama. Ini harus selalu diatur ke nilai yang lebih besar dari atau sama dengan max_degree.
	SearchCacheBudgetGBRatio	Mengontrol jumlah memori yang dialokasikan untuk menyimpan bagian grafik yang sering diakses selama konstruksi indeks.	Tipe: Kisaran Float: [0.0, 0.3) Nilai default: 0.10	Nilai yang lebih tinggi mengalokasikan lebih banyak memori untuk caching, secara signifikan mengurangi I/O disk tetapi mengkonsumsi lebih banyak memori sistem. Nilai yang lebih rendah menggunakan lebih sedikit memori untuk caching, sehingga berpotensi meningkatkan kebutuhan akses disk. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Mengontrol ukuran kode PQ (representasi titik data yang dikompresi) dibandingkan dengan ukuran data yang tidak dikompresi.	Tipe Kisaran Float: (0,0, 0,25] Nilai default: 0.125	Rasio yang lebih tinggi akan menghasilkan hasil pencarian yang lebih akurat dengan mengalokasikan proporsi memori yang lebih besar untuk kode PQ, yang secara efektif menyimpan lebih banyak informasi tentang vektor asli. Rasio yang lebih rendah mengurangi penggunaan memori tetapi berpotensi mengorbankan akurasi, karena kode PQ yang lebih kecil menyimpan lebih sedikit informasi. Pendekatan ini cocok untuk skenario di mana keterbatasan memori menjadi perhatian, sehingga memungkinkan pengindeksan set data yang lebih besar. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: (0,0625, 0,25]

Parameter pencarian khusus indeks

Parameter ini memengaruhi cara DISKANN melakukan pencarian. Menyesuaikan parameter ini dapat mempengaruhi kecepatan pencarian, latensi, dan penggunaan sumber daya.

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
Vamana	BeamWidthRatio	Mengontrol tingkat paralelisme selama pencarian dengan menentukan jumlah maksimum permintaan I/O disk paralel relatif terhadap jumlah inti CPU yang tersedia.	Jenis: Kisaran Float: [1, maks (128 / nomor CPU, 16)] Nilai default: 4.0	Nilai yang lebih tinggi akan meningkatkan paralelisme, yang dapat mempercepat pencarian pada sistem dengan CPU dan SSD yang kuat. Namun demikian, pengaturan yang terlalu tinggi dapat menyebabkan perebutan sumber daya yang berlebihan. Pada kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [1.0, 4.0].
	search_list	Selama operasi pencarian, parameter ini menentukan ukuran kumpulan kandidat yang dipertahankan oleh algoritme saat melintasi grafik. Nilai yang lebih besar meningkatkan peluang menemukan tetangga terdekat yang sebenarnya (recall yang lebih tinggi) tetapi juga meningkatkan latensi pencarian.	Jenis: Bilangan bulat Rentang: [1, int_max] Nilai default: 100	Untuk keseimbangan yang baik antara kinerja dan akurasi, disarankan untuk menetapkan nilai ini sama dengan atau sedikit lebih besar dari jumlah hasil yang ingin Anda ambil (top_k).