Mengoptimalkan NVIDIA CAGRA di Milvus: Pendekatan Hibrida GPU-CPU untuk Pengindeksan yang Lebih Cepat dan Kueri yang Lebih Murah

Ketika sistem AI beralih dari eksperimen ke infrastruktur produksi, basis data vektor tidak lagi berurusan dengan jutaan penyematan. Miliaran kini menjadi hal yang rutin, dan puluhan miliar menjadi hal yang semakin umum. Pada skala ini, pilihan algoritmik tidak hanya memengaruhi kinerja dan daya ingat, tetapi juga diterjemahkan secara langsung ke dalam biaya infrastruktur.

Hal ini mengarah pada pertanyaan inti untuk penerapan skala besar: bagaimana Anda memilih indeks yang tepat untuk menghasilkan recall dan latensi yang dapat diterima tanpa membiarkan penggunaan sumber daya komputasi menjadi tidak terkendali?

Indeks berbasis grafik seperti NSW, HNSW, CAGRA, dan Vamana telah menjadi jawaban yang paling banyak digunakan. Dengan menavigasi grafik ketetanggaan yang telah dibuat sebelumnya, indeks-indeks ini memungkinkan pencarian tetangga terdekat yang cepat dalam skala miliaran, menghindari pemindaian secara kasar dan perbandingan setiap vektor terhadap kueri.

Namun, profil biaya dari pendekatan ini tidak merata. Mengajukan kueri pada sebuah graf relatif murah; membangunnya tidak. Membangun grafik berkualitas tinggi membutuhkan komputasi jarak berskala besar dan penyempurnaan berulang di seluruh dataset-beban kerja yang sulit ditangani oleh sumber daya CPU tradisional secara efisien seiring dengan bertambahnya data.

CAGRA dari NVIDIA mengatasi hambatan ini dengan menggunakan GPU untuk mempercepat pembuatan grafik melalui paralelisme masif. Meskipun hal ini secara signifikan mengurangi waktu pembuatan, namun mengandalkan GPU untuk konstruksi indeks dan penyajian kueri akan menimbulkan kendala biaya dan skalabilitas yang lebih tinggi di lingkungan produksi.

Untuk menyeimbangkan tradeoff ini, Milvus 2.6.1 mengadopsi desain hibrida untuk indeks GPU_CAGRA: GPU hanya digunakan untuk konstruksi graf, sementara eksekusi kueri berjalan pada CPU. Hal ini mempertahankan keunggulan kualitas grafik yang dibuat oleh GPU sekaligus menjaga agar penyajian kueri tetap terukur dan hemat biaya-membuatnya sangat cocok untuk beban kerja dengan pembaruan data yang jarang, volume kueri yang besar, dan sensitivitas biaya yang ketat.

Apa Itu CAGRA dan Bagaimana Cara Kerjanya?

Indeks vektor berbasis grafik umumnya terbagi dalam dua kategori utama:

• Konstruksi graf berulang, diwakili oleh CAGRA (sudah didukung di Milvus).

• Konstruksi graf berbasis sisipan, diwakili oleh Vamana (saat ini sedang dikembangkan di Milvus).

Kedua pendekatan ini berbeda secara signifikan dalam tujuan desain dan fondasi teknisnya, sehingga masing-masing cocok untuk skala data dan pola beban kerja yang berbeda.

NVIDIA CAGRA (CUDA ANN Graph-based) adalah algoritme asli GPU untuk pencarian tetangga terdekat (ANN), yang dirancang untuk membangun dan menanyakan grafik kedekatan skala besar secara efisien. Dengan memanfaatkan paralelisme GPU, CAGRA secara signifikan mempercepat konstruksi grafik dan memberikan kinerja kueri throughput tinggi dibandingkan dengan pendekatan berbasis CPU seperti HNSW.

CAGRA dibangun di atas algoritma NN-Descent (Nearest Neighbor Descent), yang membangun graf k-nearest-neighbor (kNN) melalui penyempurnaan berulang. Dalam setiap iterasi, kandidat tetangga dievaluasi dan diperbarui, secara bertahap konvergen menuju hubungan ketetanggaan yang lebih berkualitas di seluruh kumpulan data.

