Milvus 2.4がCAGRAを発表：次世代GPUインデックスでベクトル検索を進化させる

GPUベースのインデックスとは？

ベクトル検索は本質的に計算集約的です。最も高性能なベクトルデータベースとして最前線に立つMilvusは、そのコンピューティングリソースの80%以上をベクトルデータベースと検索エンジンである Knowhereに割り当てています。ハイパフォーマンス・コンピューティングの計算需要を考えると、GPUは、特にベクトル検索領域において、ベクトルデータベースプラットフォームの極めて重要な要素として浮上してきます。

Milvusは、2021年にMilvus バージョン1.1でGPUアクセラレーションを活用した最初のベクトルデータベースとなり、先例を作りました。バージョン2.3](https://zilliz.com/blog/getting-started-with-gpu-powered-milvus-unlocking-10x-higher-performance)では、NVIDIAの RAFT ライブラリをベクトル検索に活用することで、MilvusはGPUアクセラレーションによるインデックスを導入し、NVIDIA Merlin レコメンデーションフレームワーク（レコメンデーションシステムの構築に使用）との統合を実現した。このバージョンでは、IVFFLATとIVFPQインデックスが導入され、顕著な性能向上が見られました。

このような進歩にもかかわらず、スモールバッチクエリの性能最適化やGPUベースのインデックスのコスト効率の向上といった課題は依然として残っており、革新的なソリューションの探求が続けられている。グラフベースのベクトル検索アルゴリズムへの業界のシフトは、IVFベースの手法よりも優れた性能であることが認識されており、極めて重要な進化を意味する。しかし、これらのアルゴリズムのGPUへの適応は、そのシーケンシャルな実行とランダムなメモリアクセスパターンのために単純ではなく、 GGNN や SONG のようなアルゴリズムにとって効率的なGPU実装を困難にしています。

これらの課題に対処するために、NVIDIAの最新のイノベーションであるGPUベースのグラフインデックス CAGRA は重要なマイルストーンとなります。NVIDIAの支援により、Milvusはその2.4バージョンでCAGRAのサポートを統合し、ベクトル検索における効率的なGPU実装の障害を克服するための重要な一歩を踏み出しました。

CAGRAとは？

CAGRAのビルド

CAGRA (CUDA Anns GRAph-based)は、CPU上の階層的ナビゲーシブルスモールワールド(HNSW)グラフで使用される反復挿入更新法から分岐し、グラフ構築に新しいアプローチを導入します。この変更は、CPUベースのHNSW構築プロセスでは活用できない、GPUの高度な並列グラフ構築能力を十分に活用するという課題に対処するものである。CAGRAは、IVFPQまたはNN-DESCENTを使用して、各ノードが多数の隣接ノードに接続された初期グラフを作成することから始まります。次のステップでは、これらの接続を重要度でソートし、重要度の低いエッジを刈り込み、有向グラフをマージして構造を確定し、初期グラフを構築する。初期グラフでは、各ノードは多数の隣接ノードを持つ。次にCAGRAは、すべての隣接辺を初期グラフに基づく重要度に従ってソートし、重要でない辺を削除する。

CAGRAの構築プロセス](https://assets.zilliz.com/The_build_process_of_CAGRA_45e00eb1c0.png)

初期グラフの構築

IVFPQ

IVFPQ モードでは、CAGRA はデータセットを活用して IVFPQ インデックスを構築し、Product Quantization (PQ) インデックスの量子化機能を利用してビデオメモリ使用量を最小化する。このインデックスの作成後、CAGRAはIVFPQインデックスによって特定された近似最近傍を隣接点最近傍探索として使用して、データセット内の各点の探索を実行する。このプロセスは初期グラフの構築の基礎となり、メモリを大幅に占有することなく効率的なセットアップを保証する。

nn 降下

CAGRAは、初期グラフ構築の別のアプローチとしてNN-DESCENTアルゴリズムを採用しており、これには以下の詳細なステップが含まれる：

1.初期化：データセットvからk個の点をランダムに選択し、初期隣接 リストB[v]を作成する。

2.B と R をマージして H[v] を生成する。

3.3. Neighbor Expansion:データセット中の任意のノードvについて、H[v]に基 づいて近傍ノードのすべての近傍ノードを識別し、最も近い上位kノードを新し い近傍ノードとして選択する。

4.反復:B**が安定して変化しなくなるまで、または事前に設定された反復閾値が満たされ るまで、Reversal and MergingとNeighbor Expansionのプロセスを繰り返す。

HNSWと比較して、NN-Descentは並列化が容易で、タスク間のデータ相互作用が少ないため、GPU上でのCAGRA隣接グラフのグラフ構築時間と効率が大幅に向上する。しかし、NN-DESCENTの初期グラフ品質は、IVFPQモードで達成されるグラフ品質にわずかに遅れをとる可能性があることに注意すべきである。

CAGRA 最適化

CAGRAのグラフ最適化戦略は、2つの主要な仮定に基づいている：

1.**重要度ソート： **辺の重要度を決定するために、従来の距離ベースのソートよりもパスベースのソートを優先する。この手法では、グラフの連結性が必ずしも距離ベースの重要度ソートの恩恵を受けるとは限らないと主張する。

2.2.逆グラフのマージ：あるノードが重要であると判断された場合、後者も重要であると判断される可能性があるという原則が、逆グラフをマージする戦略を支えている。

最適化プロセスには2つの主要なステップがある：

1.1.刈り込み:最初に、各ノードの隣接辺には距離に基づいて様々な重み('w')が割り当てられる。CAGRAは、'max(w_{x to z},w_{z to y}) < w_{x to y}'という条件に基づいて、最も'detourable'なノード間を接続するエッジをカットするプルーニング戦略を採用している。これは、グラフを合理化するために、あまり重要でない接続を排除することに重点を置く。

CAGRA最適化のための刈り込みプロセス](https://assets.zilliz.com/Pruning_Process_for_CAGRA_Optimization_603a397b88.png)

2.マージ：パスの有意性に基づいて順方向グラフを刈り込んだ後、辺を反転してマージする。具体的には、最終的に最適化されたCAGRAグラフを作成するために、順方向グラフと逆方向グラフの両方からエッジの半分が選択される。

グラフの構築と最適化の両方に対するこの詳細なアプローチにより、ベクトル検索操作におけるCAGRAの効率と有効性が保証され、グラフベースの検索アルゴリズムに固有の課題に対処しながら、GPUのユニークな機能を活用することができる。

CAGRAによる検索

CAGRAの検索メカニズムは、効率的なグラフナビゲーションのために、固定サイズの順序付き優先キューを使用した方法論的アプローチを採用しています。この詳細なプロセスは、構造化されたフレームワーク内の一連のステップを通して概説される：

CAGRA 検索フレームワーク

CAGRAは内部トップMリストと候補リストからなる逐次メモリバッファで動作する。内部トップMリストは優先キューとして機能し、その長さはMに設定され（ここでM≧k）、希望する最近傍の数kまで最も関連性の高い結果を確実に格納することができる。これらのリスト内の各要素は、ノードインデックスとクエリとの距離をペアにしており、効率的な検索管理を可能にしている。

CAGRA探索プロセス](https://assets.zilliz.com/CAGRA_Search_Process_bf88c0e30d.png)

検索プロセスのステップ

1.**ランダムサンプリング(初期化)

• 擬似ランダム生成器を利用して、p×d個のランダムなノードインデックスを選択し、各ノードとクエリ間の距離を計算する。
• 結果は候補リストに入力されるが、内部トップMリストは、初期ソート結果に影響を与えないように、仮想エ ントリ（FLT_MAXに設定）で初期化される。

2.内部トップMリスト更新: 内部トップMリストに含めるために、バッファ全体の最小距離に基づいてトップMノードを選択する。

3.候補リストのインデックス更新（グラフ走査）*：

• 内部トップMリストの上位pノードの近傍ノードをすべて特定する。
• この段階で距離を再計算することなく、これらの近傍ノードを候補リストに追加する。

4.**距離計算

• 前の繰り返しで評価されたノードの冗長な計算を避け、候補リストに新しく現れたノードの距離計算を実行します。
• ノードが十分に小さいか大きすぎて考慮されないかに基づいて、その距離がその関連性を正当化する場合にのみ、ノードがトップMリストに追加されることを保証する。

アルゴリズムはこれらのステップを繰り返し処理し、内部トップMリスト内のすべてのノードを、それらがすべて探索の開始点となるまで循環させる。検索は、内部トップMリストから上位k個のエントリを抽出することで終了し、近似最近傍検索(ANNS)の結果を提供する。

パフォーマンス

GPUインデックスを活用することを決定したのは、主にパフォーマンスを考慮したためである。HNSW、GPUベースのIVFFLAT、およびCAGRAインデックス間の比較に焦点を当て、オープンソースベクトルデータベースベンチマークツールを用いてMilvusのパフォーマンスを総合的に評価した。

ベンチマークセットアップ

現実的な評価のために、我々のベンチマークはNVIDIA T4とA10G GPUを搭載したAWSホスティングマシン上で実施し、テスト環境が一般的に利用可能なリソースを反映していることを確認した。選択したマシンは比較可能な価格であり、性能評価のための公平な競争の場を提供した。すべてのテストは、クライアントとしてAWS m6i.4xlargeインスタンス（16C64G）を使用し、top100@98%リコールを達成することを目的とした。

選択したマシンの基本情報](https://assets.zilliz.com/Basic_Info_for_Selected_Machine_2fb7d5556e.png)

パフォーマンスインサイト

**小バッチのパフォーマンス

一般的にGPUが十分に活用されていない小バッチ（バッチサイズ1）の検索では、CAGRAは従来の手法を大幅に上回りました。我々のテストでは、CAGRAはこのような条件下で従来の手法の10倍近いパフォーマンスを提供できることが明らかになりました。

スモールバッチデータセットの性能比較](https://assets.zilliz.com/Performance_Comparison_for_Small_Batch_Data_Set_b9bcc9f26e.png)

ラージバッチ性能:*

より大きな検索バッチ（サイズ10と100）を調べると、CAGRAの優位性はさらに顕著になった。HNSWに対して、CAGRAは劇的な性能向上を示し、検索効率を数十倍向上させた。

ラージバッチデータセットの性能比較](https://assets.zilliz.com/Performance_Comparison_for_Large_Batch_Data_Set_ef371476c6.png)

**インデックス・ビルディングの効率性

検索機能だけでなく、CAGRAの能力はインデックス構築にも及んでいる。GPUアクセラレーションにより、CAGRAは他の方法よりも約10倍速くインデックスを構築できることを実証しました。

インデックス構築のパフォーマンス比較](https://assets.zilliz.com/Performance_Comparison_for_Index_Building_2368e7a64e.png)

ベンチマークの結果は、MilvusにCAGRAのようなGPUアクセラレーションを用いたインデックスを採用することによる性能上の大きな利点を強調しています。CAGRAはバッチサイズに関わらず検索タスクの高速化に優れているだけでなく、インデックス構築速度も大幅に向上しており、ベクトルデータベースパフォーマンスの最適化におけるGPUの価値を裏付けています。

次は？

CAGRAは、ベクトル検索の境界を再定義するという我々の探求における大きな飛躍を意味し、最も要求の厳しいプロダクションの課題に取り組むGPUベースの検索の可能性を示しています。今後、Milvusはベクトル検索におけるhigh recall、低レイテンシ、コスト効率、スケーラビリティの側面をより深く探求していきます。私たちのコミットメントは、現在の成果だけでなく、より柔軟なデータ管理、充実した検索機能、画期的なパフォーマンスの最適化にも及んでいます。

このビジョンは、Milvusが非構造化データの高速検索の未来をリードし、開拓することを確実にするため、絶え間ない技術革新の原動力となっています。今日可能なことの限界に挑戦することで、明日の新たな可能性を解き放ち、ベクトル検索をより強力に、効率的に、そしてアクセスしやすくすることを目指しています。

ベクターデータベースを使用する開発者のための実用的なヒントとコツ.png あなたのソリューションにどのIndexを選べばいいかわからない？正しい選択をするためのブログがあります！*