Home
Blog
在 Milvus 中優化 NVIDIA CAGRA：GPU-CPU 混合方法可加快索引速度並降低查詢成本

在 Milvus 中優化 NVIDIA CAGRA：GPU-CPU 混合方法可加快索引速度並降低查詢成本

Engineering

December 10, 2025

Marcelo Chen

隨著人工智能系統從實驗走向生產基礎架構，向量資料庫不再需要處理數百萬的嵌入。現在，數十億個嵌入式資料已是家常便飯，數百億個嵌入式資料也越來越常見。在這種規模下，演算法的選擇不僅會影響效能與召回率，也會直接轉換為基礎架構成本。

這引出了大規模部署的核心問題：如何選擇正確的索引，以提供可接受的召回率和延遲時間，而不會讓計算資源的使用失控？

基於圖形的索引 (例如NSW、HNSW、CAGRA 和 Vamana)已經成為最廣泛採用的答案。透過瀏覽預先建立的鄰居圖，這些索引能夠以十億級的規模進行快速的最近鄰居搜尋，避免對每個向量進行粗暴掃描和與查詢進行比較。

然而，這種方法的成本並不均衡。查詢圖表相對便宜，但建構圖表就不便宜。建構高品質的圖形需要進行大規模的距離計算，並在整個資料集上反覆精煉，而傳統的 CPU 資源很難在資料成長時有效率地處理這些工作量。

NVIDIA 的 CAGRA 可利用 GPU 的大量平行性加速圖形建構，從而解決這個瓶頸問題。雖然這可大幅縮短建置時間，但在生產環境中，依賴 GPU 來建置索引與提供查詢服務，會產生較高的成本與擴充性限制。

為了平衡這些取捨，Milvus 2.6.1 採用了 GPU_CAGRA 索引 的混合設計：GPU 僅用於圖形建構，而查詢執行則在 CPU 上執行。這樣既能保留 GPU 建構圖表的品質優勢，又能保持查詢服務的可擴展性和成本效益，因此特別適合資料更新頻率低、查詢量大、成本敏感度高的工作負載。

什麼是 CAGRA 以及它如何運作？

基於圖的向量索引通常分為兩大類：

迭代圖形建構，以CAGRA為代表 (Milvus 已支援)。
插入式圖形建構，以Vamana為代表 (目前 Milvus 正在開發中)。

這兩種方法在設計目標和技術基礎上有顯著差異，因此各自適用於不同的資料規模和工作負載模式。

NVIDIA CAGRA (CUDA ANN Graph-based)是一種用於近似近鄰 (ANN) 搜尋的 GPU 原生演算法，專為有效率地建立和查詢大型近鄰圖而設計。透過利用 GPU 的平行性，CAGRA 可大幅加速圖形建構，並提供高吞吐量的查詢效能，比起 HNSW 等以 CPU 為基礎的方法更勝一籌。

CAGRA 建立在NN-Descent（最近鄰居後裔）演算法的基礎上，該演算法透過迭代精煉來建構 k 最近鄰居 (kNN) 圖。在每次迭代中，都會評估和更新候選鄰居，在整個資料集中逐漸向更高品質的鄰居關係靠攏。

每輪精煉之後，CAGRA 會應用額外的圖形剪枝技術 (例如2 跳迂迴剪枝)，以移除多餘的邊緣，同時保持搜尋品質。這種反覆精煉和剪枝的結合方式，可以產生緊湊但連接良好的圖形，在查詢時可以有效率地進行遍歷。

透過重複精煉和剪枝，CAGRA 所產生的圖結構可支援大規模的高召回率和低延遲最近鄰搜索，因此特別適合靜態或不常更新的資料集。

步驟 1：使用 NN-Descent 建立初始圖形

NN-Descent 是基於一個簡單但強大的觀察：如果節點u是v 的鄰居，而節點w是u 的鄰居，那麼w很可能也是v的鄰居。這個反式屬性允許演算法有效率地發現真正的最近鄰居，而不需要窮盡比較每一對向量。

CAGRA 使用 NN-Descent 作為其核心圖形建構演算法。過程如下：

1.隨機初始化：每個節點一開始都會隨機選取一小組鄰居，形成一個粗略的初始圖形。

2.鄰居擴展：在每次迭代中，節點收集其目前鄰居及其鄰居，形成候選人清單。演算法會計算節點與所有候選人之間的相似度。由於每個節點的候選名單都是獨立的，因此這些計算可以分配給獨立的 GPU 線程區塊，並以大規模的方式並行執行。

3.候選名單更新：如果演算法找到比節點目前鄰居更近的候選名單，就會換掉較遠的鄰居，並更新節點的 kNN 名單。經過多次迭代後，此過程會產生品質更高的近似 kNN 圖。