Setelah setiap putaran penyempurnaan, CAGRA menerapkan teknik pemangkasan graf tambahan-seperti pemangkasan detour 2-hop-untukmenghapus sisi yang berlebihan sambil menjaga kualitas pencarian. Kombinasi dari perbaikan dan pemangkasan berulang ini menghasilkan graf yang ringkas namun terhubung dengan baik dan efisien untuk dilalui pada waktu kueri.

Melalui penyempurnaan dan pemangkasan yang berulang, CAGRA menghasilkan struktur graf yang mendukung pencarian tetangga terdekat dengan daya ingat yang tinggi dan latensi rendah dalam skala besar, sehingga sangat cocok untuk set data statis atau yang jarang diperbarui.

Langkah 1: Membangun Graf Awal dengan NN-Descent

NN-Descent didasarkan pada pengamatan yang sederhana namun kuat: jika simpul u adalah tetangga v, dan simpul w adalah tetangga u, maka w kemungkinan besar adalah tetangga v juga. Sifat transitif ini memungkinkan algoritma untuk menemukan tetangga terdekat yang sebenarnya secara efisien, tanpa harus membandingkan setiap pasangan vektor.

CAGRA menggunakan NN-Descent sebagai algoritma konstruksi graf intinya. Prosesnya bekerja sebagai berikut:

1. Inisialisasi acak: Setiap node dimulai dengan sekumpulan kecil tetangga yang dipilih secara acak, membentuk graf awal yang kasar.

2. Perluasan tetangga: Dalam setiap iterasi, sebuah node mengumpulkan tetangganya saat ini dan tetangga mereka untuk membentuk daftar kandidat. Algoritma ini menghitung kemiripan antara simpul dan semua kandidat. Karena daftar kandidat setiap node bersifat independen, komputasi ini dapat ditugaskan ke blok thread GPU yang terpisah dan dieksekusi secara paralel dalam skala besar.

3. Pembaruan daftar kandidat: Jika algoritme menemukan kandidat yang lebih dekat daripada tetangga node saat ini, algoritme akan menukar tetangga yang lebih jauh dan memperbarui daftar kNN node. Melalui beberapa iterasi, proses ini menghasilkan perkiraan grafik kNN yang jauh lebih berkualitas.

4. Pemeriksaan konvergensi: Seiring dengan berjalannya iterasi, semakin sedikit pembaruan tetangga yang terjadi. Setelah jumlah koneksi yang diperbarui turun di bawah ambang batas yang ditetapkan, algoritme berhenti, yang mengindikasikan bahwa grafik telah stabil secara efektif.

Karena perluasan tetangga dan komputasi kemiripan untuk node yang berbeda sepenuhnya independen, CAGRA memetakan beban kerja NN-Descent setiap node ke blok thread GPU khusus. Desain ini memungkinkan paralelisme yang masif dan membuat konstruksi graf menjadi jauh lebih cepat daripada metode berbasis CPU tradisional.

Langkah 2: Memangkas Graf dengan Jalan Pintas 2-Hop

Setelah NN-Descent selesai, grafik yang dihasilkan akurat tetapi terlalu padat. NN-Descent dengan sengaja menyimpan kandidat tetangga ekstra, dan fase inisialisasi acak memperkenalkan banyak sisi yang lemah atau tidak relevan. Akibatnya, setiap simpul sering kali berakhir dengan derajat dua kali-atau bahkan beberapa kali-lebih tinggi dari derajat target.

Untuk menghasilkan graf yang ringkas dan efisien, CAGRA menerapkan pemangkasan jalan memutar 2 hop.

Idenya sederhana: jika simpul A dapat mencapai simpul B secara tidak langsung melalui tetangga bersama C (membentuk jalur A → C → B), dan jarak dari jalur tidak langsung ini sebanding dengan jarak langsung antara A dan B, maka sisi langsung A → B dianggap mubazir dan dapat dihapus.

Keuntungan utama dari strategi pemangkasan ini adalah bahwa pemeriksaan redundansi setiap sisi hanya bergantung pada informasi lokal-jarak antara dua titik akhir dan tetangga bersama mereka. Karena setiap edge dapat dievaluasi secara independen, langkah pemangkasan ini sangat dapat diparalelkan dan cocok secara alami dengan eksekusi batch GPU.

