DISKANN

データセットに数十億から数兆のベクトルが含まれるような大規模なシナリオでは、標準的なインメモリインデクシング手法（HNSW、IVF_FLATなど）は、メモリの制限により、しばしば追いつくことができません。DISKANNは、データセットサイズが利用可能なRAMを超える場合でも、高い検索精度と速度を維持することで、これらの課題に対処するディスクベースのアプローチを提供します。

概要

DISKANNは、効率的なベクトル探索のための2つの主要な技術を組み合わせています：

• Vamana Graph-ディスクベースの グラフベースのインデックスで、検索時に効率的なナビゲーションを行うためにデータポイント（またはベクトル）を連結します。

• 積量子化（PQ）- ベクトルのサイズを縮小し、ベクトル間の近似距離計算を迅速に行うためのメモリ内圧縮手法。

インデックス構築

バマナグラフ

VamanaグラフはDISKANNのディスクベース戦略の中心です。構築中も構築後も完全にメモリに常駐する必要がないため、非常に大きなデータセットを扱うことができます。

次の図は、Vamanaグラフの構築方法を示しています。

Diskann

1. 初期ランダム接続：各データ点（ベクトル）はグラフのノードとして表現される。これらのノードは最初はランダムに接続され、密なネットワークを形成する。通常、1つのノードは約500のエッジ（または接続）から始まり、幅広い接続性を持つ。

2. 効率化のための洗練：初期のランダム・グラフは、検索効率を高めるために最適化プロセスを経ます。これには2つの重要なステップがある：

   • 冗長なエッジの刈り込み：冗長なエッジの刈り込み：このアルゴリズムは、ノード間の距離に基づいて不要な接続を削除します。このステップは、より質の高いエッジを優先する。

     max_degree パラメータは、ノードあたりの最大エッジ数を制限します。max_degree を高くすると、グラフが密になり、より関連性の高い近傍を発見できる可能性があるが（より高い想起）、メモリ使用量と検索時間が増加する。

   • 戦略的ショートカットの追加：Vamanaは長距離エッジを導入し、ベクトル空間内で離れたデータポイント同士を接続する。これらのショートカットにより、検索はグラフを素早く飛び越え、中間ノードを迂回し、ナビゲーションを大幅に高速化する。

     search_list_size パラメータは、グラフ精密化処理の幅を決定する。search_list_size を高くすると、構築中の近傍探索が拡張され、最終的な精度が向上しますが、インデックス構築時間が長くなります。

パラメータチューニングの詳細については、DISKANN paramsを参照してください。

PQ

DISKANNはPQを使って高次元ベクトルをより小さな表現（PQコード）に圧縮し、それをメモリに保存して近似距離計算を高速に行います。

pq_code_budget_gb_ratio パラメータは、これらの PQ コードを格納するためのメモリフットプリントを管理します。これは、ベクターの合計サイズ（ギガバイト単位）とPQコードの格納に割り当てられたスペースの比率を表します。実際のPQコードバジェット（ギガバイト単位）は、次の式で計算できます：

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

ここで

• vec_field_size_gb はベクターの合計サイズ（ギガバイト単位）です。

• pq_code_budget_gb_ratio はユーザー定義の比率で、PQコード用に予約された総データ・サイズの割合を表します。このパラメータは、検索精度とメモリリソースのトレードオフを可能にします。パラメータチューニングの詳細については、DISKANN configs を参照。

基礎となるPQメソッドの技術的な詳細については、IVF_PQを参照してください。

検索プロセス

インデックス（ディスク上のVamanaグラフとメモリ上のPQコード）が構築されると、DISKANNは以下のようにANN検索を実行する：

Diskann 2

1. クエリーとエントリーポイント：最も近い近傍を見つけるためにクエリーベクトルが提供される。DISKANNは、Vamanaグラフの選択されたエントリーポイント（多くの場合、データセットのグローバルセントロイドに近いノード）から開始する。グローバルセントロイドは全ベクトルの平均を表し、これはグラフを走査して希望する近傍を見つける距離を最小化するのに役立つ。