4.收斂檢查：隨著迭代的進行，鄰居更新的次數會越來越少。一旦更新的連線數下降到設定的臨界值以下，演算法就會停止，表示圖形已經有效地穩定下來。

由於不同節點的鄰居擴充和相似性計算是完全獨立的，CAGRA 將每個節點的 NN-Descent 工作量映射到專用的 GPU 線程區塊。此設計可實現大量的平行性，並使圖形建構的速度比基於 CPU 的傳統方法快上幾個數量級。

步驟 2：使用 2 跳迂迴路徑修剪圖形

在 NN-Descent 完成之後，所得到的圖表雖然精確，但過於密集。NN-Descent 會刻意保留額外的候選鄰居，而隨機初始化階段會引入許多弱邊緣或不相關的邊緣。因此，每個節點的階級通常會是目標階級的兩倍，甚至幾倍。

為了產生緊湊且有效率的圖表，CAGRA 應用了 2 跳迂迴剪枝。

這個想法很簡單：如果節點A可以透過共用鄰居C間接抵達節點B(形成一條路徑 A → C → B)，而且這條間接路徑的距離與A和B 之間的直接距離相若，那麼 A → B 這條直接邊就會被視為多餘，可以移除。

此剪枝策略的主要優點是每條邊的冗餘檢查只取決於本地資訊 - 兩個端點及其共用鄰居之間的距離。由於每條邊緣都可以獨立評估，因此剪枝步驟具有高度的平行性，可以很自然地在 GPU 上批次執行。

因此，CAGRA 可以在 GPU 上有效率地剪枝圖形，將儲存開銷降低40-50%，同時在查詢執行過程中保持搜尋準確性並提昇遍歷速度。

Milvus 中的 GPU_CAGRA：有何不同？

儘管 GPU 為圖表建構提供了重大的效能優勢，但生產環境卻面臨實際的挑戰：GPU 資源遠比 CPU 昂貴且有限。如果索引建立和查詢執行都完全依賴 GPU，那麼幾個運作上的問題很快就會浮現：

資源利用率低：查詢流量通常是不定期且突發性的，導致 GPU 長時間閒置，浪費昂貴的計算能力。
部署成本高：為每個查詢服務實例分配 GPU 會增加硬體成本，即使大多數查詢都無法充分利用 GPU 的效能。
可擴充性有限：可用的 GPU 數量直接影響您可以執行的服務複本數量，限制了您隨需求擴充的能力。
彈性降低：當索引建立和查詢都依賴 GPU 時，系統就會被 GPU 的可用性束縛，無法輕易將工作負載轉移到 CPU。

為了解決這些限制，Milvus 2.6.1 透過adapt_for_cpu 參數為 GPU_CAGRA 索引引進了彈性部署模式。此模式可實現混合工作流程：CAGRA 使用 GPU 建立高品質的圖表索引，而查詢執行則在 CPU 上執行 - 通常使用 HNSW 作為搜尋演算法。

在此設定中，GPU 用於提供最大價值的地方 (快速、高精確度的索引建置)，而 CPU 則以更具成本效益和可擴充的方式處理大型查詢工作負載。

因此，這種混合方法特別適用於下列工作負載：

資料更新頻率低，因此索引重建次數少
查詢量大，需要許多低成本的複本
成本敏感度高，必須嚴格控制 GPU 使用量

瞭解`adapt_for_cpu`

在 Milvus 中，adapt_for_cpu 參數控制 CAGRA 索引在建立索引時如何序列化到磁碟，以及在載入時如何反序列化到記憶體。透過在建立和載入時變更這個設定，Milvus 可以靈活地在基於 GPU 的索引建立和基於 CPU 的查詢執行之間切換。

adapt_for_cpu 在建立時間和載入時間的不同組合會產生四種執行模式，每種模式都是針對特定的作業情境而設計。

建立時間 (`adapt_for_cpu`)	載入時間 (`adapt_for_cpu`)	執行邏輯	建議方案
真	真	使用 GPU_CAGRA 建立 → 序列化為 HNSW → 反序列化為 HNSW →CPU 查詢	成本敏感型工作負載；大規模查詢服務
真	假	使用 GPU_CAGRA 建立 → 序列化為 HNSW → 反序列化為 HNSW →CPU 查詢	當發生參數不匹配時，後續查詢回落到 CPU
假	真	使用 GPU_CAGRA 建立 → 序列化為 CAGRA → 反序列化為 HNSW →CPU 查詢	保留原始 CAGRA 索引進行儲存，同時啟用臨時 CPU 查詢
假	假	使用 GPU_CAGRA 建立 → 序列化為 CAGRA → 反序列化為 CAGRA →GPU 查詢	成本次要的效能關鍵工作負載