Hasilnya, CAGRA dapat memangkas graf secara efisien pada GPU, mengurangi overhead penyimpanan sebesar 40-50% sekaligus menjaga akurasi pencarian dan meningkatkan kecepatan penelusuran selama eksekusi kueri.

GPU_CAGRA di Milvus: Apa yang Berbeda?

Meskipun GPU menawarkan keunggulan performa yang besar untuk konstruksi graf, lingkungan produksi menghadapi tantangan praktis: Sumber daya GPU jauh lebih mahal dan terbatas daripada CPU. Jika pembuatan indeks dan eksekusi kueri hanya bergantung pada GPU, beberapa masalah operasional akan muncul dengan cepat:

• Pemanfaatan sumber daya yang rendah: Lalu lintas kueri sering kali tidak teratur dan meledak-ledak, membuat GPU menganggur dalam waktu lama dan memboroskan kapasitas komputasi yang mahal.

• Biaya penerapan yang tinggi: Menugaskan GPU ke setiap instance yang melayani kueri akan meningkatkan biaya perangkat keras, meskipun sebagian besar kueri tidak sepenuhnya memanfaatkan kinerja GPU.

• Skalabilitas terbatas: Jumlah GPU yang tersedia secara langsung membatasi jumlah replika layanan yang dapat Anda jalankan, sehingga membatasi kemampuan Anda untuk menyesuaikan dengan permintaan.

• Mengurangi fleksibilitas: Ketika pembuatan indeks dan kueri bergantung pada GPU, sistem menjadi terikat pada ketersediaan GPU dan tidak dapat dengan mudah mengalihkan beban kerja ke CPU.

Untuk mengatasi kendala ini, Milvus 2.6.1 memperkenalkan mode penerapan yang fleksibel untuk indeks GPU_CAGRA melalui parameter adapt_for_cpu. Mode ini memungkinkan alur kerja hybrid: CAGRA menggunakan GPU untuk membangun indeks grafik berkualitas tinggi, sementara eksekusi kueri berjalan di CPU-biasanya menggunakan HNSW sebagai algoritme pencarian.

Dalam pengaturan ini, GPU digunakan di tempat yang memberikan nilai paling tinggi - konstruksi indeks yang cepat dan akurasi tinggi - sementara CPU menangani beban kerja kueri berskala besar dengan cara yang jauh lebih hemat biaya dan dapat diskalakan.

Hasilnya, pendekatan hibrida ini sangat cocok untuk beban kerja di mana:

• Pembaruan data jarang dilakukan, sehingga pembangunan ulang indeks jarang dilakukan

• Volume kueri tinggi, sehingga membutuhkan banyak replika yang tidak mahal

• Sensitivitas biaya tinggi, dan penggunaan GPU harus dikontrol dengan ketat

Pemahaman adapt_for_cpu

Di Milvus, parameter adapt_for_cpu mengontrol bagaimana indeks CAGRA diserialisasikan ke disk selama pembuatan indeks dan bagaimana indeks tersebut diserialisasikan ke dalam memori pada waktu pemuatan. Dengan mengubah pengaturan ini pada saat membangun dan waktu pemuatan, Milvus dapat secara fleksibel beralih antara pembangunan indeks berbasis GPU dan eksekusi kueri berbasis CPU.

Kombinasi yang berbeda dari adapt_for_cpu pada saat build time dan load time menghasilkan empat mode eksekusi, masing-masing dirancang untuk skenario operasional tertentu.

Waktu Pembuatan (adapt_for_cpu)	Waktu Pemuatan (adapt_for_cpu)	Logika Eksekusi	Skenario yang Disarankan
benar	benar	Bangun dengan GPU_CAGRA → serialisasi sebagai HNSW → deserialisasi sebagai HNSW → kueri CPU	Beban kerja yang sensitif terhadap biaya; penyajian kueri skala besar
benar	salah	Bangun dengan GPU_CAGRA → serialisasi sebagai HNSW → deserialisasi sebagai HNSW → kueri CPU	Kueri berikutnya kembali ke CPU ketika terjadi ketidakcocokan parameter
false	benar	Bangun dengan GPU_CAGRA → serialisasi sebagai CAGRA → deserialisasi sebagai HNSW → kueri CPU	Menyimpan indeks CAGRA asli untuk penyimpanan sambil mengaktifkan pencarian CPU sementara
false	salah	Bangun dengan GPU_CAGRA → serialisasi sebagai CAGRA → deserialisasi sebagai CAGRA → kueri GPU	Beban kerja yang sangat penting untuk kinerja di mana biaya menjadi nomor dua