2. 近傍探索：アルゴリズムは、現在のノードのエッジから潜在的な近傍候補（図中の赤丸）を収集し、メモリ内のPQコードを活用して、これらの候補とクエリーベクトル間の距離を近似する。これらの潜在的な隣接候補は、Vamanaグラフのエッジを介して選択されたエントリーポイントに直接接続されているノードです。

3. 正確な距離計算のためのノードの選択：近似結果から、最も有望な近隣ノードのサブセット（図中の緑色の丸）が、圧縮されていない元のベクトルを使用して正確な距離評価のために選択されます。これにはディスクからデータを読み込む必要があり、時間がかかります。DISKANNはこの精度とスピードの微妙なバランスをコントロールするために2つのパラメータを使用します：

   • beam_width_ratio:探索の幅を制御する比率で、近傍探索のためにいくつの近傍候補が並列に選択されるかを決定する。beam_width_ratio を大きくすると探索範囲が広くなり、精度が向上する可能性がありますが、計算コストとディスクI/Oが増加します。ビーム幅、つまり選択されるノードの数は、以下の式で決定されます：Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio:頻繁にアクセスされるディスクデータをキャッシュするために割り当てられるメモリの割合。このキャッシングはディスクI/Oを最小化するのに役立ち、データがすでにメモリ内にあるため、繰り返しの検索が速くなります。

   パラメータチューニングの詳細については、DISKANN configsを参照してください。

4. 反復探索：十分な数の近傍が見つかるまで、近似評価（PQを使用）と正確なチェック（ディスクから元のベクトルを使用）を繰り返しながら、候補の集合を繰り返し改良します。

MilvusでDISKANNを有効にする

デフォルトでは、MilvusのDISKANNは無効になっており、RAMに快適に収まるデータセットのために、インメモリインデックスの速度を優先しています。しかし、大規模なデータセットを扱う場合や、DISKANNのスケーラビリティとSSD最適化を利用したい場合は、簡単に有効にすることができます。

MilvusでDISKANNを有効にする方法は以下の通りです：

1. Milvus設定ファイルの更新

   1. Milvusの設定ファイルを探します。(このファイルの見つけ方の詳細については、Milvusの設定に関するドキュメントを参照してください)。

   2. queryNode.enableDisk パラメータを見つけ、その値をtrue に設定する：

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

2. DISKANN 用ストレージの最適化

DISKANNで最高のパフォーマンスを得るためには、Milvusのデータを高速なNVMe SSDに保存することをお勧めします。ここでは、Milvusスタンドアロンとクラスタの両方について、この方法を説明します：

• Milvus Standaloneの場合

  • Milvusコンテナ内のNVMe SSDにMilvusデータディレクトリをマウントします。これは、docker-compose.yml ファイルまたは他のコンテナ管理ツールを使用して行うことができます。

  • たとえば、NVMe SSDが/mnt/nvme にマウントされている場合、docker-compose.yml のvolumesセクションを次のように更新します：

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

• Milvusクラスタ

  • QueryNodeとIndexNodeコンテナの両方で、MilvusデータディレクトリをNVMe SSDにマウントします。これは、コンテナ・オーケストレーション・セットアップで実現できます。

  • 両方のノードタイプでNVMe SSDにデータをマウントすることで、検索とインデックス作成の両方の操作で高速な読み取りと書き込み速度を確保できます。

これらの変更を行ったら、Milvusインスタンスを再起動して設定を有効にします。これで、MilvusはDISKANNの機能を活用して大規模なデータセットを処理し、効率的でスケーラブルなベクトル検索を実現します。

DISKANNの設定