注意： adapt_for_cpu 機制僅支援單向轉換。CAGRA 索引可以轉換為 HNSW，因為 CAGRA 圖形結構保留了 HNSW 所需的所有鄰居關係。但是，HNSW 索引不能轉換回 CAGRA，因為它缺乏基於 GPU 的查詢所需的額外結構資訊。因此，在選擇建立時間設定時應小心謹慎，並考慮長期部署和查詢需求。

測試 GPU_CAGRA

為了評估混合執行模式 (使用 GPU 建構索引，CPU 執行查詢) 的效能，我們在標準化環境中進行了一系列受控實驗。評估著重於三個層面：索引建立效能、查詢效能和回復準確度。

實驗設定

實驗在廣泛採用的業界標準硬體上進行，以確保結果仍然可靠且廣泛適用。

CPU：MD EPYC 7R13 處理器 (16 CPU)
GPU：NVIDIA L4

1.索引建立效能

我們比較在 GPU 上建立的 CAGRA 與在 CPU 上建立的 HNSW，在相同的目標圖形程度 64 下。

主要結果

GPU CAGRA 建立索引的速度比 CPU HNSW 快 12-15 倍。在 Cohere1M 和 Gist1M 上，基於 GPU 的 CAGRA 效能明顯優於基於 CPU 的 HNSW，突顯出 GPU 並行性在圖形建構過程中的效率。
建立時間隨著 NN-Descent 複製次數的增加而呈線性增加。隨著迭代次數的增加，建構時間也以接近線性的方式成長，反映出 NN-Descent 的迭代精煉性質，並在建構成本與圖表品質之間提供可預測的權衡。

2.查詢效能

在本實驗中，CAGRA 圖形在 GPU 上建立一次，然後透過兩種不同的執行路徑進行查詢：

CPU 查詢：索引被反序列化為 HNSW 格式並在 CPU 上進行搜尋
GPU 查詢：使用基於 GPU 的遍歷法直接在 CAGRA 圖上執行搜尋

主要發現

GPU 搜尋吞吐量比 CPU 搜尋高出 5-6 倍。在 Cohere1M 和 Gist1M 中，基於 GPU 的遍歷提供了大幅提升的 QPS，突顯了 GPU 上平行圖形導航的效率。
Recall 會隨著 NN-Descent 的迭代次數增加，然後停滯不前。隨著建立迭代次數的增加，CPU 和 GPU 查詢的召回率都有所改善。然而，超過某一點後，額外的迭代次數所產生的收益會逐漸減少，顯示圖表品質已大致收斂。

3.召回準確度

在本實驗中，CAGRA 和 HNSW 都在 CPU 上進行查詢，以比較相同查詢條件下的召回率。

主要結果

在這兩個資料集上，CAGRA 的召回率都比 HNSW 高，顯示即使在 GPU 上建立 CAGRA 索引，然後再反序列化供 CPU 搜尋時，圖表品質仍能維持良好。

下一步：使用 Vamana 擴展索引建置

Milvus 的 GPU-CPU 混合方法為當今的大型向量搜尋工作負載提供了實用且具成本效益的解決方案。透過在 GPU 上建立高品質的 CAGRA 圖，並在 CPU 上提供查詢服務，Milvus 將快速索引建置與可擴充、經濟實惠的查詢執行結合在一起，特別適合更新頻率低、查詢量大，以及有嚴格成本限制的工作負載。

在更大的規模（數百或數千億向量）下，索引建置本身就成為瓶頸。當整個資料集不再適合 GPU 記憶體時，業界通常會轉而採用插入式圖形建構方法，例如Vamana。Vamana 並非一次性建構圖形，而是分批處理資料，在維持全局連線性的同時，逐步插入新向量。

其建構管道遵循三個關鍵階段：

1.幾何批次成長- 從小批次開始形成骨架圖，然後增加批次大小以最大化平行性，最後再使用大批次完善細節。

2.貪婪插入- 每個新節點都從中央入口點導航插入，反覆精煉其鄰居集。

3.反向邊緣更新- 加入反向連接以保持對稱性並確保有效的圖形導航。

剪枝使用 α-RNG 準則直接整合到建構過程中：如果候選鄰居v已經被現有鄰居p′覆蓋 (即d(p′, v) < α × d(p, v))，則v會被剪枝。參數 α 可以精確控制稀疏性和精確度。GPU 加速是透過批次內平行和幾何批次縮放來實現，在索引品質和吞吐量之間取得平衡。

這些技術讓團隊能夠處理快速的資料成長和大規模的索引更新，而不會受到 GPU 記憶體的限制。