Catatan: Mekanisme adapt_for_cpu hanya mendukung konversi satu arah. Indeks CAGRA dapat dikonversi menjadi HNSW karena struktur graf CAGRA mempertahankan semua hubungan tetangga yang dibutuhkan oleh HNSW. Namun, indeks HNSW tidak dapat dikonversi kembali ke CAGRA, karena tidak memiliki informasi struktural tambahan yang diperlukan untuk kueri berbasis GPU. Akibatnya, pengaturan waktu pembuatan harus dipilih dengan hati-hati, dengan pertimbangan untuk penyebaran jangka panjang dan persyaratan kueri.

Menguji GPU_CAGRA

Untuk mengevaluasi efektivitas model eksekusi hibrida-menggunakan GPU untuk konstruksi indeks dan CPU untuk eksekusi kueri-kami melakukan serangkaian eksperimen terkontrol di lingkungan yang terstandardisasi. Evaluasi ini berfokus pada tiga dimensi: performa pembuatan indeks, performa kueri, dan akurasi pemanggilan.

Pengaturan Eksperimental

Eksperimen dilakukan pada perangkat keras standar industri yang diadopsi secara luas untuk memastikan hasilnya tetap andal dan dapat diterapkan secara luas.

• CPU Prosesor MD EPYC 7R13 (16 cpu)

• GPU NVIDIA L4

1. Kinerja Pembuatan Indeks

Kami membandingkan CAGRA yang dibangun di atas GPU dengan HNSW yang dibangun di atas CPU, di bawah tingkat grafik target yang sama, yaitu 64.

Temuan Utama

• GPU CAGRA membangun indeks 12-15× lebih cepat daripada CPU HNSW. Pada Cohere1M dan Gist1M, CAGRA berbasis GPU secara signifikan mengungguli HNSW berbasis CPU, menyoroti efisiensi paralelisme GPU selama konstruksi grafik.

• Waktu pembuatan meningkat secara linier dengan iterasi NN-Descent. Seiring dengan meningkatnya jumlah iterasi, waktu pembuatan grafik juga meningkat secara linier, yang mencerminkan sifat penyempurnaan iteratif dari NN-Descent dan memberikan pertukaran yang dapat diprediksi antara biaya pembuatan dan kualitas grafik.

2. Performa kueri

Dalam percobaan ini, grafik CAGRA dibangun sekali pada GPU dan kemudian di-query menggunakan dua jalur eksekusi yang berbeda:

• Kueri CPU: indeks dideserialisasi ke dalam format HNSW dan dicari di CPU

• Permintaan GPU: pencarian dijalankan langsung pada grafik CAGRA menggunakan penjelajahan berbasis GPU

Temuan Utama

• Throughput pencarian GPU adalah 5-6 kali lebih tinggi daripada pencarian CPU. Pada Cohere1M dan Gist1M, penjelajahan berbasis GPU menghasilkan QPS yang jauh lebih tinggi, menyoroti efisiensi navigasi grafik paralel pada GPU.

• Recall meningkat dengan iterasi NN-Descent, lalu mendatar. Seiring dengan bertambahnya jumlah iterasi build, recall meningkat baik untuk kueri CPU maupun GPU. Namun, di luar titik tertentu, iterasi tambahan menghasilkan peningkatan yang semakin berkurang, yang mengindikasikan bahwa kualitas graf sebagian besar telah konvergen.

3. Akurasi pemanggilan kembali

Dalam percobaan ini, CAGRA dan HNSW diquery di CPU untuk membandingkan recall di bawah kondisi query yang sama.

Temuan Utama

CAGRA mencapai recall yang lebih tinggi daripada HNSW pada kedua dataset, menunjukkan bahwa bahkan ketika indeks CAGRA dibangun di GPU dan dideserialisasi untuk pencarian CPU, kualitas grafik tetap terjaga dengan baik.