DISKANN関連のパラメータは、Milvusの設定ファイル(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

パラメータの詳細については、DISKANN paramsを参照してください。

DISKANN パラメータ

DISKANN のパラメータを微調整することで、特定のデータセットや検索ワークロードに合わせて、速度、精度、メモリ使用量の適切なバランスをとりながら、DISKANN の動作を調整することができます。

インデックス構築パラメータ

これらのパラメータは、DISKANNインデックスがどのように構築されるかに影響します。これらを調整することで、インデックスのサイズ、構築時間、検索品質に影響を与えることができます。

	パラメータ	説明	値の範囲	チューニングサジェスチョン
Vamana	MaxDegree	Vamanaグラフで各データポイントが持つことのできる接続（エッジ）の最大数を制御する。	タイプ整数Range：[1, 512] デフォルト値：56	値を大きくするとグラフが密になり、リコール（より関連性の高い結果を見つけること）が増加する可能性がありますが、メモリ使用量とビルド時間も増加します。 ほとんどの場合、この範囲内の値を設定することをお勧めします：[10, 100].
	SearchListSize	インデックス構築中、このパラメータは各ノードの最近傍を検索する際に使用される候補プールのサイズを定義します。グラフに追加される各ノードに対して、アルゴリズムはこれまでに見つかった最良の候補search_list_size のリストを保持します。このリストが改善されなくなると、近傍探索は停止する。この最終候補プールから、上位max_degree ノードが選択され、最終的なエッジを形成する。	タイプ整数Range：[1,int_max］ デフォルト値：100	search_list_size を大きくすると、各ノードの真の最近傍を見つける可能性が高くなり、より高品質なグラフと検索パフォーマンス（リコール）を向上させることができる。しかし、その代償としてインデックス構築時間が大幅に長くなります。これは常にmax_degree 以上の値に設定されるべきである。
	SearchCacheBudgetGBRatio	インデックス構築時に、グラフの頻繁にアクセスされる部分をキャッシュするために割り当てられるメモリの量を制御する。	タイプ：Floatレンジ：[0.0, 0.3) デフォルト値：0.10	高い値を指定すると、キャッシュのためにより多くのメモリが割り当てられ、ディスクI/Oが大幅に削減されるが、より多くのシステムメモリを消費する。ほとんどの場合、この範囲内の値を設定することをお勧めします：[0.0, 0.3).
PQ	PQCodeBudgetGBRatio	非圧縮データのサイズと比較したPQコード（データポイントの圧縮表現）のサイズを制御する。	タイプ：Float範囲：（0.0, 0.25］ デフォルト値：0.125	比率が高いほど、PQ コードに割り当てるメモリの割合が大きくなり、元のベクトルに関するより多くの情報が効果的に格納されるため、より正確な検索結果が得られる。比率を低くすると、メモリ使用量は減りますが、PQコードの保持する情報が少なくなるため、精度が犠牲になる可能性があります。この方法は、メモリ制約が懸念されるシナリオに適しており、より大きなデータセットのインデックス作成が可能になる可能性があります。 ほとんどの場合、この範囲内の値を設定することを推奨する: (0.0625, 0.25])

インデックス固有の検索パラメータ

これらのパラメータはDISKANNがどのように検索を行うかに影響します。これらのパラメータを調整することで、検索速度、待ち時間、リソースの使用量に影響を与えることができます。

	パラメータ	説明	値の範囲	チューニング案
Vamana	BeamWidthRatio	利用可能なCPUコア数に対する並列ディスクI/Oリクエストの最大数を決定することにより、検索中の並列性の程度を制御する。	タイプFloatレンジ：[1, max(128 / CPU数, 16)] を指定する。 デフォルト値：4.0	値を高くすると並列性が高まり、強力な CPU と SSD を持つシステムでの検索を高速化できる。ほとんどの場合、この範囲内の値を設定することを推奨する：[1.0, 4.0].
	search_list	検索操作中、このパラメータは、アルゴリズムがグラフを横断する際に維持する候補プールのサイズを決定します。値を大きくすると、真の最近傍を見つける可能性が高くなりますが（より高いリコール）、検索の待ち時間も長くなります。	タイプ整数：[1,int_max］ デフォルト値：100	パフォーマンスと精度のバランスをとるために、この値は検索したい結果の数(top_k)と等しいか、少し大きく設定することを推奨する。