Selanjutnya: Konstruksi Indeks Penskalaan dengan Vamana

Pendekatan hibrida GPU-CPU Milvus menawarkan solusi praktis dan hemat biaya untuk beban kerja pencarian vektor berskala besar saat ini. Dengan membangun grafik CAGRA berkualitas tinggi di GPU dan melayani kueri di CPU, ini menggabungkan konstruksi indeks yang cepat dengan eksekusi kueri yang dapat diskalakan dan terjangkau - sangatcocok untuk beban kerja dengan pembaruan yang jarang, volume kueri yang tinggi, dan kendala biaya yang ketat.

Pada skala yang lebih besar lagi-puluhanatau ratusan miliar vektor-konstruksi indeksitu sendiri menjadi hambatan. Ketika dataset lengkap tidak lagi muat dalam memori GPU, industri biasanya beralih ke metode konstruksi grafik berbasis sisipan seperti Vamana. Alih-alih membangun grafik sekaligus, Vamana memproses data secara bertahap, menyisipkan vektor baru secara bertahap sambil mempertahankan konektivitas global.

Jalur konstruksinya mengikuti tiga tahap utama:

1. Pertumbuhan batch geometris - dimulai dengan batch kecil untuk membentuk grafik kerangka, kemudian meningkatkan ukuran batch untuk memaksimalkan paralelisme, dan akhirnya menggunakan batch besar untuk menyempurnakan detail.

2. Penyisipan serakah - setiap simpul baru disisipkan dengan menavigasi dari titik masuk pusat, secara berulang-ulang menyempurnakan himpunan tetangganya.

3. Pembaruan sisi ke belakang - menambahkan koneksi terbalik untuk menjaga simetri dan memastikan navigasi graf yang efisien.

Pemangkasan diintegrasikan secara langsung ke dalam proses konstruksi menggunakan kriteria α-RNG: jika sebuah kandidat tetangga v sudah dicakup oleh tetangga yang sudah ada p′ (yaitu, d(p′, v) < α × d(p, v)), maka v dipangkas. Parameter α memungkinkan kontrol yang tepat atas sparsitas dan akurasi. Akselerasi GPU dicapai melalui paralelisme in-batch dan penskalaan batch geometris, yang menyeimbangkan antara kualitas indeks dan throughput.

Bersama-sama, teknik-teknik ini memungkinkan tim untuk menangani pertumbuhan data yang cepat dan pembaruan indeks berskala besar tanpa mengalami keterbatasan memori GPU.

Tim Milvus secara aktif membangun dukungan Vamana, dengan target rilis pada paruh pertama tahun 2026. Pantau terus perkembangannya.

Ada pertanyaan atau ingin mendalami fitur Milvus terbaru? Bergabunglah dengan saluran Discord kami atau ajukan pertanyaan di GitHub. Anda juga dapat memesan sesi tatap muka selama 20 menit untuk mendapatkan wawasan, panduan, dan jawaban atas pertanyaan Anda melalui Milvus Office Hours.

Pelajari Lebih Lanjut tentang Fitur Milvus 2.6

• Memperkenalkan Milvus 2.6: Pencarian Vektor yang Terjangkau dalam Skala Miliaran

• Memperkenalkan Fungsi Penyematan: Bagaimana Milvus 2.6 Menyederhanakan Vektorisasi dan Pencarian Semantik

• Penghancuran JSON di Milvus: Pemfilteran JSON 88,9x Lebih Cepat dengan Fleksibilitas

• Membuka Pengambilan Tingkat Entitas yang Sebenarnya: Kemampuan Array-of-Structs dan MAX_SIM Baru di Milvus

• MinHash LSH di Milvus: Senjata Rahasia untuk Memerangi Duplikat dalam Data Pelatihan LLM

• Membawa Kompresi Vektor ke Tingkat Ekstrim: Bagaimana Milvus Melayani Kueri 3× Lebih Banyak dengan RaBitQ

• Tolok Ukur Berbohong - DB Vektor Layak Mendapatkan Tes yang Sesungguhnya

• Kami Mengganti Kafka/Pulsar dengan Burung Pelatuk untuk Milvus